123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160 |
- #ifndef BOOST_FENCED_PRIORITY_QUEUE_HPP
- #define BOOST_FENCED_PRIORITY_QUEUE_HPP
- #include <vector>
- #include <queue>
- #include <functional>
- #include <boost/pending/queue.hpp>
- namespace boost
- {
- template < class T, class Compare = std::less< T >, bool implicit_fence = true,
- class Buffer = boost::queue< T > >
- class fenced_priority_queue
- {
- public:
- typedef T value_type;
- typedef typename Buffer::size_type size_type;
- fenced_priority_queue(const Compare _comp = Compare()) : PQ(_comp) {}
- void push(const T& data);
- void pop(void);
- T& top(void);
- const T& top(void) const;
- size_type size(void) const;
- bool empty(void) const;
- void fence(void);
- private:
- void fence(void) const;
-
-
- mutable std::priority_queue< T, std::vector< T >, Compare > PQ;
- mutable Buffer Q;
- };
- template < class T, class Compare, bool implicit_fence, class Buffer >
- inline void fenced_priority_queue< T, Compare, implicit_fence, Buffer >::push(
- const T& t)
- {
-
-
-
- PQ.push(t);
- }
- template < class T, class Compare, bool implicit_fence, class Buffer >
- inline void fenced_priority_queue< T, Compare, implicit_fence, Buffer >::pop(
- void)
- {
-
-
-
-
-
- if (implicit_fence)
- fence();
- if (!Q.empty())
- Q.pop();
- else
- PQ.pop();
- }
- template < class T, class Compare, bool implicit_fence, class Buffer >
- inline T& fenced_priority_queue< T, Compare, implicit_fence, Buffer >::top(void)
- {
-
-
-
- if (implicit_fence)
- fence();
- if (!Q.empty())
- return Q.top();
- else
-
- return const_cast< T& >(PQ.top());
- }
- template < class T, class Compare, bool implicit_fence, class Buffer >
- inline const T&
- fenced_priority_queue< T, Compare, implicit_fence, Buffer >::top(void) const
- {
- if (implicit_fence)
- fence();
- if (!Q.empty())
- return Q.top();
- else
- return PQ.top();
- }
- template < class T, class Compare, bool implicit_fence, class Buffer >
- inline typename fenced_priority_queue< T, Compare, implicit_fence,
- Buffer >::size_type
- fenced_priority_queue< T, Compare, implicit_fence, Buffer >::size(void) const
- {
-
- return Q.size() + PQ.size();
- }
- template < class T, class Compare, bool implicit_fence, class Buffer >
- inline bool fenced_priority_queue< T, Compare, implicit_fence, Buffer >::empty(
- void) const
- {
-
- return Q.empty() && PQ.empty();
- }
- template < class T, class Compare, bool implicit_fence, class Buffer >
- inline void fenced_priority_queue< T, Compare, implicit_fence, Buffer >::fence(
- void)
- {
-
-
- while (!PQ.empty())
- {
- Q.push(PQ.top());
- PQ.pop();
- }
- }
- template < class T, class Compare, bool implicit_fence, class Buffer >
- inline void fenced_priority_queue< T, Compare, implicit_fence, Buffer >::fence(
- void) const
- {
-
-
- while (!PQ.empty())
- {
- Q.push(PQ.top());
- PQ.pop();
- }
- }
- }
- #endif
|