Oracle Coherence for C++ API
Release 3.6.1.0
E18813-01

- Main Page
- Namespaces
- Classes
- Files

- Alphabetical List
- Class List
- Class Hierarchy
- Class Members

# TreeMap Class Reference

`#include <coherence/util/TreeMap.hpp>`

Inherits AbstractMap, and SortedMap.

List of all members.

## Detailed Description

A tree map implementation.

Stored as an AVL tree. Implementation is based on the public domain implementation by Julienne Walker. This implementation is not thread-safe.

See also:
  Implementation by Julienne Walker

Author:
  tb 2009.02.22

## 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. Returns: the number of key-value mappings in this map.
virtual bool | isEmpty () const
| Return `true` if this map contains no key-value mappings. Returns: `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. Parameters:
  | vKey | key whose presence in this map is to be tested.
Returns: `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 `NULL` if the map contains no mapping for this key. A return value of `NULL` does not necessarily indicate that the map contains no mapping for the key; it's also possible that the map explicitly maps the key to `NULL`. The `containsKey` operation may be used to distinguish these two cases. Parameters:
  | vKey | key whose associated value is to be returned.
Returns: the value to which this map maps the specified key, or `NULL` if the map contains no mapping for this key. See also: containsKey()
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. Parameters:
  | vKey | key with which the specified value is to be associated.
  | ohValue | value to be associated with the specified key.
  Returns: previous value associated with specified key, or `NULL` if there was no mapping for key. A `NULL` return can also indicate that the map previously associated `NULL` with the specified key. Exceptions:
  | coherence::lang::UnsupportedOperationException | if the put() operation is not supported by this map.
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 `NULL` if the map contained no mapping for this key. (A `NULL` return can also indicate that the map previously associated `NULL` with the specified key.) The map will not contain a mapping for the specified key once the call returns. Parameters:
  | vKey | key whose mapping is to be removed from the map.
  Returns: previous value associated with specified key, or `NULL` if there was no mapping for key. Exceptions:
  | coherence::lang::UnsupportedOperationException | if the remove() operation is not supported by this map.
virtual void | clear ()
  | Remove all mappings from this map. Exceptions:
  | coherence::lang::UnsupportedOperationException | if the clear()operation is not supported by 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. Returns: a set of the mappings contained in this map.
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. Returns: a set of the mappings contained in this map.
virtual Comparator::View | comparator () const
| Returns the comparator used in sorting this map, or NULL if it is the keys' natural ordering. Returns: the sorting comparator
virtual Object::View | firstKey () const
  | Returns the first (lowest sorted) key in the map. Returns: the first key Exceptions:
  | NoSuchElementException | if this map is empty.
virtual Object::View | lastKey () const
  | Returns the last (highest sorted) key in the map. Returns: the last key Exceptions:
  | NoSuchElementException | if this map is empty.
virtual SortedMap::Handle | headMap (Object::View vToKey)
  | Returns a handle of the portion of the map strictly less than toKey. 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. Parameters:
  | vToKey | the exclusive upper range of the sub-map
  Returns: the sub-map Exceptions:
  | ClassCastException | if toKey is not comparable to the map contents
  | IllegalArgumentException | if this is a subMap, and toKey is out of range
  | NullPointerException | if toKey is NULL but the map does not allow NULL keys
virtual SortedMap::View | headMap (Object::View vToKey) const
  | Returns a view of the portion of the map strictly less than toKey. Parameters:
  | vToKey | the exclusive upper range of the sub-map
  Returns: the sub-map Exceptions:
  | ClassCastException | if toKey is not comparable to the map contents
  | IllegalArgumentException | if this is a subMap, and toKey is out of range
  | NullPointerException | if toKey is NULL but the map does not allow NULL keys
virtual SortedMap::Handle | subMap (Object::View vFromKey, Object::View vToKey)
  | Returns a handle of the portion of the map greater than or equal to fromKey, and strictly less than toKey. 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. Parameters:
  | vFromKey | the inclusive lower range of the sub-map
  | vToKey | the exclusive upper range of the sub-map
  Returns: the sub-map Exceptions:
  | ClassCastException | if fromKey or toKey is not comparable to the map contents
  | IllegalArgumentException | if this is a subMap, and fromKey or toKey is out of range
  | NullPointerException | if fromKey or toKey is NULL but the map does not allow NULL keys
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 fromKey, and strictly less than toKey. Parameters:
  | vFromKey | the inclusive lower range of the sub-map
  | vToKey | the exclusive upper range of the sub-map
  Returns: the sub-map Exceptions:
  | ClassCastException | if fromKey or toKey is not comparable to the map contents
  | IllegalArgumentException | if this is a subMap, and fromKey or toKey is out of range
  | NullPointerException | if fromKey or toKey is NULL but the map does not allow NULL keys
virtual SortedMap::Handle | tailMap (Object::View vFromKey)
  | Returns a handle of the portion of the map greater than or equal to fromKey. 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. Parameters:
  | vFromKey | the inclusive lower range of the sub-map
  Returns: the sub-map Exceptions:
  | ClassCastException | if fromKey is not comparable to the map contents
  | IllegalArgumentException | if this is a subMap, and fromKey is out of range
  | NullPointerException | if fromKey is NULL but the map does not allow NULL keys
virtual SortedMap::View | tailMap (Object::View vFromKey) const
  | Returns a view of the portion of the map greater than or equal to fromKey. Parameters:
  | vFromKey | the inclusive lower range of the sub-map
  Returns: the sub-map Exceptions:
  | ClassCastException | if fromKey is not comparable to the map contents
  | IllegalArgumentException | if this is a subMap, and fromKey is out of range
  | NullPointerException | if fromKey is NULL but the map does not allow NULL keys
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).
MemberView< Comparator > | m_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...

## Member Function Documentation

virtual void removeNode | ( | Node::Handle | hNode | ) | `[virtual]`

Remove the specified node from the tree.

The supplied node must be part of the tree.

Parameters:

  | hNode | the node to remove

virtual bool isHead | ( | Node::View | vNode | ) | const `[virtual]`

Determine if Node is the head of the tree.

Parameters:

  | vNode | the node to compare to the head of the tree

Returns:
  true if the passed in Node is the head of the tree

virtual Iterator::Handle iterator | ( |  | ) | const `[virtual]`

Return an Iterator over this tree map.

Returns:
  an Iterator over this tree map

virtual Muterator::Handle iterator | ( |  | ) | `[virtual]`

Return an Iterator over this tree map.

Returns:
  an Iterator over this tree map

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.

Parameters:

  | v1 | the first object to compare
  | v2 | the second object to compare

Returns:
  < 0, 0 or > 0 if the first Object is less than, equal to, or greater than the second Object

virtual Node::Handle find | ( | Object::View | vKey | ) | const `[virtual]`

Find the specified key and return its node.

Parameters:

  | vKey | the key to look for

Returns:
  the node containing the index or NULL if the index is not in the TreeMap

virtual Node::Handle getHeadNode | ( |  | ) | const `[virtual]`

Get the head node.

Returns:
  this tree map's head node

virtual Node::Handle replace | ( | Node::Handle | hNodeA,
|  | Node::Handle | hNodeB |
| ) |  |  | `[protected, virtual]`

Replace one node with another.

Parameters:

  | hNodeA | the node to be unlinked
  | hNodeB | the node to be linked in nodeA's place; may be NULL

Returns:
  nodeB's new parent

virtual Node::Handle rotate | ( | Node::Handle | hNode,
|  | bool | fLeft |
| ) |  |  | `[protected, virtual]`

Rotate a node in a given direction.

Parameters:

  | hNode | the node to rotate
  | fLeft | the rotation direction

Returns:
  the node's new parent (former child)

virtual Node::Handle doubleRotate | ( | Node::Handle | hNode,
|  | bool | fLeft |
| ) |  |  | `[protected, virtual]`

Double rotate a node in a given direction.

Parameters:

  | hNode | the node to rotate
  | fLeft | the final rotation direction

Returns:
  the node's new parent (former grand child)

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.

Parameters:

  | 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.

Parameters:

  | ovKey | the key of the new node

Returns:
  NULL, node, or parent

virtual void balancedInsertion | ( | Node::Handle | hParent,
|  | Node::Handle | hChild |
| ) |  |  | `[protected, virtual]`

Insert a node into a tree and re-balance.

Parameters:

  | 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.

Parameters:

  | 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]`

Create a new Node.

Parameters:

  | vKey | the key of the new Node
  | ohValue | the value of the new Node

Returns:
  the newly instantiated Node

## Member Data Documentation

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.

The documentation for this class was generated from the following file:

- coherence/util/TreeMap.hpp

Copyright © 2000, 2010, Oracle and/or its affiliates. All rights reserved.