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_set/1
54 * is_subset/2
56 * new/0
58 * size/1
60 * subtract/2
62 * to_list/1
64 * union/1
66 * union/2
68
70 set(Element)
71 A general balanced set.
73 set() = set(term())
75 iter(Element)
77 A general balanced set iterator.
79 iter() = iter(term())
81
83 add(Element, Set1) -> Set2
84 add_element(Element, Set1) -> Set2
86 Types:
88 Set1 = Set2 = set(Element)
90 Returns a new set formed from Set1 with Element inserted. If
92 Element is already an element in Set1, nothing is changed.
93 balance(Set1) -> Set2
95 Types:
97 Set1 = Set2 = set(Element)
99 Rebalances the tree representation of Set1. Notice that this is
101 rarely necessary, but can be motivated when a large number of
102 elements have been deleted from the tree without further inser‐
103 tions. Rebalancing can then be forced to minimise lookup times,
104 as deletion does not rebalance the tree.
105 del_element(Element, Set1) -> Set2
107 Types:
109 Set1 = Set2 = set(Element)
111 Returns a new set formed from Set1 with Element removed. If Ele‐
113 ment is not an element in Set1, nothing is changed.
114 delete(Element, Set1) -> Set2
116 Types:
118 Set1 = Set2 = set(Element)
120 Returns a new set formed from Set1 with Element removed. Assumes
122 that Element is present in Set1.
123 delete_any(Element, Set1) -> Set2
125 Types:
127 Set1 = Set2 = set(Element)
129 Returns a new set formed from Set1 with Element removed. If Ele‐
131 ment is not an element in Set1, nothing is changed.
132 difference(Set1, Set2) -> Set3
134 Types:
136 Set1 = Set2 = Set3 = set(Element)
138 Returns only the elements of Set1 that are not also elements of
140 Set2.
141 empty() -> Set
143 Types:
145 Set = set()
147 Returns a new empty set.
149 filter(Pred, Set1) -> Set2
151 Types:
153 Pred = fun((Element) -> boolean())
155 Set1 = Set2 = set(Element)
156 Filters elements in Set1 using predicate function Pred.
158 fold(Function, Acc0, Set) -> Acc1
160 Types:
162 Function = fun((Element, AccIn) -> AccOut)
164 Acc0 = Acc1 = AccIn = AccOut = Acc
165 Set = set(Element)
166 Folds Function over every element in Set returning the final
168 value of the accumulator.
169 from_list(List) -> Set
171 Types:
173 List = [Element]
175 Set = set(Element)
176 Returns a set of the elements in List, where List can be
178 unordered and contain duplicates.
179 from_ordset(List) -> Set
181 Types:
183 List = [Element]
185 Set = set(Element)
186 Turns an ordered-set list List into a set. The list must not
188 contain duplicates.
189 insert(Element, Set1) -> Set2
191 Types:
193 Set1 = Set2 = set(Element)
195 Returns a new set formed from Set1 with Element inserted.
197 Assumes that Element is not present in Set1.
198 intersection(SetList) -> Set
200 Types:
202 SetList = [set(Element), ...]
204 Set = set(Element)
205 Returns the intersection of the non-empty list of sets.
207 intersection(Set1, Set2) -> Set3
209 Types:
211 Set1 = Set2 = Set3 = set(Element)
213 Returns the intersection of Set1 and Set2.
215 is_disjoint(Set1, Set2) -> boolean()
217 Types:
219 Set1 = Set2 = set(Element)
221 Returns true if Set1 and Set2 are disjoint (have no elements in
223 common), otherwise false.
224 is_element(Element, Set) -> boolean()
226 Types:
228 Set = set(Element)
230 Returns true if Element is an element of Set, otherwise false.
232 is_empty(Set) -> boolean()
234 Types:
236 Set = set()
238 Returns true if Set is an empty set, otherwise false.
240 is_member(Element, Set) -> boolean()
242 Types:
244 Set = set(Element)
246 Returns true if Element is an element of Set, otherwise false.
248 is_set(Term) -> boolean()
250 Types:
252 Term = term()
254 Returns true if Term appears to be a set, otherwise false.
256 is_subset(Set1, Set2) -> boolean()
258 Types:
260 Set1 = Set2 = set(Element)
262 Returns true when every element of Set1 is also a member of
264 Set2, otherwise false.
265 iterator(Set) -> Iter
267 Types:
269 Set = set(Element)
271 Iter = iter(Element)
272 Returns an iterator that can be used for traversing the entries
274 of Set; see next/1. The implementation of this is very effi‐
275 cient; traversing the whole set using next/1 is only slightly
276 slower than getting the list of all elements using to_list/1 and
277 traversing that. The main advantage of the iterator approach is
278 that it does not require the complete list of all elements to be
279 built in memory at one time.
280 iterator_from(Element, Set) -> Iter
282 Types:
284 Set = set(Element)
286 Iter = iter(Element)
287 Returns an iterator that can be used for traversing the entries
289 of Set; see next/1. The difference as compared to the iterator
290 returned by iterator/1 is that the first element greater than or
291 equal to Element is returned.
292 largest(Set) -> Element
294 Types:
296 Set = set(Element)
298 Returns the largest element in Set. Assumes that Set is not
300 empty.
301 new() -> Set
303 Types:
305 Set = set()
307 Returns a new empty set.
309 next(Iter1) -> {Element, Iter2} | none
311 Types:
313 Iter1 = Iter2 = iter(Element)
315 Returns {Element, Iter2}, where Element is the smallest element
317 referred to by iterator Iter1, and Iter2 is the new iterator to
318 be used for traversing the remaining elements, or the atom none
319 if no elements remain.
320 singleton(Element) -> set(Element)
322 Returns a set containing only element Element.
324 size(Set) -> integer() >= 0
326 Types:
328 Set = set()
330 Returns the number of elements in Set.
332 smallest(Set) -> Element
334 Types:
336 Set = set(Element)
338 Returns the smallest element in Set. Assumes that Set is not
340 empty.
341 subtract(Set1, Set2) -> Set3
343 Types:
345 Set1 = Set2 = Set3 = set(Element)
347 Returns only the elements of Set1 that are not also elements of
349 Set2.
350 take_largest(Set1) -> {Element, Set2}
352 Types:
354 Set1 = Set2 = set(Element)
356 Returns {Element, Set2}, where Element is the largest element in
358 Set1, and Set2 is this set with Element deleted. Assumes that
359 Set1 is not empty.
360 take_smallest(Set1) -> {Element, Set2}
362 Types:
364 Set1 = Set2 = set(Element)
366 Returns {Element, Set2}, where Element is the smallest element
368 in Set1, and Set2 is this set with Element deleted. Assumes that
369 Set1 is not empty.
370 to_list(Set) -> List
372 Types:
374 Set = set(Element)
376 List = [Element]
377 Returns the elements of Set as a list.
379 union(SetList) -> Set
381 Types:
383 SetList = [set(Element), ...]
385 Set = set(Element)
386 Returns the merged (union) set of the list of sets.
388 union(Set1, Set2) -> Set3
390 Types:
392 Set1 = Set2 = Set3 = set(Element)
394 Returns the merged (union) set of Set1 and Set2.
396
398 gb_trees(3), ordsets(3), sets(3)
399Ericsson AB stdlib 3.4.5.1 gb_sets(3)