public class TowerOfHanoi
{
	// TO DO: Instance Variables
	private HStack towers[] = new HStack[3];
	private int numDiscs;
	/* Construct the Towers of Hanoi (3 towers) with aNumDisc
	 * on the first tower. Each tower can be identified by an
	 * integer number (0 for the first tower, 1 for the second
	 * tower, and 2 for the third tower). Each disc can be identified
	 * by an integer number starting from 0 (for the smallest disc)
	 * and (aNumDisc - 1) for the largest disc.
	 */
	public TowerOfHanoi(int aNumDiscs)
	{
		towers[0] = new HStack();
		towers[1] = new HStack();
		towers[2] = new HStack();
		for(int i = 1; i <= aNumDiscs; i++)
		{
			towers[0].push(aNumDiscs-i);
		}
		numDiscs = aNumDiscs;
	}
	
	/* Returns an array of integer representing the order of
	 * discs on the tower (from bottom up). The bottom disc should
	 * be the first element in the array and the top disc should be
	 * the last element of the array. The size of the array MUST
	 * be the number of discs on the tower. For example, suppose
	 * the tower 0 contains the following discs 0,1,4,6,7,8 (from top
	 * to bottom). This method should return the array [8,7,6,4,1,0]
	 * (from first to last). 
	 * @param tower the integer identify the tower number.
	 * @return an array of integer representing the order of discs.
	 */
	public int[] getArrayOfDiscs(int tower)
	{
		return towers[tower].toArray();
	}
	
	/* Gets the total number of discs in this Towers of Hanoi
	 * @return the total number of discs in this Towers of Hanoi
	 */
	public int getNumberOfDiscs()
	{
		// TO DO
		return numDiscs;
	}
	
	/* Gets the number of discs on a tower.
	 * @param tower the tower identifier (0, 1, or 2)
	 * @return the number of discs on the tower.
	 */
	public int getNumberOfDiscs(int tower)
	{
		return towers[tower].getLength();
	}
	
	/* Moves the top disc from fromTower to toTower. Note that
	 * this operation has to follow the rule of the Tower of Hanoi
	 * puzzle. First fromTower must have at least one disc and second
	 * the top disc of toTower must not be smaller than the top disc
	 * of the fromTower.
	 * @param fromTower the source tower
	 * @param toTower the destination tower
	 * @return ture if successfully move the top disc from
	 *         fromTower to toTower.
	 */
	public boolean moveTopDisc(int fromTower, int toTower)
	{
		if(towers[fromTower].getLength() == 0)
		{
			return false;
		}
		if(towers[toTower].getLength() == 0)
		{
			towers[toTower].push(towers[fromTower].pop());
			return true;
		}
		else if(towers[fromTower].peek() < towers[toTower].peek())
		{
			towers[toTower].push(towers[fromTower].pop());
			return true;
		}
		else
		{
			return false;
		}
	}

	public String toString()
	{
		String s = "[" + towers[0].toString() + "," + towers[1].toString() + "," + towers[2].toString() + "]";
		return s;
	}

	public class HStack
	{
		private HNode head;
		private int length;
		public HStack()
		{
			length = 0;
		}
		public int peek()
		{
			return head.getData();
		}
		public int pop()
		{
			int output = head.getData();
			head = head.getNext();
			length--;
			return output;
		}
		public void push(int i)
		{
			head = new HNode(i,head);
			length++;
		}
		public boolean hasNext()
		{
			return head != null;
		}
		public int getLength()
		{
			return length;
		}
		public String toString()
		{
			String output = "";
			for(HNode tmp = head; tmp != null; tmp=tmp.getNext())
			{
				output += tmp.getData() + " ";
			}
			return output;
		}
		public int[] toArray()
		{
			int[] output = new int[length];
			int i = length-1;
			for(HNode tmp = head; tmp != null; tmp = tmp.getNext())
			{
				output[i] = tmp.getData();
				i--;
			}
			return output;
		}

	}
	public class HNode
	{
		private HNode next = null;
		private int data;
		public HNode(int d, HNode n)
		{
			data = d;
			next = n;
		}
		public int getData()
		{
			return data;
		}
		public HNode getNext()
		{
			return next;
		}
	}
}