/*

  Csu213, Wednesday 4/04/07

  Now for Big-Oh review and a few sorting algorithms

  Last time we reviewed a little big-O notation.  For homework you've been working
    on implementing a few different sorting algorithms.  To show the (big) difference
    between the running times of O(n), O(n log n), and O(n^2) functions we'll
    time the sorting of large lists using Insertion Sort (O(n^2)) Quick Sort 
    (O(n log n)) and Radix Sort (O(n)) [** Wikipedia is your friend]

  And, of course, you'll get to see an implementation of a really fast sort, Radix
    Sort, and a pretty fast randomized sort, Quick Sort, which performs well on
    average.

*/

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Random;

// The classic Algorithms class for static method implementations
class Algs{
    // The swap we've seen in lab and in class (and in HW)
    static <X> void swap(ArrayList<X> list, int i, int j){
        list.set(i, list.set(j, list.get(i)));
    }

    // Basic insertion sort algorithm
    // Starting from the back, insert the current element into the 
    //   sorted 'rest' of the list. The last element is trivially sorted  
    static <X> void insertionSort(ArrayList<X> list, Comparator<X> comp){
        for(int i = list.size()-2; i >= 0; i--)
            insert(list, i, comp);
    }

    // Insert as described in clas... swap the given element into place
    //   in a sorted list starting at index (i+1)
    static <X> void insert(ArrayList<X> list, int i, Comparator<X> comp){
        while(i < list.size()-1 && comp.compare(list.get(i+1), list.get(i)) < 0){
            swap(list, i, i+1);
            i++;
        }
    }

    // Quick Sort algorithm... only has to do with partitioning a section of
    //   the ArrayList into lessThan and greaterThan parts then recuring. We
    //   assume that a random pick will give us a decent pivot element.
    static <X> void quickSort(ArrayList<X> list, Comparator<X> comp){
        partition(list, comp, 0, list.size());
    }

    /* 
       Partition elements [start..end) of the list based on a randomly chosen
         pivot point. We keep track of to 'regions', the lessThan, and greaterThan
         regions are created, then we swap the pivot to it's right place in the
         ArrayList.  Note that the 'end' is exclusive, not inclusive.
    */
    static <X> void partition(ArrayList<X> list, Comparator<X> comp,
                              int start, int end){
        // Only one element... it's already sorted
        if(start >= end)return;

        // Random pivot, and starting indexes for the regions
        int pivot = randInt(start, end),
            less = start+1,
            greater = less;

        // Move the pivot to the front of the ArrayList
        swap(list, start, pivot);

        // Cache the pivot...
        X target = list.get(start);

        // While the regions are not the whole ArrayList
        while(greater < end){
            // If the current element is less than the pivot then
            //   it belongs in the 'left' region.  So we may need
            //   to swap it there to mantain the regions
            if(comp.compare(list.get(greater), target) < 0){
                if(less != greater)
                    swap(list, less, greater);
                // The 'lessThan' region has gotten bigger
                less++;
            }
            // The greater region always moves back since the lessThan
            //   region is in front of it.
            greater++;
        }
        // Swap the pivot back into a good spot... maintaining our regions
        swap(list, start, less-1);
        partition(list, comp, start, less-1);
        partition(list, comp, less, end);
    }

    // Return a nice random integer between: [low, high)
    static Integer randInt(int low, int high){ 
        return new Random().nextInt(high-low)+low; 
    }

    // Radix Sort Implementation
    /* Sorts numerical type data by sorting on each digit and combining
         results.  It's a little messy, but it can be better if we used
         other Java features, but this is done with what you know so far

       NOTE: This is *not* a comparison based sort, which is why it can
         be faster than all the others.
    */

    // We could make this faster by doing a few 'bit twiddles' instead of using
    //   Base 10 and multiplications, we could use a power of 2 with shifts
    static final int BASE = 10;
    // Max number of digits to sort on
    static final int NUM_DIGITS = 6;

    // radixSort: Doesn't use mutation on the list passed in
    static ArrayList<Integer> radixSort(ArrayList<Integer> list){
        ArrayList<ArrayList<Integer>> newbuckets, oldbuckets = null;
        newbuckets = initBuckets();

        // Initialize the buckets with the least signif. digit
        //   ie. the 'ones' column
        for(int i = 0; i < list.size(); i++){
            Integer elem = list.get(i);
            int digit = getDigit(elem, 0);
            newbuckets.get(digit).add(elem);
        }
        // For each digit after the 'ones' we put them into new
        //   buckets, being sure to keep the oreder of the buckets
        //   as we pull them out of the old one
        for(int i = 1; i < NUM_DIGITS; i++){
            oldbuckets = newbuckets;
            newbuckets = initBuckets();
            for(int j = 0; j < BASE; j++){
                ArrayList<Integer> curr = oldbuckets.get(j);
                for(int k = 0; k < curr.size(); k++){
                    Integer elem = curr.get(k);
                    int digit = getDigit(elem, i);
                    newbuckets.get(digit).add(elem);
                }
            }
        }
        // Just convert the nested lists into a single list, inorder
        list = new ArrayList<Integer>();
        for(int j = 0; j < BASE; j++){
            ArrayList<Integer> curr = oldbuckets.get(j);
            for(int k = 0; k < curr.size(); k++)
                list.add(curr.get(k));
        }
        return list;
    }
    // Helper Functions...
    // Get digit number 'which' from 'num', Examples:
    //    getDigit(245, 1) = 4
    //    getDigit(245, 2) = 2
    //    getDigit(245, 3) = 0
    static int getDigit(int num, int which){ 
        if(which == 0)return num % BASE;
        return (num / (which*BASE)) % BASE; 
    }
    // Initializes a (List-of (List-of Integers)) that we will use to store
    //   our numbers while sorting
    static ArrayList<ArrayList<Integer>> initBuckets(){
        ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
        for(int i = 0; i < BASE; i++)
            ret.add(new ArrayList<Integer>());
        return ret;
    }
}

// Simple Integer Comparator
class IntComp implements Comparator<Integer>{
    public int compare(Integer a, Integer b){ return a.compareTo(b); }
}

// Timing class to wrap Java's System timer calls
class Timing{
    long start;

    // Sets the starting time
    Timing(){ reset(); }
    // Current time in milliseconds
    static long current(){ return  System.currentTimeMillis(); }
    // Reset the starting time
    void reset(){ start = current(); }
    // Give the time diference
    long diff(){ return current()-start; }
    // Simple toString()
    public String toString(){ return " Timing("+diff()+")"; }
}

// Abstract a little, so I can write my Test/Print functions without
//   relying one a specific sorting algorithm
abstract class Sorter{
    String name;
    Sorter(String n){ name = n; }
    abstract ArrayList<Integer> sort(ArrayList<Integer> list, Comparator<Integer> comp);
}

// Wraps Algorithm's insertionSort
class Insert extends Sorter{
    Insert(){ super("insert"); }
    ArrayList<Integer> sort(ArrayList<Integer> list, Comparator<Integer> comp){ 
        Algs.insertionSort(list, comp);
        return list;
    }
}

// Wraps Algorithm's quickSort
class Quick extends Sorter{
    Quick(){ super("quick"); }
    ArrayList<Integer> sort(ArrayList<Integer> list, Comparator<Integer> comp){
        Algs.quickSort(list, comp);
        return list;
    }
}

// Wraps Algorithm's RadixSort
class Radix extends Sorter{
    Radix(){ super("radix"); }
    ArrayList<Integer> sort(ArrayList<Integer> list, Comparator<Integer> comp){
        return Algs.radixSort(list);
    }
}

// Tests and Examples
public class notes_4_04_07{
    // Generate a random list of integers of given size using max for a bound
    //   on the actual numbers generated
    static ArrayList<Integer> fillData(int size, int max){
        ArrayList<Integer> list = new ArrayList<Integer>(size);
        for(int i = 0; i < size; i++)
            list.add(randomInt(max));
        return list;
    }

    // Just a wrapper function for Algs randInt(...)
    static Integer randomInt(int top){ return new Integer(Algs.randInt(0, top)); }
    // Wrapper for System.out.println
    public static void println(String s){ print(s+'\n'); }
    // Wrapper for System.out.print
    public static void print(String s){ System.out.print(s); }

    // Normal main(...) for running Tests
    public static void main(String[] args) {
        // Number of times to run our timings
        //   'final' means we can't change (mutate) these ints
        final int loops = 5, runs = 100;

        // Current size of the lists being sorted
        int size = 64;

        // Easy visual sort tests
        simpleTest(new Insert());
        simpleTest(new Quick());
        simpleTest(new Radix());

        // Print out the Timings for each of the sorts in a kind of table
        println("\nTimings:");
        println(" N\tinsert\tquick\tradix");
        for(int j = 0; j < loops; j++){
            print(" "+size+"\t  ");
            print(timeSort(new Insert(), runs, size)+"\t  ");
            print(timeSort(new Quick(), runs, size)+"\t  ");
            println(""+timeSort(new Radix(), runs, size));
            size *= 2;
        }

    }

    // Abstract Test methods incase I add more Sorters
    // Visual check of the sorter methods
    static void simpleTest(Sorter sorter){        
        ArrayList<Integer> list = fillData(10, 40);
        println("          Start\t: "+list);
        list = sorter.sort(list, new IntComp());
        println("   Sort("+sorter.name+")\t: "+list);
    }

    // Timing of a number of runs of a sorter method
    static long timeSort(Sorter sorter, int runs, int size){
        ArrayList<Integer> list;
        long total = 0;
        Timing time;

        for(int i = 0; i < runs; i++){
            list = fillData(size, 1000);
            time = new Timing();
            sorter.sort(list, new IntComp());
            total += time.diff();
        }
        return total;
    }
}


/*
  When you run the above code, you should notice that the Quick Sort
    starts to win pretty big after a while and Radix wins even more. This
    has to do with the *order* of running times of the three sort
    algorithms.

  As discussed, Insertion Sort is O(n^2) and Quick Sort is O(N log N)
    on average, and Radix is O(n).  The reason I keep saying 'on average' 
    for Quick Sort is because it actually depends on the order of the list
    before sorting.  If you hand the method an already sorted list, then
    the partition method would divide the array into an empty region, and
    a full region which would make the algorithm run in O(n^2) time.

  Here's a typical run on my machine of the above code... Note the difference
    that Quick and Radix Sorts make on these randomly created ArrayLists

              Start : [5, 12, 13, 3, 37, 34, 20, 4, 16, 4]
       Sort(insert) : [3, 4, 4, 5, 12, 13, 16, 20, 34, 37]
              Start : [31, 21, 37, 29, 8, 9, 30, 21, 14, 30]
       Sort(quick)  : [8, 9, 14, 21, 21, 29, 30, 30, 31, 37]
              Start : [33, 31, 37, 18, 3, 38, 34, 32, 11, 17]
       Sort(radix)  : [3, 11, 17, 18, 31, 32, 33, 34, 37, 38]

        Timings:
         N      insert  quick   radix
         64       72      53      54
         128      176     57      41
         256      677     144     84
         512      2746    320     149
         1024     12496   682     307
         2048     45721   1513    621
 */


/*
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
  Graph Algorithms

  There will be more on these in tomrorrow's notes but we will discuss strategies
    for representing general graphs. Below is a simple Graph:

    A --- B --- D 
     \   /     /
      \ /     /
       C --- E

  As a definition of a Graph, we have a set of Vertices (or Nodes) and Edges, where
    an edge is usually a Pair of Vertices with an associated Weight (with some meaning).
    Usually the Weight is some cost of 'traveling' down that portion of the Graph. This
    could be actual distance, or just the dollar cost of a flight.

  If we say that the above graph has Weights of 1 then our abstract representation
    would be something like:
      V = {A,B,C,D,E}
      E = {(A,B,1),(A,C,1),
           (B,A,1),(B,C,1),(B,D,1),
           (C,A,1),(C,B,1)(C,E,1),
           (D,B,1),(D,E,1),
           (E,C,1)(E,D,1)}

  How do we translate this abstract definition into Java classes or Scheme structs? Well
    there are three different ways it is usually done.

  1) If we translate it directly, then we get a set representation which is a little
       inefficient to write algorithms for, but its simple to discuss.

  2) We could use an Adjacency List representation where we have a List (or HashMap) of 
       Vertices, and each Vertex has a list of (Vertex, Weight) pairs. 
     That would look like:

        L = ((A, ((B,1),(C,1)))
             (B, ((A,1),(C,1),(D,1))),
             (C, ((A,1),(B,1),(E,1))),
             (D, ((B,1),(E,1))),
             (E, ((C,1),(D,1))))

  3) There are some algorithms which benefit from a different representation known as an
       Adjacency Matrix.  Where each row/column contains the weight of the edge between
       the corresponding Vertices, infinity (or some marker) otherwise. 
     If we use '-' for 'no-edge', then that would look like:

         A  B  C  D  E
       A -  1  1  -  -
       B 1  -  1  1  -
       C 1  1  -  -  1
       D -  1  -  -  1
       E -  -  1  1  -

  We can translate these into actual datadefinitions to be used in actual algorithms, but
    It's better to make an interface to design our algorithms, then we can make the
    implementation of our datastructure(s) more efficient later.

*/