Home Man
Search
Today's Posts
Register

Linux & Unix Commands - Search Man Pages

Linux 2.6 - man page for gb_sets (linux section 3erl)

gb_sets(3erl)			     Erlang Module Definition			    gb_sets(3erl)

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

	 * 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
       gb_set() = a GB set

EXPORTS
       add(Element, Set1) -> Set2
       add_element(Element, Set1) -> Set2

	      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 min-
	      imise 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 accumula-
	      tor.

       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.

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

Ericsson AB				  stdlib 1.17.3 			    gb_sets(3erl)


All times are GMT -4. The time now is 03:16 AM.

Unix & Linux Forums Content Copyrightę1993-2018. All Rights Reserved.
UNIX.COM Login
Username:
Password:  
Show Password