chiark - git - mdw - disorder/blob - lib/heap.h

   1 /*
   2  * This file is part of DisOrder.
   3  * Copyright (C) 2007, 2008 Richard Kettlewell
   4  *
   5  * This program is free software: you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation, either version 3 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17  */
  18 /** @file lib/heap.h @brief Binary heap template */
  19
  20 #ifndef HEAP_H
  21 #define HEAP_H
  22
  23 #include "vector.h"
  24
  25 /** @brief Binary heap template.
  26  * @param NAME name of type to define
  27  * @param ETYPE element type
  28  * @param LT comparison function
  29  *
  30  * Defines a heap type called @c struct @p NAME and a number of functions to
  31  * operate on it.
  32  *
  33  * The element type of the heap will be @p ETYPE.
  34  *
  35  * @p LT will be called with two arguments of type @p ETYPE, and
  36  * implements a less-than comparison.
  37  *
  38  * The functions defined are:
  39  * - NAME_init(h) which initializes an empty heap at @p h
  40  * - NAME_count(h) which returns the number of elements in the heap
  41  * - NAME_insert(h, e) which inserts @p e into @p h
  42  * - NAME_first(g) which returns the least element of @p h
  43  * - NAME_remove(g) which removes and returns the least element of @p h
  44  *
  45  * The heap is implemented as a vector.  Element 0 is the root.  For any
  46  * element \f$i\f$, its children are elements \f$2i+1\f$ and \f$2i+2\f$ and
  47  * consequently its parent (if it is not the root) is
  48  * \f$\lfloor(i-1)/2\rfloor\f$.
  49  *
  50  * The insert and remove operations maintain two invariants: the @b
  51  * shape property (all levels of the tree are fully filled except the
  52  * deepest, and that is filled from the left), and the @b heap
  53  * property, that every element compares less than or equal to its
  54  * children.
  55  *
  56  * The shape property implies that the array representation has no gaps, which
  57  * is convenient.  It is preserved by only adding or removing the final element
  58  * of the array and otherwise only modifying the array by swapping pairs of
  59  * elements.
  60  *
  61  * @b Insertion works by inserting the new element \f$N\f$ at the end and
  62  * bubbling it up the tree until it is in the right order for its branch.
  63  * - If, for its parent \f$P\f$, \f$P \le N\f$ then it is already in the right
  64  * place and the insertion is complete.
  65  * - Otherwise \f$P > N\f$ and so \f$P\f$ and \f$N\f$ are exchanged.  If
  66  * \f$P\f$ has a second child, \f$C\f$, then \f$N < P < C\f$ so the heap
  67  * property is now satisfied from \f$P\f$ down.
  68  *
  69  * @b Removal works by first swapping the root with the final element (and then
  70  * removing it) and then bubbling the new root \f$N\f$ down the tree until it
  71  * finds its proper place.  At each stage it is compared with its children
  72  * \f$A\f$ and \f$B\f$.
  73  * - If \f$N \le A\f$ and \f$N \le B\f$ then it is in the
  74  * right place already.
  75  * - Otherwise \f$N > A\f$ or \f$N > B\f$ (or both).  WLOG \f$A \le B\f$.
  76  * \f$N\f$ and \f$A\f$ are exchanged, so now \f$A\f$ has children \f$N\f$ and
  77  * \f$B\f$.  \f$A < N\f$ and \f$A \le B\f$.
  78  */
  79 #define HEAP_TYPE(NAME, ETYPE, LT)                                      \
  80   typedef ETYPE NAME##_element;                                         \
  81   VECTOR_TYPE(NAME, NAME##_element, xrealloc);                          \
  82                                                                         \
  83   static inline int NAME##_count(struct NAME *heap) {                   \
  84     return heap->nvec;                                                  \
  85   }                                                                     \
  86                                                                         \
  87   static inline NAME##_element NAME##_first(struct NAME *heap) {        \
  88     assert(heap->nvec > 0 && "_first");                                 \
  89     return heap->vec[0];                                                \
  90   }                                                                     \
  91                                                                         \
  92   void NAME##_insert(struct NAME *heap, NAME##_element elt);            \
  93   NAME##_element NAME##_remove(struct NAME *heap);                      \
  94                                                                         \
  95   struct heap_swallow_semicolon
  96
  97 /** @brief External-linkage definitions for @ref HEAP_TYPE */
  98 #define HEAP_DEFINE(NAME, ETYPE, LT)                            \
  99   void NAME##_insert(struct NAME *heap, NAME##_element elt) {   \
 100     int n = heap->nvec;                                         \
 101     NAME##_append(heap, elt);                                   \
 102     while(n > 0) {                                              \
 103       const int p = (n-1)/2;                                    \
 104       if(!LT(heap->vec[n],heap->vec[p]))                        \
 105         break;                                                  \
 106       else {                                                    \
 107         const NAME##_element t = heap->vec[n];                  \
 108         heap->vec[n] = heap->vec[p];                            \
 109         heap->vec[p] = t;                                       \
 110         n = p;                                                  \
 111       }                                                         \
 112     }                                                           \
 113   }                                                             \
 114                                                                 \
 115   NAME##_element NAME##_remove(struct NAME *heap) {             \
 116     int n = 0;                                                  \
 117     NAME##_element r;                                           \
 118                                                                 \
 119     assert(heap->nvec > 0 && "_remove");                        \
 120     r = heap->vec[0];                                           \
 121     heap->vec[0] = heap->vec[--heap->nvec];                     \
 122     while(2 * n + 1 < heap->nvec) {                             \
 123       int a = 2 * n + 1;                                        \
 124       int b = 2 * n + 2;                                        \
 125                                                                 \
 126       if(b < heap->nvec && LT(heap->vec[b],heap->vec[a])) {     \
 127         ++a;                                                    \
 128         --b;                                                    \
 129       }                                                         \
 130       if(LT(heap->vec[a], heap->vec[n])) {                      \
 131         const NAME##_element t = heap->vec[n];                  \
 132         heap->vec[n] = heap->vec[a];                            \
 133         heap->vec[a] = t;                                       \
 134         n = a;                                                  \
 135       } else                                                    \
 136         break;                                                  \
 137     }                                                           \
 138     return r;                                                   \
 139   }                                                             \
 140                                                                 \
 141   struct heap_swallow_semicolon                                 \
 142
 143
 144 #endif /* PQUEUE_H */
 145
 146 /*
 147 Local Variables:
 148 c-basic-offset:2
 149 comment-column:40
 150 fill-column:79
 151 indent-tabs-mode:nil
 152 End:
 153 */