package edu.neu.ccs.demeterf.examples;
import edu.neu.ccs.demeterf.Traversal;
import edu.neu.ccs.demeterf.ID;
import edu.neu.ccs.demeterf.compose.CompTraversal;

/** Height/Diameter Composition.  The Height calculation (HTrip) is composed
 *    (passed to) the Diameter calculation (int).  Height is useful on it's
 *    own... but we need to keep a little more information to support the
 *    Diameter calc. */
public class Compose{    
    static BST<Integer> build(int k, BST<Integer> t, int a[]){
        if(k >= a.length)return t;
        return build(k+1, t.insert(a[k]), a);
    }
    static public void main(String args[]){
        BST<Integer> tree = build(0, new BST<Integer>(),
                new int[]{6,3,1,5,0,9,4,7,10,8});

        System.out.print("   Tree: "+tree.toString()+"\n");
        System.out.print(" Height: "+Height.height(tree)+"\n");
        System.out.print("   Diam: "+Diam.diameter(tree)+"\n");
    }

    static class BST<T extends Comparable>{
        BST(){}
        public String toString(){ return new Traversal(new ID(){
            String combine(BST<?> l){ return ""; }
            String combine(Node<?> t, int d, String l, String r)
            {return "("+d+l+r+")"; }       
        }).traverse(this); }
        BST<T> insert(T d){ return new Node<T>(d, this, this); }
    }

    static class Node<T extends Comparable> extends BST<T>{
        T data;
        BST<T> left, right;

        Node(T d, BST<T> l, BST<T> r){ data = d; left = l; right = r; }
        BST<T> insert(T d){
            if(d.compareTo(data) > 0)
                return new Node<T>(data, left.insert(d), right);
            return new Node<T>(data, left, right.insert(d));
        }
    }

    // Contains current, left and right heights of a Tree.
    static class HTrip{
        int ch,lh,rh;
        HTrip(){ this(0,0,0); }
        HTrip(int c, int l, int r){ ch = c; lh = l; rh = r; }
    }

    //  Tree Height Calculation. Produces a HTrip, so that we
    //    can use the values of current/left/right subtrees in 
    //    other calculations
    static class Height extends ID{
        HTrip combine(BST<?> l){ return new HTrip(); }
        HTrip combine(Node<?> t, int d, HTrip l, HTrip r)
        { return new HTrip(1+Math.max(l.ch, r.ch),l.ch, r.ch); }

        // Static Height calculation (could move into BST) 
        static int height(BST<Integer> t){
            return new Traversal(new Height()).<HTrip>traverse(t).ch;
        }
    }

    // Tree Diameter Calculation. The height calculation (HTrip) is passed
    //   as the last parameter to each combine method when we compose the
    //   two function objects into a single traversal.
    static class Diam extends ID{
        int combine(BST<?> l){ return 0; }
        int combine(Node<?> t, int d, int l, int r, HTrip h)
        { return Math.max(h.lh+h.rh+1, Math.max(l,r)); }

        // Static Diameter calculation (could move into BST)
        static int diameter(BST<Integer> t){
            return new CompTraversal(new Height(),new Diam()).<Integer>traverseLast(t);
        }
    }
}