Debian Codegraph @

src/pr_queue_k.h

raw
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