/* This file is in the public domain. */

#include "sortsearch.h"

static void down(unsigned int size, unsigned int el, void **ptrs, int (*cmp)(void *, void *))
{
 unsigned int i;
 unsigned int j;
 unsigned int l;
 unsigned int r;
 unsigned int cl;
 unsigned int cr;
 void *temp;

 i = el;
 while (1)
  { if (i >= size) return;
    l = i + i + 1;
    r = l + 1;
    cl = (l >= size) ? 1 : ((*cmp)(ptrs[i],ptrs[l]) >= 0);
    cr = (r >= size) ? 1 : ((*cmp)(ptrs[i],ptrs[r]) >= 0);
    switch ((cl<<1)|cr)
     { case 0:
	  j = ((*cmp)(ptrs[l],ptrs[r]) > 0) ? l : r;
	  break;
       case 1:
	  j = l;
	  break;
       case 2:
	  j = r;
	  break;
       case 3:
	  return;
     }
    temp = ptrs[j];
    ptrs[j] = ptrs[i];
    ptrs[i] = temp;
    i = j;
  }
}

void heap_sort(void **ptrs, unsigned int nels, int (*cmp)(void *, void *))
{
 unsigned int i;
 void *temp;

 if (nels <= 1) return;
 i = (nels - 1) / 2;
 do
  { down(nels,i,ptrs,cmp);
  } while (i-- > 0);
 i = nels;
 while (i > 1)
  { i --;
    temp = ptrs[i];
    ptrs[i] = ptrs[0];
    ptrs[0] = temp;
    down(i,0,ptrs,cmp);
  }
}

int bin_search(void **ptrs, unsigned int nels, int (*cmp)(void *, void *), void *el)
{
 unsigned int hi;
 unsigned int lo;
 unsigned int mid;
 int cval;

 if (nels < 1) return(-1);
 hi = nels;
 lo = -1; /* yes, I know it's unsigned */
 while (hi-lo > 1)
  { mid = (hi + lo) / 2;
    cval = (*cmp)(ptrs[mid],el);
	 if (cval < 0) lo = mid;
    else if (cval > 0) hi = mid;
    else               return(mid);
  }
 return(-1);
}