1 : // Queue implementation -*- C++ -*-
2 :
3 : // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006
4 : // Free Software Foundation, Inc.
5 : //
6 : // This file is part of the GNU ISO C++ Library. This library is free
7 : // software; you can redistribute it and/or modify it under the
8 : // terms of the GNU General Public License as published by the
9 : // Free Software Foundation; either version 2, or (at your option)
10 : // any later version.
11 :
12 : // This library is distributed in the hope that it will be useful,
13 : // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 : // GNU General Public License for more details.
16 :
17 : // You should have received a copy of the GNU General Public License along
18 : // with this library; see the file COPYING. If not, write to the Free
19 : // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
20 : // USA.
21 :
22 : // As a special exception, you may use this file as part of a free software
23 : // library without restriction. Specifically, if other files instantiate
24 : // templates or use macros or inline functions from this file, or you compile
25 : // this file and link it with other files to produce an executable, this
26 : // file does not by itself cause the resulting executable to be covered by
27 : // the GNU General Public License. This exception does not however
28 : // invalidate any other reasons why the executable file might be covered by
29 : // the GNU General Public License.
30 :
31 : /*
32 : *
33 : * Copyright (c) 1994
34 : * Hewlett-Packard Company
35 : *
36 : * Permission to use, copy, modify, distribute and sell this software
37 : * and its documentation for any purpose is hereby granted without fee,
38 : * provided that the above copyright notice appear in all copies and
39 : * that both that copyright notice and this permission notice appear
40 : * in supporting documentation. Hewlett-Packard Company makes no
41 : * representations about the suitability of this software for any
42 : * purpose. It is provided "as is" without express or implied warranty.
43 : *
44 : *
45 : * Copyright (c) 1996,1997
46 : * Silicon Graphics Computer Systems, Inc.
47 : *
48 : * Permission to use, copy, modify, distribute and sell this software
49 : * and its documentation for any purpose is hereby granted without fee,
50 : * provided that the above copyright notice appear in all copies and
51 : * that both that copyright notice and this permission notice appear
52 : * in supporting documentation. Silicon Graphics makes no
53 : * representations about the suitability of this software for any
54 : * purpose. It is provided "as is" without express or implied warranty.
55 : */
56 :
57 : /** @file stl_queue.h
58 : * This is an internal header file, included by other library headers.
59 : * You should not attempt to use it directly.
60 : */
61 :
62 : #ifndef _QUEUE_H
63 : #define _QUEUE_H 1
64 :
65 : #include <bits/concept_check.h>
66 : #include <debug/debug.h>
67 :
68 : _GLIBCXX_BEGIN_NAMESPACE(std)
69 :
70 : /**
71 : * @brief A standard container giving FIFO behavior.
72 : *
73 : * @ingroup Containers
74 : * @ingroup Sequences
75 : *
76 : * Meets many of the requirements of a
77 : * <a href="tables.html#65">container</a>,
78 : * but does not define anything to do with iterators. Very few of the
79 : * other standard container interfaces are defined.
80 : *
81 : * This is not a true container, but an @e adaptor. It holds another
82 : * container, and provides a wrapper interface to that container. The
83 : * wrapper is what enforces strict first-in-first-out %queue behavior.
84 : *
85 : * The second template parameter defines the type of the underlying
86 : * sequence/container. It defaults to std::deque, but it can be any type
87 : * that supports @c front, @c back, @c push_back, and @c pop_front,
88 : * such as std::list or an appropriate user-defined type.
89 : *
90 : * Members not found in "normal" containers are @c container_type,
91 : * which is a typedef for the second Sequence parameter, and @c push and
92 : * @c pop, which are standard %queue/FIFO operations.
93 : */
94 : template<typename _Tp, typename _Sequence = deque<_Tp> >
95 : class queue
96 11 : {
97 : // concept requirements
98 : typedef typename _Sequence::value_type _Sequence_value_type;
99 : __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
100 : __glibcxx_class_requires(_Sequence, _FrontInsertionSequenceConcept)
101 : __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept)
102 : __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
103 :
104 : template<typename _Tp1, typename _Seq1>
105 : friend bool
106 : operator==(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
107 :
108 : template<typename _Tp1, typename _Seq1>
109 : friend bool
110 : operator<(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
111 :
112 : public:
113 : typedef typename _Sequence::value_type value_type;
114 : typedef typename _Sequence::reference reference;
115 : typedef typename _Sequence::const_reference const_reference;
116 : typedef typename _Sequence::size_type size_type;
117 : typedef _Sequence container_type;
118 :
119 : protected:
120 : /**
121 : * 'c' is the underlying container. Maintainers wondering why
122 : * this isn't uglified as per style guidelines should note that
123 : * this name is specified in the standard, [23.2.3.1]. (Why?
124 : * Presumably for the same reason that it's protected instead
125 : * of private: to allow derivation. But none of the other
126 : * containers allow for derivation. Odd.)
127 : */
128 : _Sequence c;
129 :
130 : public:
131 : /**
132 : * @brief Default constructor creates no elements.
133 : */
134 : explicit
135 11 : queue(const _Sequence& __c = _Sequence()) : c(__c) {}
136 :
137 : /**
138 : * Returns true if the %queue is empty.
139 : */
140 : bool
141 0 : empty() const
142 0 : { return c.empty(); }
143 :
144 : /** Returns the number of elements in the %queue. */
145 : size_type
146 0 : size() const
147 0 : { return c.size(); }
148 :
149 : /**
150 : * Returns a read/write reference to the data at the first
151 : * element of the %queue.
152 : */
153 : reference
154 0 : front()
155 : {
156 : __glibcxx_requires_nonempty();
157 0 : return c.front();
158 : }
159 :
160 : /**
161 : * Returns a read-only (constant) reference to the data at the first
162 : * element of the %queue.
163 : */
164 : const_reference
165 : front() const
166 : {
167 : __glibcxx_requires_nonempty();
168 : return c.front();
169 : }
170 :
171 : /**
172 : * Returns a read/write reference to the data at the last
173 : * element of the %queue.
174 : */
175 : reference
176 : back()
177 : {
178 : __glibcxx_requires_nonempty();
179 : return c.back();
180 : }
181 :
182 : /**
183 : * Returns a read-only (constant) reference to the data at the last
184 : * element of the %queue.
185 : */
186 : const_reference
187 : back() const
188 : {
189 : __glibcxx_requires_nonempty();
190 : return c.back();
191 : }
192 :
193 : /**
194 : * @brief Add data to the end of the %queue.
195 : * @param x Data to be added.
196 : *
197 : * This is a typical %queue operation. The function creates an
198 : * element at the end of the %queue and assigns the given data
199 : * to it. The time complexity of the operation depends on the
200 : * underlying sequence.
201 : */
202 : void
203 0 : push(const value_type& __x)
204 0 : { c.push_back(__x); }
205 :
206 : /**
207 : * @brief Removes first element.
208 : *
209 : * This is a typical %queue operation. It shrinks the %queue by one.
210 : * The time complexity of the operation depends on the underlying
211 : * sequence.
212 : *
213 : * Note that no data is returned, and if the first element's
214 : * data is needed, it should be retrieved before pop() is
215 : * called.
216 : */
217 : void
218 0 : pop()
219 : {
220 : __glibcxx_requires_nonempty();
221 0 : c.pop_front();
222 : }
223 : };
224 :
225 :
226 : /**
227 : * @brief Queue equality comparison.
228 : * @param x A %queue.
229 : * @param y A %queue of the same type as @a x.
230 : * @return True iff the size and elements of the queues are equal.
231 : *
232 : * This is an equivalence relation. Complexity and semantics depend on the
233 : * underlying sequence type, but the expected rules are: this relation is
234 : * linear in the size of the sequences, and queues are considered equivalent
235 : * if their sequences compare equal.
236 : */
237 : template<typename _Tp, typename _Seq>
238 : inline bool
239 : operator==(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
240 : { return __x.c == __y.c; }
241 :
242 : /**
243 : * @brief Queue ordering relation.
244 : * @param x A %queue.
245 : * @param y A %queue of the same type as @a x.
246 : * @return True iff @a x is lexicographically less than @a y.
247 : *
248 : * This is an total ordering relation. Complexity and semantics
249 : * depend on the underlying sequence type, but the expected rules
250 : * are: this relation is linear in the size of the sequences, the
251 : * elements must be comparable with @c <, and
252 : * std::lexicographical_compare() is usually used to make the
253 : * determination.
254 : */
255 : template<typename _Tp, typename _Seq>
256 : inline bool
257 : operator<(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
258 : { return __x.c < __y.c; }
259 :
260 : /// Based on operator==
261 : template<typename _Tp, typename _Seq>
262 : inline bool
263 : operator!=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
264 : { return !(__x == __y); }
265 :
266 : /// Based on operator<
267 : template<typename _Tp, typename _Seq>
268 : inline bool
269 : operator>(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
270 : { return __y < __x; }
271 :
272 : /// Based on operator<
273 : template<typename _Tp, typename _Seq>
274 : inline bool
275 : operator<=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
276 : { return !(__y < __x); }
277 :
278 : /// Based on operator<
279 : template<typename _Tp, typename _Seq>
280 : inline bool
281 : operator>=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
282 : { return !(__x < __y); }
283 :
284 : /**
285 : * @brief A standard container automatically sorting its contents.
286 : *
287 : * @ingroup Containers
288 : * @ingroup Sequences
289 : *
290 : * This is not a true container, but an @e adaptor. It holds
291 : * another container, and provides a wrapper interface to that
292 : * container. The wrapper is what enforces priority-based sorting
293 : * and %queue behavior. Very few of the standard container/sequence
294 : * interface requirements are met (e.g., iterators).
295 : *
296 : * The second template parameter defines the type of the underlying
297 : * sequence/container. It defaults to std::vector, but it can be
298 : * any type that supports @c front(), @c push_back, @c pop_back,
299 : * and random-access iterators, such as std::deque or an
300 : * appropriate user-defined type.
301 : *
302 : * The third template parameter supplies the means of making
303 : * priority comparisons. It defaults to @c less<value_type> but
304 : * can be anything defining a strict weak ordering.
305 : *
306 : * Members not found in "normal" containers are @c container_type,
307 : * which is a typedef for the second Sequence parameter, and @c
308 : * push, @c pop, and @c top, which are standard %queue operations.
309 : *
310 : * @note No equality/comparison operators are provided for
311 : * %priority_queue.
312 : *
313 : * @note Sorting of the elements takes place as they are added to,
314 : * and removed from, the %priority_queue using the
315 : * %priority_queue's member functions. If you access the elements
316 : * by other means, and change their data such that the sorting
317 : * order would be different, the %priority_queue will not re-sort
318 : * the elements for you. (How could it know to do so?)
319 : */
320 : template<typename _Tp, typename _Sequence = vector<_Tp>,
321 : typename _Compare = less<typename _Sequence::value_type> >
322 : class priority_queue
323 : {
324 : // concept requirements
325 : typedef typename _Sequence::value_type _Sequence_value_type;
326 : __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
327 : __glibcxx_class_requires(_Sequence, _SequenceConcept)
328 : __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept)
329 : __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
330 : __glibcxx_class_requires4(_Compare, bool, _Tp, _Tp,
331 : _BinaryFunctionConcept)
332 :
333 : public:
334 : typedef typename _Sequence::value_type value_type;
335 : typedef typename _Sequence::reference reference;
336 : typedef typename _Sequence::const_reference const_reference;
337 : typedef typename _Sequence::size_type size_type;
338 : typedef _Sequence container_type;
339 :
340 : protected:
341 : // See queue::c for notes on these names.
342 : _Sequence c;
343 : _Compare comp;
344 :
345 : public:
346 : /**
347 : * @brief Default constructor creates no elements.
348 : */
349 : explicit
350 : priority_queue(const _Compare& __x = _Compare(),
351 : const _Sequence& __s = _Sequence())
352 : : c(__s), comp(__x)
353 : { std::make_heap(c.begin(), c.end(), comp); }
354 :
355 : /**
356 : * @brief Builds a %queue from a range.
357 : * @param first An input iterator.
358 : * @param last An input iterator.
359 : * @param x A comparison functor describing a strict weak ordering.
360 : * @param s An initial sequence with which to start.
361 : *
362 : * Begins by copying @a s, inserting a copy of the elements
363 : * from @a [first,last) into the copy of @a s, then ordering
364 : * the copy according to @a x.
365 : *
366 : * For more information on function objects, see the
367 : * documentation on @link s20_3_1_base functor base
368 : * classes@endlink.
369 : */
370 : template<typename _InputIterator>
371 : priority_queue(_InputIterator __first, _InputIterator __last,
372 : const _Compare& __x = _Compare(),
373 : const _Sequence& __s = _Sequence())
374 : : c(__s), comp(__x)
375 : {
376 : __glibcxx_requires_valid_range(__first, __last);
377 : c.insert(c.end(), __first, __last);
378 : std::make_heap(c.begin(), c.end(), comp);
379 : }
380 :
381 : /**
382 : * Returns true if the %queue is empty.
383 : */
384 : bool
385 : empty() const
386 : { return c.empty(); }
387 :
388 : /** Returns the number of elements in the %queue. */
389 : size_type
390 : size() const
391 : { return c.size(); }
392 :
393 : /**
394 : * Returns a read-only (constant) reference to the data at the first
395 : * element of the %queue.
396 : */
397 : const_reference
398 : top() const
399 : {
400 : __glibcxx_requires_nonempty();
401 : return c.front();
402 : }
403 :
404 : /**
405 : * @brief Add data to the %queue.
406 : * @param x Data to be added.
407 : *
408 : * This is a typical %queue operation.
409 : * The time complexity of the operation depends on the underlying
410 : * sequence.
411 : */
412 : void
413 : push(const value_type& __x)
414 : {
415 : c.push_back(__x);
416 : std::push_heap(c.begin(), c.end(), comp);
417 : }
418 :
419 : /**
420 : * @brief Removes first element.
421 : *
422 : * This is a typical %queue operation. It shrinks the %queue
423 : * by one. The time complexity of the operation depends on the
424 : * underlying sequence.
425 : *
426 : * Note that no data is returned, and if the first element's
427 : * data is needed, it should be retrieved before pop() is
428 : * called.
429 : */
430 : void
431 : pop()
432 : {
433 : __glibcxx_requires_nonempty();
434 : std::pop_heap(c.begin(), c.end(), comp);
435 : c.pop_back();
436 : }
437 : };
438 :
439 : // No equality/comparison operators are provided for priority_queue.
440 :
441 : _GLIBCXX_END_NAMESPACE
442 :
443 : #endif /* _QUEUE_H */
|
