import edu.neu.ccs.demeterf.*; import gen.*; // ** Main.java :: BST Test :: Bryan Chadwick // ** Generates TeX Pictures for BSTs using a few // DemeterF transformations class ToStr extends ID{ String combine(int i){ return ""+i; } String combine(NodeInt t, String d, String l, String r){return "("+d+l+r+")"; } String combine(BSTInt l){ return ""; } } class Incr extends Bc{ int combine(int i){ return i+1; } } class Strs extends IDf{ static String nums[] = {"zero","one","two","three","four","five", "six","seven","eight","nine","ten"}; String apply(int i){ return nums[i]; } } class Rev extends IDb{ BSTInt combine(NodeInt t, Integer d, BSTInt l, BSTInt r){ return new NodeInt(d, r, l); } BSTInt combine(BSTInt l){ return l; } } class Sum extends IDb{ int combine(NodeInt t, int d, int l, int r){ return d+r+l; } int combine(BSTInt l){ return 0; } } class Height extends IDba{ int update(NodeInt n, int i){ return i+1; } int combine(NodeInt t, int d, int l, int r){ return Math.max(l,r); } int combine(BSTInt l, int h){ return h; } } // DownHeight = int. class Height3 extends IDba{ DownHeight update(NodeInt n, DownHeight h){ return new DownHeight(h.get_height()+1); } int combine(NodeInt t, int d, int l, int r){ return Math.max(l,r); } int combine(BSTInt l, DownHeight h){ return h.get_height(); } } class Height2 extends IDb{ int combine(NodeInt t, int d, int l, int r){ return Math.max(l,r)+1; } int combine(BSTInt l){ return 0; } } class Pack{ boolean good; int min,max; Pack(boolean g, int mn, int mx) { good = g; min = mn; max = mx; } Pack(boolean g){ this(g, Integer.MAX_VALUE, Integer.MIN_VALUE); } } class Check extends ID{ Pack combine(BSTInt l){ return new Pack(true); } Pack combine(NodeInt t, int d, Pack lt, Pack rt){ return new Pack((lt.good && rt.good && (lt.max < d) && (d < rt.min)), Math.min(lt.min,d), Math.max(rt.max,d)); } static boolean check(BSTInt tree){ return new Traversal(new Check()) .traverse(tree).good; }} class Diameter extends IDba{ // type unifying // initializing and combining pairs DiameterPair combine(BSTInt l) {return new DiameterPair(0,0);} DiameterPair combine(Object l, DiameterPair p) { return p;} DiameterPair combine(NodeInt t, Integer d, DiameterPair l, DiameterPair r){ return // normal combine: new DiameterPair(l.get_height() + r.get_height(), l.get_diameter() + r.get_diameter()); new DiameterPair(Math.max(l.get_height(), r.get_height())+1, Math.max(l.get_height() + r.get_height() +1, Math.max(l.get_diameter(), r.get_diameter()))); } }