LimitedPriorityQueueSet.h

Go to the documentation of this file.

#ifndef FACE_CONTOUR_DETECTOR_LIMITEDPRIORITYQUEUESET_H_
#define FACE_CONTOUR_DETECTOR_LIMITEDPRIORITYQUEUESET_H_

#include <functional>
#include <algorithm>
#include <deque>
#include <stddef.h>
#include <cassert>

namespace face_contour_detector {
        template <class T, class Compare = std::less<T> >
        class LimitedPriorityQueueSet {
        public:
                LimitedPriorityQueueSet(size_t size);
                virtual ~LimitedPriorityQueueSet();
                void Push(const T& item);
                T PopFront();
                const T& Front() const;
                bool Empty() const;
                size_t Size() const;
        private:
                std::deque<T> m_deque;
                size_t m_size;
                size_t m_maxSize;
        };

        //Implementation

        template <class T, class Compare>
        LimitedPriorityQueueSet<T, Compare>::LimitedPriorityQueueSet(size_t maxSize) : m_size(0), m_maxSize(maxSize) {}

        template <class T, class Compare>
        LimitedPriorityQueueSet<T, Compare>::~LimitedPriorityQueueSet() {}

        template <class T, class Compare>
        void LimitedPriorityQueueSet<T, Compare>::Push(const T& item) {
                typename std::deque<T>::iterator it;
                bool inserted = false;
                Compare compare;
                for (it = m_deque.begin(); it != m_deque.end(); it++) {
                        if (compare(item, *it))  {
                                //insert here
                                m_size++;
                                inserted = true;
                                m_deque.insert(it, item);
                                break;
                        } else if (!compare(*it, item)) {
                                //already inside
                                inserted = true;
                                break;
                        }
                }
                if (!inserted && m_maxSize > m_size) {
                        m_deque.push_back(item);
                        m_size++;
                } else if (inserted && m_maxSize < m_size) {
                        m_deque.pop_back();
                        m_size--;
                }
                assert(m_deque.size() == m_size);
        }

        template <class T, class Compare>
        T LimitedPriorityQueueSet<T, Compare>::PopFront() {
                assert(!Empty());
                T front = this->m_deque.front();
                m_deque.pop_front();
                m_size--;
                return front;
        }

        template <class T, class Compare>
        const T& LimitedPriorityQueueSet<T, Compare>::Front() const {
                return m_deque.front();
        }

        template <class T, class Compare>
        bool LimitedPriorityQueueSet<T, Compare>::Empty() const {
                return m_deque.empty();
        }

        template <class T, class Compare>
        size_t LimitedPriorityQueueSet<T, Compare>::Size() const {
                return m_size;
        }
} //namespace face_contour_detector


#endif /* FACE_CONTOUR_DETECTOR_LIMITEDPRIORITYQUEUESET_H_ */