Oracle® Fusion Middleware C++ API Reference for Oracle Coherence
12c (12.2.1.4.0)
E90870-01

TreeMap Class Reference

#include <coherence/util/TreeMap.hpp>

Inherits AbstractMap, and NavigableMap.

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 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. Parameters: vToKey  the exclusive upper range of the sub-map Returns: the sub-map Exceptions: ClassCastException  if vToKey is not comparable to the map contents IllegalArgumentException  if this is a sub-map, and vToKey is out of range NullPointerException  if vToKey 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 vToKey. Parameters: vToKey  the exclusive upper range of the sub-map Returns: the sub-map Exceptions: ClassCastException  if vToKey is not comparable to the map contents IllegalArgumentException  if this is a sub-map, and vToKey is out of range NullPointerException  if vToKey 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 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. 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 vFromKey or vToKey is not comparable to the map contents IllegalArgumentException  if this is a sub-map, and vFromKey or vToKey is out of range NullPointerException  if vFromKey or vToKey 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 vFromKey, and strictly less than vToKey. 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 vFromKey or vToKey is not comparable to the map contents IllegalArgumentException  if this is a sub-map, and vFromKey or vToKey is out of range NullPointerException  if vFromKey or vToKey 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 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. Parameters: vFromKey  the inclusive lower range of the sub-map Returns: the sub-map Exceptions: ClassCastException  if vFromKey is not comparable to the map contents IllegalArgumentException  if this is a sub-map, and vFromKey is out of range NullPointerException  if vFromKey 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 vFromKey. Parameters: vFromKey  the inclusive lower range of the sub-map Returns: the sub-map Exceptions: ClassCastException  if vFromKey is not comparable to the map contents IllegalArgumentException  if this is a sub-map, and vFromKey is out of range NullPointerException  if vFromKey is NULL but the map does not allow NULL keys
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. Parameters: vKey  the key Returns: the least key greater than or equal to the given key, or NULL if there is no such key. Exceptions: ClassCastException  if the specified key cannot be compared with the keys currently in the map NullPointerException  if the specified key is NULL and this map does not permit NULL keys
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. Parameters: vKey  the key Returns: the greatest key less than or equal to the given key, or NULL if there is no such key. Exceptions: ClassCastException  if the specified key cannot be compared with the keys currently in the map NullPointerException  if the specified key is NULL and this map does not permit NULL keys
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. Parameters: vKey  the key Returns: the least key greater than the given key, or NULL if there is no such key Exceptions: ClassCastException  if the specified key cannot be compared with the keys currently in the map NullPointerException  if the specified key is NULL and this map does not permit NULL keys
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. Parameters: vKey  the key Returns: the greatest key less than the given key, or NULL if there is no such key Exceptions: ClassCastException  if the specified key cannot be compared with the keys currently in the map NullPointerException  if the specified key is NULL and this map does not permit NULL keys
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. Returns: the removed first entry of this map, or NULL if this 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. Returns: the removed last entry of this map, or NULL if this 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. Parameters: vToKey  the exclusive upper range of the sub-map toInclusive  true if the high endpoint is to be included in the returned view Returns: the sub-map Exceptions: ClassCastException  if vToKey is not comparable to the map contents IllegalArgumentException  if this is a sub-map, and vToKey is out of range NullPointerException  if vToKey is NULL but the map does not allow NULL keys
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. Parameters: vToKey  the exclusive upper range of the sub-map toInclusive  true if the high endpoint is to be included in the returned view Returns: the sub-map Exceptions: ClassCastException  if vToKey is not comparable to the map contents IllegalArgumentException  if this is a sub-map, and toKey is out of range NullPointerException  if vToKey is NULL but the map does not allow NULL keys
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. Parameters: vFromKey  the inclusive lower range of the sub-map fromInclusive  true if the low endpoint is to be included in the returned view vToKey  the exclusive upper range of the sub-map toInclusive  true if the high endpoint is to be included in the returned view Returns: the sub-map Exceptions: ClassCastException  if vFromKey or vToKey is not comparable to the map contents IllegalArgumentException  if this is a sub-map, and vFromKey or vToKey is out of range NullPointerException  if vFromKey or vToKey is NULL but the map does not allow NULL keys
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. Parameters: vFromKey  the inclusive lower range of the sub-map fromInclusive  true if the low endpoint is to be included in the returned view vToKey  the exclusive upper range of the sub-map toInclusive  true if the high endpoint is to be included in the returned view Returns: the sub-map Exceptions: ClassCastException  if vFromKey or vToKey is not comparable to the map contents IllegalArgumentException  if this is a sub-map, and vFromKey or vToKey is out of range NullPointerException  if vFromKey or vToKey is NULL but the map does not allow NULL keys
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. Parameters: vFromKey  the inclusive lower range of the sub-map fromInclusive  true if the low endpoint is to be included in the returned view Returns: the sub-map Exceptions: ClassCastException  if vFromKey is not comparable to the map contents IllegalArgumentException  if this is a sub-map, and vFromKey is out of range NullPointerException  if vFromKey is NULL but the map does not allow NULL keys
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. Parameters: vFromKey  the inclusive lower range of the sub-map fromInclusive  true if the low endpoint is to be included in the returned view Returns: the sub-map Exceptions: ClassCastException  if vFromKey is not comparable to the map contents IllegalArgumentException  if this is a sub-map, and vFromKey is out of range NullPointerException  if vFromKey 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).
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...

---

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, 2019, Oracle and/or its affiliates. All rights reserved.