Skip navigation links

Oracle® Coherence Java API Reference
Release 3.7.0.0

E18683-01


com.tangosol.util
Class AbstractSparseArray

java.lang.Object
  extended by com.tangosol.util.Base
      extended by com.tangosol.util.AbstractLongArray
          extended by 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

Oracle® Coherence Java API Reference
Release 3.7.0.0

E18683-01


Copyright © 2000, 2011, Oracle and/or its affiliates. All rights reserved.