Annotation of embedaddon/bird/lib/heap.h, revision 1.1

1.1     ! misho       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)

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>