Module: Essential Tools Module Group: RWCollectable Classes
RWBinaryTreeRWCollectionRWCollectable
typedef RWBinaryTree SortedCollection; // Smalltalk typedef. #include <rw/bintree.h> RWBinaryTree bt;
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.
Polymorphic
RWBinaryTree();
Constructs 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().
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.
bool 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.
bool 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.
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 bool 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 bool isEmpty() const;
Redefined from class RWCollection.
virtual bool isEqual(const RWCollectable* a) const;
Inherited from class RWCollectable.
virtual RWConstIterator* newConstIterator();
Returns a const pointer to a dynamically allocated iterator for the collection.
virtual RWIterator* newIterator();
Returns a dynamically allocated iterator for the collection.
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.
© Copyright Rogue Wave Software, Inc. All Rights Reserved.
Rogue Wave and SourcePro are registered trademarks of Rogue Wave Software, Inc. in the United States and other countries. All other trademarks are the property of their respective owners.
Contact Rogue Wave about documentation or support issues.