Computer Science 15-100 (Lecture 18), Spring 2009
Homework 11
Due:  Mon 20-Apr-2009 at 11:59pm (email copy) and at Tuesday's class/recitation (identical physical copy)
(no late submissions accepted).

Same general instructions as hw9.

1. Sorting Animation
2. Bonus/Optional:  Sokoban

1. Sorting Animation
   For this assignment, you will write a sorting animation similar in design to the one we have studied at TMCM.  Here is the completed application:  hw11SortingAnimation.jar (app)  (or hw11SortingAnimation.zip for a zipped version of the jar)
   
   The animation is self-explanatory (hit 'h' for help).  Run it for a while.  You will see that bars are arranged randomly (and sized from 1 to N, where there are N bars), then the sort is animated such that each comparison is highlighted in yellow, then each actual swap is highlighted in green.  Note that this working application is the design spec, so be sure to try every command, resize the window, etc, to understand what your task is.
   
   While not required, here is the recommended approach:
    
   1. Extend JComponentWithEvents.
   2. Include a helper class called SortStep that represents one step in a sort (either a "compare" or a "swap").
   3. Rewrite the provided versions of bubblesort, insertionsort, and selectionsort so that they not only call "swap", but they also call "compare" when comparing two elements in the array.  That is, instead of (a[i] < a[j]), they would call (compare(a,i,j) < 0).  You must write this compare method.
   4. Create an ArrayList of SortSteps.
   5. Each time you reset/shuffle the array, also clear the sortSteps ArrayList, then sort a copy of the array, but have your compare and swap methods not only do the appropriate step, but also create a new instance of SortStep that represents the step (whether it's a compare or a swap, and which indices are involved), and add this to the end of the sortSteps ArrayList.
   6. Now, even though you've sorted a copy of the array, actually display the original unsorted version.
   7. Now, with each step (either when the user hits 's' or, if we are in run mode, when the timer fires), do the current step and advance the step counter (a variable of your creation) by one.  Of course, your paint method will need to refer to the step counter and the sortSteps ArrayList to determine which bars to paint in yellow or green. 
   8. The rest is up to you.  Remember:  the provided application is the spec, so reproduce it as faithfully as possible (do not embellish, not even for bonus!).  Have fun!!!!!
       
2. Bonus/Optional:  Sokoban
   First, if you don't know already, learn how to play Sokoban (it's fun!).  Try this game, for example (among countless many on the web):
     http://javaboutique.internet.com/Sokoban/
   Now, in a file named Hw11BonusSokoban.java, create a class that extends JComponentWithEvents which reproduces Sokoban as faithfully as you can (though you can make reasonable simplifications or other changes to the visual design as you deem appropriate, such as using simplified graphics, so long as you do not change the rules of the game).  Of course, there is an abundance of free Sokoban source code out there (including at the site listed above!), so (as usual) you should not look at any of that source code!  This is both as a matter of academic integrity as well as to ensure that this is a rich learning experience for you.  Feel free to add interesting options, such as a level editor, a high score list, and -- if you think you can -- a Sokoban solver!  Be sure to include your timesheet, as usual.  And have fun!!!

Carpe diem!