root / rgbdslam / gicp / ann_1.1.1 / src / pr_queue_k.h @ 9240aaa3
History | View | Annotate | Download (4.29 KB)
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
|