Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages

  
 
  

home | help
gb_sets(3)		   Erlang Module Definition		    gb_sets(3)

NAME
       gb_sets - General balanced trees.

DESCRIPTION
       This  module provides ordered sets using	Prof. Arne Andersson's General
       Balanced	Trees. Ordered sets can	be much	more efficient than using  or-
       dered lists, for	larger sets, but depends on the	application.

       This  module considers two elements as different	if and only if they do
       not compare equal (==).

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  al-
       most 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
       10-100 times. This implementation is particularly suited	for accumulat-
       ing  elements  a	few at a time, building	up a large set (> 100-200 ele-
       ments), and repeatedly testing for membership in	the current set.

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

COMPATIBILITY
       The following functions in this module also exist and provides the same
       functionality in	the sets(3) and	ordsets(3) modules. That is,  by  only
       changing	 the  module name for each call, you can try out different set
       representations.

	 * add_element/2

	 * del_element/2

	 * filter/2

	 * fold/3

	 * from_list/1

	 * intersection/1

	 * intersection/2

	 * is_element/2

	 * is_empty/1

	 * is_set/1

	 * is_subset/2

	 * new/0

	 * size/1

	 * subtract/2

	 * to_list/1

	 * union/1

	 * union/2

DATA TYPES
       set(Element)

	      A	general	balanced set.

       set() = set(term())

       iter(Element)

	      A	general	balanced set iterator.

       iter() =	iter(term())

EXPORTS
       add(Element, Set1) -> Set2

       add_element(Element, Set1) -> Set2

	      Types:

		 Set1 =	Set2 = set(Element)

	      Returns a	new set	formed from Set1 with Element inserted.	If El-
	      ement is already an element in Set1, nothing is changed.

       balance(Set1) ->	Set2

	      Types:

		 Set1 =	Set2 = set(Element)

	      Rebalances  the tree representation of Set1. Notice that this is
	      rarely necessary,	but can	be motivated when a  large  number  of
	      elements	have been deleted from the tree	without	further	inser-
	      tions. Rebalancing can then be forced to minimise	lookup	times,
	      as deletion does not rebalance the tree.

       del_element(Element, Set1) -> Set2

	      Types:

		 Set1 =	Set2 = set(Element)

	      Returns a	new set	formed from Set1 with Element removed. If Ele-
	      ment is not an element in	Set1, nothing is changed.

       delete(Element, Set1) ->	Set2

	      Types:

		 Set1 =	Set2 = set(Element)

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

       delete_any(Element, Set1) -> Set2

	      Types:

		 Set1 =	Set2 = set(Element)

	      Returns a	new set	formed from Set1 with Element removed. If Ele-
	      ment is not an element in	Set1, nothing is changed.

       difference(Set1,	Set2) -> Set3

	      Types:

		 Set1 =	Set2 = Set3 = set(Element)

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

       empty() -> Set

	      Types:

		 Set = set()

	      Returns a	new empty set.

       filter(Pred, Set1) -> Set2

	      Types:

		 Pred =	fun((Element) -> boolean())
		 Set1 =	Set2 = set(Element)

	      Filters elements in Set1 using predicate function	Pred.

       fold(Function, Acc0, Set) -> Acc1

	      Types:

		 Function = fun((Element, AccIn) -> AccOut)
		 Acc0 =	Acc1 = AccIn = AccOut =	Acc
		 Set = set(Element)

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

       from_list(List) -> Set

	      Types:

		 List =	[Element]
		 Set = set(Element)

	      Returns a	set of the elements in List, where  List  can  be  un-
	      ordered and contain duplicates.

       from_ordset(List) -> Set

	      Types:

		 List =	[Element]
		 Set = set(Element)

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

       insert(Element, Set1) ->	Set2

	      Types:

		 Set1 =	Set2 = set(Element)

	      Returns a	new set	formed from Set1 with  Element	inserted.  As-
	      sumes that Element is not	present	in Set1.

       intersection(SetList) ->	Set

	      Types:

		 SetList = [set(Element), ...]
		 Set = set(Element)

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

       intersection(Set1, Set2)	-> Set3

	      Types:

		 Set1 =	Set2 = Set3 = set(Element)

	      Returns the intersection of Set1 and Set2.

       is_disjoint(Set1, Set2) -> boolean()

	      Types:

		 Set1 =	Set2 = set(Element)

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

       is_element(Element, Set)	-> boolean()

	      Types:

		 Set = set(Element)

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

       is_empty(Set) ->	boolean()

	      Types:

		 Set = set()

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

       is_member(Element, Set) -> boolean()

	      Types:

		 Set = set(Element)

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

       is_set(Term) -> boolean()

	      Types:

		 Term =	term()

	      Returns true if Term appears to be a set,	otherwise false.

       is_subset(Set1, Set2) ->	boolean()

	      Types:

		 Set1 =	Set2 = set(Element)

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

       iterator(Set) ->	Iter

	      Types:

		 Set = set(Element)
		 Iter =	iter(Element)

	      Returns  an iterator that	can be used for	traversing the entries
	      of Set; see next/1. The implementation of	 this  is  very	 effi-
	      cient;  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.

       iterator_from(Element, Set) -> Iter

	      Types:

		 Set = set(Element)
		 Iter =	iter(Element)

	      Returns  an iterator that	can be used for	traversing the entries
	      of Set; see next/1. The difference as compared to	 the  iterator
	      returned by iterator/1 is	that the first element greater than or
	      equal to Element is returned.

       largest(Set) -> Element

	      Types:

		 Set = set(Element)

	      Returns the largest element in Set.  Assumes  that  Set  is  not
	      empty.

       new() ->	Set

	      Types:

		 Set = set()

	      Returns a	new empty set.

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

	      Types:

		 Iter1 = Iter2 = iter(Element)

	      Returns  {Element, Iter2}, where Element is the smallest element
	      referred to by 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) -> set(Element)

	      Returns a	set containing only element Element.

       size(Set) -> integer() >= 0

	      Types:

		 Set = set()

	      Returns the number of elements in	Set.

       smallest(Set) ->	Element

	      Types:

		 Set = set(Element)

	      Returns the smallest element in Set. Assumes  that  Set  is  not
	      empty.

       subtract(Set1, Set2) -> Set3

	      Types:

		 Set1 =	Set2 = Set3 = set(Element)

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

       take_largest(Set1) -> {Element, Set2}

	      Types:

		 Set1 =	Set2 = set(Element)

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

       take_smallest(Set1) -> {Element,	Set2}

	      Types:

		 Set1 =	Set2 = set(Element)

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

       to_list(Set) -> List

	      Types:

		 Set = set(Element)
		 List =	[Element]

	      Returns the elements of Set as a list.

       union(SetList) -> Set

	      Types:

		 SetList = [set(Element), ...]
		 Set = set(Element)

	      Returns the merged (union) set of	the list of sets.

       union(Set1, Set2) -> Set3

	      Types:

		 Set1 =	Set2 = Set3 = set(Element)

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

SEE ALSO
       gb_trees(3), ordsets(3),	sets(3)

Ericsson AB			  stdlib 3.8			    gb_sets(3)

NAME | DESCRIPTION | COMPLEXITY NOTE | COMPATIBILITY | DATA TYPES | EXPORTS | SEE ALSO

Want to link to this manual page? Use this URL:
<https://www.freebsd.org/cgi/man.cgi?query=gb_sets&sektion=3&manpath=FreeBSD+13.0-RELEASE+and+Ports>

home | help