stl_queue.h

Go to the documentation of this file.
00001 // Queue implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 2, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // You should have received a copy of the GNU General Public License along
00017 // with this library; see the file COPYING.  If not, write to the Free
00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
00019 // USA.
00020 
00021 // As a special exception, you may use this file as part of a free software
00022 // library without restriction.  Specifically, if other files instantiate
00023 // templates or use macros or inline functions from this file, or you compile
00024 // this file and link it with other files to produce an executable, this
00025 // file does not by itself cause the resulting executable to be covered by
00026 // the GNU General Public License.  This exception does not however
00027 // invalidate any other reasons why the executable file might be covered by
00028 // the GNU General Public License.
00029 
00030 /*
00031  *
00032  * Copyright (c) 1994
00033  * Hewlett-Packard Company
00034  *
00035  * Permission to use, copy, modify, distribute and sell this software
00036  * and its documentation for any purpose is hereby granted without fee,
00037  * provided that the above copyright notice appear in all copies and
00038  * that both that copyright notice and this permission notice appear
00039  * in supporting documentation.  Hewlett-Packard Company makes no
00040  * representations about the suitability of this software for any
00041  * purpose.  It is provided "as is" without express or implied warranty.
00042  *
00043  *
00044  * Copyright (c) 1996,1997
00045  * Silicon Graphics Computer Systems, Inc.
00046  *
00047  * Permission to use, copy, modify, distribute and sell this software
00048  * and its documentation for any purpose is hereby granted without fee,
00049  * provided that the above copyright notice appear in all copies and
00050  * that both that copyright notice and this permission notice appear
00051  * in supporting documentation.  Silicon Graphics makes no
00052  * representations about the suitability of this software for any
00053  * purpose.  It is provided "as is" without express or implied warranty.
00054  */
00055 
00061 #ifndef __GLIBCPP_INTERNAL_QUEUE_H
00062 #define __GLIBCPP_INTERNAL_QUEUE_H
00063 
00064 #include <bits/concept_check.h>
00065 
00066 namespace std
00067 {
00068 
00069 // Forward declarations of operators < and ==, needed for friend declaration.
00070 
00071 template <class _Tp, 
00072           class _Sequence = deque<_Tp> >
00073 class queue;
00074 
00075 template <class _Tp, class _Seq>
00076 inline bool operator==(const queue<_Tp, _Seq>&, const queue<_Tp, _Seq>&);
00077 
00078 template <class _Tp, class _Seq>
00079 inline bool operator<(const queue<_Tp, _Seq>&, const queue<_Tp, _Seq>&);
00080 
00081 
00082 template <class _Tp, class _Sequence>
00083 class queue
00084 {
00085   // concept requirements
00086   __glibcpp_class_requires(_Tp, _SGIAssignableConcept)
00087   __glibcpp_class_requires(_Sequence, _FrontInsertionSequenceConcept)
00088   __glibcpp_class_requires(_Sequence, _BackInsertionSequenceConcept)
00089   typedef typename _Sequence::value_type _Sequence_value_type;
00090   __glibcpp_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept);
00091 
00092   template <class _Tp1, class _Seq1>
00093   friend bool operator== (const queue<_Tp1, _Seq1>&,
00094                           const queue<_Tp1, _Seq1>&);
00095   template <class _Tp1, class _Seq1>
00096   friend bool operator< (const queue<_Tp1, _Seq1>&,
00097                          const queue<_Tp1, _Seq1>&);
00098 public:
00099   typedef typename _Sequence::value_type      value_type;
00100   typedef typename _Sequence::size_type       size_type;
00101   typedef          _Sequence                  container_type;
00102 
00103   typedef typename _Sequence::reference       reference;
00104   typedef typename _Sequence::const_reference const_reference;
00105 protected:
00106   _Sequence c;
00107 public:
00108   explicit queue(const _Sequence& __c = _Sequence()) : c(__c) {}
00109 
00110   bool empty() const { return c.empty(); }
00111   size_type size() const { return c.size(); }
00112   reference front() { return c.front(); }
00113   const_reference front() const { return c.front(); }
00114   reference back() { return c.back(); }
00115   const_reference back() const { return c.back(); }
00116   void push(const value_type& __x) { c.push_back(__x); }
00117   void pop() { c.pop_front(); }
00118 };
00119 
00120 template <class _Tp, class _Sequence>
00121 bool 
00122 operator==(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
00123 {
00124   return __x.c == __y.c;
00125 }
00126 
00127 template <class _Tp, class _Sequence>
00128 bool
00129 operator<(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
00130 {
00131   return __x.c < __y.c;
00132 }
00133 
00134 template <class _Tp, class _Sequence>
00135 bool
00136 operator!=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
00137 {
00138   return !(__x == __y);
00139 }
00140 
00141 template <class _Tp, class _Sequence>
00142 bool 
00143 operator>(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
00144 {
00145   return __y < __x;
00146 }
00147 
00148 template <class _Tp, class _Sequence>
00149 bool 
00150 operator<=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
00151 {
00152   return !(__y < __x);
00153 }
00154 
00155 template <class _Tp, class _Sequence>
00156 bool 
00157 operator>=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
00158 {
00159   return !(__x < __y);
00160 }
00161 
00162 template <class _Tp, 
00163           class _Sequence = vector<_Tp>,
00164           class _Compare  = less<typename _Sequence::value_type> >
00165 class priority_queue
00166 {
00167   // concept requirements
00168   __glibcpp_class_requires(_Tp, _SGIAssignableConcept)
00169   __glibcpp_class_requires(_Sequence, _SequenceConcept)
00170   __glibcpp_class_requires(_Sequence, _RandomAccessContainerConcept)
00171   typedef typename _Sequence::value_type _Sequence_value_type;
00172   __glibcpp_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept);
00173   __glibcpp_class_requires4(_Compare, bool, _Tp, _Tp, _BinaryFunctionConcept);
00174 
00175 public:
00176   typedef typename _Sequence::value_type      value_type;
00177   typedef typename _Sequence::size_type       size_type;
00178   typedef          _Sequence                  container_type;
00179 
00180   typedef typename _Sequence::reference       reference;
00181   typedef typename _Sequence::const_reference const_reference;
00182 protected:
00183   _Sequence c;
00184   _Compare comp;
00185 public:
00186   explicit priority_queue(const _Compare& __x = _Compare(),
00187               const _Sequence& __s = _Sequence()) 
00188     : c(__s), comp(__x) 
00189     { make_heap(c.begin(), c.end(), comp); }
00190 
00191   template <class _InputIterator>
00192   priority_queue(_InputIterator __first, _InputIterator __last,
00193                  const _Compare& __x = _Compare(),
00194          const _Sequence& __s = _Sequence())
00195   : c(__s), comp(__x)
00196   { 
00197     c.insert(c.end(), __first, __last);
00198     make_heap(c.begin(), c.end(), comp);
00199   }
00200 
00201   bool empty() const { return c.empty(); }
00202   size_type size() const { return c.size(); }
00203   const_reference top() const { return c.front(); }
00204 
00205   void 
00206   push(const value_type& __x) 
00207   {
00208     try 
00209       {
00210     c.push_back(__x); 
00211     push_heap(c.begin(), c.end(), comp);
00212       }
00213     catch(...)
00214       {
00215     c.clear();
00216     __throw_exception_again; 
00217       }
00218   }
00219 
00220   void 
00221   pop() 
00222   {
00223     try 
00224       {
00225     pop_heap(c.begin(), c.end(), comp);
00226     c.pop_back();
00227       }
00228     catch(...)
00229       {
00230     c.clear();
00231     __throw_exception_again; 
00232       }
00233   }
00234 };
00235 
00236 // no equality is provided
00237 
00238 } // namespace std
00239 
00240 #endif /* __GLIBCPP_INTERNAL_QUEUE_H */
00241 
00242 // Local Variables:
00243 // mode:C++
00244 // End:

Generated on Tue Dec 23 12:34:10 2003 for libstdc++-v3 Source by doxygen 1.3.4