00001 // Queue implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002 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 00056 /** @file stl_queue.h 00057 * This is an internal header file, included by other library headers. 00058 * You should not attempt to use it directly. 00059 */ 00060 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 // Forward declarations of operators < and ==, needed for friend declaration. 00069 00070 template <typename _Tp, typename _Sequence = deque<_Tp> > 00071 class queue; 00072 00073 template <typename _Tp, typename _Seq> 00074 inline bool operator==(const queue<_Tp,_Seq>&, const queue<_Tp,_Seq>&); 00075 00076 template <typename _Tp, typename _Seq> 00077 inline bool operator<(const queue<_Tp,_Seq>&, const queue<_Tp,_Seq>&); 00078 00079 00080 /** 00081 * @brief A standard container giving FIFO behavior. 00082 * 00083 * @ingroup Containers 00084 * @ingroup Sequences 00085 * 00086 * Meets many of the requirements of a 00087 * <a href="tables.html#65">container</a>, 00088 * but does not define anything to do with iterators. Very few of the 00089 * other standard container interfaces are defined. 00090 * 00091 * This is not a true container, but an @e adaptor. It holds another 00092 * container, and provides a wrapper interface to that container. The 00093 * wrapper is what enforces strict first-in-first-out %queue behavior. 00094 * 00095 * The second template parameter defines the type of the underlying 00096 * sequence/container. It defaults to std::deque, but it can be any type 00097 * that supports @c front, @c back, @c push_back, and @c pop_front, 00098 * such as std::list or an appropriate user-defined type. 00099 * 00100 * Members not found in "normal" containers are @c container_type, 00101 * which is a typedef for the second Sequence parameter, and @c push and 00102 * @c pop, which are standard %queue/FIFO operations. 00103 */ 00104 template <typename _Tp, typename _Sequence> 00105 class queue 00106 { 00107 // concept requirements 00108 typedef typename _Sequence::value_type _Sequence_value_type; 00109 __glibcpp_class_requires(_Tp, _SGIAssignableConcept) 00110 __glibcpp_class_requires(_Sequence, _FrontInsertionSequenceConcept) 00111 __glibcpp_class_requires(_Sequence, _BackInsertionSequenceConcept) 00112 __glibcpp_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept) 00113 00114 template <typename _Tp1, typename _Seq1> 00115 friend bool operator== (const queue<_Tp1, _Seq1>&, 00116 const queue<_Tp1, _Seq1>&); 00117 template <typename _Tp1, typename _Seq1> 00118 friend bool operator< (const queue<_Tp1, _Seq1>&, 00119 const queue<_Tp1, _Seq1>&); 00120 00121 public: 00122 typedef typename _Sequence::value_type value_type; 00123 typedef typename _Sequence::reference reference; 00124 typedef typename _Sequence::const_reference const_reference; 00125 typedef typename _Sequence::size_type size_type; 00126 typedef _Sequence container_type; 00127 00128 protected: 00129 /** 00130 * 'c' is the underlying container. Maintainers wondering why this isn't 00131 * uglified as per style guidelines should note that this name is 00132 * specified in the standard, [23.2.3.1]. (Why? Presumably for the same 00133 * reason that it's protected instead of private: to allow derivation. 00134 * But none of the other containers allow for derivation. Odd.) 00135 */ 00136 _Sequence c; 00137 00138 public: 00139 /** 00140 * @brief Default constructor creates no elements. 00141 */ 00142 explicit 00143 queue(const _Sequence& __c = _Sequence()) 00144 : c(__c) {} 00145 00146 /** 00147 * Returns true if the %queue is empty. 00148 */ 00149 bool 00150 empty() const { return c.empty(); } 00151 00152 /** Returns the number of elements in the %queue. */ 00153 size_type 00154 size() const { return c.size(); } 00155 00156 /** 00157 * Returns a read/write reference to the data at the first element of the 00158 * %queue. 00159 */ 00160 reference 00161 front() { return c.front(); } 00162 00163 /** 00164 * Returns a read-only (constant) reference to the data at the first 00165 * element of the %queue. 00166 */ 00167 const_reference 00168 front() const { return c.front(); } 00169 00170 /** 00171 * Returns a read/write reference to the data at the last element of the 00172 * %queue. 00173 */ 00174 reference 00175 back() { return c.back(); } 00176 00177 /** 00178 * Returns a read-only (constant) reference to the data at the last 00179 * element of the %queue. 00180 */ 00181 const_reference 00182 back() const { return c.back(); } 00183 00184 /** 00185 * @brief Add data to the end of the %queue. 00186 * @param x Data to be added. 00187 * 00188 * This is a typical %queue operation. The function creates an element at 00189 * the end of the %queue and assigns the given data to it. 00190 * The time complexity of the operation depends on the underlying 00191 * sequence. 00192 */ 00193 void 00194 push(const value_type& __x) { c.push_back(__x); } 00195 00196 /** 00197 * @brief Removes first element. 00198 * 00199 * This is a typical %queue operation. It shrinks the %queue by one. 00200 * The time complexity of the operation depends on the underlying 00201 * sequence. 00202 * 00203 * Note that no data is returned, and if the first element's data is 00204 * needed, it should be retrieved before pop() is called. 00205 */ 00206 void 00207 pop() { c.pop_front(); } 00208 }; 00209 00210 00211 /** 00212 * @brief Queue equality comparison. 00213 * @param x A %queue. 00214 * @param y A %queue of the same type as @a x. 00215 * @return True iff the size and elements of the queues are equal. 00216 * 00217 * This is an equivalence relation. Complexity and semantics depend on the 00218 * underlying sequence type, but the expected rules are: this relation is 00219 * linear in the size of the sequences, and queues are considered equivalent 00220 * if their sequences compare equal. 00221 */ 00222 template <typename _Tp, typename _Sequence> 00223 inline bool 00224 operator==(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y) 00225 { return __x.c == __y.c; } 00226 00227 /** 00228 * @brief Queue ordering relation. 00229 * @param x A %queue. 00230 * @param y A %queue of the same type as @a x. 00231 * @return True iff @a x is lexographically less than @a y. 00232 * 00233 * This is an total ordering relation. Complexity and semantics depend on 00234 * the underlying sequence type, but the expected rules are: this relation 00235 * is linear in the size of the sequences, the elements must be comparable 00236 * with @c <, and std::lexographical_compare() is usually used to make the 00237 * determination. 00238 */ 00239 template <typename _Tp, typename _Sequence> 00240 inline bool 00241 operator<(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y) 00242 { return __x.c < __y.c; } 00243 00244 /// Based on operator== 00245 template <typename _Tp, typename _Sequence> 00246 inline bool 00247 operator!=(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y) 00248 { return !(__x == __y); } 00249 00250 /// Based on operator< 00251 template <typename _Tp, typename _Sequence> 00252 inline bool 00253 operator>(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y) 00254 { return __y < __x; } 00255 00256 /// Based on operator< 00257 template <typename _Tp, typename _Sequence> 00258 inline bool 00259 operator<=(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y) 00260 { return !(__y < __x); } 00261 00262 /// Based on operator< 00263 template <typename _Tp, typename _Sequence> 00264 inline bool 00265 operator>=(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y) 00266 { return !(__x < __y); } 00267 00268 00269 /** 00270 * @brief A standard container automatically sorting its contents. 00271 * 00272 * @ingroup Containers 00273 * @ingroup Sequences 00274 * 00275 * This is not a true container, but an @e adaptor. It holds another 00276 * container, and provides a wrapper interface to that container. The 00277 * wrapper is what enforces sorting and first-in-first-out %queue behavior. 00278 * Very few of the standard container/sequence interface requirements are 00279 * met (e.g., iterators). 00280 * 00281 * The second template parameter defines the type of the underlying 00282 * sequence/container. It defaults to std::vector, but it can be any type 00283 * that supports @c front(), @c push_back, @c pop_back, and random-access 00284 * iterators, such as std::deque or an appropriate user-defined type. 00285 * 00286 * The third template parameter supplies the means of making priority 00287 * comparisons. It defaults to @c less<value_type> but can be anything 00288 * defining a strict weak ordering. 00289 * 00290 * Members not found in "normal" containers are @c container_type, 00291 * which is a typedef for the second Sequence parameter, and @c push, 00292 * @c pop, and @c top, which are standard %queue/FIFO operations. 00293 * 00294 * @note No equality/comparison operators are provided for %priority_queue. 00295 * 00296 * @note Sorting of the elements takes place as they are added to, and 00297 * removed from, the %priority_queue using the %priority_queue's 00298 * member functions. If you access the elements by other means, and 00299 * change their data such that the sorting order would be different, 00300 * the %priority_queue will not re-sort the elements for you. (How 00301 * could it know to do so?) 00302 */ 00303 template <typename _Tp, typename _Sequence = vector<_Tp>, 00304 typename _Compare = less<typename _Sequence::value_type> > 00305 class priority_queue 00306 { 00307 // concept requirements 00308 typedef typename _Sequence::value_type _Sequence_value_type; 00309 __glibcpp_class_requires(_Tp, _SGIAssignableConcept) 00310 __glibcpp_class_requires(_Sequence, _SequenceConcept) 00311 __glibcpp_class_requires(_Sequence, _RandomAccessContainerConcept) 00312 __glibcpp_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept) 00313 __glibcpp_class_requires4(_Compare, bool, _Tp, _Tp, _BinaryFunctionConcept) 00314 00315 public: 00316 typedef typename _Sequence::value_type value_type; 00317 typedef typename _Sequence::reference reference; 00318 typedef typename _Sequence::const_reference const_reference; 00319 typedef typename _Sequence::size_type size_type; 00320 typedef _Sequence container_type; 00321 00322 protected: 00323 // See queue::c for notes on these names. 00324 _Sequence c; 00325 _Compare comp; 00326 00327 public: 00328 /** 00329 * @brief Default constructor creates no elements. 00330 */ 00331 explicit 00332 priority_queue(const _Compare& __x = _Compare(), 00333 const _Sequence& __s = _Sequence()) 00334 : c(__s), comp(__x) 00335 { make_heap(c.begin(), c.end(), comp); } 00336 00337 /** 00338 * @brief Builds a %queue from a range. 00339 * @param first An input iterator. 00340 * @param last An input iterator. 00341 * @param x A comparison functor describing a strict weak ordering. 00342 * @param s An initial sequence with which to start. 00343 * 00344 * Begins by copying @a s, inserting a copy of the elements from 00345 * @a [first,last) into the copy of @a s, then ordering the copy 00346 * according to @a x. 00347 * 00348 * For more information on function objects, see the documentation on 00349 * @link s20_3_1_base functor base classes@endlink. 00350 */ 00351 template <typename _InputIterator> 00352 priority_queue(_InputIterator __first, _InputIterator __last, 00353 const _Compare& __x = _Compare(), 00354 const _Sequence& __s = _Sequence()) 00355 : c(__s), comp(__x) 00356 { 00357 c.insert(c.end(), __first, __last); 00358 make_heap(c.begin(), c.end(), comp); 00359 } 00360 00361 /** 00362 * Returns true if the %queue is empty. 00363 */ 00364 bool 00365 empty() const { return c.empty(); } 00366 00367 /** Returns the number of elements in the %queue. */ 00368 size_type 00369 size() const { return c.size(); } 00370 00371 /** 00372 * Returns a read-only (constant) reference to the data at the first 00373 * element of the %queue. 00374 */ 00375 const_reference 00376 top() const { return c.front(); } 00377 00378 /** 00379 * @brief Add data to the %queue. 00380 * @param x Data to be added. 00381 * 00382 * This is a typical %queue operation. 00383 * The time complexity of the operation depends on the underlying 00384 * sequence. 00385 */ 00386 void 00387 push(const value_type& __x) 00388 { 00389 try 00390 { 00391 c.push_back(__x); 00392 push_heap(c.begin(), c.end(), comp); 00393 } 00394 catch(...) 00395 { 00396 c.clear(); 00397 __throw_exception_again; 00398 } 00399 } 00400 00401 /** 00402 * @brief Removes first element. 00403 * 00404 * This is a typical %queue operation. It shrinks the %queue by one. 00405 * The time complexity of the operation depends on the underlying 00406 * sequence. 00407 * 00408 * Note that no data is returned, and if the first element's data is 00409 * needed, it should be retrieved before pop() is called. 00410 */ 00411 void 00412 pop() 00413 { 00414 try 00415 { 00416 pop_heap(c.begin(), c.end(), comp); 00417 c.pop_back(); 00418 } 00419 catch(...) 00420 { 00421 c.clear(); 00422 __throw_exception_again; 00423 } 00424 } 00425 }; 00426 00427 // No equality/comparison operators are provided for priority_queue. 00428 } // namespace std 00429 00430 #endif /* __GLIBCPP_INTERNAL_QUEUE_H */