#ifndef PQUEUE_H
#define PQUEUE_H

#include <map>
#include <deque>

template <typename T>
class pqueue
{
public:
    class const_iterator;

    void push( const T& t);
    T    pop();
    int  size() const;

    const_iterator begin() const;
    const_iterator end() const;
private:
    typedef std::map< T, std::deque<T> >  m_t;
    m_t  m_;
};

template <typename T>
class pqueue<T>::const_iterator
{
public:
    const_iterator( const pqueue<T> *pq, bool is_end=false);
    bool operator==(const_iterator i) const;
    bool operator!=(const_iterator i) const;

    const T& operator*() const ;
    const_iterator& operator++();
private:
    const pqueue<T> *owner;
    typename pqueue<T>::m_t::const_iterator mi;
    typename std::deque<T>::const_iterator  di;
};

template <typename T>
pqueue<T>::const_iterator::const_iterator( const pqueue<T> *pq, bool is_end)
                                        : owner(pq)
{
    if ( is_end )
    {
        // end() állapotot az mi == owner->m_.end() ábrázolja
        mi = owner->m_.end();
    }
    else
    {
        mi = owner->m_.begin();
        di = mi->second.begin();
    }
}

template <typename T>
typename pqueue<T>::const_iterator pqueue<T>::begin() const
{
    return const_iterator(this);
}

template <typename T>
typename pqueue<T>::const_iterator pqueue<T>::end() const
{
    return const_iterator(this, true);
}

template <typename T>
void pqueue<T>::push(const T& t)
{
    m_[t].push_back(t);
}

template <typename T>
T pqueue<T>::pop()
{
    typename m_t::iterator i = --m_.end();
    T t = i->second.front();
    i->second.pop_front();
    if ( i->second.empty() )
        m_.erase(i);
    return t;
}

template <typename T>
int pqueue<T>::size() const
{
    int sum = 0;
    for ( typename m_t::const_iterator i = m_.begin(); i != m_.end(); ++i)
    {
        sum += i->second.size();
    }
    return sum;
}

template <typename T>
bool pqueue<T>::const_iterator::operator==(const_iterator i) const
{
    return ( owner == i.owner ) &&
           ( (mi == owner->m_.end() && i.mi == i.owner->m_.end()) ||
             mi == i.mi && di == i.di );
}
template <typename T>
bool pqueue<T>::const_iterator::operator!=(const_iterator i) const
{
    return ! operator==(i);
}

template <typename T>
const T& pqueue<T>::const_iterator::operator*() const
{
    return *di;
}

template <typename T>
typename pqueue<T>::const_iterator& pqueue<T>::const_iterator::operator++()
{
    if ( ++di == mi->second.end() )
        if ( ++mi != owner->m_.end() )
            di = mi->second.begin();
    return *this;
}

#endif /* PQUEUE_H */