pr_queue_k.h

Go to the documentation of this file.
00001 //----------------------------------------------------------------------
00002 // File:                        pr_queue_k.h
00003 // Programmer:          Sunil Arya and David Mount
00004 // Description:         Include file for priority queue with k items.
00005 // Last modified:       01/04/05 (Version 1.0)
00006 //----------------------------------------------------------------------
00007 // Copyright (c) 1997-2005 University of Maryland and Sunil Arya and
00008 // David Mount.  All Rights Reserved.
00009 // 
00010 // This software and related documentation is part of the Approximate
00011 // Nearest Neighbor Library (ANN).  This software is provided under
00012 // the provisions of the Lesser GNU Public License (LGPL).  See the
00013 // file ../ReadMe.txt for further information.
00014 // 
00015 // The University of Maryland (U.M.) and the authors make no
00016 // representations about the suitability or fitness of this software for
00017 // any purpose.  It is provided "as is" without express or implied
00018 // warranty.
00019 //----------------------------------------------------------------------
00020 // History:
00021 //      Revision 0.1  03/04/98
00022 //              Initial release
00023 //----------------------------------------------------------------------
00024 
00025 #ifndef PR_QUEUE_K_H
00026 #define PR_QUEUE_K_H
00027 
00028 #include <ANN/ANNx.h>                                   // all ANN includes
00029 #include <ANN/ANNperf.h>                                // performance evaluation
00030 
00031 //----------------------------------------------------------------------
00032 //      Basic types
00033 //----------------------------------------------------------------------
00034 typedef ANNdist                 PQKkey;                 // key field is distance
00035 typedef int                             PQKinfo;                // info field is int
00036 
00037 //----------------------------------------------------------------------
00038 //      Constants
00039 //              The NULL key value is used to initialize the priority queue, and
00040 //              so it should be larger than any valid distance, so that it will
00041 //              be replaced as legal distance values are inserted.  The NULL
00042 //              info value must be a nonvalid array index, we use ANN_NULL_IDX,
00043 //              which is guaranteed to be negative.
00044 //----------------------------------------------------------------------
00045 
00046 const PQKkey    PQ_NULL_KEY  =  ANN_DIST_INF;   // nonexistent key value
00047 const PQKinfo   PQ_NULL_INFO =  ANN_NULL_IDX;   // nonexistent info value
00048 
00049 //----------------------------------------------------------------------
00050 //      ANNmin_k
00051 //              An ANNmin_k structure is one which maintains the smallest
00052 //              k values (of type PQKkey) and associated information (of type
00053 //              PQKinfo).  The special info and key values PQ_NULL_INFO and
00054 //              PQ_NULL_KEY means that thise entry is empty.
00055 //
00056 //              It is currently implemented using an array with k items.
00057 //              Items are stored in increasing sorted order, and insertions
00058 //              are made through standard insertion sort.  (This is quite
00059 //              inefficient, but current applications call for small values
00060 //              of k and relatively few insertions.)
00061 //              
00062 //              Note that the list contains k+1 entries, but the last entry
00063 //              is used as a simple placeholder and is otherwise ignored.
00064 //----------------------------------------------------------------------
00065 
00066 class ANNmin_k {
00067         struct mk_node {                                        // node in min_k structure
00068                 PQKkey                  key;                    // key value
00069                 PQKinfo                 info;                   // info field (user defined)
00070         };
00071 
00072         int                     k;                                              // max number of keys to store
00073         int                     n;                                              // number of keys currently active
00074         mk_node         *mk;                                    // the list itself
00075 
00076 public:
00077         ANNmin_k(int max)                                       // constructor (given max size)
00078                 {
00079                         n = 0;                                          // initially no items
00080                         k = max;                                        // maximum number of items
00081                         mk = new mk_node[max+1];        // sorted array of keys
00082                 }
00083 
00084         ~ANNmin_k()                                                     // destructor
00085                 { delete [] mk; }
00086         
00087         PQKkey ANNmin_key()                                     // return minimum key
00088                 { return (n > 0 ? mk[0].key : PQ_NULL_KEY); }
00089         
00090         PQKkey max_key()                                        // return maximum key
00091                 { return (n == k ? mk[k-1].key : PQ_NULL_KEY); }
00092         
00093         PQKkey ith_smallest_key(int i)          // ith smallest key (i in [0..n-1])
00094                 { return (i < n ? mk[i].key : PQ_NULL_KEY); }
00095         
00096         PQKinfo ith_smallest_info(int i)        // info for ith smallest (i in [0..n-1])
00097                 { return (i < n ? mk[i].info : PQ_NULL_INFO); }
00098 
00099         inline void insert(                                     // insert item (inlined for speed)
00100                 PQKkey kv,                                              // key value
00101                 PQKinfo inf)                                    // item info
00102                 {
00103                         register int i;
00104                                                                                 // slide larger values up
00105                         for (i = n; i > 0; i--) {
00106                                 if (mk[i-1].key > kv)
00107                                         mk[i] = mk[i-1];
00108                                 else
00109                                         break;
00110                         }
00111                         mk[i].key = kv;                         // store element here
00112                         mk[i].info = inf;
00113                         if (n < k) n++;                         // increment number of items
00114                         ANN_FLOP(k-i+1)                         // increment floating ops
00115                 }
00116 };
00117 
00118 #endif

Generated on Wed Nov 23 19:00:28 2011 for FreeCAD by  doxygen 1.6.1