#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include "lau.h"
#include "pcp.h"
#include "intsort.h"

/*
  In-place integer sorting function based on algorithm by
  R. Sedgewick. 

  BIG NOTE: 'vector' needs to have len+1 elements. The first len
  elements are the numbers to be sorted. The last element is used
  internally by sedgesort() function (which is called by ssort()) as a
  'sentinel'.
*/
void intsort(int *vector, int len)
{
  vector[len] = INT_MAX;
  intsedgesort(vector, len);
}

/*
 |  void  intheapsort (array, len)
 |  INTKEY_T  array[];
 |  int    len;
 |
 |  Abstract:	Sort array[0..len-1] into increasing order.
 |
 |  Method:	Heap-sort (ala Jon Bentley)
 |
 |  Advantages:
 |
 |	1. Stable sorting method (doesn't spoil relative order between
 |	   equal-key elements)
 |	2. Worst case complexity is O (n log(n))
 |	3. Method of choice when only the smallest n elemens are wanted
 |	   and not a full ordering (use sift n times).
 */

void  intheapsort (INTKEY_T array[], int len, int n)
{
    register int	i;
    register INTKEY_T	temp, *sa = array - 1;
    int limit;
    /*
     |  'sa[]' is 'array[]' "shifted" one position to the left
     |  i.e.  sa[i] == array[i - 1]  (in particular:   sa[1] == array[0])
     |  'sa' has "Pascalish" indices and is thus more convenient
     |  for heap-sorting. An index i obeys the law:
     |	left_child (i) == 2i,  right_child (i) == 2i + 1
     |  Note: we don't use a[-1] which is outside our range, we just
     |  fake an array that starts one address lower, so we can refer
     |  to its first element as a[1] (rather than as a[0])
     */

    /* first step: make 'sa[]' a heap using intsiftdown len/2 times */
    for (i = len / 2; i >= 1; i--)
      intsiftdown (sa, i, len);

    /* heapify n times, to reach partial order */
    limit = 2;
    if (len-n+1 > 2)
      limit = len-n+1;
    for (i = len; i >= limit; i--) 
      {
	SWAP(sa[1], sa[i]);
	intsiftdown (sa, 1, i - 1);
      }
}


/*
 |  void  intsiftdown (array, lower, upper)
 |  INTKEY_T  array[];
 |  int    lower, upper;
 |
 |  Abstract:
 |	Assume array[] is a heap except array[lower] is not in order.
 |	Sift array[lower] down the heap as long as it is bigger than
 |	its two children nodes. Preserving the heap condition.
 |
 |	Optimization: rather than swapping array[i] with the greater
 |	of its children within the loop, we save array[lower]
 |	before the loop, shift the inner values within the loop, and
 |	finally plug the saved value into its final location.
 */
void  intsiftdown (INTKEY_T array[], int lower, int upper)
{
    register int	i = lower, c = lower;
    register int	lastindex = upper/2;
    register INTKEY_T	temp;

    temp = array[i];
    while (c <= lastindex) {
	c = 2 * i;		/* c = 2i is the left-child of i */
	if (c + 1 <= upper  &&  GT(array[c + 1], array[c]))
	    c++;		/* c is the greatest child of i */
	if (GE(temp, array[c])) break;
	array[i] = array[c];
	i = c;
    }
    array[i] = temp;
}