/*
 
  sort.c -- sort a table using quicksort
 
  Author: ppessi <Pekka.Pessi@hut.fi>
 
  Copyright (c) 1992 Pekka Pessi
                     All rights reserved
 
  Created      : Thu Dec  3 11:21:42 1992 ppessi
  Last modified: Thu Dec  3 11:57:51 1992 ppessi
 
*/

#ifdef NOMYDEBUG
#define MYDEBUG( x )
#else
#include <clib/dos_protos.h>
#define MYDEBUG(x) x
#endif

static void 
  _quick_sort(void *slots[], int left, int right, int(*compare)(void *, void *))
{
  void *ld, *rd, *md, *sd;
  int middle, l, r;

  remove_tail:
  if (right - left < 8)		/* we left this for insertion sort */
    return;
  /* Find median */
  middle = (left + right) / 2;
  ld = slots[left];
  md = slots[middle];
  rd = slots[right];

  MYDEBUG( FPrintf(Stderr, 
		   "Left (%ld): %s, middle (%ld): %s, right (%ld): %s\n", 
		  left, ld -> ed_Name, 
		   middle, md -> ed_Name, 
		  right, rd -> ed_Name) );

  if ((compare)(ld, rd) > 0) 
    sd = rd,  rd = ld,  ld = sd; /* swap */

  if ((compare)(ld, md) > 0) 
    sd = md,  md = ld,  ld = sd; /* swap */

  if ((compare)(md, rd) > 0) 
    sd = md,  md = rd,  rd = sd; /* swap */

  slots[right] = rd;		
  slots[middle] = slots[right - 1];
  slots[left] = ld;
  /* use median as a sentinel and partitioning element */
  slots[right - 1] = md;	

  MYDEBUG( FPrintf(Stderr, "Left: %s, middle:  %s, right: %s\n", 
		  ld -> ed_Name, md -> ed_Name, rd -> ed_Name) );

  for (l = left, r = right - 1; l < r; ) {    
    /* scan from left */
    do {l++;} while ((compare)(md, slots[l]) >= 0);

    MYDEBUG( FPrintf(Stderr, "Left %s \n", slots[l] -> ed_Name) );
    /* scan from right */
    do {r--;} while ((compare)(slots[r], md) >= 0);

    MYDEBUG( FPrintf(Stderr, "Right %s \n", slots[r] -> ed_Name) );

    if (l < r)
      ld = slots[l], slots[l] = slots[r], slots[r] = ld; /* swap elements */
  }
  /* move partition element into partition place */
  md = slots[right - 1], slots[right - 1] = slots[l], slots[l] = md;

  if (l > middle) {		/* sort smaller partition recursively */
    _quick_sort(slots, l + 1, right, compare);
    right = l - 1;
  } else {
    _quick_sort(slots, left, l - 1, compare);
    left = l + 1;
  }
  goto remove_tail;			/* remove tail recursion  */
}

/*
  Actual quick_sort does final sorting with insertion sort
*/
void
quick_sort(void *slots[], int size, int(*compare)(void *, void *))
{
  register int i, j;
  MYDEBUG( register int distance; )
  register void *data;

  _quick_sort(slots, 0, size- 1, compare);

  for (j = 1; j < size; j++) {
    data = slots[j];
    i = j; 

    MYDEBUG( distance = 0; )

    while (i > 0 && (compare)(data, slots[i-1]) < 0) {
      slots[i] = slots[i-1];
      i--; 

      MYDEBUG( distance++; )
    }
    slots[i] = data;
    MYDEBUG( if (distance)
	    FPrintf(Stderr, "Moved %s by %ld\n", data -> ed_Name, distance); )
  }
}