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 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 #include "vector.h"
  26
  27 /** @brief Binary heap template.
  28  * @param NAME name of type to define
  29  * @param ETYPE element type
  30  * @param LT comparison function
  31  *
  32  * Defines a heap type called @c struct @p NAME and a number of functions to
  33  * operate on it.
  34  *
  35  * The element type of the heap will be @p ETYPE.
  36  *
  37  * @p LT will be called with two arguments of type @p ETYPE, and
  38  * implements a less-than comparison.
  39  *
  40  * The functions defined are:
  41  * - NAME_init(h) which initializes an empty heap at @p h
  42  * - NAME_count(h) which returns the number of elements in the heap
  43  * - NAME_insert(h, e) which inserts @p e into @p h
  44  * - NAME_first(g) which returns the least element of @p h
  45  * - NAME_remove(g) which removes and returns the least element of @p h
  46  *
  47  * The heap is implemented as a vector.  Element 0 is the root.  For any
  48  * element \f$i\f$, its children are elements \f$2i+1\f$ and \f$2i+2\f$ and
  49  * consequently its parent (if it is not the root) is
  50  * \f$\lfloor(i-1)/2\rfloor\f$.
  51  *
  52  * The insert and remove operations maintain two invariants: the @b
  53  * shape property (all levels of the tree are fully filled except the
  54  * deepest, and that is filled from the left), and the @b heap
  55  * property, that every element compares less than or equal to its
  56  * children.
  57  *
  58  * The shape property implies that the array representation has no gaps, which
  59  * is convenient.  It is preserved by only adding or removing the final element
  60  * of the array and otherwise only modifying the array by swapping pairs of
  61  * elements.
  62  *
  63  * @b Insertion works by inserting the new element \f$N\f$ at the end and
  64  * bubbling it up the tree until it is in the right order for its branch.
  65  * - If, for its parent \f$P\f$, \f$P \le N\f$ then it is already in the right
  66  * place and the insertion is complete.
  67  * - Otherwise \f$P > N\f$ and so \f$P\f$ and \f$N\f$ are exchanged.  If
  68  * \f$P\f$ has a second child, \f$C\f$, then \f$N < P < C\f$ so the heap
  69  * property is now satisfied from \f$P\f$ down.
  70  *
  71  * @b Removal works by first swapping the root with the final element (and then
  72  * removing it) and then bubbling the new root \f$N\f$ down the tree until it
  73  * finds its proper place.  At each stage it is compared with its children
  74  * \f$A\f$ and \f$B\f$.
  75  * - If \f$N \le A\f$ and \f$N \le B\f$ then it is in the
  76  * right place already.
  77  * - Otherwise \f$N > A\f$ or \f$N > B\f$ (or both).  WLOG \f$A \le B\f$.
  78  * \f$N\f$ and \f$A\f$ are exchanged, so now \f$A\f$ has children \f$N\f$ and
  79  * \f$B\f$.  \f$A < N\f$ and \f$A \le B\f$.
  80  */
  81 #define HEAP_TYPE(NAME, ETYPE, LT)                                      \
  82   typedef ETYPE NAME##_element;                                         \
  83   VECTOR_TYPE(NAME, NAME##_element, xrealloc);                          \
  84                                                                         \
  85   static inline int NAME##_count(struct NAME *heap) {                   \
  86     return heap->nvec;                                                  \
  87   }                                                                     \
  88                                                                         \
  89   static inline NAME##_element NAME##_first(struct NAME *heap) {        \
  90     assert(heap->nvec > 0 && "_first");                                 \
  91     return heap->vec[0];                                                \
  92   }                                                                     \
  93                                                                         \
  94   void NAME##_insert(struct NAME *heap, NAME##_element elt);            \
  95   NAME##_element NAME##_remove(struct NAME *heap);                      \
  96                                                                         \
  97   struct heap_swallow_semicolon
  98
  99 /** @brief External-linkage definitions for @ref HEAP_TYPE */
 100 #define HEAP_DEFINE(NAME, ETYPE, LT)                            \
 101   void NAME##_insert(struct NAME *heap, NAME##_element elt) {   \
 102     int n = heap->nvec;                                         \
 103     NAME##_append(heap, elt);                                   \
 104     while(n > 0) {                                              \
 105       const int p = (n-1)/2;                                    \
 106       if(!LT(heap->vec[n],heap->vec[p]))                        \
 107         break;                                                  \
 108       else {                                                    \
 109         const NAME##_element t = heap->vec[n];                  \
 110         heap->vec[n] = heap->vec[p];                            \
 111         heap->vec[p] = t;                                       \
 112         n = p;                                                  \
 113       }                                                         \
 114     }                                                           \
 115   }                                                             \
 116                                                                 \
 117   NAME##_element NAME##_remove(struct NAME *heap) {             \
 118     int n = 0;                                                  \
 119     NAME##_element r;                                           \
 120                                                                 \
 121     assert(heap->nvec > 0 && "_remove");                        \
 122     r = heap->vec[0];                                           \
 123     heap->vec[0] = heap->vec[--heap->nvec];                     \
 124     while(2 * n + 1 < heap->nvec) {                             \
 125       int a = 2 * n + 1;                                        \
 126       int b = 2 * n + 2;                                        \
 127                                                                 \
 128       if(b < heap->nvec && LT(heap->vec[b],heap->vec[a])) {     \
 129         ++a;                                                    \
 130         --b;                                                    \
 131       }                                                         \
 132       if(LT(heap->vec[a], heap->vec[n])) {                      \
 133         const NAME##_element t = heap->vec[n];                  \
 134         heap->vec[n] = heap->vec[a];                            \
 135         heap->vec[a] = t;                                       \
 136         n = a;                                                  \
 137       } else                                                    \
 138         break;                                                  \
 139     }                                                           \
 140     return r;                                                   \
 141   }                                                             \
 142                                                                 \
 143   struct heap_swallow_semicolon                                 \
 144
 145
 146 #endif /* PQUEUE_H */
 147
 148 /*
 149 Local Variables:
 150 c-basic-offset:2
 151 comment-column:40
 152 fill-column:79
 153 indent-tabs-mode:nil
 154 End:
 155 */