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

NAME

6       gb_sets - Sets represented by 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  or‐
11       dered lists, for larger sets, but depends on the application.
12
13       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
18       This module considers two elements as different if and only if they  do
19       not compare equal (==).
20

COMPLEXITY NOTE

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

COMPATIBILITY

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

DATA TYPES

76       set(Element)
77
78              A general balanced set.
79
80       set() = set(term())
81
82       iter(Element)
83
84              A general balanced set iterator.
85
86       iter() = iter(term())
87

EXPORTS

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

SEE ALSO

408       gb_trees(3), ordsets(3), sets(3)
409
410
411
412Ericsson AB                     stdlib 4.3.1.3                      gb_sets(3)
Impressum