Jive Forums API (5.5.20.2-oracle) Developer Javadocs

com.jivesoftware.util
Class LongTree

java.lang.Object
  extended by com.jivesoftware.util.LongTree
All Implemented Interfaces:
Cacheable, com.tangosol.io.ExternalizableLite, java.io.Serializable

public final class LongTree
extends java.lang.Object
implements Cacheable, java.io.Serializable, com.tangosol.io.ExternalizableLite

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.

See Also:
Serialized Form

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

LongTree

public LongTree(long rootKey,
                int initialCapacity)
Creates a new tree.

Parameters:
rootKey - the value of the root node of the tree.
initialCapacity - the maximum initial capacity of the tree.

LongTree

public LongTree()
Constructor for use with the Externalizable interface. Normal users of this class should not call this constructor.

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, or -1 if there is no parent.


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.

getRecursiveKeys

public long[] getRecursiveKeys()
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.

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.

Parameters:
parentKey - the parent key to get children of.
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.


getCachedSize

public int getCachedSize()
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:
getCachedSize in interface Cacheable
Returns:
the size of the Object in bytes.

writeExternal

public void writeExternal(java.io.DataOutput out)
                   throws java.io.IOException
Specified by:
writeExternal in interface com.tangosol.io.ExternalizableLite
Throws:
java.io.IOException

readExternal

public void readExternal(java.io.DataInput in)
                  throws java.io.IOException
Specified by:
readExternal in interface com.tangosol.io.ExternalizableLite
Throws:
java.io.IOException

Jive Forums Project Page

Copyright © 1999-2006 Jive Software.