[thirdparty/bird.git] / lib / heap.h

/*
 *	UCW Library -- Universal Heap Macros
 *
 *	(c) 2001 Martin Mares <mj@ucw.cz>
 *	(c) 2005 Tomas Valla <tom@ucw.cz>
 *
 *	This software may be freely distributed and used according to the terms
 *	of the GNU Lesser General Public License.
 */

/**
 * [[intro]]
 * Introduction
 * ------------
 *
 * Binary heap is a simple data structure, which for example supports efficient insertions, deletions
 * and access to the minimal inserted item. We define several macros for such operations.
 * Note that because of simplicity of heaps, we have decided to define direct macros instead
 * of a <<generic:,macro generator>> as for several other data structures in the Libucw.
 *
 * A heap is represented by a number of elements and by an array of values. Beware that we
 * index this array from one, not from zero as do the standard C arrays.
 *
 * Most macros use these parameters:
 *
 * - @type - the type of elements
 * - @num - a variable (signed or unsigned integer) with the number of elements
 * - @heap - a C array of type @type; the heap is stored in `heap[1] .. heap[num]`; `heap[0]` is unused
 * - @less - a callback to compare two element values; `less(x, y)` shall return a non-zero value iff @x is lower than @y
 * - @swap - a callback to swap two array elements; `swap(heap, i, j, t)` must swap `heap[i]` with `heap[j]` with possible help of temporary variable @t (type @type).
 *
 * A valid heap must follow these rules:
 *
 * - `num >= 0`
 * - `heap[i] >= heap[i / 2]` for each `i` in `[2, num]`
 *
 * The first element `heap[1]` is always lower or equal to all other elements.
 *
 * [[macros]]
 * Macros
 * ------
 */

/* For internal usage. */
#define HEAP_BUBBLE_DOWN_J(heap,num,less,swap)						\
  for (;;)										\
    {											\
      _l = 2*_j;									\
      if (_l > num)									\
	break;										\
      if (less(heap[_j],heap[_l]) && (_l == num || less(heap[_j],heap[_l+1])))		\
	break;										\
      if (_l != num && less(heap[_l+1],heap[_l]))					\
	_l++;										\
      swap(heap,_j,_l,x);								\
      _j = _l;										\
    }

/* For internal usage. */
#define HEAP_BUBBLE_UP_J(heap,num,less,swap)						\
  while (_j > 1)									\
    {											\
      _u = _j/2;									\
      if (less(heap[_u], heap[_j]))							\
	break;										\
      swap(heap,_u,_j,x);								\
      _j = _u;										\
    }

/**
 * Shuffle the unordered array @heap of @num elements to become a valid heap. The time complexity is linear.
 **/
#define HEAP_INIT(heap,num,type,less,swap)						\
  do {											\
    uint _i = num;									\
    uint _j, _l;										\
    type x;										\
    while (_i >= 1)									\
      {											\
	_j = _i;									\
        HEAP_BUBBLE_DOWN_J(heap,num,less,swap)						\
	_i--;										\
      }											\
  } while(0)

/**
 * Delete the minimum element `heap[1]` in `O(log(n))` time.
 * The removed value is moved just after the resulting heap (`heap[num + 1]`).
 **/
#define HEAP_DELMIN(heap,num,type,less,swap)						\
  do {											\
    uint _j, _l;										\
    type x;										\
    swap(heap,1,num,x);									\
    num--;										\
    _j = 1;										\
    HEAP_BUBBLE_DOWN_J(heap,num,less,swap);						\
  } while(0)

/**
 * Insert `heap[num]` in `O(log(n))` time. The value of @num must be increased before.
 **/
#define HEAP_INSERT(heap,num,type,less,swap)						\
  do {											\
    uint _j, _u;										\
    type x;										\
    _j = num;										\
    HEAP_BUBBLE_UP_J(heap,num,less,swap);						\
  } while(0)

/**
 * If you need to increase the value of `heap[pos]`, just do it and then call this macro to rebuild the heap.
 * Only `heap[pos]` can be changed, the rest of the array must form a valid heap.
 * The time complexity is `O(log(n))`.
 **/
#define HEAP_INCREASE(heap,num,type,less,swap,pos)					\
  do {											\
    uint _j, _l;										\
    type x;										\
    _j = pos;										\
    HEAP_BUBBLE_DOWN_J(heap,num,less,swap);						\
  } while(0)

/**
 * If you need to decrease the value of `heap[pos]`, just do it and then call this macro to rebuild the heap.
 * Only `heap[pos]` can be changed, the rest of the array must form a valid heap.
 * The time complexity is `O(log(n))`.
 **/
#define HEAP_DECREASE(heap,num,type,less,swap,pos)					\
  do {											\
    uint _j, _u;										\
    type x;										\
    _j = pos;										\
    HEAP_BUBBLE_UP_J(heap,num,less,swap);						\
  } while(0)

/**
 * Delete `heap[pos]` in `O(log(n))` time.
 **/
#define HEAP_DELETE(heap,num,type,less,swap,pos)					\
  do {											\
    uint _j, _l, _u;									\
    type x;										\
    _j = pos;										\
    swap(heap,_j,num,x);								\
    num--;										\
    if (less(heap[_j], heap[num+1]))							\
      HEAP_BUBBLE_UP_J(heap,num,less,swap)						\
    else										\
      HEAP_BUBBLE_DOWN_J(heap,num,less,swap);						\
  } while(0)

/**
 * Default swapping macro.
 **/
#define HEAP_SWAP(heap,a,b,t) (t=heap[a], heap[a]=heap[b], heap[b]=t)
Commit	Line	Data
bf139664 OZ	1	/*
	2	* UCW Library -- Universal Heap Macros
	3	*
	4	* (c) 2001 Martin Mares <mj@ucw.cz>
	5	* (c) 2005 Tomas Valla <tom@ucw.cz>
	6	*
	7	* This software may be freely distributed and used according to the terms
	8	* of the GNU Lesser General Public License.
	9	*/
	10
	11	/**
	12	* [[intro]]
	13	* Introduction
	14	* ------------
	15	*
	16	* Binary heap is a simple data structure, which for example supports efficient insertions, deletions
	17	* and access to the minimal inserted item. We define several macros for such operations.
	18	* Note that because of simplicity of heaps, we have decided to define direct macros instead
	19	* of a <<generic:,macro generator>> as for several other data structures in the Libucw.
	20	*
	21	* A heap is represented by a number of elements and by an array of values. Beware that we
	22	* index this array from one, not from zero as do the standard C arrays.
	23	*
	24	* Most macros use these parameters:
	25	*
	26	* - @type - the type of elements
	27	* - @num - a variable (signed or unsigned integer) with the number of elements
	28	* - @heap - a C array of type @type; the heap is stored in `heap[1] .. heap[num]`; `heap[0]` is unused
	29	* - @less - a callback to compare two element values; `less(x, y)` shall return a non-zero value iff @x is lower than @y
	30	* - @swap - a callback to swap two array elements; `swap(heap, i, j, t)` must swap `heap[i]` with `heap[j]` with possible help of temporary variable @t (type @type).
	31	*
	32	* A valid heap must follow these rules:
	33	*
	34	* - `num >= 0`
	35	* - `heap[i] >= heap[i / 2]` for each `i` in `[2, num]`
	36	*
	37	* The first element `heap[1]` is always lower or equal to all other elements.
	38	*
	39	* [[macros]]
	40	* Macros
	41	* ------
	42	*/
	43
	44	/* For internal usage. */
	45	#define HEAP_BUBBLE_DOWN_J(heap,num,less,swap) \
	46	for (;;) \
	47	{ \
	48	_l = 2*_j; \
	49	if (_l > num) \
	50	break; \
	51	if (less(heap[_j],heap[_l]) && (_l == num \|\| less(heap[_j],heap[_l+1]))) \
	52	break; \
	53	if (_l != num && less(heap[_l+1],heap[_l])) \
	54	_l++; \
	55	swap(heap,_j,_l,x); \
	56	_j = _l; \
	57	}
	58
	59	/* For internal usage. */
	60	#define HEAP_BUBBLE_UP_J(heap,num,less,swap) \
	61	while (_j > 1) \
	62	{ \
	63	_u = _j/2; \
	64	if (less(heap[_u], heap[_j])) \
65	break; \
66	swap(heap,_u,_j,x); \
67	_j = _u; \
68	}
69
70	/**
71	* Shuffle the unordered array @heap of @num elements to become a valid heap. The time complexity is linear.
72	**/
73	#define HEAP_INIT(heap,num,type,less,swap) \
74	do { \
6a8d3f1c OZ	75	uint _i = num; \
6a8d3f1c OZ	76	uint _j, _l; \
bf139664 OZ	77	type x; \
	78	while (_i >= 1) \
	79	{ \
	80	_j = _i; \
	81	HEAP_BUBBLE_DOWN_J(heap,num,less,swap) \
	82	_i--; \
	83	} \
	84	} while(0)
	85
	86	/**
	87	* Delete the minimum element `heap[1]` in `O(log(n))` time.
	88	* The removed value is moved just after the resulting heap (`heap[num + 1]`).
	89	**/
	90	#define HEAP_DELMIN(heap,num,type,less,swap) \
	91	do { \
6a8d3f1c	92	uint _j, _l; \
bf139664 OZ	93	type x; \
	94	swap(heap,1,num,x); \
	95	num--; \
	96	_j = 1; \
	97	HEAP_BUBBLE_DOWN_J(heap,num,less,swap); \
	98	} while(0)
	99
	100	/**
	101	* Insert `heap[num]` in `O(log(n))` time. The value of @num must be increased before.
	102	**/
	103	#define HEAP_INSERT(heap,num,type,less,swap) \
	104	do { \
6a8d3f1c	105	uint _j, _u; \
bf139664 OZ	106	type x; \
	107	_j = num; \
	108	HEAP_BUBBLE_UP_J(heap,num,less,swap); \
	109	} while(0)
	110
	111	/**
	112	* If you need to increase the value of `heap[pos]`, just do it and then call this macro to rebuild the heap.
	113	* Only `heap[pos]` can be changed, the rest of the array must form a valid heap.
	114	* The time complexity is `O(log(n))`.
	115	**/
	116	#define HEAP_INCREASE(heap,num,type,less,swap,pos) \
	117	do { \
6a8d3f1c	118	uint _j, _l; \
bf139664 OZ	119	type x; \
	120	_j = pos; \
	121	HEAP_BUBBLE_DOWN_J(heap,num,less,swap); \
	122	} while(0)
	123
	124	/**
	125	* If you need to decrease the value of `heap[pos]`, just do it and then call this macro to rebuild the heap.
	126	* Only `heap[pos]` can be changed, the rest of the array must form a valid heap.
	127	* The time complexity is `O(log(n))`.
	128	**/
	129	#define HEAP_DECREASE(heap,num,type,less,swap,pos) \
	130	do { \
6a8d3f1c	131	uint _j, _u; \
bf139664 OZ	132	type x; \
	133	_j = pos; \
	134	HEAP_BUBBLE_UP_J(heap,num,less,swap); \
	135	} while(0)
	136
	137	/**
	138	* Delete `heap[pos]` in `O(log(n))` time.
	139	**/
	140	#define HEAP_DELETE(heap,num,type,less,swap,pos) \
	141	do { \
6a8d3f1c	142	uint _j, _l, _u; \
bf139664 OZ	143	type x; \
	144	_j = pos; \
	145	swap(heap,_j,num,x); \
	146	num--; \
	147	if (less(heap[_j], heap[num+1])) \
	148	HEAP_BUBBLE_UP_J(heap,num,less,swap) \
	149	else \
	150	HEAP_BUBBLE_DOWN_J(heap,num,less,swap); \
	151	} while(0)
	152
	153	/**
	154	* Default swapping macro.
	155	**/
	156	#define HEAP_SWAP(heap,a,b,t) (t=heap[a], heap[a]=heap[b], heap[b]=t)