package com.seanhandley.projects.BinaryTree;

/**
 * A generic binary tree data structure.
 * 
 * @author Sean Handley, 320097@swan.ac.uk
 * @version May 2007
 */
public class BinaryTree<T extends Comparable<T>>
{
    private Node<T> root;
    private IStrategy<T> strategy;
    /**
     * Constructor for the generic binary tree.
     * 
     * @param strategy Strategy object for the tree.
     */
    public BinaryTree(IStrategy<T> strategy)
    {
        root = null;
        this.strategy = strategy;
    }
    /**
     * Add a new item to the tree.
     * 
     * @param t New item to be added.
     */
    public void add(T t)
    {
        root = add(root,t);
    }
    /*
     * Recursive helper for adding nodes.
     */
    private Node<T> add(Node<T> n, T t)
    {
        strategy.compute(t);
        if (n == null)
        {
            n = new Node<T>(t,null,null);
        }
        else
        {
            if (n.element.compareTo(t) >= 0)
            {
                n.left = add(n.left, t);
            }
            else
            {
                n.right = add(n.right, t);
            }
        }
        return(n);
    }
    /**
     * Test whether the tree is empty.
     * 
     * @return true if tree is empty, false if otherwise.
     */
    public boolean empty()
    {
        if(root == null)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    /**
     * Determine number of elements in the tree.
     * 
     * @return Number of elements in the tree.
     */
    public int size()
    {
        return count(root);
    }
    /*
     * Recursive helper for size()
     */
    private int count(Node<T> n)
    {
        int nodes = 0;
        if(n != null)
        {
            nodes += count(n.left);
            nodes++;
            nodes += count(n.right);
        }
        return nodes;
    }
    /**
     * Print out tree contents in order.
     * 
     * Overrides the toString method of Object.
     * 
     * @return Tree contents
     */
    public String toString()
    {
        String list = inOrder(root);
        if(root != null)
        {
            //trim the final comma
            if((list.substring(list.length()-2,list.length())).equalsIgnoreCase(", "))
            {
                list = list.substring(0,list.length() - 2);
            }
        }
        return "[" + list + "]";
    }
    /*
     * Recursive helper function for retrieving tree contents in order.
     */
    private String inOrder(Node<T> n)
    {
        String out = "";
        if(n != null)
        {
            out += inOrder(n.left);
            out += n.element.toString() + ", ";
            out += inOrder(n.right);
        }
        return out;
    }
    /**
     * 
     * Visit method for some arbitrary visitor object.
     * 
     * @param <R> return type of the visitor
     * @param v visitor itself
     * @return an arbitrary object
     */
    public <R> R visit(IVisitor<T,R> v)
    {
        return visit(v,root);
    }
    /*
     * Recursive helper for visiting each node.
     */
    private <R> R visit(IVisitor<T,R> v, Node<T> n)
    {
        R ret = null;
        if(n != null)
        {
            visit(v,n.left);
            ret = n.visit(v);
            visit(v,n.right);
        }
        return ret;
    }
    /*
     * Inner node class.
     */
    class Node <E extends Comparable<E>>
    {
        E element;
        Node <E> left, right;
        Node(E element, Node<E> left, Node<E> right)
        {
            this.element = element;
            this.left = left;
            this.right = right;
        }
        /*
         * Visitor method for this node.
         */
        <R> R visit(IVisitor<E,R> v)
        {
            return v.node(element);
        }
    }
}