/* ListSorts.java */

import DataStructures.*;
import Supporting.*;
import Exceptions.*;
import Timer.*;

public class ListSorts {

  /** Performs some tests on merge sort and quicksort.  Feel free
   *   to add more tests of your own to make sure your algorithms
   *   work on various boundary cases.  This code will not be graded.
   */
  public static void main (String [] argv) {

    GoodQueue q = makeRandom(10);
    printQueue(q);
    mergeSort(q);
    printQueue(q);

    q = makeRandom(10);
    printQueue(q);
    quickSort(q);
    printQueue(q);

    /* Remove these comments for part 3. 
    Timer stopWatch = new Timer();
    q = makeRandom(1000);
    stopWatch.start();
    mergeSort(q);
    stopWatch.stop();
    System.out.println("time for merge sort: " + stopWatch.elapsed());

    stopWatch.reset();
    q = makeRandom(1000);
    stopWatch.start();
    quickSort(q);
    stopWatch.stop();
    System.out.println("time for quick sort: " + stopWatch.elapsed());
    */
  }

  /** Sorts q from smallest to largest using a merge sort algorithm.
   *  @param q is a GoodQueue of Comparable objects.  
   */
  public static void mergeSort(GoodQueue q) {
  }

  /** Sorts q from smallest to largest using a quicksort algorithm.
   *  @param q is a GoodQueue of Comparable objects.  
   */
  public static void quickSort(GoodQueue q) {
  }

  /** Partitions qIn using the divider element; qIn will be empty after
   *  this method returns.  
   *  @qIn is a GoodQueue of Comparable objects.
   *  @param divider is a Comparable element used for partitioning.
   *  @qSmall is a GoodQueue of Objects to which all elements less than
   *   divider will be enqueued.
   *  @qLarge is a GoodQueue of Objects to which all elements greater than
   *   that divider will be enqueued.  
   *  @qEquals is a GoodQueue of Objects to which all elements equals
   *   the divider will be enqueued.
   */   
  public static void partition (GoodQueue qIn, Comparable divider, 
				GoodQueue qSmall, GoodQueue qEquals, 
				GoodQueue qLarge) {
  }

  /** Merge two sorted queues into a third.
   *  @param q1 is GoodQueue of Comparable objects, sorted from smallest 
   *    to largest.
   *  @param q2 is GoodQueue of Comparable objects, sorted from smallest 
   *    to largest.
   *  @return a GoodQueue containing all the Comparable objects from q1 
   *   and q2 (and nothing else), sorted from smallest to largest.
   *  q1 and q2 will be empty when this method returns.
   */
  public static GoodQueue mergeSortedQueues (GoodQueue q1, GoodQueue q2) {
    return null; // remove this line
  }

  /** Make a queue of queues, each containing 1 element of q.
   *  @param q is a GoodQueue of any type of Object; it will be 
   *    empty after this method returns.
   *  @return a GoodQueue containing GoodQueue objects, each of which 
   *    contains one of the objects from q.
   */
  public static GoodQueue makeQueueOfQueues(GoodQueue q) {
    return null;  // remove this line
  }

  /** Performs a circular shift by shiftAmount.  For example, if
   *   we are given the queue [ 3 9 6 2 ] and a shiftAmount of 2,
   *   after running this method the queue will be [ 6 2 3 9 ].
   *   @param q is a GoodQueue of Objects; if empty, this method does
   *    nothing to the queue.
   *   @param shiftAmount is an int representing the number of shifts
   *    to be performed.
   */
  public static void circularShift(GoodQueue q, int shiftAmount) {
  }

  /** Builds a GoodQueue of the indicated size containing MyInteger elements.
   *  The elements are randomly chosen between 0 and size.
   *  @param size is the size of the resulting GoodQueue.
   */
  public static GoodQueue makeRandom(int size) {
    GoodQueue q = new GoodQueue();
    for (int i = 0; i < size; i++) {
      q.enqueue(new MyInteger((int) (size * Math.random())));
    }
    return q;
  }

  /** Print the queue q on the standard output.
   *  @param q is a GoodQueue of objects.  The toString method on 
   *   q's elements will be used for printing.
   */
  public static void printQueue (GoodQueue q) {
    System.out.print("[ ");
    try {
      for (int i = 0; i < q.length(); i++) {
	System.out.print(q.getFront() + " ");
	q.enqueue(q.dequeue());
      }
    } catch (Underflow uf) {
      System.err.println("Error in program -- dequeued from empty queue");
    }
    System.out.println("]");
  }
}