libUTL++
|
Binary tree abstraction. More...
#include <BinTree.h>
Public Member Functions | |
BinTree (bool owner, bool multiSet=false, Ordering *ordering=nullptr) | |
Constructor. More... | |
virtual void | steal (Object &rhs) |
"Steal" the internal representation from another instance. More... | |
Misc. Read-Only | |
void | dumpTree (Stream &os) const |
Dump the tree to the given stream (for debugging). More... | |
Misc. Modification | |
void | serializeFast (Stream &stream, uint_t io, uint_t mode=ser_default) |
Serialize to/from the given stream. More... | |
void | serializeFast (const RunTimeClass *rtc, Stream &stream, uint_t io, uint_t mode=ser_default) |
Serialize to/from the given stream. More... | |
Searching | |
virtual Object * | find (const Object &key) const |
Find an object matching a given key. More... | |
iterator | findIt (const Object &key) const |
Find the object matching the given key. More... | |
iterator | findIt (const Object &key) |
Find the object matching the given key. More... | |
void | findIt (const Object &key, BidIt &it) const |
virtual void | findIt (const Object &key, BidIt &it) |
Find an object matching a given key. More... | |
void | findFirstIt (const Object &key, BidIt &it, bool insert=false) const |
virtual void | findFirstIt (const Object &key, BidIt &it, bool insert=false) |
Find the first object matching the given key. More... | |
iterator | findFirstIt (const Object &key, bool insert=false) const |
Find the first object matching the given key. More... | |
iterator | findFirstIt (const Object &key, bool insert=false) |
Find the first object matching the given key. More... | |
void | findLastIt (const Object &key, BidIt &it) const |
virtual void | findLastIt (const Object &key, BidIt &it) |
Find the last object matching the given key. More... | |
iterator | findLastIt (const Object &key) const |
Find the last object matching the given key. More... | |
iterator | findLastIt (const Object &key) |
Find the last object matching the given key. More... | |
Adding Objects | |
bool | add (const Object &object) |
virtual bool | add (const Object *object) |
Add an object to the collection. More... | |
void | add (const Collection &collection) |
void | insert (const Object &object, const BidIt &it) |
virtual void | insert (const Object *object, const BidIt &it) |
Insert an object before the pointed-to location. More... | |
Removing Objects | |
virtual void | clear () |
Clear the collection by removing all objects. More... | |
bool | remove (const Object *key) |
virtual bool | remove (const Object &key) |
Remove the object matching the given key. More... | |
virtual void | removeIt (BidIt &it) |
Remove the object the given iterator points to. More... | |
virtual void | removeIt (BidIt &begin, BidIt &end) |
Iterators | |
iterator | begin () const |
Return a const in-order iterator for the first object. More... | |
iterator | begin () |
Return an in-order iterator for the first object. More... | |
BinTreeBfsIt | beginBFS () const |
Return a const breadth-first iterator for the root object. More... | |
BinTreeBfsIt | beginBFS () |
Return a breadth-first iterator for the root object. More... | |
virtual BidIt * | beginNew () const |
Return a const iterator pointing to the beginning of the collection. More... | |
virtual BidIt * | beginNew () |
Return an iterator pointing to the beginning of the collection. More... | |
BinTreeBfsIt * | beginBFSNew () const |
Return a const breadth-first iterator for the root object. More... | |
BinTreeBfsIt * | beginBFSNew () |
Return a breadth-first iterator for the root object. More... | |
iterator | end () const |
Return a const in-order iterator for the end. More... | |
iterator | end () |
Return an in-order iterator for the end. More... | |
BinTreeBfsIt | endBFS () const |
Return a const breadth-first iterator for the end of the tree. | |
BinTreeBfsIt | endBFS () |
Return a breadth-first iterator for the end of the tree. More... | |
virtual BidIt * | endNew () const |
Return a const iterator pointing to the end of the collection. More... | |
virtual BidIt * | endNew () |
Return an iterator pointing to the end of the collection. More... | |
BinTreeBfsIt * | endBFSNew () const |
Return a const breadth-first iterator for the end of the tree. | |
BinTreeBfsIt * | endBFSNew () |
Return a breadth-first iterator for the end of the tree. More... | |
iterator | root () const |
Return a const iterator for the root object. More... | |
iterator | root () |
Return an iterator for the root object. More... | |
Public Member Functions inherited from utl::SortedCollection | |
void | clobber (const SortedCollection *rhs) |
Where self and rhs intersect, make self's object equal to the rhs version (i.e. More... | |
virtual int | compare (const Object &rhs) const |
Compare with another SortedCollection by comparing contained objects. More... | |
virtual Object * | addOrFind (const Object *object) |
Add the given object, or find a matching object already contained. More... | |
virtual bool | addOrUpdate (const Object *object) |
Add or update the given object. More... | |
void | insert (const Object &object, const BidIt &it) |
Insert an object before the pointed-to location. More... | |
void | reverse () |
Reverse the order of the contained objects. More... | |
void | setOrdering (const Ordering &ordering, uint_t algorithm=sort_quickSort) |
Set the ordering, and optionally sort the collection to reflect the new ordering. More... | |
virtual void | setOrdering (Ordering *ordering, uint_t algorithm=sort_quickSort) |
Set the ordering, and optionally sort the collection to reflect the new ordering. More... | |
void | findEqualRange (const Object &key, BidIt &begin, BidIt &end) const |
Find the range elements [begin,end) that match a given key. More... | |
virtual void | findEqualRange (const Object &key, BidIt &begin, BidIt &end) |
Find the range of elements [begin,end) that match a given key. More... | |
void | findFirstIt (const Object &key, BidIt &it, bool insert=false) const |
Find the first object matching the given key. More... | |
void | findLastIt (const Object &key, BidIt &it) const |
Find the last object matching the given key. More... | |
Object * | findLinear (const Object &key) const |
Linear search for an object matching the given key. More... | |
Object * | findLinearSorted (const Object &key) const |
Linear search for an object matching the given key. More... | |
bool | remove (const Object *key) |
void | remove (const SortedCollection *rhs) |
Remove objects that have a match in rhs. More... | |
virtual void | removeIt (BidIt &begin, const BidIt &end) |
Remove part of the collection. More... | |
SortedCollection & | operator-= (const SortedCollection &rhs) |
Remove objects that have a match in rhs. More... | |
Collection * | difference (const SortedCollection *rhs, Collection *out=nullptr) const |
Determine the difference between self and rhs. More... | |
void | intersect (const SortedCollection *rhs) |
Set self to the intersection of self and rhs. More... | |
Collection * | intersection (const SortedCollection *rhs, Collection *out=nullptr, bool multiSet=false) const |
Determine the intersection of self and rhs. More... | |
size_t | intersectCard (const SortedCollection *rhs) const |
Determine the cardinality of the intersection of self and rhs. More... | |
bool | intersects (const SortedCollection *rhs) const |
Determine whether the intersection of self and rhs is non-empty. More... | |
bool | isSubSet (const SortedCollection *rhs) const |
Determine whether self is a subset of rhs. More... | |
bool | isSuperSet (const SortedCollection *rhs) const |
Determine whether self is a superset of rhs. More... | |
Collection * | merge (const SortedCollection *rhs, Collection *out=nullptr) const |
Merge with rhs to form a single sorted sequence. More... | |
Collection * | symmetricDifference (const SortedCollection *rhs, Collection *out=nullptr) const |
Determine the symmetric difference of self and rhs. More... | |
void | symmetricDifference (const SortedCollection *rhs, Collection *lhsOut, Collection *rhsOut) const |
Determine the symmetric difference of self and rhs. More... | |
Collection * | unique (Collection *out=nullptr) |
Remove duplicate objects. More... | |
SortedCollection & | operator &= (const SortedCollection *rhs) |
Intersect with rhs. More... | |
bool | operator<= (const SortedCollection *rhs) |
Determine whether self is a subset of rhs. More... | |
bool | operator>= (const SortedCollection *rhs) |
Determine whether self is a superset of rhs. More... | |
bool | testSorted () const |
Determine whether the collection is sorted (often useful for testing). More... | |
void | multiKeyQuickSort (bool key=true, bool reverse=false) |
Multi-key quick-sort the collection. More... | |
void | sort () |
Sort the collection using the quicksort algorithm. More... | |
virtual void | sort (uint_t algorithm) |
Sort the collection using the given algorithm. More... | |
Public Member Functions inherited from utl::Collection | |
void | assertOwner () |
Assert ownership of contained objects. More... | |
virtual void | copy (const Object &rhs) |
Copy another instance. More... | |
virtual void | vclone (const Object &rhs) |
Make an exact copy of another instance. More... | |
virtual void | dump (Stream &os, uint_t level=uint_t_max) const |
Dump a human-readable representation of self to the given output stream. More... | |
virtual void | serialize (Stream &stream, uint_t io, uint_t mode=ser_default) |
Serialize to or from a stream. More... | |
void | serialize (const RunTimeClass *rtc, Stream &stream, uint_t io, uint_t mode=ser_default) |
Serialize to/from the given stream. More... | |
virtual size_t | innerAllocatedSize () const |
Get the "inner" allocated size. More... | |
virtual bool | update (const Object *object) |
Update the given object. More... | |
bool | isOwner () const |
Get the owner flag. More... | |
void | setOwner (bool owner) |
Set the owner flag. More... | |
const Ordering * | ordering () const |
Get the ordering. More... | |
Ordering * | ordering () |
Get the ordering. More... | |
void | setOrdering (const Ordering &ordering, uint_t algorithm=sort_quickSort) |
Set the ordering, and optionally sort the collection to reflect the new ordering. More... | |
bool | empty () const |
Determine whether the collection is empty. More... | |
bool | isMultiSet () const |
Get the multiSet flag. More... | |
void | setMultiSet (bool multiSet) |
Set the multiSet flag. More... | |
bool | isMarked () const |
Get marked flag. More... | |
void | setMarked (bool marked=true) |
Set marked flag. More... | |
size_t | items () const |
Get the number of contained objects. More... | |
size_t | size () const |
Get the number of contained objects. More... | |
bool | add (const Object &object) |
Add an object to the collection. More... | |
void | add (const Collection &collection) |
Add another collection's objects. More... | |
virtual BidIt * | addIt (const Object *object) |
Add an object to the collection. More... | |
Object * | addOrFind (const Object &object) |
Add the given object, or find a matching object already contained. More... | |
bool | addOrUpdate (const Object &object) |
Add or update the given object. More... | |
Collection & | copyItems (const Collection *src, const Predicate *pred=nullptr, bool predVal=true) |
Copy objects from another collection. More... | |
Collection & | copyItems (const ListNode *src, const Predicate *pred=nullptr, bool predVal=true) |
Copy objects from a double-linked list. More... | |
Collection & | copyItems (const SlistNode *src, const Predicate *pred=nullptr, bool predVal=true) |
Copy objects from a single-linked list. More... | |
Collection & | stealItems (Collection *src) |
"Steal" items from another collection. More... | |
Collection & | operator+= (const Object &rhs) |
Add an object to the collection. More... | |
Collection & | operator+= (const Object *rhs) |
Add an object to the collection. More... | |
Collection & | operator+= (const Collection &rhs) |
Add another collection's objects. More... | |
Collection & | operator-= (const Object &rhs) |
Remove an object from the collection. More... | |
void | dump (Stream &os, uint_t level, bool key, bool printClassName, uint_t indent, const char *separator) const |
Dump contained objects to a stream. More... | |
virtual String | toString () const |
Obtain a string representation by invoking Object::toString() on all contained objects. | |
String | toString (bool key) const |
Obtain a string representation by invoking Object::toString() on all contained objects (or their keys). More... | |
String | toString (const char *sep, bool key=false) const |
Obtain a string represenation by invoking Object::toString() on all contained objects (or their keys). More... | |
String | toString (const String &sep, bool key=false) const |
Obtain a string represenation of the collection by invoking Object::toString() on all contained objects (or their keys). More... | |
iterator | begin () const |
Return a const iterator pointing to the first object in the collection. More... | |
iterator | begin () |
Return an iterator pointing to the first object in the collection. More... | |
virtual BidIt * | createIt () const |
Create a const iterator. More... | |
virtual BidIt * | createIt () |
Create an iterator. More... | |
iterator | end () const |
Return a const iterator pointing to the end of the collection. More... | |
iterator | end () |
Return an iterator pointing to the end of the collection. More... | |
bool | contains (const Object *key) const |
Determine whether the collection contains an object matching the given key. More... | |
bool | contains (const Object &key) const |
Determine whether the collection contains an object matching the given key. More... | |
size_t | count (const Predicate *pred=nullptr, bool predVal=true) const |
Count contained objects. More... | |
Object * | find (const Object *key) const |
Find an object matching a given key. More... | |
void | findIt (const Object &key, BidIt &it) const |
Find an object matching a given key. More... | |
Object * | first () const |
Return the first object (nullptr if empty). More... | |
bool | has (const Object *key) const |
See contains(). More... | |
bool | has (const Object &key) const |
See contains(). More... | |
Object * | last () const |
Get the last object (nullptr if empty). More... | |
bool | remove (const Object *key) |
Remove the object matching the given key. More... | |
Object * | take (BidIt &it) |
Remove the object the given iterator points to, but do not delete the object even if the collection owns its objects. More... | |
Object * | operator[] (const Object *object) |
add-or-find access operator (returns Object*). More... | |
Object & | operator() (const Object *object) |
add-or-find access operator (returns Object&). More... | |
Public Member Functions inherited from utl::Object | |
void | clear () |
Revert to initial state. More... | |
void | dumpWithClassName (Stream &os, uint_t indent=4, uint_t level=uint_t_max) const |
Front-end for dump() that prints the object's class name. More... | |
virtual const Object & | getKey () const |
Get the key for this object. More... | |
bool | hasKey () const |
Determine whether or not the object has a key. More... | |
virtual const Object & | getProxiedObject () const |
Get the proxied object (= self if none). More... | |
virtual Object & | getProxiedObject () |
Get the proxied object (= self if none). More... | |
virtual size_t | hash (size_t size) const |
Get the hash code for the object. More... | |
bool | _isA (const RunTimeClass *runTimeClass) const |
Determine whether self's class is a descendent of the given class. More... | |
operator String () const | |
Conversion to String. More... | |
size_t | allocatedSize () const |
Get the total allocated size of this object. More... | |
virtual void | addOwnedIt (const class FwdIt *it) const |
Notify self that it owns the given iterator. More... | |
virtual void | removeOwnedIt (const class FwdIt *it) const |
Notify self that the given owned iterator has been destroyed. More... | |
bool | operator< (const Object &rhs) const |
Less-than operator. More... | |
bool | operator<= (const Object &rhs) const |
Less-than-or-equal-to operator. More... | |
bool | operator> (const Object &rhs) const |
Greater-than operator. More... | |
bool | operator>= (const Object &rhs) const |
Greater-than-or-equal-to operator. More... | |
bool | operator== (const Object &rhs) const |
Equal-to operator. More... | |
bool | operator!= (const Object &rhs) const |
Unequal-to operator. More... | |
void | serializeIn (Stream &is, uint_t mode=ser_default) |
Serialize from an input stream. More... | |
void | serializeOut (Stream &os, uint_t mode=ser_default) const |
Serialize to an output stream. More... | |
void | serializeOutBoxed (Stream &os, uint_t mode=ser_default) const |
Serialize a boxed object to an output stream. More... | |
Additional Inherited Members | |
Static Public Member Functions inherited from utl::Object | |
static Object * | serializeInNullable (Stream &is, uint_t mode=ser_default) |
Serialize a nullptr-able object from an input stream. More... | |
static void | serializeOutNullable (const Object *object, Stream &os, uint_t mode=ser_default) |
Serialize a nullptr-able object to an output stream. More... | |
static void | serializeNullable (Object *&object, Stream &stream, uint_t io, uint_t mode=ser_default) |
Serialize a nullptr-able object to or from a stream. More... | |
static Object * | serializeInBoxed (Stream &is, uint_t mode=ser_default) |
Serialize a boxed object from an input stream. More... | |
static void | serializeBoxed (Object *&object, Stream &stream, uint_t io, uint_t mode=ser_default) |
Serialize a boxed object to or from a stream. More... | |
Protected Member Functions inherited from utl::FlagsMI | |
FlagsMI () | |
Constructor. More... | |
virtual | ~FlagsMI () |
Destructor. More... | |
void | copyFlags (const FlagsMI &rhs) |
Copy the given flags. More... | |
void | copyFlags (const FlagsMI &rhs, uint_t lsb, uint_t msb) |
Copy (some of) the given flags. More... | |
void | copyFlags (uint64_t flags, uint_t lsb, uint_t msb) |
Copy (some of) the given flags. More... | |
bool | getFlag (uint_t flagNum) const |
Get a user-defined flag. More... | |
void | setFlag (uint_t flagNum, bool val) |
Set a user-defined flag. More... | |
uint64_t | getFlagsNumber (uint64_t mask, uint64_t shift=0) |
Get a multi-bit value in the flags data (which is stored as one 64-bit integer). More... | |
void | setFlagsNumber (uint64_t mask, uint64_t shift, uint64_t num) |
Set a multi-bit value in the flags data (which is stored as one 64-bit integer). More... | |
uint64_t | getFlags () const |
Get the flags. More... | |
void | setFlags (uint64_t flags) |
Set the flags. More... | |
Binary tree abstraction.
BinTree provides an absraction for a SortedCollection with a binary tree representation. It provides a basic binary tree implementation, which can be subclassed to implement different kinds of binary trees, such as red/black (RBtree).
utl::BinTree::BinTree | ( | bool | owner, |
bool | multiSet = false , |
||
Ordering * | ordering = nullptr |
||
) |
Constructor.
owner | owner flag |
multiSet | (optional : false) multiSet flag |
ordering | (optional) ordering |
|
virtual |
"Steal" the internal representation from another instance.
The default implementation just calls vclone(), so you have to override this if you want a "move" capability.
Reimplemented from utl::Collection.
Reimplemented in utl::RBtree.
|
inline |
|
inline |
Serialize to/from the given stream.
Definition at line 68 of file BinTree.h.
References ASSERTD, const_cast_this, utl::deInit(), IFDEBUG, utl::init(), utl::maxObject, utl::ser_default, and utl::FwdIt::setConst().
void utl::BinTree::serializeFast | ( | const RunTimeClass * | rtc, |
Stream & | stream, | ||
uint_t | io, | ||
uint_t | mode = ser_default |
||
) |
Serialize to/from the given stream.
If a utl::RunTimeClass is given, it is assumed that all objects are of that same type.
Find an object matching a given key.
key | search key |
Reimplemented from utl::Collection.
Find the object matching the given key.
key | search key |
Find the object matching the given key.
key | search key |
Find an object matching a given key.
key | search key |
it | result iterator (= end() if no object found) |
Reimplemented from utl::Collection.
|
virtual |
Find the first object matching the given key.
key | search key |
it | result iterator (= end if no object found) |
insert | (optional : false) find insertion point? |
Reimplemented from utl::SortedCollection.
Reimplemented in utl::TRBtree< T >, utl::TRBtree< String >, utl::TRBtree< Production >, utl::TRBtree< Terminal >, utl::TRBtree< CmdLineArg >, and utl::TRBtree< Span< T, D > >.
Find the first object matching the given key.
key | search key |
insert | (optional : false) find insertion point? |
Find the first object matching the given key.
key | search key |
insert | (optional : false) find insertion point? |
Find the last object matching the given key.
key | search key |
it | result iterator (= end if no object found) |
Reimplemented from utl::SortedCollection.
Reimplemented in utl::TRBtree< T >, utl::TRBtree< String >, utl::TRBtree< Production >, utl::TRBtree< Terminal >, utl::TRBtree< CmdLineArg >, and utl::TRBtree< Span< T, D > >.
Find the last object matching the given key.
key | search key |
Find the last object matching the given key.
key | search key |
|
virtual |
Add an object to the collection.
object | object to add |
Implements utl::Collection.
Reimplemented in utl::SpanCol< T, D >.
Insert an object before the pointed-to location.
object | object being inserted |
it | reference location |
Reimplemented from utl::SortedCollection.
|
virtual |
Clear the collection by removing all objects.
Implements utl::Collection.
Reimplemented in utl::RBtree, and utl::SpanAllocator< T, D >.
|
virtual |
Remove the object matching the given key.
key | search key |
Reimplemented from utl::SortedCollection.
Reimplemented in utl::TRBtree< T >, utl::TRBtree< String >, utl::TRBtree< Production >, utl::TRBtree< Terminal >, utl::TRBtree< CmdLineArg >, utl::TRBtree< Span< T, D > >, utl::SpanCol< T, D >, and utl::SpanAllocator< T, D >.
|
virtual |
Remove the object the given iterator points to.
it | iterator |
Reimplemented from utl::SortedCollection.
|
inline |
Return a const in-order iterator for the first object.
Definition at line 140 of file BinTreeIt.h.
References IFDEBUG.
|
inline |
Return an in-order iterator for the first object.
Definition at line 150 of file BinTreeIt.h.
|
inline |
Return a const breadth-first iterator for the root object.
Definition at line 112 of file BinTreeBfsIt.h.
References utl::BinTreeBfsIt::forward(), utl::BinTreeBfsIt::get(), IFDEBUG, and utl::FwdIt::setConst().
|
inline |
Return a breadth-first iterator for the root object.
Definition at line 123 of file BinTreeBfsIt.h.
References utl::BinTreeBfsIt::forward(), and utl::BinTreeBfsIt::get().
|
inlinevirtual |
Return a const iterator pointing to the beginning of the collection.
Implements utl::Collection.
Definition at line 158 of file BinTreeIt.h.
References IFDEBUG, and utl::FwdIt::setConst().
|
inlinevirtual |
Return an iterator pointing to the beginning of the collection.
Implements utl::Collection.
Definition at line 168 of file BinTreeIt.h.
|
inline |
Return a const breadth-first iterator for the root object.
Definition at line 133 of file BinTreeBfsIt.h.
References utl::BinTreeBfsIt::forward(), utl::BinTreeBfsIt::get(), IFDEBUG, and utl::FwdIt::setConst().
|
inline |
Return a breadth-first iterator for the root object.
Definition at line 144 of file BinTreeBfsIt.h.
References utl::BinTreeBfsIt::forward(), and utl::BinTreeBfsIt::get().
|
inline |
Return a const in-order iterator for the end.
Definition at line 176 of file BinTreeIt.h.
References IFDEBUG.
|
inline |
Return an in-order iterator for the end.
Definition at line 186 of file BinTreeIt.h.
|
inline |
Return a breadth-first iterator for the end of the tree.
Definition at line 164 of file BinTreeBfsIt.h.
|
inlinevirtual |
Return a const iterator pointing to the end of the collection.
Implements utl::Collection.
Definition at line 194 of file BinTreeIt.h.
References IFDEBUG, and utl::FwdIt::setConst().
|
inlinevirtual |
Return an iterator pointing to the end of the collection.
Implements utl::Collection.
Definition at line 204 of file BinTreeIt.h.
|
inline |
Return a breadth-first iterator for the end of the tree.
Definition at line 182 of file BinTreeBfsIt.h.
|
inline |
Return a const iterator for the root object.
Definition at line 212 of file BinTreeIt.h.
References IFDEBUG, and utl::FwdIt::setConst().
|
inline |
Return an iterator for the root object.
Definition at line 222 of file BinTreeIt.h.