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

   1 // Queue implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004 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 2, 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 // You should have received a copy of the GNU General Public License along
  17 // with this library; see the file COPYING.  If not, write to the Free
  18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  19 // USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 /*
  31  *
  32  * Copyright (c) 1994
  33  * Hewlett-Packard Company
  34  *
  35  * Permission to use, copy, modify, distribute and sell this software
  36  * and its documentation for any purpose is hereby granted without fee,
  37  * provided that the above copyright notice appear in all copies and
  38  * that both that copyright notice and this permission notice appear
  39  * in supporting documentation.  Hewlett-Packard Company makes no
  40  * representations about the suitability of this software for any
  41  * purpose.  It is provided "as is" without express or implied warranty.
  42  *
  43  *
  44  * Copyright (c) 1996,1997
  45  * Silicon Graphics Computer Systems, Inc.
  46  *
  47  * Permission to use, copy, modify, distribute and sell this software
  48  * and its documentation for any purpose is hereby granted without fee,
  49  * provided that the above copyright notice appear in all copies and
  50  * that both that copyright notice and this permission notice appear
  51  * in supporting documentation.  Silicon Graphics makes no
  52  * representations about the suitability of this software for any
  53  * purpose.  It is provided "as is" without express or implied warranty.
  54  */
  55
  56 /** @file stl_queue.h
  57  *  This is an internal header file, included by other library headers.
  58  *  You should not attempt to use it directly.
  59  */
  60
  61 #ifndef _QUEUE_H
  62 #define _QUEUE_H 1
  63
  64 #include <bits/concept_check.h>
  65 #include <debug/debug.h>
  66
  67 namespace std
  68 {
  69   // Forward declarations of operators < and ==, needed for friend declaration.
  70   template<typename _Tp, typename _Sequence = deque<_Tp> >
  71     class queue;
  72
  73   template<typename _Tp, typename _Seq>
  74     inline bool
  75     operator==(const queue<_Tp,_Seq>&, const queue<_Tp,_Seq>&);
  76
  77   template<typename _Tp, typename _Seq>
  78     inline bool
  79     operator<(const queue<_Tp,_Seq>&, const queue<_Tp,_Seq>&);
  80
  81   /**
  82    *  @brief  A standard container giving FIFO behavior.
  83    *
  84    *  @ingroup Containers
  85    *  @ingroup Sequences
  86    *
  87    *  Meets many of the requirements of a
  88    *  <a href="tables.html#65">container</a>,
  89    *  but does not define anything to do with iterators.  Very few of the
  90    *  other standard container interfaces are defined.
  91    *
  92    *  This is not a true container, but an @e adaptor.  It holds another
  93    *  container, and provides a wrapper interface to that container.  The
  94    *  wrapper is what enforces strict first-in-first-out %queue behavior.
  95    *
  96    *  The second template parameter defines the type of the underlying
  97    *  sequence/container.  It defaults to std::deque, but it can be any type
  98    *  that supports @c front, @c back, @c push_back, and @c pop_front,
  99    *  such as std::list or an appropriate user-defined type.
 100    *
 101    *  Members not found in "normal" containers are @c container_type,
 102    *  which is a typedef for the second Sequence parameter, and @c push and
 103    *  @c pop, which are standard %queue/FIFO operations.
 104   */
 105   template<typename _Tp, typename _Sequence>
 106     class queue
 107     {
 108       // concept requirements
 109       typedef typename _Sequence::value_type _Sequence_value_type;
 110       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
 111       __glibcxx_class_requires(_Sequence, _FrontInsertionSequenceConcept)
 112       __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept)
 113       __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
 114
 115       template<typename _Tp1, typename _Seq1>
 116         friend bool
 117         operator==(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
 118
 119       template<typename _Tp1, typename _Seq1>
 120         friend bool
 121         operator<(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
 122
 123     public:
 124       typedef typename _Sequence::value_type                value_type;
 125       typedef typename _Sequence::reference                 reference;
 126       typedef typename _Sequence::const_reference           const_reference;
 127       typedef typename _Sequence::size_type                 size_type;
 128       typedef          _Sequence                            container_type;
 129
 130     protected:
 131       /**
 132        *  'c' is the underlying container.  Maintainers wondering why
 133        *  this isn't uglified as per style guidelines should note that
 134        *  this name is specified in the standard, [23.2.3.1].  (Why?
 135        *  Presumably for the same reason that it's protected instead
 136        *  of private: to allow derivation.  But none of the other
 137        *  containers allow for derivation.  Odd.)
 138        */
 139       _Sequence c;
 140
 141     public:
 142       /**
 143        *  @brief  Default constructor creates no elements.
 144        */
 145       explicit
 146       queue(const _Sequence& __c = _Sequence()) : c(__c) {}
 147
 148       /**
 149        *  Returns true if the %queue is empty.
 150        */
 151       bool
 152       empty() const
 153       { return c.empty(); }
 154
 155       /**  Returns the number of elements in the %queue.  */
 156       size_type
 157       size() const
 158       { return c.size(); }
 159
 160       /**
 161        *  Returns a read/write reference to the data at the first
 162        *  element of the %queue.
 163        */
 164       reference
 165       front()
 166       {
 167         __glibcxx_requires_nonempty();
 168         return c.front();
 169       }
 170
 171       /**
 172        *  Returns a read-only (constant) reference to the data at the first
 173        *  element of the %queue.
 174        */
 175       const_reference
 176       front() const
 177       {
 178         __glibcxx_requires_nonempty();
 179         return c.front();
 180       }
 181
 182       /**
 183        *  Returns a read/write reference to the data at the last
 184        *  element of the %queue.
 185        */
 186       reference
 187       back()
 188       {
 189         __glibcxx_requires_nonempty();
 190         return c.back();
 191       }
 192
 193       /**
 194        *  Returns a read-only (constant) reference to the data at the last
 195        *  element of the %queue.
 196        */
 197       const_reference
 198       back() const
 199       {
 200         __glibcxx_requires_nonempty();
 201         return c.back();
 202       }
 203
 204       /**
 205        *  @brief  Add data to the end of the %queue.
 206        *  @param  x  Data to be added.
 207        *
 208        *  This is a typical %queue operation.  The function creates an
 209        *  element at the end of the %queue and assigns the given data
 210        *  to it.  The time complexity of the operation depends on the
 211        *  underlying sequence.
 212        */
 213       void
 214       push(const value_type& __x)
 215       { c.push_back(__x); }
 216
 217       /**
 218        *  @brief  Removes first element.
 219        *
 220        *  This is a typical %queue operation.  It shrinks the %queue by one.
 221        *  The time complexity of the operation depends on the underlying
 222        *  sequence.
 223        *
 224        *  Note that no data is returned, and if the first element's
 225        *  data is needed, it should be retrieved before pop() is
 226        *  called.
 227        */
 228       void
 229       pop()
 230       {
 231         __glibcxx_requires_nonempty();
 232         c.pop_front();
 233       }
 234     };
 235
 236
 237   /**
 238    *  @brief  Queue equality comparison.
 239    *  @param  x  A %queue.
 240    *  @param  y  A %queue of the same type as @a x.
 241    *  @return  True iff the size and elements of the queues are equal.
 242    *
 243    *  This is an equivalence relation.  Complexity and semantics depend on the
 244    *  underlying sequence type, but the expected rules are:  this relation is
 245    *  linear in the size of the sequences, and queues are considered equivalent
 246    *  if their sequences compare equal.
 247   */
 248   template<typename _Tp, typename _Sequence>
 249     inline bool
 250     operator==(const queue<_Tp,_Sequence>& __x,
 251                const queue<_Tp,_Sequence>& __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 _Sequence>
 268     inline bool
 269     operator<(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y)
 270     { return __x.c < __y.c; }
 271
 272   /// Based on operator==
 273   template<typename _Tp, typename _Sequence>
 274     inline bool
 275     operator!=(const queue<_Tp,_Sequence>& __x,
 276                const queue<_Tp,_Sequence>& __y)
 277     { return !(__x == __y); }
 278
 279   /// Based on operator<
 280   template<typename _Tp, typename _Sequence>
 281     inline bool
 282     operator>(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y)
 283     { return __y < __x; }
 284
 285   /// Based on operator<
 286   template<typename _Tp, typename _Sequence>
 287     inline bool
 288     operator<=(const queue<_Tp,_Sequence>& __x,
 289                const queue<_Tp,_Sequence>& __y)
 290     { return !(__y < __x); }
 291
 292   /// Based on operator<
 293   template<typename _Tp, typename _Sequence>
 294     inline bool
 295     operator>=(const queue<_Tp,_Sequence>& __x,
 296                const queue<_Tp,_Sequence>& __y)
 297     { return !(__x < __y); }
 298
 299   /**
 300    *  @brief  A standard container automatically sorting its contents.
 301    *
 302    *  @ingroup Containers
 303    *  @ingroup Sequences
 304    *
 305    *  This is not a true container, but an @e adaptor.  It holds
 306    *  another container, and provides a wrapper interface to that
 307    *  container.  The wrapper is what enforces sorting and
 308    *  first-in-first-out %queue behavior.  Very few of the standard
 309    *  container/sequence interface requirements are met (e.g.,
 310    *  iterators).
 311    *
 312    *  The second template parameter defines the type of the underlying
 313    *  sequence/container.  It defaults to std::vector, but it can be
 314    *  any type that supports @c front(), @c push_back, @c pop_back,
 315    *  and random-access iterators, such as std::deque or an
 316    *  appropriate user-defined type.
 317    *
 318    *  The third template parameter supplies the means of making
 319    *  priority comparisons.  It defaults to @c less<value_type> but
 320    *  can be anything defining a strict weak ordering.
 321    *
 322    *  Members not found in "normal" containers are @c container_type,
 323    *  which is a typedef for the second Sequence parameter, and @c
 324    *  push, @c pop, and @c top, which are standard %queue/FIFO
 325    *  operations.
 326    *
 327    *  @note No equality/comparison operators are provided for
 328    *  %priority_queue.
 329    *
 330    *  @note Sorting of the elements takes place as they are added to,
 331    *  and removed from, the %priority_queue using the
 332    *  %priority_queue's member functions.  If you access the elements
 333    *  by other means, and change their data such that the sorting
 334    *  order would be different, the %priority_queue will not re-sort
 335    *  the elements for you.  (How could it know to do so?)
 336   */
 337   template<typename _Tp, typename _Sequence = vector<_Tp>,
 338            typename _Compare  = less<typename _Sequence::value_type> >
 339     class priority_queue
 340     {
 341       // concept requirements
 342       typedef typename _Sequence::value_type _Sequence_value_type;
 343       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
 344       __glibcxx_class_requires(_Sequence, _SequenceConcept)
 345       __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept)
 346       __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
 347       __glibcxx_class_requires4(_Compare, bool, _Tp,_Tp,_BinaryFunctionConcept)
 348
 349     public:
 350       typedef typename _Sequence::value_type                value_type;
 351       typedef typename _Sequence::reference                 reference;
 352       typedef typename _Sequence::const_reference           const_reference;
 353       typedef typename _Sequence::size_type                 size_type;
 354       typedef          _Sequence                            container_type;
 355
 356     protected:
 357       //  See queue::c for notes on these names.
 358       _Sequence  c;
 359       _Compare   comp;
 360
 361     public:
 362       /**
 363        *  @brief  Default constructor creates no elements.
 364        */
 365       explicit
 366       priority_queue(const _Compare& __x = _Compare(),
 367                      const _Sequence& __s = _Sequence())
 368       : c(__s), comp(__x)
 369       { std::make_heap(c.begin(), c.end(), comp); }
 370
 371       /**
 372        *  @brief  Builds a %queue from a range.
 373        *  @param  first  An input iterator.
 374        *  @param  last  An input iterator.
 375        *  @param  x  A comparison functor describing a strict weak ordering.
 376        *  @param  s  An initial sequence with which to start.
 377        *
 378        *  Begins by copying @a s, inserting a copy of the elements
 379        *  from @a [first,last) into the copy of @a s, then ordering
 380        *  the copy according to @a x.
 381        *
 382        *  For more information on function objects, see the
 383        *  documentation on @link s20_3_1_base functor base
 384        *  classes@endlink.
 385        */
 386       template<typename _InputIterator>
 387         priority_queue(_InputIterator __first, _InputIterator __last,
 388                        const _Compare& __x = _Compare(),
 389                        const _Sequence& __s = _Sequence())
 390         : c(__s), comp(__x)
 391         {
 392           __glibcxx_requires_valid_range(__first, __last);
 393           c.insert(c.end(), __first, __last);
 394           std::make_heap(c.begin(), c.end(), comp);
 395         }
 396
 397       /**
 398        *  Returns true if the %queue is empty.
 399        */
 400       bool
 401       empty() const { return c.empty(); }
 402
 403       /**  Returns the number of elements in the %queue.  */
 404       size_type
 405       size() const { return c.size(); }
 406
 407       /**
 408        *  Returns a read-only (constant) reference to the data at the first
 409        *  element of the %queue.
 410        */
 411       const_reference
 412       top() const
 413       {
 414         __glibcxx_requires_nonempty();
 415         return c.front();
 416       }
 417
 418       /**
 419        *  @brief  Add data to the %queue.
 420        *  @param  x  Data to be added.
 421        *
 422        *  This is a typical %queue operation.
 423        *  The time complexity of the operation depends on the underlying
 424        *  sequence.
 425        */
 426       void
 427       push(const value_type& __x)
 428       {
 429         try
 430         {
 431           c.push_back(__x);
 432           std::push_heap(c.begin(), c.end(), comp);
 433         }
 434         catch(...)
 435         {
 436           c.clear();
 437           __throw_exception_again;
 438         }
 439       }
 440
 441       /**
 442        *  @brief  Removes first element.
 443        *
 444        *  This is a typical %queue operation.  It shrinks the %queue
 445        *  by one.  The time complexity of the operation depends on the
 446        *  underlying sequence.
 447        *
 448        *  Note that no data is returned, and if the first element's
 449        *  data is needed, it should be retrieved before pop() is
 450        *  called.
 451        */
 452       void
 453       pop()
 454       {
 455         __glibcxx_requires_nonempty();
 456         try
 457         {
 458           std::pop_heap(c.begin(), c.end(), comp);
 459           c.pop_back();
 460         }
 461         catch(...)
 462         {
 463           c.clear();
 464           __throw_exception_again;
 465         }
 466       }
 467     };
 468
 469   // No equality/comparison operators are provided for priority_queue.
 470 } // namespace std
 471
 472 #endif /* _QUEUE_H */