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

   1 /*
   2  * This file is part of DisOrder.
   3  * Copyright (C) 2007 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 2 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, but
  11  * WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * 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, write to the Free Software
  17  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
  18  * USA
  19  */
  20 /** @file lib/heap.h @brief Binary heap template */
  21
  22 #ifndef HEAP_H
  23 #define HEAP_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);                                             \
  89     return heap->vec[0];                                                \
  90   }                                                                     \
  91                                                                         \
  92   static void NAME##_insert(struct NAME *heap, NAME##_element elt) {    \
  93     int n = heap->nvec;                                                 \
  94     NAME##_append(heap, elt);                                           \
  95     while(n > 0) {                                                      \
  96       const int p = (n-1)/2;                                            \
  97       if(!LT(heap->vec[n],heap->vec[p]))                                \
  98         break;                                                          \
  99       else {                                                            \
 100         const NAME##_element t = heap->vec[n];                          \
 101         heap->vec[n] = heap->vec[p];                                    \
 102         heap->vec[p] = t;                                               \
 103         n = p;                                                          \
 104       }                                                                 \
 105     }                                                                   \
 106   }                                                                     \
 107                                                                         \
 108   static NAME##_element NAME##_remove(struct NAME *heap) {              \
 109     int n = 0;                                                          \
 110     NAME##_element r;                                                   \
 111                                                                         \
 112     assert(heap->nvec > 0);                                             \
 113     r = heap->vec[0];                                                   \
 114     heap->vec[0] = heap->vec[--heap->nvec];                             \
 115     while(2 * n + 1 < heap->nvec) {                                     \
 116       int a = 2 * n + 1;                                                \
 117       int b = 2 * n + 2;                                                \
 118                                                                         \
 119       if(b < heap->nvec && LT(heap->vec[b],heap->vec[a])) {             \
 120         ++a;                                                            \
 121         --b;                                                            \
 122       }                                                                 \
 123       if(LT(heap->vec[a], heap->vec[n])) {                              \
 124         const NAME##_element t = heap->vec[n];                          \
 125         heap->vec[n] = heap->vec[a];                                    \
 126         heap->vec[a] = t;                                               \
 127         n = a;                                                          \
 128       } else                                                            \
 129         break;                                                          \
 130     }                                                                   \
 131     return r;                                                           \
 132   }                                                                     \
 133                                                                         \
 134   struct heap_swallow_semicolon
 135
 136
 137 #endif /* PQUEUE_H */
 138
 139 /*
 140 Local Variables:
 141 c-basic-offset:2
 142 comment-column:40
 143 fill-column:79
 144 indent-tabs-mode:nil
 145 End:
 146 */