com.jivesoftware.util
Class LongTree

java.lang.Object
  |
  +--com.jivesoftware.util.LongTree

public final class LongTree

extends Object

implements Cacheable

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 |-1
 

Where 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(long rootKey, int size)
Constructs a new tree.

Method Summary

void	addChild(long parentKey, long newKey) Adds a child to the tree.
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.
long[]	getRecursiveChildren(long parentKey) Returns the keys in the in the tree in depth-first order.
int	getSize() Returns the approximate size of the Object in bytes.
boolean	isLeaf(long key) Returns true if the tree node is a leaf.
long[]	keys() Returns the keys in the tree.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

LongTree

public LongTree(long rootKey,
                int size)

Constructs a new tree.

Parameters:

rootKey - the value of the root node of the tree.

size - the maximum size of the tree. It cannot grow beyond this size.

Method Detail

addChild

public void addChild(long parentKey,
                     long newKey)

Adds a child to the tree.

Parameters:

parentKey - the parent to add the new value to.

newKey - new value to add to the tree.

getParent

public long getParent(long childKey)

Returns a parent of childKey.

getChild

public long getChild(long parentKey,
                     int index)

Returns a child of parentKey at index index.

getChildCount

public int getChildCount(long parentKey)

Returns the number of children of parentKey.

getChildren

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

Parameters:

parentKey - the parent to get the children of.

Returns:

the children of parentKey

getIndexOfChild

public int getIndexOfChild(long parentKey,
                           long childKey)

Returns the index of childKey in parentKey or -1 if childKey is not a child of parentKey.

getDepth

public 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. For example, the root element is depth 0, direct children of the root element are depth 1, etc.

Parameters:

key - the key to find the depth for.

Returns:

the depth of key in the tree hiearchy.

getRecursiveChildren

public long[] getRecursiveChildren(long parentKey)

Returns the keys in the in the tree in depth-first order. For example, give the tree:

   1
   |-- 3
   |-- |-- 4
   |-- |-- |-- 7
   |-- |-- 6
   |-- 5
 

Then this method would return the sequence: 1, 3, 4, 7, 6, 5.

Returns:

the keys of the tree in depth-first order.

isLeaf

public boolean isLeaf(long key)

Returns true if the tree node is a leaf.

Returns:

true if key has no children.

keys

public long[] keys()

Returns the keys in the tree.

getSize

public int getSize()

Description copied from interface: Cacheable

Returns the approximate size of the Object in bytes. The size should be considered to be a best estimate of how much memory the Object occupies and may be based on empirical trials or dynamic calculations.

Specified by:

getSize in interface Cacheable

Tags copied from interface: Cacheable

Returns:

the size of the Object in bytes.