1gb_sets(3)                 Erlang Module Definition                 gb_sets(3)
2
3
4

NAME

6       gb_sets - General balanced trees.
7

DESCRIPTION

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
13       This  module considers two elements as different if and only if they do
14       not compare equal (==).
15

COMPLEXITY NOTE

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
28       As with normal tree structures, lookup (membership testing), insertion,
29       and deletion have logarithmic complexity.
30

COMPATIBILITY

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
37         * add_element/2
38
39         * del_element/2
40
41         * filter/2
42
43         * fold/3
44
45         * from_list/1
46
47         * intersection/1
48
49         * intersection/2
50
51         * is_element/2
52
53         * is_empty/1
54
55         * is_set/1
56
57         * is_subset/2
58
59         * new/0
60
61         * size/1
62
63         * subtract/2
64
65         * to_list/1
66
67         * union/1
68
69         * union/2
70

DATA TYPES

72       set(Element)
73
74              A general balanced set.
75
76       set() = set(term())
77
78       iter(Element)
79
80              A general balanced set iterator.
81
82       iter() = iter(term())
83

EXPORTS

85       add(Element, Set1) -> Set2
86
87       add_element(Element, Set1) -> Set2
88
89              Types:
90
91                 Set1 = Set2 = set(Element)
92
93              Returns  a  new  set  formed from Set1 with Element inserted. If
94              Element is already an element in Set1, nothing is changed.
95
96       balance(Set1) -> Set2
97
98              Types:
99
100                 Set1 = Set2 = set(Element)
101
102              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
108       del_element(Element, Set1) -> Set2
109
110              Types:
111
112                 Set1 = Set2 = set(Element)
113
114              Returns a new set formed from Set1 with Element removed. If Ele‐
115              ment is not an element in Set1, nothing is changed.
116
117       delete(Element, Set1) -> Set2
118
119              Types:
120
121                 Set1 = Set2 = set(Element)
122
123              Returns a new set formed from Set1 with Element removed. Assumes
124              that Element is present in Set1.
125
126       delete_any(Element, Set1) -> Set2
127
128              Types:
129
130                 Set1 = Set2 = set(Element)
131
132              Returns a new set formed from Set1 with Element removed. If Ele‐
133              ment is not an element in Set1, nothing is changed.
134
135       difference(Set1, Set2) -> Set3
136
137              Types:
138
139                 Set1 = Set2 = Set3 = set(Element)
140
141              Returns  only the elements of Set1 that are not also elements of
142              Set2.
143
144       empty() -> Set
145
146              Types:
147
148                 Set = set()
149
150              Returns a new empty set.
151
152       filter(Pred, Set1) -> Set2
153
154              Types:
155
156                 Pred = fun((Element) -> boolean())
157                 Set1 = Set2 = set(Element)
158
159              Filters elements in Set1 using predicate function Pred.
160
161       fold(Function, Acc0, Set) -> Acc1
162
163              Types:
164
165                 Function = fun((Element, AccIn) -> AccOut)
166                 Acc0 = Acc1 = AccIn = AccOut = Acc
167                 Set = set(Element)
168
169              Folds Function over every element in  Set  returning  the  final
170              value of the accumulator.
171
172       from_list(List) -> Set
173
174              Types:
175
176                 List = [Element]
177                 Set = set(Element)
178
179              Returns  a  set  of  the  elements  in  List,  where List can be
180              unordered and contain duplicates.
181
182       from_ordset(List) -> Set
183
184              Types:
185
186                 List = [Element]
187                 Set = set(Element)
188
189              Turns an ordered-set list List into a set.  The  list  must  not
190              contain duplicates.
191
192       insert(Element, Set1) -> Set2
193
194              Types:
195
196                 Set1 = Set2 = set(Element)
197
198              Returns  a  new  set  formed  from  Set1  with Element inserted.
199              Assumes that Element is not present in Set1.
200
201       intersection(SetList) -> Set
202
203              Types:
204
205                 SetList = [set(Element), ...]
206                 Set = set(Element)
207
208              Returns the intersection of the non-empty list of sets.
209
210       intersection(Set1, Set2) -> Set3
211
212              Types:
213
214                 Set1 = Set2 = Set3 = set(Element)
215
216              Returns the intersection of Set1 and Set2.
217
218       is_disjoint(Set1, Set2) -> boolean()
219
220              Types:
221
222                 Set1 = Set2 = set(Element)
223
224              Returns true if Set1 and Set2 are disjoint (have no elements  in
225              common), otherwise false.
226
227       is_element(Element, Set) -> boolean()
228
229              Types:
230
231                 Set = set(Element)
232
233              Returns true if Element is an element of Set, otherwise false.
234
235       is_empty(Set) -> boolean()
236
237              Types:
238
239                 Set = set()
240
241              Returns true if Set is an empty set, otherwise false.
242
243       is_member(Element, Set) -> boolean()
244
245              Types:
246
247                 Set = set(Element)
248
249              Returns true if Element is an element of Set, otherwise false.
250
251       is_set(Term) -> boolean()
252
253              Types:
254
255                 Term = term()
256
257              Returns true if Term appears to be a set, otherwise false.
258
259       is_subset(Set1, Set2) -> boolean()
260
261              Types:
262
263                 Set1 = Set2 = set(Element)
264
265              Returns  true  when  every  element  of Set1 is also a member of
266              Set2, otherwise false.
267
268       iterator(Set) -> Iter
269
270              Types:
271
272                 Set = set(Element)
273                 Iter = iter(Element)
274
275              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
283       iterator_from(Element, Set) -> Iter
284
285              Types:
286
287                 Set = set(Element)
288                 Iter = iter(Element)
289
290              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
295       largest(Set) -> Element
296
297              Types:
298
299                 Set = set(Element)
300
301              Returns  the  largest  element  in  Set. Assumes that Set is not
302              empty.
303
304       new() -> Set
305
306              Types:
307
308                 Set = set()
309
310              Returns a new empty set.
311
312       next(Iter1) -> {Element, Iter2} | none
313
314              Types:
315
316                 Iter1 = Iter2 = iter(Element)
317
318              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
323       singleton(Element) -> set(Element)
324
325              Returns a set containing only element Element.
326
327       size(Set) -> integer() >= 0
328
329              Types:
330
331                 Set = set()
332
333              Returns the number of elements in Set.
334
335       smallest(Set) -> Element
336
337              Types:
338
339                 Set = set(Element)
340
341              Returns  the  smallest  element  in Set. Assumes that Set is not
342              empty.
343
344       subtract(Set1, Set2) -> Set3
345
346              Types:
347
348                 Set1 = Set2 = Set3 = set(Element)
349
350              Returns only the elements of Set1 that are not also elements  of
351              Set2.
352
353       take_largest(Set1) -> {Element, Set2}
354
355              Types:
356
357                 Set1 = Set2 = set(Element)
358
359              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
363       take_smallest(Set1) -> {Element, Set2}
364
365              Types:
366
367                 Set1 = Set2 = set(Element)
368
369              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
373       to_list(Set) -> List
374
375              Types:
376
377                 Set = set(Element)
378                 List = [Element]
379
380              Returns the elements of Set as a list.
381
382       union(SetList) -> Set
383
384              Types:
385
386                 SetList = [set(Element), ...]
387                 Set = set(Element)
388
389              Returns the merged (union) set of the list of sets.
390
391       union(Set1, Set2) -> Set3
392
393              Types:
394
395                 Set1 = Set2 = Set3 = set(Element)
396
397              Returns the merged (union) set of Set1 and Set2.
398

SEE ALSO

400       gb_trees(3), ordsets(3), sets(3)
401
402
403
404Ericsson AB                     stdlib 3.8.2.1                      gb_sets(3)
Impressum