00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #ifndef BOUNDED_PRIORITY_QUEUE
00018 #define BOUNDED_PRIORITY_QUEUE
00019
00020 #include <vector>
00021 #include <queue>
00022 #include <algorithm>
00023
00024 namespace oasys {
00051 template <class T, class TSize,
00052 class TCompare = std::less<T> >
00053 class BoundedPriorityQueue :
00054 public std::priority_queue<T,std::vector<T>,TCompare> {
00055
00056 public:
00057
00058
00059 typedef std::vector<T> Sequence;
00060 typedef std::priority_queue<T,Sequence,TCompare> PriorityQueue;
00061
00066 BoundedPriorityQueue(u_int max_size) :
00067 PriorityQueue(),
00068 cur_size_(0),
00069 max_size_(max_size)
00070 {
00071 init();
00072 }
00073
00079 BoundedPriorityQueue(const TCompare& comp, u_int max_size) :
00080 PriorityQueue(comp),
00081 cur_size_(0),
00082 max_size_(max_size)
00083 {
00084 init();
00085 }
00086
00091 void push(const T& obj)
00092 {
00093 PriorityQueue::push(obj);
00094 cur_size_ += TSize()(obj);
00095 enforce_bound();
00096 }
00097
00102 void pop()
00103 {
00104 cur_size_ -= TSize()(PriorityQueue::c.front());
00105 PriorityQueue::pop();
00106 }
00107
00111 u_int current() const
00112 {
00113 return cur_size_;
00114 }
00115
00119 u_int max() const
00120 {
00121 return max_size_;
00122 }
00123
00127 void set_max(u_int max_size)
00128 {
00129 max_size_ = max_size;
00130 enforce_bound();
00131 }
00132
00133 #ifndef _DEBUG
00134 protected:
00135 #endif
00136 const Sequence& container() const
00137 {
00138 return PriorityQueue::c;
00139 }
00140
00141 typedef typename Sequence::const_iterator const_iterator;
00142 typedef typename Sequence::iterator iterator;
00143
00147 void init() {
00148 const_iterator it = (const_iterator) PriorityQueue::c.begin();
00149 while(it != (const_iterator) PriorityQueue::c.end()) {
00150 cur_size_ += TSize()(*it);
00151 }
00152 enforce_bound();
00153 }
00154
00159 void erase_member(iterator pos)
00160 {
00161 PriorityQueue::c.erase(pos);
00162 }
00163
00168 void enforce_bound() {
00169 iterator minObj;
00170 while(cur_size_ > max_size_) {
00171
00172 minObj = std::min_element (
00173 PriorityQueue::c.begin(),
00174 PriorityQueue::c.end(),
00175 PriorityQueue::comp);
00176
00177 cur_size_ -= TSize()(*minObj);
00178
00179 erase_member(minObj);
00180 }
00181
00182 make_heap(PriorityQueue::c.begin(),
00183 PriorityQueue::c.end(),
00184 PriorityQueue::comp);
00185 }
00186
00187 u_int cur_size_;
00188 u_int max_size_;
00189 };
00190
00191 }
00192 #endif // BOUNDED_PRIORITY_QUEUE