]> mj.ucw.cz Git - moe.git/blob - lib/binheap.h
Added libucw from Sherlock v3.12.2.
[moe.git] / lib / binheap.h
1 /*
2  *      UCW Library -- Binomial Heaps
3  *
4  *      (c) 2003 Martin Mares <mj@ucw.cz>
5  *
6  *      This software may be freely distributed and used according to the terms
7  *      of the GNU Lesser General Public License.
8  */
9
10 /*
11  *  This is a generic implementation of Binomial Heaps. Each time you include
12  *  this file with parameters set in the corresponding preprocessor macros
13  *  as described below, it generates functions for manipulating the particular
14  *  version of the binomial heap.
15  *
16  *  You need to specify:
17  *
18  *  BH_PREFIX(x)        macro to add a name prefix (used on all global names
19  *                      defined by the hash table generator). All further
20  *                      names mentioned here except for macro names will be
21  *                      implicitly prefixed.
22  *
23  *  Then you continue by including "lib/binheap-node.h" which defines struct bh_node
24  *  and struct bh_root (both without prefix). The heap elements are always allocated by
25  *  you and they must include struct bh_node which serves as a handle used for all
26  *  the heap functions and it contains all information needed for heap-keeping.
27  *  The heap itself is also allocated by you and it's represented by struct bh_heap.
28  *
29  *  When you have the declaration of heap nodes, you continue with defining:
30  *
31  *  less(p,q)           returns 1 if the key corresponding to bh_node *p
32  *                      is less than the one corresponding to *q.
33  *
34  *  Then specify what operations you request:
35  *
36  *  <always defined>    init(heap*) -- initialize the heap.
37  *  BH_WANT_INSERT      insert(heap*, node*) -- insert the node to the heap.
38  *  BH_WANT_FINDMIN     node *findmin(heap*) -- find node with minimum key.
39  *  BH_WANT_DELETEMIN   node *deletemin(heap*) -- findmin and delete the node.
40  *
41  *  Then include "lib/binheap.h" and voila, you have a binomial heap
42  *  suiting all your needs (at least those which you've revealed :) ).
43  *
44  *  You also get a iterator macro at no extra charge:
45  *
46  *  BH_FOR_ALL(bh_prefix, hash*, variable)
47  *    {
48  *      // node *variable gets declared automatically
49  *      do_something_with_node(variable);
50  *      // use BH_BREAK and BH_CONTINUE instead of break and continue
51  *      // you must not alter contents of the hash table here
52  *    }
53  *  BH_END_FOR;
54  *
55  *  After including this file, all parameter macros are automatically
56  *  undef'd.
57  */
58
59 #define BH_NODE struct bh_node
60 #define BH_HEAP struct bh_heap
61
62 static void
63 BH_PREFIX(merge)(BH_NODE *a, BH_NODE *b)
64 {
65   BH_NODE **pp = &a->first_son;
66   BH_NODE *q = b->first_son;
67   BH_NODE *p, *r, *s;
68
69   while ((p = *pp) && q)
70     {
71       /* p,q are the next nodes of a,b; pp points to where p is linked */
72       if (p->order < q->order)          /* p is smaller => skip it */
73         pp = &p->next_sibling;
74       else if (p->order > q->order)     /* q is smaller => insert it before p */
75         {
76           r = q;
77           q = q->next_sibling;
78           r->next_sibling = p;
79           *pp = r;
80           pp = &r->next_sibling;
81         }
82       else                              /* p and q are of the same order => need to merge them */
83         {
84           if (BH_PREFIX(less)(p, q))    /* we'll hang r below s */
85             {
86               r = q;
87               s = p;
88             }
89           else
90             {
91               r = p;
92               s = q;
93             }
94           *pp = p->next_sibling;        /* unlink p,q from their lists */
95           q = q->next_sibling;
96
97           if (s->last_son)              /* merge r to s, increasing order */
98             s->last_son->next_sibling = r;
99           else
100             s->first_son = r;
101           s->last_son = r;
102           s->order++;
103           r->next_sibling = NULL;
104
105           if (!q || q->order > s->order) /* put the result into the b's list if possible */
106             {
107               s->next_sibling = q;
108               q = s;
109             }
110           else                          /* otherwise put the result to the a's list */
111             {
112               p = s->next_sibling = *pp;
113               *pp = s;
114               if (p && p->order == s->order) /* 3-collision */
115                 pp = &s->next_sibling;
116             }
117         }
118     }
119   if (!p)
120     *pp = q;
121 }
122
123 #ifdef BH_WANT_INSERT
124 static void
125 BH_PREFIX(insert)(BH_HEAP *heap, BH_NODE *a)
126 {
127   BH_NODE sh;
128
129   sh.first_son = a;
130   a->first_son = a->last_son = a->next_sibling = NULL;
131   BH_PREFIX(merge)(&heap->root, &sh);
132 }
133 #endif
134
135 #ifdef BH_WANT_FINDMIN
136 static BH_NODE *
137 BH_PREFIX(findmin)(BH_HEAP *heap)
138 {
139   BH_NODE *p, *best;
140
141   best = NULL;
142   for (p=heap->root.first_son; p; p=p->next_sibling)
143     if (!best || BH_PREFIX(less)(p, best))
144       best = p;
145   return best;
146 }
147 #endif
148
149 #ifdef BH_WANT_DELETEMIN
150 static BH_NODE *
151 BH_PREFIX(deletemin)(BH_HEAP *heap)
152 {
153   BH_NODE *p, **pp, **bestp;
154
155   bestp = NULL;
156   for (pp=&heap->root.first_son; p=*pp; pp=&p->next_sibling)
157     if (!bestp || BH_PREFIX(less)(p, *bestp))
158       bestp = pp;
159   if (!bestp)
160     return NULL;
161
162   p = *bestp;
163   *bestp = p->next_sibling;
164   BH_PREFIX(merge)(&heap->root, p);
165   return p;
166 }
167 #endif
168
169 static inline void
170 BH_PREFIX(init)(BH_HEAP *heap)
171 {
172   bzero(heap, sizeof(*heap));
173 }
174
175 #ifndef BH_FOR_ALL
176
177 #define BH_FOR_ALL(bh_px, bh_heap, bh_var)      \
178 do {                                            \
179   struct bh_node *bh_stack[32];                 \
180   uns bh_sp = 0;                                \
181   if (bh_stack[0] = (bh_heap)->root.first_son)  \
182     bh_sp++;                                    \
183   while (bh_sp) {                               \
184     struct bh_node *bh_var = bh_stack[--bh_sp]; \
185     if (bh_var->next_sibling)                   \
186       bh_stack[bh_sp++] = bh_var->next_sibling; \
187     if (bh_var->first_son)                      \
188       bh_stack[bh_sp++] = bh_var->first_son;
189 #define BH_END_FOR                              \
190   }                                             \
191 } while (0)
192
193 #define BH_BREAK { bh_sp=0; break; }
194 #define BH_CONTINUE continue
195
196 #endif
197
198 #undef BH_PREFIX
199 #undef BH_NODE
200 #undef BH_HEAP
201 #undef BH_WANT_INSERT
202 #undef BH_WANT_FINDMIN
203 #undef BH_WANT_DELETEMIN