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) 19972005 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[k1].key : PQ_NULL_KEY); } 
92 

93 
PQKkey ith_smallest_key(int i) // ith smallest key (i in [0..n1]) 
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..n1]) 
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[i1].key > kv) 
107 
mk[i] = mk[i1];

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(ki+1) // increment floating ops 
115 
} 
116 
}; 
117  
118 
#endif
