source: NonGTP/Boost/boost/pending/fenced_priority_queue.hpp @ 857

Revision 857, 5.2 KB checked in by igarcia, 19 years ago (diff)
Line 
1//  (C) Copyright Jeremiah Willcock 2004
2//  Distributed under the Boost Software License, Version 1.0. (See
3//  accompanying file LICENSE_1_0.txt or copy at
4//  http://www.boost.org/LICENSE_1_0.txt)
5
6#ifndef BOOST_FENCED_PRIORITY_QUEUE_HPP
7#define BOOST_FENCED_PRIORITY_QUEUE_HPP
8
9#include <vector>
10#include <queue>
11#include <functional>
12#include <boost/pending/queue.hpp>
13
14// Fenced priority queue
15// Jeremiah Willcock
16
17// This class implements a fenced priority queue.  This is similar to
18// a normal priority queue (sorts its members, and only returns the
19// first), except that members cannot be sorted around a "fence" that
20// can be placed into the buffer.  This fence is inserted using the
21// fence() member function or (possibly) implicitly by the top() and
22// pop() methods, and is removed automatically when the elements
23// around it are popped.
24
25// The implementation is as follows:  Q is an unsorted queue that
26// contains the already-sorted list data, and PQ is a priority queue
27// that contains new elements (since the last fence) that have yet to
28// be sorted.  New elements are inserted into PQ, and a fence moves
29// all elements in PQ into the back of Q in sorted order.  Elements
30// are then popped from the front of Q, and if that is empty the front
31// of PQ.
32
33namespace boost {
34
35  template<class T, class Compare = std::less<T>, bool implicit_fence = true,
36           class Buffer = boost::queue<T> >
37  class fenced_priority_queue {
38  public:
39    typedef T value_type;
40    typedef typename Buffer::size_type size_type;
41
42    fenced_priority_queue(const Compare _comp = Compare() )
43      : PQ(_comp) {}
44   
45    void push(const T& data);
46    void pop(void);
47    T& top(void);
48    const T& top(void) const;
49    size_type size(void) const;
50    bool empty(void) const;
51    void fence(void);
52   
53  private:
54    void fence(void) const;
55
56    //let them mutable to allow const version of top and the same
57    //semantics with non-constant version. Rich Lee
58    mutable std::priority_queue<T, std::vector<T>, Compare> PQ;
59    mutable Buffer Q;
60  };
61 
62  template<class T, class Compare, bool implicit_fence, class Buffer>
63  inline void
64  fenced_priority_queue<T, Compare, implicit_fence, Buffer>::
65  push(const T &t) {
66    // Push a new element after the last fence.  This puts it into the
67    // priority queue to be sorted with all other elements in its
68    // partition.
69    PQ.push(t);
70  }
71
72  template<class T, class Compare, bool implicit_fence, class Buffer>
73  inline void fenced_priority_queue<T, Compare, implicit_fence, Buffer>::
74  pop(void) {
75    // Pop one element from the front of the queue.  Removes from the
76    // already-sorted part of the queue if it is non-empty, otherwise
77    // removes from the new-element priority queue.  Runs an implicit
78    // "fence" operation if the implicit_fence template argument is
79    // true.
80    if (implicit_fence) fence();
81    if ( !Q.empty() )
82      Q.pop();
83    else
84      PQ.pop();
85  }
86
87  template<class T, class Compare, bool implicit_fence, class Buffer>
88  inline T& fenced_priority_queue<T, Compare, implicit_fence, Buffer>::
89  top(void) {
90    // Get the top element from the queue.  This element comes from Q if
91    // possible, otherwise from PQ.  Causes an implicit "fence"
92    // operation if the implicit_fence template argument is true.
93    if (implicit_fence) fence();
94    if ( !Q.empty() )
95      return Q.top();
96    else
97      //std::priority_queue only have const version of top. Rich Lee
98      return const_cast<T&>(PQ.top());
99  }
100
101  template<class T, class Compare, bool implicit_fence, class Buffer>
102  inline const T&
103  fenced_priority_queue<T, Compare, implicit_fence, Buffer>::
104  top(void) const {
105    if (implicit_fence) fence();
106    if ( !Q.empty() )
107      return Q.top();
108    else
109      return PQ.top();
110  }
111
112  template<class T, class Compare, bool implicit_fence, class Buffer>
113  inline typename fenced_priority_queue<T, Compare, implicit_fence, Buffer>::size_type
114  fenced_priority_queue<T, Compare, implicit_fence, Buffer>::
115  size(void) const {
116    // Returns the size of the queue (both parts together).
117    return Q.size() + PQ.size();
118  }
119
120  template<class T, class Compare, bool implicit_fence, class Buffer>
121  inline bool
122  fenced_priority_queue<T, Compare, implicit_fence, Buffer>::
123  empty(void) const {
124    // Returns if the queue is empty, i.e. both parts are empty.
125    return Q.empty() && PQ.empty();
126  }
127 
128  template<class T, class Compare, bool implicit_fence, class Buffer>
129  inline void
130  fenced_priority_queue<T, Compare, implicit_fence, Buffer>::
131  fence(void) {
132    // Perform a fence operation.  Remove elements from PQ in sorted
133    // order and insert them in the back of Q.
134    while ( !PQ.empty() ) {
135      Q.push(PQ.top());
136      PQ.pop();
137    }
138  }
139  template<class T, class Compare, bool implicit_fence, class Buffer>
140  inline void
141  fenced_priority_queue<T, Compare, implicit_fence, Buffer>::
142  fence(void) const {
143    // Perform a fence operation.  Remove elements from PQ in sorted
144    // order and insert them in the back of Q.
145    while ( !PQ.empty() ) {
146      Q.push(PQ.top());
147      PQ.pop();
148    }
149  }
150
151
152#endif /* BOOST_FENCED_PRIORITY_QUEUE_HPP */
Note: See TracBrowser for help on using the repository browser.