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
       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.

       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
       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  represen-
       tations.

	 * add_element/2

	 * del_element/2

	 * filter/2

	 * fold/3

	 * from_list/1

	 * intersection/1

	 * intersection/2

	 * is_element/2

	 * is_set/1

	 * is_subset/2

	 * new/0

	 * size/1

	 * subtract/2

	 * to_list/1

	 * union/1

	 * union/2

DATA TYPES
       set(Element)

	      A	GB set.

       set()

	      set() is equivalent to set(term()).

       iter(Element)

	      A	GB set iterator.

       iter()

	      iter() is	equivalent to 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. Note	that  this  is
	      rarely  necessary,  but  may be motivated	when a large number of
	      elements have been deleted from the tree without further	inser-
	      tions.  Rebalancing  could  then	be forced in order to minimise
	      lookup times, since deletion only	does not rebalance the tree.

       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

       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.

       difference(Set1,	Set2) -> Set3

       subtract(Set1, Set2) -> Set3

	      Types:

		 Set1 =	Set2 = Set3 = set(Element)

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

       empty() -> Set

       new() ->	Set

	      Types:

		 Set = gb_sets: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  may  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(Set1, Set2)	-> Set3

	      Types:

		 Set1 =	Set2 = Set3 = set(Element)

	      Returns the intersection of Set1 and Set2.

       intersection(SetList) ->	Set

	      Types:

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

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

       is_disjoint(Set1, Set2) -> boolean()

	      Types:

		 Set1 =	Set2 = set(Element)

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

       is_empty(Set) ->	boolean()

	      Types:

		 Set = gb_sets:set()

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

       is_member(Element, Set) -> boolean()

       is_element(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.

       largest(Set) -> Element

	      Types:

		 Set = set(Element)

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

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

	      Types:

		 Iter1 = Iter2 = iter(Element)

	      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) -> set(Element)

	      Returns a	set containing only the	element	Element.

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

	      Types:

		 Set = gb_sets: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
	      nonempty.

       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 nonempty.

       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 nonempty.

       to_list(Set) -> List

	      Types:

		 Set = set(Element)
		 List =	[Element]

	      Returns the elements of Set as a list.

       union(Set1, Set2) -> Set3

	      Types:

		 Set1 =	Set2 = Set3 = set(Element)

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

       union(SetList) -> Set

	      Types:

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

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

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

Ericsson AB			  stdlib 2.4			    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+12.1-RELEASE+and+Ports>

home | help