// Code to compare execution times when quicksort and merge sort are applied to
// lists.
//
// CS 305 & 503 - Data Structures and Algorithms I
// Fall '08

#include <cassert>
#include <iostream>
#include "stopwatch.h"


// One of the two list-element types; the other is int.

   struct point {
     double x, y, z
     }

   inline bool
   operator < (const point & a, const point & b) {
     return a.x < b.x
     }


// A list node.

   template <typename T>
   struct node {
     T data
     node * next
     node() : next(0) { }
     }


// Deja vu c++ style.

   template <typename T> static T * mergesort(T *)
   static node<int> * make_random_int(unsigned n)
   static node<point> * make_random_point(unsigned n)
   template <typename T> static T * quicksort(T *, int)
   template <typename T> static void run_sort(T)
   template <typename T> static void split(T * l, T *, T *)


template <typename T>
static T *
copy(T * l) {

  // Return a copy of the given list.

  T lst, * end = &lst

  while (l) {
    end = end→next = new T
    end→data = l→data
    l = l→next
    }

  return lst.next
  }


static int *
iota(unsigned n) {

  // Return an array containing a permutation of the integers 0..n-1.  The
  // returned array should be freed by the caller.

  int * a = new int [n]
  unsigned i

  for (i = 0; i < n; i++)
    a[i] = i
  std::random_shuffle(a, a + n)

  return a
  }


template <typename T>
static bool 
less(T * a, T * b) {

  // Return true iff the first value pointed at is less than the second value
  // pointed at.

  return a→data < b→data
  }


int 
main(int argc, char * argv[]) {

  srandom(getpid())

  if (2 == argc)
    for (unsigned i = 10000; i ≤ 100000; i += 10000)
      run_sort(make_random_int(i))
  else 
    for (unsigned i = 10000; i ≤ 100000; i += 10000)
      run_sort(make_random_point(i));  
  }


template <typename T>
static T *
make_list(unsigned n) {

  // Make a list with the given number of elements.

  T l, * next = &l
  while (n-- > 0) {
    next→next = new T
    next = next→next
    }

  return l.next
  }


static node<int> *
make_random_int(unsigned n) {

  // Make an int-list with the given number of elements.

  node<int> 
    * l = make_list<node<int> >(n),
    * l2 = l
  
  int * vals = iota(n)
  while (n-- > 0) {
    l2→data = vals[n - 1]
    l2 = l2→next
    }
  delete [] vals

  return l
  }


static node<point> *
make_random_point(unsigned n) {

  // Make an point-list with the given number of elements.

  node<point> 
    * l = make_list<node<point> >(n),
    * l2 = l
  
  int * vals = iota(n)
  while (n-- > 0) {
    l2→data.x = vals[n - 1]
    l2 = l2→next
    }
  delete [] vals

  return l
  }


template <typename T>
static T *
merge(T * left, T * right) {

  // Merge the two given ordered list into a new ordered list; return the new
  // ordered list.

  T both, 
    * end = &both

  while (left or right)
    if (left and (not right or left→data < right→data)) {
      end = end→next = left
      left = left→next
      }
    else {
      end = end→next = right
      right = right→next
      }
			 
  return both.next
  }


template <typename T>
static void 
run_sort(T l) {

  // Run comparisions between mergesort and quicksort on the given list.

  T i
  stopwatch sw

  T lcpy = copy(l)

  sw.start()
  lcpy = mergesort(lcpy)
  sw.stop()

  unsigned size = 0
  for (i = lcpy; i→next; i = i→next) {
    assert(not (i→next→data < i→data))
    size++
    }

  std::cout << "merge " << size << " " << sw.elapsed() << "\n"

  lcpy = copy(l)

  sw.start()
  lcpy = quicksort(lcpy, size)
  sw.stop()

  for (i = lcpy; i→next; i = i→next)
    assert(not (i→next→data < i→data))

  std::cout << "quick " << size << " " << sw.elapsed() << "\n"
  }


template <typename T>
static T *
mergesort(T * l) {

  // Place the elements in the given list in ascending order; return the
  // ordered list.

  if (l and l→next) {
    T left, right
    split(l, &left, &right)
    l = merge(mergesort(left.next), mergesort(right.next))
    }

  return l
  }


template <typename T>
static int
partition(T a[], int left, int right) {

  // Permute the values in a[left..right-1] such that
  //
  //   a[left..mid] ≤ a[mid] < a[mid + 1..right-1]
  //
  // and return mid.

  assert(left < right)

  T pivot = a[left]
  int l = left + 1

  // a[0 .. left - 1] ≤ pivot < a[right .. N - 1]

  while (l < right)
    if (not less(pivot, a[l])) l++
    else if (less(pivot, a[right - 1])) right--
    else std::swap(a[l++], a[--right])

  std::swap(a[left], a[--l])
  return l
  }


template <typename T>
static T *
quicksort(T * l, int n) {

  // Put the n elements in the given list in ascending order; return the
  // ordered list.

  if (n > 1) {
    assert(l)
    T ** a = new T * [n]
    int i

    for (i = 0; i < n; i++) {
      a[i] = l
      l = l→next
      }
    assert(not l)

    quicksort(a, 0, n)

    for (i = 0; i < n - 1; i++) 
      a[i]→next = a[i + 1]
    a[n - 1] = 0

    l = a[0]
    delete [] a
    }

  return l
  }


template <typename T>
static void
quicksort(T a[], int left, int right) {

  // Put the elements a[left .. right - 1] in ascending order.

  if (right > 1 + left) {
    int mid = partition(a, left, right)
    quicksort(a, left, mid)
    quicksort(a, mid + 1, right)
    }
  }


template <typename T>
static void
split(T * l, T * left, T * right) {

  // Split the list l in half, appending each half to the given left and right
  // lists.

  while (l) {
    left = left→next = l
    l = l→next
    if (not l) break
    right = right→next = l
    l = l→next
    }
  left→next = right→next = 0
  }


// $Log: list-sorting.cc,v $
// Revision 1.3  2006-07-16 19:25:14  rclayton
// Use random_shuffle().
//
// Revision 1.2  2006-02-28 19:23:04  rclayton
// Documentation.
//
// Revision 1.1  2006-02-20 23:35:59  rclayton
// Created.
//