SourcePro® API Reference Guide

 
Loading...
Searching...
No Matches

Represents a group of ordered elements, as sorted by a comparison method, and allowing duplicates. More...

#include <rw/bintree.h>

Inheritance diagram for RWBinaryTree:
RWCollection RWCollectable

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 RWCollectablecopy () const
 
virtual size_t entries () const
 
virtual RWCollectablefind (const RWCollectable *target) const
 
size_t 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 RWBinaryTree &bt) const
 
RWBinaryTreeoperator= (const RWBinaryTree &bt)
 
RWBinaryTreeoperator= (RWBinaryTree &&bt)
 
bool operator== (const RWBinaryTree &bt) const
 
virtual RWCollectableremove (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 &)
 
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 ()
 

Friends

class RWBinaryTreeConstIterator
 
class RWBinaryTreeIterator
 

Additional Inherited Members

- Static Public Attributes inherited from RWCollection
static size_t DEFAULT_CAPACITY
 

Detailed Description

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.

Synopsis
typedef RWBinaryTree SortedCollection; // Smalltalk typedef.
#include <rw/bintree.h>
Represents a group of ordered elements, as sorted by a comparison method, and allowing duplicates.
Definition bintree.h:51
Persistence
Polymorphic

Constructor & Destructor Documentation

◆ RWBinaryTree() [1/3]

RWBinaryTree::RWBinaryTree ( )

Constructs an empty sorted collection.

◆ RWBinaryTree() [2/3]

RWBinaryTree::RWBinaryTree ( const RWBinaryTree & t)

Copy constructor. Constructs a shallow copy from t. Member function balance() is called before returning.

◆ RWBinaryTree() [3/3]

RWBinaryTree::RWBinaryTree ( RWBinaryTree && bt)

Move constructor. The constructed RWBinaryTree takes ownership of the data owned by bt.

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

◆ ~RWBinaryTree()

virtual RWBinaryTree::~RWBinaryTree ( )
virtual

Calls clear().

Member Function Documentation

◆ apply()

virtual void RWBinaryTree::apply ( RWapplyCollectable ap,
void *  )
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.

◆ balance()

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.

◆ classIsA()

static RWClassID RWBinaryTree::classIsA ( )
static

Returns the RWClassID of this class.

◆ clear()

virtual void RWBinaryTree::clear ( )
virtual

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

Implements RWCollection.

◆ copy()

virtual RWCollectable * RWBinaryTree::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.

◆ entries()

virtual size_t RWBinaryTree::entries ( ) const
virtual

Returns the total number of items in the collection.

Implements RWCollection.

◆ find()

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

Returns the first item that compares equal to the item pointed to by target, or rwnil if no item was found.

Implements RWCollection.

◆ height()

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.

◆ insert()

virtual RWCollectable * RWBinaryTree::insert ( RWCollectable * c)
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.

◆ isA()

virtual RWClassID RWBinaryTree::isA ( ) const
virtual

Returns __RWBINARYTREE.

Reimplemented from RWCollection.

◆ isEmpty()

virtual bool RWBinaryTree::isEmpty ( ) const
inlinevirtual

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

Implements RWCollection.

◆ isEqual()

virtual bool RWBinaryTree::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.

◆ newConstIterator()

virtual RWConstIterator * RWBinaryTree::newConstIterator ( ) const
virtual

Returns a const pointer to a dynamically allocated iterator for the collection.

Implements RWCollection.

◆ newIterator()

virtual RWIterator * RWBinaryTree::newIterator ( )
virtual

Returns a dynamically allocated iterator for the collection.

Implements RWCollection.

◆ newSpecies()

virtual RWCollectable * RWBinaryTree::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.

◆ occurrencesOf()

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

Returns the number of items that compare equal to the item pointed to by target.

Implements RWCollection.

◆ operator<=()

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.

◆ operator=() [1/2]

RWBinaryTree & RWBinaryTree::operator= ( const RWBinaryTree & bt)

Sets self to a shallow copy of bt.

◆ operator=() [2/2]

RWBinaryTree & RWBinaryTree::operator= ( RWBinaryTree && bt)

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

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

◆ operator==()

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.

◆ remove()

virtual RWCollectable * RWBinaryTree::remove ( const RWCollectable * target)
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.

◆ saveGuts() [1/2]

virtual void RWBinaryTree::saveGuts ( RWFile & ) const
virtual

Calls the global operator:

RWFile& operator<<(RWFile&, const RWCollectable&);
Contains virtual functions for identifying, hashing, comparing, storing and retrieving collectable ob...
Definition collect.h:441
Represents an abstraction of a filesystem regular file.
Definition rwfile.h:68

for each object in the collection.

Reimplemented from RWCollection.

◆ saveGuts() [2/2]

virtual void RWBinaryTree::saveGuts ( RWvostream & ) const
virtual

Calls the global operator.

RWvostream& operator<<(RWvostream&, const RWCollectable&);
Abstract base class that provides an interface for format-dependent storage of fundamental types and ...
Definition vstream.h:749

for each object in the collection.

Reimplemented from RWCollection.

◆ swap()

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.