using edu.neu.ccs.demeterf;
using Edge = edu.neu.ccs.demeterf.control.Edge;
using Fields = edu.neu.ccs.demeterf.control.Fields;
using System;
using System.IO;

public class threetree{
    public static void Main(string[] a){
        tree t = new none().insert(6).insert(10)
            .insert(12).insert(4).insert(9)
            .insert(3).insert(7).insert(2)
            .insert(5).insert(8).insert(13)
            .insert(11);
        
        Console.WriteLine("     tree: "+t);
        Console.WriteLine("      min: "+t.min());
        Console.WriteLine("   minalt: "+Min.minalt(t));
        Console.WriteLine("     min2: "+Min2.min(t));
        Console.WriteLine("      max: "+t.max());
        Console.WriteLine("isLeaf(n): "+new none().isLeaf());
        Console.WriteLine("isLeaf(o): "+new one(5).isLeaf());
        Console.WriteLine("isLeaf(t): "+t.isLeaf());
        
        /*  Console.WriteLine("  n == n : "+Equal.equal(new none(),new none()));
          Console.WriteLine("  n == o : "+Equal.equal(new none(),new one(4)));
          Console.WriteLine("  o == o : "+Equal.equal(new one(5),new one(5)));
          Console.WriteLine("  o != o : "+Equal.equal(new one(5),new one(4)));
          Console.WriteLine("  t != o : "+Equal.equal(t,new one(4)));
          Console.WriteLine("  o != t : "+Equal.equal(new one(4),t));
          Console.WriteLine("  t == t : "+Equal.equal(t,t));

          tree t1 = new none().insert(3).insert(11);
          tree t2 = new none().insert(11).insert(3);
          
          Console.WriteLine("  t == t : "+Equal.equal(t1,t2));
          Console.WriteLine("  t == t : "+Equal.equal(t2,t1));
          Console.WriteLine("  t == t : "+Equal.equal(t2.insert(4),t1.insert(4)));
          Console.WriteLine("  t != n : "+Equal.equal(t2,new none()));
          Console.WriteLine("  t != t : "+Equal.equal(t2,t1.insert(4)));
          Console.WriteLine("  t != s : "+Equal.equal(t2,"TEST"));
          Console.WriteLine("  t != i : "+Equal.equal(t2,4));

          /**/
        
        tree[] ts = {new none(),new one(6),new one(10).insert(6),t};
        int[] ws = {50,50,50,200};
        int[] hs = {50,50,60,100};
        StreamWriter s = new StreamWriter(new FileStream("test.tex",FileMode.Create));
        s.WriteLine(tex.fileHead());
        for(int i = 0; i < ts.Length; i++)
            s.WriteLine(Display.display(ts[i],ws[i],hs[i]));
        s.WriteLine(tex.fileFoot());
        s.Close();
    }
}

// Ternary Trees
abstract class tree{
    public abstract tree insert(int d);
    public override string ToString(){
        return new Traversal(new ToString()).traverse<string>(this);
    }
    public int min(){ return Min.min(this); }
    public int max(){ return Max.max(this); }
    public bool isLeaf(){ return Leaf.isLeaf3(this); }
}
// Empty Tree
class none : tree{
    public override tree insert(int d){ return new one(d); }
}
// Single integer data
class one : tree{
    static tree e = new none();
    internal int data;
    public one(int d){ data = d; }
    public override tree insert(int d){
        if(d <= data)
            return new three(e,d,e,data,e);
        return new three(e,data,e,d,e);
    }
    public class dataF : Fields.any{}     
}
// Three branches, two datas
class three : tree{
    internal tree left;
    internal int ldata; internal tree mid;
    internal int rdata; internal tree right;

    public three(tree l, int ld, tree m, int rd, tree r){
        left = l; ldata = ld;
        mid = m;
        rdata = rd; right = r;
    }
    public override tree insert(int d){
        if(d <= ldata)
            return new three(left.insert(d),ldata,mid,rdata,right);
        if(d <= rdata)
            return new three(left,ldata,mid.insert(d),rdata,right);
        return new three(left,ldata,mid,rdata,right.insert(d));
    }
    public class leftF : Fields.any{}
    public class ldataF : Fields.any{}
    public class midF : Fields.any{}
    public class rdataF : Fields.any{}
    public class rightF : Fields.any{}
}


class ToString : ID{
    string combine(none n){ return "."; } 
    string combine(one o, int i){ return "("+i+")"; }
    string combine(three t, string l, int ld, string m, int rd, string r){
        return "["+l+","+ld+","+m+","+rd+","+r+"]";
    }
}

class Min : ID{
    none combine(none n){ return n; }
    int combine(tree t, int i){ return i; }
    int combine(three t, tree l, int ld){ return ld; }

    public static int min(tree t){
        Control c = Control.bypass(new Edge(typeof(three),"mid"),
                                   new Edge(typeof(three),"right"));
        return new Traversal(new Min(),c).traverse<int>(t);
    }
    public static int minalt(tree t){
        Control c = Control.only("three.left");
        return new Traversal(new Min(),c).traverse<int>(t);
    }
}
class Max : Min{
    int combine(three t, tree l, int ld, tree m, int rd){ return rd; }
    int combine(three t, tree l, int ld, tree m, int rd, int r){ return r; }

    public static int max(tree t){
        Control c = Control.bypass("three.left three.mid");
        return new Traversal(new Max(),c).traverse<int>(t);
    }
}

class Leaf : ID{
    bool combine(none n){ return true; }
    bool combine(tree t){ return false; }

    public static bool isLeaf(tree t){
        return new Traversal(new Leaf(), Control.nowhere())
                   .traverse<bool>(t);
    }
    public static bool isLeaf2(tree t){
        return Traversal.onestep(new Leaf()).traverse<bool>(t);
    }
    public static bool isLeaf3(tree t){
        return new Traversal(new Leaf(), Control.builtins(typeof(tree)))
                   .traverse<bool>(t);
    }
}

class Equal : ID{
    int update(one o, one.dataF f, one t){ return t.data; }
    int update(three th,  three.ldataF f, three t){ return t.ldata; }
    int update(three th,  three.rdataF f, three t){ return t.rdata; }
    tree update(three th, three.leftF  f, three t){ return t.left; }
    tree update(three th, three.midF   f, three t){ return t.mid; }
    tree update(three th, three.rightF f, three t){ return t.right; }

    bool combine(){ return false; }
    bool combine(none a, none b){ return true; }
    bool combine(int a, int b){ return a == b; }
    bool combine(one a, bool d, one b){ return d; }
    bool combine(three a, bool l, bool ld, bool m, bool rd, bool r, three b){
        return l && ld && m && rd && r;
    }
    
    public static bool equal(object a, object b){ 
        return new Traversal(new Equal()).traverse<bool>(a,b);    
    }
} 

class Min2 : Min{
    int combine(three t, none l, int ld){ return ld; }
    int combine(three t, tree l, int ld){ return min(l); }

    static Traversal trav = Traversal.onestep(new Min2());
    public static int min(tree t){ return trav.traverse<int>(t); }
}


class trip{
    double lx,rx,h;
    public trip(double lxx, double rxx, double hh)
    { lx = lxx; rx = rxx; h = hh; }
    
    public trip left(double dh){ return new trip(lx, lx+w()-20, h+dh); }
    public trip right(double dh){ return new trip(rx-w()+20, rx, h+dh); }
    public trip mid(double dh){ return new trip(lx+w()+20, rx-w()-20, h+dh); }
    public double w(){ return (rx-lx)/3; }
    public double x(){ return (lx+rx)/2; }
    public double y(){ return h; }
}

class Display : ID{
    static double dH = -30;

    trip update(three t, three.leftF f, trip c){ return c.left(dH); }
    trip update(three t, three.midF f, trip c){ return c.mid(dH); }
    trip update(three t, three.rightF f, trip c){ return c.right(dH); }
    
    string combine(none n, trip c){ return tex.circle(c.x(),c.y()+4,4); }
    string combine(one t, int i, trip c){ return tex.box(c.x(),c.y(),12,12,""+i); }
    string combine(three t, string l, int ld, string m, int rd, string r, trip c){
        return (l+m+r+lines(c)+
                tex.box(c.x(),c.y(),28,12,ld+tex.space()+rd));
    }
    static string lines(trip c){
        double h = c.y()-6,
               nh = h+dH+12,
               cx = c.x();
        return (tex.line(cx,h,c.mid(0).x(),nh)+
                tex.line(cx-12,h,c.left(0).x(),nh)+
                tex.line(cx+12,h,c.right(0).x(),nh));
    }
    public static string display(tree t, int w, int h){
        return (tex.head(w,h)+
                new Traversal(new Display())
                .traverse<string>(t,new trip(12,w-12,h-20))
                +tex.foot());
    }
}

class tex{
    public static string d(double v){ return ""+v; }
    public static string fileHead(){
        return ("\\documentclass{article}\n"+
                "\\usepackage{amsmath,amssymb,epic,eepic}\n"+
                "\\title{\\TeX Document}\\date{}"+
                "\\begin{document}\\maketitle\n");
    }
    public static string head(int w, int h){
        return ("{\\small\n"+
                //"\\setlength{\\unitlength}{0.05in}\n"+
                "\\begin{picture}("+w+","+h+")\n"+
                box(w/2,h/2,w+20,h));
    }
    public static string fileFoot(){ return "\\end{document}\n"; }
    public static string foot(){ return "\\end{picture}}\n"; }

    public static string circle(double x, double y, double r)
    { return put(x,y, "\\circle{"+d(r)+"}"); }
    public static string box(double x, double y, double w, double h)
    { return box(x,y,w,h,""); }
    public static string box(double x, double y, double w, double h, string s)
    { return put(x-w/2,y-h/2, "\\framebox("+d(w)+","+d(h)+"){"+s+"}"); }
    public static string put(double x, double y, string tex)
    { return "   \\put("+d(x)+", "+d(y)+"){"+tex+"}\n"; }
    public static string text(double x, double y, string t)
    { return put(x,y,t); }
    public static string line(double x1, double y1, double x2, double y2){
        return "    \\drawline("+d(x1)+","+d(y1)+")("+d(x2)+","+d(y2)+")\n";
    }
    public static string space(){ return " \\  "; }
}