//TowersOfHanoi.java

/**
 * A model of the Towers of Hanai problem,
 * complete with a solution.
 *
 * @author Zach Tomaszewski
 * @version 15 Sept 2004
 */
 public class TowersOfHanoi {
 
   /** The number of Towers to use in this simulation */
   public static final int NUM_OF_TOWERS = 3;
   protected Tower[] towers = new Tower[NUM_OF_TOWERS];

   
   /**
    * Constructor.
    * Sets up scenario with the given number of Disks on the first Tower.
    * 
    * @param numOfDisks  must be > 0, or a 0 disks are created.
    */
   public TowersOfHanoi (int numOfDisks){
     //init the towers
     for (int i = 0; i < NUM_OF_TOWERS; i++) {
       towers[i] = new Tower();
     }
     //add the disks on the first tower
     for (int i = numOfDisks; i > 0; i--){
       towers[0].push(new Disk(i));
     }
   }

   /**
    * Empty scenario constructor
    */
    public TowersOfHanoi() {
      this(0);
    }

   /**
    * Returns a String representation of this scenario.
    */
   public String toString() {
     String repres = "";
     for (int i = 0; i < NUM_OF_TOWERS; i++) {
       repres += (char)('A'+i) + " " + towers[i].toString();
     }
     return repres;
   }
 
 
   /**
    * Solves the current Tower of Hanoi scenario,
    * assuming that all disks need to be moved from the first 
    * tower to the last tower.
    *
    * @param print  Whether each step should be printed to the screen.
    */
   public void solve(boolean print) {
     //assuming all disks are on the first tower
     this.move(towers[0].size(), towers[0], towers[2], towers[1], print);
   }
   
   /**
    * Moves n disks from source to destination using temp along the way.
    *
    * @param n  The number of disks to move
    * @param source  The Tower to move disks from
    * @param dest    The Tower to move disks to
    * @param temp    The Tower to use as temporary storage during the move
    * @param print   Whether each move should be printed to the screen
    */
   public void move(int n, Tower source, Tower dest, Tower temp, 
                    boolean print){
     if (n <= 0) { 
       //error case/bad input, so do nothing
       return;
     }else if (n == 1) {
       //only one disk, so just move it
       dest.push(source.pop());
       if (print){
         System.out.println(this);
       }
     }else {
        //move n-1 disks to temp first, using dest as temp
        this.move(n-1, source, temp, dest, print);
        //move the last (nth) disk
        this.move(1, source, dest, temp, print);
        //now that we've moved the biggest (nth) disk, move the n-1
        //disks back from temp to dest
        this.move(n-1, temp, dest, source, print);
     }
   }
  

   /**
    * Runs a scenario as specified by command line args.
    * See the program's usage message for more details.
    */
   public static void main(String[] args){
     if (args.length > 2 || args.length == 0) {
       //incorrect usage, so print usage statement
       printUsage();
     }else {
       try{
         int disks = Integer.parseInt(args[0]);
         boolean print = args.length >= 2 &&
                         (args[1].equalsIgnoreCase("print") ||
                          args[1].equalsIgnoreCase("verbose") ||
                          args[1].equalsIgnoreCase("debug"));
         TowersOfHanoi toh = new TowersOfHanoi(disks);
         System.out.println("INITIAL STATE: \n" + toh);
         toh.solve(print);
         System.out.println("---------------------------");         
         System.out.println("FINAL STATE: \n" + toh);
       }catch (NumberFormatException nfe){
         //problem parsing args[0] as a number
         printUsage();
       }
     }
   }

   /**
    * Prints a usage message for this program to the screen.
    */
   protected static void printUsage() {
     System.out.print("TowersOfHanoi: ");
     System.out.println("Solves of Tower of Hanoi problem.");
     System.out.println("\nUSAGE:  java TowersOfHanoi # [print]");
     System.out.println("\t#     \t- The number of \"disks\" to solve for.");
     System.out.println("\tprint \t- Whether to print each " +
                        "step to the screen."); 
     System.out.println();
   }
 
}
 


//Tower.java

import java.util.Stack;
import java.util.EmptyStackException;

/**
 * A model of a Tower for the Towers of Hanoi problem.
 * Essentially, just a stack, though this Tower will
 * also complain if a large Disk is every placed on top
 * of a smaller Disk.
 *
 * @author Zach Tomaszewski
 * @version 15 Sept 2004
 */
public class Tower extends Stack {
  /*
   * NOTE: In the end, the extra "complain if disk too large is added" 
   * functionality was never used in my TowersOfHanoi solution.  But
   * it could be useful in other problems. (Shouldn't have written it
   * if the first place, but now that it's done, may as well leave it
   * in case someone else needs it.  And it's part of my specs...)
   */
   
  /**
   * Pushes an disk (or other item) onto the Stack.
   * 
   * @throws DiskTooLargeException  if the disk being added is larger 
   *                                than the disk at the top of the stack.
   */
  public Object push(Object disk) {
    if (!this.empty() &&
        ((Comparable) disk).compareTo((Comparable) this.peek()) > 0){
      throw new DiskTooLargeException(disk + " is larger than " + this.peek());
    }
    return super.push(disk);
  }

  /**
   * Returns a String representation of this Tower,
   * printed horizontally and ending in a newline.
   */
  public String toString() {
    String repres = "Tower: ";
    if (this.empty()) {
      repres += "(empty)";
    }else {
      for (int i = 0; i < this.size(); i++) {
        repres += this.get(i).toString();
      }
    }
    repres += "\n";
    return repres;
  }
}



//Disk.java

/**
 * A Disk to be used in a Towers of Hanoi simulation.
 *
 * @author Zach Tomaszewski
 * @version 15 Sept 2004
 */
public class Disk implements Comparable {

  protected int size;  //the size, or order, of this disk
  
  /**
   * Constructor.
   * All Disks must have a size.  A larger value means a larger size.
   */
  public Disk (int size) {
    this.size = size;
  }
  

  /**
   * Returns a string representation of this object
   */
  public String toString() {
    return "[Disk: " + size + "]";
  }
  

  /**
   * @see Comparable
   */
  public int compareTo(Object item){
    return this.size - ((Disk) item).size;
  }

}



//DiskTooLargeException.java

/**
 * An exception for when a disk is added to a tower but is 
 * larger than the disk already on that tower.
 * <p>
 * NOTE: This exception extends RuntimeException because it will only be
 * thrown if the user violates the rules of Towers of Hanoi, which a
 * correct algorithm will never do.  (But if I do violate those rules,
 * I want to know about it immediatedly; hence the reason for having an
 * exception at all.)
 * <p>
 * Also, only by extending  RuntimeException can Tower's push override 
 * Stack's push and still throw an exception.
 *
 * @author Zach Tomaszewski
 * @version 15 Sept 2004
 */
public class DiskTooLargeException extends RuntimeException {

  public DiskTooLargeException() {
    super();
  }

  public DiskTooLargeException(String message) {
    super(message);
  }
}



//Bowl.java

/**
 * A Bowl for a BananaSplit simulation, this ADT acts like a Tower.
 *
 * @author Zach Tomaszewski
 * @version 22 Sept 2004
 */
public class Bowl extends Tower {

  /**
   * Returns a String representation of this Bowl,
   * printed horizontally and ending in a newline.
   */
  public String toString() {
    String repres = "Bowl: ";
    if (this.empty()) {
      repres += "(empty)";
    }else {
      for (int i = 0; i < this.size(); i++) {
        repres += this.get(i).toString();
      }
    }
    repres += "\n";
    return repres;
  }
}


//Ingredient.java

/**
 * Acts like a Disk in a dessert version of the TowersOfHanoi.
 *
 * @author Zach Tomaszewski
 * @version 22 Sept 2004
 */
 public class Ingredient extends Disk {
 
   /**
    * Constructor.
    * All Ingredients must have a size.  A larger value means a larger size.
    */
   public Ingredient (int size) {
     super(size);
   }

  /**
   * Returns a string representation of this object
   */
  public String toString() {
    String repres = "";
    switch (size) {
      case 1: 
        repres = "[cherry]";
        break;
      case 2: 
        repres = "[whipped cream]";
        break;
      case 3: 
        repres = "[pineapples]";
        break;
      case 4: 
        repres = "[bananas]";
        break;
      case 5: 
        repres = "[ice cream]";
        break;
      default:
        repres = "[Ingredient (" + size + ")]";
        break;
    }
    return repres;
        
  }
  
}
 
 
//BananaSplit.java

/**
 * A dessert-like problem based on the Towers of Hanoi
 */
public class BananaSplit extends TowersOfHanoi {

  /**
   * Constructor.
   * Sets up scenario with 5 Ingredients in the first Bowl.
   */
  public BananaSplit (){
    //create the bowls
    for (int i = 0; i < NUM_OF_TOWERS; i++) {
      towers[i] = new Bowl();
    }
    //setup the first bowl
    for (int i = 5; i > 0; i--){
      towers[0].push(new Ingredient(i));
    }
  }
   
  /**
   * Runs a scenario of 5 Ingredients and 3 bowls.
   */
  public static void main(String[] args){
    TowersOfHanoi toh = new BananaSplit();
    System.out.println("INITIAL STATE: \n" + toh);
    toh.solve(true);
    System.out.println("---------------------------");         
    System.out.println("FINAL STATE: \n" + toh);
  }

}