[Click] Priority queue

[Eddie Kohler]

Hi Ruben,

Click's heap algorithms work great to implement a priority queue.

See include/click/algorithm.hh for the functions.  They are STL compatible 
with extensions.

An STL-compatible PriorityQueue class might look something like this (code 
untested):

template <typename T, typename Compare = less<T> >
class priority_queue { public:

priority_queue() : _compare() { }
priority_queue(const Compare &c) : _compare(c) { }

bool empty() const { return _v.empty(); }
int size() const { return _v.size(); }
const T &top() const { return _v.front(); }
void push(const T &v) const {
    _v.push_back(v);
    push_heap(_v.begin(), _v.end(), _compare);
}
void pop() const {
    pop_heap(_v.begin(), _v.end(), _compare);
    _v.pop_back();
}

private:

Vector<T> _v;
Compare _compare;

};


E



Ruben Merz wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> 
> Hello,
> 
> I need the functionality of a priority queue. I checked the source code
> and did not find anything. Hence, if anyone has something similar or if
> I missed it, please let me know. Otherwise, I'll just implement it myself.
> 
> Best,
> Ruben
> 
> - -- 
> Ruben Merz                   Deutsche Telekom Laboratories
> http://www.net.t-labs.tu-berlin.de/people/ruben_merz.shtml
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.10 (Darwin)
> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/
> 
> iQEcBAEBAgAGBQJLg/w5AAoJEIem9YkUyRjt0LEH/0M0LbLIyZYUC55y1NgdmqGT
> Y+NZD3FZBYuilM5IWPg5pHydRPAEj0hs99kwrElJIXW7jS02rFBrsX5HPid1WOV+
> Pdqg/P3gCD3WQjJKmri5jk6peOOB+FO5YBu5PWNZyIUp9maKSroqZhtG369WK9hW
> wrmJEDJL/Uk1YBg6lKdXMH5h85lAtw9yrUPY+4qfxBgZ7nzKR9R2TC0OpwiBI5sB
> hrrHXHsS0M2NB85DPTYMbw0MRiA0pMwNJQB1zeLCW3uoeybfVmJDeBAAQe/Nckj/
> LR395AFcESvN76eXXmhQC3j2e1CShMQke8LofPW2UeFolbT3ZJpmNVcNoqrvAJk=
> =9NHw
> -----END PGP SIGNATURE-----
> _______________________________________________
> click mailing list
> click at amsterdam.lcs.mit.edu
> https://amsterdam.lcs.mit.edu/mailman/listinfo/click