import java.util.*;

/*
 * YOU MUST FILL IN THE CODE FOR THE FOLLOWING TWO METHODS:
 * - runPlayoffsRecursively
 * - runPlayoffsIteratively
 * 
 * This class uses an array to manage a full tree.
 * 
 * NOTE: YOU MAY ADD HELPER METHODS
 */
public class PlayoffsManager 
{
	// ALL OF OUR TREE DATA GOES IN THIS ARRAY. REMEMBER, WE
	// ARE NOT STORING SEQUENTIAL DATA.
	private BaseballTeam[] bracket = null;
	
	// THIS REPRESENTS THE NUMBER OF NODES IN THE LOWEST LEVEL
	// IT'S IMPORTANT FOR VARIOUS CALCULATIONS
	private int numTeams = 0;

	/*
	 * Default constructor, it does nothing
	 */
	public PlayoffsManager() {}

	/*
	 * ACCESSOR METHOD
	 */
	public int getNumTeams() { return numTeams; }

	/*
	 * DO NOT CHANGE THIS METHOD
	 * 
	 * This method is given the 8 teams participating in the
	 * playoffs and it places them in the correct locations
	 * inside the array.
	 */
	public void initTeams(BaseballTeam[] teams)
	{
		numTeams = teams.length;
		bracket = new BaseballTeam[(numTeams*2)-1];
		int bracketFirstTeamIndex = bracket.length - numTeams;
		
		// ADD THE TEAMS
		for (int i = 0; i < teams.length; i++)
		{
			bracket[bracketFirstTeamIndex + i] = teams[i];
		}
		
		// THE REST OF THE NODES ARE NOT YET DETERMINED
		// SINCE WE HAVEN'T YET PLAYED THE GAMES
		for (int j = 0; j < bracketFirstTeamIndex; j++)
		{
			bracket[j] = null;
		}
	}
	
	public int getIndexOfParentNode(int childIndex)
	{
		return (int)(Math.floor((childIndex-1)/2));
	}
	
	public int getIndexOfLeftChildNode(int parentIndex)
	{
		return (2 * parentIndex) + 1;
	}
	
	public int getIndexOfRightChildNode(int parentIndex)
	{
		return (2 * parentIndex) + 2;
	}

	/*
	 * YOU MUST DEFINE THIS METHOD
	 * 
	 * This method does the same thing as 
	 * runPlayoffsRecursively, but does it
	 * iteratively.
	 */	
	public void runPlayoffsIteratively()
	{
		for (int i = 6; i >= 0; i--)
		{
			int left = getIndexOfLeftChildNode(i);
			int right = getIndexOfRightChildNode(i);
			bracket[i] = playGame(bracket[left], bracket[right]);
		}
	}
	
	/*
	 * YOU MUST DEFINE THIE METHOD
	 * 
	 * This method should walk the tree and use the playGame to
	 * determine winners in all games. It should then fill in the
	 * bracket with this data. THIS METHOD MUST BE
	 * IMPLEMENTED RECURSIVELY (USE HELPER METHOD)
	 */
	public void runPlayoffsRecursively()
	{
// ADD YOUR CODE HERE
		if (bracket == null)
			return;
		else if (bracket.length == 0)
			return;
		else
			computeGames(0);
	}
	
	public boolean nodeIsLeaf(int node)
	{
		int minLeafIndex = bracket.length - numTeams;
		if (node < minLeafIndex)
			return false;
		else
			return true;
	}
	
	public void computeGames(int node)
	{
		// POST-ORDER TRAVERSAL HERE		
		if (!nodeIsLeaf(node))
		{
			int left = getIndexOfLeftChildNode(node);
			int right = getIndexOfRightChildNode(node);
			computeGames(left);
			computeGames(right);
			bracket[node] = playGame(bracket[left], bracket[right]);
		}
	}

	/*
	 * DO NOT CHANGE THIS METHOD
	 * 
	 * This method takes 2 constructed team objects and returns the
	 * winner. It uses the records of the two teams to make a weighted
	 * random prediction and returns the winner.
	 */
	public BaseballTeam playGame(BaseballTeam team1, BaseballTeam team2)
	{
		double team1RandomNum = team1.calculateWinningPercentage() * Math.random();
		double team2RandomNum = team2.calculateWinningPercentage() * Math.random();
		if (team1RandomNum > team2RandomNum)
		{
			return team1;
		}
		else
		{
			return team2;
		}
	}

	/*
	 * DO NOT CHANGE THIS METHOD
	 * 
	 * This method returns your Iterator
	 */
	public Iterator bottomUpPlayoffsIterator()
	{
		return new BottomUpPlayoffsIterator();
	}

	/*
	 * DO NOT CHANGE THIS METHOD
	 * 
	 * This is a helper method for our Iterator
	 */
	public int logBase2(int num)
	{
		int counter = 0;
		while (num > 1)
		{
			counter++;
			num /= 2;
		}
		return counter;
	}

	/*
	 * DO NOT CHANGE THIS CLASS. IT WILL PRODUCE 
	 * ELEMENTS LEFT TO RIGHT, BOTTOM LEVEL FIRST.
	 */
	class BottomUpPlayoffsIterator implements Iterator
	{
		int index = bracket.length - numTeams;
		int level = logBase2(numTeams);

		public boolean hasNext()
		{
			if (index >= 0)
				return true;
			else
				return false;
		}
		
		public Object next()
		{
			if (index < 0)
				return null;
			else if (index == 0)
				return bracket[index--];
			else
			{
				// RANGE FOR A LEVEL IS 2^(level-1) through 2^(level) - 1
				int min = (int)Math.pow(2, level)-1;
				int max = (int)Math.pow(2, level+1) - 2;
				if (index > max)
				{
					level--;
					index = (int)Math.pow(2, level)-1;
				}
				Object objectToReturn = bracket[index];
				if (index == 0)
					index--;
				else
					index++;
				return objectToReturn;
			}
		}
		
		public void remove(){}
	}
}