pr_queue_k.h

Go to the documentation of this file.

//----------------------------------------------------------------------
// File:                        pr_queue_k.h
// Programmer:          Sunil Arya and David Mount
// Description:         Include file for priority queue with k items.
// Last modified:       01/04/05 (Version 1.0)
//----------------------------------------------------------------------
// Copyright (c) 1997-2005 University of Maryland and Sunil Arya and
// David Mount.  All Rights Reserved.
//
// This software and related documentation is part of the Approximate
// Nearest Neighbor Library (ANN).  This software is provided under
// the provisions of the Lesser GNU Public License (LGPL).  See the
// file ../ReadMe.txt for further information.
//
// The University of Maryland (U.M.) and the authors make no
// representations about the suitability or fitness of this software for
// any purpose.  It is provided "as is" without express or implied
// warranty.
//----------------------------------------------------------------------
// History:
//      Revision 0.1  03/04/98
//              Initial release
//----------------------------------------------------------------------

#ifndef PR_QUEUE_K_H
#define PR_QUEUE_K_H

#include <ANN/ANNx.h>                                   // all ANN includes
#include <ANN/ANNperf.h>                                // performance evaluation

//----------------------------------------------------------------------
//      Basic types
//----------------------------------------------------------------------
typedef ANNdist                 PQKkey;                 // key field is distance
typedef int                             PQKinfo;                // info field is int

//----------------------------------------------------------------------
//      Constants
//              The NULL key value is used to initialize the priority queue, and
//              so it should be larger than any valid distance, so that it will
//              be replaced as legal distance values are inserted.  The NULL
//              info value must be a nonvalid array index, we use ANN_NULL_IDX,
//              which is guaranteed to be negative.
//----------------------------------------------------------------------

const PQKkey    PQ_NULL_KEY  =  ANN_DIST_INF;   // nonexistent key value
const PQKinfo   PQ_NULL_INFO =  ANN_NULL_IDX;   // nonexistent info value

//----------------------------------------------------------------------
//      ANNmin_k
//              An ANNmin_k structure is one which maintains the smallest
//              k values (of type PQKkey) and associated information (of type
//              PQKinfo).  The special info and key values PQ_NULL_INFO and
//              PQ_NULL_KEY means that thise entry is empty.
//
//              It is currently implemented using an array with k items.
//              Items are stored in increasing sorted order, and insertions
//              are made through standard insertion sort.  (This is quite
//              inefficient, but current applications call for small values
//              of k and relatively few insertions.)
//
//              Note that the list contains k+1 entries, but the last entry
//              is used as a simple placeholder and is otherwise ignored.
//----------------------------------------------------------------------

class ANNmin_k {
        struct mk_node {                                        // node in min_k structure
                PQKkey                  key;                    // key value
                PQKinfo                 info;                   // info field (user defined)
        };

        int                     k;                                              // max number of keys to store
        int                     n;                                              // number of keys currently active
        mk_node         *mk;                                    // the list itself

public:
        ANNmin_k(int max)                                       // constructor (given max size)
                {
                        n = 0;                                          // initially no items
                        k = max;                                        // maximum number of items
                        mk = new mk_node[max+1];        // sorted array of keys
                }

        ~ANNmin_k()                                                     // destructor
                { delete [] mk; }

        PQKkey ANNmin_key()                                     // return minimum key
                { return (n > 0 ? mk[0].key : PQ_NULL_KEY); }

        PQKkey max_key()                                        // return maximum key
                { return (n == k ? mk[k-1].key : PQ_NULL_KEY); }

        PQKkey ith_smallest_key(int i)          // ith smallest key (i in [0..n-1])
                { return (i < n ? mk[i].key : PQ_NULL_KEY); }

        PQKinfo ith_smallest_info(int i)        // info for ith smallest (i in [0..n-1])
                { return (i < n ? mk[i].info : PQ_NULL_INFO); }

        inline void insert(                                     // insert item (inlined for speed)
                PQKkey kv,                                              // key value
                PQKinfo inf)                                    // item info
                {
                        register int i;
                                                                                // slide larger values up
                        for (i = n; i > 0; i--) {
                                if (mk[i-1].key > kv)
                                        mk[i] = mk[i-1];
                                else
                                        break;
                        }
                        mk[i].key = kv;                         // store element here
                        mk[i].info = inf;
                        if (n < k) n++;                         // increment number of items
                        ANN_FLOP(k-i+1)                         // increment floating ops
                }
};

#endif