Return to heap.h CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird2 / lib

bird2 ver 2.0.7

    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 {											\
   75:     uint _i = num;									\
   76:     uint _j, _l;										\
   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 {											\
   92:     uint _j, _l;										\
   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 {											\
  105:     uint _j, _u;										\
  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 {											\
  118:     uint _j, _l;										\
  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 {											\
  131:     uint _j, _u;										\
  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 {											\
  142:     uint _j, _l, _u;									\
  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)