RWBTree(3C++)

Name
     RWBTree - Rogue Wave library class

Synopsis
              #include <rw/btree.h>



              RWBTree a;




Description
     Class RWBTree represents a group of ordered elements, not accessible by
     an external key.  Duplicates are not allowed.  An object stored by class
     RWBTree must inherit abstract base class RWCollectable -- the elements
     are ordered internally according to the value returned by virtual
     function compareTo() (see class RWCollectable).  This class has certain
     advantages over class RWBinaryTree.  First, the B-tree is automatically
     balanced.  (With class RWBinaryTree, you must call member function
     balance() explicitly to balance the tree.)  Nodes are never allowed to
     have less than a certain number of items (called the order).  The default
     order is 50, but may be changed by resetting the value of the static
     constant "order" in the header file <btree.h> and recompiling.  Larger
     values will result in shallower trees, but less efficient use of memory.
     Because many keys are held in a single node, class RWBTree also tends to
     fragment memory less.

Persistence
     Polymorphic

Public Constructors
              RWBTree();


     Construct an empty B-tree.

              RWBTree(const RWBTree& btr);


     Construct self as a shallow copy of btr.

              Public Destructor
          virtual
          ~RWBTree();

     Redefined from RWCollection.  Calls clear().

Public Member Operators
              void
          operator=(const RWBTree& btr);


     Set self to a shallow copy of btr.

              RWBoolean
          operator<=(const RWBTree& btr) const;


     Returns TRUE if self is a subset of btr.  That is, for every item in
     self, there must be an item in btr that compares equal.  Note:  If you
     inherit from RWBTree in the presence of the Standard C++ Library, we
     recommend that you override this operator and explicitly forward the
     call.  Overload resolution in C++ will choose the Standard Library
     provided global operators over inherited class members.  These global
     definitions are not appropriate for set-like partial orderings.

              RWBoolean
          operator==(const RWBTree& btr) const;


     Returns TRUE if self and btr are equivalent.  That is, they must have the
     same number of items and for every item in self, there must be an item in
     btr that compares equal.

Public Member Functions
              virtual void
          apply(RWapplyCollectable ap, void*);


     Redefined from class RWCollection to apply the user-supplied function
     pointed to by ap to each member of the collection, in order, from
     smallest to largest.  This supplied function should not do anything to
     the items that could change the ordering of the collection.

              virtual RWspace
          binaryStoreSize() const;


     Inherited from class RWCollection.

              virtual void
          clear();


     Redefined from class RWCollection.

              virtual void
          clearAndDestroy();


     Inherited from class RWCollection.

              virtual int
          compareTo(const RWCollectable* a) const;


     Inherited from class RWCollectable.

              virtual RWBoolean
          contains(const RWCollectable* target) const;


     Inherited from class RWCollection.

              virtual size_t
          entries() const;


     Redefined from class RWCollection.

              virtual RWCollectable*
          find(const RWCollectable* target) const;


     Redefined from class RWCollection.  The first item that compares equal to
     the object pointed to by target is returned or nil if no item is found.

              virtual unsigned
          hash() const;


     Inherited from class RWCollectable.

              unsigned
          height() const;


     Special member function of this class.  Returns the height of the tree,
     defined as the number of nodes traversed while descending from the root
     node to an external (leaf) node.

              virtual RWCollectable*
          insert(RWCollectable* c);


     Redefined from class RWCollection.  Inserts the item c into the
     collection and returns it. The item c is inserted according to the value
     returned by compareTo().  If an item is already in the collection which
     isEqual to c, then the old item is returned and the new item is not
     inserted.  Otherwise returns nil if the insertion was unsuccessful.

              virtual RWClassID
          isA() const;


     Redefined from class RWCollectable to return __RWBTREE.

              virtual RWBoolean
          isEmpty() const;


     Redefined from class RWCollection.

              virtual RWBoolean
          isEqual(const RWCollectable* a) const;


     Inherited from class RWCollectable.

              virtual size_t
          occurrencesOf(const RWCollectable* target) const;


     Redefined from class RWCollection.  Returns the number of items that
     compare equal to target.  Since duplicates are not allowed, this function
     can only return 0 or 1.

              virtual RWCollectable*
          remove(const RWCollectable* target);


     Redefined from class RWCollection.  Removes and returns the first item
     that compares equal to the object pointed to by target.  Returns nil if
     no item was found.

              virtual void
          removeAndDestroy(const RWCollectable* target);


     Inherited from class RWCollection.

              virtual void
          restoreGuts(RWvistream&);
          virtual void
          restoreGuts(RWFile&);
          virtual void
          saveGuts(RWvostream&) const;
          virtual void
          saveGuts(RWFile&) const;

     Inherited from class RWCollection.

              RWStringID
          stringID();


     (acts virtual) Inherited from class RWCollectable.