1 // Copyright (C) 2004-2006 The Trustees of Indiana University.
2 
3 // Use, modification and distribution is subject to the Boost Software
4 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
5 // http://www.boost.org/LICENSE_1_0.txt)
6 
7 //  Authors: Douglas Gregor
8 //           Andrew Lumsdaine
9 #ifndef BOOST_FILTERED_QUEUE_HPP
10 #define BOOST_FILTERED_QUEUE_HPP
11 
12 #ifndef BOOST_GRAPH_USE_MPI
13 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
14 #endif
15 
16 #include <algorithm>
17 
18 namespace boost {
19 
20 /** Queue adaptor that filters elements pushed into the queue
21  * according to some predicate.
22  */
23 template<typename Buffer, typename Predicate>
24 class filtered_queue
25 {
26  public:
27   typedef Buffer                      buffer_type;
28   typedef Predicate                   predicate_type;
29   typedef typename Buffer::value_type value_type;
30   typedef typename Buffer::size_type  size_type;
31 
32   /**
33    * Constructs a new filtered queue with an initial buffer and a
34    * predicate.
35    *
36    * @param buffer the initial buffer
37    * @param pred the predicate
38    */
39   explicit
40   filtered_queue(const buffer_type& buffer = buffer_type(),
41                  const predicate_type& pred = predicate_type())
42     : buffer(buffer), pred(pred) {}
43 
44   /** Push a value into the queue.
45    *
46    *  If the predicate returns @c true for @p x, pushes @p x into the
47    *  buffer.
48    */
49   void push(const value_type& x)  { if (pred(x)) buffer.push(x); }
50 
51   /** Pop the front element off the buffer.
52    *
53    * @pre @c !empty()
54    */
55   void pop()                      { buffer.pop(); }
56 
57   /** Retrieve the front (top) element in the buffer.
58    *
59    * @pre @c !empty()
60    */
61   value_type& top()               { return buffer.top(); }
62 
63   /**
64    * \overload
65    */
66   const value_type& top() const   { return buffer.top(); }
67 
68   /** Determine the number of elements in the buffer. */
69   size_type size() const          { return buffer.size(); }
70 
71   /** Determine if the buffer is empty. */
72   bool empty() const              { return buffer.empty(); }
73 
74   /** Get a reference to the underlying buffer. */
75   buffer_type& base()             { return buffer; }
76   const buffer_type& base() const { return buffer; }
77 
78   /** Swap the contents of this with @p other. */
79   void swap(filtered_queue& other)
80   {
81     using std::swap;
82     swap(buffer, other.buffer);
83     swap(pred, other.pred);
84   }
85 
86  private:
87   buffer_type buffer;
88   predicate_type pred;
89 };
90 
91 /** Create a filtered queue. */
92 template<typename Buffer, typename Predicate>
93 inline filtered_queue<Buffer, Predicate>
94 make_filtered_queue(const Buffer& buffer, const Predicate& pred)
95 { return filtered_queue<Buffer, Predicate>(buffer, pred); }
96 
97 /** Swap a filtered_queue. */
98 template<typename Buffer, typename Predicate>
99 inline void
100 swap(filtered_queue<Buffer, Predicate>& x,
101      filtered_queue<Buffer, Predicate>& y)
102 {
103   x.swap(y);
104 }
105 
106 } // end namespace boost
107 
108 #endif // BOOST_FILTERED_QUEUE_HPP
109