|
Jive Forums API (5.5.20.2-oracle) Developer Javadocs | |||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectcom.jivesoftware.util.LongTree
public final class LongTree
A simple tree structure for long values. It's nowhere near a complete tree implementation since we don't really need one. However, if anyone is interested in finishing this class, or optimizing it, that would be appreciated.
The tree uses three arrays to keep the tree structure. It works as in the following example:
1 |-- 3 |-- |--4 |-- |--6 |-- 5 array index: 0 | 1 | 2 | 3 | 4 key: 1 | 3 | 4 | 5 | 6 leftChild: 1 | 2 |-1 |-1 |-1 rightChild -1 | 3 | 4 |-1 |-1Where the key array holds key values, and the leftChild and rightChild arrays are pointers to other array indices.
The tree holds a maximum of 65534 nodes. It is not intended to be thread-safe. Based on algorithm found in the book "Introduction To Algorithms" by Cormen et all, MIT Press, 1997.
Constructor Summary | |
---|---|
LongTree()
Constructor for use with the Externalizable interface. |
|
LongTree(long rootKey,
int initialCapacity)
Creates a new tree. |
Method Summary | |
---|---|
void |
addChild(long parentKey,
long newKey)
Adds a child to the tree. |
int |
getCachedSize()
Returns the approximate size of the Object in bytes. |
long |
getChild(long parentKey,
int index)
Returns a child of parentKey at index index . |
int |
getChildCount(long parentKey)
Returns the number of children of parentKey . |
long[] |
getChildren(long parentKey)
Returns an array of the children of the parentKey, or an empty array if there are no children or the parent key is not in the tree. |
int |
getDepth(long key)
Returns the depth in the tree that the element can be found at or -1 if the element is not in the tree. |
int |
getIndexOfChild(long parentKey,
long childKey)
Returns the index of childKey in parentKey or
-1 if childKey is not a child of parentKey . |
long |
getParent(long childKey)
Returns a parent of childKey , or -1 if there is no parent. |
long[] |
getRecursiveChildren(long parentKey)
Returns the keys in the in the tree in depth-first order. |
long[] |
getRecursiveKeys()
Returns the keys in the in the tree in depth-first order. |
boolean |
isLeaf(long key)
Returns true if the tree node is a leaf. |
long[] |
keys()
Returns the keys in the tree. |
void |
readExternal(java.io.DataInput in)
|
void |
writeExternal(java.io.DataOutput out)
|
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Constructor Detail |
---|
public LongTree(long rootKey, int initialCapacity)
rootKey
- the value of the root node of the tree.initialCapacity
- the maximum initial capacity of the tree.public LongTree()
Method Detail |
---|
public void addChild(long parentKey, long newKey)
parentKey
- the parent to add the new value to.newKey
- new value to add to the tree.public long getParent(long childKey)
childKey
, or -1 if there is no parent.
public long getChild(long parentKey, int index)
parentKey
at index index
.
public int getChildCount(long parentKey)
parentKey
.
public long[] getChildren(long parentKey)
parentKey
- the parent to get the children of.
public int getIndexOfChild(long parentKey, long childKey)
childKey
in parentKey
or
-1 if childKey
is not a child of parentKey
.
public int getDepth(long key)
key
- the key to find the depth for.
public long[] getRecursiveKeys()
1 |-- 3 |-- |-- 4 |-- |-- |-- 7 |-- |-- 6 |-- 5Then this method would return the sequence: 1, 3, 4, 7, 6, 5.
public long[] getRecursiveChildren(long parentKey)
1 |-- 3 |-- |-- 4 |-- |-- |-- 7 |-- |-- 6 |-- 5Then this method would return the sequence: 1, 3, 4, 7, 6, 5.
parentKey
- the parent key to get children of.
public boolean isLeaf(long key)
key
has no children.public long[] keys()
public int getCachedSize()
Cacheable
getCachedSize
in interface Cacheable
public void writeExternal(java.io.DataOutput out) throws java.io.IOException
writeExternal
in interface com.tangosol.io.ExternalizableLite
java.io.IOException
public void readExternal(java.io.DataInput in) throws java.io.IOException
readExternal
in interface com.tangosol.io.ExternalizableLite
java.io.IOException
|
Jive Forums Project Page | |||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |