silentbob/gclib/src/dheapsort.cxx

   1 /*
   2  * (c) Oleg Puchinin 2006
   3  * graycardinalster@gmail.com
   4  *
   5  */
   6
   7 #include <unistd.h>
   8 #include <stdlib.h>
   9 #include <stdint.h>
  10 #include <string.h>
  11 #include <gclib/dheapsort.h>
  12
  13 DHeapSort::DHeapSort (int n)
  14 {
  15         size = 0;
  16         h = (char **) malloc (sizeof (char *) * n+10);
  17 }
  18
  19 DHeapSort::~DHeapSort()
  20 {
  21         if (h)
  22                 free (h);
  23 }
  24
  25 char * DHeapSort::add(char * x)
  26 {
  27         h[++size]=x;
  28         checkup(size);
  29         return x;
  30 }
  31
  32 char * DHeapSort::extract_min()
  33 {
  34         char *x;
  35         if(size <= 0)
  36                 return NULL;
  37         x = h[1];
  38         h[1] = h[size--];
  39         checkdown (1);
  40         return x;
  41 }
  42
  43 void DHeapSort::checkup(int c) {
  44         int p;
  45         char * tmp;
  46         p = c>>1;
  47         if (! p)
  48                 return;
  49         if (strcmp (h[p], h[c]) > 0) {
  50                 tmp = h[p]; h[p] = h[c]; h[c] = tmp;
  51                 checkup(p);
  52         }
  53 }
  54
  55 void DHeapSort::checkdown(int p)
  56 {
  57         int c;
  58         char * tmp;
  59         c = p<<1;
  60         if (c > size)
  61                 return;
  62         if ( ((c+1) <= size) && strcmp (h[c + 1], h[c]) < 0)
  63                 ++c;
  64         if (strcmp (h[c], h[p]) < 0) {
  65                 tmp =  h[c];
  66                 h[c] = h[p];
  67                 h[p] = tmp;
  68                 checkdown (c);
  69         }
  70 }
  71