l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.8/include/bits/stl_queue.h

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