pr_queue_k.h
Go to the documentation of this file.00001 //---------------------------------------------------------------------- 00002 // File: pr_queue_k.h 00003 // Programmer: Sunil Arya and David Mount 00004 // Description: Include file for priority queue with k items. 00005 // Last modified: 01/04/05 (Version 1.0) 00006 //---------------------------------------------------------------------- 00007 // Copyright (c) 1997-2005 University of Maryland and Sunil Arya and 00008 // David Mount. All Rights Reserved. 00009 // 00010 // This software and related documentation is part of the Approximate 00011 // Nearest Neighbor Library (ANN). This software is provided under 00012 // the provisions of the Lesser GNU Public License (LGPL). See the 00013 // file ../ReadMe.txt for further information. 00014 // 00015 // The University of Maryland (U.M.) and the authors make no 00016 // representations about the suitability or fitness of this software for 00017 // any purpose. It is provided "as is" without express or implied 00018 // warranty. 00019 //---------------------------------------------------------------------- 00020 // History: 00021 // Revision 0.1 03/04/98 00022 // Initial release 00023 //---------------------------------------------------------------------- 00024 00025 #ifndef PR_QUEUE_K_H 00026 #define PR_QUEUE_K_H 00027 00028 #include <stereo_wall_detection/ANN/ANNx.h> // all ANN includes 00029 #include <stereo_wall_detection/ANN/ANNperf.h> // performance evaluation 00030 00031 //---------------------------------------------------------------------- 00032 // Basic types 00033 //---------------------------------------------------------------------- 00034 typedef ANNdist PQKkey; // key field is distance 00035 typedef int PQKinfo; // info field is int 00036 00037 //---------------------------------------------------------------------- 00038 // Constants 00039 // The NULL key value is used to initialize the priority queue, and 00040 // so it should be larger than any valid distance, so that it will 00041 // be replaced as legal distance values are inserted. The NULL 00042 // info value must be a nonvalid array index, we use ANN_NULL_IDX, 00043 // which is guaranteed to be negative. 00044 //---------------------------------------------------------------------- 00045 00046 const PQKkey PQ_NULL_KEY = ANN_DIST_INF; // nonexistent key value 00047 const PQKinfo PQ_NULL_INFO = ANN_NULL_IDX; // nonexistent info value 00048 00049 //---------------------------------------------------------------------- 00050 // ANNmin_k 00051 // An ANNmin_k structure is one which maintains the smallest 00052 // k values (of type PQKkey) and associated information (of type 00053 // PQKinfo). The special info and key values PQ_NULL_INFO and 00054 // PQ_NULL_KEY means that thise entry is empty. 00055 // 00056 // It is currently implemented using an array with k items. 00057 // Items are stored in increasing sorted order, and insertions 00058 // are made through standard insertion sort. (This is quite 00059 // inefficient, but current applications call for small values 00060 // of k and relatively few insertions.) 00061 // 00062 // Note that the list contains k+1 entries, but the last entry 00063 // is used as a simple placeholder and is otherwise ignored. 00064 //---------------------------------------------------------------------- 00065 00066 class ANNmin_k { 00067 struct mk_node { // node in min_k structure 00068 PQKkey key; // key value 00069 PQKinfo info; // info field (user defined) 00070 }; 00071 00072 int k; // max number of keys to store 00073 int n; // number of keys currently active 00074 mk_node *mk; // the list itself 00075 00076 public: 00077 ANNmin_k(int max) // constructor (given max size) 00078 { 00079 n = 0; // initially no items 00080 k = max; // maximum number of items 00081 mk = new mk_node[max+1]; // sorted array of keys 00082 } 00083 00084 ~ANNmin_k() // destructor 00085 { delete [] mk; } 00086 00087 PQKkey ANNmin_key() // return minimum key 00088 { return (n > 0 ? mk[0].key : PQ_NULL_KEY); } 00089 00090 PQKkey max_key() // return maximum key 00091 { return (n == k ? mk[k-1].key : PQ_NULL_KEY); } 00092 00093 PQKkey ith_smallest_key(int i) // ith smallest key (i in [0..n-1]) 00094 { return (i < n ? mk[i].key : PQ_NULL_KEY); } 00095 00096 PQKinfo ith_smallest_info(int i) // info for ith smallest (i in [0..n-1]) 00097 { return (i < n ? mk[i].info : PQ_NULL_INFO); } 00098 00099 inline void insert( // insert item (inlined for speed) 00100 PQKkey kv, // key value 00101 PQKinfo inf) // item info 00102 { 00103 register int i; 00104 // slide larger values up 00105 for (i = n; i > 0; i--) { 00106 if (mk[i-1].key > kv) 00107 mk[i] = mk[i-1]; 00108 else 00109 break; 00110 } 00111 mk[i].key = kv; // store element here 00112 mk[i].info = inf; 00113 if (n < k) n++; // increment number of items 00114 ANN_FLOP(k-i+1) // increment floating ops 00115 } 00116 }; 00117 00118 #endif