Package com.tangosol.util

Class AbstractSparseArray<V>

java.lang.Object
com.tangosol.util.AbstractLongArray<V>
com.tangosol.util.AbstractSparseArray<V>
All Implemented Interfaces:
LongArray<V>, Serializable, Cloneable, Iterable<V>
Direct Known Subclasses:
PrimitiveSparseArray, SparseArray
public abstract class AbstractSparseArray<V> extends AbstractLongArray<V>
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 2007.10.08
See Also:

  • Field Details

    • m_head

      protected AbstractSparseArray.Node<V> 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 Details

    • AbstractSparseArray

      public AbstractSparseArray()
      Default constructor.

  • Method Details

    • get

      public V get(long lIndex)
      Return the value stored at the specified index.
      Specified by:
      get in interface LongArray<V>
      Overrides:
      get in class AbstractLongArray<V>
      Parameters:
      lIndex - a long index value
      Returns:
      the object stored at the specified index, or null

    • floorIndex

      public long floorIndex(long lIndex)
      Return the "first" index which is less than or equal to the specified index.
      Parameters:
      lIndex - the index
      Returns:
      the index or NOT_FOUND

    • floor

      public V floor(long lIndex)
      Return the "first" value with an index which is less than or equal to the specified index.
      Parameters:
      lIndex - the index
      Returns:
      the value or null

    • ceilingIndex

      public long ceilingIndex(long lIndex)
      Return the "first" index which is greater than or equal to the specified index.
      Parameters:
      lIndex - the index
      Returns:
      the index or NOT_FOUND

    • ceiling

      public V ceiling(long lIndex)
      Return the "first" value with an index which is greater than or equal to the specified index.
      Parameters:
      lIndex - the index
      Returns:
      the value or null

    • set

      public V set(long lIndex, V 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<V>
      Overrides:
      exists in class AbstractLongArray<V>
      Parameters:
      lIndex - a long index value
      Returns:
      true if a value (including null) is stored at the specified index, otherwise false

    • remove

      public V remove(long lIndex)
      Remove the specified index from the LongArray, returning its associated value.
      Specified by:
      remove in interface LongArray<V>
      Overrides:
      remove in class AbstractLongArray<V>
      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

    • remove

      public void remove(long lIndexFrom, long lIndexTo)
      Remove all nodes in the specified range.
      Specified by:
      remove in interface LongArray<V>
      Overrides:
      remove in class AbstractLongArray<V>
      Parameters:
      lIndexFrom - the floor index
      lIndexTo - the ceiling index (exclusive)

    • clear

      public void clear()
      Remove all nodes from the LongArray.
      Specified by:
      clear in interface LongArray<V>
      Overrides:
      clear in class AbstractLongArray<V>

    • getSize

      public int getSize()
      Determine the size of the LongArray.
      Specified by:
      getSize in interface LongArray<V>
      Overrides:
      getSize in class AbstractLongArray<V>
      Returns:
      the number of nodes in the LongArray

    • iterator

      public LongArray.Iterator<V> iterator()
      Obtain a LongArray.Iterator of the contents of the LongArray.
      Returns:
      an instance of LongArray.Iterator

    • iterator

      public LongArray.Iterator<V> 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<V> 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<V> 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<V>
      Overrides:
      getFirstIndex in class AbstractLongArray<V>
      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<V>
      Overrides:
      getLastIndex in class AbstractLongArray<V>
      Returns:
      the highest long value that exists in this LongArray, or NOT_FOUND if the LongArray is empty

    • clone

      public AbstractSparseArray<V> clone()
      Make a clone of the LongArray. The element values are not deep-cloned.
      Specified by:
      clone in interface LongArray<V>
      Overrides:
      clone in class AbstractLongArray<V>
      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.* Note, Java assertions must be enabled for this to be effective.

    • find

      protected AbstractSparseArray.Node<V> 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<V> 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<V> replace(AbstractSparseArray.Node<V> nodeA, AbstractSparseArray.Node<V> 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<V> rotate(AbstractSparseArray.Node<V> 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<V> doubleRotate(AbstractSparseArray.Node<V> 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<V> node, AbstractSparseArray.Node<V> child, int iBal)
      Adjust the balance factor of a node and its descendants 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<V> 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<V> parent, AbstractSparseArray.Node<V> 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<V> pruned, boolean fPrunedLeft)
      Rebalance the tree following the removal of a node.
      Parameters:
      pruned - the node whose sub-tree shrunk
      fPrunedLeft - the side on which the sub-tree shrunk

    • instantiateNode

      protected abstract AbstractSparseArray.Node<V> instantiateNode(long lKey, V 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<V>.Crawler instantiateCrawler(AbstractSparseArray.Node<V> head, int fromdir, boolean fForward)
      Instantiate a new Crawler at the specified location and direction.
      Parameters:
      head - the node at which to start crawling
      fromdir - the direction in which to start crawling
      fForward - true iff crawler should advance forward towards the next element
      Returns:
      the new crawler