include/AD/sort/heapsrt2.h

   1 //////////////////////////////////////////////////////////////////////////////
   2 // NOTICE:
   3 //
   4 // ADLib, Prop and their related set of tools and documentation are in the
   5 // public domain.   The author(s) of this software reserve no copyrights on
   6 // the source code and any code generated using the tools.  You are encouraged
   7 // to use ADLib and Prop to develop software, in both academic and commercial
   8 // settings, and are free to incorporate any part of ADLib and Prop into
   9 // your programs.
  10 //
  11 // Although you are under no obligation to do so, we strongly recommend that
  12 // you give away all software developed using our tools.
  13 //
  14 // We also ask that credit be given to us when ADLib and/or Prop are used in
  15 // your programs, and that this notice be preserved intact in all the source
  16 // code.
  17 //
  18 // This software is still under development and we welcome any suggestions
  19 // and help from the users.
  20 //
  21 // Allen Leung
  22 // 1994
  23 //////////////////////////////////////////////////////////////////////////////
  24
  25 #ifndef heap_sort2_h
  26 #define heap_sort2_h
  27
  28 #include <AD/sort/sorting2.h>
  29
  30 //
  31 // Heap sort using Floyd's heap construction algorithm\cite{algo-hand-book}
  32 //
  33 // The sorting algorithm is divided into two phases.  In the
  34 // first, a heap is constructed in place, with the maximum
  35 // element in location 0.  The second phase repeatedly extract
  36 // the maximum and move it to the end of the array.
  37 //
  38 //
  39 // e.g.:   heapSort2(char *, int, names, salaries, 100, strcmp(key,names[i]) < 0);
  40 //
  41
  42 ///////////////////////////////////////////////////////////////////////////
  43 //  Macro version
  44 ///////////////////////////////////////////////////////////////////////////
  45 #define heapSort2(KEY,VALUE,A,B,N,predicate)             \
  46    do { register int i, j, k;                            \
  47         for (k = 1; k < (N); k++) {                      \
  48            register KEY   key   = (A)[k];                \
  49            register VALUE value = (B)[k];                \
  50            for (j = k; j > 0; j = i) {                   \
  51               i = (j-1)/2;                               \
  52               if (predicate) break;                      \
  53               (A)[j] = (A)[i];                           \
  54               (B)[j] = (B)[i];                           \
  55            }                                             \
  56            (A)[j] = key;                                 \
  57            (B)[j] = value;                               \
  58         }                                                \
  59         for (k = (N)-1; k > 0; k--) {                    \
  60            KEY   max     = (A)[0];                       \
  61            VALUE max_val = (B)[0];                       \
  62            register KEY   key   = (A)[k];                \
  63            register VALUE value = (B)[k];                \
  64            for (j = 0; (i = j+j+1) < k; j = i) {         \
  65               if (! (predicate)) {                       \
  66                  i++; if (i > k || ! (predicate)) break; \
  67               } else if (i + 1 < k) {                    \
  68                  register KEY& key = (A)[i+1];           \
  69                  if (! (predicate)) i++;                 \
  70               }                                          \
  71               (A)[j] = (A)[i];                           \
  72               (B)[j] = (B)[i];                           \
  73            }                                             \
  74            (A)[j] = key;   (A)[k] = max;                 \
  75            (B)[j] = value; (B)[k] = max_val;             \
  76         }                                                \
  77    } while(0)
  78
  79 ///////////////////////////////////////////////////////////////////////////
  80 //  Template version
  81 ///////////////////////////////////////////////////////////////////////////
  82 template <class K, class V, class Ord>
  83    class HeapSort2 : public Sorting2<K,V,Ord> {
  84    public:
  85       void sort(int, K [], V []);
  86    };
  87
  88 template <class K, class V, class Ord>
  89    void HeapSort2<K,V,Ord>::sort(int N, K keys[], V values[])
  90    {  heapSort2(K, V, keys, values, N, Ord::less(key,keys[i])); }
  91
  92 #endif