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