com.tangosol.util
Class SparseArray

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

All Implemented Interfaces:

LongArray, Serializable, Cloneable

public class SparseArray
extends AbstractLongArray
implements LongArray

A data structure resembling an array keyed by Java long values.

Version:

1.00 04/23/02 used Tree to create SparseArray

Author:

Cameron Purdy

See Also:

Tree

Nested Class Summary

protected class	SparseArray.Crawler A red/black tree node iterator.
protected static class	SparseArray.Node A red/black tree node.

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

LongArray.Iterator

Field Summary

protected SparseArray.Node	head The first node of the tree (or NIL if the tree is empty).
protected static SparseArray.Node	NIL NIL is the sentinal Node that is used instead of null, simplifying the implementation of the red/black tree.
protected int	size The number of nodes in the tree.

Constructor Summary

SparseArray()
Default constructor.

Method Summary

protected void	balance(SparseArray.Node child) Maintain balance on insertion.
void	clear() Remove all nodes from the LongArray.
Object	clone() Make a clone of the LongArray.
boolean	exists(long lIndex) Determine if the specified index is in use.
protected SparseArray.Node	find(long lIndex) Find the specified key and return its node.
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.
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.
Object	remove(long lIndex) Remove the specified index from the LongArray, returning its associated value.
Object	set(long lIndex, Object oValue) Add the passed item to the LongArray at the specified index.

Methods inherited from class com.tangosol.util.AbstractLongArray

add, contains, equals, isEmpty, toString

Methods inherited from interface com.tangosol.util.LongArray

add, contains, equals, isEmpty, toString

Field Detail

NIL

protected static final SparseArray.Node NIL

NIL is the sentinal Node that is used instead of null, simplifying the implementation of the red/black tree.

head

protected SparseArray.Node head

The first node of the tree (or NIL if the tree is empty). The first node is referred to as the "head" or the "root" node.

size

protected int 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

SparseArray

public SparseArray()

Default constructor.

Method Detail

get

public 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 Object set(long lIndex,
                  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.

Specified by:

set in interface LongArray

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

Specified by:

iterator in interface 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.

Specified by:

iterator in interface LongArray

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, 0 <= n <= Long.MAX_VALUE, that exists in this LongArray, or -1 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, 0 <= n <= Long.MAX_VALUE, that exists in this LongArray, or -1 if the LongArray is empty

clone

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

find

protected SparseArray.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

balance

protected void balance(SparseArray.Node child)

Maintain balance on insertion.

Parameters:

child - the current node in the traversal of the tree