/* ListSorts.java */

import list.*;

public class ListSorts {

  private final static int SORTSIZE = 1000;

  /**
   *  makeQueueOfQueues() makes a queue of queues, each containing one element
   *  of q.  Upon completion of this method, q is empty.
   *  @param q is a LinkedQueue of objects.
   *  @return a LinkedQueue containing LinkedQueue objects, each of which
   *    contains one object from q.
   **/
  public static LinkedQueue makeQueueOfQueues(LinkedQueue q) {
    // Replace the following line with your solution.
    return null;
  }

  /**
   *  mergeSortedQueues() merges two sorted queues into a third.  On completion
   *  of this method, q1 and q2 are empty, and their elements have been merged
   *  into the returned queue.
   *  @param q1 is LinkedQueue of Comparable objects, sorted from smallest 
   *    to largest.
   *  @param q2 is LinkedQueue of Comparable objects, sorted from smallest 
   *    to largest.
   *  @return a LinkedQueue containing all the Comparable objects from q1 
   *   and q2 (and nothing else), sorted from smallest to largest.
   **/
  public static LinkedQueue mergeSortedQueues(LinkedQueue q1, LinkedQueue q2) {
    // Replace the following line with your solution.
    return null;
  }

  /**
   *  circularShift performs a circular shift consituting shiftAmount dequeues
   *  and enqueues.  For example, if q is [ 3 9 6 2 ] and shiftAmount is 2,
   *  q becomes [ 6 2 3 9 ].  If q is empty, it is not changed.
   *  @param q is a LinkedQueue.
   *  @param shiftAmount is an int representing the number of shifts to be
   *    performed.
   **/
  public static void circularShift(LinkedQueue q, int shiftAmount) {
    // Your solution here.
  }

  /**
   *  partition() partitions qIn using the pivot element.  On completion of
   *  this method, qIn is empty, and its elements have been moved to qSmall,
   *  qEquals, and qLarge, according to their relationship to the pivot.
   *  @param qIn is a LinkedQueue of Comparable objects.
   *  @param pivot is a Comparable element used for partitioning.
   *  @param qSmall is a LinkedQueue, in which all elements less than pivot
   *    will be enqueued.
   *  @param qEquals is a LinkedQueue, in which all elements equal to the pivot
   *    will be enqueued.
   *  @param qLarge is a LinkedQueue, in which all elements greater than pivot
   *    will be enqueued.  
   **/   
  public static void partition(LinkedQueue qIn, Comparable pivot, 
                               LinkedQueue qSmall, LinkedQueue qEquals, 
                               LinkedQueue qLarge) {
    // Your solution here.
  }

  /**
   *  mergeSort() sorts q from smallest to largest using merge sort.
   *  @param q is a LinkedQueue of Comparable objects.
   **/
  public static void mergeSort(LinkedQueue q) {
    // Your solution here.
  }

  /**
   *  quickSort() sorts q from smallest to largest using quicksort.
   *  @param q is a LinkedQueue of Comparable objects.
   **/
  public static void quickSort(LinkedQueue q) {
    // Your solution here.
  }

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

  /**
   *  printQueue() prints the queue q on the standard output.
   *  @param q is a LinkedQueue.  q's elements are printed using their toString
   *    method.
   **/
  public static void printQueue(LinkedQueue q) {
    System.out.print("[ ");
    try {
      for (int i = 0; i < q.size(); i++) {
	System.out.print(q.front() + " ");
	q.enqueue(q.dequeue());
      }
    } catch (QueueEmptyException uf) {
      System.err.println("Error:  attempt to dequeue from empty queue.");
    }
    System.out.println("]");
  }

  /**
   *  main() performs some tests on merge sort and quicksort.  Feel free to add
   *  more tests of your own to make sure your algorithms works on boundary
   *  cases.  Your test code will not be graded.
   **/
  public static void main(String [] args) {

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

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

    /* Remove these comments for Part III.
    Timer stopWatch = new Timer();
    q = makeRandom(SORTSIZE);
    stopWatch.start();
    mergeSort(q);
    stopWatch.stop();
    System.out.println("Merge sort time, " + SORTSIZE + " Integers:  " +
                       stopWatch.elapsed() + " msec.");

    stopWatch.reset();
    q = makeRandom(SORTSIZE);
    stopWatch.start();
    quickSort(q);
    stopWatch.stop();
    System.out.println("Quick sort time, " + SORTSIZE + " Integers:  " +
                       stopWatch.elapsed() + " msec.");
    */
  }

}