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 combine(leaf l) { return new Empty(); } List combine(node n, int d, List l, List 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 : TP { 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(t); } } class Sum : TU{ 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 TU.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>(tree, "root") .ToString("\n"," ")); Console.WriteLine("\n Incr: "+new Traversal(new Incr()).traverse(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(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 { protected int data; protected 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 { } } }