import java.util.Random;
import java.util.Set;
import java.util.Stack;

public class Main {

  public static void main(String[] args) {
    int RUNS = 100;

    long starttime, endtime;
    int sum = 0;
    double runningTime = 0;

    Tree<Integer> t = generateTree(7, 5, new Random());

    /* recursiveSum */
    for (int i = 0; i < RUNS; i++) {
      starttime = System.nanoTime();
      sum = recursiveSum(t);
      endtime = System.nanoTime();
      runningTime += (endtime - starttime);
    }

    System.out.println("recursiveSum = " + sum
      + ", avg. run time: " + runningTime / RUNS + " ns");

    /* iterativeSum */
    runningTime = 0;
    for (int i = 0; i < RUNS; i++) {
      starttime = System.nanoTime();
      sum = iterativeSum(t);
      endtime = System.nanoTime();
      runningTime += (endtime - starttime);
    }

    System.out.println("iterativeSum = " + sum
      + ", avg. run time: " + runningTime / RUNS + " ns");

  }

  private static int recursiveSum(Tree<Integer> t) {
    if (t == null)
      return 0;

    int sum = t.elem();
    Set<Tree<Integer>> subtrees = t.subtrees();

    for (Tree<Integer> subtree : subtrees) {
      sum += recursiveSum(subtree);
    }

    return sum;
  }

  private static int iterativeSum(Tree<Integer> t) {
    if (t == null)
      return 0;

    int sum = 0;

    Stack<Tree<Integer>> s = new Stack<Tree<Integer>>();
    s.push(t);

    Tree<Integer> tr;
    Set<Tree<Integer>> subtrees;
    while (!s.isEmpty()) {
      tr = s.pop();
      sum += tr.elem();

      subtrees = tr.subtrees();
      for (Tree<Integer> subtree : subtrees) {
        s.push(subtree);
      }
    }

    return sum;
  }

  /**
   * @param h - height of tree
   * @param bf - branching factor
   * @param rand - random generator for generating elements
   */
  private static Tree<Integer> generateTree(int h, int bf, Random rand) {
    Tree<Integer> t = new Tree<Integer>(rand.nextInt(10));

    for (int i = 0; i < bf & h > 0; i++) {
      t.addSubtree(generateTree(h-1, bf, rand));
    }

    return t;

  }

}