Oracle Coherence for C++ API
Release 3.7.0.0

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