RWBinaryTree(3C++)

Name
     RWBinaryTree - Rogue Wave library class

Synopsis
              typedef RWBinaryTree SortedCollection;   // Smalltalk typedef.



              #include <rw/bintree.h>
          RWBinaryTree bt;




Description
     Class RWBinaryTree represents a group of ordered elements, internally
     sorted by the compareTo() function.  Duplicates are allowed.  An object
     stored by an RWBinaryTree must inherit abstract base class RWCollectable.

Persistence
     Polymorphic

Public Constructors
              RWBinaryTree();


     Construct an empty sorted collection.

              RWBinaryTree(const RWBinaryTree& t);


     Copy constructor.  Constructs a shallow copy from t.  Member function
     balance() (see below) is called before returning.

              virtual ~RWBinaryTree();


     Redefined from RWCollection.  Calls clear().

Public Member Operators
              void
          operator=(const RWBinaryTree& bt);


     Sets self to a shallow copy of bt.

              void
          operator+=(const RWCollection ct);


     Inserts each element of .ct into self.  Note that using this operator to
     insert an already-sorted collection will result in creating a very
     unbalanced tree, possibly to the point of stack overflow.

              RWBoolean
          operator<=(const RWBinaryTree& bt) const;


     Returns TRUE if self is a subset of the collection bt.  That is, every
     item in self must compare equal to a unique item in bt.

              RWBoolean
          operator==(const RWBinaryTree& bt) const;


     Returns TRUE if self and bt are equivalent.  That is, they must have the
     same number of items and every item in self must compare equal to a
     unique item in bt.

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.

              void
          balance();


     Special function to balance the tree.  In a perfectly balanced binary
     tree with no duplicate elements, the number of nodes from the root to any
     external (leaf) node differs by at most one node.  Since this collection
     allows duplicate elements, a perfectly balanced tree is not always
     possible.  Preserves the order of duplicate elements.

              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.  Returns the first item that compares
     equal to the item pointed to by target, or nil if no item was found.

              virtual unsigned
          hash() const;


     Inherited from class RWCollectable.

              unsigned
          height() const;


     Returns the number of nodes between the root node and the farthest leaf.
     A RWBinaryTree with one entry will have a height of 1.  Note that the
     entire tree is traversed to discover this value.

              virtual RWCollectable*
          insert(RWCollectable* c);


     Redefined from class RWCollection.  Inserts the item c into the
     collection and returns it.  Returns nil if the insertion was
     unsuccessful.  The item c is inserted according to the value returned by
     compareTo(). insert() does not automatically balance the RWBinaryTree.
     Be careful not to insert() a long sequence of sorted items without
     calling balance() since the result will be very unbalanced (and therefore
     inefficient).
              virtual RWClassID
          isA() const;


     Redefined from class RWCollectable to return __RWBINARYTREE.

              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 the item pointed to by target.

              virtual RWCollectable*
          remove(const RWCollectable* target);


     Redefined from class RWCollection.  Removes the first item that compares
     equal to the object pointed to by target and returns it.  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&);


     Inherited from class RWCollection.

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

     Redefined from class RWCollection to store objects by level, rather than
     in order.  This results in the tree maintaining its morphology.

              RWStringID
          stringID();


     (acts virtual) Inherited from class RWCollectable.