1 files changed, 164 insertions, 0 deletions
diff --git a/labs/lab6_toh/TowerOfHanoi.java b/labs/lab6_toh/TowerOfHanoi.java
new file mode 100644
index 0000000..51a394c
--- /dev/null
+++ b/labs/lab6_toh/TowerOfHanoi.java
@@ -0,0 +1,164 @@
+
+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 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;
+		}
+	}
+}