Oracle Coherence for C++ API
Release 3.7.1.0

E22845-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< Nodem_hHead
 The first node of the tree (or NULL if the tree is empty).
MemberView< Comparatorm_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, 2011, Oracle and/or its affiliates. All rights reserved.