← Back to branch summary

~ubuntu-branches/ubuntu/warty/aqsis/warty

« back to all changes in this revision

Viewing changes to boost/boost/pending/fenced_priority_queue.hpp

  • Committer: Bazaar Package Importer
  • Author(s): LaMont Jones
  • Date: 2004-08-24 07:25:04 UTC
  • Revision ID: james.westby@ubuntu.com-20040824072504-zf993vnevvisdsvb
Tags: upstream-0.9.1
Import upstream version 0.9.1

Show diffs side-by-side

added added

removed removed

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