#include <coherence/util/AbstractSparseArray.hpp>
Inherits AbstractLongArray.
Inherited by SparseArray.
Implementation is based on the public domain implementation by Julienne Walker. This implementation is not thread-safe.
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.
| |||||||
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.
| |||||||
virtual bool | exists (int64_t lIndex) const | ||||||
Determine if the specified index is in use.
| |||||||
virtual Object::Holder | remove (int64_t lIndex) | ||||||
Remove the specified index from the LongArray, returning its associated value.
| |||||||
virtual void | clear () | ||||||
Remove all nodes from the LongArray. | |||||||
virtual size32_t | getSize () const | ||||||
Determine the size of the LongArray.
| |||||||
virtual LongArrayIterator::Handle | iterator () | ||||||
Obtain a LongArray.Iterator of the contents of the LongArray.
| |||||||
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.
| |||||||
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.
| |||||||
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.
| |||||||
virtual int64_t | getFirstIndex () const | ||||||
Determine the first index that exists in the LongArray.
| |||||||
virtual int64_t | getLastIndex () const | ||||||
Determine the last index that exists in the LongArray.
| |||||||
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... |
virtual void remove | ( | Node::Handle | hNode | ) | [virtual] |
Remove the specified node from the tree.
The supplied node must be part of the tree.
hNode | the node to remove |
Reimplemented in SparseArray.
virtual bool isHead | ( | Node::View | vNode | ) | const [virtual] |
virtual Node::Handle find | ( | int64_t | lIndex | ) | const [protected, virtual] |
Find the specified key and return its node.
lIndex | the long index to look for in the SparseArray |
virtual Node::Handle replace | ( | Node::Handle | hNodeA, | |
Node::Handle | hNodeB | |||
) | [protected, virtual] |
Replace one node with another.
hNodeA | the node to be unlinked | |
hNodeB | the node to be linked in nodeA's place; may be NULL |
virtual Node::Handle rotate | ( | Node::Handle | hNode, | |
bool | fLeft | |||
) | [protected, virtual] |
Rotate a node in a given direction.
hNode | the node to rotate | |
fLeft | the rotation direction |
virtual Node::Handle doubleRotate | ( | Node::Handle | hNode, | |
bool | fLeft | |||
) | [protected, virtual] |
Double rotate a node in a given direction.
hNode | the node to rotate | |
fLeft | the final rotation direction |
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.
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.
lIndex | the index of the new node |
virtual void balancedInsertion | ( | Node::Handle | hParent, | |
Node::Handle | hChild | |||
) | [protected, virtual] |
Insert a node into a tree and re-balance.
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.
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] |
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.