home *** CD-ROM | disk | FTP | other *** search
/ Beginning C++ Through Gam…rogramming (2nd Edition) / BCGP2E.ISO / bloodshed / devcpp-4.9.9.2_setup.exe / stl_queue.h < prev    next >
C/C++ Source or Header  |  2005-01-29  |  16KB  |  473 lines
  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 */
  473.