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 #ifndef INCLUDED_PQUEUE_H
17 #define INCLUDED_PQUEUE_H
18 
19 #ifdef __cplusplus
20 extern "C" {
21 #endif /* __cplusplus */
22 
23 #include <glib.h>
24 #include "recyclebin.h"
25 
26 typedef struct PQueue_Node {
27               gpointer  data;
28     struct PQueue_Node *left;
29     struct PQueue_Node *next;
30     struct PQueue_Node *prev;
31 } PQueue_Node;
32 
33 typedef void (*PQueue_Free_Func)(gpointer data, gpointer user_data);
34 typedef gboolean (*PQueue_Compare_Func)(gpointer low, gpointer high,
35                                         gpointer user_data);
36 
37 typedef struct {
38     RecycleBin *pq_recycle;
39     RecycleBin *node_recycle;
40 } PQueueSet;
41 
42 typedef struct {
43             PQueue_Node  *root;      /* The root node       */
44                    gint   total;     /* Number of members   */
45     PQueue_Compare_Func   comp_func; /* Comparison function */
46               PQueueSet  *set;
47                gpointer   user_data;
48 } PQueue;
49 
50 PQueueSet *PQueueSet_create(void);
51      void  PQueueSet_destroy(PQueueSet *pq_set);
52 
53      PQueue *PQueue_create(PQueueSet *pq_set,
54                            PQueue_Compare_Func comp_func,
55                            gpointer user_data);
56        void  PQueue_destroy(PQueue *pq, PQueue_Free_Func free_func,
57                             gpointer user_data);
58 PQueue_Node *PQueue_push(PQueue *pq, gpointer data);
59        void  PQueue_raise(PQueue *pq, PQueue_Node *pqn);
60        void  PQueue_change(PQueue *pq, PQueue_Node *pqn);
61    gpointer  PQueue_pop(PQueue *pq);
62 
63  PQueue *PQueue_join(PQueue *a, PQueue *b);
64 gpointer PQueue_remove(PQueue *pq, PQueue_Node *pqn);
65 typedef gboolean (*PQueue_Traverse_Func)(gpointer data,
66                                          gpointer user_data);
67 /* Returns TRUE to stop the traversal */
68 
69 void PQueue_traverse(PQueue *pq, PQueue_Traverse_Func tf,
70                      gpointer user_data);
71 
72 #define PQueue_total(pq) ((pq)->total)
73 
74 #define PQueue_top(pq) \
75         ((pq)?(((pq)->root)?((pq)->root->data):(NULL)):(NULL))
76 
77 #ifdef __cplusplus
78 }
79 #endif /* __cplusplus */
80 
81 #endif /* INCLUDED_PQUEUE_H */
82 
83