1 // Queue implementation -*- C++ -*- 2 3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 4 // Free Software Foundation, Inc. 5 // 6 // This file is part of the GNU ISO C++ Library. This library is free 7 // software; you can redistribute it and/or modify it under the 8 // terms of the GNU General Public License as published by the 9 // Free Software Foundation; either version 2, or (at your option) 10 // any later version. 11 12 // This library is distributed in the hope that it will be useful, 13 // but WITHOUT ANY WARRANTY; without even the implied warranty of 14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 // GNU General Public License for more details. 16 17 // You should have received a copy of the GNU General Public License along 18 // with this library; see the file COPYING. If not, write to the Free 19 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 20 // USA. 21 22 // As a special exception, you may use this file as part of a free software 23 // library without restriction. Specifically, if other files instantiate 24 // templates or use macros or inline functions from this file, or you compile 25 // this file and link it with other files to produce an executable, this 26 // file does not by itself cause the resulting executable to be covered by 27 // the GNU General Public License. This exception does not however 28 // invalidate any other reasons why the executable file might be covered by 29 // the GNU General Public License. 30 31 /* 32 * 33 * Copyright (c) 1994 34 * Hewlett-Packard Company 35 * 36 * Permission to use, copy, modify, distribute and sell this software 37 * and its documentation for any purpose is hereby granted without fee, 38 * provided that the above copyright notice appear in all copies and 39 * that both that copyright notice and this permission notice appear 40 * in supporting documentation. Hewlett-Packard Company makes no 41 * representations about the suitability of this software for any 42 * purpose. It is provided "as is" without express or implied warranty. 43 * 44 * 45 * Copyright (c) 1996,1997 46 * Silicon Graphics Computer Systems, Inc. 47 * 48 * Permission to use, copy, modify, distribute and sell this software 49 * and its documentation for any purpose is hereby granted without fee, 50 * provided that the above copyright notice appear in all copies and 51 * that both that copyright notice and this permission notice appear 52 * in supporting documentation. Silicon Graphics makes no 53 * representations about the suitability of this software for any 54 * purpose. It is provided "as is" without express or implied warranty. 55 */ 56 57 /** @file stl_queue.h 58 * This is an internal header file, included by other library headers. 59 * You should not attempt to use it directly. 60 */ 61 62 #ifndef _QUEUE_H 63 #define _QUEUE_H 1 64 65 #include <bits/concept_check.h> 66 #include <debug/debug.h> 67 68 _GLIBCXX_BEGIN_NAMESPACE(std) 69 70 /** 71 * @brief A standard container giving FIFO behavior. 72 * 73 * @ingroup Containers 74 * @ingroup Sequences 75 * 76 * Meets many of the requirements of a 77 * <a href="tables.html#65">container</a>, 78 * but does not define anything to do with iterators. Very few of the 79 * other standard container interfaces are defined. 80 * 81 * This is not a true container, but an @e adaptor. It holds another 82 * container, and provides a wrapper interface to that container. The 83 * wrapper is what enforces strict first-in-first-out %queue behavior. 84 * 85 * The second template parameter defines the type of the underlying 86 * sequence/container. It defaults to std::deque, but it can be any type 87 * that supports @c front, @c back, @c push_back, and @c pop_front, 88 * such as std::list or an appropriate user-defined type. 89 * 90 * Members not found in "normal" containers are @c container_type, 91 * which is a typedef for the second Sequence parameter, and @c push and 92 * @c pop, which are standard %queue/FIFO operations. 93 */ 94 template<typename _Tp, typename _Sequence = deque<_Tp> > 95 class queue 96 { 97 // concept requirements 98 typedef typename _Sequence::value_type _Sequence_value_type; 99 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 100 __glibcxx_class_requires(_Sequence, _FrontInsertionSequenceConcept) 101 __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept) 102 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept) 103 104 template<typename _Tp1, typename _Seq1> 105 friend bool 106 operator==(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&); 107 108 template<typename _Tp1, typename _Seq1> 109 friend bool 110 operator<(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&); 111 112 public: 113 typedef typename _Sequence::value_type value_type; 114 typedef typename _Sequence::reference reference; 115 typedef typename _Sequence::const_reference const_reference; 116 typedef typename _Sequence::size_type size_type; 117 typedef _Sequence container_type; 118 119 protected: 120 /** 121 * 'c' is the underlying container. Maintainers wondering why 122 * this isn't uglified as per style guidelines should note that 123 * this name is specified in the standard, [23.2.3.1]. (Why? 124 * Presumably for the same reason that it's protected instead 125 * of private: to allow derivation. But none of the other 126 * containers allow for derivation. Odd.) 127 */ 128 _Sequence c; 129 130 public: 131 /** 132 * @brief Default constructor creates no elements. 133 */ 134 explicit 135 queue(const _Sequence& __c = _Sequence()) : c(__c) {} 136 137 /** 138 * Returns true if the %queue is empty. 139 */ 140 bool 141 empty() const 142 { return c.empty(); } 143 144 /** Returns the number of elements in the %queue. */ 145 size_type 146 size() const 147 { return c.size(); } 148 149 /** 150 * Returns a read/write reference to the data at the first 151 * element of the %queue. 152 */ 153 reference 154 front() 155 { 156 __glibcxx_requires_nonempty(); 157 return c.front(); 158 } 159 160 /** 161 * Returns a read-only (constant) reference to the data at the first 162 * element of the %queue. 163 */ 164 const_reference 165 front() const 166 { 167 __glibcxx_requires_nonempty(); 168 return c.front(); 169 } 170 171 /** 172 * Returns a read/write reference to the data at the last 173 * element of the %queue. 174 */ 175 reference 176 back() 177 { 178 __glibcxx_requires_nonempty(); 179 return c.back(); 180 } 181 182 /** 183 * Returns a read-only (constant) reference to the data at the last 184 * element of the %queue. 185 */ 186 const_reference 187 back() const 188 { 189 __glibcxx_requires_nonempty(); 190 return c.back(); 191 } 192 193 /** 194 * @brief Add data to the end of the %queue. 195 * @param x Data to be added. 196 * 197 * This is a typical %queue operation. The function creates an 198 * element at the end of the %queue and assigns the given data 199 * to it. The time complexity of the operation depends on the 200 * underlying sequence. 201 */ 202 void 203 push(const value_type& __x) 204 { c.push_back(__x); } 205 206 /** 207 * @brief Removes first element. 208 * 209 * This is a typical %queue operation. It shrinks the %queue by one. 210 * The time complexity of the operation depends on the underlying 211 * sequence. 212 * 213 * Note that no data is returned, and if the first element's 214 * data is needed, it should be retrieved before pop() is 215 * called. 216 */ 217 void 218 pop() 219 { 220 __glibcxx_requires_nonempty(); 221 c.pop_front(); 222 } 223 }; 224 225 226 /** 227 * @brief Queue equality comparison. 228 * @param x A %queue. 229 * @param y A %queue of the same type as @a x. 230 * @return True iff the size and elements of the queues are equal. 231 * 232 * This is an equivalence relation. Complexity and semantics depend on the 233 * underlying sequence type, but the expected rules are: this relation is 234 * linear in the size of the sequences, and queues are considered equivalent 235 * if their sequences compare equal. 236 */ 237 template<typename _Tp, typename _Seq> 238 inline bool 239 operator==(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 240 { return __x.c == __y.c; } 241 242 /** 243 * @brief Queue ordering relation. 244 * @param x A %queue. 245 * @param y A %queue of the same type as @a x. 246 * @return True iff @a x is lexicographically less than @a y. 247 * 248 * This is an total ordering relation. Complexity and semantics 249 * depend on the underlying sequence type, but the expected rules 250 * are: this relation is linear in the size of the sequences, the 251 * elements must be comparable with @c <, and 252 * std::lexicographical_compare() is usually used to make the 253 * determination. 254 */ 255 template<typename _Tp, typename _Seq> 256 inline bool 257 operator<(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 258 { return __x.c < __y.c; } 259 260 /// Based on operator== 261 template<typename _Tp, typename _Seq> 262 inline bool 263 operator!=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 264 { return !(__x == __y); } 265 266 /// Based on operator< 267 template<typename _Tp, typename _Seq> 268 inline bool 269 operator>(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 270 { return __y < __x; } 271 272 /// Based on operator< 273 template<typename _Tp, typename _Seq> 274 inline bool 275 operator<=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 276 { return !(__y < __x); } 277 278 /// Based on operator< 279 template<typename _Tp, typename _Seq> 280 inline bool 281 operator>=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 282 { return !(__x < __y); } 283 284 /** 285 * @brief A standard container automatically sorting its contents. 286 * 287 * @ingroup Containers 288 * @ingroup Sequences 289 * 290 * This is not a true container, but an @e adaptor. It holds 291 * another container, and provides a wrapper interface to that 292 * container. The wrapper is what enforces priority-based sorting 293 * and %queue behavior. Very few of the standard container/sequence 294 * interface requirements are met (e.g., iterators). 295 * 296 * The second template parameter defines the type of the underlying 297 * sequence/container. It defaults to std::vector, but it can be 298 * any type that supports @c front(), @c push_back, @c pop_back, 299 * and random-access iterators, such as std::deque or an 300 * appropriate user-defined type. 301 * 302 * The third template parameter supplies the means of making 303 * priority comparisons. It defaults to @c less<value_type> but 304 * can be anything defining a strict weak ordering. 305 * 306 * Members not found in "normal" containers are @c container_type, 307 * which is a typedef for the second Sequence parameter, and @c 308 * push, @c pop, and @c top, which are standard %queue operations. 309 * 310 * @note No equality/comparison operators are provided for 311 * %priority_queue. 312 * 313 * @note Sorting of the elements takes place as they are added to, 314 * and removed from, the %priority_queue using the 315 * %priority_queue's member functions. If you access the elements 316 * by other means, and change their data such that the sorting 317 * order would be different, the %priority_queue will not re-sort 318 * the elements for you. (How could it know to do so?) 319 */ 320 template<typename _Tp, typename _Sequence = vector<_Tp>, 321 typename _Compare = less<typename _Sequence::value_type> > 322 class priority_queue 323 { 324 // concept requirements 325 typedef typename _Sequence::value_type _Sequence_value_type; 326 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 327 __glibcxx_class_requires(_Sequence, _SequenceConcept) 328 __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept) 329 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept) 330 __glibcxx_class_requires4(_Compare, bool, _Tp, _Tp, 331 _BinaryFunctionConcept) 332 333 public: 334 typedef typename _Sequence::value_type value_type; 335 typedef typename _Sequence::reference reference; 336 typedef typename _Sequence::const_reference const_reference; 337 typedef typename _Sequence::size_type size_type; 338 typedef _Sequence container_type; 339 340 protected: 341 // See queue::c for notes on these names. 342 _Sequence c; 343 _Compare comp; 344 345 public: 346 /** 347 * @brief Default constructor creates no elements. 348 */ 349 explicit 350 priority_queue(const _Compare& __x = _Compare(), 351 const _Sequence& __s = _Sequence()) 352 : c(__s), comp(__x) 353 { std::make_heap(c.begin(), c.end(), comp); } 354 355 /** 356 * @brief Builds a %queue from a range. 357 * @param first An input iterator. 358 * @param last An input iterator. 359 * @param x A comparison functor describing a strict weak ordering. 360 * @param s An initial sequence with which to start. 361 * 362 * Begins by copying @a s, inserting a copy of the elements 363 * from @a [first,last) into the copy of @a s, then ordering 364 * the copy according to @a x. 365 * 366 * For more information on function objects, see the 367 * documentation on @link s20_3_1_base functor base 368 * classes@endlink. 369 */ 370 template<typename _InputIterator> 371 priority_queue(_InputIterator __first, _InputIterator __last, 372 const _Compare& __x = _Compare(), 373 const _Sequence& __s = _Sequence()) 374 : c(__s), comp(__x) 375 { 376 __glibcxx_requires_valid_range(__first, __last); 377 c.insert(c.end(), __first, __last); 378 std::make_heap(c.begin(), c.end(), comp); 379 } 380 381 /** 382 * Returns true if the %queue is empty. 383 */ 384 bool 385 empty() const 386 { return c.empty(); } 387 388 /** Returns the number of elements in the %queue. */ 389 size_type 390 size() const 391 { return c.size(); } 392 393 /** 394 * Returns a read-only (constant) reference to the data at the first 395 * element of the %queue. 396 */ 397 const_reference 398 top() const 399 { 400 __glibcxx_requires_nonempty(); 401 return c.front(); 402 } 403 404 /** 405 * @brief Add data to the %queue. 406 * @param x Data to be added. 407 * 408 * This is a typical %queue operation. 409 * The time complexity of the operation depends on the underlying 410 * sequence. 411 */ 412 void 413 push(const value_type& __x) 414 { 415 c.push_back(__x); 416 std::push_heap(c.begin(), c.end(), comp); 417 } 418 419 /** 420 * @brief Removes first element. 421 * 422 * This is a typical %queue operation. It shrinks the %queue 423 * by one. The time complexity of the operation depends on the 424 * underlying sequence. 425 * 426 * Note that no data is returned, and if the first element's 427 * data is needed, it should be retrieved before pop() is 428 * called. 429 */ 430 void 431 pop() 432 { 433 __glibcxx_requires_nonempty(); 434 std::pop_heap(c.begin(), c.end(), comp); 435 c.pop_back(); 436 } 437 }; 438 439 // No equality/comparison operators are provided for priority_queue. 440 441 _GLIBCXX_END_NAMESPACE 442 443 #endif /* _QUEUE_H */ 444