package org.ahmadsoft.recursion;

import java.io.PrintStream;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Random;
import java.util.Stack;

/**
 * Test program to quantify recursive performance on Java.
 * @author aahmad
 */
public class RecursionTester {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		PrintStream out = System.out;
		out.println("Recursion Tester v1.0");
		out.println(System.getProperty("java.runtime.name"));
		out.println(System.getProperty("java.runtime.version"));
		
		
		// Create 1,000,000 node tree with a branch
		// factor of 5.

		int branchFactor = 5;
		out.print("creating tree with branch factor " + branchFactor + "...");
		long ts = System.nanoTime();
		Random random = new Random(System.currentTimeMillis());
		TreeNode root = new TreeNode(null, random.nextInt(5));
		int created = 1;

		LinkedList toProcess = new LinkedList();
		toProcess.add(root);
		
		while (created < 100000) {
			TreeNode node = (TreeNode) toProcess.removeFirst();
			for (int j=0; j<branchFactor; ++j) {
				TreeNode child = new TreeNode(node, random.nextInt(5));
				toProcess.addLast(child);
			}
			created += branchFactor;
		}
		long te = System.nanoTime();
		out.println(created + " nodes created in " + (te-ts) + "ns.");
		
		int iterations = 50;
		long tsum=0,msum=0;

		out.print("summing with recursion 1...");
		for (int j=0; j<iterations; ++j) {
			runGC();
			long m1 = usedMemory(), a = System.nanoTime();
			computeSumRecursive_impl1(root);
			long b = System.nanoTime(), m2 = usedMemory();
			tsum += (b-a);
			msum += (m2-m1);
		}
		out.println("average time="+(tsum/iterations)+", average memory="+(msum/iterations));
		
		tsum=0; msum=0;
		out.print("summing with recursion 2...");
		for (int j=0; j<iterations; ++j) {
			runGC();
			long m1 = usedMemory(), a = System.nanoTime();
			computeSumRecursive_impl2(root);
			long b = System.nanoTime(), m2 = usedMemory();
			tsum += (b-a);
			msum += (m2-m1);
		}
		out.println("average time="+(tsum/iterations)+", average memory="+(msum/iterations));
		
		tsum=0; msum=0;
		out.print("summing with stack 1...");
		for (int j=0; j<iterations; ++j) {
			runGC();
			long m1 = usedMemory(), a = System.nanoTime();
			computeSumStack_impl1(root);
			long b = System.nanoTime(), m2 = usedMemory();
			tsum += (b-a);
			msum += (m2-m1);
		}
		out.println("average time="+(tsum/iterations)+", average memory="+(msum/iterations));
		
		tsum=0; msum=0;
		out.print("summing with stack 2...");
		for (int j=0; j<iterations; ++j) {
			runGC();
			long m1 = usedMemory(), a = System.nanoTime();
			computeSumStack_impl2(root);
			long b = System.nanoTime(), m2 = usedMemory();
			tsum += (b-a);
			msum += (m2-m1);
		}
		out.println("average time="+(tsum/iterations)+", average memory="+(msum/iterations));
		
		tsum=0; msum=0;
		out.print("summing with stack 3...");
		for (int j=0; j<iterations; ++j) {
			runGC();
			long m1 = usedMemory(), a = System.nanoTime();
			computeSumStack_impl3(root);
			long b = System.nanoTime(), m2 = usedMemory();
			tsum += (b-a);
			msum += (m2-m1);
		}
		out.println("average time="+(tsum/iterations)+", average memory="+(msum/iterations));
	}

	/**
	 * Compute the sum of a tree node and its descendants recursively.
	 * Sacrifice code elegance to maximize efficiency.
	 * 
	 * @param root
	 * @return
	 */
	private static int computeSumRecursive_impl1(TreeNode root) {
		int result = root.getValue();
		ArrayList children = root.getChildren();
		
		int size = children.size();
		for (int j=0; j<size; ++j) {
			result += computeSumRecursive_impl1((TreeNode) children.get(j));
		}
		
		return result;
	}

	/**
	 * Compute the sum of a tree node and its descendants recursively.
	 * Use Java 5 syntax for more elegant code but more processing 
	 * overhead.
	 * 
	 * @param root
	 * @return
	 */
	private static int computeSumRecursive_impl2(TreeNode root) {
		int result = root.getValue();
		
		for (TreeNode n: root.getChildren())
			result += computeSumRecursive_impl2(n);
		
		return result;
	}

	/**
	 * A stack-based summation routine that uses loop optimization 
	 * like recursive implementation 1.
	 * @param root
	 * @return
	 */
	private static int computeSumStack_impl1(TreeNode root) {
		Stack<TreeNode> toExamine = new Stack<TreeNode>();
		toExamine.push(root);
		
		int result=root.getValue();
		while (!toExamine.isEmpty()) {
			TreeNode node = toExamine.pop();
			ArrayList children = node.getChildren();
			
			int size = children.size();
			for (int j=0; j<size; ++j) {
				TreeNode child = (TreeNode) children.get(j);
				result += child.getValue();
				toExamine.push(child);
			}
		}
		return result;
	}

	/**
	 * A stack-based summation routine that focuses on readability.
	 * @param root
	 * @return
	 */
	private static int computeSumStack_impl2(TreeNode root) {
		Stack<TreeNode> toExamine = new Stack<TreeNode>();
		toExamine.push(root);
		
		int result=root.getValue();
		while (!toExamine.isEmpty()) 
			for (TreeNode n: toExamine.pop().getChildren()) {
				result += n.getValue();
				toExamine.push(n);
			}
		return result;
	}

	/**
	 * A stack-based summation routine that sacrifices readability
	 * and scalability to achieve maximum performance.
	 * @param root
	 * @return
	 */
	private static int computeSumStack_impl3(TreeNode root) {
		final TreeNode[] nodeStack = new TreeNode[100];
		int start = 0;
		int end = 1;
		nodeStack[start] = root;
		
		int result=root.getValue();
		while (start != end) {
			ArrayList children = nodeStack[start].getChildren();
			if (++start == 100)
				start = 0;
			
			int size = children.size();
			for (int j=0; j<size; ++j) {
				TreeNode child = (TreeNode) children.get(j);
				result += child.getValue();
				if (--start < 0)
					start = 99;
				nodeStack[start] = child;
			}
		}
		return result;
	}
	
	

    private static void runGC ()
    {
        // It helps to call Runtime.gc()
        // using several method calls:
        for (int r = 0; r < 4; ++ r)
			try {
				_runGC ();
			} catch (Exception e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
    }

    private static void _runGC () throws Exception
    {
        long usedMem1 = usedMemory (), usedMem2 = Long.MAX_VALUE;
        for (int i = 0; (usedMem1 < usedMem2) && (i < 500); ++ i)
        {
            s_runtime.runFinalization ();
            s_runtime.gc ();
            Thread.currentThread ().yield ();
            
            usedMem2 = usedMem1;
            usedMem1 = usedMemory ();
        }
    }

    private static long usedMemory ()
    {
        return s_runtime.totalMemory () - s_runtime.freeMemory ();
    }
    
    private static final Runtime s_runtime = Runtime.getRuntime ();
}