Skip navigation links

Overview | Package | Class | Tree | Index | Help
| Oracle® Coherence Java API Reference Release 3.6.1.0 E18814-01
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## 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, 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

Overview | Package | Class | Tree | Index | Help
| Oracle® Coherence Java API Reference Release 3.6.1.0 E18814-01
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

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