/*******************************************************************************
* YORKTOWN ADVANCED SGML PARSER (YASP)                                         *
*         An SGML Parser conforming to International Standard ISO 8879 --      *
*         Standard Generalized Markup Language                                 *
*------------------------------------------------------------------------------*
* Written 1987 - 1993 by                                                       *
*         Pierre G. Richard                                                    *
*         IBM T.J. Watson Research Center                                      *
*         Yorktown Heights, New York                                           *
*         petrus@watson.ibm.com                                                *
*------------------------------------------------------------------------------*
* FUNCTION NAME    = YASP / General Library                                    *
* STATUS           = Version 0, Release 1, Level 16 and up                     *
* COMPONENT NAME   = wqsort.c                                                  *
* DESCRIPTIVE NAME = Hoares Quick Sort                                         *
* DATE_WR          = 06/30/1987                                                *
* AUTHOR           = Pierre G. Richard - PETRUS at YKTVMX                      *
*                                                                              *
* FUNCTIONAL DESCRIPTION =                                                     *
* Sort an array of elements "in place" using Hoare's Quicksort algorithm.      *
*                                                                              *
* void wqsort(num,compare,exchange,base)                                       *
*                                                                              *
* where:                                                                       *
* - "num" is the number of elements of the array,                              *
* - "compare" is an user-supplied routine that compares two array elements,    *
* - "exchange" is an user-supplied routine that exchanges two array elements.  *
*                                                                              *
* The form of the call to "compare" is:                                        *
*                                                                              *
*  compare(element_1_index,element_2_index,base)                               *
*  unsigned int element_1_index, element_2_index;                              *
*                                                                              *
*  where: "element_1_index"/"element_2_index" is the index of the              *
*          element_1/element_2 within the array.                               *
*                                                                              *
* This must return:                                                            *
* - 0 if the key in element_1 is equal to the one in element_2,                *
* - Less than 0 if the key if the key in element_1 is less                     *
*   than the one in element_2,                                                 *
* - Greather than 0 if the key if the key in element_1 is is greather          *
*   than the one in element_2.                                                 *
*                                                                              *
* The form of the call to "exchange" is:                                       *
*                                                                              *
*  exchange(element_1_index,element_2_index,base)                              *
*  unsigned int element_1_index, element_2_index;                              *
*                                                                              *
*  where: "element_1_index"/"element_2_index" is the index of the              *
*          element_1/element_2 within the array.                               *
*                                                                              *
*                                                                              *
* IMPLEMENTATION NOTE =                                                        *
* Recursive                                                                    *
*                                                                              *
* DEPENDENCIES =  (see Include list)                                           *
*                                                                              *
* IMPORT= NONE                                                                 *
*                                                                              *
* EXPORT= NONE                                                                 *
*                                                                              *
* CHANGE HISTORY =                                                             *
* Number Date     Inits    Change & Reason (brief)                             *
*      1 01/28/89 PETRUS   Make it reentrant                                   *
*******************************************************************************/

/*-------------+
|Include Files |
+-------------*/
#include "machine.h"
#include "portable.h"
#include "usrlib.h"

/*------------------------+
|Local Functions and Types|
+------------------------*/
typedef struct {                         /* reduce stack space */
   int  (P_FCT *comp)(int,int,void *);   /* key comparison function */
   void (P_FCT *exchg)(int,int,void *);  /* record exchange function */
   void *base;                           /* passed as it is (base ?)*/
}W;

static void LP_FCT hoares_sort (int, int, W const * const);

/*-----------------------------------------------------------------hoares_sort-+
|recursive function to sort array[beg..end] using Hoares algorithm             |
+-----------------------------------------------------------------------------*/
static void LP_FCT hoares_sort(int beg, int end, W const * const w_p)
{
   register int j, k;

   k = end + 1;
   while (beg < end) {
      j = beg;
      /*-------------------------------------------------+
      |Get "k" such that:                                |
      |in the range beg+1 to k, all values are <= V[beg] |
      +-------------------------------------------------*/
      for (;;) {
         while ((++j < k) && ((*w_p->comp)(j,beg,w_p->base) <= 0));
/*O**    while ((--k >=j) && ((*w_p->comp)(k,beg,w_p->base) >= 0)); */
/*N*/    while ((--k > j) && ((*w_p->comp)(k,beg,w_p->base) >= 0));
         if (k > j) {
            (*w_p->exchg)(j,k,w_p->base);
            continue;
         }
/*N*/    if (j == k) --k;
         break;
      }
      if (k != beg) (*w_p->exchg)(beg,k,w_p->base);

      /*--------------------+
      |Sort the lowest range|
      +--------------------*/
      if ((k - beg) >= (end - k)) {
         hoares_sort(k+1, end, w_p);
         end = k-1;
         /* k = end+1; */
      }else {
         hoares_sort(beg, k-1, w_p);
         beg = k+1;
         k = end+1;
      }
   }
}

/*----------------------------------------------------------------------wqsort-+
|Main routine:                                                                 |
|Check if we need to sort the array, then call the recursive routine.          |
+-----------------------------------------------------------------------------*/
void P_FCT wqsort(
   int num,                                    /* number of items to sort */
   int(P_FCT *compare)(int,int,void *),        /* key comparison function */
   void(P_FCT *exchange)(int,int,void *),      /* record exchange function */
   void *base)                                 /* passed as it is (base ?) */
{
   uint i;
   register int j, k;
   W w;

   if (num > 1) {                              /* else, nothing to sort */
      for (i=num, j=-1, k=0; --i; ) {
         if ((*compare)(++j,++k,base) > 0) {   /* at least one ... */
            w.comp = compare;
            w.exchg = exchange;
            w.base = base;
            hoares_sort(0, num - 1, &w);
            break;
         }
      }
   }
}
/******************************************************************************/
