Jerome Piovano

Research in Medical Imaging and Computer Vision

• Home
• Research
• Publications
• Teaching
• Biography
• Shared code and data

/home/jpiovano/src/Odyssee++/trunk/Libs/LevelSet/src/PriorityQueue.h

Go to the documentation of this file.

#ifndef PRIORITY_QUEUE_H
#define PRIORITY_QUEUE_H

#include <list>
#include <cmath>
#include <iomanip>

namespace levelset {

        template <class Element>
        class PriorityQueue
        {
        public:
                typedef std::list<Element>                              ElementList;
                typedef typename ElementList::iterator                  ElementListIterator;
                typedef std::pair<ElementListIterator, int>             QueuePosition;        // pair of list_iterator/bucket to quickly remove elements in the priority queue


                PriorityQueue(unsigned _size    = 2000,   
                              double   _inc_max = 3       
                        );

                ~PriorityQueue();



                
                bool empty() const;
                QueuePosition push(const Element &e, double t);
                void pop();
                const Element & top();
                QueuePosition increase_priority(const Element& e, QueuePosition& pos, double t_new);
                void clear();
                unsigned size() const;

                void print() const;

        private:



                ElementList *    m_tab;      
                unsigned         m_size;     
                unsigned         m_nb_elem;  
                double           m_t0;       
                int              m_i0;       
                double           m_delta;    
                double           m_inc_max;  
                
        };


        // Constructors - Destructor


        template <class Element>
                PriorityQueue<Element>::PriorityQueue(unsigned _size, double _inc_max) 
                : m_size(_size), m_t0(0), m_i0(0), m_nb_elem(0),m_inc_max(_inc_max)
        {
                m_tab   = new ElementList[_size];
                m_delta = _inc_max / static_cast<double>(_size);
        }

        template <class Element>
                PriorityQueue<Element>::~PriorityQueue() 
        {
                delete[] m_tab; 
        }


        // Access/Modif the queue


        template <class Element>
                bool PriorityQueue<Element>::empty() const
        {
                return (m_nb_elem == 0);
        }
                
        template <class Element>
                typename PriorityQueue<Element>::QueuePosition PriorityQueue<Element>::push(const Element &e, double t)
        {

                if (t-m_t0 > m_inc_max) 
                        std::cerr << "Warning : Increment " << t-m_t0 << " superior to maximum increment " << m_inc_max << std::endl;
                else if (t-m_t0 < 0) 
                        std::cerr << "Warning : Priority " << t << " inferior to the lowest priority in the queue " << m_t0 << std::endl;

                int i = 0;
                if (empty()) {
                        m_t0    = t;
                        m_i0    = 0;
                }
                else {
                        // compute the indice in the circular array.
                        i = static_cast<int>(floor((t-m_t0) * m_size / m_inc_max));

                        // compute the true indice in the regular array.
                        i = (i >= m_size)? m_size-1 : ((i < 0)? 0 : i);
                        i = (i + m_i0) % m_size;
                }

                m_nb_elem++;
                m_tab[i].push_front(e);
                return QueuePosition(m_tab[i].begin(), i);
        }
                
        template <class Element>
                void PriorityQueue<Element>::pop()
        {
                if (empty()) return;

                // shift m_i0 in order to be on a non empty level of quantization
                while (m_tab[m_i0].empty()){
                        m_i0 = (m_i0 + 1) % m_size;
                        m_t0 += m_delta;
                }

                m_nb_elem--;
                m_tab[m_i0].pop_back();
        }

        template <class Element>
                const Element & PriorityQueue<Element>::top()
        {
                // shift m_i0 in order to be on a non empty level of quantization
                while (m_tab[m_i0].empty()){
                        m_i0 = (m_i0 + 1) % m_size;
                        m_t0 += m_delta;
                }

                return m_tab[m_i0].back();
        }
                
        template <class Element>
                typename PriorityQueue<Element>::QueuePosition PriorityQueue<Element>::increase_priority(const Element& e, QueuePosition& pos, double t_new)
        {
                if (t_new-m_t0 > m_inc_max) 
                        std::cerr << "Warning : Increment " << t_new-m_t0 << " superior to maximum increment" << m_inc_max << std::endl;
                else if (t_new - m_t0 < 0) 
                        std::cerr << "Warning : Priority " << t_new << " inferior to the lowest priority in the queue " << m_t0 << std::endl;

                // compute the indice in the circular array
                int  i = static_cast<int>(floor((t_new-m_t0) * m_size / m_inc_max));

                i = (i >= m_size)? m_size-1 : ((i < 0)? 0 : i);
                i = (i + m_i0) % m_size;
                
                m_tab[pos.second].erase(pos.first);
                m_tab[i].push_front(e);
                return QueuePosition(m_tab[i].begin(), i);
        }
                
        template <class Element>
                void PriorityQueue<Element>::clear()
        {
                m_nb_elem = 0;
                m_t0      = 0;
                m_i0      = 0;
                for (int i= 0 ; i<m_size ; i++)
                        m_tab[i].clear();
        }

        template <class Element>
                unsigned PriorityQueue<Element>::size() const
        {
                return m_nb_elem;
        }

        template <class Element>
                void PriorityQueue<Element>::print() const
        {
                std::cout << "-------------------------------------"  << std::endl;
                std::cout << "m_t0 = " << m_t0 << std::endl;
                std::cout << "m_i0 = " << m_i0 << std::endl;
                std::cout << "size = " << m_nb_elem << std::endl;
                for (int i = 0; i < m_size; i++){
                        if (!m_tab[i].empty()){
                                // index in the circular array, starting at m_i0
                                int j = (i-(int)m_i0 >= 0)? i-(int)m_i0 : i-(int)m_i0+m_size;
        
                                // print infos concerning the bucket
                                std::cout << "  i=" << std::setw(2) << i 
                                          << "| l=" << std::setw(2) << j 
                                          << "| p=" << std::setw(5) << m_t0 + j*m_delta 
                                          << "->"   << std::setw(5) << m_t0 + j*m_delta + m_delta;
                                // print the elements in the bucket
                                for (typename ElementList::iterator it = m_tab[i].begin() ; it!= m_tab[i].end() ; it++)
                                        std::cout << " " << *it ;
        
                                std::cout << std::endl; 
                        }
                }
        }

}

#endif // PRIORITY_QUEUE_H

For further information, please contact Jerome Piovano - Last update 2008-02-08