[disorder] / lib / heap.h

/*
 * This file is part of DisOrder.
 * Copyright (C) 2007, 2008 Richard Kettlewell
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
/** @file lib/heap.h @brief Binary heap template */

#ifndef HEAP_H
#define HEAP_H

#include "vector.h"

/** @brief Binary heap template.
 * @param NAME name of type to define
 * @param ETYPE element type
 * @param LT comparison function
 *
 * Defines a heap type called @c struct @p NAME and a number of functions to
 * operate on it.
 *
 * The element type of the heap will be @p ETYPE.
 *
 * @p LT will be called with two arguments of type @p ETYPE, and
 * implements a less-than comparison.
 *
 * The functions defined are:
 * - NAME_init(h) which initializes an empty heap at @p h
 * - NAME_count(h) which returns the number of elements in the heap
 * - NAME_insert(h, e) which inserts @p e into @p h
 * - NAME_first(g) which returns the least element of @p h
 * - NAME_remove(g) which removes and returns the least element of @p h
 *
 * The heap is implemented as a vector.  Element 0 is the root.  For any
 * element \f$i\f$, its children are elements \f$2i+1\f$ and \f$2i+2\f$ and
 * consequently its parent (if it is not the root) is
 * \f$\lfloor(i-1)/2\rfloor\f$.
 * 
 * The insert and remove operations maintain two invariants: the @b
 * shape property (all levels of the tree are fully filled except the
 * deepest, and that is filled from the left), and the @b heap
 * property, that every element compares less than or equal to its
 * children.
 *
 * The shape property implies that the array representation has no gaps, which
 * is convenient.  It is preserved by only adding or removing the final element
 * of the array and otherwise only modifying the array by swapping pairs of
 * elements.
 *
 * @b Insertion works by inserting the new element \f$N\f$ at the end and
 * bubbling it up the tree until it is in the right order for its branch.
 * - If, for its parent \f$P\f$, \f$P \le N\f$ then it is already in the right
 * place and the insertion is complete.
 * - Otherwise \f$P > N\f$ and so \f$P\f$ and \f$N\f$ are exchanged.  If
 * \f$P\f$ has a second child, \f$C\f$, then \f$N < P < C\f$ so the heap
 * property is now satisfied from \f$P\f$ down.
 *
 * @b Removal works by first swapping the root with the final element (and then
 * removing it) and then bubbling the new root \f$N\f$ down the tree until it
 * finds its proper place.  At each stage it is compared with its children
 * \f$A\f$ and \f$B\f$.
 * - If \f$N \le A\f$ and \f$N \le B\f$ then it is in the
 * right place already.
 * - Otherwise \f$N > A\f$ or \f$N > B\f$ (or both).  WLOG \f$A \le B\f$.
 * \f$N\f$ and \f$A\f$ are exchanged, so now \f$A\f$ has children \f$N\f$ and
 * \f$B\f$.  \f$A < N\f$ and \f$A \le B\f$.
 */
#define HEAP_TYPE(NAME, ETYPE, LT)                                      \
  typedef ETYPE NAME##_element;                                         \
  VECTOR_TYPE(NAME, NAME##_element, xrealloc);                          \
                                                                        \
  static inline int NAME##_count(struct NAME *heap) {                   \
    return heap->nvec;                                                  \
  }                                                                     \
                                                                        \
  static inline NAME##_element NAME##_first(struct NAME *heap) {        \
    assert(heap->nvec > 0 && "_first");                                 \
    return heap->vec[0];                                                \
  }                                                                     \
                                                                        \
  void NAME##_insert(struct NAME *heap, NAME##_element elt);            \
  NAME##_element NAME##_remove(struct NAME *heap);                      \
                                                                        \
  struct heap_swallow_semicolon

/** @brief External-linkage definitions for @ref HEAP_TYPE */
#define HEAP_DEFINE(NAME, ETYPE, LT)                            \
  void NAME##_insert(struct NAME *heap, NAME##_element elt) {   \
    int n = heap->nvec;                                         \
    NAME##_append(heap, elt);                                   \
    while(n > 0) {                                              \
      const int p = (n-1)/2;                                    \
      if(!LT(heap->vec[n],heap->vec[p]))                        \
        break;                                                  \
      else {                                                    \
        const NAME##_element t = heap->vec[n];                  \
        heap->vec[n] = heap->vec[p];                            \
        heap->vec[p] = t;                                       \
        n = p;                                                  \
      }                                                         \
    }                                                           \
  }                                                             \
                                                                \
  NAME##_element NAME##_remove(struct NAME *heap) {             \
    int n = 0;                                                  \
    NAME##_element r;                                           \
                                                                \
    assert(heap->nvec > 0 && "_remove");                        \
    r = heap->vec[0];                                           \
    heap->vec[0] = heap->vec[--heap->nvec];                     \
    while(2 * n + 1 < heap->nvec) {                             \
      int a = 2 * n + 1;                                        \
      int b = 2 * n + 2;                                        \
                                                                \
      if(b < heap->nvec && LT(heap->vec[b],heap->vec[a])) {     \
        ++a;                                                    \
        --b;                                                    \
      }                                                         \
      if(LT(heap->vec[a], heap->vec[n])) {                      \
        const NAME##_element t = heap->vec[n];                  \
        heap->vec[n] = heap->vec[a];                            \
        heap->vec[a] = t;                                       \
        n = a;                                                  \
      } else                                                    \
        break;                                                  \
    }                                                           \
    return r;                                                   \
  }                                                             \
                                                                \
  struct heap_swallow_semicolon                                 \
  

#endif /* PQUEUE_H */

/*
Local Variables:
c-basic-offset:2
comment-column:40
fill-column:79
indent-tabs-mode:nil
End:
*/
Commit	Line	Data
033fd4e3 RK	1	/*
033fd4e3 RK	2	* This file is part of DisOrder.
5aff007d	3	* Copyright (C) 2007, 2008 Richard Kettlewell
033fd4e3	4	*
e7eb3a27	5	* This program is free software: you can redistribute it and/or modify
033fd4e3	6	* it under the terms of the GNU General Public License as published by
e7eb3a27	7	* the Free Software Foundation, either version 3 of the License, or
033fd4e3	8	* (at your option) any later version.
e7eb3a27 RK	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	*
033fd4e3	15	* You should have received a copy of the GNU General Public License
e7eb3a27	16	* along with this program. If not, see <http://www.gnu.org/licenses/>.
033fd4e3 RK	17	*/
	18	/** @file lib/heap.h @brief Binary heap template */
	19
	20	#ifndef HEAP_H
	21	#define HEAP_H
	22
05b75f8d RK	23	#include "vector.h"
05b75f8d RK	24
033fd4e3 RK	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	*/
b8956e9e RK	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) { \
4c672170	88	assert(heap->nvec > 0 && "_first"); \
b8956e9e RK	89	return heap->vec[0]; \
	90	} \
	91	\
8e3fe3d8	92	void NAME##_insert(struct NAME *heap, NAME##_element elt); \
8e3fe3d8	93	NAME##_element NAME##_remove(struct NAME *heap); \
b8956e9e	94	\
033fd4e3	95	struct heap_swallow_semicolon
8e3fe3d8	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	\
4c672170	119	assert(heap->nvec > 0 && "_remove"); \
8e3fe3d8	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 \
033fd4e3 RK	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	*/