SourcePro® API Reference Guide

 
Loading...
Searching...
No Matches

Represents a group of ordered elements not accessible by an external key, and for which duplicates are not allowed. More...

#include <rw/btree.h>

Inheritance diagram for RWBTree:
RWCollection RWCollectable RWBTreeDictionary

Public Member Functions

 RWBTree ()
 
 RWBTree (const RWBTree &btr)
 
 RWBTree (RWBTree &&btr)
 
virtual ~RWBTree ()
 
virtual void apply (RWapplyCollectable ap, void *)
 
virtual void clear ()
 
virtual RWCollectablecopy () const
 
virtual size_t entries () const
 
virtual RWCollectablefind (const RWCollectable *target) const
 
unsigned height () const
 
virtual RWCollectableinsert (RWCollectable *c)
 
virtual RWClassID isA () const
 
virtual bool isEmpty () const
 
virtual bool isEqual (const RWCollectable *a) const
 
virtual RWConstIteratornewConstIterator () const
 
virtual RWIteratornewIterator ()
 
virtual RWCollectablenewSpecies () const
 
virtual size_t occurrencesOf (const RWCollectable *target) const
 
bool operator<= (const RWBTree &btr) const
 
RWBTreeoperator= (const RWBTree &btr)
 
RWBTreeoperator= (RWBTree &&btr)
 
bool operator== (const RWBTree &btr) const
 
virtual RWCollectableremove (const RWCollectable *target)
 
void swap (RWBTree &btr)
 
- Public Member Functions inherited from RWCollection
virtual ~RWCollection ()
 
RWBag asBag () const
 
RWBinaryTree asBinaryTree () const
 
RWOrdered asOrderedCollection () const
 
RWSet asSet () const
 
RWBinaryTree asSortedCollection () const
 
virtual RWspace binaryStoreSize () const
 
virtual void clearAndDestroy ()
 
virtual bool contains (const RWCollectable *target) const
 
void operator+= (const RWCollection &c)
 
void operator-= (const RWCollection &c)
 
virtual void removeAndDestroy (const RWCollectable *target)
 
virtual void restoreGuts (RWFile &)
 
virtual void restoreGuts (RWvistream &)
 
virtual void saveGuts (RWFile &) const
 
virtual void saveGuts (RWvostream &) const
 
RWCollectionselect (RWtestCollectable tst, void *vp) const
 
- Public Member Functions inherited from RWCollectable
virtual ~RWCollectable ()
 
virtual int compareTo (const RWCollectable *) const
 
virtual unsigned hash () const
 
RWspace recursiveStoreSize () const
 
RWStringID stringID () const
 

Static Public Member Functions

static RWClassID classIsA ()
 
- Static Public Member Functions inherited from RWCollectable
static RWClassID classID (const RWStringID &name)
 
static RWClassID classIsA ()
 
static bool isAtom (RWClassID id)
 
static RWspace nilStoreSize ()
 

Additional Inherited Members

- Static Public Attributes inherited from RWCollection
static size_t DEFAULT_CAPACITY
 

Detailed 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 RWCollectable::compareTo().

This class has certain advantages over class RWBinaryTree. First, the B-tree is automatically balanced. (With class RWBinaryTree, you must call member function RWBinaryTree::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 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.

Synopsis
#include <rw/btree.h>
Represents a group of ordered elements not accessible by an external key, and for which duplicates ar...
Definition btree.h:84
Persistence
Polymorphic

Constructor & Destructor Documentation

◆ RWBTree() [1/3]

RWBTree::RWBTree ( )

Constructs an empty B-tree.

◆ ~RWBTree()

virtual RWBTree::~RWBTree ( )
virtual

Calls clear().

◆ RWBTree() [2/3]

RWBTree::RWBTree ( const RWBTree & btr)

Constructs self as a shallow copy of btr.

◆ RWBTree() [3/3]

RWBTree::RWBTree ( RWBTree && btr)

Move constructor. The constructed RWBTree takes ownership of the data owned by btr.

Condition:
This method is available only on platforms with rvalue reference support.

Member Function Documentation

◆ apply()

virtual void RWBTree::apply ( RWapplyCollectable ap,
void *  )
virtual

Invokes the function pointer ap on each item in 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.

Implements RWCollection.

◆ classIsA()

static RWClassID RWBTree::classIsA ( )
static

Returns the RWClassID of this class.

◆ clear()

virtual void RWBTree::clear ( )
virtual

Removes all objects from the collection. Does not delete the objects themselves.

Implements RWCollection.

Reimplemented in RWBTreeDictionary.

◆ copy()

virtual RWCollectable * RWBTree::copy ( ) const
virtual

Returns a new, copy-constructed object of the same type as self. The caller is responsible for deleting the object.

Reimplemented from RWCollectable.

Reimplemented in RWBTreeDictionary.

◆ entries()

virtual size_t RWBTree::entries ( ) const
virtual

Returns the total number of items in the collection.

Implements RWCollection.

◆ find()

virtual RWCollectable * RWBTree::find ( const RWCollectable * target) const
virtual

The first item that compares equal to the object pointed to by target is returned or rwnil if no item is found.

Implements RWCollection.

Reimplemented in RWBTreeDictionary.

◆ height()

unsigned RWBTree::height ( ) const

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

◆ insert()

virtual RWCollectable * RWBTree::insert ( RWCollectable * c)
virtual

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 that isEqual() to c, then the old item is returned and the new item is not inserted. Returns rwnil if the insertion was unsuccessful.

Note
If self is a collection of key-value pairs (e.g. RWBTreeDictionary), this function throws std::bad_cast if c does not inherit from RWCollectableAssociation. If the collection does not contain an association with a key that "matches" the key of c, then a copy of the association is inserted and that association's key is returned. Otherwise, the insert fails by returning either rwnil or a pointer to the existing association's key.

Implements RWCollection.

Reimplemented in RWBTreeDictionary.

◆ isA()

virtual RWClassID RWBTree::isA ( ) const
virtual

Returns __RWBTREE.

Reimplemented from RWCollection.

Reimplemented in RWBTreeDictionary.

◆ isEmpty()

virtual bool RWBTree::isEmpty ( ) const
inlinevirtual

Returns true if the collection is empty, otherwise returns false.

Implements RWCollection.

◆ isEqual()

virtual bool RWBTree::isEqual ( const RWCollectable * t) const
virtual

Behaves as if compareTo(t) was invoked, returning true if the result equals 0, false otherwise.

Reimplemented from RWCollectable.

Reimplemented in RWBTreeDictionary.

◆ newConstIterator()

virtual RWConstIterator * RWBTree::newConstIterator ( ) const
inlinevirtual

Returns rwnil

Implements RWCollection.

◆ newIterator()

virtual RWIterator * RWBTree::newIterator ( )
inlinevirtual

Returns rwnil

Implements RWCollection.

◆ newSpecies()

virtual RWCollectable * RWBTree::newSpecies ( ) const
virtual

Returns a new, default-constructed object of the same type as self. The caller is responsible for deleting the object.

Reimplemented from RWCollectable.

Reimplemented in RWBTreeDictionary.

◆ occurrencesOf()

virtual size_t RWBTree::occurrencesOf ( const RWCollectable * target) const
virtual

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

Implements RWCollection.

◆ operator<=()

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

◆ operator=() [1/2]

RWBTree & RWBTree::operator= ( const RWBTree & btr)

Sets self to a shallow copy of btr.

◆ operator=() [2/2]

RWBTree & RWBTree::operator= ( RWBTree && btr)

Move assignment. Self takes ownership of the data owned by btr.

Condition:
This method is available only on platforms with rvalue reference support.

◆ operator==()

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

◆ remove()

virtual RWCollectable * RWBTree::remove ( const RWCollectable * target)
virtual

Removes and returns the first item that compares equal to the object pointed to by target. Returns rwnil if no item was found.

Implements RWCollection.

Reimplemented in RWBTreeDictionary.

◆ swap()

void RWBTree::swap ( RWBTree & btr)

Swaps the data owned by self with the data owned by btr.

Copyright © 2024 Rogue Wave Software, Inc., a Perforce company. All Rights Reserved.