00001 00003 #ifndef __gdtnode_pq__ 00004 #define __gdtnode_pq__ 00005 00006 #include "gdtp_queue.h" 00007 #include "gdtmap.h" 00008 00009 namespace gdt { 00010 00011 template <class P> 00012 class gdtnode_pq : public gdtp_queue<P,gdtnode> { 00013 00014 const undi_graph* g; 00015 typedef gdtp_queue<P,gdtnode> base; 00016 gdtmap<gdtnode, pq_item> item; 00017 00018 public: 00019 00020 gdtnode_pq(const undi_graph& _g) : g(&_g), item(NULL) {} 00021 00022 ~gdtnode_pq() { } 00023 00024 void insert(gdtnode v, const P& p) { 00025 pq_item it = base::insert(p,v); 00026 item[v] = it; 00027 } 00028 00029 const P& prio(gdtnode v) const { return base::prio(v); } 00030 00031 bool member(gdtnode v) const { return (item[v] != NULL); } 00032 00033 void decrease_p(gdtnode v, const P& p) { base::decrease_p(p,v); } 00034 00035 gdtnode find_min() const { return base::inf(base::find_min()); } 00036 00037 void del(gdtnode v) { 00038 base::del_item(item[v]); 00039 item.undefine(v); 00040 } 00041 00042 gdtnode del_min() 00043 { 00044 gdtnode v = find_min(); 00045 if (v) { base::del_min(); } 00046 return v; 00047 } 00048 00049 void get_nodes(gdtlist<gdtnode>& l) 00050 { 00051 l.clear(); 00052 gdtnode v; 00053 gdt::list_item it; 00054 forall_items(it,*this) { 00055 l.append(base::inf(it)); 00056 } 00057 } 00058 00059 void clear() { 00060 base::clear(); 00061 item.clear(); 00062 } 00063 00064 const P& inf(gdtnode v) const { 00065 return base::prio(item[v]); 00066 } 00067 00068 void decrease_inf(gdtnode v, const P& x) { base::decrease_p(item[v], x); } 00069 }; 00070 } 00071 00072 #endif