OSDN Git Service

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