#ifndef SORTINGMETHODS
#define SORTINGMETHODS
#include <apstack.h>
//////////////////
//sort functions//
//////////////////
/*In all of these, the first parameter is always the list to be sorted. It will
be passed by reference to ensure when the function complete, the list is prepared.
Extra parameters are noted below.*/

template <class T>
void selectionsort(T &stock, int &LIMIT, int &swaps, int &comps);                //lame selection sort
   //lovable old selection sort
   //selects lowest element, moves it to front, repeat for remaining selection
   //returns number of swaps required to complete sorting process

template <class T>
void qsort(T* &mylist, int low, int high, int &swaps, int &comps);     //really cool quicksort
   //this is a recursive quicksort.
   //low is the first element to be sorted, and high is the final element to be
   //sorted. These indices are inclusive.
   //returns number of swaps needed to sort mylist

template <class T>
void nr_qsort(T* &mylist, int low, int high, int &swaps, int &comps);     //really cool quicksort
   //this is a NONrecursive quicksort.
   //low is the first element to be sorted, and high is the final element to be
   //sorted. These indices are inclusive.
   //returns number of swaps needed to sort mylist

template <class T>
void merge(T* &ar, int lowerindex, int upperindex, int &LIMIT, int &swaps, int &comps); //totally awesome mergesort
   //lowerindex and upperindex are the ranges of the array (ar) to sort.
   //The indices are inclusive.
   //returns number of data moves needed to sort initial array

template <class T>
void heapsort(T* &ar, int &LIMIT, int &swaps, int &comps);                          //truly spectacular heapsort
   //a heapsort using a pseudo-linked list in an array
   //this function is not recursive
   //returns number of swaps required

template <class T>
void shell(T &ar, const int &STEP, int &LIMIT, int &swaps, int &comps)
   //sorts using the shell algorithm. It is a divided insertion sort.
   //ar is to be sorted, STEP is the number of elements to put in a single
   //column on a given pass.
   //RETURNS number of swaps required.

template <class T>
void insertion(T &ar, int &LIMIT, int &swaps, int &comps);
   //ar is array to be sorted
   //performs a shell sort with colheight=1.
   //RETURNS number of swaps required.

template <class T>
inline void swap(T &L, T &R) { T temp=L; L=R; R=temp;};
   //somewhat useful swap function.
   //would not work with templates.

template <class T>
void selectionsort(T &stock, int &LIMIT, int &swaps, int &comps)
{
   for(int i=0; i<LIMIT-1; i++)
   {
      int target=i;
      for(int j=i+1; j<LIMIT; j++)   //seek smallest item
      {
         comps++;
         if(stock[j]<stock[target])
            target=j;
      }
      if(target!=i)
      {
         swap(stock[i],stock[target]);           //swap with front, advance front
         swaps++;
      }
   }
}

template <class T>
void qsort(T* &mylist, int low, int high, int &swaps, int &comps)
{
   if(low>=high)       //bail out on empty to-do list
      return;

   int pivot=low,
       left=pivot+1,   //values to traverse the list
       right=high;     //and progress toward center

   while(right>=left)
   {
      comps++;
      if(mylist[right]<mylist[left])          //if out of place
      {
         swap(mylist[right],mylist[left]);
         swaps++;
      }
      else
      {
         comps++;
         if(mylist[left]<mylist[pivot])
            left++;
         else
            right--;
      }
   }                                //assertion: now right==left
   swap(mylist[pivot],mylist[right]);
   swaps++;
   qsort(mylist,low,right,swaps,comps);                //sort left half
   qsort(mylist,left,high,swaps,comps);              //sort right half
}

template <class T>
void nr_qsort(T* &mylist, int low, int high, int &swaps, int &comps)
{
   apstack <int> low_stack;
   apstack <int> high_stack;

   low_stack.push(low);
   high_stack.push(high);

   while(low_stack.length()>0)
   {
      low_stack.pop(low);           //get first set of boundaries to sort by
      high_stack.pop(high);

      if(low<high)       //bail out on empty to-do list
      {
         int pivot=low,
             left=pivot+1,   //values to traverse the list
             right=high;     //and progress toward center

         while(right>=left)
         {
            comps++;
            if(mylist[right]<mylist[left])          //if out of place
            {
               swap(mylist[right],mylist[left]);
               swaps++;
            }
            else
            {
               comps++;
               if(mylist[left]<mylist[pivot])
                  left++;
               else
                  right--;
            }
         }                                //assertion: now right==left
         swap(mylist[pivot],mylist[right]);
         swaps++;

         low_stack.push(low);                 //sort left half
         high_stack.push(right);              //by pushing it on to the stack

         low_stack.push(left);                //sort right half
         high_stack.push(high);               //by pushing it on to the stack
      }
   }
}

template <class T>
void merge(T* &ar, int lowerindex, int upperindex, int &LIMIT, int &swaps, int &comps)
{
   int split=(upperindex+lowerindex-1)/2;           //last index of left array fragment

   if(upperindex-lowerindex>1)                      //if array fragment is greater than 1,
   {
      merge(ar,lowerindex,split,LIMIT,swaps,comps);        //divide and conquer
      merge(ar,split+1,upperindex,LIMIT,swaps,comps);
   }

   //temporary array in which sorted values are stored. Is then used to
   //replace all the "stuff" into the original array
   T* temp=new T[LIMIT];

   //keeps track of the "next in line" element for both partial arrays
   int Lmark=lowerindex,
       Rmark=split+1,
       Imark=lowerindex; //Imark is for temp array
   while(Imark<=upperindex)
   {
      comps++;
      if(Rmark>upperindex || (ar[Lmark]<ar[Rmark] && Lmark<=split))
      {
         temp[Imark]=ar[Lmark];
         swaps++;
         Imark++; Lmark++;
      }
      else
      {
         temp[Imark]=ar[Rmark];
         swaps++;
         Imark++; Rmark++;
      }
   }

   //replace elements of ar with sorted temp stuff
   for(int i=lowerindex; i<=upperindex; i++)
   {
      ar[i]=temp[i];
      swaps++;
   }

   delete[] temp;
}

template <class T>
void heapsort(T* &ar, int &LIMIT, int &swaps, int &comps)
{
   apvector <T> temp(1);                  //a vector used to build a heapified array

   for(int i=0; i<LIMIT; i++)              //for each ar[]
   {
      temp.resize(temp.length()+1);               //append to back, then
      temp[temp.length()-1]=ar[i];
      int f=i;
      while(f>1)
      {
         comps++;
         if(temp[f/2]<temp[f])             //check against parent
         {
            swap(temp[f/2],temp[f]);       //swap on low
            swaps++;
         }
         f/=2;                             //repeat as far up tree as necessary
      }
   }

   for(int i=0; i<LIMIT; i++)     //now shift over newly built heap to ar[]
      ar[i]=temp[i+1];

   //assertion: now any node is greater than its two children

   for(int i=LIMIT-1; i>=1; i--)
   {
      swap(ar[i],ar[0]);                       //put largest item in back
      swaps++;

      //now move swapped head to correct position in heap
      int toppos=0;                            //position of head to move down
      while(toppos<(i+1)/2-1)
      {
         if(ar[toppos]<ar[(toppos+1)*2-1] && ar[(toppos+1)*2  ]<ar[(toppos+1)*2-1]) //left  child is biggest
         {
            swap(ar[toppos],ar[(toppos+1)*2-1]);
            swaps++;
            toppos=(toppos+1)*2-1;                              //stalk child
            comps+=1;
         }
         else if(ar[toppos]<ar[(toppos+1)*2  ] && ar[(toppos+1)*2-1]<ar[(toppos+1)*2  ]) //right child is biggest
         {
            swap(ar[toppos],ar[(toppos+1)*2  ]);
            swaps++;
            toppos=(toppos+1)*2;                                //stalk child
            comps+=2;
         }
         else                                                                             //node is in position
         {
            break;
            comps+=2;                                         //child is safe
         }
      }                            //loop ends when node is in place or array runs out of children
   }
}
template <class T>
void shell(T &ar, const int &STEP, int &LIMIT, int &swaps, int &comps)
{
   for(int h=0; h<STEP; h++)
      for(int i=STEP+h; i<LIMIT; i+=STEP)
      {
         int j=i;
         while(j>=STEP && ar[j]<ar[j-STEP])
         {
            comps++;
            swap(ar[j],ar[j-STEP]);
            j-=STEP;
            swaps++;
         }
         comps++;
      }
}
template <class T>
void insertion(T &ar, int &LIMIT, int &swaps, int &comps)
{
   shell(ar,1,LIMIT,swaps,comps); //insertion a subset of shell, specifically when columnheight=1.
}

#endif