/*****************************************************************************
 * Author: Shawn Stoffer (Though derived from class notes from CS461, 
 *                        taught by Dr. Moret of the University of New Mexico, 
 *                        Fall 99)
 *
 * Description : This program implements the SillySort algorithm, which is an
 *               algorithm to sort a list of numbers.  So by now you are
 *               saying, "so why is this important?  I have seen hundreds of 
 *               sorting algorithms before, why is this any different?"  Well
 *               That question can be answered by this: This algorithm is not
 *               a good sorting algorithm, and that is its appeal.  This 
 *               algorithm is not only not good, but it is in fact bad, and 
 *               not even just bad, but REALLY BAD.  This algorithm sorts a 
 *               list in exponential time...which is actually pretty difficult,
 *               because even a bad normal sorting algorithm can sort in better
 *               than exponential time.  This algorithm sorts in O(n^lg(n))
 *               time.  How does it possibly perform this badly?  The secret is
 *               in recursion.  The algorithm uses the divide and conquer 
 *               method (splits the array into two pieces and then recurses on
 *               both pieces) to find the smallest number in the array.  It
 *               then puts this number at the beginning of the array, and then
 *               recurses on the array minus the first element.  
 *
 * Warning:      This code is heavily commented, and as I am not sure who 
 *               just might be reading this code, it is commented as though 
 *               for a beginner to the language or programming in general.
 ****************************************************************************/

/* 
 * This is required for use of the C++ standard input/output functionality, 
 * the iostreams.  
 */
#include <iostream.h>

/* 
 * We are using this header for clock(), which returns the number of
 * milliseconds since it was last called.
 */
#include <time.h>

/* 
 * This will give us a growable array, so that the input can be an array of 
 * any size, without any program specific limitations.
 */
#include "int_table.h"

/* This little macro is just so that we can keep to the algorithm description.*/
/* The macro is written so that it can be used just as though it were a
 * function, with one small caveat, it does not, and cannot return a value.  
 *   One way to make it even more like a function would be to append a ,0 to 
 * the end, making the line look like:
   #define swap(x, y) { int temp; temp = x; x = y; y = temp; }, 0
 * what this would do is make the entire expression 0, as the ',' operator 
 * will always evaluate all expressions joined by it, but will return only the 
 * rightmost expression's value.  Though this is an aside, as it would not be
 * necessary in the uses of this particular program.
 */
#define swap(x, y) { int temp; temp = x; x = y; y = temp; }

/* 
 * Eww...bad practice, but globals were a better choice than adding three 
 * params to each function.  These are mainly in order to produce statistics 
 * for the programs and if you were really using this program (Why would you
 * EVER do that??) than you would want to remove these anyway.
 */
int num_sorted = 0;
int beginning_time = 0;
int ending_time = 0;

/* 
 * One note...we could probably make this algorithm even worse by passing an 
 * object that was an integer array in by value instead of by reference...
 * but why tempt fate?
 */
int_table & SillySort(int i, int j, int_table & B) {
  /* 
   * Set up the base case for the recursion, if i >= j, then we have reached
   * last element of the array, and no further processing is needed...
   */
  if (i < j) {
    /* find the middle of the array */
    int m = (i+j)/2;
    /* 
     * use this function (recursively) to find put the minimum elements of 
     * each half into the first elements of each half
     */
    SillySort(i, m, B);
    SillySort(m+1, j, B);
    /* 
     * Choose the smallest element of the two halves, and put that element in
     * the first position
     */
    if (B[i] >= B[m+1]) 
      swap(B[i],B[m+1]);
    /* Now call this function on the rest of the array. */
    SillySort(i+1, j, B);
  }
  /* 
   * Amazingly enough, this sorting routine does sort the array, though, an
   * astute observer would notice that the first time through the array, both
   * halves are now sorted, and so, this function does alot of redundant work,
   * though it does not do a merge, intelligently, that is the third call to
   * SillySort, and so this is the error that makes this sorting algorithm so
   * bad.
   */
  { 
    int z = 0;
    /* See just how many elements are sorted... */
    for (int y = 1; y < j && B[z] < B[y]; y++, z++);
    /* if we have sorted the number that we set as the lower limit, then 
     * we should output the amount of time taken to sort this many elements.
     */
    if (z > num_sorted-1) {
      /* A note here is that, so we do not produce bad results, the first
       * time through the loop, we only set the clock.
       */
      if (z > num_sorted) {
        ending_time = clock();
        /* Considering the definition of clock(), that it returns the number
         * of milliseconds since its first call in the function, you may be 
         * concerned about the validity of this test, but recall, the first 
         * clock call will return 0, and so beginning_time starts at zero, 
         * and therefore, we have a valid test and report.
         */
        int diff = ending_time - beginning_time;
        num_sorted = z;
        printf("%d elements sorted..in %d milliseconds...\n", num_sorted, diff);
      }
      
      /* Here we set ending time again, because the printf and other operations
       * are not part of what we are timing...
       */
      ending_time = beginning_time = clock();
      /* 
       * one final note is that this block, the statistics block, effectively 
       * squares the running time of this algorithm, because of the fact that 
       * everytime that SillySort runs, this runs as well, and we run through
       * the entire array every time.  So this effectively says, 
       *   T(n) = 2T(n/2) + T(n-1) + n
       * Ewww...
       * The standard Silly Sort routine is:
       *   T(n) = 2T(n/2) + T(n-1) + 1
       */
    }
  }
  return B;
}

int main() {
  int_table SillySortArray;
  int tmp;

  cout << "Enter a list of space delimited numbers.  End them with a EOF \n"
       << "character, if you are on a UNIX xterm this is a ^D, if you are \n"
       << "feeding this program a file, the file is automatically terminated \n"
       << "by EOF.  Otherwise, consult your operating system, or software \n"
       << "documentation." << endl;


  /* 
   * The simplicity of this loop is largely thanks to the growable array, were
   * it otherwise, then we would have to realize that this would be more complex
   * as one would need to keep track of place in the array, and whether one 
   * was nearing the limit.  Though this flexibility does come at a price, 
   * the growable int_table is more expensive (timewise and spacewise) than
   * a simple array, though the cost is not significant, as the average case
   * running time is O(n) (the same as though it were a simple array, though
   * there is a pretty nasty constant hidden by the O(n)) and the space 
   * concerns are only two extra ints.
   */
  for (cin >> tmp; !cin.eof(); cin >> tmp)
    SillySortArray.add_elem(tmp);

  SillySort(0,SillySortArray.cur_size()-1, SillySortArray);

  SillySortArray.print_out();

  /* 
   * On an Ultra 10, Sun, workstation, this does not return any longer after 
   * 137 elements, and that take 3 days!  The sun Workstation that this was 
   * tested on was a 333MHz UltraSparc processor with 512 Mb of RAM.  
   */
  return 0;
}