1gb_sets(3) Erlang Module Definition gb_sets(3)
2
6 gb_sets - Sets represented by 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 or‐
11 dered lists, for larger sets, but depends on the application.
12 The data representing a set as used by this module is to be regarded as
14 opaque by other modules. In abstract terms, the representation is a
15 composite type of existing Erlang terms. See note on data types. Any
16 code assuming knowledge of the format is running on thin ice.
17 This module considers two elements as different if and only if they do
19 not compare equal (==).
20
22 The complexity on set operations is bounded by either O(|S|) or O(|T| *
23 log(|S|)), where S is the largest given set, depending on which is
24 fastest for any particular function call. For operating on sets of al‐
25 most equal size, this implementation is about 3 times slower than using
26 ordered-list sets directly. For sets of very different sizes, however,
27 this solution can be arbitrarily much faster; in practical cases, often
28 10-100 times. This implementation is particularly suited for accumulat‐
29 ing elements a few at a time, building up a large set (> 100-200 ele‐
30 ments), and repeatedly testing for membership in the current set.
31 As with normal tree structures, lookup (membership testing), insertion,
33 and deletion have logarithmic complexity.
34
36 The following functions in this module also exist and provides the same
37 functionality in the sets(3) and ordsets(3) modules. That is, by only
38 changing the module name for each call, you can try out different set
39 representations.
40 * add_element/2
42 * del_element/2
44 * filter/2
46 * fold/3
48 * from_list/1
50 * intersection/1
52 * intersection/2
54 * is_element/2
56 * is_empty/1
58 * is_set/1
60 * is_subset/2
62 * new/0
64 * size/1
66 * subtract/2
68 * to_list/1
70 * union/1
72 * union/2
74
76 set(Element)
77 A general balanced set.
79 set() = set(term())
81 iter(Element)
83 A general balanced set iterator.
85 iter() = iter(term())
87
89 add(Element, Set1) -> Set2
90 add_element(Element, Set1) -> Set2
92 Types:
94 Set1 = Set2 = set(Element)
96 Returns a new set formed from Set1 with Element inserted. If El‐
98 ement is already an element in Set1, nothing is changed.
99 balance(Set1) -> Set2
101 Types:
103 Set1 = Set2 = set(Element)
105 Rebalances the tree representation of Set1. Notice that this is
107 rarely necessary, but can be motivated when a large number of
108 elements have been deleted from the tree without further inser‐
109 tions. Rebalancing can then be forced to minimise lookup times,
110 as deletion does not rebalance the tree.
111 del_element(Element, Set1) -> Set2
113 Types:
115 Set1 = Set2 = set(Element)
117 Returns a new set formed from Set1 with Element removed. If Ele‐
119 ment is not an element in Set1, nothing is changed.
120 delete(Element, Set1) -> Set2
122 Types:
124 Set1 = Set2 = set(Element)
126 Returns a new set formed from Set1 with Element removed. Assumes
128 that Element is present in Set1.
129 delete_any(Element, Set1) -> Set2
131 Types:
133 Set1 = Set2 = set(Element)
135 Returns a new set formed from Set1 with Element removed. If Ele‐
137 ment is not an element in Set1, nothing is changed.
138 difference(Set1, Set2) -> Set3
140 Types:
142 Set1 = Set2 = Set3 = set(Element)
144 Returns only the elements of Set1 that are not also elements of
146 Set2.
147 empty() -> Set
149 Types:
151 Set = set()
153 Returns a new empty set.
155 filter(Pred, Set1) -> Set2
157 Types:
159 Pred = fun((Element) -> boolean())
161 Set1 = Set2 = set(Element)
162 Filters elements in Set1 using predicate function Pred.
164 fold(Function, Acc0, Set) -> Acc1
166 Types:
168 Function = fun((Element, AccIn) -> AccOut)
170 Acc0 = Acc1 = AccIn = AccOut = Acc
171 Set = set(Element)
172 Folds Function over every element in Set returning the final
174 value of the accumulator.
175 from_list(List) -> Set
177 Types:
179 List = [Element]
181 Set = set(Element)
182 Returns a set of the elements in List, where List can be un‐
184 ordered and contain duplicates.
185 from_ordset(List) -> Set
187 Types:
189 List = [Element]
191 Set = set(Element)
192 Turns an ordered-set list List into a set. The list must not
194 contain duplicates.
195 insert(Element, Set1) -> Set2
197 Types:
199 Set1 = Set2 = set(Element)
201 Returns a new set formed from Set1 with Element inserted. As‐
203 sumes that Element is not present in Set1.
204 intersection(SetList) -> Set
206 Types:
208 SetList = [set(Element), ...]
210 Set = set(Element)
211 Returns the intersection of the non-empty list of sets.
213 intersection(Set1, Set2) -> Set3
215 Types:
217 Set1 = Set2 = Set3 = set(Element)
219 Returns the intersection of Set1 and Set2.
221 is_disjoint(Set1, Set2) -> boolean()
223 Types:
225 Set1 = Set2 = set(Element)
227 Returns true if Set1 and Set2 are disjoint (have no elements in
229 common), otherwise false.
230 is_element(Element, Set) -> boolean()
232 Types:
234 Set = set(Element)
236 Returns true if Element is an element of Set, otherwise false.
238 is_empty(Set) -> boolean()
240 Types:
242 Set = set()
244 Returns true if Set is an empty set, otherwise false.
246 is_member(Element, Set) -> boolean()
248 Types:
250 Set = set(Element)
252 Returns true if Element is an element of Set, otherwise false.
254 is_set(Term) -> boolean()
256 Types:
258 Term = term()
260 Returns true if Term appears to be a set, otherwise false. This
262 function will return true for any term that coincides with the
263 representation of a gb_set, while not really being a gb_set,
264 thus it might return false positive results. See also note on
265 data types.
266 is_subset(Set1, Set2) -> boolean()
268 Types:
270 Set1 = Set2 = set(Element)
272 Returns true when every element of Set1 is also a member of
274 Set2, otherwise false.
275 iterator(Set) -> Iter
277 Types:
279 Set = set(Element)
281 Iter = iter(Element)
282 Returns an iterator that can be used for traversing the entries
284 of Set; see next/1. The implementation of this is very effi‐
285 cient; traversing the whole set using next/1 is only slightly
286 slower than getting the list of all elements using to_list/1 and
287 traversing that. The main advantage of the iterator approach is
288 that it does not require the complete list of all elements to be
289 built in memory at one time.
290 iterator_from(Element, Set) -> Iter
292 Types:
294 Set = set(Element)
296 Iter = iter(Element)
297 Returns an iterator that can be used for traversing the entries
299 of Set; see next/1. The difference as compared to the iterator
300 returned by iterator/1 is that the first element greater than or
301 equal to Element is returned.
302 largest(Set) -> Element
304 Types:
306 Set = set(Element)
308 Returns the largest element in Set. Assumes that Set is not
310 empty.
311 new() -> Set
313 Types:
315 Set = set()
317 Returns a new empty set.
319 next(Iter1) -> {Element, Iter2} | none
321 Types:
323 Iter1 = Iter2 = iter(Element)
325 Returns {Element, Iter2}, where Element is the smallest element
327 referred to by iterator Iter1, and Iter2 is the new iterator to
328 be used for traversing the remaining elements, or the atom none
329 if no elements remain.
330 singleton(Element) -> set(Element)
332 Returns a set containing only element Element.
334 size(Set) -> integer() >= 0
336 Types:
338 Set = set()
340 Returns the number of elements in Set.
342 smallest(Set) -> Element
344 Types:
346 Set = set(Element)
348 Returns the smallest element in Set. Assumes that Set is not
350 empty.
351 subtract(Set1, Set2) -> Set3
353 Types:
355 Set1 = Set2 = Set3 = set(Element)
357 Returns only the elements of Set1 that are not also elements of
359 Set2.
360 take_largest(Set1) -> {Element, Set2}
362 Types:
364 Set1 = Set2 = set(Element)
366 Returns {Element, Set2}, where Element is the largest element in
368 Set1, and Set2 is this set with Element deleted. Assumes that
369 Set1 is not empty.
370 take_smallest(Set1) -> {Element, Set2}
372 Types:
374 Set1 = Set2 = set(Element)
376 Returns {Element, Set2}, where Element is the smallest element
378 in Set1, and Set2 is this set with Element deleted. Assumes that
379 Set1 is not empty.
380 to_list(Set) -> List
382 Types:
384 Set = set(Element)
386 List = [Element]
387 Returns the elements of Set as a list.
389 union(SetList) -> Set
391 Types:
393 SetList = [set(Element), ...]
395 Set = set(Element)
396 Returns the merged (union) set of the list of sets.
398 union(Set1, Set2) -> Set3
400 Types:
402 Set1 = Set2 = Set3 = set(Element)
404 Returns the merged (union) set of Set1 and Set2.
406
408 gb_trees(3), ordsets(3), sets(3)
409Ericsson AB stdlib 4.2 gb_sets(3)