pr_queue_k.h
Go to the documentation of this file.
1 //----------------------------------------------------------------------
2 // File: pr_queue_k.h
3 // Programmer: Sunil Arya and David Mount
4 // Description: Include file for priority queue with k items.
5 // Last modified: 01/04/05 (Version 1.0)
6 //----------------------------------------------------------------------
7 // Copyright (c) 1997-2005 University of Maryland and Sunil Arya and
8 // David Mount. All Rights Reserved.
9 //
10 // This software and related documentation is part of the Approximate
11 // Nearest Neighbor Library (ANN). This software is provided under
12 // the provisions of the Lesser GNU Public License (LGPL). See the
13 // file ../ReadMe.txt for further information.
14 //
15 // The University of Maryland (U.M.) and the authors make no
16 // representations about the suitability or fitness of this software for
17 // any purpose. It is provided "as is" without express or implied
18 // warranty.
19 //----------------------------------------------------------------------
20 // History:
21 // Revision 0.1 03/04/98
22 // Initial release
23 //----------------------------------------------------------------------
24 
25 #ifndef PR_QUEUE_K_H
26 #define PR_QUEUE_K_H
27 
28 #include <ANN/ANNx.h> // all ANN includes
29 #include <ANN/ANNperf.h> // performance evaluation
30 
31 //----------------------------------------------------------------------
32 // Basic types
33 //----------------------------------------------------------------------
34 typedef ANNdist PQKkey; // key field is distance
35 typedef int PQKinfo; // info field is int
36 
37 //----------------------------------------------------------------------
38 // Constants
39 // The NULL key value is used to initialize the priority queue, and
40 // so it should be larger than any valid distance, so that it will
41 // be replaced as legal distance values are inserted. The NULL
42 // info value must be a nonvalid array index, we use ANN_NULL_IDX,
43 // which is guaranteed to be negative.
44 //----------------------------------------------------------------------
45 
46 const PQKkey PQ_NULL_KEY = ANN_DIST_INF; // nonexistent key value
47 const PQKinfo PQ_NULL_INFO = ANN_NULL_IDX; // nonexistent info value
48 
49 //----------------------------------------------------------------------
50 // ANNmin_k
51 // An ANNmin_k structure is one which maintains the smallest
52 // k values (of type PQKkey) and associated information (of type
53 // PQKinfo). The special info and key values PQ_NULL_INFO and
54 // PQ_NULL_KEY means that thise entry is empty.
55 //
56 // It is currently implemented using an array with k items.
57 // Items are stored in increasing sorted order, and insertions
58 // are made through standard insertion sort. (This is quite
59 // inefficient, but current applications call for small values
60 // of k and relatively few insertions.)
61 //
62 // Note that the list contains k+1 entries, but the last entry
63 // is used as a simple placeholder and is otherwise ignored.
64 //----------------------------------------------------------------------
65 
66 class ANNmin_k {
67  struct mk_node { // node in min_k structure
68  PQKkey key; // key value
69  PQKinfo info; // info field (user defined)
70  };
71 
72  int k; // max number of keys to store
73  int n; // number of keys currently active
74  mk_node *mk; // the list itself
75 
76 public:
77  ANNmin_k(int max) // constructor (given max size)
78  {
79  n = 0; // initially no items
80  k = max; // maximum number of items
81  mk = new mk_node[max+1]; // sorted array of keys
82  }
83 
84  ~ANNmin_k() // destructor
85  { delete [] mk; }
86 
87  PQKkey ANNmin_key() // return minimum key
88  { return (n > 0 ? mk[0].key : PQ_NULL_KEY); }
89 
90  PQKkey max_key() // return maximum key
91  { return (n == k ? mk[k-1].key : PQ_NULL_KEY); }
92 
93  PQKkey ith_smallest_key(int i) // ith smallest key (i in [0..n-1])
94  { return (i < n ? mk[i].key : PQ_NULL_KEY); }
95 
96  PQKinfo ith_smallest_info(int i) // info for ith smallest (i in [0..n-1])
97  { return (i < n ? mk[i].info : PQ_NULL_INFO); }
98 
99  inline void insert( // insert item (inlined for speed)
100  PQKkey kv, // key value
101  PQKinfo inf) // item info
102  {
103  register int i;
104  // slide larger values up
105  for (i = n; i > 0; i--) {
106  if (mk[i-1].key > kv)
107  mk[i] = mk[i-1];
108  else
109  break;
110  }
111  mk[i].key = kv; // store element here
112  mk[i].info = inf;
113  if (n < k) n++; // increment number of items
114  ANN_FLOP(k-i+1) // increment floating ops
115  }
116 };
117 
118 #endif
PQKkey ANNmin_key()
Definition: pr_queue_k.h:87
PQKkey ith_smallest_key(int i)
Definition: pr_queue_k.h:93
const ANNidx ANN_NULL_IDX
Definition: ANN.h:176
PQKinfo ith_smallest_info(int i)
Definition: pr_queue_k.h:96
const ANNdist ANN_DIST_INF
Definition: ANN.h:199
ANNmin_k(int max)
Definition: pr_queue_k.h:77
#define ANN_FLOP(n)
Definition: ANNperf.h:131
~ANNmin_k()
Definition: pr_queue_k.h:84
ANNdist PQKkey
Definition: pr_queue_k.h:34
PQKkey max_key()
Definition: pr_queue_k.h:90
mk_node * mk
Definition: pr_queue_k.h:74
int PQKinfo
Definition: pr_queue_k.h:35
const PQKinfo PQ_NULL_INFO
Definition: pr_queue_k.h:47
const PQKkey PQ_NULL_KEY
Definition: pr_queue_k.h:46
void insert(PQKkey kv, PQKinfo inf)
Definition: pr_queue_k.h:99
double ANNdist
Definition: ANN.h:159


addwa_local_planner
Author(s): Xie Fusheng
autogenerated on Mon Jun 10 2019 15:52:59