package edu.neu.ccs.demeterf.examples;
import edu.neu.ccs.demeterf.*;
import edu.neu.ccs.demeterf.parallel.ParTraversal;

import java.util.Random;

/** Test of the parallel version of Traversal.  Generates a (Huge) Binary
 * Search Tree (BST), then Sums the data elements (ints) sequentially
 * and in parallel, giving the timing results for each. */

public class ParallelTree {
    static leaf leaf = new leaf();
    static Random rand = new Random();
    static int randInt(){ return rand.nextInt(2000); }
    
    static bst generate(int depth){
        if(depth == 0)return leaf;
        return new node(randInt(), generate(depth-1), generate(depth-1)); 
    }
    static Traversal pTrav(ID b){ return new ParTraversal(b); }
    static Traversal sTrav(ID b){ return new Traversal(b); }
    public static void main(String s[]){
        Traversal ssum = sTrav(new SumTree());
        Traversal psum = pTrav(new SumTree());
        bst t = generate(10);
        
        Long l = System.currentTimeMillis();
        System.out.println("  S-SUM: "+ssum.traverse(t));
        System.out.println(" S-Time: "+(System.currentTimeMillis()-l)/1000.0+" sec");
        
        l = System.currentTimeMillis();
        System.out.println("  P-SUM: "+psum.traverse(t));
        System.out.println(" P-Time: "+(System.currentTimeMillis()-l)/1000.0+" sec\n");
    }
    
    static abstract class bst{
        public String toString(){
            return new Traversal(new ID(){
                String combine(leaf l){ return "_"; }
                String combine(node n, int d, String l, String r)
                { return "("+d+" "+l+" "+r+")"; }        
            }).traverse(this);
        }
    }
    static class leaf extends bst{}
    static class node extends bst{
        int data;
        bst left, right;
        node(int d, bst l, bst r){ data = d; left = l; right = r; }
    }
    
    static class SumTree extends ID{
        int combine(leaf l){ return 0; }
        int combine(node n, int d, int l, int r){ return d+l+r; }
    }
}