BoundedPriorityQueue.h

Go to the documentation of this file.
00001 /*
00002  *    Copyright 2006 Baylor University
00003  * 
00004  *    Licensed under the Apache License, Version 2.0 (the "License");
00005  *    you may not use this file except in compliance with the License.
00006  *    You may obtain a copy of the License at
00007  * 
00008  *        http://www.apache.org/licenses/LICENSE-2.0
00009  * 
00010  *    Unless required by applicable law or agreed to in writing, software
00011  *    distributed under the License is distributed on an "AS IS" BASIS,
00012  *    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00013  *    See the License for the specific language governing permissions and
00014  *    limitations under the License.
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     // Grab a shortcut, PriorityQueue, for scoping to base class below 
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             // find the minimum object
00172             minObj = std::min_element (
00173                         PriorityQueue::c.begin(),
00174                         PriorityQueue::c.end(),
00175                         PriorityQueue::comp);
00176             // decrement by this node's capacity value
00177             cur_size_ -= TSize()(*minObj);
00178             // remove the leaf but break the heap
00179             erase_member(minObj);
00180         }
00181         // re-heapify
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 } // oasys
00192 #endif // BOUNDED_PRIORITY_QUEUE

Generated on Thu Jun 7 12:54:25 2007 for DTN Reference Implementation by  doxygen 1.5.1