contrib/gcc-4.1/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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  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 priority-based sorting
 308    *  and %queue behavior.  Very few of the standard container/sequence
 309    *  interface requirements are met (e.g., iterators).
 310    *
 311    *  The second template parameter defines the type of the underlying
 312    *  sequence/container.  It defaults to std::vector, but it can be
 313    *  any type that supports @c front(), @c push_back, @c pop_back,
 314    *  and random-access iterators, such as std::deque or an
 315    *  appropriate user-defined type.
 316    *
 317    *  The third template parameter supplies the means of making
 318    *  priority comparisons.  It defaults to @c less<value_type> but
 319    *  can be anything defining a strict weak ordering.
 320    *
 321    *  Members not found in "normal" containers are @c container_type,
 322    *  which is a typedef for the second Sequence parameter, and @c
 323    *  push, @c pop, and @c top, which are standard %queue operations.
 324    *
 325    *  @note No equality/comparison operators are provided for
 326    *  %priority_queue.
 327    *
 328    *  @note Sorting of the elements takes place as they are added to,
 329    *  and removed from, the %priority_queue using the
 330    *  %priority_queue's member functions.  If you access the elements
 331    *  by other means, and change their data such that the sorting
 332    *  order would be different, the %priority_queue will not re-sort
 333    *  the elements for you.  (How could it know to do so?)
 334   */
 335   template<typename _Tp, typename _Sequence = vector<_Tp>,
 336            typename _Compare  = less<typename _Sequence::value_type> >
 337     class priority_queue
 338     {
 339       // concept requirements
 340       typedef typename _Sequence::value_type _Sequence_value_type;
 341       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
 342       __glibcxx_class_requires(_Sequence, _SequenceConcept)
 343       __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept)
 344       __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
 345       __glibcxx_class_requires4(_Compare, bool, _Tp,_Tp,_BinaryFunctionConcept)
 346
 347     public:
 348       typedef typename _Sequence::value_type                value_type;
 349       typedef typename _Sequence::reference                 reference;
 350       typedef typename _Sequence::const_reference           const_reference;
 351       typedef typename _Sequence::size_type                 size_type;
 352       typedef          _Sequence                            container_type;
 353
 354     protected:
 355       //  See queue::c for notes on these names.
 356       _Sequence  c;
 357       _Compare   comp;
 358
 359     public:
 360       /**
 361        *  @brief  Default constructor creates no elements.
 362        */
 363       explicit
 364       priority_queue(const _Compare& __x = _Compare(),
 365                      const _Sequence& __s = _Sequence())
 366       : c(__s), comp(__x)
 367       { std::make_heap(c.begin(), c.end(), comp); }
 368
 369       /**
 370        *  @brief  Builds a %queue from a range.
 371        *  @param  first  An input iterator.
 372        *  @param  last  An input iterator.
 373        *  @param  x  A comparison functor describing a strict weak ordering.
 374        *  @param  s  An initial sequence with which to start.
 375        *
 376        *  Begins by copying @a s, inserting a copy of the elements
 377        *  from @a [first,last) into the copy of @a s, then ordering
 378        *  the copy according to @a x.
 379        *
 380        *  For more information on function objects, see the
 381        *  documentation on @link s20_3_1_base functor base
 382        *  classes@endlink.
 383        */
 384       template<typename _InputIterator>
 385         priority_queue(_InputIterator __first, _InputIterator __last,
 386                        const _Compare& __x = _Compare(),
 387                        const _Sequence& __s = _Sequence())
 388         : c(__s), comp(__x)
 389         {
 390           __glibcxx_requires_valid_range(__first, __last);
 391           c.insert(c.end(), __first, __last);
 392           std::make_heap(c.begin(), c.end(), comp);
 393         }
 394
 395       /**
 396        *  Returns true if the %queue is empty.
 397        */
 398       bool
 399       empty() const { return c.empty(); }
 400
 401       /**  Returns the number of elements in the %queue.  */
 402       size_type
 403       size() const { 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         try
 428         {
 429           c.push_back(__x);
 430           std::push_heap(c.begin(), c.end(), comp);
 431         }
 432         catch(...)
 433         {
 434           c.clear();
 435           __throw_exception_again;
 436         }
 437       }
 438
 439       /**
 440        *  @brief  Removes first element.
 441        *
 442        *  This is a typical %queue operation.  It shrinks the %queue
 443        *  by one.  The time complexity of the operation depends on the
 444        *  underlying sequence.
 445        *
 446        *  Note that no data is returned, and if the first element's
 447        *  data is needed, it should be retrieved before pop() is
 448        *  called.
 449        */
 450       void
 451       pop()
 452       {
 453         __glibcxx_requires_nonempty();
 454         try
 455         {
 456           std::pop_heap(c.begin(), c.end(), comp);
 457           c.pop_back();
 458         }
 459         catch(...)
 460         {
 461           c.clear();
 462           __throw_exception_again;
 463         }
 464       }
 465     };
 466
 467   // No equality/comparison operators are provided for priority_queue.
 468 } // namespace std
 469
 470 #endif /* _QUEUE_H */