package net.imglib2.algorithms.opt.astar;

import java.io.Serializable;
import java.util.*;


public class SortedTreeNode<T extends Comparable<T>> implements Comparable<SortedTreeNode<T>>,  Serializable{
	/**
	 * 
	 */
	private static final long serialVersionUID = -6683027733135726639L;
	private T							data;
	private SortedTreeNode<T> 			parent;
	private SortedSet<SortedTreeNode<T>> children;
	
	private int depth; // the depth this node in the tree
					   // root has depth 0 
	
	/**
	 * Constructor
	 * @param data
	 * @param parent
	 */
	public SortedTreeNode(T data, SortedTreeNode<T> parent ){
		this.data = data;
		this.parent = parent;
		
		children = new TreeSet<SortedTreeNode<T>>();
		
		if( parent != null )
			parent.addChild( this );
		
		if( isRoot() )
			depth = 0;
		else
			depth = parent.depth + 1;
	}
	
	/**
	 * Constructor for the root.
	 * @param data
	 */
	public SortedTreeNode( T data ){
		this( data, null );
	}
	
	public void addChild( SortedTreeNode<T> child ){
		child.setParent( this );
		children.add( child );
	}
	
	public void addChildren( Collection<SortedTreeNode<T>> children ){
		Iterator<SortedTreeNode<T>> it = children.iterator();
		while (it.hasNext()){
			addChild( it.next() );
		}
	}
	
	public boolean removeChild( SortedTreeNode<T> child ){
		return children.remove( child );
	}
	
	public boolean removeChildren( Collection<SortedTreeNode<T>> children ){
		return children.removeAll( children );
	}
	
	public T getData(){
		return data;
	}
	public int getDepth(){
		return depth;
	}
	
	public void setData( T data){
		this.data = data;
	}
	
	protected void setParent( SortedTreeNode<T> parent ){
		this.parent = parent;
	}
	
	public SortedTreeNode<T> getParent(){
		return parent;
	}
	
	public Set<SortedTreeNode<T>> getChildren(){
		return Collections.unmodifiableSet( children );
	}
	
	@Override
	public int compareTo(SortedTreeNode<T> arg) {
		return data.compareTo(arg.getData());
	}
	
	/*
	 * Returns true if this node is the tree's root
	 */
	public boolean isRoot(){
		return (parent == null);
	}
	
	/*
	 * Returns true if this node is a leaf
	 */
	public boolean isLeaf(){
		return children.isEmpty();
	}
	
	public void printAsTree( ){
		String pad = "";
		printAsTree( pad );
	}
	
	public void printAsTree( String pad ){
		
		System.out.println( pad + this );
		
		if( !isLeaf()){
			String nextPad = pad+"\t";
			Iterator<SortedTreeNode<T>> it = getChildren().iterator();
			while( it.hasNext() ){
				it.next().printAsTree(nextPad);
			}
		}
		
	}
	
	public LinkedList<SortedTreeNode<T>> pathToRoot(){
		LinkedList<SortedTreeNode<T>> path = new LinkedList<SortedTreeNode<T>>( );
		
		SortedTreeNode<T> obj = this;
		path.addFirst( obj );
		
		while( !obj.isRoot() ){
			obj = obj.getParent();
			path.addFirst( obj );
		}
		
		return path;
	}
	

	
	public String toString(){
		String out = "STN (" + data + ") " ;
		
		if( isRoot() ){
			out += "ROOT "; 
		}
		
		// it's possible to be a both a root and a leaf
		// in the case of a tree with a single node
		if( isLeaf() ){
			out += "LEAF ";
		}else{
			out += "[" + children.size() + " children]";
		}
		
		return out;
	}
	
	public static <T extends Comparable<T>> String pathToString( Collection<SortedTreeNode<T>> path, String pad ){
		String out = "";
		Iterator<SortedTreeNode<T>> it = path.iterator();

		String prefix = "";
		while( it.hasNext() ){
			out = out + prefix + it.next() + "\n";
			prefix = prefix + pad;
		}
		
		return out;
	}
}
@@ -1435,32 +1435,270 @@
 hildren );%0A%09%7D%0A%09%0A
+%09public int numDescendants()%7B%0A%09%09if( isLeaf() )%7B%0A%09%09%09return 0;%0A%09%09%7Delse%7B%0A%09%09%09int N = 0;%0A%09%09%09Iterator%3CSortedTreeNode%3CT%3E%3E it = getChildren().iterator();%0A%09%09%09while( it.hasNext() )%7B%0A%09%09%09%09N += it.next().numDescendants();%0A%09%09%09%7D%0A%09%09%09return N;%0A%09%09%7D%0A%09%7D%0A%09%0A%09%0A
 %09public T getDat

add numDescendants method to SortedTreeNode