Solve the classic Tower of Hanoi using recursion using the following class. Solve the game, step by step, and display your moves in a Window. The design of this project separates the front end and the back end. The backend extends Observable and the front end extends Observer. This design allows for separation of responsibility for the front and back end which increases cohesion and reduces coupling. When there is a change in the observable backend the frontend observer is notified and can update the display accordingly.

Disc extends Shape implements Comparable

Disc(int width): Call the super() constructor, which takes 4 pararemeters: x, y, width and height. Use coordinates (0,0) for now. The width comes from the parameter and the height should come from GameWindow's DISK_HEIGHT which can be referenced statically. Well move these discs after theyre built. After calling super, set the discs background color to a random new Color. To randomly generate a color, call the Color constructor with three random integers ranging from 0 to 255.

compareTo(Disc otherDisc): For use in determining relative size of discs, our Discs are comparable to other discs. If otherDiscis null, be sure to throw an IllegalArgumentException. Otherwise, compare widths and return a negative number if this Disc is smaller than the disc parameter, a positive number for the opposite, and a zero if their widths are equal.

toString(): Return the width of this Disc as a string. Use its getWidth() method.

equals(Object obj): Two discs are equal if they have the same width.

LinkedStack implements StackInterface: Write a LinkedStack class that implements the given StackInterface. Implement this stack with linked nodes. Include a size field and the size() method for keeping track of how many objects are in the LinkedStack. The front end of our project will need this information from the backend.

private Node class: In the LinkedStack class, implement your own inner private Node class at the bottom of the class. These Nodes should be singly linked. To make your logic easier, we recommend making a constructor which sets both its data and its nextNode fields immediately upon creation.

LinkedStack(): One Node field, named topNode, should be null by default. Since the stack is empty, there isnt a head node yet.

size() && isEmpty() && clear() && toString() : Implement these yourself. Make toString() look the same as if you were printing out an array with the same contents. For example, if stack1 is a LinkedStack with 3 items in it, stack1.toString() should output "[lastPush, secondPush, firstPush]", or "[]" if stack1 is empty. Notice the order of the output is from top to bottom. It is generally preferable to use a StringBuilder for string concatenation in Java. It is much faster and consumes less memory.

push(T anEntry): Push will push a new entry on the top of the stack. Place anEntry in a new Node, and set its nextNode to be your head field. This puts anEntry in front of your topNode. Finally, update topNode to be the new Node, and increment your size.

peek(): Peek exists to show whats on the top of the stack, without modifying the stack in any way. If the stack is empty, this method throws an EmptyStackException. Otherwise, return your topNodes data. You'll need to import java.util.EmptyStackException.

pop(): Pop will throw an EmptyStackException if called on an empty stack. Use java.util.EmptyStackException. Otherwise, your job here is to take away the Node from the top of the stack, and return its data. Store your topNode data field in a local variable. Set the topNode to be the topNodes next node, effectively losing the original top Node. Luckily, you already saved it as a local variable. Decrement your size, and return the original top Nodes data.

enumerator Position: Make a new Enum much like you would make a new Class, go to File> New > Enum. Name it Position, and click Finish. Inside our Position enum file, youll see an empty code block. Inside, separated by commas, name your positions. They are LEFT, MIDDLE, RIGHT, OTHER; and will be used to determine the Tower position. The constructor in this Enum is not needed.

Tower extends LinkedStack : The Towers on which we store Discs function as stacks. We extend the LinkedStack we just implemented, since Towers offer a unique extension to a normal stack - they only allow smaller discs to be placed on top of larger ones.

Tower(Position position) Call the super() constructor to create our stack and then store this Towers position in a field.

position() Return your Towers position here.

push(Disc disc) This push method must override the LinkedStacks push. Make sure you add an @Override tag to this method.

We need to check if it is valid to push the disc provided. If this tower is already empty, or the disc on top is larger than the disc being pushed, we have a valid push. Use the discs compareTo()method to determine which is smaller. If it is a valid push, we call super.push(), and provide the disc. If this is an invalid push, we will throw an IllegalStateException or if the disc passed in is null we should throw an IllegalArgumentException.

HanoiSolver extends Observable: Your HanoiSolver represents a Tower of Hanoi game. These games vary in regard to how many discs are used, so the constructor requires this as a parameter. There are always three towers, so you will have three private Tower fields named left, middle, and right. You also extend Observable, so that theGameWindow may observe HanoiSolver to update the display which animates the Discs.

HanoiSolver(int numDiscs): Every Tower of Hanoi game requires the number of discs to be specified. Store numDiscs in a field, and initialize your three Tower fields to be new Towers, with the corresponding Position.LEFT,Position.MIDDLE, or Position.RIGHT provided as parameters. Leave them empty for now. The front end will fill them in later.

discs(): return the number of discs, numDiscs.

getTower(Position pos): Depending on the position requested, return either left, middle, or right. The enumerated type makes it straightforward to use a switch statement here. Note that there is still the fourth enum type other. This is for testing purposes so that you have a way to test the default case in your switch statement. In the default case, you should return the left tower.

toString(): Return left , middle, and rights toString() appended. For example: if the left, middle, right tower each have a single disc with width of 10, 20, and 30 respectively, the output of toString() is [10][20][30]". To test toString() you will need to instantiate a HanoiSolver object and push discs onto its towers.

move(Tower source, Tower destination): This method executes the specified move. Pop the Disc from the "source" Tower, and push it onto the "destination" Tower. Any error checking and handling will be done by the Tower class, such asIllegalStateException or NullPointerException. Now we need to then indicate that something has changed about this class with a call to setChanged(), then tells any observers that its time to update with a call notifyObservers(destination.position()). The destination towers position is provided, to communicate with the front end as to which Tower needs to be updated.

solveTowers(int currentDiscs, Tower startPole, Tower tempPole, Tower endPole): Implement your recursive solveTowers() method with help from your textbook. Start with the base case where there is only one disc left to move. Otherwise, you recursively solve smaller subproblems by callingsolveTowers() with slightly different parameters, invoking the move()method when it is necessary for a disc to be moved.

solve(): Your solve() method will be public and it makes the initial call to the recursive solveTowers()method. It provides the solveTowers() method the correct parameters, with left being the start, middle being the temp, and right being the end.

GameWindow implements Observer: Our GameWindow creates the Window in which we view the game, and observes HanoiSolvergiven to it by the main method present in ProjectRunner (refer the complete UML diagram given in the beginning) for updates on when to animate the Window. Because this class is an Observer, it requires the update() method. Leave it empty for now. This front end class should have oneHanoiSolver field named game, and three Shape fields indicating the left, middle and righttowers on the front end.

Copy and paste the two methods below into this GameWindow.

private void sleep() {

try { Thread.sleep(500); } catch (Exception e) { }

} public void clickedSolve(Button button) {

button.disable();

new Thread() {

public void run() {

game.solve();

}

}.start();

}

moveDisc(Position position)

This method updates the front end, after the back end has been changed. We only need the position parameter so we can peek at the Disc that was just moved to get needed information for the display. The backend already moved the discs between the Towers.

Make a local Disc variable named currentDisc and a local Shape variable currentPole for storing theDisc and pole associated with the move. Use position as a parameter togetTower() to get the current disc.

Hint, to invoke getTower() from within moveDisc(Position position) please recall the following:

1) the getTower() method was implemented within HanoiSolver.

2) GameWindow should include a field of type HanoiSolver (see UML for further detail).

Then, determine which Shape field corresponds to this position. If the Position is LEFT, set your local variable to be left, and so on.

The moveTo() method that Disc inherits from Shape will graphically relocate the disc in the display. Use the getX(), getY(), getWidth(), and getHeight() methods for the disc and pole to determine the new X and Y coordinates to which the disc will move. You will also need the size() of the tower to know how many discs are underneath the current one, to adjust its Y position appropriately. If you want to add a gap between discs or a height from the base of the pole, you can use the final attributes DISK_GAP and DISK_HEIGHT respectively in your calculations of the new y.

GameWindow(HanoiSolver game)

Store the game parameter in a field, and call games addObserver(this) method. Provide this (not a string) as its parameter to indicate that this class is observing it for updates.

Declare a new Window as a class field. Give it the title Tower of Hanoi.

Now were going to initialize your Shape fields that represent the towers. They should be very tall and narrow rectangles, somewhat reasonably spaced in the window, with the left one being the farthest left, and so on. The Color and everything else is up to you. Once you see them on the display, play with the parameters. They should not affect your programs performance or test compatibility.

In a for loop, based on the games number of discs, generate the discs from largest to smallest. Make a new Disc with its width based on the for loops index. Make the disc width a multiple of some number between 5 and 15, depending on your aesthetic preference. Next, add the Discto the Window. Push eachDisc onto the games left Tower, then call moveDisc(Position.LEFT) inside the loop. This will update the discs x,y location to the correct spot on the Window.

After the loop, add the previously created left, middle, and right Shape fields to the Window. We add them after the discs so that they appear underneath the discs. If you want to manipulate the ordering of aShape, you can call its bringToFront() or sendToBack() methods. Now well deal with your button. Declare a new Button named solve that says Solve, add it to the SOUTH side of the Window, and tell it to onClick(this, "clickedSolve").

update(Observable o, Object arg): Our update method is called automatically when the games move method calls notifyObservers. InHanoiSolver, we passed notifyObservers() a Position as a parameter. That Position will passed as our arg parameter here. To start, check if arg.getClass() equals Position.class. If true, cast your arg to be a Position. Call the previously created moveDisc method with your position, then call sleep().

ProjectRunner: main(String[] args): Here, we make a new GameWindow, and pass it a new HanoiSolver, which we pass the number of discs to use. To determine how many discs to use, declare a local variable named discs which is five by default. If the String array args length is exactly one, set your discs integer to be the Integer parsed from the args[0] location (discs = Integer.parseInt(args[0])). This allows you to change this programs Run Configuration > Arguments to any number you like, but only if there's one argument.

> GProjectRunner towerofhanoi Java Class>> GDisc towerofhanoi > TStacklnterface ProjectRunner0 Disc(int) o compare To Disc):int stack main(String]):void o push(T):void opop):T o equals(Object):boolean o toString:String Java Class>> CGameWindow towerofhanoi peek0:T o isEmpty0:boolean o clear0:void a window: Window a left: Shape a midde: Shape a right: Shape a aame: HanoiSolver DISC_GAP: int SDISC HEIGHT: int > Hanoi Solver towerofhanoi a left: Tower a midde: Tower Java Class>> Linked Stack Tower towerofhanoi a numDiscs: int atopNode: Node a sze: int GameWindow(HanoiSolver) a sleep):void o clickedSolve(Button):void o update (Observable,Object):void HanoiSolverfint) o discs0:int o getTower(Position): Tower E move(lower, lower).vo a solve Towers(int, Tower,Tower, Tower):void LinkedStack0 o clear): void o isEmpty0:boolean o peek0 o popO o size):int o push(T):void o toString0:String moeDisc(Position):void o solve.void o toString:String > Position towerofhanoi Java Class>> GNode towerofhanoi SLEFT: Position Java Class>> CTower towerofhanoi a position: Position Tower(Position) o position0:Position MIDDLE: Position a next: Node o getData0 e setNextNode(Node):void Position o push(Disc):void