package gd09solution.util;

import y.base.Node;
import y.util.YRandom;
import y.view.Graph2D;

/**
 * This classes method randomly generates a binary tree, with a given number of nodes.
 * The first node of the graph is the root, an all edges are directed towards the leaves.
 * @author mader
 *
 */
public class BinaryTreeGenerator {
	
	/**
	 * returns a random binary rooted tree with n nodes.
	 * @param g the graph to which to store the tree.
	 * @param n the desired number of nodes
	 * @return the <code>Graph2D</code> containing the generated tree.
	 */
	public static void getBinaryTree(Graph2D g, int n){
		// check integrity of parameters
		if (n<1) return;
		
		// clear the graph
		g.clear();
		
		// fields
		Node[] tempNodes = new Node[n];
		YRandom randomIntGen = new YRandom();
		
		// create root, index is 0
		Node root = g.createNode();
		tempNodes[root.index()] = root;
		
		if (n<2) return;
		
		// create node with index 1, can only be appended to root
		Node n1 = g.createNode();
		tempNodes[n1.index()] = n1;
		g.createEdge(root, n1);
		
		// create other nodes, index from 2 to n-1
		// every new node will be a leaf, for each index,
		// a current node with outdegree < 2 is randomly choosen, 
		// and the new node is appended to that node.
		for (int i=2; i<n; i++){
			// create the new leaf
			Node leaf = g.createNode();
			tempNodes[leaf.index()] = leaf;
			// look for a node to which to append the new leaf
			int x;
			do {
				x = randomIntGen.nextInt(i-1);
			} while (tempNodes[x].outDegree() >= 2);
			Node parent = tempNodes[x];
			// connect leaf to new node
			g.createEdge(parent, leaf);
		}
		
	}

}