Go to the documentation of this file.00001 #ifndef mbl_priority_bounded_queue_h_
00002 #define mbl_priority_bounded_queue_h_
00003
00004
00005
00006
00007
00008
00009 #include <vcl_vector.h>
00010 #include <vcl_functional.h>
00011 #include <vcl_algorithm.h>
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024 template <class T, class C= vcl_vector<T>, class O= vcl_less<
00025 #ifndef VCL_VC
00026 typename
00027 #endif
00028 C::value_type> >
00029 class mbl_priority_bounded_queue
00030 {
00031 public:
00032 typedef typename C::value_type value_type;
00033 typedef typename C::size_type size_type;
00034 #if defined(VCL_SGI_CC)
00035 typedef vcl_alloc allocator_type;
00036 #else
00037 typedef typename C::allocator_type allocator_type;
00038 #endif
00039
00040 explicit
00041 mbl_priority_bounded_queue(unsigned bound_size = 10, const O& comp = O()):
00042 b_size_(bound_size), comp_(comp) { }
00043
00044 #if 0 // #if VCL_HAS_MEMBER_TEMPLATES
00045 template <class ITER>
00046 #else
00047 typedef const value_type *ITER;
00048 #endif
00049
00050
00051 mbl_priority_bounded_queue(
00052 size_type bound_size, ITER first, ITER last, const O& comp = O(),
00053 const allocator_type& alloc = allocator_type()):
00054 b_size_(0), c_(alloc), comp_(comp)
00055 {for (; first != last; ++first) {++b_size_; push(*first);} }
00056
00057
00058 size_type bound_size() const {return b_size_;}
00059
00060
00061
00062 void set_bound_size(size_type bound_size) {
00063 while (bound_size > size()) pop();
00064 b_size_ = bound_size; }
00065
00066 bool empty() const {return c_.empty(); }
00067
00068 size_type size() const {return c_.size(); }
00069
00070 value_type& top() {return c_.front(); }
00071
00072 const value_type& top() const {return c_.front(); }
00073
00074 void push(const value_type & x) {
00075 if (size() >= b_size_)
00076 {
00077 if ( comp_(x, top()) )
00078 pop();
00079 else return;
00080 }
00081 c_.push_back(x);
00082 vcl_push_heap(c_.begin(), c_.end(), comp_); }
00083
00084
00085
00086
00087 void pop() {vcl_pop_heap(c_.begin(), c_.end(), comp_); c_.pop_back(); }
00088
00089 protected:
00090 size_type b_size_;
00091 C c_;
00092 O comp_;
00093 };
00094
00095 #endif // mbl_priority_bounded_queue_h_