use of new iterator style
[dyninst.git] / common / h / Queue.h
1 /*
2  * Copyright (c) 1996 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * This license is for research uses.  For such uses, there is no
12  * charge. We define "research use" to mean you may freely use it
13  * inside your organization for whatever purposes you see fit. But you
14  * may not re-distribute Paradyn or parts of Paradyn, in any form
15  * source or binary (including derivatives), electronic or otherwise,
16  * to any other organization or entity without our permission.
17  * 
18  * (for other uses, please contact us at paradyn@cs.wisc.edu)
19  * 
20  * All warranties, including without limitation, any warranty of
21  * merchantability or fitness for a particular purpose, are hereby
22  * excluded.
23  * 
24  * By your use of Paradyn, you understand and agree that we (or any
25  * other person or entity with proprietary rights in Paradyn) are
26  * under no obligation to provide either maintenance services,
27  * update services, notices of latent defects, or correction of
28  * defects for Paradyn.
29  * 
30  * Even if advised of the possibility of such damages, under no
31  * circumstances shall we (or any other person or entity with
32  * proprietary rights in the software licensed hereunder) be liable
33  * to you or any third party for direct, indirect, or consequential
34  * damages of any character regardless of type of action, including,
35  * without limitation, loss of profits, loss of use, loss of good
36  * will, or computer failure or malfunction.  You agree to indemnify
37  * us (and any other person or entity with proprietary rights in the
38  * software licensed hereunder) for any and all liability it may
39  * incur to third parties resulting from your use of Paradyn.
40  */
41
42 /************************************************************************
43  * Queue.h: implementation of a stack-based queue.
44 ************************************************************************/
45
46
47 \f
48
49
50 #if !defined(_Queue_h_)
51 #define _Queue_h_
52
53 #if defined(external_templates)
54 #pragma interface
55 #endif
56
57 \f
58
59
60 /************************************************************************
61  * header files.
62 ************************************************************************/
63
64 #include "util/h/Stack.h"
65
66
67 \f
68
69 #if !defined(DO_INLINE_P)
70 #define DO_INLINE_P
71 #endif
72
73 #if !defined(DO_INLINE_F)
74 #define DO_INLINE_F
75 #endif
76
77
78 /************************************************************************
79  * template<class T> class queue
80 ************************************************************************/
81
82 template<class T>
83 class queue {
84 public:
85     DO_INLINE_F         queue ();
86     DO_INLINE_F         queue (const queue<T> &);
87     DO_INLINE_F virtual ~queue ();
88
89     DO_INLINE_F queue<T>&  operator= (const queue<T> &);
90     DO_INLINE_F bool      operator== (const queue<T> &) const;
91     DO_INLINE_F queue<T>& operator+= (const queue<T> &);
92     DO_INLINE_F queue<T>   operator+ (const queue<T> &) const;
93     DO_INLINE_F queue<T>   operator- ()                 const;
94     DO_INLINE_F unsigned        size ()                 const;
95     DO_INLINE_F void         enqueue (const T &);
96     DO_INLINE_F T            dequeue ();
97     DO_INLINE_F T&              head ()                 const;
98     DO_INLINE_F T&              tail ()                 const;
99     DO_INLINE_F void           clear ();
100 #if defined(notdef)
101     DO_INLINE_F void           write (ostream &)        const;
102
103     DO_INLINE_F friend ostream& operator<< (ostream &, const queue<T> &);
104 #endif
105 private:
106     DO_INLINE_P void         reverse ();
107
108     stack<T> in_;
109     stack<T> out_;
110 };
111
112 template<class T>
113 DO_INLINE_F
114 queue<T>::queue()
115     : in_(), out_() {
116 }
117
118 template<class T>
119 DO_INLINE_F
120 queue<T>::queue(const queue<T>& q)
121     : in_(q.in_), out_(q.out_) {
122 }
123
124 template<class T>
125 DO_INLINE_F
126 queue<T>::~queue() {
127 }
128
129 template<class T>
130 DO_INLINE_F
131 queue<T>&
132 queue<T>::operator=(const queue<T>& q) {
133     if (this == &q) {
134         return *this;
135     }
136     in_  = q.in_;
137     out_ = q.out_;
138     return *this;
139 }
140
141 template<class T>
142 DO_INLINE_F
143 bool
144 queue<T>::operator==(const queue<T>& q) const {
145     if (this == &q) {
146         return true;
147     }
148
149     if ((in_ == q.in_) && (out_ == q.out_)) {
150         return true;;
151     }
152
153     if (size() != q.size()) {
154         return false;
155     }
156
157     stack<T> t1 = out_   + (-in_);
158     stack<T> t2 = q.out_ + (-q.in_);
159     return (t1 == t2);
160 }
161
162 template<class T>
163 DO_INLINE_F
164 queue<T>&
165 queue<T>::operator+=(const queue<T>& q) {
166     in_ += (-q.out_ + q.in_);
167     return *this;
168 }
169
170 template<class T>
171 DO_INLINE_F
172 queue<T>
173 queue<T>::operator+(const queue<T>& q) const {
174     queue<T> n = *this;
175     n += q;
176     return n;
177 }
178
179 template<class T>
180 DO_INLINE_F
181 queue<T>
182 queue<T>::operator-() const {
183     queue<T> t;
184     t.in_  = out_;
185     t.out_ = in_;
186     return t;
187 }
188
189 template<class T>
190 DO_INLINE_F
191 unsigned
192 queue<T>::size() const {
193     return (in_.size() + out_.size());
194 }
195
196 template<class T>
197 DO_INLINE_F
198 void
199 queue<T>::enqueue(const T& t) {
200     in_.push(t);
201 }
202
203 template<class T>
204 DO_INLINE_P
205 T
206 queue<T>::dequeue() {
207     reverse();
208     assert(out_.size() != 0);
209     return out_.pop();
210 }
211
212 template<class T>
213 DO_INLINE_F
214 T&
215 queue<T>::head() const {
216     assert(size() != 0);
217     return ((out_.size() > 0) ? out_.top() : in_.bottom());
218 }
219
220 template<class T>
221 DO_INLINE_F
222 T&
223 queue<T>::tail() const {
224     assert(size() != 0);
225     return ((in_.size() > 0) ? in_.top() : out_.bottom());
226 }
227
228 template<class T>
229 DO_INLINE_F
230 void
231 queue<T>::clear() {
232     in_.clear();
233     out_.clear();
234 }
235 #if defined(notdef)
236 template<class T>
237 DO_INLINE_F
238 void
239 queue<T>::write(ostream& os) const {
240     stack<T> t = out_ + (-in_);
241     t.write(os);
242 }
243
244 template<class T>
245 DO_INLINE_F
246 ostream&
247 operator<<(ostream& os, const queue<T>& q) {
248     return os << "[ head: "; q.write(os); return os << " :tail ]";
249 }
250 #endif
251 template<class T>
252 DO_INLINE_F
253 void
254 queue<T>::reverse() {
255     if (out_.size() != 0) {
256         return;
257     }
258     out_ += -in_;
259     in_.clear();
260 }
261
262
263 \f
264
265
266 #endif /* !defined(_Queue_h_) */