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