00001 00003 #ifndef __gdtp_queue__ 00004 #define __gdtp_queue__ 00005 00006 #include "gdtbinary_heap2.h" 00007 00008 namespace gdt { 00009 00010 typedef heap_item pq_item; 00011 00012 template <class T, class L> 00013 struct LessToGreater { 00014 bool operator () (const T& x, const T& y) { 00015 return L()(y,x); 00016 } 00017 }; 00018 00019 template<class P, class I, class less = stdless<P> > 00020 class gdtp_queue : protected gdtbinary_heap2<P, I, LessToGreater<P, less> > 00021 { 00022 typedef gdtbinary_heap2<P, I, LessToGreater<P, less> > base; 00023 00024 public: 00025 00026 const P& prio(pq_item it) const 00027 { 00028 return base::prio(it); 00029 } 00030 00031 const I& inf(pq_item it) const { 00032 return base::inf(it); 00033 } 00034 00035 pq_item insert(const P& p, const I& i) { 00036 return base::insert(p,i); 00037 } 00038 00039 pq_item find_min() const { 00040 return base::find_max(); 00041 } 00042 00043 void decrease_p(pq_item it, const P& x) { 00044 base::increase_key(it,x); 00045 } 00046 00047 P del_min() 00048 { 00049 assert(base::size()>0); 00050 P p = base::prio(base::find_max()); 00051 base::extract_max(); 00052 return p; 00053 } 00054 00055 void del_item(pq_item it) { 00056 base::remove(it); 00057 } 00058 00059 bool empty() const { 00060 return base::size() == 0; 00061 } 00062 00063 typedef heap_item item; 00064 heap_item first_item() const { return base::data.first(); } 00065 heap_item last_item() const { return base::data.last(); } 00066 heap_item next_item(heap_item p) const { return base::data.next_item(p); } 00067 heap_item pred_item(heap_item p) const { return base::data.pred_item(p); } 00068 }; 00069 00070 00071 } 00072 00073 00074 00075 #endif 00076