Kstars

src/priorityq.h
1 /*
2 ** Author: Eric Veach, July 1994.
3 **
4 */
5 
6 #ifndef __priorityq_sort_h_
7 #define __priorityq_sort_h_
8 
9 #include "priorityq-heap.h"
10 
11 #undef PQkey
12 #undef PQhandle
13 #undef PriorityQ
14 #undef pqNewPriorityQ
15 #undef pqDeletePriorityQ
16 #undef pqInit
17 #undef pqInsert
18 #undef pqMinimum
19 #undef pqExtractMin
20 #undef pqDelete
21 #undef pqIsEmpty
22 
23 /* Use #define's so that another heap implementation can use this one */
24 
25 #define PQkey PQSortKey
26 #define PQhandle PQSortHandle
27 #define PriorityQ PriorityQSort
28 
29 #define pqNewPriorityQ(leq) __gl_pqSortNewPriorityQ(leq)
30 #define pqDeletePriorityQ(pq) __gl_pqSortDeletePriorityQ(pq)
31 
32 /* The basic operations are insertion of a new key (pqInsert),
33  * and examination/extraction of a key whose value is minimum
34  * (pqMinimum/pqExtractMin). Deletion is also allowed (pqDelete);
35  * for this purpose pqInsert returns a "handle" which is supplied
36  * as the argument.
37  *
38  * An initial heap may be created efficiently by calling pqInsert
39  * repeatedly, then calling pqInit. In any case pqInit must be called
40  * before any operations other than pqInsert are used.
41  *
42  * If the heap is empty, pqMinimum/pqExtractMin will return a NULL key.
43  * This may also be tested with pqIsEmpty.
44  */
45 #define pqInit(pq) __gl_pqSortInit(pq)
46 #define pqInsert(pq, key) __gl_pqSortInsert(pq, key)
47 #define pqMinimum(pq) __gl_pqSortMinimum(pq)
48 #define pqExtractMin(pq) __gl_pqSortExtractMin(pq)
49 #define pqDelete(pq, handle) __gl_pqSortDelete(pq, handle)
50 #define pqIsEmpty(pq) __gl_pqSortIsEmpty(pq)
51 
52 /* Since we support deletion the data structure is a little more
53  * complicated than an ordinary heap. "nodes" is the heap itself;
54  * active nodes are stored in the range 1..pq->size. When the
55  * heap exceeds its allocated size (pq->max), its size doubles.
56  * The children of node i are nodes 2i and 2i+1.
57  *
58  * Each node stores an index into an array "handles". Each handle
59  * stores a key, plus a pointer back to the node which currently
60  * represents that key (ie. nodes[handles[i].node].handle == i).
61  */
62 
63 typedef PQHeapKey PQkey;
64 typedef PQHeapHandle PQhandle;
65 typedef struct PriorityQ PriorityQ;
66 
67 struct PriorityQ
68 {
69  PriorityQHeap *heap;
70  PQkey *keys;
71  PQkey **order;
72  PQhandle size, max;
73  int initialized;
74  int (*leq)(PQkey key1, PQkey key2);
75 };
76 
77 PriorityQ *pqNewPriorityQ(int (*leq)(PQkey key1, PQkey key2));
78 void pqDeletePriorityQ(PriorityQ *pq);
79 
80 int pqInit(PriorityQ *pq);
81 PQhandle pqInsert(PriorityQ *pq, PQkey key);
82 PQkey pqExtractMin(PriorityQ *pq);
83 void pqDelete(PriorityQ *pq, PQhandle handle);
84 
85 PQkey pqMinimum(PriorityQ *pq);
86 int pqIsEmpty(PriorityQ *pq);
87 
88 #endif
This file is part of the KDE documentation.
Documentation copyright © 1996-2022 The KDE developers.
Generated on Sat Aug 13 2022 04:01:57 by doxygen 1.8.17 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.