KDPQueue.h

Go to the documentation of this file.

/* Copyright (C) 2004
   Priority Queue for Nearest Neighbor Search in K-Dimension Tree Node Data
   Structure Implementation

   This library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Lesser General Public
   License as published by the Free Software Foundation; either
   version 2.1 of the License, or (at your option) any later version.

   This library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Lesser General Public License for more details.

   You should have received a copy of the GNU Lesser General Public
   License along with this library; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
*/

#ifndef _KDPQUEUE_H_
#define _KDPQUEUE_H_

#include "Object.h"
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <float.h>
#include "KDPoint.h"


// Template class for node values
// IMPORTANT: class KDPQKey requires =, > operators
template <class KDPQKey, class KDPQElement>
class KDPQueue : public FD::Object
{
public:
        /*
                KDPQueue

                Default constructor
        */
        KDPQueue()
        : m_maxKeys(0), m_numKeys(0), m_keys(NULL), m_elements(NULL)
        {

        }

        /*
                KDPQueue

                Other constructor

                PARAMETERS
                i_maxKeys : maximum number of elements to keep in queue
        */
        KDPQueue(int i_maxKeys)
        : m_maxKeys(i_maxKeys), m_numKeys(0)
        {
                m_keys = new KDPQKey[m_maxKeys+1];
                m_elements = new KDPQElement[m_maxKeys+1];
        }

        /*
                ~KDPQueue

                Destructor
        */
        ~KDPQueue()
        {
                delete [] m_keys;
                delete [] m_elements;
                fflush(stdout);
        }

        /*
                printOn

                Object routine required to print its content

                PARAMETERS
                out : output stream to print the object content
        */
        void printOn(std::ostream &out) const
        {
                throw new FD::GeneralException ("KDPQueue::printOn : routine not implemented",__FILE__,__LINE__);
        }

        /*
                readFrom

                Object routine required to read an Object content

                PARAMETERS
                in : input stream to read the object content
        */
        void readFrom(std::istream &in)
        {
                throw new FD::GeneralException ("KDPQueue::readFrom : routine not implemented",__FILE__,__LINE__);
        }

        /*
                Insert

                Insert an element i_element with key i_key in queue.

                PARAMETERS
                i_key : key value of the element to insert in queue
                i_element : element to insert in queue
        */
        inline void Insert(KDPQKey i_key, KDPQElement *i_element)
        {
                int i;

                // Shift all larger value than key
                for (i=m_numKeys; i>0; --i) {
                        if (m_keys[i-1] > i_key) {
                                m_keys[i] = m_keys[i-1];
                                m_elements[i] = m_elements[i-1];
                        }
                        else {
                                break;
                        }
                }

                // Store element
                m_keys[i] = i_key;
                m_elements[i] = *i_element;

                if (m_numKeys < m_maxKeys) {
                        m_numKeys++;
                }

        }

        /*
                GetMaxKey

                Return the current queue maximum key value.

                RETURNS
                The current queue maximum key value
        */
        inline KDPQKey GetMaxKey() const
        {
                if (m_numKeys == m_maxKeys) {
                        return m_keys[m_numKeys-1];
                }
                else {
                        return (KDPQKey)DBL_MAX;
                }
        }

        /*
                GetMinKey

                Return the current queue minimum key value.

                RETURNS
                The current queue minimum key value
        */
        inline KDPQKey GetMinKey() const
        {
                if (m_numKeys > 0) {
                        return m_keys[0];
                }
                else {
                        return (KDPQKey)DBL_MAX;
                }
        }

        /*
                GetIthKey

                Return the current queue ith key value.

                PARAMETER:
                i_idx : index to key in queue

                RETURNS
                The current queue ith key value
        */
        inline KDPQKey GetIthKey(int i_idx) const
        {
                if (i_idx < m_numKeys) {
                        return m_keys[i_idx];
                }
                else {
                        return (KDPQKey)DBL_MAX;
                }
        }

        /*
                GetIthKey

                Return the current queue ith element value.

                PARAMETER:
                i_idx : index to element in queue

                RETURNS
                The current queue ith element value
        */
        inline KDPQElement *GetIthElement(int i_idx) const
        {
                if (i_idx < m_numKeys) {
                        return &(m_elements[i_idx]);
                }
                else {
                        return NULL;
                }
        }

private:
        // Maximum number of keys/elements in queue
        int m_maxKeys;
        // Current number of keys/elements in queue
        int m_numKeys;
        // Keys array
        KDPQKey *m_keys;
        // Elements array
        KDPQElement *m_elements;
};

#endif

---