import java.util.Random;

/*
 * Created on Jul 12, 2004
 */

/** Code for Midterm 1 exam, last question (plus test code).
 * @author dickey
 */
public class Midterm1WeightBalancedTrees {
	
	static class BinTreeNode {
		Object element;  //should have just made this an int!
		BinTreeNode left, right;

		/** Constructor used in testing (not needed in exam solution)
		 * @param weight weight of this element, >= 0.
		 */
		public BinTreeNode(int weight) {
			assert weight >= 0;
			this.element = new Integer(weight);
		}
		
		/** Constructor used in testing (not needed in exam solution)
		 * A default weight of 0 is assigned.
		 */
		public BinTreeNode() {
			this(0);
		}

	}
	
	//////// Solution to the midterm question starts here.
	//////// The two methods are not required to be static.
	//////// Also, no points were deducted if the "element"
	//////// was treated as if it was declared as int.
	
	public static boolean checkBalance(BinTreeNode node) {
		if (node == null) {
			return true;
		}
		return sum(node.left) == sum(node.right);			
	}
	
	private static int sum(BinTreeNode node) {
		if (node == null) {
			return 0;
		}
		return ((Integer) node.element).intValue()
			+ sum(node.left) + sum(node.right);
	}
	
	///// code below here is for testing -- not part of the solution
	
	static Random rand = new Random();
	
	static BinTreeNode generateTree(int totalWeight) {
		assert totalWeight >= 0;
		if (totalWeight == 0) {
			//could generate a null node, or a 0-weight non-null tree
			if (rand.nextInt(10) > 0) {
				return null; //do this most of the time
			}
		}
		BinTreeNode retNode = new BinTreeNode();
		int[] weights = randomPartsOfSum(totalWeight);
		retNode.element = new Integer(weights[0]);
		retNode.left = generateTree(weights[1]);
		retNode.right = generateTree(weights[2]);
		assert totalWeight == sum(retNode);
		return retNode;
	}
	
	static BinTreeNode generateWeightBalancedNode(int totalWeight) {
		assert totalWeight >= 0;
		if (totalWeight == 0) {
			return generateTree(0);
		}
		if (totalWeight == 1) {
			return new BinTreeNode(1);
		}
		BinTreeNode retNode = new BinTreeNode();
		int childWeights = 2 * rand.nextInt(totalWeight/2);
		retNode.element = new Integer(totalWeight - childWeights);
		retNode.left = generateTree(childWeights/2);
		retNode.right = generateTree(childWeights/2);
		assert totalWeight == sum(retNode);
		assert checkBalance(retNode);
		return retNode;		
	}
	
	/** Find three integers which sum to a given value.
	 * 
	 * @param sum a non-negative integer.
	 * @return an array of three non-negative integers, whose sum
	 * is the given value.
	 */
	public static int[] randomPartsOfSum(int sum) {
		int[] retArray = new int[3];
		if (sum < 0) {
			throw new IllegalArgumentException("target sum " +
					sum + " must be >= 0");
		}
		if (sum == 0) {
			//the default array of all zeros is just fine
		} else {
			//generate the first number
			retArray[0] = rand.nextInt(sum+1);
			//generate the second number
			int remainder = sum - retArray[0];
			retArray[1] = rand.nextInt(remainder+1);
			
		}
		//third number is what's left
		retArray[2] = sum - retArray[0] - retArray[1];
		assert retArray[2] >= 0;
		assert retArray[0] + retArray[1] + retArray[2] == sum;
		return retArray;		
	}
	public static void preOrderDump(BinTreeNode node) {
		if (node == null) {
			System.out.print("null");
			return;
		}
		System.out.print("[S" + sum(node) + "] " + 
									node.element + " (");
		System.out.print("L ");
		preOrderDump(node.left);
		System.out.print(", R ");
		preOrderDump(node.right);
		System.out.print(")");
	}
	
	/** Just for testing.
	 * These may not seem like tests, but the asserts buried inside
	 * the methods are doing lots of self-checking.
	 * @param args
	 */
	public static void main(String[] args) {
		System.out.println("test mid1 weight-balanced trees");
		assert sum(null) == 0;
		BinTreeNode n0 = new BinTreeNode();
		assert sum(n0) == 0;
		assert checkBalance(n0);
		BinTreeNode n1 = new BinTreeNode(1);
		assert sum(n1) == 1;
		assert checkBalance(n1);
		n0.left = n1;
		assert sum(n0) == 1;
		assert !checkBalance(n0);
		n0.right = new BinTreeNode(5);
		assert sum(n0) == 6;
		assert !checkBalance(n0);
		final int MAX_TESTWEIGHT = 3000;
		for (int weight = 0; weight <= MAX_TESTWEIGHT; weight += 29) {
			BinTreeNode node = generateTree(weight);
			//System.out.print("\nW" + weight + ": ");
			//preOrderDump(node);
			BinTreeNode bnode = generateWeightBalancedNode(weight);
			System.out.print("\nBW" + weight + ": ");
			preOrderDump(bnode);
		}
	}

}