Line data Source code
1 : // Queue implementation -*- C++ -*-
2 :
3 : // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
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 3, 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 : // Under Section 7 of GPL version 3, you are granted additional
18 : // permissions described in the GCC Runtime Library Exception, version
19 : // 3.1, as published by the Free Software Foundation.
20 :
21 : // You should have received a copy of the GNU General Public License and
22 : // a copy of the GCC Runtime Library Exception along with this program;
23 : // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 : // <http://www.gnu.org/licenses/>.
25 :
26 : /*
27 : *
28 : * Copyright (c) 1994
29 : * Hewlett-Packard Company
30 : *
31 : * Permission to use, copy, modify, distribute and sell this software
32 : * and its documentation for any purpose is hereby granted without fee,
33 : * provided that the above copyright notice appear in all copies and
34 : * that both that copyright notice and this permission notice appear
35 : * in supporting documentation. Hewlett-Packard Company makes no
36 : * representations about the suitability of this software for any
37 : * purpose. It is provided "as is" without express or implied warranty.
38 : *
39 : *
40 : * Copyright (c) 1996,1997
41 : * Silicon Graphics Computer Systems, Inc.
42 : *
43 : * Permission to use, copy, modify, distribute and sell this software
44 : * and its documentation for any purpose is hereby granted without fee,
45 : * provided that the above copyright notice appear in all copies and
46 : * that both that copyright notice and this permission notice appear
47 : * in supporting documentation. Silicon Graphics makes no
48 : * representations about the suitability of this software for any
49 : * purpose. It is provided "as is" without express or implied warranty.
50 : */
51 :
52 : /** @file stl_queue.h
53 : * This is an internal header file, included by other library headers.
54 : * You should not attempt to use it directly.
55 : */
56 :
57 : #ifndef _STL_QUEUE_H
58 : #define _STL_QUEUE_H 1
59 :
60 : #include <bits/concept_check.h>
61 : #include <debug/debug.h>
62 :
63 : _GLIBCXX_BEGIN_NAMESPACE(std)
64 :
65 : /**
66 : * @brief A standard container giving FIFO behavior.
67 : *
68 : * @ingroup sequences
69 : *
70 : * Meets many of the requirements of a
71 : * <a href="tables.html#65">container</a>,
72 : * but does not define anything to do with iterators. Very few of the
73 : * other standard container interfaces are defined.
74 : *
75 : * This is not a true container, but an @e adaptor. It holds another
76 : * container, and provides a wrapper interface to that container. The
77 : * wrapper is what enforces strict first-in-first-out %queue behavior.
78 : *
79 : * The second template parameter defines the type of the underlying
80 : * sequence/container. It defaults to std::deque, but it can be any type
81 : * that supports @c front, @c back, @c push_back, and @c pop_front,
82 : * such as std::list or an appropriate user-defined type.
83 : *
84 : * Members not found in "normal" containers are @c container_type,
85 : * which is a typedef for the second Sequence parameter, and @c push and
86 : * @c pop, which are standard %queue/FIFO operations.
87 : */
88 : template<typename _Tp, typename _Sequence = deque<_Tp> >
89 : class queue
90 0 : {
91 : // concept requirements
92 : typedef typename _Sequence::value_type _Sequence_value_type;
93 : __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
94 : __glibcxx_class_requires(_Sequence, _FrontInsertionSequenceConcept)
95 : __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept)
96 : __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
97 :
98 : template<typename _Tp1, typename _Seq1>
99 : friend bool
100 : operator==(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
101 :
102 : template<typename _Tp1, typename _Seq1>
103 : friend bool
104 : operator<(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
105 :
106 : public:
107 : typedef typename _Sequence::value_type value_type;
108 : typedef typename _Sequence::reference reference;
109 : typedef typename _Sequence::const_reference const_reference;
110 : typedef typename _Sequence::size_type size_type;
111 : typedef _Sequence container_type;
112 :
113 : protected:
114 : /**
115 : * 'c' is the underlying container. Maintainers wondering why
116 : * this isn't uglified as per style guidelines should note that
117 : * this name is specified in the standard, [23.2.3.1]. (Why?
118 : * Presumably for the same reason that it's protected instead
119 : * of private: to allow derivation. But none of the other
120 : * containers allow for derivation. Odd.)
121 : */
122 : _Sequence c;
123 :
124 : public:
125 : /**
126 : * @brief Default constructor creates no elements.
127 : */
128 : #ifndef __GXX_EXPERIMENTAL_CXX0X__
129 : explicit
130 165 : queue(const _Sequence& __c = _Sequence())
131 165 : : c(__c) { }
132 : #else
133 : explicit
134 : queue(const _Sequence& __c)
135 : : c(__c) { }
136 :
137 : explicit
138 : queue(_Sequence&& __c = _Sequence())
139 : : c(std::move(__c)) { }
140 :
141 : queue(queue&& __q)
142 : : c(std::move(__q.c)) { }
143 :
144 : queue&
145 : operator=(queue&& __q)
146 : {
147 : c = std::move(__q.c);
148 : return *this;
149 : }
150 : #endif
151 :
152 : /**
153 : * Returns true if the %queue is empty.
154 : */
155 : bool
156 0 : empty() const
157 0 : { return c.empty(); }
158 :
159 : /** Returns the number of elements in the %queue. */
160 : size_type
161 : size() const
162 : { return c.size(); }
163 :
164 : /**
165 : * Returns a read/write reference to the data at the first
166 : * element of the %queue.
167 : */
168 : reference
169 0 : front()
170 : {
171 : __glibcxx_requires_nonempty();
172 0 : return c.front();
173 : }
174 :
175 : /**
176 : * Returns a read-only (constant) reference to the data at the first
177 : * element of the %queue.
178 : */
179 : const_reference
180 : front() const
181 : {
182 : __glibcxx_requires_nonempty();
183 : return c.front();
184 : }
185 :
186 : /**
187 : * Returns a read/write reference to the data at the last
188 : * element of the %queue.
189 : */
190 : reference
191 : back()
192 : {
193 : __glibcxx_requires_nonempty();
194 : return c.back();
195 : }
196 :
197 : /**
198 : * Returns a read-only (constant) reference to the data at the last
199 : * element of the %queue.
200 : */
201 : const_reference
202 : back() const
203 : {
204 : __glibcxx_requires_nonempty();
205 : return c.back();
206 : }
207 :
208 : /**
209 : * @brief Add data to the end of the %queue.
210 : * @param x Data to be added.
211 : *
212 : * This is a typical %queue operation. The function creates an
213 : * element at the end of the %queue and assigns the given data
214 : * to it. The time complexity of the operation depends on the
215 : * underlying sequence.
216 : */
217 : void
218 0 : push(const value_type& __x)
219 0 : { c.push_back(__x); }
220 :
221 : #ifdef __GXX_EXPERIMENTAL_CXX0X__
222 : void
223 : push(value_type&& __x)
224 : { c.push_back(std::move(__x)); }
225 :
226 : template<typename... _Args>
227 : void
228 : emplace(_Args&&... __args)
229 : { c.emplace_back(std::forward<_Args>(__args)...); }
230 : #endif
231 :
232 : /**
233 : * @brief Removes first element.
234 : *
235 : * This is a typical %queue operation. It shrinks the %queue by one.
236 : * The time complexity of the operation depends on the underlying
237 : * sequence.
238 : *
239 : * Note that no data is returned, and if the first element's
240 : * data is needed, it should be retrieved before pop() is
241 : * called.
242 : */
243 : void
244 0 : pop()
245 : {
246 : __glibcxx_requires_nonempty();
247 0 : c.pop_front();
248 0 : }
249 :
250 : #ifdef __GXX_EXPERIMENTAL_CXX0X__
251 : void
252 : swap(queue&& __q)
253 : { c.swap(__q.c); }
254 : #endif
255 : };
256 :
257 : /**
258 : * @brief Queue equality comparison.
259 : * @param x A %queue.
260 : * @param y A %queue of the same type as @a x.
261 : * @return True iff the size and elements of the queues are equal.
262 : *
263 : * This is an equivalence relation. Complexity and semantics depend on the
264 : * underlying sequence type, but the expected rules are: this relation is
265 : * linear in the size of the sequences, and queues are considered equivalent
266 : * if their sequences compare equal.
267 : */
268 : template<typename _Tp, typename _Seq>
269 : inline bool
270 : operator==(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
271 : { return __x.c == __y.c; }
272 :
273 : /**
274 : * @brief Queue ordering relation.
275 : * @param x A %queue.
276 : * @param y A %queue of the same type as @a x.
277 : * @return True iff @a x is lexicographically less than @a y.
278 : *
279 : * This is an total ordering relation. Complexity and semantics
280 : * depend on the underlying sequence type, but the expected rules
281 : * are: this relation is linear in the size of the sequences, the
282 : * elements must be comparable with @c <, and
283 : * std::lexicographical_compare() is usually used to make the
284 : * determination.
285 : */
286 : template<typename _Tp, typename _Seq>
287 : inline bool
288 : operator<(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
289 : { return __x.c < __y.c; }
290 :
291 : /// Based on operator==
292 : template<typename _Tp, typename _Seq>
293 : inline bool
294 : operator!=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
295 : { return !(__x == __y); }
296 :
297 : /// Based on operator<
298 : template<typename _Tp, typename _Seq>
299 : inline bool
300 : operator>(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
301 : { return __y < __x; }
302 :
303 : /// Based on operator<
304 : template<typename _Tp, typename _Seq>
305 : inline bool
306 : operator<=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
307 : { return !(__y < __x); }
308 :
309 : /// Based on operator<
310 : template<typename _Tp, typename _Seq>
311 : inline bool
312 : operator>=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
313 : { return !(__x < __y); }
314 :
315 : #ifdef __GXX_EXPERIMENTAL_CXX0X__
316 : template<typename _Tp, typename _Seq>
317 : inline void
318 : swap(queue<_Tp, _Seq>& __x, queue<_Tp, _Seq>& __y)
319 : { __x.swap(__y); }
320 :
321 : template<typename _Tp, typename _Seq>
322 : inline void
323 : swap(queue<_Tp, _Seq>&& __x, queue<_Tp, _Seq>& __y)
324 : { __x.swap(__y); }
325 :
326 : template<typename _Tp, typename _Seq>
327 : inline void
328 : swap(queue<_Tp, _Seq>& __x, queue<_Tp, _Seq>&& __y)
329 : { __x.swap(__y); }
330 : #endif
331 :
332 : /**
333 : * @brief A standard container automatically sorting its contents.
334 : *
335 : * @ingroup sequences
336 : *
337 : * This is not a true container, but an @e adaptor. It holds
338 : * another container, and provides a wrapper interface to that
339 : * container. The wrapper is what enforces priority-based sorting
340 : * and %queue behavior. Very few of the standard container/sequence
341 : * interface requirements are met (e.g., iterators).
342 : *
343 : * The second template parameter defines the type of the underlying
344 : * sequence/container. It defaults to std::vector, but it can be
345 : * any type that supports @c front(), @c push_back, @c pop_back,
346 : * and random-access iterators, such as std::deque or an
347 : * appropriate user-defined type.
348 : *
349 : * The third template parameter supplies the means of making
350 : * priority comparisons. It defaults to @c less<value_type> but
351 : * can be anything defining a strict weak ordering.
352 : *
353 : * Members not found in "normal" containers are @c container_type,
354 : * which is a typedef for the second Sequence parameter, and @c
355 : * push, @c pop, and @c top, which are standard %queue operations.
356 : *
357 : * @note No equality/comparison operators are provided for
358 : * %priority_queue.
359 : *
360 : * @note Sorting of the elements takes place as they are added to,
361 : * and removed from, the %priority_queue using the
362 : * %priority_queue's member functions. If you access the elements
363 : * by other means, and change their data such that the sorting
364 : * order would be different, the %priority_queue will not re-sort
365 : * the elements for you. (How could it know to do so?)
366 : */
367 : template<typename _Tp, typename _Sequence = vector<_Tp>,
368 : typename _Compare = less<typename _Sequence::value_type> >
369 : class priority_queue
370 0 : {
371 : // concept requirements
372 : typedef typename _Sequence::value_type _Sequence_value_type;
373 : __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
374 : __glibcxx_class_requires(_Sequence, _SequenceConcept)
375 : __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept)
376 : __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
377 : __glibcxx_class_requires4(_Compare, bool, _Tp, _Tp,
378 : _BinaryFunctionConcept)
379 :
380 : public:
381 : typedef typename _Sequence::value_type value_type;
382 : typedef typename _Sequence::reference reference;
383 : typedef typename _Sequence::const_reference const_reference;
384 : typedef typename _Sequence::size_type size_type;
385 : typedef _Sequence container_type;
386 :
387 : protected:
388 : // See queue::c for notes on these names.
389 : _Sequence c;
390 : _Compare comp;
391 :
392 : public:
393 : /**
394 : * @brief Default constructor creates no elements.
395 : */
396 : #ifndef __GXX_EXPERIMENTAL_CXX0X__
397 : explicit
398 0 : priority_queue(const _Compare& __x = _Compare(),
399 : const _Sequence& __s = _Sequence())
400 0 : : c(__s), comp(__x)
401 0 : { std::make_heap(c.begin(), c.end(), comp); }
402 : #else
403 : explicit
404 : priority_queue(const _Compare& __x,
405 : const _Sequence& __s)
406 : : c(__s), comp(__x)
407 : { std::make_heap(c.begin(), c.end(), comp); }
408 :
409 : explicit
410 : priority_queue(const _Compare& __x = _Compare(),
411 : _Sequence&& __s = _Sequence())
412 : : c(std::move(__s)), comp(__x)
413 : { std::make_heap(c.begin(), c.end(), comp); }
414 : #endif
415 :
416 : /**
417 : * @brief Builds a %queue from a range.
418 : * @param first An input iterator.
419 : * @param last An input iterator.
420 : * @param x A comparison functor describing a strict weak ordering.
421 : * @param s An initial sequence with which to start.
422 : *
423 : * Begins by copying @a s, inserting a copy of the elements
424 : * from @a [first,last) into the copy of @a s, then ordering
425 : * the copy according to @a x.
426 : *
427 : * For more information on function objects, see the
428 : * documentation on @link functors functor base
429 : * classes@endlink.
430 : */
431 : #ifndef __GXX_EXPERIMENTAL_CXX0X__
432 : template<typename _InputIterator>
433 : priority_queue(_InputIterator __first, _InputIterator __last,
434 : const _Compare& __x = _Compare(),
435 : const _Sequence& __s = _Sequence())
436 : : c(__s), comp(__x)
437 : {
438 : __glibcxx_requires_valid_range(__first, __last);
439 : c.insert(c.end(), __first, __last);
440 : std::make_heap(c.begin(), c.end(), comp);
441 : }
442 : #else
443 : template<typename _InputIterator>
444 : priority_queue(_InputIterator __first, _InputIterator __last,
445 : const _Compare& __x,
446 : const _Sequence& __s)
447 : : c(__s), comp(__x)
448 : {
449 : __glibcxx_requires_valid_range(__first, __last);
450 : c.insert(c.end(), __first, __last);
451 : std::make_heap(c.begin(), c.end(), comp);
452 : }
453 :
454 : template<typename _InputIterator>
455 : priority_queue(_InputIterator __first, _InputIterator __last,
456 : const _Compare& __x = _Compare(),
457 : _Sequence&& __s = _Sequence())
458 : : c(std::move(__s)), comp(__x)
459 : {
460 : __glibcxx_requires_valid_range(__first, __last);
461 : c.insert(c.end(), __first, __last);
462 : std::make_heap(c.begin(), c.end(), comp);
463 : }
464 :
465 : priority_queue(priority_queue&& __pq)
466 : : c(std::move(__pq.c)), comp(std::move(__pq.comp)) { }
467 :
468 : priority_queue&
469 : operator=(priority_queue&& __pq)
470 : {
471 : c = std::move(__pq.c);
472 : comp = std::move(__pq.comp);
473 : return *this;
474 : }
475 : #endif
476 :
477 : /**
478 : * Returns true if the %queue is empty.
479 : */
480 : bool
481 0 : empty() const
482 0 : { return c.empty(); }
483 :
484 : /** Returns the number of elements in the %queue. */
485 : size_type
486 0 : size() const
487 0 : { return c.size(); }
488 :
489 : /**
490 : * Returns a read-only (constant) reference to the data at the first
491 : * element of the %queue.
492 : */
493 : const_reference
494 0 : top() const
495 : {
496 : __glibcxx_requires_nonempty();
497 0 : return c.front();
498 : }
499 :
500 : /**
501 : * @brief Add data to the %queue.
502 : * @param x Data to be added.
503 : *
504 : * This is a typical %queue operation.
505 : * The time complexity of the operation depends on the underlying
506 : * sequence.
507 : */
508 : void
509 0 : push(const value_type& __x)
510 : {
511 0 : c.push_back(__x);
512 0 : std::push_heap(c.begin(), c.end(), comp);
513 0 : }
514 :
515 : #ifdef __GXX_EXPERIMENTAL_CXX0X__
516 : void
517 : push(value_type&& __x)
518 : {
519 : c.push_back(std::move(__x));
520 : std::push_heap(c.begin(), c.end(), comp);
521 : }
522 :
523 : template<typename... _Args>
524 : void
525 : emplace(_Args&&... __args)
526 : {
527 : c.emplace_back(std::forward<_Args>(__args)...);
528 : std::push_heap(c.begin(), c.end(), comp);
529 : }
530 : #endif
531 :
532 : /**
533 : * @brief Removes first element.
534 : *
535 : * This is a typical %queue operation. It shrinks the %queue
536 : * by one. The time complexity of the operation depends on the
537 : * underlying sequence.
538 : *
539 : * Note that no data is returned, and if the first element's
540 : * data is needed, it should be retrieved before pop() is
541 : * called.
542 : */
543 : void
544 0 : pop()
545 : {
546 : __glibcxx_requires_nonempty();
547 0 : std::pop_heap(c.begin(), c.end(), comp);
548 0 : c.pop_back();
549 0 : }
550 :
551 : #ifdef __GXX_EXPERIMENTAL_CXX0X__
552 : void
553 : swap(priority_queue&& __pq)
554 : {
555 : using std::swap;
556 : c.swap(__pq.c);
557 : swap(comp, __pq.comp);
558 : }
559 : #endif
560 : };
561 :
562 : // No equality/comparison operators are provided for priority_queue.
563 :
564 : #ifdef __GXX_EXPERIMENTAL_CXX0X__
565 : template<typename _Tp, typename _Sequence, typename _Compare>
566 : inline void
567 : swap(priority_queue<_Tp, _Sequence, _Compare>& __x,
568 : priority_queue<_Tp, _Sequence, _Compare>& __y)
569 : { __x.swap(__y); }
570 :
571 : template<typename _Tp, typename _Sequence, typename _Compare>
572 : inline void
573 : swap(priority_queue<_Tp, _Sequence, _Compare>&& __x,
574 : priority_queue<_Tp, _Sequence, _Compare>& __y)
575 : { __x.swap(__y); }
576 :
577 : template<typename _Tp, typename _Sequence, typename _Compare>
578 : inline void
579 : swap(priority_queue<_Tp, _Sequence, _Compare>& __x,
580 : priority_queue<_Tp, _Sequence, _Compare>&& __y)
581 : { __x.swap(__y); }
582 : #endif
583 :
584 : _GLIBCXX_END_NAMESPACE
585 :
586 : #endif /* _STL_QUEUE_H */
|
