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

AbstractSparseArray Class Reference

#include <coherence/util/AbstractSparseArray.hpp>

Inherits AbstractLongArray.

Inherited by SparseArray.

List of all members.

Detailed Description

A data structure resembling an array indexed by long values, 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:: js 2008.04.25

Public Types

typedef spec::Handle Handle

AbstractSparseArray Handle definition.

typedef spec::View View

AbstractSparseArray View definition.

typedef spec::Holder Holder

AbstractSparseArray Holder definition.

Public Member Functions

virtual Object::Holder get (int64_t lIndex) const

Return the value stored at the specified index.

Parameters:

lIndex

a long index value

Returns:: the object stored at the specified index, or NULL

virtual Object::Holder set (int64_t lIndex, Object::Holder ohValue)

Add the passed item to the LongArray at the specified index.

If the index is already used, the passed value will replace the current value stored with the key, and the replaced value will be returned.

It is expected that LongArray implementations will "grow" as necessary to support the specified index.

Parameters:

	lIndex	a long index value
	ohValue	the object to store at the specified index

Returns:: the object that was stored at the specified index, or NULL

virtual bool exists (int64_t lIndex) const

Determine if the specified index is in use.

Parameters:

lIndex

a long index value

Returns:: true if a value (including NULL) is stored at the specified index, otherwise false

virtual Object::Holder remove (int64_t lIndex)

Remove the specified index from the LongArray, returning its associated value.

Parameters:

lIndex

the index into the LongArray

Returns:: the associated value (which can be NULL) or NULL if the specified index is not in the LongArray

virtual void clear ()

Remove all nodes from the LongArray.

virtual size32_t getSize () const

Determine the size of the LongArray.

Returns:: the number of nodes in the LongArray

virtual
LongArrayIterator::Handle iterator ()

Obtain a LongArray.Iterator of the contents of the LongArray.

Returns:: an instance of LongArray.Iterator

virtual
LongArrayIterator::Handle iterator () const

Obtain a "read-only" LongArray.Iterator of the contents of the LongArray.

Any attempt to modify the backing LongArray through this iterator will result in an exception.

Returns:: an instance of LongArray.Iterator

virtual
LongArrayIterator::Handle iterator (int64_t lIndex)

Obtain a LongArray.Iterator of the contents of the LongArray, starting at a particular index such that the first call to next will set the location of the iterator at the first existent index that is greater than or equal to the specified index, or will throw a NoSuchElementException if there is no such existent index.

Parameters:

lIndex

the LongArray index to iterate from

Returns:: an instance of LongArray.Iterator

virtual
LongArrayIterator::Handle iterator (int64_t lIndex) const

Obtain a "read-only" LongArray.Iterator of the contents of the LongArray, starting at a particular index such that the first call to next will set the location of the iterator at the first existent index that is greater than or equal to the specified index, or will throw a NoSuchElementException if there is no such existent index.

Any attempt to modify the backing LongArray through this iterator will result in an exception.

Parameters:

lIndex

the LongArray index to iterate from

Returns:: an instance of LongArray.Iterator

virtual int64_t getFirstIndex () const

Determine the first index that exists in the LongArray.

Returns:: the lowest long value, 0 <= n <= Long.max_value, that exists in this LongArray, or -1 if the LongArray is empty

virtual int64_t getLastIndex () const

Determine the last index that exists in the LongArray.

Returns:: the highest long value, 0 <= n <= Long.max_value, that exists in this LongArray, or -1 if the LongArray is empty

virtual void remove (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.

Protected Member Functions

virtual Node::Handle find (int64_t lIndex) const

Find the specified key and return its node.

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 (int64_t lIndex) 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 (int64_t lKey, Object::Holder ohValue)=0

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

Classes

class Node

An AVL tree node. More...

Member Function Documentation

virtual void remove ( 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 Node::Handle find ( int64_t lIndex ) const [protected, virtual]

Find the specified key and return its node.

Parameters:

lIndex

the long index to look for in the SparseArray

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

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 ( int64_t lIndex ) 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:

lIndex

the index 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	(	int64_t	lKey,
		Object::Holder	ohValue
	)			`[protected, pure virtual]`

Create a new Node.

Parameters:

	lKey	the key of the new Node
	ohValue	the value of the new Node

Returns:: the newly instantiated Node

Implemented in SparseArray.

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/AbstractSparseArray.hpp