|
Oracle® Coherence Java API Reference Release 3.6.0.0 E15725-01 |
|||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object
com.tangosol.util.Base
com.tangosol.util.AbstractLongArray
com.tangosol.util.AbstractSparseArray
public abstract class AbstractSparseArray
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.
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. |
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. |
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, 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. |
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. |
Object |
set(long lIndex, 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 |
---|
protected AbstractSparseArray.Node m_head
protected int m_size
Constructor Detail |
---|
public AbstractSparseArray()
Method Detail |
---|
public Object get(long lIndex)
get
in interface LongArray
get
in class AbstractLongArray
lIndex
- a long index valuepublic Object set(long lIndex, Object oValue)
lIndex
- a long index valueoValue
- the object to store at the specified indexpublic boolean exists(long lIndex)
exists
in interface LongArray
exists
in class AbstractLongArray
lIndex
- a long index valuepublic Object remove(long lIndex)
remove
in interface LongArray
remove
in class AbstractLongArray
lIndex
- the index into the LongArraypublic void clear()
clear
in interface LongArray
clear
in class AbstractLongArray
public int getSize()
getSize
in interface LongArray
getSize
in class AbstractLongArray
public LongArray.Iterator iterator()
public LongArray.Iterator iterator(long lIndex)
lIndex
- the LongArray index to iterate frompublic LongArray.Iterator reverseIterator()
public LongArray.Iterator reverseIterator(long lIndex)
lIndex
- the LongArray index to iterate frompublic long getFirstIndex()
getFirstIndex
in interface LongArray
getFirstIndex
in class AbstractLongArray
public long getLastIndex()
getLastIndex
in interface LongArray
getLastIndex
in class AbstractLongArray
public Object clone()
clone
in interface LongArray
clone
in class AbstractLongArray
public void print()
public void validate()
protected AbstractSparseArray.Node find(long lIndex)
lIndex
- the long index to look for in the SparseArrayprotected void remove(AbstractSparseArray.Node node)
node
- the node to removeprotected AbstractSparseArray.Node replace(AbstractSparseArray.Node nodeA, AbstractSparseArray.Node nodeB)
nodeA
- the node to be unlinkednodeB
- the node to be linked in nodeA's place; may be nullprotected AbstractSparseArray.Node rotate(AbstractSparseArray.Node node, boolean fLeft)
node
- the node to rotatefLeft
- the rotation directionprotected AbstractSparseArray.Node doubleRotate(AbstractSparseArray.Node node, boolean fLeft)
node
- the node to rotatefLeft
- the final rotation directionprotected void adjustDoubleBalance(AbstractSparseArray.Node node, AbstractSparseArray.Node child, int iBal)
node
- the node which was rotatedchild
- the child to adjustiBal
- the balance adjustmentprotected AbstractSparseArray.Node findInsertionPoint(long lIndex)
lIndex
- the index of the new nodeprotected void balancedInsertion(AbstractSparseArray.Node parent, AbstractSparseArray.Node child)
parent
- the location at which to insert the nodechild
- the node to insertprotected void balancePostRemove(AbstractSparseArray.Node pruned, boolean fPrunedLeft)
pruned
- the node whose sub-tree shurnkfPrunedLeft
- the side on which the sub-tree shurnkprotected abstract AbstractSparseArray.Node instantiateNode(long lKey, Object oValue)
lKey
- the long keyoValue
- the object valueprotected AbstractSparseArray.Crawler instantiateCrawler(AbstractSparseArray.Node head, int fromdir, boolean fForward)
head
- the node at which to start the crawlfromdir
- the direction in which to start the crawl
|
Oracle® Coherence Java API Reference Release 3.6.0.0 E15725-01 |
|||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |