/* 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: * <ul><li><font size=4><code>public T combine(){ ... }</code></font><br/> No parameters, the * return becomes the default value for traversal leafs</li> * <li><font size=4><code>public T fold(T acc, T one){ ... }</code></font><br/> Folds * together two <code>T</code>s for unification of compound objects</li> * <li>Then you just need to implement <code>T combine(X x)</code> for interesting * types, that will add to the final accumulated value.</li> * </ul> * * The easiest way to use TUCombiner is to subclass, and create a wrapper method: * <style type='text/css'> * .def{ color: #000000; } * .grade{ * border: solid #FF0000 1px; * background-color: #FFFF60; * } * .gcom{ font-weight: bold; background-color: #FFC0C0; } * .com{ font-style: italic; color: #880000; } * .keyw{ font-weight: bold; color: #000088; } * .num{ color: #00AA00; } * .func{ color: #BB7733; } * .str{ color: #CC00AB; } * .prim{ color: #0000FF; } * </style> * <blockquote><code><pre> * </span><span class="def"> </span><span class="com">// Example Binary Tree Representation...</span><span class="def"> * </span><span class="keyw">abstract</span><span class="def"> </span><span class="keyw">class</span><span class="def"> BTree{} * </span><span class="keyw">class</span><span class="def"> Leaf </span><span class="keyw">extends</span><span class="def"> BTree{ * </span><span class="keyw">int</span><span class="def"> data; * </span><span class="func">Leaf</span><span class="def">(</span><span class="keyw">int</span><span class="def"> i){ data = i; } * } * </span><span class="keyw">class</span><span class="def"> Node </span><span class="keyw">extends</span><span class="def"> BTree{ * BTree left, right; * </span><span class="func">Node</span><span class="def">(BTree l, BTree r){ left = l; right = r; } * } * * </span><span class="com">// Concrete TUCombiner Class * // Counts the number of Leafs in a BTree instance</span><span class="def"> * </span><span class="keyw">class</span><span class="def"> CountLeafs </span><span class="keyw">extends</span><span class="def"> TUCombiner<</span><span class="prim">Integer</span><span class="def">>{ * </span><span class="keyw">public</span><span class="def"> </span><span class="prim">Integer</span><span class="def"> </span><span class="func">combine</span><span class="def">(){ </span><span class="keyw">return</span><span class="def"> </span><span class="num">0</span><span class="def">; } * </span><span class="keyw">public</span><span class="def"> </span><span class="prim">Integer</span><span class="def"> </span><span class="func">fold</span><span class="def">(</span><span class="prim">Integer</span><span class="def"> i, </span><span class="prim">Integer</span><span class="def"> j){ </span><span class="keyw">return</span><span class="def"> i+j; } * </span><span class="keyw">int</span><span class="def"> </span><span class="func">combine</span><span class="def">(Leaf l){ </span><span class="keyw">return</span><span class="def"> </span><span class="num">1</span><span class="def">; } * * </span><span class="keyw">static</span><span class="def"> </span><span class="keyw">int</span><span class="def"> </span><span class="func">leafs</span><span class="def">(BTree t){ * </span><span class="keyw">return</span><span class="def"> TUCombiner.</span><span class="func">traverse</span><span class="def">(t, </span><span class="keyw">new</span><span class="def"> </span><span class="func">CountLeafs</span><span class="def">()); * } * } </span> * </pre></code></blockquote> * * <p>TUCombiner will make sure that the <code>Leaf</code> class becomes an actual * <i>leaf</i> of the traversal, because the combine method only takes one parameter. * If there are other cases that we care about we can add more <code>combine</code> * methods, one for each to be considered a <i>value producing</i> leaf with a * return type <code>T</code>.</p> * * For <i>non-leaf</i> 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<T> 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())).<T>traverse(o); } /** Use this to do a TU Traversal of an Object with a given Control * for optimization purposes. <i>Note</i>: The function object is <b>not</b> run on <i>bypassed</i> edges, so * your methods *must* handle these edges correctly. */ public T traverse(Object o, MutableControl c){ return new Traversal(this, control(this, c)).<T>traverse(o); } /** TU Traversal On the Heap instead of the stack */ public T traverseHeap(Object o){ return new HeapTrav(this, control(this, Control.builtins())).<T>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)).<T>traverse(o); } /** Uses ParTraversal to do combines in parallel */ public static <R> R traversePar(Object o, TU<R> tuc){ return new ParTraversal(tuc, control(tuc, Control.builtins())).<R>traverse(o); } /** Uses ParTraversal to do combines in parallel */ public static <R> R traversePar(Object o, TU<R> tuc, MutableControl c){ return new ParTraversal(tuc, control(tuc, c)).<R>traverse(o); } /** Collect the implied control from the TUCombiner's signatures and add it * to the given MutableControl */ protected static <R> MutableControl control(TU<R> tuc, MutableControl c){ for(DBEntry<Method> dbe : MethodDB.getMethods(tuc.getClass(), FC.buildMethodName)){ if(dbe.numArgs() == 1 && !dbe.arg(0).equals(Object.class)) c.addBuiltIn(dbe.arg(0)); } return c; } }