Branch data Line data Source code
1 : : // Queue implementation -*- C++ -*-
2 : :
3 : : // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
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 _STL_QUEUE_H
63 : : #define _STL_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 : 2 : {
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 : : #ifndef __GXX_EXPERIMENTAL_CXX0X__
135 : : explicit
136 : : queue(const _Sequence& __c = _Sequence())
137 : 2 : : c(__c) { }
138 : : #else
139 : : explicit
140 : : queue(const _Sequence& __c)
141 : : : c(__c) { }
142 : :
143 : : explicit
144 : : queue(_Sequence&& __c = _Sequence())
145 : : : c(std::move(__c)) { }
146 : :
147 : : queue(queue&& __q)
148 : : : c(std::move(__q.c)) { }
149 : :
150 : : queue&
151 : : operator=(queue&& __q)
152 : : {
153 : : c = std::move(__q.c);
154 : : return *this;
155 : : }
156 : : #endif
157 : :
158 : : /**
159 : : * Returns true if the %queue is empty.
160 : : */
161 : : bool
162 : : empty() const
163 : 108006 : { return c.empty(); }
164 : :
165 : : /** Returns the number of elements in the %queue. */
166 : : size_type
167 : : size() const
168 : 0 : { return c.size(); }
169 : :
170 : : /**
171 : : * Returns a read/write reference to the data at the first
172 : : * element of the %queue.
173 : : */
174 : : reference
175 : : front()
176 : : {
177 : : __glibcxx_requires_nonempty();
178 : 0 : return c.front();
179 : : }
180 : :
181 : : /**
182 : : * Returns a read-only (constant) reference to the data at the first
183 : : * element of the %queue.
184 : : */
185 : : const_reference
186 : : front() const
187 : : {
188 : : __glibcxx_requires_nonempty();
189 : : return c.front();
190 : : }
191 : :
192 : : /**
193 : : * Returns a read/write reference to the data at the last
194 : : * element of the %queue.
195 : : */
196 : : reference
197 : : back()
198 : : {
199 : : __glibcxx_requires_nonempty();
200 : : return c.back();
201 : : }
202 : :
203 : : /**
204 : : * Returns a read-only (constant) reference to the data at the last
205 : : * element of the %queue.
206 : : */
207 : : const_reference
208 : : back() const
209 : : {
210 : : __glibcxx_requires_nonempty();
211 : : return c.back();
212 : : }
213 : :
214 : : /**
215 : : * @brief Add data to the end of the %queue.
216 : : * @param x Data to be added.
217 : : *
218 : : * This is a typical %queue operation. The function creates an
219 : : * element at the end of the %queue and assigns the given data
220 : : * to it. The time complexity of the operation depends on the
221 : : * underlying sequence.
222 : : */
223 : : #ifndef __GXX_EXPERIMENTAL_CXX0X__
224 : : void
225 : 0 : push(const value_type& __x)
226 : 0 : { c.push_back(__x); }
227 : : #else
228 : : // NB: DR 756.
229 : : template<typename... _Args>
230 : : void
231 : : push(_Args&&... __args)
232 : : { c.push_back(std::forward<_Args>(__args)...); }
233 : : #endif
234 : :
235 : : /**
236 : : * @brief Removes first element.
237 : : *
238 : : * This is a typical %queue operation. It shrinks the %queue by one.
239 : : * The time complexity of the operation depends on the underlying
240 : : * sequence.
241 : : *
242 : : * Note that no data is returned, and if the first element's
243 : : * data is needed, it should be retrieved before pop() is
244 : : * called.
245 : : */
246 : : void
247 : 0 : pop()
248 : : {
249 : : __glibcxx_requires_nonempty();
250 : 0 : c.pop_front();
251 : 0 : }
252 : :
253 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
254 : : void
255 : : swap(queue&& __q)
256 : : { c.swap(__q.c); }
257 : : #endif
258 : : };
259 : :
260 : : /**
261 : : * @brief Queue equality comparison.
262 : : * @param x A %queue.
263 : : * @param y A %queue of the same type as @a x.
264 : : * @return True iff the size and elements of the queues are equal.
265 : : *
266 : : * This is an equivalence relation. Complexity and semantics depend on the
267 : : * underlying sequence type, but the expected rules are: this relation is
268 : : * linear in the size of the sequences, and queues are considered equivalent
269 : : * if their sequences compare equal.
270 : : */
271 : : template<typename _Tp, typename _Seq>
272 : : inline bool
273 : : operator==(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
274 : : { return __x.c == __y.c; }
275 : :
276 : : /**
277 : : * @brief Queue ordering relation.
278 : : * @param x A %queue.
279 : : * @param y A %queue of the same type as @a x.
280 : : * @return True iff @a x is lexicographically less than @a y.
281 : : *
282 : : * This is an total ordering relation. Complexity and semantics
283 : : * depend on the underlying sequence type, but the expected rules
284 : : * are: this relation is linear in the size of the sequences, the
285 : : * elements must be comparable with @c <, and
286 : : * std::lexicographical_compare() is usually used to make the
287 : : * determination.
288 : : */
289 : : template<typename _Tp, typename _Seq>
290 : : inline bool
291 : : operator<(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
292 : : { return __x.c < __y.c; }
293 : :
294 : : /// Based on operator==
295 : : template<typename _Tp, typename _Seq>
296 : : inline bool
297 : : operator!=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
298 : : { return !(__x == __y); }
299 : :
300 : : /// Based on operator<
301 : : template<typename _Tp, typename _Seq>
302 : : inline bool
303 : : operator>(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
304 : : { return __y < __x; }
305 : :
306 : : /// Based on operator<
307 : : template<typename _Tp, typename _Seq>
308 : : inline bool
309 : : operator<=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
310 : : { return !(__y < __x); }
311 : :
312 : : /// Based on operator<
313 : : template<typename _Tp, typename _Seq>
314 : : inline bool
315 : : operator>=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
316 : : { return !(__x < __y); }
317 : :
318 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
319 : : template<typename _Tp, typename _Seq>
320 : : inline void
321 : : swap(queue<_Tp, _Seq>& __x, queue<_Tp, _Seq>& __y)
322 : : { __x.swap(__y); }
323 : :
324 : : template<typename _Tp, typename _Seq>
325 : : inline void
326 : : swap(queue<_Tp, _Seq>&& __x, queue<_Tp, _Seq>& __y)
327 : : { __x.swap(__y); }
328 : :
329 : : template<typename _Tp, typename _Seq>
330 : : inline void
331 : : swap(queue<_Tp, _Seq>& __x, queue<_Tp, _Seq>&& __y)
332 : : { __x.swap(__y); }
333 : : #endif
334 : :
335 : : /**
336 : : * @brief A standard container automatically sorting its contents.
337 : : *
338 : : * @ingroup Containers
339 : : * @ingroup Sequences
340 : : *
341 : : * This is not a true container, but an @e adaptor. It holds
342 : : * another container, and provides a wrapper interface to that
343 : : * container. The wrapper is what enforces priority-based sorting
344 : : * and %queue behavior. Very few of the standard container/sequence
345 : : * interface requirements are met (e.g., iterators).
346 : : *
347 : : * The second template parameter defines the type of the underlying
348 : : * sequence/container. It defaults to std::vector, but it can be
349 : : * any type that supports @c front(), @c push_back, @c pop_back,
350 : : * and random-access iterators, such as std::deque or an
351 : : * appropriate user-defined type.
352 : : *
353 : : * The third template parameter supplies the means of making
354 : : * priority comparisons. It defaults to @c less<value_type> but
355 : : * can be anything defining a strict weak ordering.
356 : : *
357 : : * Members not found in "normal" containers are @c container_type,
358 : : * which is a typedef for the second Sequence parameter, and @c
359 : : * push, @c pop, and @c top, which are standard %queue operations.
360 : : *
361 : : * @note No equality/comparison operators are provided for
362 : : * %priority_queue.
363 : : *
364 : : * @note Sorting of the elements takes place as they are added to,
365 : : * and removed from, the %priority_queue using the
366 : : * %priority_queue's member functions. If you access the elements
367 : : * by other means, and change their data such that the sorting
368 : : * order would be different, the %priority_queue will not re-sort
369 : : * the elements for you. (How could it know to do so?)
370 : : */
371 : : template<typename _Tp, typename _Sequence = vector<_Tp>,
372 : : typename _Compare = less<typename _Sequence::value_type> >
373 : : class priority_queue
374 : : {
375 : : // concept requirements
376 : : typedef typename _Sequence::value_type _Sequence_value_type;
377 : : __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
378 : : __glibcxx_class_requires(_Sequence, _SequenceConcept)
379 : : __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept)
380 : : __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
381 : : __glibcxx_class_requires4(_Compare, bool, _Tp, _Tp,
382 : : _BinaryFunctionConcept)
383 : :
384 : : public:
385 : : typedef typename _Sequence::value_type value_type;
386 : : typedef typename _Sequence::reference reference;
387 : : typedef typename _Sequence::const_reference const_reference;
388 : : typedef typename _Sequence::size_type size_type;
389 : : typedef _Sequence container_type;
390 : :
391 : : protected:
392 : : // See queue::c for notes on these names.
393 : : _Sequence c;
394 : : _Compare comp;
395 : :
396 : : public:
397 : : /**
398 : : * @brief Default constructor creates no elements.
399 : : */
400 : : #ifndef __GXX_EXPERIMENTAL_CXX0X__
401 : : explicit
402 : : priority_queue(const _Compare& __x = _Compare(),
403 : : const _Sequence& __s = _Sequence())
404 : : : c(__s), comp(__x)
405 : : { std::make_heap(c.begin(), c.end(), comp); }
406 : : #else
407 : : explicit
408 : : priority_queue(const _Compare& __x,
409 : : const _Sequence& __s)
410 : : : c(__s), comp(__x)
411 : : { std::make_heap(c.begin(), c.end(), comp); }
412 : :
413 : : explicit
414 : : priority_queue(const _Compare& __x = _Compare(),
415 : : _Sequence&& __s = _Sequence())
416 : : : c(std::move(__s)), comp(__x)
417 : : { std::make_heap(c.begin(), c.end(), comp); }
418 : : #endif
419 : :
420 : : /**
421 : : * @brief Builds a %queue from a range.
422 : : * @param first An input iterator.
423 : : * @param last An input iterator.
424 : : * @param x A comparison functor describing a strict weak ordering.
425 : : * @param s An initial sequence with which to start.
426 : : *
427 : : * Begins by copying @a s, inserting a copy of the elements
428 : : * from @a [first,last) into the copy of @a s, then ordering
429 : : * the copy according to @a x.
430 : : *
431 : : * For more information on function objects, see the
432 : : * documentation on @link s20_3_1_base functor base
433 : : * classes@endlink.
434 : : */
435 : : #ifndef __GXX_EXPERIMENTAL_CXX0X__
436 : : template<typename _InputIterator>
437 : : priority_queue(_InputIterator __first, _InputIterator __last,
438 : : const _Compare& __x = _Compare(),
439 : : const _Sequence& __s = _Sequence())
440 : : : c(__s), comp(__x)
441 : : {
442 : : __glibcxx_requires_valid_range(__first, __last);
443 : : c.insert(c.end(), __first, __last);
444 : : std::make_heap(c.begin(), c.end(), comp);
445 : : }
446 : : #else
447 : : template<typename _InputIterator>
448 : : priority_queue(_InputIterator __first, _InputIterator __last,
449 : : const _Compare& __x,
450 : : const _Sequence& __s)
451 : : : c(__s), comp(__x)
452 : : {
453 : : __glibcxx_requires_valid_range(__first, __last);
454 : : c.insert(c.end(), __first, __last);
455 : : std::make_heap(c.begin(), c.end(), comp);
456 : : }
457 : :
458 : : template<typename _InputIterator>
459 : : priority_queue(_InputIterator __first, _InputIterator __last,
460 : : const _Compare& __x = _Compare(),
461 : : _Sequence&& __s = _Sequence())
462 : : : c(std::move(__s)), comp(__x)
463 : : {
464 : : __glibcxx_requires_valid_range(__first, __last);
465 : : c.insert(c.end(), __first, __last);
466 : : std::make_heap(c.begin(), c.end(), comp);
467 : : }
468 : :
469 : : priority_queue(priority_queue&& __pq)
470 : : : c(std::move(__pq.c)), comp(std::move(__pq.comp)) { }
471 : :
472 : : priority_queue&
473 : : operator=(priority_queue&& __pq)
474 : : {
475 : : c = std::move(__pq.c);
476 : : comp = std::move(__pq.comp);
477 : : return *this;
478 : : }
479 : : #endif
480 : :
481 : : /**
482 : : * Returns true if the %queue is empty.
483 : : */
484 : : bool
485 : : empty() const
486 : : { return c.empty(); }
487 : :
488 : : /** Returns the number of elements in the %queue. */
489 : : size_type
490 : : size() const
491 : : { return c.size(); }
492 : :
493 : : /**
494 : : * Returns a read-only (constant) reference to the data at the first
495 : : * element of the %queue.
496 : : */
497 : : const_reference
498 : : top() const
499 : : {
500 : : __glibcxx_requires_nonempty();
501 : : return c.front();
502 : : }
503 : :
504 : : /**
505 : : * @brief Add data to the %queue.
506 : : * @param x Data to be added.
507 : : *
508 : : * This is a typical %queue operation.
509 : : * The time complexity of the operation depends on the underlying
510 : : * sequence.
511 : : */
512 : : #ifndef __GXX_EXPERIMENTAL_CXX0X__
513 : : void
514 : : push(const value_type& __x)
515 : : {
516 : : c.push_back(__x);
517 : : std::push_heap(c.begin(), c.end(), comp);
518 : : }
519 : : #else
520 : : // NB: DR 756.
521 : : template<typename... _Args>
522 : : void
523 : : push(_Args&&... __args)
524 : : {
525 : : c.push_back(std::forward<_Args>(__args)...);
526 : : std::push_heap(c.begin(), c.end(), comp);
527 : : }
528 : : #endif
529 : :
530 : : /**
531 : : * @brief Removes first element.
532 : : *
533 : : * This is a typical %queue operation. It shrinks the %queue
534 : : * by one. The time complexity of the operation depends on the
535 : : * underlying sequence.
536 : : *
537 : : * Note that no data is returned, and if the first element's
538 : : * data is needed, it should be retrieved before pop() is
539 : : * called.
540 : : */
541 : : void
542 : : pop()
543 : : {
544 : : __glibcxx_requires_nonempty();
545 : : std::pop_heap(c.begin(), c.end(), comp);
546 : : c.pop_back();
547 : : }
548 : :
549 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
550 : : void
551 : : swap(priority_queue&& __pq)
552 : : {
553 : : using std::swap;
554 : : c.swap(__pq.c);
555 : : swap(comp, __pq.comp);
556 : : }
557 : : #endif
558 : : };
559 : :
560 : : // No equality/comparison operators are provided for priority_queue.
561 : :
562 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
563 : : template<typename _Tp, typename _Sequence, typename _Compare>
564 : : inline void
565 : : swap(priority_queue<_Tp, _Sequence, _Compare>& __x,
566 : : priority_queue<_Tp, _Sequence, _Compare>& __y)
567 : : { __x.swap(__y); }
568 : :
569 : : template<typename _Tp, typename _Sequence, typename _Compare>
570 : : inline void
571 : : swap(priority_queue<_Tp, _Sequence, _Compare>&& __x,
572 : : priority_queue<_Tp, _Sequence, _Compare>& __y)
573 : : { __x.swap(__y); }
574 : :
575 : : template<typename _Tp, typename _Sequence, typename _Compare>
576 : : inline void
577 : : swap(priority_queue<_Tp, _Sequence, _Compare>& __x,
578 : : priority_queue<_Tp, _Sequence, _Compare>&& __y)
579 : : { __x.swap(__y); }
580 : : #endif
581 : :
582 : : _GLIBCXX_END_NAMESPACE
583 : :
584 : : #endif /* _STL_QUEUE_H */
|
