RWBTree(3C++) RWBTree(3C++)
NameRWBTree - 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 ConstructorsRWBTree();
Construct an empty B-tree.
RWBTree(const RWBTree& btr);
Construct self as a shallow copy of btr.
Public Destructor
virtual
~RWBTree();
Page 1
RWBTree(3C++) RWBTree(3C++)
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.
Page 2
RWBTree(3C++) RWBTree(3C++)
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
Page 3
RWBTree(3C++) RWBTree(3C++)
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;
Page 4
RWBTree(3C++) RWBTree(3C++)
Inherited from class RWCollection.
RWStringID
stringID();
(acts virtual) Inherited from class RWCollectable.
Page 5