#include <coherence/util/TreeMap.hpp>
Inherits AbstractMap, and NavigableMap.
Stored as an AVL tree. Implementation is based on the public domain implementation by Julienne Walker. This implementation is not thread-safe.
Public Types | ||||||||||||||||||||||
typedef spec::Handle | Handle | |||||||||||||||||||||
TreeMap Handle definition. | ||||||||||||||||||||||
typedef spec::View | View | |||||||||||||||||||||
TreeMap View definition. | ||||||||||||||||||||||
typedef spec::Holder | Holder | |||||||||||||||||||||
TreeMap Holder definition. | ||||||||||||||||||||||
Public Member Functions | ||||||||||||||||||||||
virtual size32_t | size () const | |||||||||||||||||||||
Return the number of key-value mappings in this map.
| ||||||||||||||||||||||
virtual bool | isEmpty () const | |||||||||||||||||||||
Return true if this map contains no key-value mappings.
| ||||||||||||||||||||||
virtual bool | containsKey (Object::View vKey) const | |||||||||||||||||||||
Return true if this map contains a mapping for the specified key.
| ||||||||||||||||||||||
virtual Object::Holder | get (Object::View vKey) const | |||||||||||||||||||||
Return the value to which this map maps the specified key.
Return
| ||||||||||||||||||||||
virtual Object::Holder | put (Object::View vKey, Object::Holder ohValue) | |||||||||||||||||||||
Associate the specified value with the specified key in this map. If the map previously contained a mapping for this key, the old value is replaced by the specified value.
| ||||||||||||||||||||||
virtual Object::Holder | remove (Object::View vKey) | |||||||||||||||||||||
Remove the mapping for this key from this map if it is present.
Return the value to which the map previously associated the key, or
| ||||||||||||||||||||||
virtual void | clear () | |||||||||||||||||||||
Remove all mappings from this map.
| ||||||||||||||||||||||
virtual Set::View | entrySet () const | |||||||||||||||||||||
Return a set of the mappings contained in this map. Each element in the returned set is a Map::Entry::View. The set is backed by the map, so changes to the map are reflected in the set. If the map is modified while an iteration over the set is in progress, the results of the iteration are undefined.
| ||||||||||||||||||||||
virtual Set::Handle | entrySet () | |||||||||||||||||||||
Return a set of the mappings contained in this map. Each element in the returned set is a Map::Entry::Handle. The set is backed by the map, so changes to one are reflected in the other. If the map is modified while an iteration over the set is in progress, the results of the iteration are undefined.
| ||||||||||||||||||||||
virtual Comparator::View | comparator () const | |||||||||||||||||||||
Returns the comparator used in sorting this map, or NULL if it is the keys' natural ordering.
| ||||||||||||||||||||||
virtual Object::View | firstKey () const | |||||||||||||||||||||
Returns the first (lowest sorted) key in the map.
| ||||||||||||||||||||||
virtual Object::View | lastKey () const | |||||||||||||||||||||
Returns the last (highest sorted) key in the map.
| ||||||||||||||||||||||
virtual SortedMap::Handle | headMap (Object::View vToKey) | |||||||||||||||||||||
Returns a handle of the portion of the map strictly less than vToKey. The handle is backed by this map, so changes in one show up in the other. The sub-map supports all optional operations of the original.
| ||||||||||||||||||||||
virtual SortedMap::View | headMap (Object::View vToKey) const | |||||||||||||||||||||
Returns a view of the portion of the map strictly less than vToKey.
| ||||||||||||||||||||||
virtual SortedMap::Handle | subMap (Object::View vFromKey, Object::View vToKey) | |||||||||||||||||||||
Returns a handle of the portion of the map greater than or equal to vFromKey, and strictly less than vToKey. The handle is backed by this map, so changes in one show up in the other. The sub-map supports all optional operations of the original.
| ||||||||||||||||||||||
virtual SortedMap::View | subMap (Object::View vFromKey, Object::View vToKey) const | |||||||||||||||||||||
Returns a view of the portion of the map greater than or equal to vFromKey, and strictly less than vToKey.
| ||||||||||||||||||||||
virtual SortedMap::Handle | tailMap (Object::View vFromKey) | |||||||||||||||||||||
Returns a handle of the portion of the map greater than or equal to vFromKey. The handle is backed by this map, so changes in one show up in the other. The sub-map supports all optional operations of the original.
| ||||||||||||||||||||||
virtual SortedMap::View | tailMap (Object::View vFromKey) const | |||||||||||||||||||||
Returns a view of the portion of the map greater than or equal to vFromKey.
| ||||||||||||||||||||||
virtual Object::View | ceilingKey (Object::View vKey) const | |||||||||||||||||||||
Returns the least key greater than or equal to the given key, or NULL if there is no such key.
| ||||||||||||||||||||||
virtual Object::View | floorKey (Object::View vKey) const | |||||||||||||||||||||
Returns the greatest key less than or equal to the given key, or NULL if there is no such key.
| ||||||||||||||||||||||
virtual Object::View | higherKey (Object::View vKey) const | |||||||||||||||||||||
Returns the least key strictly greater than the given key, or NULL if there is no such key.
| ||||||||||||||||||||||
virtual Object::View | lowerKey (Object::View vKey) const | |||||||||||||||||||||
Returns the greatest key strictly less than the given key, or NULL if there is no such key.
| ||||||||||||||||||||||
virtual Map::Entry::Holder | pollFirstEntry () | |||||||||||||||||||||
Removes and returns a key-value mapping associated with the least key in this map, or NULL if the map is empty.
| ||||||||||||||||||||||
virtual Map::Entry::Holder | pollLastEntry () | |||||||||||||||||||||
Removes and returns a key-value mapping associated with the greatest key in this map, or NULL if the map is empty.
| ||||||||||||||||||||||
virtual NavigableMap::Handle | headMap (Object::View vToKey, bool toInclusive) | |||||||||||||||||||||
Returns a handle of the portion of the map whose keys are less than (or equal to, if toInclusive is true) vToKey. The handle is backed by this map, so changes in one show up in the other. The sub-map supports all optional operations of the original.
| ||||||||||||||||||||||
virtual NavigableMap::View | headMap (Object::View vToKey, bool toInclusive) const | |||||||||||||||||||||
Returns a view of the portion of the map whose keys are less than (or equal to, if toInclusive is true) vToKey.
| ||||||||||||||||||||||
virtual NavigableMap::Handle | subMap (Object::View vFromKey, bool fromInclusive, Object::View vToKey, bool toInclusive) | |||||||||||||||||||||
Returns a handle of the portion of this map whose keys range from vFromKey to vToKey. If vFromKey and vToKey are equal, the returned map is empty unless fromInclusive and toInclusive are both true. The handle is backed by this map, so changes in one show up in the other. The sub-map supports all optional operations of the original.
| ||||||||||||||||||||||
virtual NavigableMap::View | subMap (Object::View vFromKey, bool fromInclusive, Object::View vToKey, bool toInclusive) const | |||||||||||||||||||||
Returns a view of the portion of this map whose keys range from vFromKey to vToKey. If vFromKey and vToKey are equal, the returned map is empty unless fromInclusive and toInclusive are both true.
| ||||||||||||||||||||||
virtual NavigableMap::Handle | tailMap (Object::View vFromKey, bool fromInclusive) | |||||||||||||||||||||
Returns a handle of the portion of the map whose keys are greater than (or equal to, if fromInclusive} is true) vFromKey. The handle is backed by this map, so changes in one show up in the other. The sub-map supports all optional operations of the original.
| ||||||||||||||||||||||
virtual NavigableMap::View | tailMap (Object::View vFromKey, bool fromInclusive) const | |||||||||||||||||||||
Returns a view of the portion of the map whose keys are greater than (or equal to, if fromInclusive} is true) vFromKey.
| ||||||||||||||||||||||
virtual void | removeNode (Node::Handle hNode) | |||||||||||||||||||||
Remove the specified node from the tree. | ||||||||||||||||||||||
virtual bool | isHead (Node::View vNode) const | |||||||||||||||||||||
Determine if Node is the head of the tree. | ||||||||||||||||||||||
virtual Iterator::Handle | iterator () const | |||||||||||||||||||||
Return an Iterator over this tree map. | ||||||||||||||||||||||
virtual Muterator::Handle | iterator () | |||||||||||||||||||||
Return an Iterator over this tree map. | ||||||||||||||||||||||
virtual int32_t | compare (Object::View v1, Object::View v2) const | |||||||||||||||||||||
Compare two Objects. | ||||||||||||||||||||||
virtual Node::Handle | find (Object::View vKey) const | |||||||||||||||||||||
Find the specified key and return its node. | ||||||||||||||||||||||
virtual Node::Handle | getHeadNode () const | |||||||||||||||||||||
Get the head node. | ||||||||||||||||||||||
Protected Member Functions | ||||||||||||||||||||||
virtual Node::Handle | replace (Node::Handle hNodeA, Node::Handle hNodeB) | |||||||||||||||||||||
Replace one node with another. | ||||||||||||||||||||||
virtual Node::Handle | rotate (Node::Handle hNode, bool fLeft) | |||||||||||||||||||||
Rotate a node in a given direction. | ||||||||||||||||||||||
virtual Node::Handle | doubleRotate (Node::Handle hNode, bool fLeft) | |||||||||||||||||||||
Double rotate a node in a given direction. | ||||||||||||||||||||||
virtual void | adjustDoubleBalance (Node::Handle hNode, Node::Handle hChild, int32_t nBal) | |||||||||||||||||||||
Adjust the balance factor of a node and its descendants prior to a double rotation. | ||||||||||||||||||||||
virtual Node::Handle | findInsertionPoint (Object::View ovKey) const | |||||||||||||||||||||
Find the point at which a Node with the specified index would be inserted. | ||||||||||||||||||||||
virtual void | balancedInsertion (Node::Handle hParent, Node::Handle hChild) | |||||||||||||||||||||
Insert a node into a tree and re-balance. | ||||||||||||||||||||||
virtual void | balancePostRemove (Node::Handle hPruned, bool fPrunedLeft) | |||||||||||||||||||||
Re-balance the tree following the removal of a node. | ||||||||||||||||||||||
virtual Node::Handle | instantiateNode (Object::View vKey, Object::Holder ohValue) | |||||||||||||||||||||
Create a new Node. | ||||||||||||||||||||||
Protected Attributes | ||||||||||||||||||||||
size32_t | m_nSize | |||||||||||||||||||||
The number of nodes in the tree. | ||||||||||||||||||||||
MemberHandle< Node > | m_hHead | |||||||||||||||||||||
The first node of the tree (or NULL if the tree is empty). | ||||||||||||||||||||||
FinalView< Comparator > | f_vComparator | |||||||||||||||||||||
The comparator used to maintain order in this tree map, or NULL if it uses the natural ordering of its keys. | ||||||||||||||||||||||
Classes | ||||||||||||||||||||||
class | Node | |||||||||||||||||||||
An AVL tree node. More... |
virtual void removeNode | ( | Node::Handle | hNode | ) | [virtual] |
Remove the specified node from the tree.
The supplied node must be part of the tree.
hNode | the node to remove |
virtual bool isHead | ( | Node::View | vNode | ) | const [virtual] |
virtual Iterator::Handle iterator | ( | ) | const [virtual] |
virtual Muterator::Handle iterator | ( | ) | [virtual] |
virtual int32_t compare | ( | Object::View | v1, | |
Object::View | v2 | |||
) | const [virtual] |
Compare two Objects.
If both Objects are comparable with this tree map's Comparator, return < 0, 0 or > 0 if the first Object is less than, equal to, or greater than the second Object.
v1 | the first object to compare | |
v2 | the second object to compare |
virtual Node::Handle find | ( | Object::View | vKey | ) | const [virtual] |
Find the specified key and return its node.
vKey | the key to look for |
virtual Node::Handle getHeadNode | ( | ) | const [virtual] |
Get the head node.
virtual Node::Handle replace | ( | Node::Handle | hNodeA, | |
Node::Handle | hNodeB | |||
) | [protected, virtual] |
Replace one node with another.
hNodeA | the node to be unlinked | |
hNodeB | the node to be linked in nodeA's place; may be NULL |
virtual Node::Handle rotate | ( | Node::Handle | hNode, | |
bool | fLeft | |||
) | [protected, virtual] |
Rotate a node in a given direction.
hNode | the node to rotate | |
fLeft | the rotation direction |
virtual Node::Handle doubleRotate | ( | Node::Handle | hNode, | |
bool | fLeft | |||
) | [protected, virtual] |
Double rotate a node in a given direction.
hNode | the node to rotate | |
fLeft | the final rotation direction |
virtual void adjustDoubleBalance | ( | Node::Handle | hNode, | |
Node::Handle | hChild, | |||
int32_t | nBal | |||
) | [protected, virtual] |
Adjust the balance factor of a node and its descendants prior to a double rotation.
hNode | the node which was rotated | |
hChild | the child to adjust | |
nBal | the balance adjustment |
virtual Node::Handle findInsertionPoint | ( | Object::View | ovKey | ) | const [protected, virtual] |
Find the point at which a Node with the specified index would be inserted.
If the tree is empty then null is returned. If the index already exists then the existing Node is returned, otherwise the Node which will be the parent of the new Node is returned.
ovKey | the key of the new node |
virtual void balancedInsertion | ( | Node::Handle | hParent, | |
Node::Handle | hChild | |||
) | [protected, virtual] |
Insert a node into a tree and re-balance.
hParent | the location at which to insert the node | |
hChild | the node to insert |
virtual void balancePostRemove | ( | Node::Handle | hPruned, | |
bool | fPrunedLeft | |||
) | [protected, virtual] |
Re-balance the tree following the removal of a node.
hPruned | the node whose sub-tree shrunk | |
fPrunedLeft | the side on which the sub-tree shrunk |
virtual Node::Handle instantiateNode | ( | Object::View | vKey, | |
Object::Holder | ohValue | |||
) | [protected, virtual] |
size32_t m_nSize [protected] |
The number of nodes in the tree.
This can be determined by iterating through the tree, but by keeping the size cached, certain operations that need the size of the tree up front are much more efficient.
MemberHandle<Node> m_hHead [mutable, protected] |
The first node of the tree (or NULL if the tree is empty).
The first node is referred to as the "head" or the "root" node.