public abstract class AbstractSparseArray<V> extends AbstractLongArray<V>
Modifier and Type | Class and Description |
---|---|
protected class |
AbstractSparseArray.Crawler
A tree node iterator.
|
protected static class |
AbstractSparseArray.Node<V>
An AVL tree node.
|
LongArray.Iterator<V>
Modifier and Type | Field and Description |
---|---|
protected AbstractSparseArray.Node<V> |
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.
|
Constructor and Description |
---|
AbstractSparseArray()
Default constructor.
|
Modifier and Type | Method and Description |
---|---|
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.
|
protected void |
balancedInsertion(AbstractSparseArray.Node<V> parent,
AbstractSparseArray.Node<V> child)
Insert a node into a tree and rebalance.
|
protected void |
balancePostRemove(AbstractSparseArray.Node<V> pruned,
boolean fPrunedLeft)
Rebalance the tree following the removal of a node.
|
V |
ceiling(long lIndex)
Return the "first" value with an index which is greater than or equal to the specified index.
|
long |
ceilingIndex(long lIndex)
Return the "first" index which is greater than or equal to the specified index.
|
void |
clear()
Remove all nodes from the LongArray.
|
AbstractSparseArray<V> |
clone()
Make a clone of the LongArray.
|
protected AbstractSparseArray.Node<V> |
doubleRotate(AbstractSparseArray.Node<V> 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<V> |
find(long lIndex)
Find the specified key and return its node.
|
protected AbstractSparseArray.Node<V> |
findInsertionPoint(long lIndex)
Find the point at which a Node with the specified index would be inserted.
|
V |
floor(long lIndex)
Return the "first" value with an index which is less than or equal to the specified index.
|
long |
floorIndex(long lIndex)
Return the "first" index which is less than or equal to the specified index.
|
V |
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<V> head,
int fromdir,
boolean fForward)
Instantiate a new Crawler at the specified location and direction.
|
protected abstract AbstractSparseArray.Node<V> |
instantiateNode(long lKey,
V oValue)
Factory pattern: create a new Node with the specified key and value.
|
LongArray.Iterator<V> |
iterator()
Obtain a LongArray.Iterator of the contents of the LongArray.
|
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. |
void |
print()
In-order printing of the contents of the SparseArray.
|
protected void |
remove(AbstractSparseArray.Node<V> node)
Remove the specified node from the tree.
|
V |
remove(long lIndex)
Remove the specified index from the LongArray, returning its associated
value.
|
void |
remove(long lIndexFrom,
long lIndexTo)
Remove all nodes in the specified range.
|
protected AbstractSparseArray.Node<V> |
replace(AbstractSparseArray.Node<V> nodeA,
AbstractSparseArray.Node<V> nodeB)
Replace one node with another.
|
LongArray.Iterator<V> |
reverseIterator()
Obtain a LongArray.Iterator of the contents of the LongArray in
reverse order (decreasing indices).
|
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. |
protected AbstractSparseArray.Node<V> |
rotate(AbstractSparseArray.Node<V> node,
boolean fLeft)
Rotate a node in a given direction.
|
V |
set(long lIndex,
V oValue)
Add the passed item to the LongArray at the specified index.
|
void |
validate()
Validate that the tree is a proper AVL tree.*
Note, Java assertions must be enabled for this to be effective.
|
add, contains, equals, hashCode, indexOf, indexOf, isEmpty, lastIndexOf, lastIndexOf, toString
finalize, getClass, notify, notifyAll, wait, wait, wait
forEach, spliterator
protected AbstractSparseArray.Node<V> m_head
protected int m_size
public V get(long lIndex)
public long floorIndex(long lIndex)
lIndex
- the indexpublic V floor(long lIndex)
lIndex
- the indexpublic long ceilingIndex(long lIndex)
lIndex
- the indexpublic V ceiling(long lIndex)
lIndex
- the indexpublic V set(long lIndex, V oValue)
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.
lIndex
- a long index valueoValue
- the object to store at the specified indexpublic boolean exists(long lIndex)
public V remove(long lIndex)
public void remove(long lIndexFrom, long lIndexTo)
public void clear()
public int getSize()
public LongArray.Iterator<V> iterator()
public LongArray.Iterator<V> iterator(long lIndex)
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.lIndex
- the LongArray index to iterate frompublic LongArray.Iterator<V> reverseIterator()
public LongArray.Iterator<V> reverseIterator(long lIndex)
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.lIndex
- the LongArray index to iterate frompublic long getFirstIndex()
getFirstIndex
in interface LongArray<V>
getFirstIndex
in class AbstractLongArray<V>
public long getLastIndex()
getLastIndex
in interface LongArray<V>
getLastIndex
in class AbstractLongArray<V>
public AbstractSparseArray<V> clone()
public void print()
public void validate()
protected AbstractSparseArray.Node<V> find(long lIndex)
lIndex
- the long index to look for in the SparseArrayprotected void remove(AbstractSparseArray.Node<V> node)
The supplied node must be part of the tree.
node
- the node to removeprotected AbstractSparseArray.Node<V> replace(AbstractSparseArray.Node<V> nodeA, AbstractSparseArray.Node<V> nodeB)
nodeA
- the node to be unlinkednodeB
- the node to be linked in nodeA's place; may be nullprotected AbstractSparseArray.Node<V> rotate(AbstractSparseArray.Node<V> node, boolean fLeft)
node
- the node to rotatefLeft
- the rotation directionprotected AbstractSparseArray.Node<V> doubleRotate(AbstractSparseArray.Node<V> node, boolean fLeft)
node
- the node to rotatefLeft
- the final rotation directionprotected void adjustDoubleBalance(AbstractSparseArray.Node<V> node, AbstractSparseArray.Node<V> child, int iBal)
node
- the node which was rotatedchild
- the child to adjustiBal
- the balance adjustmentprotected AbstractSparseArray.Node<V> findInsertionPoint(long lIndex)
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.
lIndex
- the index of the new nodeprotected void balancedInsertion(AbstractSparseArray.Node<V> parent, AbstractSparseArray.Node<V> child)
parent
- the location at which to insert the nodechild
- the node to insertprotected void balancePostRemove(AbstractSparseArray.Node<V> pruned, boolean fPrunedLeft)
pruned
- the node whose sub-tree shrunkfPrunedLeft
- the side on which the sub-tree shrunkprotected abstract AbstractSparseArray.Node<V> instantiateNode(long lKey, V oValue)
lKey
- the long keyoValue
- the object valueprotected AbstractSparseArray.Crawler instantiateCrawler(AbstractSparseArray.Node<V> head, int fromdir, boolean fForward)
head
- the node at which to start crawlingfromdir
- the direction in which to start crawlingfForward
- true iff crawler should advance forward towards
the next element