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

   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     {
  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       : 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       { return c.empty(); }
 164
 165       /**  Returns the number of elements in the %queue.  */
 166       size_type
 167       size() const
 168       { 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         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       push(const value_type& __x)
 226       { 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       pop()
 248       {
 249         __glibcxx_requires_nonempty();
 250         c.pop_front();
 251       }
 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 */