File: gb_sets.html

package info (click to toggle)
erlang-doc-html 1%3A11.b.2-1
links: PTS
area: main
in suites: etch, etch-m68k
size: 23,284 kB
ctags: 10,724
sloc: erlang: 505; ansic: 323; makefile: 62; perl: 61; sh: 45
file content (694 lines) | stat: -rw-r--r-- 16,037 bytes
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<!-- This document was generated using DocBuilder 3.3.3 -->
<HTML>
<HEAD>
  <TITLE>gb_sets</TITLE>
  <SCRIPT type="text/javascript" src="../../../../doc/erlresolvelinks.js">
</SCRIPT>
  <STYLE TYPE="text/css">
<!--
    .REFBODY     { margin-left: 13mm }
    .REFTYPES    { margin-left: 8mm }
-->
  </STYLE>
</HEAD>
<BODY BGCOLOR="#FFFFFF" TEXT="#000000" LINK="#0000FF" VLINK="#FF00FF"
      ALINK="#FF0000">
<!-- refpage -->
<CENTER>
<A HREF="http://www.erlang.se">
  <IMG BORDER=0 ALT="[Ericsson AB]" SRC="min_head.gif">
</A>
<H1>gb_sets</H1>
</CENTER>

<H3>MODULE</H3>
<DIV CLASS=REFBODY>
gb_sets
</DIV>

<H3>MODULE SUMMARY</H3>
<DIV CLASS=REFBODY>
General Balanced Trees
</DIV>

<H3>DESCRIPTION</H3>
<DIV CLASS=REFBODY>

<P>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.
</DIV>

<H3>Complexity note</H3>
<DIV CLASS=REFBODY>

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

<H3>Compatibility</H3>
<DIV CLASS=REFBODY>

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

<LI>
<CODE>add_element/2</CODE><BR>

</LI>


<LI>
<CODE>del_element/2</CODE><BR>

</LI>


<LI>
<CODE>filter/2</CODE><BR>

</LI>


<LI>
<CODE>fold/3</CODE><BR>

</LI>


<LI>
<CODE>from_list/1</CODE><BR>

</LI>


<LI>
<CODE>intersection/1</CODE><BR>

</LI>


<LI>
<CODE>intersection/2</CODE><BR>

</LI>


<LI>
<CODE>is_element/2</CODE><BR>

</LI>


<LI>
<CODE>is_set/1</CODE><BR>

</LI>


<LI>
<CODE>is_subset/2</CODE><BR>

</LI>


<LI>
<CODE>new/0</CODE><BR>

</LI>


<LI>
<CODE>size/1</CODE><BR>

</LI>


<LI>
<CODE>subtract/2</CODE><BR>

</LI>


<LI>
<CODE>to_list/1</CODE><BR>

</LI>


<LI>
<CODE>union/1</CODE><BR>

</LI>


<LI>
<CODE>union/2</CODE><BR>

</LI>


</UL>

</DIV>

<H3>DATA TYPES</H3>
<DIV CLASS=REFBODY>

<PRE>
gb_set() = a GB set
    
</PRE>

</DIV>

<H3>EXPORTS</H3>

<P><A NAME="add/2"><STRONG><CODE>add(Element, Set1) -&#62; Set2</CODE></STRONG></A><BR>
<A NAME="add_element/2"><STRONG><CODE>add_element(Element, Set1) -&#62; Set2</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Element = term()</CODE></STRONG><BR>
<STRONG><CODE>Set1 = Set2 = gb_set()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns a new gb_set formed from <CODE>Set1</CODE> with
         <CODE>Element</CODE> inserted. If <CODE>Element</CODE> is already an
         element in <CODE>Set1</CODE>, nothing is changed.
</DIV>

<P><A NAME="balance/1"><STRONG><CODE>balance(Set1) -&#62; Set2</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Set1 = Set2 = gb_set()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Rebalances the tree representation of <CODE>Set1</CODE>. 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.
</DIV>

<P><A NAME="delete/2"><STRONG><CODE>delete(Element, Set1) -&#62; Set2</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Element = term()</CODE></STRONG><BR>
<STRONG><CODE>Set1 = Set2 = gb_set()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns a new gb_set formed from <CODE>Set1</CODE> with
         <CODE>Element</CODE> removed. Assumes that <CODE>Element</CODE> is present
         in <CODE>Set1</CODE>.
</DIV>

<P><A NAME="delete_any/2"><STRONG><CODE>delete_any(Element, Set1) -&#62; Set2</CODE></STRONG></A><BR>
<A NAME="del_element/2"><STRONG><CODE>del_element(Element, Set1) -&#62; Set2</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Element = term()</CODE></STRONG><BR>
<STRONG><CODE>Set1 = Set2 = gb_set()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns a new gb_set formed from <CODE>Set1</CODE> with
         <CODE>Element</CODE> removed. If <CODE>Element</CODE> is not an element
         in <CODE>Set1</CODE>, nothing is changed.
</DIV>

<P><A NAME="difference/2"><STRONG><CODE>difference(Set1, Set2) -&#62; Set3</CODE></STRONG></A><BR>
<A NAME="subtract/2"><STRONG><CODE>subtract(Set1, Set2) -&#62; Set3</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Set1 = Set2 = Set3 = gb_set()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns only the elements of <CODE>Set1</CODE> which are not also
         elements of <CODE>Set2</CODE>.
</DIV>

<P><A NAME="empty/0"><STRONG><CODE>empty() -&#62; Set</CODE></STRONG></A><BR>
<A NAME="new/0"><STRONG><CODE>new() -&#62; Set</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Set = gb_set()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns a new empty gb_set.
</DIV>

<P><A NAME="filter/2"><STRONG><CODE>filter(Pred, Set1) -&#62; Set2</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Pred = fun (E) -&#62; bool()</CODE></STRONG><BR>
<STRONG><CODE>E = term()</CODE></STRONG><BR>
<STRONG><CODE>Set1 = Set2 = gb_set()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Filters elements in <CODE>Set1</CODE> using predicate function
         <CODE>Pred</CODE>.
</DIV>

<P><A NAME="fold/3"><STRONG><CODE>fold(Function, Acc0, Set) -&#62; Acc1</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Function = fun (E, AccIn) -&#62; AccOut</CODE></STRONG><BR>
<STRONG><CODE>Acc0 = Acc1 = AccIn = AccOut = term()</CODE></STRONG><BR>
<STRONG><CODE>E = term()</CODE></STRONG><BR>
<STRONG><CODE>Set = gb_set()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Folds <CODE>Function</CODE> over every element in <CODE>Set</CODE>
         returning the final value of the accumulator.
</DIV>

<P><A NAME="from_list/1"><STRONG><CODE>from_list(List) -&#62; Set</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>List = [term()]</CODE></STRONG><BR>
<STRONG><CODE>Set = gb_set()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns a gb_set of the elements in <CODE>List</CODE>, where
         <CODE>List</CODE> may be unordered and contain duplicates.
</DIV>

<P><A NAME="from_ordset/1"><STRONG><CODE>from_ordset(List) -&#62; Set</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>List = [term()]</CODE></STRONG><BR>
<STRONG><CODE>Set = gb_set()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Turns an ordered-set list <CODE>List</CODE> into a gb_set. The list
         must not contain duplicates.
</DIV>

<P><A NAME="insert/2"><STRONG><CODE>insert(Element, Set1) -&#62; Set2</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Element = term()</CODE></STRONG><BR>
<STRONG><CODE>Set1 = Set2 = gb_set()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns a new gb_set formed from <CODE>Set1</CODE> with
         <CODE>Element</CODE> inserted. Assumes that <CODE>Element</CODE> is not
         present in <CODE>Set1</CODE>.
</DIV>

<P><A NAME="intersection/2"><STRONG><CODE>intersection(Set1, Set2) -&#62; Set3</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Set1 = Set2 = Set3 = gb_set()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns the intersection of <CODE>Set1</CODE> and <CODE>Set2</CODE>.
</DIV>

<P><A NAME="intersection/1"><STRONG><CODE>intersection(SetList) -&#62; Set</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>SetList = [gb_set()]</CODE></STRONG><BR>
<STRONG><CODE>Set = gb_set()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns the intersection of the non-empty list of gb_sets.
        
</DIV>

<P><A NAME="is_empty/1"><STRONG><CODE>is_empty(Set) -&#62; bool()</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Set = gb_set()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns <CODE>true</CODE> if <CODE>Set</CODE> is an empty set, and
         <CODE>false</CODE> otherwise.
</DIV>

<P><A NAME="is_member/2"><STRONG><CODE>is_member(Element, Set) -&#62; bool()</CODE></STRONG></A><BR>
<A NAME="is_element/2"><STRONG><CODE>is_element(Element, Set) -&#62; bool()</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Element = term()</CODE></STRONG><BR>
<STRONG><CODE>Set = gb_set()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns <CODE>true</CODE> if <CODE>Element</CODE> is an element of
         <CODE>Set</CODE>, otherwise <CODE>false</CODE>.
</DIV>

<P><A NAME="is_set/1"><STRONG><CODE>is_set(Set) -&#62; bool()</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Set = gb_set()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns <CODE>true</CODE> if <CODE>Set</CODE> appears to be a gb_set,
         otherwise <CODE>false</CODE>.
</DIV>

<P><A NAME="is_subset/2"><STRONG><CODE>is_subset(Set1, Set2) -&#62; bool()</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Set1 = Set2 = gb_set()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns <CODE>true</CODE> when every element of <CODE>Set1</CODE> is
         also a member of <CODE>Set2</CODE>, otherwise <CODE>false</CODE>.
</DIV>

<P><A NAME="iterator/1"><STRONG><CODE>iterator(Set) -&#62; Iter</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Set = gb_set()</CODE></STRONG><BR>
<STRONG><CODE>Iter = term()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns an iterator that can be used for traversing the
         entries of <CODE>Set</CODE>; see <CODE>next/1</CODE>. The implementation
         of this is very efficient; traversing the whole set using
         <CODE>next/1</CODE> is only slightly slower than getting the list
         of all elements using <CODE>to_list/1</CODE> 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.
</DIV>

<P><A NAME="largest/1"><STRONG><CODE>largest(Set) -&#62; term()</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Set = gb_set()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns the largest element in <CODE>Set</CODE>. Assumes that
         <CODE>Set</CODE> is nonempty.
</DIV>

<P><A NAME="next/1"><STRONG><CODE>next(Iter1) -&#62; {Element, Iter2 | none}</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Iter1 = Iter2 = Element = term()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

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

<P><A NAME="singleton/1"><STRONG><CODE>singleton(Element) -&#62; gb_set()</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Element = term()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns a gb_set containing only the element <CODE>Element</CODE>.
        
</DIV>

<P><A NAME="size/1"><STRONG><CODE>size(Set) -&#62; int()</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Set = gb_set()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns the number of elements in <CODE>Set</CODE>.
</DIV>

<P><A NAME="smallest/1"><STRONG><CODE>smallest(Set) -&#62; term()</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Set = gb_set()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns the smallest element in <CODE>Set</CODE>. Assumes that
         <CODE>Set</CODE> is nonempty.
</DIV>

<P><A NAME="take_largest/1"><STRONG><CODE>take_largest(Set1) -&#62; {Element, Set2}</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Set1 = Set2 = gb_set()</CODE></STRONG><BR>
<STRONG><CODE>Element = term()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns <CODE>{Element, Set2}</CODE>, where <CODE>Element</CODE> is the
         largest element in <CODE>Set1</CODE>, and <CODE>Set2</CODE> is this set
         with <CODE>Element</CODE> deleted. Assumes that <CODE>Set1</CODE> is
         nonempty.
</DIV>

<P><A NAME="take_smallest/1"><STRONG><CODE>take_smallest(Set1) -&#62; {Element, Set2}</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Set1 = Set2 = gb_set()</CODE></STRONG><BR>
<STRONG><CODE>Element = term()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns <CODE>{Element, Set2}</CODE>, where <CODE>Element</CODE> is the
         smallest element in <CODE>Set1</CODE>, and <CODE>Set2</CODE> is this set
         with <CODE>Element</CODE> deleted. Assumes that <CODE>Set1</CODE> is
         nonempty.
</DIV>

<P><A NAME="to_list/1"><STRONG><CODE>to_list(Set) -&#62; List</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Set = gb_set()</CODE></STRONG><BR>
<STRONG><CODE>List = [term()]</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns the elements of <CODE>Set</CODE> as a list.
</DIV>

<P><A NAME="union/2"><STRONG><CODE>union(Set1, Set2) -&#62; Set3</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Set1 = Set2 = Set3 = gb_set()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns the merged (union) gb_set of <CODE>Set1</CODE> and
         <CODE>Set2</CODE>.
</DIV>

<P><A NAME="union/1"><STRONG><CODE>union(SetList) -&#62; Set</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>SetList = [gb_set()]</CODE></STRONG><BR>
<STRONG><CODE>Set = gb_set()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns the merged (union) gb_set of the list of gb_sets.
</DIV>

<H3>SEE ALSO</H3>
<DIV CLASS=REFBODY>

<P> <A HREF="gb_trees.html">gb_trees(3)</A>, 
<A HREF="ordsets.html">ordsets(3)</A>, 
<A HREF="sets.html">sets(3)</A>

</DIV>

<H3>AUTHORS</H3>
<DIV CLASS=REFBODY>
Richard Carlsson - support@erlang.ericsson.se<BR>

</DIV>
<CENTER>
<HR>
<SMALL>stdlib 1.14.2<BR>
Copyright &copy; 1991-2006
<A HREF="http://www.erlang.se">Ericsson AB</A><BR>
</SMALL>
</CENTER>
</BODY>
</HTML>