1 /****************************************************************\
2 *                                                                *
3 *  Priority queue library using pairing heaps.                   *
4 *                                                                *
5 *  Guy St.C. Slater..   mailto:guy@ebi.ac.uk                     *
6 *  Copyright (C) 2000-2009.  All Rights Reserved.                *
7 *                                                                *
8 *  This source code is distributed under the terms of the        *
9 *  GNU General Public License, version 3. See the file COPYING   *
10 *  or http://www.gnu.org/licenses/gpl.txt for details            *
11 *                                                                *
12 *  If you use this code, please keep this notice intact.         *
13 *                                                                *
14 \****************************************************************/
15 
16 #include "pqueue.h"
17 
PQueueSet_create(void)18 PQueueSet *PQueueSet_create(void){
19     register PQueueSet *pq_set = g_new(PQueueSet, 1);
20     pq_set->pq_recycle = RecycleBin_create("PQueue",
21                                            sizeof(PQueue), 64);
22     pq_set->node_recycle = RecycleBin_create("PQueue_Node",
23                                            sizeof(PQueue), 64);
24     return pq_set;
25     }
26 
PQueueSet_destroy(PQueueSet * pq_set)27 void PQueueSet_destroy(PQueueSet *pq_set){
28     g_assert(pq_set);
29     RecycleBin_destroy(pq_set->pq_recycle);
30     RecycleBin_destroy(pq_set->node_recycle);
31     g_free(pq_set);
32     return;
33     }
34 
PQueue_create(PQueueSet * pq_set,PQueue_Compare_Func comp_func,gpointer user_data)35 PQueue *PQueue_create(PQueueSet *pq_set,
36                       PQueue_Compare_Func comp_func,
37                       gpointer user_data){
38     register PQueue *pq;
39     g_assert(pq_set);
40     g_assert(comp_func);
41     pq = RecycleBin_alloc(pq_set->pq_recycle);
42     pq->root = NULL;
43     pq->total = 0;
44     pq->comp_func = comp_func;
45     pq->set = pq_set;
46     pq->user_data = user_data;
47     return pq;
48     }
49 
PQueue_Node_destroy(PQueueSet * pq_set,PQueue_Node * pqn)50 static void PQueue_Node_destroy(PQueueSet *pq_set, PQueue_Node *pqn){
51     if(pqn){
52         PQueue_Node_destroy(pq_set, pqn->left);
53         PQueue_Node_destroy(pq_set, pqn->next);
54         RecycleBin_recycle(pq_set->node_recycle, pqn);
55         }
56     return;
57     }
58 
PQueue_Node_destroy_with_func(PQueueSet * pq_set,PQueue_Node * pqn,PQueue_Free_Func free_func,gpointer * user_data)59 static void PQueue_Node_destroy_with_func(PQueueSet *pq_set,
60                    PQueue_Node *pqn,
61                    PQueue_Free_Func free_func, gpointer *user_data){
62     if(pqn){
63         PQueue_Node_destroy_with_func(pq_set, pqn->left,
64                                       free_func, user_data);
65         PQueue_Node_destroy_with_func(pq_set, pqn->next,
66                                       free_func, user_data);
67         free_func(pqn->data, user_data);
68         RecycleBin_recycle(pq_set->node_recycle, pqn);
69         }
70     return;
71     }
72 
PQueue_destroy(PQueue * pq,PQueue_Free_Func free_func,gpointer user_data)73 void PQueue_destroy(PQueue *pq, PQueue_Free_Func free_func,
74                     gpointer user_data){
75     if(free_func)
76         PQueue_Node_destroy_with_func(pq->set, pq->root,
77                                       free_func, user_data);
78     else
79         PQueue_Node_destroy(pq->set, pq->root);
80     RecycleBin_recycle(pq->set->pq_recycle, pq);
81     return;
82     }
83 
84 #ifndef Swap
85 #define Swap(x,y,temp) ((temp)=(x),(x)=(y),(y)=(temp))
86 #endif /* Swap */
87 
PQueue_Node_order(PQueue * pq,PQueue_Node * a,PQueue_Node * b)88 static PQueue_Node *PQueue_Node_order(PQueue *pq,
89                     PQueue_Node *a, PQueue_Node *b){
90     register PQueue_Node *tmp;
91     g_assert(a);
92     g_assert(b);
93     if(pq->comp_func(a->data, b->data, pq->user_data)){
94         /* Add b before a */
95         a->next = b->next;
96         if(a->next)
97             a->next->prev = a;
98         Swap(a, b, tmp);
99     } else { /* Add a before b */
100         b->prev = a->prev;
101         }
102     a->prev = b;
103     a->next = b->left;
104     if(a->next)
105         a->next->prev = a;
106     b->left = a;
107     return b;
108     }
109 
PQueue_push(PQueue * pq,gpointer data)110 PQueue_Node *PQueue_push(PQueue *pq, gpointer data){
111     register PQueue_Node *pqn = RecycleBin_alloc(pq->set->node_recycle);
112     /* Create empty heap and meld with existing heap */
113     pqn->data = data;
114     pqn->left = pqn->next = pqn->prev = NULL;
115     if(pq->root)
116         pq->root = PQueue_Node_order(pq, pq->root, pqn);
117     else
118         pq->root = pqn; /* Is the first node */
119     pq->total++;
120     return pqn;
121     }
122 
PQueue_Node_extract(PQueue_Node * pqn)123 static void PQueue_Node_extract(PQueue_Node *pqn){
124     if(pqn->next)
125         pqn->next->prev = pqn->prev;
126     if(pqn->prev->left == pqn)
127         pqn->prev->left = pqn->next;
128     else
129         pqn->prev->next = pqn->next;
130     pqn->next = NULL;
131     return;
132     }
133 
PQueue_raise(PQueue * pq,PQueue_Node * pqn)134 void PQueue_raise(PQueue *pq, PQueue_Node *pqn){
135     if(pq->root == pqn) /* If the root node */
136         return;
137     PQueue_Node_extract(pqn);
138     pq->root = PQueue_Node_order(pq, pq->root, pqn);
139     return;
140     }
141 
PQueue_change(PQueue * pq,PQueue_Node * pqn)142 void PQueue_change(PQueue *pq, PQueue_Node *pqn){
143     register PQueue_Node *npqn;
144     npqn = PQueue_push(pq, PQueue_remove(pq, pqn));
145     g_assert(npqn == pqn);
146     return;
147     }
148 
PQueue_Node_combine(PQueue * pq,PQueue_Node * pqn)149 static PQueue_Node *PQueue_Node_combine(PQueue *pq,
150                                         PQueue_Node *pqn){
151     register gint i, count;
152     register GPtrArray *combine;
153     register PQueue_Node *npqn;
154     if(!pqn->next){ /* Single member */
155         return pqn;
156         }
157     combine = g_ptr_array_new();
158     for(count = 0; pqn; count++){
159         g_ptr_array_add(combine, pqn);
160         pqn->prev->next = NULL; /* Break links */
161         pqn = pqn->next;
162         }
163     count--;
164     for(i = 0; i < count; i+=2)
165         combine->pdata[i] = PQueue_Node_order(pq, combine->pdata[i],
166                                                   combine->pdata[i+1]);
167     if(!(count&1)) /* Pick up spare if odd count */
168         combine->pdata[i-2] = PQueue_Node_order(pq, combine->pdata[i-2],
169                                                     combine->pdata[i]);
170     for(i-=2; i>=2; i-=2)
171         combine->pdata[i-2] = PQueue_Node_order(pq, combine->pdata[i-2],
172                                                     combine->pdata[i]);
173     npqn = combine->pdata[0];
174     g_ptr_array_free(combine, TRUE);
175     return npqn;
176     }
177 
PQueue_pop(PQueue * pq)178 gpointer PQueue_pop(PQueue *pq){
179     register PQueue_Node *pqn = pq->root;
180     register gpointer data;
181     if(!pq->root)
182         return NULL; /* Queue is empty */
183     data = pq->root->data;
184     g_assert((pq->total <= 1) || pq->root->left);
185     pq->root = pq->root->left
186              ? PQueue_Node_combine(pq, pq->root->left)
187              : NULL;
188     g_assert(pqn);
189     RecycleBin_recycle(pq->set->node_recycle, pqn);
190     if(!--pq->total) /* Set root as NULL if PQueue is now empty */
191         pq->root = NULL;
192     return data;
193     }
194 
PQueue_join(PQueue * a,PQueue * b)195 PQueue *PQueue_join(PQueue *a, PQueue *b){
196     g_assert(a->set == b->set);
197     g_assert(a->comp_func == b->comp_func);
198     g_assert(a->user_data == b->user_data);
199     a->root = PQueue_Node_combine(a, b->root);
200     a->total += b->total;
201     RecycleBin_recycle(a->set->pq_recycle, b);
202     return a;
203     }
204 
PQueue_remove(PQueue * pq,PQueue_Node * pqn)205 gpointer PQueue_remove(PQueue *pq, PQueue_Node *pqn){
206     register gpointer data = pqn->data;
207     register PQueue_Node *nb;
208     g_assert(pqn);
209     g_assert(pq->root);
210     if(pqn == pq->root)
211         return PQueue_pop(pq);
212     g_assert(pq->total > 1);
213     PQueue_Node_extract(pqn);
214     if(--pq->total){
215         if(pqn->left){
216             nb = PQueue_Node_combine(pq, pqn->left);
217             pq->root = PQueue_Node_order(pq, pq->root, nb);
218             }
219     } else {
220         pq->root = NULL;
221         }
222     RecycleBin_recycle(pq->set->node_recycle, pqn);
223     return data;
224     }
225 
PQueue_traverse_recur(PQueue * pq,PQueue_Node * pqn,PQueue_Traverse_Func tf,gpointer user_data,gboolean * stop)226 static void PQueue_traverse_recur(PQueue *pq, PQueue_Node *pqn,
227                        PQueue_Traverse_Func tf, gpointer user_data,
228                        gboolean *stop){
229     if((!pqn || (*stop)))
230         return;
231     (*stop) = tf(pqn->data, user_data);
232     PQueue_traverse_recur(pq, pqn->left, tf, user_data, stop);
233     PQueue_traverse_recur(pq, pqn->next, tf, user_data, stop);
234     return;
235     }
236 
PQueue_traverse(PQueue * pq,PQueue_Traverse_Func tf,gpointer user_data)237 void PQueue_traverse(PQueue *pq, PQueue_Traverse_Func tf,
238                      gpointer user_data){
239     gboolean stop = FALSE;
240     PQueue_traverse_recur(pq, pq->root, tf, user_data, &stop);
241     return;
242     }
243 
244