/***********************************************************************/
/*  HSORT(): Heap Sort function.                                       */
/*  See the function declaration for calling information.              */
/*  Set STANDALONE != 0 to compile a shell to test the sucker;         */
/*    to compile just hsort() and its supporting functions, set        */
/*    STANDALONE = 0.                                                  */
/* DEBUG determines how much debugging info is displayed; 0 is none.   */
/* TRACE determines what level of tracing information is displayed;    */
/*    0 is none.                                                       */
/* Function is by Bruce Feist; please contact me on CompuServe with    */
/*    a message on BORPRO or through EASYPLEX if you have any          */
/*    questions or problems.                                           */
/* Feel free to make use of this code in your own programs.            */
/***********************************************************************/

#define DEBUG 0
#define STANDALONE 0
#define TRACE 0

#include <stdio.h>
#include <process.h>
#include <alloc.h>
#include <stdlib.h>
#include <mem.h>

static void pascal swap (unsigned int, unsigned int);
static void pascal buildheap (void);
static void pascal heapify (unsigned int, unsigned int);
void       hsort (void *, unsigned int, unsigned int, int (*)());

#if STANDALONE
static int int_compare (int *, int *);
static void showarray (int *, unsigned int, unsigned int);

void
main()
{
  unsigned int n_entries, entry_num;
  int *entries;

  printf ("How many entries do you wish to sort?  ");
  scanf ("%d", &n_entries);
  entries = (int *) malloc (n_entries * sizeof(int));

  for (entry_num = 0; entry_num < n_entries; entry_num++)
  {
    printf ("Enter #%d:  ", entry_num);
    scanf ("%d", entries + entry_num);
    }

  printf ("\n");

  hsort (entries, n_entries, sizeof (int), int_compare);

  showarray (entries, 0, n_entries - 1);

  exit (0);
  }


int
int_compare (i, j)
int *i, *j;
{
  return (*i - *j);
  }


void
showarray(base, bot, top)
int *base;
unsigned int bot, top;
{
  unsigned int i;

  for (i=bot; i<=top; i++)
    printf("%4d", base[i]);
  printf ("\n");
  }

#endif   /* STANDALONE */


static int (*static_compare) (void *, void *), static_width, static_n_elements;
static void *temp_element, *static_base;

void
hsort(base, n_elements, element_width, compare)
/***************************************************************************/
/* Heap Sort routine -- similar in calling sequence to standard 'qsort()'  */
/* Base is a pointer to an array                                           */
/* n_elements is the number of elements in the array                       */
/* element_width is the width of each element in bytes                     */
/* compare is a function of two pointers (each to an element of the array) */
/*    returning a negative value if the first is smaller, a positive value */
/*    if the second is smaller, or 0 if they should be sorted the same.    */
/* Warning!  This function will halt your program if it can't allocate     */
/*    element_width bytes using malloc().                                  */
/***************************************************************************/

void *base;
unsigned int  n_elements, element_width;
int           (*compare)();
{
  register unsigned int i;

#if TRACE >= 1
  printf("hsort(base at %lX, %u elements, width %u, compare at %ld)\n",
         (long) base, n_elements, element_width, (long) compare);
#endif

  /* this lets us reference elements of array as 1 to n */

  (char *) base -= element_width;

  /*  The following assignments to static variables reduce the */
  /* overhead of subroutine calls later.                       */

  static_width = element_width;
  static_compare = compare;
  static_n_elements = n_elements;
  static_base = base;

  temp_element = malloc (element_width);

  if (temp_element == NULL)
  {
    fputs ("Unable to allocate room for a temporary element in hsort().\n",
           stderr);
    exit (1);
    }


  buildheap ();

  for (i = n_elements; i>1; i--)
  {
    swap (1, i);
    heapify (1, i-1);
    }

  free (temp_element);
  }


static void pascal
swap (i, j)
unsigned int i,j;

{
  register int temp_int;
  long temp_long;

#if TRACE >= 2
  printf("swap (i=%d, j=%d) called.\n",i,j);
#endif

  switch (static_width)
  {
    case sizeof (int): temp_int = ((int *) static_base) [i];
                       ((int *) static_base) [i] = ((int *) static_base) [j];
                       ((int *) static_base) [j] = temp_int;
                       break;

    case sizeof(long): temp_long = ((long *) static_base) [i];
                       ((long *) static_base) [i] = ((long *) static_base) [j];
                       ((long *) static_base) [j] = temp_long;
                       break;

    case sizeof(char): temp_int = ((char *) static_base) [i];
                       ((char *) static_base) [i] = ((char *) static_base) [j];
                       ((char *) static_base) [j] = (char) temp_int;
                       break;

    default:           memcpy (temp_element,
                               (char *) static_base + i*static_width,
                               static_width);
                      memcpy ((char *) static_base + i*static_width,
                              (char *) static_base + j*static_width,
                              static_width);
                      memcpy ((char *) static_base + j*static_width,
                              temp_element,
                              static_width);
                      break;
    }  /* end of switch */

#if TRACE >= 2
  printf ("swap exited.\n");
#endif
  }


static void pascal
buildheap()

{
  register unsigned int element_number;

#if TRACE >= 2
  printf("buildheap() called.\n");
#endif

  for (element_number = static_n_elements >> 1;
       element_number >= 1;
       element_number--)
  {
#if DEBUG >= 2
    printf ("buildheap calls heapify (%d, %d).\n",
            element_number, static_n_elements);
#endif
    heapify(element_number, static_n_elements);
    }

#if TRACE >= 2
  printf ("buildheap exited.\n");
#endif
  }


#define son1(i)    (i << 1)
#define son2(i)    ((i << 1) + 1)
#define pointer(i) ((char *) static_base + i * static_width)
#define child_count(i, j) \
     (j > son1(i) \
       ? 2 \
       : j < son1(i) \
          ? 0 \
          : 1)


static void pascal
heapify (i,j)

unsigned int i, j;
{
  /* The following are static to avoid recursive stack overhead */

  static unsigned int son1i, son2i;
  static void *pson1, *pson2, *pi;
  static unsigned int k;

#if TRACE >= 3
  printf("heapify(i=%d, j=%d) called.\n", i, j);
#endif

  son1i = son1 (i);
  son2i = son2 (i);
  pson1 = pointer (son1i);
  pson2 = pointer (son2i);
  pi    = pointer (i);

#if DEBUG >= 2
  printf ("child_count (%d) = %d.\n", i, child_count(i, j));
#endif

  switch (child_count (i, j))
  {
    case 0: break;

    case 2: {
              k = (*static_compare) (pson1, pson2) > 0 ? son1i : son2i;
              if ((*static_compare) (pi, pointer (k)) < 0)
              {
#if STANDALONE && DEBUG >= 1
                printf ("heapify changes\n");
                showarray (static_base, 1, static_n_elements);
#endif

                swap (i, k);
                heapify (k, j);

#if STANDALONE && DEBUG >= 1
                printf ("into\n");
                showarray (static_base, 1, static_n_elements);
#endif
                }
              break;
            }  /* end case */

    case 1: if ((*static_compare) (pi, pson1) < 0)
            {
#if STANDALONE && DEBUG >= 1
              printf ("heapify changes\n");
              showarray (static_base, 1, static_n_elements);
#endif

              swap (i, son1i);
              heapify (son1i, j);

#if STANDALONE && DEBUG >= 1
              printf ("into\n");
              showarray (static_base, 1, static_n_elements);
#endif
              }
            break;
    }  /* end of case */

#if TRACE >= 3
  printf ("heapify exited.\n");
#endif
  }