Mega Code Archive
Tree Node
<![CDATA[
//package org.j4me.collections;
/**
* <code>TreeNode</code> objects can be combined into a tree. The tree is not
* a special tree such as a balanced tree. It can have any number of levels
* and each node can have any number of children.
* <p>
* Each tree node may have at most one parent and 0 or more children.
* <code>TreeNode</code> provides operations for examining and modifying a node's
* parent and children. A node's tree is the set of all nodes that can be
* reached by starting at the node and following all the possible links to
* parents and children. A node with no parent is the root of its tree; a
* node with no children is a leaf. A tree may consist of many subtrees,
* each node acting as the root for its own subtree.
* <p>
* Every <code>TreeNode</code> can hold a reference to one user object. It is up
* to the developer to decide what the object is and how to use it. For
* example in maintaining the golf course tree the user object is an
* <code>ICourseElement</code>.
* <p>
* <i>This is not a thread safe class.</i> If used from multiple threads it
* must be manually sychronized by your code.
*/
public class TreeNode
{
/**
* This node's parent node. If this is the root of the tree then
* the parent will be <code>null</code>.
*/
private TreeNode parent;
/**
* An array of all this node's child nodes. The array will always
* exist (i.e. never <code>null</code>) and be of length zero if this is
* a leaf node.
* <p>
* This is an array instead of a <code>Vector</code> to favor speed of
* accessing the children. The array takes longer on adds because
* of array copying and management. However to get the array it
* can just be returned instead of creating a new array from the
* <code>Vector</code> each time. The tree is used frequently enough for
* reading course elements that this difference makes a small impact
* on rendering.
*/
private TreeNode[] children = new TreeNode[0];
/**
* Constructs a tree node object. It can become the root of a tree.
* Or it can become a child of another node by calling the other node's
* <code>add</code> method.
* <p>
* There is no user object attached to the node. Call <code>setUserObject</code>
* to attach one.
*/
public TreeNode ()
{
// Nothing needed.
}
/**
* Constructs a tree node object. It can become the root of a tree.
* Or it can become a child of another node by calling the other node's
* <code>add</code> method.
*
* @param userObject is an object this node encapsulates. It is up to
* the developer to maintain its type. To get the object back out
* call <code>getUserObject</code>.
*/
public TreeNode (Object userObject)
{
m_userData = userObject;
}
/**
* Adds the <code>child</code> node to this container making this its parent.
*
* @param child is the node to add to the tree as a child of <code>this</code>
*
* @param index is the position within the children list to add the
* child. It must be between 0 (the first child) and the
* total number of current children (the last child). If it is
* negative the child will become the last child.
*/
public void add (TreeNode child, int index)
{
// Add the child to the list of children.
if ( index < 0 || index == children.length ) // then append
{
TreeNode[] newChildren = new TreeNode[ children.length + 1 ];
System.arraycopy( children, 0, newChildren, 0, children.length );
newChildren[children.length] = child;
children = newChildren;
}
else if ( index > children.length )
{
throw new IllegalArgumentException("Cannot add child to index " + index + ". There are only " + children.length + " children.");
}
else // insert
{
TreeNode[] newChildren = new TreeNode[ children.length + 1 ];
if ( index > 0 )
{
System.arraycopy( children, 0, newChildren, 0, index );
}
newChildren[index] = child;
System.arraycopy( children, index, newChildren, index + 1, children.length - index );
children = newChildren;
}
// Set the parent of the child.
child.parent = this;
}
/**
* Adds the <code>child</code> node to this container making this its parent.
* The child is appended to the list of children as the last child.
*/
public void add (TreeNode child)
{
add( child, -1 );
}
/**
* Removes the child at position <code>index</code> from the tree.
*
* @param index is the position of the child. It should be between
* 0 (the first child) and the total number of children minus 1
* (the last child).
* @return The removed child node. This will be <code>null</code> if
* no child exists at the specified <code>index</code>.
*/
public TreeNode remove (int index)
{
if ( index < 0 || index >= children.length ) throw new IllegalArgumentException("Cannot remove element with index " + index + " when there are " + children.length + " elements.");
// Get a handle to the node being removed.
TreeNode node = children[index];
node.parent = null;
// Remove the child from this node.
TreeNode[] newChildren = new TreeNode[ children.length - 1 ];
if ( index > 0 )
{
System.arraycopy( children, 0, newChildren, 0, index );
}
if ( index != children.length - 1 )
{
System.arraycopy( children, index + 1, newChildren, index, children.length - index - 1 );
}
children = newChildren;
return node;
}
/**
* Removes this node from its parent. This node becomes the root
* of a subtree where all of its children become first level
* nodes.
* <p>
* Calling this on the root node has no effect.
*/
public void removeFromParent ()
{
if ( parent != null )
{
int position = this.index();
parent.remove( position );
parent = null;
}
}
/**
* Gets the parent node of this one.
*
* @return The parent of this node. This will return <code>null</code>
* if this node is the root node in the tree.
*/
public TreeNode getParent ()
{
return parent;
}
/**
* Returns if this node is the root node in the tree or not.
*
* @return <code>true</code> if this node is the root of the tree;
* <code>false</code> if it has a parent.
*/
public boolean isRoot ()
{
if ( parent == null )
{
return true;
}
else
{
return false;
}
}
/**
* Gets a list of all the child nodes of this node.
*
* @return An array of all the child nodes. The array will
* be the size of the number of children. A leaf node
* will return an empty array, not <code>null</code>.
*/
public TreeNode[] children ()
{
return children;
}
/**
* Returns if this node has children or if it is a leaf
* node.
*
* @return <code>true</code> if this node has children; <code>false</code>
* if it does not have any children.
*/
public boolean hasChildren ()
{
if ( children.length == 0 )
{
return false;
}
else
{
return true;
}
}
/**
* Gets the position of this node in the list of siblings
* managed by the parent node. This node can be obtained
* by <code>this = parent.children[this.index()]</code>.
*
* @return The index of the child array of this node's
* parent. If this is the root node it will return -1.
*/
public int index ()
{
if ( parent != null )
{
for ( int i = 0; ; i++ )
{
Object node = parent.children[i];
if ( this == node )
{
return i;
}
}
}
// Only ever make it here if this is the root node.
return -1;
}
/**
* Gets this node's depth in the tree. The root node will
* have a depth of 0, first-level nodes will have a depth
* of 1, and so on.
*
* @return The depth of this node in the tree.
*/
public int depth ()
{
int depth = recurseDepth( parent, 0 );
return depth;
}
/**
* Recursive helper method to calculate the depth of a node.
* The caller should pass its parent and an initial depth of 0.
* <p>
* A recursive approach is used so that when a node that is
* part of a tree is removed from that tree, we do not need
* to recalculate the depth of every node in that subtree.
*
* @param node is the node to recursively check for its depth.
* This should be set to <code>parent</code> by the caller.
* @param depth is the depth of the current node (i.e. the
* child of <code>node</code>). This should be set to 0 by the
* caller.
*/
private int recurseDepth (TreeNode node, int depth)
{
if ( node == null ) // reached top of tree
{
return depth;
}
else
{
return recurseDepth( node.parent, depth + 1 );
}
}
/**
* A handle to the programmer assigned object encapsulated by this
* node. This will be <code>null</code> when the user has not assigned
* any data to this node.
*/
private Object m_userData;
/**
* Attaches a user defined object to this node. Only one
* object can be attached to a node.
*
* @param userObject is the programmer defined object to
* attach to this node in the tree. Set it to <code>null</code>
* to clear any objects.
*/
public void setUserObject (Object userObject)
{
m_userData = userObject;
}
/**
* Gets the user defined object attached to this node. It
* must be cast back to what it was inserted as. It is up
* to the developer to make this cast.
*
* @return The programmer defined object attached to this
* node in the tree. Returns <code>null</code> if no object is
* attached.
*/
public Object getUserObject ()
{
return m_userData;
}
}
--------
package org.j4me.collections;
import j2meunit.framework.*;
/**
* Tests the <code>TreeNode</code> object. It is a generic tree (integer.e. not a balanced tree
* or some other specialized tree).
*
* @see org.j4me.collections.TreeNode
*/
public class TreeNodeTest
extends TestCase
{
public TreeNodeTest ()
{
super();
}
public TreeNodeTest (String name, TestMethod method)
{
super( name, method );
}
public Test suite ()
{
TestSuite suite = new TestSuite();
suite.addTest(new TreeNodeTest("testIllegalOperations", new TestMethod()
{ public void run(TestCase tc) {((TreeNodeTest) tc).testIllegalOperations(); } }));
suite.addTest(new TreeNodeTest("testUserObjects", new TestMethod()
{ public void run(TestCase tc) {((TreeNodeTest) tc).testUserObjects(); } }));
suite.addTest(new TreeNodeTest("testRoot", new TestMethod()
{ public void run(TestCase tc) {((TreeNodeTest) tc).testRoot(); } }));
suite.addTest(new TreeNodeTest("testOneChild", new TestMethod()
{ public void run(TestCase tc) {((TreeNodeTest) tc).testOneChild(); } }));
suite.addTest(new TreeNodeTest("testMultipleChildren", new TestMethod()
{ public void run(TestCase tc) {((TreeNodeTest) tc).testMultipleChildren(); } }));
suite.addTest(new TreeNodeTest("testMultipleLevels", new TestMethod()
{ public void run(TestCase tc) {((TreeNodeTest) tc).testMultipleLevels(); } }));
suite.addTest(new TreeNodeTest("testBigTree", new TestMethod()
{ public void run(TestCase tc) {((TreeNodeTest) tc).testBigTree(); } }));
return suite;
}
/**
* Tests the tree nodes defend themselves again invalid parameters that would
* be the result of programming errors.
*/
public void testIllegalOperations ()
{
// Test cannot add a child node to position greater than available number of children.
boolean caughtException = false;
try
{
TreeNode root = new TreeNode();
root.add( new TreeNode(), 1 );
}
catch (IllegalArgumentException e)
{
caughtException = true;
}
catch (Throwable t)
{
String actualExceptionName = t.getClass().getName();
fail( "Expected exception 'IllegalArgumentException' and got '" + actualExceptionName + "'." );
}
if ( caughtException == false )
{
fail( "Expected exception 'IllegalArgumentException' but no exceptions caught." );
}
// Test remove a child node from position greater than available number of children.
caughtException = false;
try
{
TreeNode root = new TreeNode();
root.remove( 1 );
}
catch (IllegalArgumentException e)
{
caughtException = true;
}
catch (Throwable t)
{
String actualExceptionName = t.getClass().getName();
fail( "Expected exception 'IllegalArgumentException' and got '" + actualExceptionName + "'." );
}
if ( caughtException == false )
{
fail( "Expected exception 'IllegalArgumentException' but no exceptions caught." );
}
}
/**
* Tests that user objects can be attached and extracted from
* a tree node.
*/
public void testUserObjects ()
{
String user = "This is a test string.\n It should go in and come out the same.";
Integer user2 = new Integer(13);
// Create a node with the user defined object.
TreeNode node = new TreeNode( user );
// Get the object back out.
Object obj = node.getUserObject();
String result = (String)obj;
assertEquals("The attached string should be the same one as put in.", user, result);
// Try erasing the string.
node.setUserObject( null );
obj = node.getUserObject();
assertNull("No user object should be attached to the node.", obj);
// Put a different object back in and pull it out.
node.setUserObject( user2 );
obj = node.getUserObject();
Integer intResult = (Integer)obj;
assertEquals("The attached Integer should be the same one as put in.", user2, intResult);
}
/**
* Tests assertions about a root node. This is a very simple test
* and should be right before working with children.
*/
public void testRoot ()
{
TreeNode root = new TreeNode();
// Verify properties of the root node.
boolean isRoot = root.isRoot();
assertTrue("The node should be the root node.", isRoot);
int index = root.index();
assertEquals("The root node should have an index of -1 since it has no parent.", -1, index);
int depth = root.depth();
assertEquals("The root node should have depth of 0 since it has no parent.", 0, depth);
TreeNode parent = root.getParent();
assertNull("The root node should not have a parent node.", parent);
boolean hasChildren = root.hasChildren();
assertTrue("The root node should not have any children because none have been added.", hasChildren == false);
TreeNode[] children = root.children();
int childLength = children.length;
assertEquals("The root node should not have any children because none have been added.", 0, childLength);
// Verify the following method doesn't throw an exception.
root.removeFromParent();
}
/**
* Test a tree that has a root and just one child. This is a simple
* test to verify the child has properties appropriately set before
* testing more complex trees.
*/
public void testOneChild ()
{
// Create the tree.
TreeNode root = new TreeNode();
TreeNode child = new TreeNode();
root.add( child );
// Verify properties of the child node.
boolean isRoot = child.isRoot();
assertTrue("The node should not be the root node.", isRoot == false);
int index = child.index();
assertEquals("The child node should have an index of 0 since it is the only child.", 0, index);
int depth = child.depth();
assertEquals("The child node should have depth of 1 since it is a first level node.", 1, depth);
TreeNode parent = child.getParent();
assertEquals("The child's parent should be the root node.", root, parent);
boolean hasChildren = child.hasChildren();
assertTrue("The child node should not have any children because none have been added.", hasChildren == false);
hasChildren = root.hasChildren();
assertTrue("The root node should now have children.", hasChildren == true);
TreeNode[] children = child.children();
int childLength = children.length;
assertEquals("The child node should not have any children because none have been added.", 0, childLength);
children = root.children();
childLength = children.length;
assertEquals("The root node should have 1 child.", 1, childLength);
TreeNode theChild = children[0];
assertEquals("The root's child should be child.", child, theChild);
// Now remove the child from the root.
child.removeFromParent();
isRoot = child.isRoot();
assertTrue("The child node should now be the root of its own subtree.", isRoot == true);
depth = child.depth();
assertEquals("The child node should have depth of 0 since it is now the root.", 0, depth);
parent = child.getParent();
assertEquals("The child should not have a parent since it is now the root.", null, parent);
hasChildren = root.hasChildren();
assertTrue("The root node should no longer have any children.", hasChildren == false);
}
/**
* This tests a tree only 1 level deep, but there are several first
* level children. This is useful to test that siblings are kept
* correctly before testing multiple level trees.
*/
public void testMultipleChildren ()
{
TreeNode root = new TreeNode();
TreeNode child1 = new TreeNode();
TreeNode child2 = new TreeNode();
TreeNode child3 = new TreeNode();
// Add the children.
root.add( child1, 0 );
root.add( child3, 1 ); // Add with index, but really appending child
root.add( child2, 1 ); // Add out of order to test insertion in the middle of the children
TreeNode[] children = root.children();
assertEquals("child1 should be the first child.", child1, children[0]);
assertEquals("child2 should be the second child.", child2, children[1]);
assertEquals("child3 should be the third child.", child3, children[2]);
// Verify the properties of the children.
for ( int i = 0; i < children.length; i++ )
{
TreeNode child = children[i];
int index = child.index();
assertEquals("child" + (i+1) + " should have an index of " + i, i, index);
boolean isRoot = child.isRoot();
assertTrue("child" + (i+1) + " should not be the root node.", isRoot == false);
int depth = child.depth();
assertEquals("child" + (i+1) + " should have depth of 1 since it is a first level node.", 1, depth);
TreeNode parent = child.getParent();
assertEquals("child" + (i+1) + "'s parent should be the root node.", root, parent);
boolean hasChildren = child.hasChildren();
assertTrue("child" + (i+1) + " should not have any children because none have been added.", hasChildren == false);
}
// Remove the middle child.
TreeNode removed = root.remove( 1 );
assertEquals("The removed node should be child2.", child2, removed);
assertEquals("child2 should now have a depth of 0.", 0, removed.depth());
children = root.children();
assertEquals("The root should now have 2 children.", 2, children.length);
assertEquals("child3 should be the second child.", child3, children[1]);
// Add the middle child back in.
root.add( removed, 1 );
children = root.children();
TreeNode node = children[1];
assertEquals("The second node should be child2 again.", child2, node);
assertEquals("child2's parent should be the root again.", root, child2.getParent());
assertEquals("child2's depth should be 1 again.", 1, child2.depth());
// Remove all the children.
root.remove( 1 );
root.remove( 1 );
child1.removeFromParent();
assertTrue("The root should not have any children now.", root.hasChildren() == false);
}
/**
* This tests that multiple levels of the tree work correctly. Each
* level has only 1 child. This is a simple test to verify depth
* works before moving onto more complex trees.
*/
public void testMultipleLevels ()
{
TreeNode root = new TreeNode();
TreeNode depth1 = new TreeNode();
TreeNode depth2 = new TreeNode();
TreeNode depth3 = new TreeNode();
// Add the children.
root.add( depth1 );
depth2.add( depth3 );
depth1.add( depth2 );
// Verify the properties of the nodes.
assertTrue("The root should have 1 child.", root.hasChildren() == true);
assertEquals("The root should have a depth of 0.", 0, root.depth());
assertEquals("The root should not have a parent.", null, root.getParent());
assertTrue("depth1 should have 1 child.", depth1.hasChildren() == true);
assertEquals("depth1 should have a depth of 1.", 1, depth1.depth());
assertEquals("depth1 should have root as its parent.", root, depth1.getParent());
assertTrue("depth2 should have 1 child.", depth2.hasChildren() == true);
assertEquals("depth2 should have a depth of 2.", 2, depth2.depth());
assertEquals("depth2 should have depth1 as its parent.", depth1, depth2.getParent());
assertTrue("depth3 should have not have any children.", depth3.hasChildren() == false);
assertEquals("depth3 should have a depth of 3.", 3, depth3.depth());
assertEquals("depth3 should have depth2 as its parent.", depth2, depth3.getParent());
// Cut the tree in 1/2.
depth2.removeFromParent();
assertTrue("depth2 should now be a root.", depth2.isRoot() == true);
assertEquals("depth2 should now have a depth of 0.", 0, depth2.depth());
assertEquals("depth3 should now have a depth of 1.", 1, depth3.depth());
assertTrue("depth1 should not have any children now.", depth1.hasChildren() == false);
}
/**
* This tests a tree with multiple varying depths and multiple
* varying amounts of children at each depth.
*/
public void testBigTree ()
{
String testData = "";
TreeNode root = new TreeNode();
TreeNode d1c0 = new TreeNode( testData );
TreeNode d1c1 = new TreeNode( testData );
TreeNode d1c2 = new TreeNode( testData );
TreeNode d2c1c0 = new TreeNode( testData );
TreeNode d2c1c1 = new TreeNode( testData );
TreeNode d2c1c2 = new TreeNode( testData );
TreeNode d2c2c0 = new TreeNode( testData );
TreeNode d2c2c1 = new TreeNode( testData );
TreeNode d3c2c0c0 = new TreeNode( testData );
TreeNode d3c2c0c1 = new TreeNode( testData );
root.add( d1c0 );
root.add( d1c1 );
root.add( d1c2 );
d1c1.add( d2c1c1 ); // Second child
d1c1.add( d2c1c0, 0 ); // First child
d1c1.add( d2c1c2 ); // Third child
d1c2.add( d2c2c0 );
d2c2c0.add( d3c2c0c0 );
d2c2c0.add( d3c2c0c1 );
d1c2.add( d2c2c1 );
// Verify the tree structure.
assertEquals("root should be the parent of d1c0", root, d1c0.getParent());
assertEquals("root should be the parent of d1c1", root, d1c1.getParent());
assertEquals("root should be the parent of d1c2", root, d1c2.getParent());
assertEquals("d1c1 should be the parent of d2c1c0", d1c1, d2c1c0.getParent());
assertEquals("d1c1 should be the parent of d2c1c1", d1c1, d2c1c1.getParent());
assertEquals("d1c1 should be the parent of d2c1c2", d1c1, d2c1c2.getParent());
assertEquals("d1c2 should be the parent of d2c2c0", d1c2, d2c2c0.getParent());
assertEquals("d1c2 should be the parent of d2c2c1", d1c2, d2c2c1.getParent());
assertEquals("d2c2c0 should be the parent of d3c2c0c0", d2c2c0, d3c2c0c0.getParent());
assertEquals("d2c2c0 should be the parent of d3c2c0c1", d2c2c0, d3c2c0c1.getParent());
// Verify the depths of some of the nodes.
assertEquals("root should have a depth of 0", 0, root.depth());
assertEquals("d1c1 should have a depth of 1", 1, d1c1.depth());
assertEquals("d2c2c0 should have a depth of 2", 2, d2c2c0.depth());
assertEquals("d3c2c0c1 should have a depth of 3", 3, d3c2c0c1.depth());
// Verify we can traverse the tree from root to d3c2c0c0.
TreeNode node = root.children()[2]; // d1c2
node = node.children()[0]; // d2c2c0
node = node.children()[0]; // d3c2c0c0
assertEquals("We should have tranversed the tree to d3c2c0c0.", d3c2c0c0, node);
assertEquals("Should have test data as user object from node d3c2c0c0.", testData, node.getUserObject());
}
}
]]>