00001 //---------------------------------------------------------------------- 00002 // File: pr_queue.h 00003 // Programmer: Sunil Arya and David Mount 00004 // Description: Include file for priority queue and related 00005 // structures. 00006 // Last modified: 01/04/05 (Version 1.0) 00007 //---------------------------------------------------------------------- 00008 // Copyright (c) 1997-2005 University of Maryland and Sunil Arya and 00009 // David Mount. All Rights Reserved. 00010 // 00011 // This software and related documentation is part of the Approximate 00012 // Nearest Neighbor Library (ANN). This software is provided under 00013 // the provisions of the Lesser GNU Public License (LGPL). See the 00014 // file ../ReadMe.txt for further information. 00015 // 00016 // The University of Maryland (U.M.) and the authors make no 00017 // representations about the suitability or fitness of this software for 00018 // any purpose. It is provided "as is" without express or implied 00019 // warranty. 00020 //---------------------------------------------------------------------- 00021 // History: 00022 // Revision 0.1 03/04/98 00023 // Initial release 00024 //---------------------------------------------------------------------- 00025 00026 #ifndef PR_QUEUE_H 00027 #define PR_QUEUE_H 00028 00029 #include <ANN/ANNx.h> // all ANN includes 00030 #include <ANN/ANNperf.h> // performance evaluation 00031 00032 //---------------------------------------------------------------------- 00033 // Basic types. 00034 //---------------------------------------------------------------------- 00035 typedef void *PQinfo; // info field is generic pointer 00036 typedef ANNdist PQkey; // key field is distance 00037 00038 //---------------------------------------------------------------------- 00039 // Priority queue 00040 // A priority queue is a list of items, along with associated 00041 // priorities. The basic operations are insert and extract_minimum. 00042 // 00043 // The priority queue is maintained using a standard binary heap. 00044 // (Implementation note: Indexing is performed from [1..max] rather 00045 // than the C standard of [0..max-1]. This simplifies parent/child 00046 // computations.) User information consists of a void pointer, 00047 // and the user is responsible for casting this quantity into whatever 00048 // useful form is desired. 00049 // 00050 // Because the priority queue is so central to the efficiency of 00051 // query processing, all the code is inline. 00052 //---------------------------------------------------------------------- 00053 00054 class ANNpr_queue { 00055 00056 struct pq_node { // node in priority queue 00057 PQkey key; // key value 00058 PQinfo info; // info field 00059 }; 00060 int n; // number of items in queue 00061 int max_size; // maximum queue size 00062 pq_node *pq; // the priority queue (array of nodes) 00063 00064 public: 00065 ANNpr_queue(int max) // constructor (given max size) 00066 { 00067 n = 0; // initially empty 00068 max_size = max; // maximum number of items 00069 pq = new pq_node[max+1]; // queue is array [1..max] of nodes 00070 } 00071 00072 ~ANNpr_queue() // destructor 00073 { delete [] pq; } 00074 00075 ANNbool empty() // is queue empty? 00076 { if (n==0) return ANNtrue; else return ANNfalse; } 00077 00078 ANNbool non_empty() // is queue nonempty? 00079 { if (n==0) return ANNfalse; else return ANNtrue; } 00080 00081 void reset() // make existing queue empty 00082 { n = 0; } 00083 00084 inline void insert( // insert item (inlined for speed) 00085 PQkey kv, // key value 00086 PQinfo inf) // item info 00087 { 00088 if (++n > max_size) annError("Priority queue overflow.", ANNabort); 00089 register int r = n; 00090 while (r > 1) { // sift up new item 00091 register int p = r/2; 00092 ANN_FLOP(1) // increment floating ops 00093 if (pq[p].key <= kv) // in proper order 00094 break; 00095 pq[r] = pq[p]; // else swap with parent 00096 r = p; 00097 } 00098 pq[r].key = kv; // insert new item at final location 00099 pq[r].info = inf; 00100 } 00101 00102 inline void extr_min( // extract minimum (inlined for speed) 00103 PQkey &kv, // key (returned) 00104 PQinfo &inf) // item info (returned) 00105 { 00106 kv = pq[1].key; // key of min item 00107 inf = pq[1].info; // information of min item 00108 register PQkey kn = pq[n--].key;// last item in queue 00109 register int p = 1; // p points to item out of position 00110 register int r = p<<1; // left child of p 00111 while (r <= n) { // while r is still within the heap 00112 ANN_FLOP(2) // increment floating ops 00113 // set r to smaller child of p 00114 if (r < n && pq[r].key > pq[r+1].key) r++; 00115 if (kn <= pq[r].key) // in proper order 00116 break; 00117 pq[p] = pq[r]; // else swap with child 00118 p = r; // advance pointers 00119 r = p<<1; 00120 } 00121 pq[p] = pq[n+1]; // insert last item in proper place 00122 } 00123 }; 00124 00125 #endif
1.6.1