// Code to compare execution times when quicksort and merge sort are applied to
// lists.
//
// CS 503 - Advanced Programming I
// Spring '06

#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.
//


syntax highlighted by Code2HTML, v. 0.9.1