package edu.neu.ccs.demeterf.examples;
/** Test of the Parallel Traversal Version.  Generates a (Huge) Binary
 * Search Tree (BST), then Sums the data elements (ints) sequentially
 * and in parallel, giving the timing results for each. */

import edu.neu.ccs.demeterf.*;
import java.util.Random;

abstract class PTree{}
class PNode extends PTree{
    int data;
    PTree left, right;
    PNode(int d, PTree l, PTree r){ data = d; left = l; right = r; }
}
class PLeaf extends PTree{ PLeaf(){} }

class SumTree extends IDb{
    int combine(PLeaf l){ 
        //System.out.println(" Thread = "+Thread.currentThread().getId());
        return 0;    
    }
    int combine(PNode n, int d, int l, int r){ return d+l+r; }
}

class StringTree extends IDb{
    String combine(PLeaf l){ return "_"; }
    String combine(PNode n, int d, String l, String r)
    { return "("+d+" "+l+" "+r+")"; }
}

public class ParallelTree {
    static PLeaf leaf = new PLeaf();
    static Random rand = new Random();
    static void p(String s){ System.out.print(s); }
    static int randInt(){ return rand.nextInt(2000); }
    
    static PTree generate(int depth){
        if(depth == 0)return leaf;
        return new PNode(randInt(), generate(depth-1), generate(depth-1)); 
    }
    static Traversal pTrav(IDb b){ return new ParTraversal(b); }
    static Traversal sTrav(IDb b){ return new Traversal(b); }
    public static void main(String s[]){
        //Traversal str = sTrav(new StringTree());
        Traversal ssum = sTrav(new SumTree());
        Traversal psum = pTrav(new SumTree());
        PTree t = generate(10);
        
        Long l = System.currentTimeMillis();
        //p("TREE: "+str.traverse(t));
        p(" P-SUM: "+psum.traverse(t));
        p("\nP-Time: "+(System.currentTimeMillis()-l)/1000.0+" sec");
        
        l = System.currentTimeMillis();
        p("\n\n S-SUM: "+ssum.traverse(t));
        p("\nS-Time: "+(System.currentTimeMillis()-l)/1000.0+" sec");
    }
}