import net.datastructures.Sort;
import net.datastructures.List;
import net.datastructures.NodeList;
import java.util.Comparator;
import net.datastructures.DefaultComparator;

/* 
 * This class provides an example of how to use the various sorting
 * algorithms provided by the net.datastructures Package.  The example
 * consists of initialization, execution, and output.  Two arrays and
 * two lists are created, each storing the same randomly generated
 * sequence of integers.  Each of the four sorting methods is called
 * on either an array or list.  Finally, the four sorted sequences are
 * printed.
 */

public class SortExample {

  public static void main(String[] args) {

    /* INITIALIZATION */

    // construct the sort object
    Sort sortObj = new Sort();
    
    // generate a data set to be sorted, and store it in an array
    int numElements = 10; 
    Object[] data1 = new Object[numElements];
    for(int i = 0; i < numElements; i++)
      data1[i] = new Integer(randomNumber(-100,100));
    
    Object[] data2 = new Object[numElements];
    // this simply copies the contents of one array to another
    System.arraycopy(data1,0,data2,0,numElements);

    List data3 = new NodeList();
    List data4 = new NodeList();

    // copy the contents of the arrays into these lists
    for(int i = 0; i < numElements; i++) {
      data3.insertLast(data1[i]);
      data4.insertLast(data2[i]);
    }
    
    // initialize a default comparator
    Comparator c = new DefaultComparator();

    // print out the unsorted sequence of numbers

    // since all four data structures store the same sequence, print
    // just one of them
    System.out.println("The Input Sequence:");
    System.out.println(data3);
    System.out.println();

    /* SORTING THE DATA */

    // iterative merge-sort
    sortObj.mergeSort(data1,c);

    // in-place quick-sort
    sortObj.quickSort(data2,c);

    // recursive merge-sort
    sortObj.mergeSort(data3,c);
    
    // recursive quick-sort
    sortObj.quickSort(data4,c);
    
    /* PRINTING THE RESULTS */

    System.out.println("RESULTS:\n");

    // java.util.Arrays.asList is a helper method that converts an
    // array to a java.util.List, for ease of printing.

    System.out.println("Iterative merge-sort: " + 
		       java.util.Arrays.asList(data1));
    System.out.println("In-place quick-sort:  " +
		       java.util.Arrays.asList(data2));
    System.out.println("Recursive merge-sort: " + 
		       data3);
    System.out.println("Recursive quick-sort: " +
		       data4);
    
  }
 
  // helper function to return a random number in the interval
  // [low,high] (inclusive)
  private static int randomNumber(int high, int low) {
    return low + (int)(Math.random()*(high-low+1));
  }
}