//  (C) Porkolab 2003
//
//  A.6.11.
//  Sequential adapters:  Priority queue



template <class T, class C = vector<T>, class Cmp = less<typename C::value_type> >
class std::priority_queue {
protected:
    C c;
    Cmp cmp;
public:
    typedef typename C::value_type value_type;
    typedef typename C::size_type size_type;
    typedef C container_type;

    explicit priority_queue(const Cmp& a1 = Cmp(), const C& a2 = C())
        : c(a2), cmp(a1) { make_heap(c.begin(),c.end(),cmp); }  // see _algo.heap_
    template <class In>
    priority_queue(In first, In last, const Cmp& = Cmp(), const C& = C());

    bool empty() const { return c.empty(); }
    size_type size() const { return c.size(); }

    const value_type& top() const { return c.front(); }

    void push(const value_type&);
    void pop();
};


/*
 *  Usage of priority queue
 *
 */

struct Message {
    int priority;
    bool operator<(const Message& x) const { return priority < x.priority; }
    // ...
};

void server(priority_queue<Message>& q, Lock& lck)
{
    while(!q.empty()) {
        Message m;
        {
        LockPtr h(lck);     // hold lock only while extracting message (see _except.using_)
        if (q.empty()) return;  // somebody else got the message
        m = q.top();
        q.pop();
    }
    m.service();    // call function to serve request
    }
}