contrib/libstdc++/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   /**
  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       explicit
 135       queue(const _Sequence& __c = _Sequence()) : c(__c) {}
 136
 137       /**
 138        *  Returns true if the %queue is empty.
 139        */
 140       bool
 141       empty() const
 142       { return c.empty(); }
 143
 144       /**  Returns the number of elements in the %queue.  */
 145       size_type
 146       size() const
 147       { return c.size(); }
 148
 149       /**
 150        *  Returns a read/write reference to the data at the first
 151        *  element of the %queue.
 152        */
 153       reference
 154       front()
 155       {
 156         __glibcxx_requires_nonempty();
 157         return c.front();
 158       }
 159
 160       /**
 161        *  Returns a read-only (constant) reference to the data at the first
 162        *  element of the %queue.
 163        */
 164       const_reference
 165       front() const
 166       {
 167         __glibcxx_requires_nonempty();
 168         return c.front();
 169       }
 170
 171       /**
 172        *  Returns a read/write reference to the data at the last
 173        *  element of the %queue.
 174        */
 175       reference
 176       back()
 177       {
 178         __glibcxx_requires_nonempty();
 179         return c.back();
 180       }
 181
 182       /**
 183        *  Returns a read-only (constant) reference to the data at the last
 184        *  element of the %queue.
 185        */
 186       const_reference
 187       back() const
 188       {
 189         __glibcxx_requires_nonempty();
 190         return c.back();
 191       }
 192
 193       /**
 194        *  @brief  Add data to the end of the %queue.
 195        *  @param  x  Data to be added.
 196        *
 197        *  This is a typical %queue operation.  The function creates an
 198        *  element at the end of the %queue and assigns the given data
 199        *  to it.  The time complexity of the operation depends on the
 200        *  underlying sequence.
 201        */
 202       void
 203       push(const value_type& __x)
 204       { c.push_back(__x); }
 205
 206       /**
 207        *  @brief  Removes first element.
 208        *
 209        *  This is a typical %queue operation.  It shrinks the %queue by one.
 210        *  The time complexity of the operation depends on the underlying
 211        *  sequence.
 212        *
 213        *  Note that no data is returned, and if the first element's
 214        *  data is needed, it should be retrieved before pop() is
 215        *  called.
 216        */
 217       void
 218       pop()
 219       {
 220         __glibcxx_requires_nonempty();
 221         c.pop_front();
 222       }
 223     };
 224
 225
 226   /**
 227    *  @brief  Queue equality comparison.
 228    *  @param  x  A %queue.
 229    *  @param  y  A %queue of the same type as @a x.
 230    *  @return  True iff the size and elements of the queues are equal.
 231    *
 232    *  This is an equivalence relation.  Complexity and semantics depend on the
 233    *  underlying sequence type, but the expected rules are:  this relation is
 234    *  linear in the size of the sequences, and queues are considered equivalent
 235    *  if their sequences compare equal.
 236   */
 237   template<typename _Tp, typename _Seq>
 238     inline bool
 239     operator==(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
 240     { return __x.c == __y.c; }
 241
 242   /**
 243    *  @brief  Queue ordering relation.
 244    *  @param  x  A %queue.
 245    *  @param  y  A %queue of the same type as @a x.
 246    *  @return  True iff @a x is lexicographically less than @a y.
 247    *
 248    *  This is an total ordering relation.  Complexity and semantics
 249    *  depend on the underlying sequence type, but the expected rules
 250    *  are: this relation is linear in the size of the sequences, the
 251    *  elements must be comparable with @c <, and
 252    *  std::lexicographical_compare() is usually used to make the
 253    *  determination.
 254   */
 255   template<typename _Tp, typename _Seq>
 256     inline bool
 257     operator<(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
 258     { return __x.c < __y.c; }
 259
 260   /// Based on operator==
 261   template<typename _Tp, typename _Seq>
 262     inline bool
 263     operator!=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
 264     { return !(__x == __y); }
 265
 266   /// Based on operator<
 267   template<typename _Tp, typename _Seq>
 268     inline bool
 269     operator>(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
 270     { return __y < __x; }
 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 !(__y < __x); }
 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 !(__x < __y); }
 283
 284   /**
 285    *  @brief  A standard container automatically sorting its contents.
 286    *
 287    *  @ingroup Containers
 288    *  @ingroup Sequences
 289    *
 290    *  This is not a true container, but an @e adaptor.  It holds
 291    *  another container, and provides a wrapper interface to that
 292    *  container.  The wrapper is what enforces priority-based sorting
 293    *  and %queue behavior.  Very few of the standard container/sequence
 294    *  interface requirements are met (e.g., iterators).
 295    *
 296    *  The second template parameter defines the type of the underlying
 297    *  sequence/container.  It defaults to std::vector, but it can be
 298    *  any type that supports @c front(), @c push_back, @c pop_back,
 299    *  and random-access iterators, such as std::deque or an
 300    *  appropriate user-defined type.
 301    *
 302    *  The third template parameter supplies the means of making
 303    *  priority comparisons.  It defaults to @c less<value_type> but
 304    *  can be anything defining a strict weak ordering.
 305    *
 306    *  Members not found in "normal" containers are @c container_type,
 307    *  which is a typedef for the second Sequence parameter, and @c
 308    *  push, @c pop, and @c top, which are standard %queue operations.
 309    *
 310    *  @note No equality/comparison operators are provided for
 311    *  %priority_queue.
 312    *
 313    *  @note Sorting of the elements takes place as they are added to,
 314    *  and removed from, the %priority_queue using the
 315    *  %priority_queue's member functions.  If you access the elements
 316    *  by other means, and change their data such that the sorting
 317    *  order would be different, the %priority_queue will not re-sort
 318    *  the elements for you.  (How could it know to do so?)
 319   */
 320   template<typename _Tp, typename _Sequence = vector<_Tp>,
 321            typename _Compare  = less<typename _Sequence::value_type> >
 322     class priority_queue
 323     {
 324       // concept requirements
 325       typedef typename _Sequence::value_type _Sequence_value_type;
 326       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
 327       __glibcxx_class_requires(_Sequence, _SequenceConcept)
 328       __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept)
 329       __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
 330       __glibcxx_class_requires4(_Compare, bool, _Tp, _Tp,
 331                                 _BinaryFunctionConcept)
 332
 333     public:
 334       typedef typename _Sequence::value_type                value_type;
 335       typedef typename _Sequence::reference                 reference;
 336       typedef typename _Sequence::const_reference           const_reference;
 337       typedef typename _Sequence::size_type                 size_type;
 338       typedef          _Sequence                            container_type;
 339
 340     protected:
 341       //  See queue::c for notes on these names.
 342       _Sequence  c;
 343       _Compare   comp;
 344
 345     public:
 346       /**
 347        *  @brief  Default constructor creates no elements.
 348        */
 349       explicit
 350       priority_queue(const _Compare& __x = _Compare(),
 351                      const _Sequence& __s = _Sequence())
 352       : c(__s), comp(__x)
 353       { std::make_heap(c.begin(), c.end(), comp); }
 354
 355       /**
 356        *  @brief  Builds a %queue from a range.
 357        *  @param  first  An input iterator.
 358        *  @param  last  An input iterator.
 359        *  @param  x  A comparison functor describing a strict weak ordering.
 360        *  @param  s  An initial sequence with which to start.
 361        *
 362        *  Begins by copying @a s, inserting a copy of the elements
 363        *  from @a [first,last) into the copy of @a s, then ordering
 364        *  the copy according to @a x.
 365        *
 366        *  For more information on function objects, see the
 367        *  documentation on @link s20_3_1_base functor base
 368        *  classes@endlink.
 369        */
 370       template<typename _InputIterator>
 371         priority_queue(_InputIterator __first, _InputIterator __last,
 372                        const _Compare& __x = _Compare(),
 373                        const _Sequence& __s = _Sequence())
 374         : c(__s), comp(__x)
 375         {
 376           __glibcxx_requires_valid_range(__first, __last);
 377           c.insert(c.end(), __first, __last);
 378           std::make_heap(c.begin(), c.end(), comp);
 379         }
 380
 381       /**
 382        *  Returns true if the %queue is empty.
 383        */
 384       bool
 385       empty() const
 386       { return c.empty(); }
 387
 388       /**  Returns the number of elements in the %queue.  */
 389       size_type
 390       size() const
 391       { return c.size(); }
 392
 393       /**
 394        *  Returns a read-only (constant) reference to the data at the first
 395        *  element of the %queue.
 396        */
 397       const_reference
 398       top() const
 399       {
 400         __glibcxx_requires_nonempty();
 401         return c.front();
 402       }
 403
 404       /**
 405        *  @brief  Add data to the %queue.
 406        *  @param  x  Data to be added.
 407        *
 408        *  This is a typical %queue operation.
 409        *  The time complexity of the operation depends on the underlying
 410        *  sequence.
 411        */
 412       void
 413       push(const value_type& __x)
 414       {
 415         c.push_back(__x);
 416         std::push_heap(c.begin(), c.end(), comp);
 417       }
 418
 419       /**
 420        *  @brief  Removes first element.
 421        *
 422        *  This is a typical %queue operation.  It shrinks the %queue
 423        *  by one.  The time complexity of the operation depends on the
 424        *  underlying sequence.
 425        *
 426        *  Note that no data is returned, and if the first element's
 427        *  data is needed, it should be retrieved before pop() is
 428        *  called.
 429        */
 430       void
 431       pop()
 432       {
 433         __glibcxx_requires_nonempty();
 434         std::pop_heap(c.begin(), c.end(), comp);
 435         c.pop_back();
 436       }
 437     };
 438
 439   // No equality/comparison operators are provided for priority_queue.
 440
 441 _GLIBCXX_END_NAMESPACE
 442
 443 #endif /* _QUEUE_H */