Kstars

src/priorityq-sort.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
63typedef PQHeapKey PQkey;
64typedef PQHeapHandle PQhandle;
65typedef struct PriorityQ PriorityQ;
66
67struct 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
77PriorityQ *pqNewPriorityQ(int (*leq)(PQkey key1, PQkey key2));
78void pqDeletePriorityQ(PriorityQ *pq);
79
80int pqInit(PriorityQ *pq);
81PQhandle pqInsert(PriorityQ *pq, PQkey key);
82PQkey pqExtractMin(PriorityQ *pq);
83void pqDelete(PriorityQ *pq, PQhandle handle);
84
85PQkey pqMinimum(PriorityQ *pq);
86int pqIsEmpty(PriorityQ *pq);
87
88#endif
This file is part of the KDE documentation.
Documentation copyright © 1996-2024 The KDE developers.
Generated on Mon Nov 4 2024 16:38:43 by doxygen 1.12.0 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.