RWBTree

Module:  Essential Tools Module   Group:  RWCollectable Classes

RWBTreeRWCollectionRWCollectable

• Local Index
• Synopsis
• Description
• Persistence
• Public Constructors
• Public Destructor
• Public Member Operators
• Public Member Functions

Members

apply() binaryStoreSize() clear() clearAndDestroy() compareTo() contains() entries()

find() hash() height() insert() isA() isEmpty() isEqual()

newConstIterator() newIterator() occurrencesOf() operator<=() operator=() operator==() remove()

removeAndDestroy() restoreGuts() RWBTree() saveGuts() stringID() ~RWBTree()

#include <rw/btree.h>
RWBTree a;

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

Polymorphic

RWBTree();

Construct an empty B-tree.

RWBTree(const RWBTree& btr);

Construct self as a shallow copy of btr.

virtual 
~RWBTree();

Redefined from RWCollection. Calls clear().

void
operator=(const RWBTree& btr);

Set self to a shallow copy of btr.

bool
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 C++ Standard 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.

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

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

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