using System;
using edu.neu.ccs.demeterf;
using edu.neu.ccs.demeterf.control;
using edu.neu.ccs.demeterf.lib;


// Test using BSTs... Tests the path based "update", traversal control, and
//   general "combine"s
public class BSTTest {

    // Produces a list of strings representing the paths to each
    //   "data" element in the tree
    class Paths : ID {
        string update(node n, node.leftF f, string path) { return path+".left"; }
        string update(node n, node.rightF f, string path) { return path+".right"; }
        List<string> combine(leaf l) { return new Empty<string>(); }
        List<string> combine(node n, int d, List<string> l, List<string> r, string p) {
            return l.append(r).push(" "+d+" : "+p);
        }
    }

    // Produces a string representation of the tree
    class Str : ID {
        string combine(leaf l) { return ""; }
        string combine(node n, int d, string l, string r) {
            return "("+d+" "+l+" "+r+")";
        }
    }

    // Increments each data element and rebuilds the resulting tree
    class Incr : Bc { int combine(int i) { return i+1; } }

    // Find the minimum data element in the BST... keep going left
    class Min : ID {
        leaf combine(leaf l) { return l; }
        int combine(node n, int d, leaf l) { return d; }
        int combine(node n, int d, int l) { return l;  }
            
        public static int min(bst t) { 
            return new Traversal(new Min(), Control.only(new Edge(typeof(node),"left")))
                       .traverse<int>(t);
        }
    }

    class Sum : TUCombiner<int>{
        public override int combine(){ return 0; }
        public override int fold(int a, int b){ return a+b; }
        int combine(int i){ return i; }
        public static int sum(bst t){ return TUCombiner<int>.traverse(t,new Sum()); }
    }

    // Main method...
    public static void Main(String[] args) {
        bst tree = bst.create(4, 6, 2, 3, 1, 7, 5);
        Console.WriteLine(" Tree: "+tree);
        Console.WriteLine(" Paths:\n"+new Traversal(new Paths())
                                           .traverse<List<string>>(tree, "root")
                                           .ToString("\n","  "));
        Console.WriteLine("\n Incr: "+new Traversal(new Incr()).traverse<bst>(tree));
        Console.WriteLine(" Min: "+Min.min(tree));
        Console.WriteLine(" Sum: "+Sum.sum(tree));
    }

    // The usual functional BST class
    public abstract class bst {
        public abstract bst insert(int d);
        public static bst create(params int[] ns) {
            bst t = new leaf();
            foreach(int i in ns)
                t = t.insert(i);
            return t;
        }
        public override string ToString() {
            return new Traversal(new Str()).traverse<string>(this);
        }
    }
    // Functional Leafs
    public class leaf : bst {
        public override bst insert(int d) { return new node(d, this, this); }
    }
    // Functional Nodes
    public class node : bst {
        int data;
        bst left, right;
        public node(int d, bst l, bst r) { data = d; left = l; right = r; }
        public override bst insert(int d) {
            if(d <= data)
                return new node(data, left.insert(d), right);
            return new node(data, left, right.insert(d));
        }
        // Field classes... have to have different names in C# :(
        //   so we append the "F".  Must be public.
        public class dataF { }
        public class leftF { }
        public class rightF { }
    }
}