1gb_sets(3) Erlang Module Definition gb_sets(3)
2
6 gb_sets - General balanced trees.
7
9 This module provides ordered sets using Prof. Arne Andersson's General
10 Balanced Trees. Ordered sets can be much more efficient than using
11 ordered lists, for larger sets, but depends on the application.
12 This module considers two elements as different if and only if they do
14 not compare equal (==).
15
17 The complexity on set operations is bounded by either O(|S|) or O(|T| *
18 log(|S|)), where S is the largest given set, depending on which is
19 fastest for any particular function call. For operating on sets of
20 almost equal size, this implementation is about 3 times slower than
21 using ordered-list sets directly. For sets of very different sizes,
22 however, this solution can be arbitrarily much faster; in practical
23 cases, often 10-100 times. This implementation is particularly suited
24 for accumulating elements a few at a time, building up a large set (>
25 100-200 elements), and repeatedly testing for membership in the current
26 set.
27 As with normal tree structures, lookup (membership testing), insertion,
29 and deletion have logarithmic complexity.
30
32 The following functions in this module also exist and provides the same
33 functionality in the sets(3) and ordsets(3) modules. That is, by only
34 changing the module name for each call, you can try out different set
35 representations.
36 * add_element/2
38 * del_element/2
40 * filter/2
42 * fold/3
44 * from_list/1
46 * intersection/1
48 * intersection/2
50 * is_element/2
52 * is_empty/1
54 * is_set/1
56 * is_subset/2
58 * new/0
60 * size/1
62 * subtract/2
64 * to_list/1
66 * union/1
68 * union/2
70
72 set(Element)
73 A general balanced set.
75 set() = set(term())
77 iter(Element)
79 A general balanced set iterator.
81 iter() = iter(term())
83
85 add(Element, Set1) -> Set2
86 add_element(Element, Set1) -> Set2
88 Types:
90 Set1 = Set2 = set(Element)
92 Returns a new set formed from Set1 with Element inserted. If
94 Element is already an element in Set1, nothing is changed.
95 balance(Set1) -> Set2
97 Types:
99 Set1 = Set2 = set(Element)
101 Rebalances the tree representation of Set1. Notice that this is
103 rarely necessary, but can be motivated when a large number of
104 elements have been deleted from the tree without further inser‐
105 tions. Rebalancing can then be forced to minimise lookup times,
106 as deletion does not rebalance the tree.
107 del_element(Element, Set1) -> Set2
109 Types:
111 Set1 = Set2 = set(Element)
113 Returns a new set formed from Set1 with Element removed. If Ele‐
115 ment is not an element in Set1, nothing is changed.
116 delete(Element, Set1) -> Set2
118 Types:
120 Set1 = Set2 = set(Element)
122 Returns a new set formed from Set1 with Element removed. Assumes
124 that Element is present in Set1.
125 delete_any(Element, Set1) -> Set2
127 Types:
129 Set1 = Set2 = set(Element)
131 Returns a new set formed from Set1 with Element removed. If Ele‐
133 ment is not an element in Set1, nothing is changed.
134 difference(Set1, Set2) -> Set3
136 Types:
138 Set1 = Set2 = Set3 = set(Element)
140 Returns only the elements of Set1 that are not also elements of
142 Set2.
143 empty() -> Set
145 Types:
147 Set = set()
149 Returns a new empty set.
151 filter(Pred, Set1) -> Set2
153 Types:
155 Pred = fun((Element) -> boolean())
157 Set1 = Set2 = set(Element)
158 Filters elements in Set1 using predicate function Pred.
160 fold(Function, Acc0, Set) -> Acc1
162 Types:
164 Function = fun((Element, AccIn) -> AccOut)
166 Acc0 = Acc1 = AccIn = AccOut = Acc
167 Set = set(Element)
168 Folds Function over every element in Set returning the final
170 value of the accumulator.
171 from_list(List) -> Set
173 Types:
175 List = [Element]
177 Set = set(Element)
178 Returns a set of the elements in List, where List can be
180 unordered and contain duplicates.
181 from_ordset(List) -> Set
183 Types:
185 List = [Element]
187 Set = set(Element)
188 Turns an ordered-set list List into a set. The list must not
190 contain duplicates.
191 insert(Element, Set1) -> Set2
193 Types:
195 Set1 = Set2 = set(Element)
197 Returns a new set formed from Set1 with Element inserted.
199 Assumes that Element is not present in Set1.
200 intersection(SetList) -> Set
202 Types:
204 SetList = [set(Element), ...]
206 Set = set(Element)
207 Returns the intersection of the non-empty list of sets.
209 intersection(Set1, Set2) -> Set3
211 Types:
213 Set1 = Set2 = Set3 = set(Element)
215 Returns the intersection of Set1 and Set2.
217 is_disjoint(Set1, Set2) -> boolean()
219 Types:
221 Set1 = Set2 = set(Element)
223 Returns true if Set1 and Set2 are disjoint (have no elements in
225 common), otherwise false.
226 is_element(Element, Set) -> boolean()
228 Types:
230 Set = set(Element)
232 Returns true if Element is an element of Set, otherwise false.
234 is_empty(Set) -> boolean()
236 Types:
238 Set = set()
240 Returns true if Set is an empty set, otherwise false.
242 is_member(Element, Set) -> boolean()
244 Types:
246 Set = set(Element)
248 Returns true if Element is an element of Set, otherwise false.
250 is_set(Term) -> boolean()
252 Types:
254 Term = term()
256 Returns true if Term appears to be a set, otherwise false.
258 is_subset(Set1, Set2) -> boolean()
260 Types:
262 Set1 = Set2 = set(Element)
264 Returns true when every element of Set1 is also a member of
266 Set2, otherwise false.
267 iterator(Set) -> Iter
269 Types:
271 Set = set(Element)
273 Iter = iter(Element)
274 Returns an iterator that can be used for traversing the entries
276 of Set; see next/1. The implementation of this is very effi‐
277 cient; traversing the whole set using next/1 is only slightly
278 slower than getting the list of all elements using to_list/1 and
279 traversing that. The main advantage of the iterator approach is
280 that it does not require the complete list of all elements to be
281 built in memory at one time.
282 iterator_from(Element, Set) -> Iter
284 Types:
286 Set = set(Element)
288 Iter = iter(Element)
289 Returns an iterator that can be used for traversing the entries
291 of Set; see next/1. The difference as compared to the iterator
292 returned by iterator/1 is that the first element greater than or
293 equal to Element is returned.
294 largest(Set) -> Element
296 Types:
298 Set = set(Element)
300 Returns the largest element in Set. Assumes that Set is not
302 empty.
303 new() -> Set
305 Types:
307 Set = set()
309 Returns a new empty set.
311 next(Iter1) -> {Element, Iter2} | none
313 Types:
315 Iter1 = Iter2 = iter(Element)
317 Returns {Element, Iter2}, where Element is the smallest element
319 referred to by iterator Iter1, and Iter2 is the new iterator to
320 be used for traversing the remaining elements, or the atom none
321 if no elements remain.
322 singleton(Element) -> set(Element)
324 Returns a set containing only element Element.
326 size(Set) -> integer() >= 0
328 Types:
330 Set = set()
332 Returns the number of elements in Set.
334 smallest(Set) -> Element
336 Types:
338 Set = set(Element)
340 Returns the smallest element in Set. Assumes that Set is not
342 empty.
343 subtract(Set1, Set2) -> Set3
345 Types:
347 Set1 = Set2 = Set3 = set(Element)
349 Returns only the elements of Set1 that are not also elements of
351 Set2.
352 take_largest(Set1) -> {Element, Set2}
354 Types:
356 Set1 = Set2 = set(Element)
358 Returns {Element, Set2}, where Element is the largest element in
360 Set1, and Set2 is this set with Element deleted. Assumes that
361 Set1 is not empty.
362 take_smallest(Set1) -> {Element, Set2}
364 Types:
366 Set1 = Set2 = set(Element)
368 Returns {Element, Set2}, where Element is the smallest element
370 in Set1, and Set2 is this set with Element deleted. Assumes that
371 Set1 is not empty.
372 to_list(Set) -> List
374 Types:
376 Set = set(Element)
378 List = [Element]
379 Returns the elements of Set as a list.
381 union(SetList) -> Set
383 Types:
385 SetList = [set(Element), ...]
387 Set = set(Element)
388 Returns the merged (union) set of the list of sets.
390 union(Set1, Set2) -> Set3
392 Types:
394 Set1 = Set2 = Set3 = set(Element)
396 Returns the merged (union) set of Set1 and Set2.
398
400 gb_trees(3), ordsets(3), sets(3)
401Ericsson AB stdlib 3.8.2.1 gb_sets(3)