/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
/*             ********   ***                                 SparseLib++    */
/*          *******  **  ***       ***      ***                              */
/*           *****      ***     ******** ********                            */
/*            *****    ***     ******** ********              R. Pozo        */
/*       **  *******  ***   **   ***      ***                 K. Remington   */
/*        ********   ********                                 A. Lumsdaine   */
/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
/*                                                                           */
/*                                                                           */
/*                     SparseLib++ : Sparse Matrix Library                   */
/*                                                                           */
/*               National Institute of Standards and Technology              */
/*                        University of Notre Dame                           */
/*              Authors: R. Pozo, K. Remington, A. Lumsdaine                 */
/*                                                                           */
/*                                 NOTICE                                    */
/*                                                                           */
/* Permission to use, copy, modify, and distribute this software and         */
/* its documentation for any purpose and without fee is hereby granted       */
/* provided that the above notice appear in all copies and supporting        */
/* documentation.                                                            */
/*                                                                           */
/* Neither the Institutions (National Institute of Standards and Technology, */
/* University of Notre Dame) nor the Authors make any representations about  */
/* the suitability of this software for any purpose.  This software is       */
/* provided ``as is'' without expressed or implied warranty.                 */
/*                                                                           */
/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/

// An adaptation of Schmidt's new quicksort (taken from GNU emacs)
// for MV++
// by Andrew Lumsdaine

#include "qsort_TYPE.h"

#ifdef sparc
#include <alloca.h>
#endif

// Invoke the < comparison function
#define CMP(A,B) ((A) < (B))

// swap two items
//
static inline void SWAP_TYPE(TYPE &A, TYPE &B)
{
    TYPE tmp = A; A = B; B = tmp;
}
 

static inline void swap_int(int &a, int &b)
{
    int tmp=a; a=b; b=tmp;
}

// This should be replaced by a standard ANSI macro.
#define BYTES_PER_WORD 8

/* The next 4 #defines implement a very fast in-line stack abstraction. */
#define STACK_SIZE (BYTES_PER_WORD * sizeof (long))
#define PUSH(LOW,HIGH) do {top->lo = LOW;top++->hi = HIGH;} while (0)
#define POP(LOW,HIGH)  do {LOW = (--top)->lo;HIGH = top->hi;} while (0)
#define STACK_NOT_EMPTY (stack < top)                

/* Discontinue quicksort algorithm when partition gets below this size.
   This particular magic number was chosen to work best on a Sun 4/260. */
#define MAX_THRESH 4

/* Stack node declarations used to store unfulfilled partition obligations. */
typedef struct {
  int lo;
  int hi;
} stack_node;

/* Order size using quicksort.  This implementation incorporates
   four optimizations discussed in Sedgewick:
   
   1. Non-recursive, using an explicit stack of pointer that store the 
      next array partition to sort.  To save time, this maximum amount 
      of space required to store an array of MAX_INT is allocated on the 
      stack.  Assuming a 32-bit integer, this needs only 32 * 
      sizeof (stack_node) == 136 bits.  Pretty cheap, actually.

   2. Chose the pivot element using a median-of-three decision tree.
      This reduces the probability of selecting a bad pivot value and 
      eliminates certain extraneous comparisons.

   3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
      insertion sort to order the MAX_THRESH items within each partition.  
      This is a big win, since insertion sort is faster for small, mostly
      sorted array segments.
   
   4. The larger of the two sub-partitions is always pushed onto the
      stack first, with the algorithm then concentrating on the
      smaller partition.  This *guarantees* no more than log (n)
      stack size is needed (actually O(1) in this case)! */
      

int QSort(VECTOR_TYPE& v, int base_ptr, int total_elems)
{
  TYPE pivot_buffer;
  
  if (total_elems > MAX_THRESH) {
    
    int lo = base_ptr;
    int hi = lo + total_elems - 1;
    
    stack_node stack[STACK_SIZE]; /* Largest size needed for 32-bit int!!! */
    stack_node *top = stack + 1;
    
    while (STACK_NOT_EMPTY) {
      int left_ptr;
      int right_ptr;
      {

    {

      /* Select median value from among LO, MID, and HI. Rearrange
         LO and HI so the three values are sorted. This lowers the 
         probability of picking a pathological pivot value and 
         skips a comparison for both the LEFT_PTR and RIGHT_PTR. */
      
      int mid = lo + (hi - lo) / 2;
      
      if (CMP (v[mid], v[lo]))
        SWAP_TYPE(v[mid], v[lo]);
      if (CMP (v[hi], v[mid]))
        SWAP_TYPE(v[hi], v[mid]);
      else 
        goto jump_over;
      
      if (CMP (v[mid], v[lo]))
        SWAP_TYPE(v[mid], v[lo]);
      
    jump_over:

      pivot_buffer = v[mid];
    }
    
    left_ptr  = lo + 1;
    right_ptr = hi - 1;
    
    /* Here's the famous ``collapse the walls'' section of quicksort.  
       Gotta like those tight inner loops!  They are the main reason 
       that this algorithm runs much faster than others. */
    do {
      while (CMP (v[left_ptr], pivot_buffer))
        left_ptr++;
      
      while (CMP (pivot_buffer, v[right_ptr]))
        right_ptr--;
      
      if (left_ptr < right_ptr) {
        SWAP_TYPE(v[left_ptr], v[right_ptr]);
        left_ptr++;
        right_ptr--;
      } else if (left_ptr == right_ptr) {
        left_ptr ++;
        right_ptr --;
        break;
      }
    } while (left_ptr <= right_ptr);
      }
      
      /* Set up pointers for next iteration.  First determine whether
     left and right partitions are below the threshold size. If so, 
     ignore one or both.  Otherwise, push the larger partition's
     bounds on the stack and continue sorting the smaller one. */
      
      if ((right_ptr - lo) <= MAX_THRESH) {
    if ((hi - left_ptr) <= MAX_THRESH)
      POP (lo, hi); 
    else
      lo = left_ptr;
      } else if ((hi - left_ptr) <= MAX_THRESH)
    hi = right_ptr;
      else if ((right_ptr - lo) > (hi - left_ptr)) {                   
    PUSH (lo, right_ptr);
    lo = left_ptr;
      } else {                   
    PUSH (left_ptr, hi);
    hi = right_ptr;
      }
    }
  }
  
  /* Once the BASE_PTR array is partially sorted by quicksort the rest
     is completely sorted using insertion sort, since this is efficient 
     for partitions below MAX_THRESH size. BASE_PTR points to the beginning 
     of the array to sort, and END_PTR points at the very last element in
     the array (*not* one beyond it!). */
  
#define MIN(X,Y) ((X) < (Y) ? (X) : (Y))

  {
    int end_ptr = base_ptr + total_elems - 1;
    int run_ptr;
    int tmp_ptr = base_ptr;
    int thresh = MIN (end_ptr, base_ptr + MAX_THRESH);
    
    for (run_ptr = tmp_ptr + 1; run_ptr <= thresh; run_ptr++)
      if (CMP (v[run_ptr], v[tmp_ptr]))
    tmp_ptr = run_ptr;
    
    if (tmp_ptr != base_ptr)
      SWAP_TYPE(v[tmp_ptr], v[base_ptr]);
    
    for (run_ptr = base_ptr + 1; (tmp_ptr = run_ptr += 1) <= end_ptr;) {
      
      while (CMP (v[run_ptr], v[tmp_ptr -= 1]))
    ;
      
      if ((tmp_ptr += 1) != run_ptr) {
    int trav;
    
    for (trav = run_ptr + 1; --trav >= run_ptr;) {
      TYPE c;
      c = v[trav];
      int hi, lo;
      
      for (hi = lo = trav; (lo -= 1) >= tmp_ptr; hi = lo)
        v[hi] = v[lo];
      v[hi] = c;
    }
      }
    }
  }

  return 1;
}


int QSort(VECTOR_int & v, VECTOR_TYPE& x, int base_ptr, int total_elems)
{
  int pivot_buffer;
  TYPE pixot_buffer;
  
  if (total_elems > MAX_THRESH) {
    
    int lo = base_ptr;
    int hi = lo + total_elems - 1;
    
    stack_node stack[STACK_SIZE]; /* Largest size needed for 32-bit int!!! */
    stack_node *top = stack + 1;
    
    while (STACK_NOT_EMPTY) {
      int left_ptr;
      int right_ptr;
      {

    {

      /* Select median value from among LO, MID, and HI. Rearrange
         LO and HI so the three values are sorted. This lowers the 
         probability of picking a pathological pivot value and 
         skips a comparison for both the LEFT_PTR and RIGHT_PTR. */
      
      int mid = lo + (hi - lo) / 2;
      
      if (CMP (v[mid], v[lo])) {
        swap_int (v[mid], v[lo]);
        SWAP_TYPE (x[mid], x[lo]);
      }
      if (CMP (v[hi], v[mid])) {
        swap_int (v[hi], v[mid]);
        SWAP_TYPE (x[hi], x[mid]);
      } else 
        goto jump_over;
      
      if (CMP (v[mid], v[lo])) {
        swap_int(v[mid], v[lo]);
        SWAP_TYPE (x[mid], x[lo]);
      }
      
    jump_over:

      pivot_buffer = v[mid];
      pixot_buffer = x[mid];
    }
    
    left_ptr  = lo + 1;
    right_ptr = hi - 1;
    
    /* Here's the famous ``collapse the walls'' section of quicksort.  
       Gotta like those tight inner loops!  They are the main reason 
       that this algorithm runs much faster than others. */
    do {
      while (CMP (v[left_ptr], pivot_buffer))
        left_ptr++;
      
      while (CMP (pivot_buffer, v[right_ptr]))
        right_ptr--;
      
      if (left_ptr < right_ptr) {
        swap_int (v[left_ptr], v[right_ptr]);
        SWAP_TYPE (x[left_ptr], x[right_ptr]);
        left_ptr++;
        right_ptr--;
      } else if (left_ptr == right_ptr) {
        left_ptr ++;
        right_ptr --;
        break;
      }
    } while (left_ptr <= right_ptr);
      }
      
      /* Set up pointers for next iteration.  First determine whether
     left and right partitions are below the threshold size. If so, 
     ignore one or both.  Otherwise, push the larger partition's
     bounds on the stack and continue sorting the smaller one. */
      
      if ((right_ptr - lo) <= MAX_THRESH) {
    if ((hi - left_ptr) <= MAX_THRESH)
      POP (lo, hi); 
    else
      lo = left_ptr;
      } else if ((hi - left_ptr) <= MAX_THRESH)
    hi = right_ptr;
      else if ((right_ptr - lo) > (hi - left_ptr)) {                   
    PUSH (lo, right_ptr);
    lo = left_ptr;
      } else {                   
    PUSH (left_ptr, hi);
    hi = right_ptr;
      }
    }
  }
  
  /* Once the BASE_PTR array is partially sorted by quicksort the rest
     is completely sorted using insertion sort, since this is efficient 
     for partitions below MAX_THRESH size. BASE_PTR points to the beginning 
     of the array to sort, and END_PTR points at the very last element in
     the array (*not* one beyond it!). */
  
#define MIN(X,Y) ((X) < (Y) ? (X) : (Y))

  {
    int end_ptr = base_ptr + total_elems - 1;
    int run_ptr;
    int tmp_ptr = base_ptr;
    int thresh = MIN (end_ptr, base_ptr + MAX_THRESH);
    
    for (run_ptr = tmp_ptr + 1; run_ptr <= thresh; run_ptr++)
      if (CMP (v[run_ptr], v[tmp_ptr]))
    tmp_ptr = run_ptr;
    
    if (tmp_ptr != base_ptr) {
      swap_int(v[tmp_ptr], v[base_ptr]);
      SWAP_TYPE (x[tmp_ptr], x[base_ptr]);
    }
    
    for (run_ptr = base_ptr + 1; (tmp_ptr = run_ptr += 1) <= end_ptr;) {
      
      while (CMP (v[run_ptr], v[tmp_ptr -= 1]))
    ;
      
      if ((tmp_ptr += 1) != run_ptr) {
    int trav;
    
    for (trav = run_ptr + 1; --trav >= run_ptr;) {
      int  c;
      TYPE d;
      c = v[trav];
      d = x[trav];
      int hi, lo;
      
      for (hi = lo = trav; (lo -= 1) >= tmp_ptr; hi = lo) {
        v[hi] = v[lo];
        x[hi] = x[lo];
      }
      v[hi] = c;
      x[hi] = d;
    }
      }
    }
  }

  return 1;
}
