#include "defmerge.h"

/*
 * Korjataan paikoissa [ 0 .. i - 1 ] oleva keko kuntoon, kun paikassa
 * h[ 0 ] oleva alkio on mahdollisesti vaarassa paikassa.
 */

void downheap_f(int h[], int low, int high, int (*f)(TYPE *, TYPE *))
{
  int temp = h[ low ];
  int son = low << 1;
  add_assignments(1);

  /* ETSITAAN ISOMPIEN POIKIEN POLKU LEHTITASOLLE */
  
  /* silmukoidaan tassa, KUN pojalla ON veli */
  while ( son < high ) {
    add_comparisons(1);
    if (f(&h[ son ], &h[son + 1]) <= 0)
      ++son;
    add_assignments(1);
    h[ son >> 1 ] = h[ son ];
    son <<= 1;
  }
  
  /* paadyttiinko poikaan, jolla ei ole veljea */
  if ( son == high ) {
    add_assignments(1);
    h[ son >> 1 ] = h[ son ];
  }
  else { 
    /* on ohitettu lehtitaso,  */
    /* siispa pienennetaan 'son':n arvoa edelliseen arvoon */
    son >>= 1;
  }
  
  /* NYT kursorin 'k' pitaisi osoittaa lehtitasossa olevaan 'koloon' */
  /* lahdetaan tyontamaan 'temp' alkiota ylospain, vert. insert  */
  
  while (son > low ) {
    add_comparisons(1);
    if ( f(&h[ son >> 1 ], &temp) < 0) {
      add_assignments(1);
      h[ son ] = h[ son >> 1 ];
      son >>= 1;
    }
    else
      low = son;
  }
  add_assignments(1);
  h[ son ] = temp;
  
}

/* HEAP SORT */
void heapsort_f(int h[], int n, int (*f)(TYPE *, TYPE *))
{
  /* keko paikoissa 1..n */
  int i, temp;
  for ( i = n >> 1; i >= 1; --i) {
    downheap_f(h, i, n, f);
  }
  for ( i = n; i > 1; --i ) {
    add_assignments(3);
    temp = h[ i ];
    h[ i ] = h[1];
    h[ 1 ] = temp;
    downheap_f(h, 1, i - 1, f);
  }
}