Package com.tangosol.util

Class AbstractSparseArray<V>

    • Field Detail

      • 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 Detail

      • AbstractSparseArray

        public AbstractSparseArray()
        Default constructor.

    • Method Detail

      • 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)

      • 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

      • 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

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