SourcePro® 2024.1 |
SourcePro® API Reference Guide |
Represents a group of ordered elements, as sorted by a comparison method, and allowing duplicates. More...
#include <rw/bintree.h>
Public Member Functions | |
RWBinaryTree () | |
RWBinaryTree (const RWBinaryTree &t) | |
RWBinaryTree (RWBinaryTree &&bt) | |
virtual | ~RWBinaryTree () |
virtual void | apply (RWapplyCollectable ap, void *) |
void | balance () |
virtual void | clear () |
virtual RWCollectable * | copy () const |
virtual size_t | entries () const |
virtual RWCollectable * | find (const RWCollectable *target) const |
size_t | height () const |
virtual RWCollectable * | insert (RWCollectable *c) |
virtual RWClassID | isA () const |
virtual bool | isEmpty () const |
virtual bool | isEqual (const RWCollectable *a) const |
virtual RWConstIterator * | newConstIterator () const |
virtual RWIterator * | newIterator () |
virtual RWCollectable * | newSpecies () const |
virtual size_t | occurrencesOf (const RWCollectable *target) const |
bool | operator<= (const RWBinaryTree &bt) const |
RWBinaryTree & | operator= (const RWBinaryTree &bt) |
RWBinaryTree & | operator= (RWBinaryTree &&bt) |
bool | operator== (const RWBinaryTree &bt) const |
virtual RWCollectable * | remove (const RWCollectable *target) |
virtual void | saveGuts (RWFile &) const |
virtual void | saveGuts (RWvostream &) const |
void | swap (RWBinaryTree &bt) |
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 &) |
RWCollection * | select (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 () |
Friends | |
class | RWBinaryTreeConstIterator |
class | RWBinaryTreeIterator |
Additional Inherited Members | |
Static Public Attributes inherited from RWCollection | |
static size_t | DEFAULT_CAPACITY |
Related Symbols inherited from RWCollection | |
typedef void(* | RWapplyCollectable) (RWCollectable *, void *) |
typedef bool(* | RWtestCollectable) (const RWCollectable *, const void *) |
typedef bool(* | RWtestCollectablePair) (const RWCollectable *, const RWCollectable *, const void *) |
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.
RWBinaryTree::RWBinaryTree | ( | ) |
Constructs an empty sorted collection.
RWBinaryTree::RWBinaryTree | ( | const RWBinaryTree & | t | ) |
Copy constructor. Constructs a shallow copy from t. Member function balance() is called before returning.
RWBinaryTree::RWBinaryTree | ( | RWBinaryTree && | bt | ) |
Move constructor. The constructed RWBinaryTree takes ownership of the data owned by bt.
|
virtual |
Calls clear().
|
virtual |
Invokes the function pointer ap on each item in the collection, in order, from smallest to largest. The function pointed to by ap should take no action that could change the ordering of items in the collection.
Implements RWCollection.
void RWBinaryTree::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 |
Removes all objects from the collection. Does not delete the objects themselves.
Implements RWCollection.
|
virtual |
Returns a new, copy-constructed object of the same type as self. The caller is responsible for deleting the object.
Reimplemented from RWCollectable.
|
virtual |
Returns the total number of items in the collection.
Implements RWCollection.
|
virtual |
Returns the first item that compares equal to the item pointed to by target, or rwnil if no item was found.
Implements RWCollection.
size_t RWBinaryTree::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 |
Inserts the item c into the collection and returns it. Returns rwnil 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 call insert() on a long sequence of sorted items without also calling balance() since the result will be very unbalanced (and therefore inefficient).
Implements RWCollection.
|
virtual |
Returns __RWBINARYTREE
.
Reimplemented from RWCollection.
|
inlinevirtual |
Returns true
if the collection is empty, otherwise returns false
.
Implements RWCollection.
|
virtual |
Behaves as if compareTo(t) was invoked, returning true
if the result equals 0, false
otherwise.
Reimplemented from RWCollectable.
|
virtual |
Returns a const pointer to a dynamically allocated iterator for the collection.
Implements RWCollection.
|
virtual |
Returns a dynamically allocated iterator for the collection.
Implements RWCollection.
|
virtual |
Returns a new, default-constructed object of the same type as self. The caller is responsible for deleting the object.
Reimplemented from RWCollectable.
|
virtual |
Returns the number of items that compare equal to the item pointed to by target.
Implements RWCollection.
bool RWBinaryTree::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.
RWBinaryTree & RWBinaryTree::operator= | ( | const RWBinaryTree & | bt | ) |
Sets self to a shallow copy of bt.
RWBinaryTree & RWBinaryTree::operator= | ( | RWBinaryTree && | bt | ) |
Move assignment. Self takes ownership of the data owned by bt.
bool RWBinaryTree::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 |
Removes the first item that compares equal to the object pointed to by target and returns it. Returns rwnil if no item was found.
Implements RWCollection.
|
virtual |
Calls the global operator:
for each object in the collection.
Reimplemented from RWCollection.
|
virtual |
Calls the global operator.
for each object in the collection.
Reimplemented from RWCollection.
void RWBinaryTree::swap | ( | RWBinaryTree & | bt | ) |
Swaps the data owned by self with the data owned by bt.
Copyright © 2024 Rogue Wave Software, Inc., a Perforce company. All Rights Reserved. |