/* TUCombiner.java * Bryan Chadwick :: 2007 * TypeUnifying Combiner... Still a work in progress */ package edu.neu.ccs.demeterf; import edu.neu.ccs.demeterf.control.MutableControl; import edu.neu.ccs.demeterf.dispatch.*; import edu.neu.ccs.demeterf.parallel.ParTraversal; import edu.neu.ccs.demeterf.stackless.HeapTrav; import java.lang.reflect.Method; /** A Helper Class to implement something like SYB queries. To use this class, * you must implement at least three methods: *

public T combine(){ ... }
No parameters, the * return becomes the default value for traversal leafs
public T fold(T acc, T one){ ... }
Folds * together two Ts for unification of compound objects
Then you just need to implement T combine(X x) for interesting * types, that will add to the final accumulated value.

* * The easiest way to use TUCombiner is to subclass, and create a wrapper method: * *

 *    // Example Binary Tree Representation...
 *    abstract class BTree{}
 *    class Leaf extends BTree{
 *       int data;
 *       Leaf(int i){ data = i; }
 *    }
 *    class Node extends BTree{
 *       BTree left, right;
 *       Node(BTree l, BTree r){ left = l; right = r; }
 *    }
 *
 *    // Concrete TUCombiner Class
 *    //    Counts the number of Leafs in a BTree instance
 *    class CountLeafs extends TUCombiner<Integer>{
 *       public Integer combine(){ return 0; }
 *       public Integer fold(Integer i, Integer j){ return i+j; }
 *       int combine(Leaf l){ return 1; }
 *   
 *       static int leafs(BTree t){
 *          return TUCombiner.traverse(t, new CountLeafs());
 *       }
 *    } 
 *

* *

TUCombiner will make sure that the Leaf class becomes an actual * leaf of the traversal, because the combine method only takes one parameter. * If there are other cases that we care about we can add more combine * methods, one for each to be considered a value producing leaf with a * return type T.

* * For non-leaf classes of interest, you can write a normal combine methods * (more than one parameter) for special cases, but the recursive results of fields * will always be of type T unless you handle the or to use non-type-unifying traversal * for a portion of the data structure. */ public abstract class TU extends FC{ // Type Unifying combiner (TU) // Default for objects without fields (unless handled earlier) public T combine(Object o1){ return combine(); } /** A Bunch of simple Object* methods to catch all the rest */ public T combine(Object o1, T o2) { return simplify(o2); } public T combine(Object o1, T o2, T o3) { return simplify(o2,o3); } public T combine(Object o1, T o2, T o3, T o4) { return simplify(o2,o3,o4); } public T combine(Object o1, T o2, T o3, T o4, T o5) { return simplify(o2,o3,o4,o5); } public T combine(Object o1, T o2, T o3, T o4, T o5, T o6) { return simplify(o2,o3,o4,o5,o6); } public T combine(Object o1, T o2, T o3, T o4, T o5, T o6, T o7) { return simplify(o2,o3,o4,o5,o6,o7); } public T combine(Object o1, T o2, T o3, T o4, T o5, T o6, T o7, T o8) { return simplify(o2,o3,o4,o5,o6,o7,o8); } public T combine(Object o1, T o2, T o3, T o4, T o5, T o6, T o7, T o8, T o9) { return simplify(o2,o3,o4,o5,o6,o7,o8,o9); } public T combine(Object o1, T o2, T o3, T o4, T o5, T o6, T o7, T o8, T o9, T o10) { return simplify(o2,o3,o4,o5,o6,o7,o8,o9,o10); } //** More if needed... /** The simplify for an array... called from above */ T simplify(T ... o){ return simplify(o, o[0], 1); } /** Recursive fold over the array */ T simplify(T o[], T t, int i){ if(i >= o.length)return t; return simplify(o, fold(t, o[i]), i+1); } // * * * * Actual Stuff... * * * * // Clients extend TUCombiner and implement the methods below. /** Perform one step of the combination */ public abstract T fold(T accum, T one); /** Default combine (must be implemented for safety) */ public abstract T combine(); /** Use this to do a TU Traversal of an Object. It reflects on the given TUCombiner, and sees what you're * interested in (single argument combine methods), making those * classes BuiltIns */ public T traverse(Object o){ return new Traversal(this, control(this, Control.builtins())).traverse(o); } /** Use this to do a TU Traversal of an Object with a given Control * for optimization purposes. Note: The function object is not run on bypassed edges, so * your methods *must* handle these edges correctly. */ public T traverse(Object o, MutableControl c){ return new Traversal(this, control(this, c)).traverse(o); } /** TU Traversal On the Heap instead of the stack */ public T traverseHeap(Object o){ return new HeapTrav(this, control(this, Control.builtins())).traverse(o); } /** TU Traversal On the Heap instead of the stack, with the given control */ public T traverseHeap(Object o, MutableControl c){ return new HeapTrav(this, control(this, c)).traverse(o); } /** Uses ParTraversal to do combines in parallel */ public static R traversePar(Object o, TU tuc){ return new ParTraversal(tuc, control(tuc, Control.builtins())).traverse(o); } /** Uses ParTraversal to do combines in parallel */ public static R traversePar(Object o, TU tuc, MutableControl c){ return new ParTraversal(tuc, control(tuc, c)).traverse(o); } /** Collect the implied control from the TUCombiner's signatures and add it * to the given MutableControl */ protected static MutableControl control(TU tuc, MutableControl c){ for(DBEntry dbe : MethodDB.getMethods(tuc.getClass(), FC.buildMethodName)){ if(dbe.numArgs() == 1 && !dbe.arg(0).equals(Object.class)) c.addBuiltIn(dbe.arg(0)); } return c; } }