File indexing completed on 2024-04-21 14:46:24
0001 /* 0002 ** Author: Eric Veach, July 1994. 0003 ** 0004 */ 0005 0006 #ifndef __priorityq_sort_h_ 0007 #define __priorityq_sort_h_ 0008 0009 #include "priorityq-heap.h" 0010 0011 #undef PQkey 0012 #undef PQhandle 0013 #undef PriorityQ 0014 #undef pqNewPriorityQ 0015 #undef pqDeletePriorityQ 0016 #undef pqInit 0017 #undef pqInsert 0018 #undef pqMinimum 0019 #undef pqExtractMin 0020 #undef pqDelete 0021 #undef pqIsEmpty 0022 0023 /* Use #define's so that another heap implementation can use this one */ 0024 0025 #define PQkey PQSortKey 0026 #define PQhandle PQSortHandle 0027 #define PriorityQ PriorityQSort 0028 0029 #define pqNewPriorityQ(leq) __gl_pqSortNewPriorityQ(leq) 0030 #define pqDeletePriorityQ(pq) __gl_pqSortDeletePriorityQ(pq) 0031 0032 /* The basic operations are insertion of a new key (pqInsert), 0033 * and examination/extraction of a key whose value is minimum 0034 * (pqMinimum/pqExtractMin). Deletion is also allowed (pqDelete); 0035 * for this purpose pqInsert returns a "handle" which is supplied 0036 * as the argument. 0037 * 0038 * An initial heap may be created efficiently by calling pqInsert 0039 * repeatedly, then calling pqInit. In any case pqInit must be called 0040 * before any operations other than pqInsert are used. 0041 * 0042 * If the heap is empty, pqMinimum/pqExtractMin will return a NULL key. 0043 * This may also be tested with pqIsEmpty. 0044 */ 0045 #define pqInit(pq) __gl_pqSortInit(pq) 0046 #define pqInsert(pq, key) __gl_pqSortInsert(pq, key) 0047 #define pqMinimum(pq) __gl_pqSortMinimum(pq) 0048 #define pqExtractMin(pq) __gl_pqSortExtractMin(pq) 0049 #define pqDelete(pq, handle) __gl_pqSortDelete(pq, handle) 0050 #define pqIsEmpty(pq) __gl_pqSortIsEmpty(pq) 0051 0052 /* Since we support deletion the data structure is a little more 0053 * complicated than an ordinary heap. "nodes" is the heap itself; 0054 * active nodes are stored in the range 1..pq->size. When the 0055 * heap exceeds its allocated size (pq->max), its size doubles. 0056 * The children of node i are nodes 2i and 2i+1. 0057 * 0058 * Each node stores an index into an array "handles". Each handle 0059 * stores a key, plus a pointer back to the node which currently 0060 * represents that key (ie. nodes[handles[i].node].handle == i). 0061 */ 0062 0063 typedef PQHeapKey PQkey; 0064 typedef PQHeapHandle PQhandle; 0065 typedef struct PriorityQ PriorityQ; 0066 0067 struct PriorityQ 0068 { 0069 PriorityQHeap *heap; 0070 PQkey *keys; 0071 PQkey **order; 0072 PQhandle size, max; 0073 int initialized; 0074 int (*leq)(PQkey key1, PQkey key2); 0075 }; 0076 0077 PriorityQ *pqNewPriorityQ(int (*leq)(PQkey key1, PQkey key2)); 0078 void pqDeletePriorityQ(PriorityQ *pq); 0079 0080 int pqInit(PriorityQ *pq); 0081 PQhandle pqInsert(PriorityQ *pq, PQkey key); 0082 PQkey pqExtractMin(PriorityQ *pq); 0083 void pqDelete(PriorityQ *pq, PQhandle handle); 0084 0085 PQkey pqMinimum(PriorityQ *pq); 0086 int pqIsEmpty(PriorityQ *pq); 0087 0088 #endif