Statistics
| Branch: | Revision:

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