#include <stdlib.h>
#include <stdio.h>

#include "List.h"       // Defines NodePtr, among other things

// Free-space list
NodePtr freeSpace = NULL;

NodePtr newNode ( int data, NodePtr nxt )
{
   NodePtr rtn;

   if ( freeSpace == NULL )
   {
      rtn = (NodePtr) calloc (1, sizeof(*rtn));
//**/  puts ( "New cell" );
   }
   else
   {
      rtn = freeSpace;
      freeSpace = freeSpace->next;
   }
   rtn->data = data;
   rtn->next = nxt;

   return rtn;
}

void recycle ( NodePtr node )
{
   node->next = freeSpace;
   freeSpace  = node;
}

NodePtr empty( NodePtr head )
{
//**/ puts ("Emptying out list");
   while ( head != NULL )
   {
      NodePtr nxt = head->next;
      recycle (head);
      head = nxt;
   }
   return head;
}

NodePtr insertBefore ( NodePtr cell, NodePtr node )
{
   if ( cell == NULL )
   {
      cell = node;
      cell->next = NULL;
   }
   else
   {
      // Swap contents of data fields to interchange identities
      int hold = cell->data;
      cell->data = node->data;
      node->data = hold;
      // Now do the list insertion
      node->next = cell->next;
      cell->next = node;
   }
   return cell;
}

NodePtr insertAfter ( NodePtr cell, NodePtr node )
{
   if ( cell == NULL )
   {
      cell = node;
      cell->next = NULL;
   }
   else
   {
      node->next = cell->next;
      cell->next = node;
   }
   return cell;
}

// Merge together two lists and return their head pointer
NodePtr mergeList ( NodePtr left, NodePtr right )
{
   NodePtr head, current, tail;

   if ( left == NULL )
      return right;
   if ( right == NULL )
      return left;

   if ( right->data > left->data )
   {  head = tail = left;  left = left->next;  }
   else
   {  head = tail = right;  right = right->next;  }

   while ( left != NULL && right != NULL )
   {
      if ( right->data > left->data )
      {  current = left;  left = left->next;  }
      else
      {  current = right; right = right->next;  }

      current->next = NULL;     // Not strictly needed.
      tail = tail->next = current;
   }

   tail->next = ( left != NULL ) ? left : right;

   return head;
}

// Traverse the list, printing out its contents.
void traverse ( NodePtr current )
{
   while ( current != NULL )
   {
      printf ( " %d", current->data);
      current = current->next;
   }
   printf (" --- finished\n");
}

/* Recursive merge sort
 *
 * Split the list in two.
 * Recursively mergeRecur those two lists
 * Merge the sorted result to generate the new list.
 */
NodePtr mergeRecur ( NodePtr head, int n )
{
   int k,
       ltN = n/2,
       rtN = n - ltN;
   NodePtr current = head,
           left = head,
           right;

   if ( n < 2 )
      return head;

   for ( k = 1; k < ltN; k++ )
      current = current->next;

   right = current->next;
   current->next = NULL;

//**/  fputs (stdout, "Left:   "); ListNode::traverse(left);
//**/  fputs (stdout, "Right:  "); ListNode::traverse(right);

   left  = mergeRecur ( left,  ltN );
   right = mergeRecur ( right, rtN );
   head  = mergeList ( left, right );
//**/  fputs (stdout, "Result: "); ListNode::traverse(head);
   return head;
}

/* Public entry point:  call the above function.  */
NodePtr mergeRecurse ( NodePtr head )
{
   int     size;
   NodePtr current = head;

// Preliminary:  find the size of the list
   for ( size = 0 ; current != NULL ; size++ )
      current = current->next;

// mergeRecur correctly handles the empty and one-node lists
   return mergeRecur ( head, size );
}

/* Iterative merge sort
 *
 * (A) Generate an array of length-one lists, ending with an extra
 *     NULL reference
 *
 * (B) Repeatedly merge pairs of lists and reinsert them into the front
 *     of the array.  If the current logical size of the array is odd,
 *     the last list will be merged with a null list to generate the
 *     last entry in the new array.  After each pass, a null reference
 *     is appended to the array in case its new logical size should be
 *     odd.
 *
 * (C) When the logical size of the array comes down to 1, we're finished.
 */
NodePtr mergeIter ( NodePtr head )
{
   int j,       // Destination index at the front
       k,       // Source index advanced by twos
       lim;     // Current logical size
   int size;
   NodePtr *work;
   NodePtr current = head;

// Preliminary:  find the size of the list
   for ( size = 0 ; current != NULL ; size++ )
      current = current->next;

   if ( size < 2 ) return head;

// Allow space for the appended null reference at the end.
   work = (NodePtr*) calloc ( size+1, sizeof(*work) );

// (A) Generate the initial array of size-one lists.
   for ( k = 0; k < size; k++ )
   {
      work[k] = head;
      head = head->next;
      work[k]->next = NULL;
   }
   work[k] = NULL;        // Extra null reference for odd cases

// (B) Repeatedly merge pairs of lists . . .
   for ( lim = size ; lim > 1; lim = (lim+1)/2 )
   {
      for ( j = k = 0; k < lim; j++, k += 2 )
         work[j] = mergeList ( work[k], work[k+1] );
      work[j] = NULL;     // Extra null reference for odd cases
   }

// (C) Return space to the heap and return the head pointer
   head = work[0];
   free (work);
   return head;
}

/* Natural merge sort
 *
 * (A) Generate an array of sorted lists separated out of the incoming
 *     list, ending with an extra null reference
 *
 * (B) Repeatedly merge pairs of lists and reinsert them into the front
 *     of the array.  If the current logical size of the array is odd,
 *     the last list will be merged with a null list to generate the
 *     last entry in the new array.  After each pass, a null reference
 *     is appended to the array in case its new logical size should be
 *     odd.
 *
 * (C) When the logical size of the array comes down to 1, we're finished.
 */
NodePtr mergeNatural ( NodePtr head )
{
   int j,       // Destination index at the front
       k,       // Source index advanced by twos
       lim;     // Current logical size
   int size;
   NodePtr *work;
   NodePtr current = head;

// Preliminary:  find the size of the list
   for ( size = 0 ; current != NULL ; size++ )
      current = current->next;

   if ( size < 2 ) return head;

// Worst-case situation:  reversed data with all list of size one.
// Allow space for the appended null reference at the end.
   work = (NodePtr*) calloc ( size+1, sizeof(*work) );

// (A) Generate the initial array of lists.
   for ( lim = 0; head != NULL; lim++ )
   {
      NodePtr parent = head, // Find the control break
              child;
      work[lim] = parent;
      child = parent->next;
      while ( child != NULL && parent->data <= child->data )
      {
         parent = child;
         child = parent->next;
      }
      head = child;
      parent->next = NULL;
   }
   work[lim] = NULL;         // Extra null reference for odd cases

// (B) Repeatedly merge pairs of lists . . .
   for ( ; lim > 1; lim = (lim+1)/2 )
   {
      for ( j = k = 0; k < lim; j++, k += 2 )
         work[j] = mergeList ( work[k], work[k+1] );
      work[j] = NULL;     // Extra null reference for odd cases
   }

// (C) Return space to the heap and return the head pointer
   head = work[0];
   free (work);
   return head;
}

/* QuickSort for lists
 *
 * (A) Generate an array of nodes
 *
 * (B) QuickSort that list
 *
 * (C) Traverse the ARRAY, connecting the nodes together
 */
void qSortOpt (NodePtr x[], int n);   // Defined below

NodePtr quickSort ( NodePtr head )
{
   int k,          // Loop variable
       size;       // List size
   NodePtr *work;  // Dynamic array of node pointers
   NodePtr current = head;

// Preliminary:  find the size of the list
   for ( size = 0 ; current != NULL ; size++ )
      current = current->next;

   if ( size < 2 ) return head;

   work = (NodePtr*) calloc ( size, sizeof(*work) );

// (A) Generate the initial array of node pointers.
   for ( k = 0; k < size; k++ )
   {
      work[k] = head;
      head = head->next;
//    work[k]->next = NULL;       // Not needed in this context
   }

// (B) QuickSort that array
   qSortOpt (work, size);

// (C) Traverse the ARRAY, connecting the nodes together
   head = work[0];
   work[size-1]->next = NULL;     // Tail of the new list
   for ( k = 1; k < size; k++ )
      work[k-1]->next = work[k];

// Return space to the heap and return the list
   free (work);
   return head;
}

/**
 * Public access to optimized quick sort
 */
void qSortO(int lo, int hi, NodePtr x[]);

void qSortOpt (NodePtr x[], int n)
{  qSortO(0, n-1, x);  }

/**
 * Optimized quick sort --- insertion sort for segments < CUTOFF
 */
// Preliminary definition and prototypes
#define CUTOFF 30
int  partition(int, int, NodePtr[]);
void inSort(int, int, NodePtr[]);

void qSortO(int lo, int hi, NodePtr x[])
{/* Basic QuickSort algorithm:

       1)  Check for exit condition:  if hi does not come after lo,
           there is nothing left to sort.
       2)  Let the "partition" function position one element to its
           exact position:  everything to its left belongs on the
           left, everything to its right belongs on its right.
       3)  QuickSort can then call itself to sort everything to the
           left as a sub-array.
       4)  Rather than recursively calling itself for the right
           sub-array, QuickSort can just update lo and stay within
           the current call, thus removing the tail recursion.

    Note:  Almost _all_ of the work for qSort is embedded in the
           partition routine.

    Optimization:  use insertion sort for small segments
*/
   int mid;

   while (lo < hi)   // while allows for removing tail recursion
   {  if ( hi-lo < CUTOFF )            // Small case: Insert Sort
      {  inSort(lo, hi, x); break;  }

      mid = partition(lo, hi, x);
      qSortO(lo, mid - 1, x);          // Recursive part for left
      lo = mid + 1;                    // "Tail" recursion on right
   } // end while
}

/**
 * Swap two elements in an array --- used by partition
 */
void swap (int lt, int rt, NodePtr x[])
{  NodePtr tmp = x[lt];  x[lt] = x[rt];  x[rt] = tmp;  }

/**
 * Partition method used by quick sort methods.
 */
int partition (int lo, int hi, NodePtr x[])
{/*Rearrange the x[] array so that a single element is properly
   positioned:  all elements to the left of the "partitioning
   element" (or pivot) belong on the left; all to the right
   belong on the right.  The position of this partitioning
   element is then the value of the partition function.

   This version of partition based on Thomas Naps, "Introduction
   to Data Structures and Algorithm Analysis"; the Median of Three
   improvement is taken from Robert Sedgewick, "Algorithms."
*/
// "Median of Three" --- middle element becomes the actual element.
//                       Insure that ends up in x[lo].
   int mid;
   NodePtr hold;

   if (lo >= hi) return hi;
   mid = (lo + hi) / 2;
// We wish to move the median -- b in "abc" -- to position lo
   if (x[lo]->data < x[hi]->data)        // abc acb bac
      if (x[lo]->data < x[mid]->data)    // abc acb
         if (x[mid]->data < x[hi]->data) // abc
            swap(lo, mid, x);
         else                             // acb
            swap(lo, hi, x);
      else ;                              // bac --- null statement
   else                                   // bca cab cba
      if (x[lo]->data > x[mid]->data)    // otherwise bca and no action
         if (x[mid]->data > x[hi]->data) // cba
            swap(lo, mid, x);
         else                             // cab
            swap(lo, hi, x);
// Open up a "hole" at x[lo], with median as pivot value
   hold = x[lo];
// The loop has two exits:  the two places where the lo and the hi
// indexes have come together.  In lieu of extra flags or logical
// comparisons, this code uses an explicit "break" at those two places.
   while (1)       // Note:  "break" out when (lo == hi)
   {//Search for the value from hi downward to plug the hole at x[lo]
      while (hold->data < x[hi]->data && lo < hi)
         hi = hi - 1;
//    If we've come together, we're done
      if (lo == hi) break;
//    Otherwise plug the hole at lo with the value at hi
      x[lo] = x[hi];
//    The hole is now at hi and lo is guaranteed good w.r.t. Pivot
      lo = lo + 1;

//    Search for the value from lo upward to plug the hole at x[hi]
      while (x[lo]->data < hold->data && lo < hi)
         lo = lo + 1;
//    If we've come together, we're done
      if (lo == hi) break;
//    Otherwise plug the hole at hi with the value at lo
      x[hi] = x[lo];
//    The hole is now at lo and hi is guaranteed good w.r.t. Pivot
      hi = hi - 1;
   } // end "infinite" while loop --- (lo == hi) became true
// Plug the remaining hole (which is guaranteed to be in hi = lo)
// with the pivot value, making this the partitioning element.

   x[hi] = hold;

   return hi;
}

/**
 * Insertion sort method, used by qSortO
 */
void inSort ( int lo, int hi, NodePtr x[] )
{  int  lim,    // start of unsorted region
        hole;   // insertion point in sorted region

   for ( lim = lo+1 ; lim <= hi ; lim++ )
   {  NodePtr save = x[lim];

      for ( hole = lim ;
            hole > lo && save->data < x[hole-1]->data ;
            hole-- )
      {  x[hole] = x[hole-1];  }

      x[hole] = save;
   } // end for (lim...
} // end inSort()