[disorder] / lib / heap.h

/*
 * This file is part of DisOrder.
 * Copyright (C) 2007 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 2 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, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
 * USA
 */
/** @file lib/heap.h @brief Binary heap template */

#ifndef HEAP_H
#define HEAP_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);                                             \
    return heap->vec[0];                                                \
  }                                                                     \
                                                                        \
  static 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;                                                          \
      }                                                                 \
    }                                                                   \
  }                                                                     \
                                                                        \
  static NAME##_element NAME##_remove(struct NAME *heap) {              \
    int n = 0;                                                          \
    NAME##_element r;                                                   \
                                                                        \
    assert(heap->nvec > 0);                                             \
    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	/*
	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	*/
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) { \
	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	\
033fd4e3 RK	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	*/