/*
*
* Copyright (c) 2007
* Adrian Michel
* http://www.tradery.com
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation. Adrian Michel makes no
* representations about the suitability of this software for any
* purpose. It is provided "as is" without express or implied warranty.
*/
package com.tradery.collections;
import java.util.*;
import java.io.OutputStream;
import java.io.IOException;
import com.tradery.contract.Contract;
/**
* Implements a n-ary tree, i.e. a tree whose nodes can have any number of children.
* Not thread safe
*/
public class NaryTree
{
/***************************************************
* private data
**************************************************/
// the tree has a root
private Node root = null;
/**
* Node - a node in the tree
* A node has a name, which does not have any special meaning -
* it can be used for debugging or other purposes
*
* The traversal of a level in the tree can only be done
* sequentially - random access in the to the nodes is not possible.
* Each node has links to all the sorrounding nodes: parent, left, right, first child, last child
*/
public static class Node
{
// a node has a name and...
private String name = null;
// a parent and ...
private Node parent = null;
// a left sibling and ...
private Node prev = null;
// a right sibling and ...
private Node next = null;
// children
private Node firstChild = null;
private Node lastChild = null;
/**
* This is to be used in case where a class that is also a node cannot actually be implemented
* as extending Node because Java doesn't allow multiple inheritance, and instead contains
* a node as a way of being still a node in a tree. Then, the nodeObject is used to keep a link
* between the "abstract" node and the actual object that is supposed to be the concrete node
* In order to still have strong typing, a class extending Node can be defined to do the
* appropriate casts
*/
private Object _nodeObject = null;
// the number of children a node has
private int childrenCount = 0;
/**
* Constructs a node with a name
*
* @param _name The name of the node
*/
public Node( String _name )
{
name = _name;
}
/**
* Default constructor - constructs a node with an empty name.
*/
public Node()
{
name = null;
}
/**
* copy constructor - only copies the name of another node.
*
* Note: to see what the sense of this is. It may not be used at all.
*
* @param node The node to be copied
*/
public Node( Node node )
{
name = node.getName();
}
/**
* Constructs a node with a name and a node object
*
* @param _name The name of the node
* @param nodeObject The node object associated with the node
*/
public Node( String _name, Object nodeObject )
{
_nodeObject = nodeObject;
name = _name;
}
/**
* Constructs a node from a node object
*
* @param nodeObject The node object to be associated with this node
*/
public Node( Object nodeObject )
{
_nodeObject = nodeObject;
}
/**
* Gets the parent node of the current node
*
* @return The parent node or null if this is the root node
*/
public final Node getParent()
{
return parent;
}
/**
* Sets the parent of the current node
*
* @param _parent The new parent node
*/
final void setParent( Node _parent )
{
parent = _parent;
}
/**
* Sets the node next to the current node
*
* @param node The node to become the next node
*/
final void setNext( Node node )
{
next = node;
}
/**
* Sets the node to be the new previous node to the current node
*
* @param node The node to become the previous node
*/
final void setPrev( Node node )
{
prev = node;
}
/**
* Sets the last child of the current node
*
* @param node The node to become the last child of the current node
*/
final void setLastChild( Node node )
{
lastChild = node;
}
/**
* Sets the node to become the first child to the current node
*
* @param node The node to become the first child
*/
final void setFirstChild( Node node )
{
firstChild = node;
}
/**
* Retrievs the first child of the current node
*
* @return The first child
*/
public final Node getFirstChild()
{
return firstChild;
}
/**
* Retrievs the last child of the current node
*
* @return The last child
*/
public final Node getLastChild()
{
return lastChild;
}
/**
* The name of the current node
*
* @return The name
*/
final protected String getName()
{
return name;
}
/**
* Indicates if the current node is root (it does not have any parent)
*
* @return true if the node is root, false otherwise
*/
public final boolean isRoot()
{
return parent == null;
}
/**
* Retrievs the node object associated with the current node
*
* @return The node object
*/
final Object getNodeObject()
{
return _nodeObject;
}
/**
* Adds a child node to the end of the children list
*
* @param node The node to be added
* @return The node added to the back
*/
public final Node addChildToBack( Node node )
{
if( Contract.REQUIRE )
Contract.require( node != null );
// set the new child parent link
node.setParent( this );
// adding the child to the end of the list
if( firstChild == null )
firstChild = lastChild = node;
else
{
lastChild.setNext( node );
node.setPrev( lastChild );
}
lastChild = node;
childrenCount++;
return node;
}
/**
* Adds a child node to the front of the children list
*
* @param node The node to be added to the front
* @return The node added to the front
*/
final Node addChildToFront( Node node )
{
if( Contract.REQUIRE )
Contract.require( node != null );
// set the new child parent link
node.setParent( this );
// adding the child to the front of the list
if( firstChild == null )
firstChild = lastChild = node;
else
{
firstChild.setPrev( node );
node.setNext( firstChild );
}
firstChild = node;
childrenCount++;
return node;
}
/**
* Adds a node to the front of the siblings list on the same level as the current node.
*
* @param sibling The new sibling to be added
* @return The new sibling added
*/
final Node addSiblingToFront( Node sibling )
{
if( Contract.REQUIRE )
{
Contract.require( parent != null );
Contract.require( sibling != null );
}
return parent.addChildToFront( sibling );
}
/**
* Adds a node to the back of the siblings list on the same level as the current node.
*
* @param sibling The new sibling to be added
* @return The new sibling added
*/
public final Node addSiblingToBack( Node sibling )
{
if( Contract.REQUIRE )
{
Contract.require( parent != null, "com.tradery.util.NaryTree.Node.addSiblingToBack - parent of current node is null, so cannot add sibling" );
Contract.require( sibling != null, "com.tradery.util.NaryTree.Node.addSiblingToBack - the sibling to be added is null, cannot add a null sibling" );
}
return parent.addChildToBack( sibling );
}
/**
* Inserts a parent in the children list between the current node and
* its old parent. The current node is added to the end of the list
* of children nodes of the new parent (in case the new parent already has
* children)
*
* The current node becomes child of the new parent and the new parent becomes
* child of the old parent of the current node
*
* @param newParent The new parent to be inserted
* @return The node inserted as parent
*/
public final Node insertParent( Node newParent )
{
if( Contract.REQUIRE )
Contract.require( newParent != null );
// this is root in the tree
Node oldParent = parent;
// set the new parent for the current node
parent = newParent;
// position the new parent in the list of siblings
newParent.setPrev( prev );
newParent.setNext( next );
if( prev != null )
prev.setNext( newParent );
else if( oldParent != null )
oldParent.setFirstChild( newParent );
if( next != null )
next.setPrev( newParent );
else if( oldParent != null )
oldParent.setLastChild( newParent );
// set the parent of the newParent to oldParent
newParent.setParent( oldParent );
// add the current node as a child of the new parent
newParent.addChildToBack( this );
// set lastchild/firstchild of the old parent, in case
// the new parent is either of them
return newParent;
}
/**
* Inserts a parent in the children list between the current node and
* its old parent. The current node is added to the front of the list
* of children nodes of the new parent (in case the new parent already has
* children)
*
* The current node becomes child of the new parent and the new parent becomes
* child of the old parent of the current node
*
* @param newParent The new parent to be inserted
* @return The node inserted as parent
*/
final Node insertParentToFront( Node newParent )
{
if( Contract.REQUIRE )
Contract.require( newParent != null );
// this is root in the tree
Node oldParent = parent;
// set the new parent for the current node
parent = newParent;
// position the new parent in the list of siblings
newParent.setPrev( prev );
newParent.setNext( next );
if( prev != null )
prev.setNext( newParent );
else if( oldParent != null )
oldParent.setFirstChild( newParent );
if( next != null )
next.setPrev( newParent );
else if( oldParent != null )
oldParent.setLastChild( newParent );
// set the parent of the newParent to oldParent
newParent.setParent( oldParent );
// add the current node as a child of the new parent
newParent.addChildToFront( this );
// set lastchild/firstchild of the old parent, in case
// the new parent is either of them
return newParent;
}
/**
* Generate a string with as many spaces as the indentation level and writes
* it to the output stream.
*
* Used when dumping the tree, in order to show the indentation of
* different levels.
*
* @param os The output stream
* @param n The indentation level
* @exception IOException
*/
protected void Indent( OutputStream os, int n )
throws IOException
{
String str = new String();
while( n-- > 0 )
str += " ";
os.write( str.getBytes() );
}
/**
* Indicates if the current node is a leaf in the tree i.e. it does not
* have any children
*
* @return true if the current node is a leaf, false otherwise
*/
boolean isLeaf()
{
return childrenCount == 0;
}
/**
* Retrievs the next sibling node of the current node
*
* @return The next sibling or null if there is none
*/
public final Node getNextSibling()
{
return next;
}
/**
* Get the previous sibling node of the current node
*
* @return The previous sibling node or null if there is none
*/
public final Node getPrevSibling()
{
return prev;
}
/**
* Retrievs the number of children nodes of the current node
*
* @return The number of children
*/
public final int getChildrenCount()
{
return childrenCount;
}
/**
* returns the number of siblings on the level of the current node,
* including itself.
*
* @return The number of siblings
*/
final int getSiblingsCount()
{
if( parent != null )
return parent.getChildrenCount();
else
// there is only one root
return 1;
}
/**
* Dumps the contents of the node to the output stream as a string,
* considering the indent level
*
* @param os The output stream
* @param n The indentation level.
* @exception IOException
*/
public void dump( OutputStream os, int n )
throws IOException
{ Indent( os, n ); dump( os ); os.write( ("\n").getBytes() );}
/**
* Sends the name of the current node to the output stream
*
* @param os The output stream
* @exception IOException
*/
public void dump( OutputStream os )
throws IOException
{ os.write( name.getBytes() );}
/**
* Clones the current node.
*
* Note: the copy constructor does not seem to be doing anyhing. Check
*
* @return A clone of the current node
*/
public Object clone()
{
return new Node( this );
}
}
/**
* enumerator for post order traversal of the tree
* More efficient that recursive traversal
*
* Note: if the tree is changed while traversing it,
* objects of this class become invalid
* TODO: should I enforce this, or should I assume that the programmer follows this rule?
*/
private class PostOrderEnumerator implements Enumeration
{
/**
* The current node
*/
private Node crtNode;
/**
* Indicates if the subtree starting at crtNode was traversed or not
*/
private boolean traversed;
/**
* Constructs a PostOrderEnumerator for a tree initialized to the root of the tree
*
* @param _tree The tree whose enumerator we need
*/
PostOrderEnumerator( NaryTree _tree )
{
crtNode = _tree.getRoot(); traversed = false;
}
/**
* Indicates if there are more nodes or not in the enumeration
*
* @return true if there are more nodes in the enumeration, false if there are no more nodes
*/
public boolean hasMoreElements()
{
return crtNode != null;
}
/**
* Retrievs the next element in the enumeration
*
* @return The next node in the enumeration or null if there are no more nodes or if the tree is empty
*/
public Object nextElement()
{
Node retNode;
Node node;
// if the crtNode == null, no more elements
if( crtNode == null )
return null;
if( traversed )
{
// if we traversed the subtree starting at the current node
// next element is the current node
retNode = crtNode;
// calculate the next current node
crtNode = nextCrtNode( crtNode );
}
else
{
// if the subtree hasn't been traversed, find the first leaf
node = findFirstLeaf( crtNode );
if( node != null )
{
// next node is this first leaf
retNode = node;
// calculate the next current node
crtNode = nextCrtNode( node );
}
else
{
// if no leaf, next node is current node
retNode = crtNode;
// calculate the next current node
crtNode = nextCrtNode( node );
}
}
return retNode;
}
/**
* calculate the next current node
*
* @param node The present current node
* @return The newly calculated current node, or null if there are no more nodes or if the tree is empty
*/
private Node nextCrtNode( Node node )
{
Node node1 = node.getNextSibling();
if( node1 == null )
{
// if node doesn't have any siblings
// the current node is its parent,
// also set the parent as traversed,
// since we are coming from the child
traversed = true;
return node.getParent();
}
else
{
// if it has sibling, set the current node to it
// also, since it is a new node, st traversed to false
traversed = false;
return node1;
}
}
/**
* Finds the first leaf for the subtree starting at node
*
* @param node The root of the subnode
* @return The first leaf or null if there are no more
*/
private Node findFirstLeaf( Node node )
{
if( node != null )
while( !node.isLeaf() ) node = node.getFirstChild();
return node;
}
}
/**
* "Copy" constructor. Creates a tree whose nodes and structure is a copy of
* another tree
*
* @param tree The source tree to be cloned
*/
public NaryTree( NaryTree tree )
{
if( Contract.REQUIRE )
Contract.require( tree != null );
Node root = tree.getRoot();
root = (Node)root.clone();
setRoot( root );
cloneChildren( getRoot(), tree.getRoot() );
}
/**
* Default constructor. Constructs an empty tree
*/
public NaryTree()
{
}
/**
* Adds a child to the back of the list of nodes of the parent
*
* @param parent The parent node
* @param child The new child to be added
* @return The new child
*/
final public Node addChildToBack( Node parent, Node child )
{
if( Contract.REQUIRE )
{
Contract.require( parent != null );
Contract.require( child != null );
}
return parent.addChildToBack( child );
}
/**
* Adds a sibling to the back of the list of siblings of the node
*
* @param node The node on whose list of siblings the new sibling will be added
* @param sibling
* @return The new sibling node
*/
final public Node addSiblingToBack( Node node, Node sibling )
{
if( Contract.REQUIRE )
{
Contract.require( node != null );
Contract.require( sibling != null );
}
return node.addSiblingToBack( sibling );
}
/**
* Adds a child to the front of the list of children of the node
*
* @param parent The parent node
* @param child The new child node
* @return The new child node
*/
final public Node addChildToFront( Node parent, Node child )
{
if( Contract.REQUIRE )
{
Contract.require( parent != null );
Contract.require( child != null );
}
return parent.addChildToFront( child );
}
/**
* Adds a sibling to the back of the list of siblings of the node
*
* @param node The node on whose list of siblings the new sibling will be added
* @param sibling The new sibling
* @return The new sibling
*/
final public Node addSiblingToFront( Node node, Node sibling )
{
if( Contract.REQUIRE )
{
Contract.require( node != null );
Contract.require( sibling != null );
}
return node.addSiblingToFront( sibling );
}
final public boolean isRoot( Node node )
{
return node == root;
}
/**
* Adds a subtree to the current tree by making the root of the subtree
* a child of the parent node. The subtree is added at the end of the list
* of children
*
* @param parent The parent of the new subtree
* @param child The tree to be added as a subtree to the current tree
* @return The current tree
*/
public NaryTree addChildTreeToBack( Node parent, NaryTree child )
{
if( Contract.REQUIRE )
{
if( parent == null )
Contract.require( root == null );
else
Contract.require( parent != null );
Contract.require( child != null );
}
if( parent == null )
root = child.getRoot();
else
parent.addChildToBack( child.getRoot() );
return this;
}
/**
* Adds a subtree to the current tree by making the root of the subtree
* a sibling of the node. The subtree is added at the end of the list
* of siblings of the node.
*
* @param node The node whose sibling the new tree will become
* @param sibling The tree to become a subtree
* @return The current tree
*/
public NaryTree addSiblingTreeToBack( Node node, NaryTree sibling )
{
if( Contract.REQUIRE )
{
Contract.require( node != null );
Contract.require( sibling != null );
}
node.addSiblingToBack( sibling.getRoot() );
return this;
}
/**
* Inserts a new parent between the node and its current parent.
*
* @param node The node whose parent is to be changed
* @param parent The new parent node
* @return The node whose parent was changed
* @see Node.insertParentToFront
*/
final public Node insertParentToFront( Node node, Node parent )
{
// if we are inserting at root, newParent becomes root
if( isRoot( node ) )
{
setRoot( parent );
if( parent != null )
parent.addChildToFront( node );
}
else
node.insertParentToFront( parent );
return node;
}
/**
* Inserts a new parent between the node and its current parent.
*
* @param node The node whose parent is to be changed
* @param parent The new parent node
* @return The node whose parent was changed
* @see Node.insertParentToBack
*/
final public Node insertParentToBack( Node node, Node parent )
{
// if we are inserting at root, newParent becomes root
if( isRoot( node ) )
{
setRoot( parent );
if( node != null )
parent.addChildToBack( node );
}
else
node.insertParent( parent );
return node;
}
/**
* Retrievs the parent of a node
*
* @param node The node whose parent is to retrieved
* @return The parent node or null if node is the root
*/
final public Node getParent( Node node )
{
return node.getParent();
}
/**
* Retrievs the root node of the current tree
*
* @return The root node or null if the tree is empty
*/
final public Node getRoot()
{
return root;
}
/**
* Sets the root node of the current tree
*
* @param _root The new root.
*
* Note: the new root cannot be null
* @todo throw exception in non debug mode if the node is null
* @return The new root node
*/
final public Node setRoot( Node _root )
{
if( Contract.REQUIRE )
Contract.require( _root != null );
return root = _root;
}
/**
* Retrievs the next sibling of a node
*
* @param node The node whose sibling is to be retrieved
* @return The next sibling or null if there is no next sibling
*/
final public Node getNextSibling( Node node )
{
if( Contract.REQUIRE )
Contract.require( node != null );
return node.getNextSibling();
}
/**
* Retrievs the previous sibling of a node
*
* @param node The node whose sibling is to be retrieved
* @return The previous sibling or null if there is no previous sibling
*/
final public Node getPrevSibling( Node node )
{
if( Contract.REQUIRE )
Contract.require( node != null );
return node.getPrevSibling();
}
/**
* Clones a subtree starting at nodeFrom and attaches it as a subtree of
* nodeTo
*
* @param nodeTo The destination node
* @param nodeFrom The root of the source subtree
*/
private void cloneChildren( Node nodeTo, Node nodeFrom )
{
if( Contract.REQUIRE )
{
Contract.require( nodeTo != null );
Contract.require( nodeFrom != null );
}
for( Node node = nodeFrom.getFirstChild(); node != null; node = node.getNextSibling() )
{
Node newNode = (Node)node.clone();
nodeTo.addChildToBack( newNode );
cloneChildren( newNode, node );
}
}
/**
* Retrievs an Enumeration object, whose implementation is a PostOrderEnumerator
*
* @return The Enumeration object
*/
public Enumeration getPostOrderEnumerator()
{
return new PostOrderEnumerator( this );
}
/**
* Dumps the content of the tree to the output stream
*
* @param os Output stream
* @exception IOException
*/
public void dump( OutputStream os ) throws IOException { if( root != null ) dump( os, root, 0 ); /* else tree empty*/}
/**
* Dumps a subtree of the current tree whose root is node, to the output stream
*
* @param os Output stream
* @param node The root of the subtree to be dumped
* @param n The indentation level, based on the level in the tree
* @exception IOException
*/
private void dump( OutputStream os, Node node, int n )
throws IOException
{
node.dump( os, n );
for( Node child = node.getFirstChild(); child != null; child = child.getNextSibling() )
dump( os, child, n + 1 );
}
}