1 #ifndef INDEXED_PRIORITY_QUEUE_H 2 #define INDEXED_PRIORITY_QUEUE_H 35 template <
class IT,
class PT>
39 typedef std::pair<PT,IT> value_type;
40 typedef typename std::set<std::pair<PT,IT> >::iterator iterator;
41 typedef typename std::set<std::pair<PT,IT> >::const_iterator const_iterator;
43 iterator begin() {
return q.begin(); }
44 const_iterator begin()
const {
return q.begin(); }
45 iterator end() {
return q.end(); }
46 const iterator end()
const {
return q.end(); }
47 const value_type& front()
const {
return *q.begin(); }
48 const value_type& back()
const { const_iterator i=q.end(); --i;
return *i; }
49 bool empty()
const {
return q.empty(); }
50 void clear() { q.clear(); indices.clear(); }
51 size_t size()
const {
return q.size(); }
52 const value_type& top()
const {
return *q.begin(); }
53 void erase(iterator i) {
54 size_t n=indices.erase(i->second);
61 iterator insert(
const value_type& item) {
62 iterator i=q.insert(item).first;
63 Assert(indices.count(item.second)==0);
64 indices[item.second] = i;
67 template <
class InputIterator>
68 void insert(InputIterator i,InputIterator j) {
69 for(InputIterator k=i;k!=j;++k)
72 iterator insert(
const IT& index,
const PT& p) {
73 iterator i=q.insert(value_type(p,index)).first;
74 Assert(indices.count(index)==0);
78 iterator find(
const IT& index) {
79 auto i=indices.find(index);
80 if(i==indices.end())
return end();
83 iterator refresh(
const IT& index,
const PT& p) {
84 iterator i=find(index);
85 if(i != q.end()) q.erase(i);
86 i = q.insert(value_type(p,index)).first;
90 bool is_valid()
const {
91 for(
auto i=indices.begin();i!=indices.end();++i) {
92 if(i->second->second != i->first)
return false;
98 std::map<IT,iterator> indices;
99 std::set<std::pair<PT,IT> > q;
Contains a priority queue with an associated index, allowing updates of the priority value...
Definition: IndexedPriorityQueue.h:36