00001 // Queue implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 00004 // Free Software Foundation, Inc. 00005 // 00006 // This file is part of the GNU ISO C++ Library. This library is free 00007 // software; you can redistribute it and/or modify it under the 00008 // terms of the GNU General Public License as published by the 00009 // Free Software Foundation; either version 2, or (at your option) 00010 // any later version. 00011 00012 // This library is distributed in the hope that it will be useful, 00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 // GNU General Public License for more details. 00016 00017 // You should have received a copy of the GNU General Public License along 00018 // with this library; see the file COPYING. If not, write to the Free 00019 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 00020 // USA. 00021 00022 // As a special exception, you may use this file as part of a free software 00023 // library without restriction. Specifically, if other files instantiate 00024 // templates or use macros or inline functions from this file, or you compile 00025 // this file and link it with other files to produce an executable, this 00026 // file does not by itself cause the resulting executable to be covered by 00027 // the GNU General Public License. This exception does not however 00028 // invalidate any other reasons why the executable file might be covered by 00029 // the GNU General Public License. 00030 00031 /* 00032 * 00033 * Copyright (c) 1994 00034 * Hewlett-Packard Company 00035 * 00036 * Permission to use, copy, modify, distribute and sell this software 00037 * and its documentation for any purpose is hereby granted without fee, 00038 * provided that the above copyright notice appear in all copies and 00039 * that both that copyright notice and this permission notice appear 00040 * in supporting documentation. Hewlett-Packard Company makes no 00041 * representations about the suitability of this software for any 00042 * purpose. It is provided "as is" without express or implied warranty. 00043 * 00044 * 00045 * Copyright (c) 1996,1997 00046 * Silicon Graphics Computer Systems, Inc. 00047 * 00048 * Permission to use, copy, modify, distribute and sell this software 00049 * and its documentation for any purpose is hereby granted without fee, 00050 * provided that the above copyright notice appear in all copies and 00051 * that both that copyright notice and this permission notice appear 00052 * in supporting documentation. Silicon Graphics makes no 00053 * representations about the suitability of this software for any 00054 * purpose. It is provided "as is" without express or implied warranty. 00055 */ 00056 00057 /** @file stl_queue.h 00058 * This is an internal header file, included by other library headers. 00059 * You should not attempt to use it directly. 00060 */ 00061 00062 #ifndef _QUEUE_H 00063 #define _QUEUE_H 1 00064 00065 #include <bits/concept_check.h> 00066 #include <debug/debug.h> 00067 00068 _GLIBCXX_BEGIN_NAMESPACE(std) 00069 00070 /** 00071 * @brief A standard container giving FIFO behavior. 00072 * 00073 * @ingroup Containers 00074 * @ingroup Sequences 00075 * 00076 * Meets many of the requirements of a 00077 * <a href="tables.html#65">container</a>, 00078 * but does not define anything to do with iterators. Very few of the 00079 * other standard container interfaces are defined. 00080 * 00081 * This is not a true container, but an @e adaptor. It holds another 00082 * container, and provides a wrapper interface to that container. The 00083 * wrapper is what enforces strict first-in-first-out %queue behavior. 00084 * 00085 * The second template parameter defines the type of the underlying 00086 * sequence/container. It defaults to std::deque, but it can be any type 00087 * that supports @c front, @c back, @c push_back, and @c pop_front, 00088 * such as std::list or an appropriate user-defined type. 00089 * 00090 * Members not found in "normal" containers are @c container_type, 00091 * which is a typedef for the second Sequence parameter, and @c push and 00092 * @c pop, which are standard %queue/FIFO operations. 00093 */ 00094 template<typename _Tp, typename _Sequence = deque<_Tp> > 00095 class queue 00096 { 00097 // concept requirements 00098 typedef typename _Sequence::value_type _Sequence_value_type; 00099 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 00100 __glibcxx_class_requires(_Sequence, _FrontInsertionSequenceConcept) 00101 __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept) 00102 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept) 00103 00104 template<typename _Tp1, typename _Seq1> 00105 friend bool 00106 operator==(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&); 00107 00108 template<typename _Tp1, typename _Seq1> 00109 friend bool 00110 operator<(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&); 00111 00112 public: 00113 typedef typename _Sequence::value_type value_type; 00114 typedef typename _Sequence::reference reference; 00115 typedef typename _Sequence::const_reference const_reference; 00116 typedef typename _Sequence::size_type size_type; 00117 typedef _Sequence container_type; 00118 00119 protected: 00120 /** 00121 * 'c' is the underlying container. Maintainers wondering why 00122 * this isn't uglified as per style guidelines should note that 00123 * this name is specified in the standard, [23.2.3.1]. (Why? 00124 * Presumably for the same reason that it's protected instead 00125 * of private: to allow derivation. But none of the other 00126 * containers allow for derivation. Odd.) 00127 */ 00128 _Sequence c; 00129 00130 public: 00131 /** 00132 * @brief Default constructor creates no elements. 00133 */ 00134 explicit 00135 queue(const _Sequence& __c = _Sequence()) : c(__c) {} 00136 00137 /** 00138 * Returns true if the %queue is empty. 00139 */ 00140 bool 00141 empty() const 00142 { return c.empty(); } 00143 00144 /** Returns the number of elements in the %queue. */ 00145 size_type 00146 size() const 00147 { return c.size(); } 00148 00149 /** 00150 * Returns a read/write reference to the data at the first 00151 * element of the %queue. 00152 */ 00153 reference 00154 front() 00155 { 00156 __glibcxx_requires_nonempty(); 00157 return c.front(); 00158 } 00159 00160 /** 00161 * Returns a read-only (constant) reference to the data at the first 00162 * element of the %queue. 00163 */ 00164 const_reference 00165 front() const 00166 { 00167 __glibcxx_requires_nonempty(); 00168 return c.front(); 00169 } 00170 00171 /** 00172 * Returns a read/write reference to the data at the last 00173 * element of the %queue. 00174 */ 00175 reference 00176 back() 00177 { 00178 __glibcxx_requires_nonempty(); 00179 return c.back(); 00180 } 00181 00182 /** 00183 * Returns a read-only (constant) reference to the data at the last 00184 * element of the %queue. 00185 */ 00186 const_reference 00187 back() const 00188 { 00189 __glibcxx_requires_nonempty(); 00190 return c.back(); 00191 } 00192 00193 /** 00194 * @brief Add data to the end of the %queue. 00195 * @param x Data to be added. 00196 * 00197 * This is a typical %queue operation. The function creates an 00198 * element at the end of the %queue and assigns the given data 00199 * to it. The time complexity of the operation depends on the 00200 * underlying sequence. 00201 */ 00202 void 00203 push(const value_type& __x) 00204 { c.push_back(__x); } 00205 00206 /** 00207 * @brief Removes first element. 00208 * 00209 * This is a typical %queue operation. It shrinks the %queue by one. 00210 * The time complexity of the operation depends on the underlying 00211 * sequence. 00212 * 00213 * Note that no data is returned, and if the first element's 00214 * data is needed, it should be retrieved before pop() is 00215 * called. 00216 */ 00217 void 00218 pop() 00219 { 00220 __glibcxx_requires_nonempty(); 00221 c.pop_front(); 00222 } 00223 }; 00224 00225 00226 /** 00227 * @brief Queue equality comparison. 00228 * @param x A %queue. 00229 * @param y A %queue of the same type as @a x. 00230 * @return True iff the size and elements of the queues are equal. 00231 * 00232 * This is an equivalence relation. Complexity and semantics depend on the 00233 * underlying sequence type, but the expected rules are: this relation is 00234 * linear in the size of the sequences, and queues are considered equivalent 00235 * if their sequences compare equal. 00236 */ 00237 template<typename _Tp, typename _Seq> 00238 inline bool 00239 operator==(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 00240 { return __x.c == __y.c; } 00241 00242 /** 00243 * @brief Queue ordering relation. 00244 * @param x A %queue. 00245 * @param y A %queue of the same type as @a x. 00246 * @return True iff @a x is lexicographically less than @a y. 00247 * 00248 * This is an total ordering relation. Complexity and semantics 00249 * depend on the underlying sequence type, but the expected rules 00250 * are: this relation is linear in the size of the sequences, the 00251 * elements must be comparable with @c <, and 00252 * std::lexicographical_compare() is usually used to make the 00253 * determination. 00254 */ 00255 template<typename _Tp, typename _Seq> 00256 inline bool 00257 operator<(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 00258 { return __x.c < __y.c; } 00259 00260 /// Based on operator== 00261 template<typename _Tp, typename _Seq> 00262 inline bool 00263 operator!=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 00264 { return !(__x == __y); } 00265 00266 /// Based on operator< 00267 template<typename _Tp, typename _Seq> 00268 inline bool 00269 operator>(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 00270 { return __y < __x; } 00271 00272 /// Based on operator< 00273 template<typename _Tp, typename _Seq> 00274 inline bool 00275 operator<=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 00276 { return !(__y < __x); } 00277 00278 /// Based on operator< 00279 template<typename _Tp, typename _Seq> 00280 inline bool 00281 operator>=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 00282 { return !(__x < __y); } 00283 00284 /** 00285 * @brief A standard container automatically sorting its contents. 00286 * 00287 * @ingroup Containers 00288 * @ingroup Sequences 00289 * 00290 * This is not a true container, but an @e adaptor. It holds 00291 * another container, and provides a wrapper interface to that 00292 * container. The wrapper is what enforces priority-based sorting 00293 * and %queue behavior. Very few of the standard container/sequence 00294 * interface requirements are met (e.g., iterators). 00295 * 00296 * The second template parameter defines the type of the underlying 00297 * sequence/container. It defaults to std::vector, but it can be 00298 * any type that supports @c front(), @c push_back, @c pop_back, 00299 * and random-access iterators, such as std::deque or an 00300 * appropriate user-defined type. 00301 * 00302 * The third template parameter supplies the means of making 00303 * priority comparisons. It defaults to @c less<value_type> but 00304 * can be anything defining a strict weak ordering. 00305 * 00306 * Members not found in "normal" containers are @c container_type, 00307 * which is a typedef for the second Sequence parameter, and @c 00308 * push, @c pop, and @c top, which are standard %queue operations. 00309 * 00310 * @note No equality/comparison operators are provided for 00311 * %priority_queue. 00312 * 00313 * @note Sorting of the elements takes place as they are added to, 00314 * and removed from, the %priority_queue using the 00315 * %priority_queue's member functions. If you access the elements 00316 * by other means, and change their data such that the sorting 00317 * order would be different, the %priority_queue will not re-sort 00318 * the elements for you. (How could it know to do so?) 00319 */ 00320 template<typename _Tp, typename _Sequence = vector<_Tp>, 00321 typename _Compare = less<typename _Sequence::value_type> > 00322 class priority_queue 00323 { 00324 // concept requirements 00325 typedef typename _Sequence::value_type _Sequence_value_type; 00326 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 00327 __glibcxx_class_requires(_Sequence, _SequenceConcept) 00328 __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept) 00329 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept) 00330 __glibcxx_class_requires4(_Compare, bool, _Tp, _Tp, 00331 _BinaryFunctionConcept) 00332 00333 public: 00334 typedef typename _Sequence::value_type value_type; 00335 typedef typename _Sequence::reference reference; 00336 typedef typename _Sequence::const_reference const_reference; 00337 typedef typename _Sequence::size_type size_type; 00338 typedef _Sequence container_type; 00339 00340 protected: 00341 // See queue::c for notes on these names. 00342 _Sequence c; 00343 _Compare comp; 00344 00345 public: 00346 /** 00347 * @brief Default constructor creates no elements. 00348 */ 00349 explicit 00350 priority_queue(const _Compare& __x = _Compare(), 00351 const _Sequence& __s = _Sequence()) 00352 : c(__s), comp(__x) 00353 { std::make_heap(c.begin(), c.end(), comp); } 00354 00355 /** 00356 * @brief Builds a %queue from a range. 00357 * @param first An input iterator. 00358 * @param last An input iterator. 00359 * @param x A comparison functor describing a strict weak ordering. 00360 * @param s An initial sequence with which to start. 00361 * 00362 * Begins by copying @a s, inserting a copy of the elements 00363 * from @a [first,last) into the copy of @a s, then ordering 00364 * the copy according to @a x. 00365 * 00366 * For more information on function objects, see the 00367 * documentation on @link s20_3_1_base functor base 00368 * classes@endlink. 00369 */ 00370 template<typename _InputIterator> 00371 priority_queue(_InputIterator __first, _InputIterator __last, 00372 const _Compare& __x = _Compare(), 00373 const _Sequence& __s = _Sequence()) 00374 : c(__s), comp(__x) 00375 { 00376 __glibcxx_requires_valid_range(__first, __last); 00377 c.insert(c.end(), __first, __last); 00378 std::make_heap(c.begin(), c.end(), comp); 00379 } 00380 00381 /** 00382 * Returns true if the %queue is empty. 00383 */ 00384 bool 00385 empty() const 00386 { return c.empty(); } 00387 00388 /** Returns the number of elements in the %queue. */ 00389 size_type 00390 size() const 00391 { return c.size(); } 00392 00393 /** 00394 * Returns a read-only (constant) reference to the data at the first 00395 * element of the %queue. 00396 */ 00397 const_reference 00398 top() const 00399 { 00400 __glibcxx_requires_nonempty(); 00401 return c.front(); 00402 } 00403 00404 /** 00405 * @brief Add data to the %queue. 00406 * @param x Data to be added. 00407 * 00408 * This is a typical %queue operation. 00409 * The time complexity of the operation depends on the underlying 00410 * sequence. 00411 */ 00412 void 00413 push(const value_type& __x) 00414 { 00415 c.push_back(__x); 00416 std::push_heap(c.begin(), c.end(), comp); 00417 } 00418 00419 /** 00420 * @brief Removes first element. 00421 * 00422 * This is a typical %queue operation. It shrinks the %queue 00423 * by one. The time complexity of the operation depends on the 00424 * underlying sequence. 00425 * 00426 * Note that no data is returned, and if the first element's 00427 * data is needed, it should be retrieved before pop() is 00428 * called. 00429 */ 00430 void 00431 pop() 00432 { 00433 __glibcxx_requires_nonempty(); 00434 std::pop_heap(c.begin(), c.end(), comp); 00435 c.pop_back(); 00436 } 00437 }; 00438 00439 // No equality/comparison operators are provided for priority_queue. 00440 00441 _GLIBCXX_END_NAMESPACE 00442 00443 #endif /* _QUEUE_H */