libstdc++-v3/include/bits/stl_queue.h

   1 // Queue implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006
   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 _QUEUE_H
  63 #define _QUEUE_H 1
  64
  65 #include <bits/concept_check.h>
  66 #include <debug/debug.h>
  67
  68 _GLIBCXX_BEGIN_NAMESPACE(std)
  69
  70   // Forward declarations of operators < and ==, needed for friend declaration.
  71   template<typename _Tp, typename _Sequence = deque<_Tp> >
  72     class queue;
  73
  74   template<typename _Tp, typename _Seq>
  75     inline bool
  76     operator==(const queue<_Tp, _Seq>&, const queue<_Tp, _Seq>&);
  77
  78   template<typename _Tp, typename _Seq>
  79     inline bool
  80     operator<(const queue<_Tp, _Seq>&, const queue<_Tp, _Seq>&);
  81
  82   /**
  83    *  @brief  A standard container giving FIFO behavior.
  84    *
  85    *  @ingroup Containers
  86    *  @ingroup Sequences
  87    *
  88    *  Meets many of the requirements of a
  89    *  <a href="tables.html#65">container</a>,
  90    *  but does not define anything to do with iterators.  Very few of the
  91    *  other standard container interfaces are defined.
  92    *
  93    *  This is not a true container, but an @e adaptor.  It holds another
  94    *  container, and provides a wrapper interface to that container.  The
  95    *  wrapper is what enforces strict first-in-first-out %queue behavior.
  96    *
  97    *  The second template parameter defines the type of the underlying
  98    *  sequence/container.  It defaults to std::deque, but it can be any type
  99    *  that supports @c front, @c back, @c push_back, and @c pop_front,
 100    *  such as std::list or an appropriate user-defined type.
 101    *
 102    *  Members not found in "normal" containers are @c container_type,
 103    *  which is a typedef for the second Sequence parameter, and @c push and
 104    *  @c pop, which are standard %queue/FIFO operations.
 105   */
 106   template<typename _Tp, typename _Sequence>
 107     class queue
 108     {
 109       // concept requirements
 110       typedef typename _Sequence::value_type _Sequence_value_type;
 111       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
 112       __glibcxx_class_requires(_Sequence, _FrontInsertionSequenceConcept)
 113       __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept)
 114       __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
 115
 116       template<typename _Tp1, typename _Seq1>
 117         friend bool
 118         operator==(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
 119
 120       template<typename _Tp1, typename _Seq1>
 121         friend bool
 122         operator<(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
 123
 124     public:
 125       typedef typename _Sequence::value_type                value_type;
 126       typedef typename _Sequence::reference                 reference;
 127       typedef typename _Sequence::const_reference           const_reference;
 128       typedef typename _Sequence::size_type                 size_type;
 129       typedef          _Sequence                            container_type;
 130
 131     protected:
 132       /**
 133        *  'c' is the underlying container.  Maintainers wondering why
 134        *  this isn't uglified as per style guidelines should note that
 135        *  this name is specified in the standard, [23.2.3.1].  (Why?
 136        *  Presumably for the same reason that it's protected instead
 137        *  of private: to allow derivation.  But none of the other
 138        *  containers allow for derivation.  Odd.)
 139        */
 140       _Sequence c;
 141
 142     public:
 143       /**
 144        *  @brief  Default constructor creates no elements.
 145        */
 146       explicit
 147       queue(const _Sequence& __c = _Sequence()) : c(__c) {}
 148
 149       /**
 150        *  Returns true if the %queue is empty.
 151        */
 152       bool
 153       empty() const
 154       { return c.empty(); }
 155
 156       /**  Returns the number of elements in the %queue.  */
 157       size_type
 158       size() const
 159       { return c.size(); }
 160
 161       /**
 162        *  Returns a read/write reference to the data at the first
 163        *  element of the %queue.
 164        */
 165       reference
 166       front()
 167       {
 168         __glibcxx_requires_nonempty();
 169         return c.front();
 170       }
 171
 172       /**
 173        *  Returns a read-only (constant) reference to the data at the first
 174        *  element of the %queue.
 175        */
 176       const_reference
 177       front() const
 178       {
 179         __glibcxx_requires_nonempty();
 180         return c.front();
 181       }
 182
 183       /**
 184        *  Returns a read/write reference to the data at the last
 185        *  element of the %queue.
 186        */
 187       reference
 188       back()
 189       {
 190         __glibcxx_requires_nonempty();
 191         return c.back();
 192       }
 193
 194       /**
 195        *  Returns a read-only (constant) reference to the data at the last
 196        *  element of the %queue.
 197        */
 198       const_reference
 199       back() const
 200       {
 201         __glibcxx_requires_nonempty();
 202         return c.back();
 203       }
 204
 205       /**
 206        *  @brief  Add data to the end of the %queue.
 207        *  @param  x  Data to be added.
 208        *
 209        *  This is a typical %queue operation.  The function creates an
 210        *  element at the end of the %queue and assigns the given data
 211        *  to it.  The time complexity of the operation depends on the
 212        *  underlying sequence.
 213        */
 214       void
 215       push(const value_type& __x)
 216       { c.push_back(__x); }
 217
 218       /**
 219        *  @brief  Removes first element.
 220        *
 221        *  This is a typical %queue operation.  It shrinks the %queue by one.
 222        *  The time complexity of the operation depends on the underlying
 223        *  sequence.
 224        *
 225        *  Note that no data is returned, and if the first element's
 226        *  data is needed, it should be retrieved before pop() is
 227        *  called.
 228        */
 229       void
 230       pop()
 231       {
 232         __glibcxx_requires_nonempty();
 233         c.pop_front();
 234       }
 235     };
 236
 237
 238   /**
 239    *  @brief  Queue equality comparison.
 240    *  @param  x  A %queue.
 241    *  @param  y  A %queue of the same type as @a x.
 242    *  @return  True iff the size and elements of the queues are equal.
 243    *
 244    *  This is an equivalence relation.  Complexity and semantics depend on the
 245    *  underlying sequence type, but the expected rules are:  this relation is
 246    *  linear in the size of the sequences, and queues are considered equivalent
 247    *  if their sequences compare equal.
 248   */
 249   template<typename _Tp, typename _Seq>
 250     inline bool
 251     operator==(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
 252     { return __x.c == __y.c; }
 253
 254   /**
 255    *  @brief  Queue ordering relation.
 256    *  @param  x  A %queue.
 257    *  @param  y  A %queue of the same type as @a x.
 258    *  @return  True iff @a x is lexicographically less than @a y.
 259    *
 260    *  This is an total ordering relation.  Complexity and semantics
 261    *  depend on the underlying sequence type, but the expected rules
 262    *  are: this relation is linear in the size of the sequences, the
 263    *  elements must be comparable with @c <, and
 264    *  std::lexicographical_compare() is usually used to make the
 265    *  determination.
 266   */
 267   template<typename _Tp, typename _Seq>
 268     inline bool
 269     operator<(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
 270     { return __x.c < __y.c; }
 271
 272   /// Based on operator==
 273   template<typename _Tp, typename _Seq>
 274     inline bool
 275     operator!=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
 276     { return !(__x == __y); }
 277
 278   /// Based on operator<
 279   template<typename _Tp, typename _Seq>
 280     inline bool
 281     operator>(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
 282     { return __y < __x; }
 283
 284   /// Based on operator<
 285   template<typename _Tp, typename _Seq>
 286     inline bool
 287     operator<=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
 288     { return !(__y < __x); }
 289
 290   /// Based on operator<
 291   template<typename _Tp, typename _Seq>
 292     inline bool
 293     operator>=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
 294     { return !(__x < __y); }
 295
 296   /**
 297    *  @brief  A standard container automatically sorting its contents.
 298    *
 299    *  @ingroup Containers
 300    *  @ingroup Sequences
 301    *
 302    *  This is not a true container, but an @e adaptor.  It holds
 303    *  another container, and provides a wrapper interface to that
 304    *  container.  The wrapper is what enforces priority-based sorting
 305    *  and %queue behavior.  Very few of the standard container/sequence
 306    *  interface requirements are met (e.g., iterators).
 307    *
 308    *  The second template parameter defines the type of the underlying
 309    *  sequence/container.  It defaults to std::vector, but it can be
 310    *  any type that supports @c front(), @c push_back, @c pop_back,
 311    *  and random-access iterators, such as std::deque or an
 312    *  appropriate user-defined type.
 313    *
 314    *  The third template parameter supplies the means of making
 315    *  priority comparisons.  It defaults to @c less<value_type> but
 316    *  can be anything defining a strict weak ordering.
 317    *
 318    *  Members not found in "normal" containers are @c container_type,
 319    *  which is a typedef for the second Sequence parameter, and @c
 320    *  push, @c pop, and @c top, which are standard %queue operations.
 321    *
 322    *  @note No equality/comparison operators are provided for
 323    *  %priority_queue.
 324    *
 325    *  @note Sorting of the elements takes place as they are added to,
 326    *  and removed from, the %priority_queue using the
 327    *  %priority_queue's member functions.  If you access the elements
 328    *  by other means, and change their data such that the sorting
 329    *  order would be different, the %priority_queue will not re-sort
 330    *  the elements for you.  (How could it know to do so?)
 331   */
 332   template<typename _Tp, typename _Sequence = vector<_Tp>,
 333            typename _Compare  = less<typename _Sequence::value_type> >
 334     class priority_queue
 335     {
 336       // concept requirements
 337       typedef typename _Sequence::value_type _Sequence_value_type;
 338       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
 339       __glibcxx_class_requires(_Sequence, _SequenceConcept)
 340       __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept)
 341       __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
 342       __glibcxx_class_requires4(_Compare, bool, _Tp, _Tp,
 343                                 _BinaryFunctionConcept)
 344
 345     public:
 346       typedef typename _Sequence::value_type                value_type;
 347       typedef typename _Sequence::reference                 reference;
 348       typedef typename _Sequence::const_reference           const_reference;
 349       typedef typename _Sequence::size_type                 size_type;
 350       typedef          _Sequence                            container_type;
 351
 352     protected:
 353       //  See queue::c for notes on these names.
 354       _Sequence  c;
 355       _Compare   comp;
 356
 357     public:
 358       /**
 359        *  @brief  Default constructor creates no elements.
 360        */
 361       explicit
 362       priority_queue(const _Compare& __x = _Compare(),
 363                      const _Sequence& __s = _Sequence())
 364       : c(__s), comp(__x)
 365       { std::make_heap(c.begin(), c.end(), comp); }
 366
 367       /**
 368        *  @brief  Builds a %queue from a range.
 369        *  @param  first  An input iterator.
 370        *  @param  last  An input iterator.
 371        *  @param  x  A comparison functor describing a strict weak ordering.
 372        *  @param  s  An initial sequence with which to start.
 373        *
 374        *  Begins by copying @a s, inserting a copy of the elements
 375        *  from @a [first,last) into the copy of @a s, then ordering
 376        *  the copy according to @a x.
 377        *
 378        *  For more information on function objects, see the
 379        *  documentation on @link s20_3_1_base functor base
 380        *  classes@endlink.
 381        */
 382       template<typename _InputIterator>
 383         priority_queue(_InputIterator __first, _InputIterator __last,
 384                        const _Compare& __x = _Compare(),
 385                        const _Sequence& __s = _Sequence())
 386         : c(__s), comp(__x)
 387         {
 388           __glibcxx_requires_valid_range(__first, __last);
 389           c.insert(c.end(), __first, __last);
 390           std::make_heap(c.begin(), c.end(), comp);
 391         }
 392
 393       /**
 394        *  Returns true if the %queue is empty.
 395        */
 396       bool
 397       empty() const
 398       { return c.empty(); }
 399
 400       /**  Returns the number of elements in the %queue.  */
 401       size_type
 402       size() const
 403       { return c.size(); }
 404
 405       /**
 406        *  Returns a read-only (constant) reference to the data at the first
 407        *  element of the %queue.
 408        */
 409       const_reference
 410       top() const
 411       {
 412         __glibcxx_requires_nonempty();
 413         return c.front();
 414       }
 415
 416       /**
 417        *  @brief  Add data to the %queue.
 418        *  @param  x  Data to be added.
 419        *
 420        *  This is a typical %queue operation.
 421        *  The time complexity of the operation depends on the underlying
 422        *  sequence.
 423        */
 424       void
 425       push(const value_type& __x)
 426       {
 427         c.push_back(__x);
 428         std::push_heap(c.begin(), c.end(), comp);
 429       }
 430
 431       /**
 432        *  @brief  Removes first element.
 433        *
 434        *  This is a typical %queue operation.  It shrinks the %queue
 435        *  by one.  The time complexity of the operation depends on the
 436        *  underlying sequence.
 437        *
 438        *  Note that no data is returned, and if the first element's
 439        *  data is needed, it should be retrieved before pop() is
 440        *  called.
 441        */
 442       void
 443       pop()
 444       {
 445         __glibcxx_requires_nonempty();
 446         std::pop_heap(c.begin(), c.end(), comp);
 447         c.pop_back();
 448       }
 449     };
 450
 451   // No equality/comparison operators are provided for priority_queue.
 452
 453 _GLIBCXX_END_NAMESPACE
 454
 455 #endif /* _QUEUE_H */