contrib/mul/mbl/mbl_priority_bounded_queue.h
Go to the documentation of this file.
00001 #ifndef mbl_priority_bounded_queue_h_
00002 #define mbl_priority_bounded_queue_h_
00003 //:
00004 // \file
00005 // \brief Describes a bounded priority queue
00006 // \author Ian Scott
00007 // \date   Fri Oct  5  2001
00008 
00009 #include <vcl_vector.h>
00010 #include <vcl_functional.h>
00011 #include <vcl_algorithm.h> 
00012 
00013 //: A bounded priority queue
00014 // This is identical to a vcl_priority_queue, but
00015 // as more elements are added past the queue's bound size
00016 // the largest values are thrown out.
00017 // So this queue keeps the n smallest values that
00018 // are passed to it.
00019 //
00020 // To store the largest values, use vcl_more as the comparator O.
00021 //
00022 // top() returns the value that is closest to being thrown out,
00023 // which is the largest value in the case of the default predicate.
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; // there is no way to find out second template argument 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   //: Construct a bounded priority queue from a controlled sequence.
00050   // The bounded size will be the length of the sequence.
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   //: The largest size the queue can be before it starts throwing out data.
00058   size_type bound_size() const {return b_size_;}
00059 
00060   //: Set the largest size the queue can be before it starts throwing out data.
00061   // If the bound_size is smaller that the current size, then data will be thrown out.
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_); } // ignore purify:UMR error here
00083   // It can be resolved by replacing a comparator object with a function pointer.
00084   // It seems that when using an object, some compilers put a small data marker in
00085   // to represent the object. But it contains no useful data.
00086   // Ignore purify:UMR error on next line as well - same cause.
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_