Oracle Coherence for C++ API
Release 3.6.1.0

E18813-01

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:
Copyright © 2000, 2010, Oracle and/or its affiliates. All rights reserved.