Skip navigation links

com.tangosol.util
Class AbstractSparseArray

java.lang.Object
com.tangosol.util.Base
com.tangosol.util.AbstractLongArray
com.tangosol.util.AbstractSparseArray

All Implemented Interfaces:

LongArray, java.io.Serializable, java.lang.Cloneable

Direct Known Subclasses:

PrimitiveSparseArray, SparseArray

public abstract class AbstractSparseArray

extends AbstractLongArray

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.

Author:

cp, mf 10.08.2007

See Also:

Implementation by Julienne Walker

Nested Class Summary

protected class	AbstractSparseArray.Crawler A tree node iterator.
protected static class	AbstractSparseArray.Node An AVL tree node.

Nested classes/interfaces inherited from interface com.tangosol.util.LongArray

LongArray.Iterator

Field Summary

protected AbstractSparseArray.Node	m_head The first node of the tree (or null if the tree is empty).
protected int	m_size The number of nodes in the tree.

Fields inherited from interface com.tangosol.util.LongArray

NOT_FOUND

Constructor Summary

AbstractSparseArray()
Default constructor.

Method Summary

protected void	adjustDoubleBalance(AbstractSparseArray.Node node, AbstractSparseArray.Node child, int iBal) Adjust the balance factor of a node and its decendentans prior to a a double rotation.
protected void	balancedInsertion(AbstractSparseArray.Node parent, AbstractSparseArray.Node child) Insert a node into a tree and rebalance.
protected void	balancePostRemove(AbstractSparseArray.Node pruned, boolean fPrunedLeft) Rebalance the tree following the removal of a node.
void	clear() Remove all nodes from the LongArray.
java.lang.Object	clone() Make a clone of the LongArray.
protected AbstractSparseArray.Node	doubleRotate(AbstractSparseArray.Node node, boolean fLeft) Double rotate a node in a given direction.
boolean	exists(long lIndex) Determine if the specified index is in use.
protected AbstractSparseArray.Node	find(long lIndex) Find the specified key and return its node.
protected AbstractSparseArray.Node	findInsertionPoint(long lIndex) Find the point at which a Node with the specified index would be inserted.
java.lang.Object	get(long lIndex) Return the value stored at the specified index.
long	getFirstIndex() Determine the first index that exists in the LongArray.
long	getLastIndex() Determine the last index that exists in the LongArray.
int	getSize() Determine the size of the LongArray.
protected AbstractSparseArray.Crawler	instantiateCrawler(AbstractSparseArray.Node head, int fromdir, boolean fForward) Instantate a new Crawler at the specified location and direction.
protected abstract AbstractSparseArray.Node	instantiateNode(long lKey, java.lang.Object oValue) Factory pattern: create a new Node with the specified key and value.
LongArray.Iterator	iterator() Obtain a LongArray.Iterator of the contents of the LongArray.
LongArray.Iterator	iterator(long 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.
void	print() In-order printing of the contents of the SparseArray.
protected void	remove(AbstractSparseArray.Node node) Remove the specified node from the tree.
java.lang.Object	remove(long lIndex) Remove the specified index from the LongArray, returning its associated value.
protected AbstractSparseArray.Node	replace(AbstractSparseArray.Node nodeA, AbstractSparseArray.Node nodeB) Replace one node with another.
LongArray.Iterator	reverseIterator() Obtain a LongArray.Iterator of the contents of the LongArray in reverse order (decreasing indices).
LongArray.Iterator	reverseIterator(long lIndex) Obtain a LongArray.Iterator of the contents of the LongArray in reverse order (decreasing indices), 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 less than or equal to the specified index, or will throw a NoSuchElementException if there is no such existent index.
protected AbstractSparseArray.Node	rotate(AbstractSparseArray.Node node, boolean fLeft) Rotate a node in a given direction.
java.lang.Object	set(long lIndex, java.lang.Object oValue) Add the passed item to the LongArray at the specified index.
void	validate() Validate that the tree is a proper AVL tree.

Methods inherited from class com.tangosol.util.AbstractLongArray

add, contains, equals, hashCode, indexOf, indexOf, isEmpty, lastIndexOf, lastIndexOf, toString

Field Detail

m_head

protected AbstractSparseArray.Node m_head

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.

m_size

protected int m_size

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.

Constructor Detail

AbstractSparseArray

public AbstractSparseArray()

Default constructor.

Method Detail

get

public java.lang.Object get(long lIndex)

Return the value stored at the specified index.

Specified by:

get in interface LongArray

Overrides:

get in class AbstractLongArray

Parameters:

lIndex - a long index value

Returns:

the object stored at the specified index, or null

set

public java.lang.Object set(long lIndex,
                            java.lang.Object oValue)

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

oValue - the object to store at the specified index

Returns:

the object that was stored at the specified index, or null

exists

public boolean exists(long lIndex)

Determine if the specified index is in use.

Specified by:

exists in interface LongArray

Overrides:

exists in class AbstractLongArray

Parameters:

lIndex - a long index value

Returns:

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

remove

public java.lang.Object remove(long lIndex)

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

Specified by:

remove in interface LongArray

Overrides:

remove in class AbstractLongArray

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

clear

public void clear()

Remove all nodes from the LongArray.

Specified by:

clear in interface LongArray

Overrides:

clear in class AbstractLongArray

getSize

public int getSize()

Determine the size of the LongArray.

Specified by:

getSize in interface LongArray

Overrides:

getSize in class AbstractLongArray

Returns:

the number of nodes in the LongArray

iterator

public LongArray.Iterator iterator()

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

Returns:

an instance of LongArray.Iterator

iterator

public LongArray.Iterator iterator(long 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

reverseIterator

public LongArray.Iterator reverseIterator()

Obtain a LongArray.Iterator of the contents of the LongArray in reverse order (decreasing indices).

Returns:

an instance of LongArray.Iterator

reverseIterator

public LongArray.Iterator reverseIterator(long lIndex)

Obtain a LongArray.Iterator of the contents of the LongArray in reverse order (decreasing indices), 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 less 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

getFirstIndex

public long getFirstIndex()

Determine the first index that exists in the LongArray.

Specified by:

getFirstIndex in interface LongArray

Overrides:

getFirstIndex in class AbstractLongArray

Returns:

the lowest long value that exists in this LongArray, or NOT_FOUND if the LongArray is empty

getLastIndex

public long getLastIndex()

Determine the last index that exists in the LongArray.

Specified by:

getLastIndex in interface LongArray

Overrides:

getLastIndex in class AbstractLongArray

Returns:

the highest long value that exists in this LongArray, or NOT_FOUND if the LongArray is empty

clone

public java.lang.Object clone()

Make a clone of the LongArray. The element values are not deep-cloned.

Specified by:

clone in interface LongArray

Overrides:

clone in class AbstractLongArray

Returns:

a clone of this LongArray object

print

public void print()

In-order printing of the contents of the SparseArray.

validate

public void validate()

Validate that the tree is a proper AVL tree.

find

protected AbstractSparseArray.Node find(long lIndex)

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

remove

protected void remove(AbstractSparseArray.Node node)

Remove the specified node from the tree.

The supplied node must be part of the tree.

Parameters:

node - the node to remove

replace

protected AbstractSparseArray.Node replace(AbstractSparseArray.Node nodeA,
                                           AbstractSparseArray.Node nodeB)

Replace one node with another.

Parameters:

nodeA - the node to be unlinked

nodeB - the node to be linked in nodeA's place; may be null

Returns:

nodeB's new parent;

rotate

protected AbstractSparseArray.Node rotate(AbstractSparseArray.Node node,
                                          boolean fLeft)

Rotate a node in a given direction.

Parameters:

node - the node to rotate

fLeft - the rotation direction

Returns:

the node's new parent (former child)

doubleRotate

protected AbstractSparseArray.Node doubleRotate(AbstractSparseArray.Node node,
                                                boolean fLeft)

Double rotate a node in a given direction.

Parameters:

node - the node to rotate

fLeft - the final rotation direction

Returns:

the node's new parent (former grandchild)

adjustDoubleBalance

protected void adjustDoubleBalance(AbstractSparseArray.Node node,
                                   AbstractSparseArray.Node child,
                                   int iBal)

Adjust the balance factor of a node and its decendentans prior to a a double rotation.

Parameters:

node - the node which was rotated

child - the child to adjust

iBal - the balance adjustment

findInsertionPoint

protected AbstractSparseArray.Node findInsertionPoint(long lIndex)

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

balancedInsertion

protected void balancedInsertion(AbstractSparseArray.Node parent,
                                 AbstractSparseArray.Node child)

Insert a node into a tree and rebalance.

Parameters:

parent - the location at which to insert the node

child - the node to insert

balancePostRemove

protected void balancePostRemove(AbstractSparseArray.Node pruned,
                                 boolean fPrunedLeft)

Rebalance the tree following the removal of a node.

Parameters:

pruned - the node whose sub-tree shurnk

fPrunedLeft - the side on which the sub-tree shurnk

instantiateNode

protected abstract AbstractSparseArray.Node instantiateNode(long lKey,
                                                            java.lang.Object oValue)

Factory pattern: create a new Node with the specified key and value.

Parameters:

lKey - the long key

oValue - the object value

Returns:

the new node

instantiateCrawler

protected AbstractSparseArray.Crawler instantiateCrawler(AbstractSparseArray.Node head,
                                                         int fromdir,
                                                         boolean fForward)

Instantate a new Crawler at the specified location and direction.

Parameters:

head - the node at which to start the crawl

fromdir - the direction in which to start the crawl

Returns:

the new crawler

Skip navigation links