1224133Sdim// Queue implementation -*- C++ -*- 2224133Sdim 3224133Sdim// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 4224133Sdim// Free Software Foundation, Inc. 5224133Sdim// 6224133Sdim// This file is part of the GNU ISO C++ Library. This library is free 7224133Sdim// software; you can redistribute it and/or modify it under the 8224133Sdim// terms of the GNU General Public License as published by the 9224133Sdim// Free Software Foundation; either version 3, or (at your option) 10224133Sdim// any later version. 11224133Sdim 12224133Sdim// This library is distributed in the hope that it will be useful, 13224133Sdim// but WITHOUT ANY WARRANTY; without even the implied warranty of 14224133Sdim// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15224133Sdim// GNU General Public License for more details. 16224133Sdim 17224133Sdim// Under Section 7 of GPL version 3, you are granted additional 18224133Sdim// permissions described in the GCC Runtime Library Exception, version 19224133Sdim// 3.1, as published by the Free Software Foundation. 20224133Sdim 21224133Sdim// You should have received a copy of the GNU General Public License and 22224133Sdim// a copy of the GCC Runtime Library Exception along with this program; 23224133Sdim// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 24224133Sdim// <http://www.gnu.org/licenses/>. 25224133Sdim 26224133Sdim/* 27224133Sdim * 28234353Sdim * Copyright (c) 1994 29224133Sdim * Hewlett-Packard Company 30224133Sdim * 31224133Sdim * Permission to use, copy, modify, distribute and sell this software 32224133Sdim * and its documentation for any purpose is hereby granted without fee, 33224133Sdim * provided that the above copyright notice appear in all copies and 34224133Sdim * that both that copyright notice and this permission notice appear 35224133Sdim * in supporting documentation. Hewlett-Packard Company makes no 36224133Sdim * representations about the suitability of this software for any 37224133Sdim * purpose. It is provided "as is" without express or implied warranty. 38224133Sdim * 39224133Sdim * 40224133Sdim * Copyright (c) 1996,1997 41224133Sdim * Silicon Graphics Computer Systems, Inc. 42224133Sdim * 43224133Sdim * Permission to use, copy, modify, distribute and sell this software 44224133Sdim * and its documentation for any purpose is hereby granted without fee, 45224133Sdim * provided that the above copyright notice appear in all copies and 46224133Sdim * that both that copyright notice and this permission notice appear 47224133Sdim * in supporting documentation. Silicon Graphics makes no 48224133Sdim * representations about the suitability of this software for any 49224133Sdim * purpose. It is provided "as is" without express or implied warranty. 50224133Sdim */ 51224133Sdim 52234353Sdim/** @file stl_queue.h 53234353Sdim * This is an internal header file, included by other library headers. 54224133Sdim * You should not attempt to use it directly. 55234353Sdim */ 56234353Sdim 57234353Sdim#ifndef _STL_QUEUE_H 58234353Sdim#define _STL_QUEUE_H 1 59234353Sdim 60224133Sdim#include <bits/concept_check.h> 61224133Sdim#include <debug/debug.h> 62224133Sdim 63224133Sdim_GLIBCXX_BEGIN_NAMESPACE(std) 64234353Sdim 65224133Sdim /** 66224133Sdim * @brief A standard container giving FIFO behavior. 67224133Sdim * 68224133Sdim * @ingroup sequences 69224133Sdim * 70234353Sdim * Meets many of the requirements of a 71234353Sdim * <a href="tables.html#65">container</a>, 72234353Sdim * but does not define anything to do with iterators. Very few of the 73224133Sdim * other standard container interfaces are defined. 74224133Sdim * 75224133Sdim * This is not a true container, but an @e adaptor. It holds another 76224133Sdim * container, and provides a wrapper interface to that container. The 77224133Sdim * wrapper is what enforces strict first-in-first-out %queue behavior. 78224133Sdim * 79224133Sdim * The second template parameter defines the type of the underlying 80224133Sdim * sequence/container. It defaults to std::deque, but it can be any type 81224133Sdim * that supports @c front, @c back, @c push_back, and @c pop_front, 82224133Sdim * such as std::list or an appropriate user-defined type. 83224133Sdim * 84224133Sdim * Members not found in @a normal containers are @c container_type, 85224133Sdim * which is a typedef for the second Sequence parameter, and @c push and 86224133Sdim * @c pop, which are standard %queue/FIFO operations. 87 */ 88 template<typename _Tp, typename _Sequence = deque<_Tp> > 89 class queue 90 { 91 // concept requirements 92 typedef typename _Sequence::value_type _Sequence_value_type; 93 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 94 __glibcxx_class_requires(_Sequence, _FrontInsertionSequenceConcept) 95 __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept) 96 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept) 97 98 template<typename _Tp1, typename _Seq1> 99 friend bool 100 operator==(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&); 101 102 template<typename _Tp1, typename _Seq1> 103 friend bool 104 operator<(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&); 105 106 public: 107 typedef typename _Sequence::value_type value_type; 108 typedef typename _Sequence::reference reference; 109 typedef typename _Sequence::const_reference const_reference; 110 typedef typename _Sequence::size_type size_type; 111 typedef _Sequence container_type; 112 113 protected: 114 /** 115 * 'c' is the underlying container. Maintainers wondering why 116 * this isn't uglified as per style guidelines should note that 117 * this name is specified in the standard, [23.2.3.1]. (Why? 118 * Presumably for the same reason that it's protected instead 119 * of private: to allow derivation. But none of the other 120 * containers allow for derivation. Odd.) 121 */ 122 _Sequence c; 123 124 public: 125 /** 126 * @brief Default constructor creates no elements. 127 */ 128#ifndef __GXX_EXPERIMENTAL_CXX0X__ 129 explicit 130 queue(const _Sequence& __c = _Sequence()) 131 : c(__c) { } 132#else 133 explicit 134 queue(const _Sequence& __c) 135 : c(__c) { } 136 137 explicit 138 queue(_Sequence&& __c = _Sequence()) 139 : c(std::move(__c)) { } 140 141 queue(queue&& __q) 142 : c(std::move(__q.c)) { } 143 144 queue& 145 operator=(queue&& __q) 146 { 147 c = std::move(__q.c); 148 return *this; 149 } 150#endif 151 152 /** 153 * Returns true if the %queue is empty. 154 */ 155 bool 156 empty() const 157 { return c.empty(); } 158 159 /** Returns the number of elements in the %queue. */ 160 size_type 161 size() const 162 { return c.size(); } 163 164 /** 165 * Returns a read/write reference to the data at the first 166 * element of the %queue. 167 */ 168 reference 169 front() 170 { 171 __glibcxx_requires_nonempty(); 172 return c.front(); 173 } 174 175 /** 176 * Returns a read-only (constant) reference to the data at the first 177 * element of the %queue. 178 */ 179 const_reference 180 front() const 181 { 182 __glibcxx_requires_nonempty(); 183 return c.front(); 184 } 185 186 /** 187 * Returns a read/write reference to the data at the last 188 * element of the %queue. 189 */ 190 reference 191 back() 192 { 193 __glibcxx_requires_nonempty(); 194 return c.back(); 195 } 196 197 /** 198 * Returns a read-only (constant) reference to the data at the last 199 * element of the %queue. 200 */ 201 const_reference 202 back() const 203 { 204 __glibcxx_requires_nonempty(); 205 return c.back(); 206 } 207 208 /** 209 * @brief Add data to the end of the %queue. 210 * @param x Data to be added. 211 * 212 * This is a typical %queue operation. The function creates an 213 * element at the end of the %queue and assigns the given data 214 * to it. The time complexity of the operation depends on the 215 * underlying sequence. 216 */ 217 void 218 push(const value_type& __x) 219 { c.push_back(__x); } 220 221#ifdef __GXX_EXPERIMENTAL_CXX0X__ 222 void 223 push(value_type&& __x) 224 { c.push_back(std::move(__x)); } 225 226 template<typename... _Args> 227 void 228 emplace(_Args&&... __args) 229 { c.emplace_back(std::forward<_Args>(__args)...); } 230#endif 231 232 /** 233 * @brief Removes first element. 234 * 235 * This is a typical %queue operation. It shrinks the %queue by one. 236 * The time complexity of the operation depends on the underlying 237 * sequence. 238 * 239 * Note that no data is returned, and if the first element's 240 * data is needed, it should be retrieved before pop() is 241 * called. 242 */ 243 void 244 pop() 245 { 246 __glibcxx_requires_nonempty(); 247 c.pop_front(); 248 } 249 250#ifdef __GXX_EXPERIMENTAL_CXX0X__ 251 void 252 swap(queue& __q) 253 { c.swap(__q.c); } 254#endif 255 }; 256 257 /** 258 * @brief Queue equality comparison. 259 * @param x A %queue. 260 * @param y A %queue of the same type as @a x. 261 * @return True iff the size and elements of the queues are equal. 262 * 263 * This is an equivalence relation. Complexity and semantics depend on the 264 * underlying sequence type, but the expected rules are: this relation is 265 * linear in the size of the sequences, and queues are considered equivalent 266 * if their sequences compare equal. 267 */ 268 template<typename _Tp, typename _Seq> 269 inline bool 270 operator==(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 271 { return __x.c == __y.c; } 272 273 /** 274 * @brief Queue ordering relation. 275 * @param x A %queue. 276 * @param y A %queue of the same type as @a x. 277 * @return True iff @a x is lexicographically less than @a y. 278 * 279 * This is an total ordering relation. Complexity and semantics 280 * depend on the underlying sequence type, but the expected rules 281 * are: this relation is linear in the size of the sequences, the 282 * elements must be comparable with @c <, and 283 * std::lexicographical_compare() is usually used to make the 284 * determination. 285 */ 286 template<typename _Tp, typename _Seq> 287 inline bool 288 operator<(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 289 { return __x.c < __y.c; } 290 291 /// Based on operator== 292 template<typename _Tp, typename _Seq> 293 inline bool 294 operator!=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 295 { return !(__x == __y); } 296 297 /// Based on operator< 298 template<typename _Tp, typename _Seq> 299 inline bool 300 operator>(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 301 { return __y < __x; } 302 303 /// Based on operator< 304 template<typename _Tp, typename _Seq> 305 inline bool 306 operator<=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 307 { return !(__y < __x); } 308 309 /// Based on operator< 310 template<typename _Tp, typename _Seq> 311 inline bool 312 operator>=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 313 { return !(__x < __y); } 314 315#ifdef __GXX_EXPERIMENTAL_CXX0X__ 316 template<typename _Tp, typename _Seq> 317 inline void 318 swap(queue<_Tp, _Seq>& __x, queue<_Tp, _Seq>& __y) 319 { __x.swap(__y); } 320#endif 321 322 /** 323 * @brief A standard container automatically sorting its contents. 324 * 325 * @ingroup sequences 326 * 327 * This is not a true container, but an @e adaptor. It holds 328 * another container, and provides a wrapper interface to that 329 * container. The wrapper is what enforces priority-based sorting 330 * and %queue behavior. Very few of the standard container/sequence 331 * interface requirements are met (e.g., iterators). 332 * 333 * The second template parameter defines the type of the underlying 334 * sequence/container. It defaults to std::vector, but it can be 335 * any type that supports @c front(), @c push_back, @c pop_back, 336 * and random-access iterators, such as std::deque or an 337 * appropriate user-defined type. 338 * 339 * The third template parameter supplies the means of making 340 * priority comparisons. It defaults to @c less<value_type> but 341 * can be anything defining a strict weak ordering. 342 * 343 * Members not found in @a normal containers are @c container_type, 344 * which is a typedef for the second Sequence parameter, and @c 345 * push, @c pop, and @c top, which are standard %queue operations. 346 * 347 * @note No equality/comparison operators are provided for 348 * %priority_queue. 349 * 350 * @note Sorting of the elements takes place as they are added to, 351 * and removed from, the %priority_queue using the 352 * %priority_queue's member functions. If you access the elements 353 * by other means, and change their data such that the sorting 354 * order would be different, the %priority_queue will not re-sort 355 * the elements for you. (How could it know to do so?) 356 */ 357 template<typename _Tp, typename _Sequence = vector<_Tp>, 358 typename _Compare = less<typename _Sequence::value_type> > 359 class priority_queue 360 { 361 // concept requirements 362 typedef typename _Sequence::value_type _Sequence_value_type; 363 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 364 __glibcxx_class_requires(_Sequence, _SequenceConcept) 365 __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept) 366 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept) 367 __glibcxx_class_requires4(_Compare, bool, _Tp, _Tp, 368 _BinaryFunctionConcept) 369 370 public: 371 typedef typename _Sequence::value_type value_type; 372 typedef typename _Sequence::reference reference; 373 typedef typename _Sequence::const_reference const_reference; 374 typedef typename _Sequence::size_type size_type; 375 typedef _Sequence container_type; 376 377 protected: 378 // See queue::c for notes on these names. 379 _Sequence c; 380 _Compare comp; 381 382 public: 383 /** 384 * @brief Default constructor creates no elements. 385 */ 386#ifndef __GXX_EXPERIMENTAL_CXX0X__ 387 explicit 388 priority_queue(const _Compare& __x = _Compare(), 389 const _Sequence& __s = _Sequence()) 390 : c(__s), comp(__x) 391 { std::make_heap(c.begin(), c.end(), comp); } 392#else 393 explicit 394 priority_queue(const _Compare& __x, 395 const _Sequence& __s) 396 : c(__s), comp(__x) 397 { std::make_heap(c.begin(), c.end(), comp); } 398 399 explicit 400 priority_queue(const _Compare& __x = _Compare(), 401 _Sequence&& __s = _Sequence()) 402 : c(std::move(__s)), comp(__x) 403 { std::make_heap(c.begin(), c.end(), comp); } 404#endif 405 406 /** 407 * @brief Builds a %queue from a range. 408 * @param first An input iterator. 409 * @param last An input iterator. 410 * @param x A comparison functor describing a strict weak ordering. 411 * @param s An initial sequence with which to start. 412 * 413 * Begins by copying @a s, inserting a copy of the elements 414 * from @a [first,last) into the copy of @a s, then ordering 415 * the copy according to @a x. 416 * 417 * For more information on function objects, see the 418 * documentation on @link functors functor base 419 * classes@endlink. 420 */ 421#ifndef __GXX_EXPERIMENTAL_CXX0X__ 422 template<typename _InputIterator> 423 priority_queue(_InputIterator __first, _InputIterator __last, 424 const _Compare& __x = _Compare(), 425 const _Sequence& __s = _Sequence()) 426 : c(__s), comp(__x) 427 { 428 __glibcxx_requires_valid_range(__first, __last); 429 c.insert(c.end(), __first, __last); 430 std::make_heap(c.begin(), c.end(), comp); 431 } 432#else 433 template<typename _InputIterator> 434 priority_queue(_InputIterator __first, _InputIterator __last, 435 const _Compare& __x, 436 const _Sequence& __s) 437 : c(__s), comp(__x) 438 { 439 __glibcxx_requires_valid_range(__first, __last); 440 c.insert(c.end(), __first, __last); 441 std::make_heap(c.begin(), c.end(), comp); 442 } 443 444 template<typename _InputIterator> 445 priority_queue(_InputIterator __first, _InputIterator __last, 446 const _Compare& __x = _Compare(), 447 _Sequence&& __s = _Sequence()) 448 : c(std::move(__s)), comp(__x) 449 { 450 __glibcxx_requires_valid_range(__first, __last); 451 c.insert(c.end(), __first, __last); 452 std::make_heap(c.begin(), c.end(), comp); 453 } 454 455 priority_queue(priority_queue&& __pq) 456 : c(std::move(__pq.c)), comp(std::move(__pq.comp)) { } 457 458 priority_queue& 459 operator=(priority_queue&& __pq) 460 { 461 c = std::move(__pq.c); 462 comp = std::move(__pq.comp); 463 return *this; 464 } 465#endif 466 467 /** 468 * Returns true if the %queue is empty. 469 */ 470 bool 471 empty() const 472 { return c.empty(); } 473 474 /** Returns the number of elements in the %queue. */ 475 size_type 476 size() const 477 { return c.size(); } 478 479 /** 480 * Returns a read-only (constant) reference to the data at the first 481 * element of the %queue. 482 */ 483 const_reference 484 top() const 485 { 486 __glibcxx_requires_nonempty(); 487 return c.front(); 488 } 489 490 /** 491 * @brief Add data to the %queue. 492 * @param x Data to be added. 493 * 494 * This is a typical %queue operation. 495 * The time complexity of the operation depends on the underlying 496 * sequence. 497 */ 498 void 499 push(const value_type& __x) 500 { 501 c.push_back(__x); 502 std::push_heap(c.begin(), c.end(), comp); 503 } 504 505#ifdef __GXX_EXPERIMENTAL_CXX0X__ 506 void 507 push(value_type&& __x) 508 { 509 c.push_back(std::move(__x)); 510 std::push_heap(c.begin(), c.end(), comp); 511 } 512 513 template<typename... _Args> 514 void 515 emplace(_Args&&... __args) 516 { 517 c.emplace_back(std::forward<_Args>(__args)...); 518 std::push_heap(c.begin(), c.end(), comp); 519 } 520#endif 521 522 /** 523 * @brief Removes first element. 524 * 525 * This is a typical %queue operation. It shrinks the %queue 526 * by one. The time complexity of the operation depends on the 527 * underlying sequence. 528 * 529 * Note that no data is returned, and if the first element's 530 * data is needed, it should be retrieved before pop() is 531 * called. 532 */ 533 void 534 pop() 535 { 536 __glibcxx_requires_nonempty(); 537 std::pop_heap(c.begin(), c.end(), comp); 538 c.pop_back(); 539 } 540 541#ifdef __GXX_EXPERIMENTAL_CXX0X__ 542 void 543 swap(priority_queue& __pq) 544 { 545 using std::swap; 546 c.swap(__pq.c); 547 swap(comp, __pq.comp); 548 } 549#endif 550 }; 551 552 // No equality/comparison operators are provided for priority_queue. 553 554#ifdef __GXX_EXPERIMENTAL_CXX0X__ 555 template<typename _Tp, typename _Sequence, typename _Compare> 556 inline void 557 swap(priority_queue<_Tp, _Sequence, _Compare>& __x, 558 priority_queue<_Tp, _Sequence, _Compare>& __y) 559 { __x.swap(__y); } 560#endif 561 562_GLIBCXX_END_NAMESPACE 563 564#endif /* _STL_QUEUE_H */ 565