package edu.neu.ccs.demeterf.examples;

import edu.neu.ccs.demeterf.*;
import edu.neu.ccs.demeterf.lib.List;

// 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
    static class Paths extends ID {
        String update(node n, node.left f, String path) { return path+".left"; }
        String update(node n, node.right f, String path) { return path+".right"; }
        List<String> combine(leaf l) { return List.<String>create(); }
        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
    static class Str extends 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
    static class Incr extends Bc { int combine(int i) { return i+1; } }

    // Find the minimum data element in the BST... keep going left
    static class Min extends 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("node.left"))
                       .<Integer>traverse(t);
        }
    }

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

    // The usual functional BST class
    public static abstract class bst {
        public abstract bst insert(int d);
        public static bst create(int ... ns) {
            bst t = new leaf();
            for(int i:ns)
                t = t.insert(i);
            return t;
        }
        public String toString() {
            return new Traversal(new Str()).<String>traverse(this);
        }
    }
    // Functional Leafs
    public static class leaf extends bst {
        public bst insert(int d) { return new node(d, this, this); }
    }
    // Functional Nodes
    public static class node extends bst {
        int data;
        bst left, right;
        public node(int d, bst l, bst r) { data = d; left = l; right = r; }
        public 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... Must be public+static.
        public static class data { }
        public static class left { }
        public static class right { }
    }
}