Statistics
| Branch: | Revision:

iof-bird / bird-2.0.1 / lib / heap.h @ 6b3f1a54

History | View | Annotate | Download (4.86 KB)

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)