Homepage > Man Pages > Category > Subroutines
Homepage > Man Pages > Name > G

# gb_sets

## man page of gb_sets

### gb_sets: General Balanced Trees

```NAME
gb_sets - General Balanced Trees

DESCRIPTION
An  implementation of ordered sets using Prof. Arne Andersson's General
Balanced Trees. This can be much  more  efficient  than  using  ordered
lists, for larger sets, but depends on the application.

COMPLEXITY NOTE
The complexity on set operations is bounded by either O(|S|) or O(|T| *
log(|S|)), where S is the largest given  set,  depending  on  which  is
fastest  for  any  particular  function  call. For operating on sets of
almost equal size, this implementation is about  3  times  slower  than
using  ordered-list  sets  directly.  For sets of very different sizes,
however, this solution can be arbitrarily  much  faster;  in  practical
cases,   often  between  10  and  100  times.  This  implementation  is
particularly suited for accumulating elements a few at a time, building
up a large set (more than 100-200 elements), and repeatedly testing for
membership in the current set.

As with normal tree structures, lookup (membership testing),  insertion
and deletion have logarithmic complexity.

COMPATIBILITY
All  of  the  following  functions in this module also exist and do the
same thing in the sets and ordsets modules. That is, by  only  changing
the  module  name  for  each  call,  you  can  try  out  different  set
representations.

* del_element/2 .br .br

* filter/2 .br .br

* fold/3 .br .br

* from_list/1 .br .br

* intersection/1 .br .br

* intersection/2 .br .br

* is_element/2 .br .br

* is_set/1 .br .br

* is_subset/2 .br .br

* new/0 .br .br

* size/1 .br .br

* subtract/2 .br .br

* to_list/1 .br .br

* union/1 .br .br

* union/2 .br .br

DATA TYPES
gb_set() = a GB set

EXPORTS

Types  Element = term()
Set1 = Set2 = gb_set()

Returns a new gb_set formed from Set1 with Element inserted.  If
Element is already an element in Set1, nothing is changed.

balance(Set1) -> Set2

Types  Set1 = Set2 = gb_set()

Rebalances  the  tree  representation of Set1. Note that this is
rarely necessary, but may be motivated when a  large  number  of
elements  have  been  deleted  from  the  tree  without  further
insertions.  Rebalancing  could  then  be  forced  in  order  to
minimise  lookup  times,  since deletion only does not rebalance
the tree.

delete(Element, Set1) -> Set2

Types  Element = term()
Set1 = Set2 = gb_set()

Returns a new gb_set formed  from  Set1  with  Element  removed.
Assumes that Element is present in Set1.

delete_any(Element, Set1) -> Set2
del_element(Element, Set1) -> Set2

Types  Element = term()
Set1 = Set2 = gb_set()

Returns  a  new gb_set formed from Set1 with Element removed. If
Element is not an element in Set1, nothing is changed.

difference(Set1, Set2) -> Set3
subtract(Set1, Set2) -> Set3

Types  Set1 = Set2 = Set3 = gb_set()

Returns only the elements of Set1 which are not also elements of
Set2.

empty() -> Set
new() -> Set

Types  Set = gb_set()

Returns a new empty gb_set.

filter(Pred, Set1) -> Set2

Types  Pred = fun (E) -> bool()
E = term()
Set1 = Set2 = gb_set()

Filters elements in Set1 using predicate function Pred.

fold(Function, Acc0, Set) -> Acc1

Types  Function = fun (E, AccIn) -> AccOut
Acc0 = Acc1 = AccIn = AccOut = term()
E = term()
Set = gb_set()

Folds  Function  over  every  element in Set returning the final
value of the accumulator.

from_list(List) -> Set

Types  List = [term()]
Set = gb_set()

Returns a gb_set of the elements in  List,  where  List  may  be
unordered and contain duplicates.

from_ordset(List) -> Set

Types  List = [term()]
Set = gb_set()

Turns  an ordered-set list List into a gb_set. The list must not
contain duplicates.

insert(Element, Set1) -> Set2

Types  Element = term()
Set1 = Set2 = gb_set()

Returns a new gb_set formed from  Set1  with  Element  inserted.
Assumes that Element is not present in Set1.

intersection(Set1, Set2) -> Set3

Types  Set1 = Set2 = Set3 = gb_set()

Returns the intersection of Set1 and Set2.

intersection(SetList) -> Set

Types  SetList = [gb_set()]
Set = gb_set()

Returns the intersection of the non-empty list of gb_sets.

is_disjoint(Set1, Set2) -> bool()

Types  Set1 = Set2 = gb_set()

Returns  true if Set1 and Set2 are disjoint (have no elements in
common), and false otherwise.

is_empty(Set) -> bool()

Types  Set = gb_set()

Returns true if Set is an empty set, and false otherwise.

is_member(Element, Set) -> bool()
is_element(Element, Set) -> bool()

Types  Element = term()
Set = gb_set()

Returns true if Element is an element of Set, otherwise false.

is_set(Term) -> bool()

Types  Term = term()

Returns true if Set appears to be a gb_set, otherwise false.

is_subset(Set1, Set2) -> bool()

Types  Set1 = Set2 = gb_set()

Returns true when every element of Set1  is  also  a  member  of
Set2, otherwise false.

iterator(Set) -> Iter

Types  Set = gb_set()
Iter = term()

Returns  an iterator that can be used for traversing the entries
of  Set;  see  next/1.  The  implementation  of  this  is   very
efficient;  traversing  the  whole  set  using  next/1  is  only
slightly slower than getting the  list  of  all  elements  using
to_list/1  and  traversing  that.  The  main  advantage  of  the
iterator approach is that it does not require the complete  list
of all elements to be built in memory at one time.

largest(Set) -> term()

Types  Set = gb_set()

Returns  the  largest  element  in  Set.  Assumes  that  Set  is
nonempty.

next(Iter1) -> {Element, Iter2} | none

Types  Iter1 = Iter2 = Element = term()

Returns {Element, Iter2} where Element is the  smallest  element
referred to by the iterator Iter1, and Iter2 is the new iterator
to be used for traversing the remaining elements,  or  the  atom
none if no elements remain.

singleton(Element) -> gb_set()

Types  Element = term()

Returns a gb_set containing only the element Element.

size(Set) -> int()

Types  Set = gb_set()

Returns the number of elements in Set.

smallest(Set) -> term()

Types  Set = gb_set()

Returns  the  smallest  element  in  Set.  Assumes  that  Set is
nonempty.

take_largest(Set1) -> {Element, Set2}

Types  Set1 = Set2 = gb_set()
Element = term()

Returns {Element, Set2}, where Element is the largest element in
Set1,  and  Set2  is this set with Element deleted. Assumes that
Set1 is nonempty.

take_smallest(Set1) -> {Element, Set2}

Types  Set1 = Set2 = gb_set()
Element = term()

Returns {Element, Set2}, where Element is the  smallest  element
in Set1, and Set2 is this set with Element deleted. Assumes that
Set1 is nonempty.

to_list(Set) -> List

Types  Set = gb_set()
List = [term()]

Returns the elements of Set as a list.

union(Set1, Set2) -> Set3

Types  Set1 = Set2 = Set3 = gb_set()

Returns the merged (union) gb_set of Set1 and Set2.

union(SetList) -> Set

Types  SetList = [gb_set()]
Set = gb_set()

Returns the merged (union) gb_set of the list of gb_sets.

gb_trees(3erl), ordsets(3erl), sets(3erl)

GB_SETS(3)
```