1 // Queue implementation -*- C++ -*- 2 3 // Copyright (C) 2001, 2002 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 __GLIBCPP_INTERNAL_QUEUE_H 62 #define __GLIBCPP_INTERNAL_QUEUE_H 63 64 #include <bits/concept_check.h> 65 66 namespace std 67 { 68 // Forward declarations of operators < and ==, needed for friend declaration. 69 70 template <typename _Tp, typename _Sequence = deque<_Tp> > 71 class queue; 72 73 template <typename _Tp, typename _Seq> 74 inline bool operator==(const queue<_Tp,_Seq>&, const queue<_Tp,_Seq>&); 75 76 template <typename _Tp, typename _Seq> 77 inline bool operator<(const queue<_Tp,_Seq>&, const queue<_Tp,_Seq>&); 78 79 80 /** 81 * @brief A standard container giving FIFO behavior. 82 * 83 * @ingroup Containers 84 * @ingroup Sequences 85 * 86 * Meets many of the requirements of a 87 * <a href="tables.html#65">container</a>, 88 * but does not define anything to do with iterators. Very few of the 89 * other standard container interfaces are defined. 90 * 91 * This is not a true container, but an @e adaptor. It holds another 92 * container, and provides a wrapper interface to that container. The 93 * wrapper is what enforces strict first-in-first-out %queue behavior. 94 * 95 * The second template parameter defines the type of the underlying 96 * sequence/container. It defaults to std::deque, but it can be any type 97 * that supports @c front, @c back, @c push_back, and @c pop_front, 98 * such as std::list or an appropriate user-defined type. 99 * 100 * Members not found in "normal" containers are @c container_type, 101 * which is a typedef for the second Sequence parameter, and @c push and 102 * @c pop, which are standard %queue/FIFO operations. 103 */ 104 template <typename _Tp, typename _Sequence> 105 class queue 106 { 107 // concept requirements 108 typedef typename _Sequence::value_type _Sequence_value_type; 109 __glibcpp_class_requires(_Tp, _SGIAssignableConcept) 110 __glibcpp_class_requires(_Sequence, _FrontInsertionSequenceConcept) 111 __glibcpp_class_requires(_Sequence, _BackInsertionSequenceConcept) 112 __glibcpp_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept) 113 114 template <typename _Tp1, typename _Seq1> 115 friend bool operator== (const queue<_Tp1, _Seq1>&, 116 const queue<_Tp1, _Seq1>&); 117 template <typename _Tp1, typename _Seq1> 118 friend bool operator< (const queue<_Tp1, _Seq1>&, 119 const queue<_Tp1, _Seq1>&); 120 121 public: 122 typedef typename _Sequence::value_type value_type; 123 typedef typename _Sequence::reference reference; 124 typedef typename _Sequence::const_reference const_reference; 125 typedef typename _Sequence::size_type size_type; 126 typedef _Sequence container_type; 127 128 protected: 129 /** 130 * 'c' is the underlying container. Maintainers wondering why this isn't 131 * uglified as per style guidelines should note that this name is 132 * specified in the standard, [23.2.3.1]. (Why? Presumably for the same 133 * reason that it's protected instead of private: to allow derivation. 134 * But none of the other containers allow for derivation. Odd.) 135 */ 136 _Sequence c; 137 138 public: 139 /** 140 * @brief Default constructor creates no elements. 141 */ 142 explicit 143 queue(const _Sequence& __c = _Sequence()) c(__c)144 : c(__c) {} 145 146 /** 147 * Returns true if the %queue is empty. 148 */ 149 bool empty()150 empty() const { return c.empty(); } 151 152 /** Returns the number of elements in the %queue. */ 153 size_type size()154 size() const { return c.size(); } 155 156 /** 157 * Returns a read/write reference to the data at the first element of the 158 * %queue. 159 */ 160 reference front()161 front() { return c.front(); } 162 163 /** 164 * Returns a read-only (constant) reference to the data at the first 165 * element of the %queue. 166 */ 167 const_reference front()168 front() const { return c.front(); } 169 170 /** 171 * Returns a read/write reference to the data at the last element of the 172 * %queue. 173 */ 174 reference back()175 back() { return c.back(); } 176 177 /** 178 * Returns a read-only (constant) reference to the data at the last 179 * element of the %queue. 180 */ 181 const_reference back()182 back() const { return c.back(); } 183 184 /** 185 * @brief Add data to the end of the %queue. 186 * @param x Data to be added. 187 * 188 * This is a typical %queue operation. The function creates an element at 189 * the end of the %queue and assigns the given data to it. 190 * The time complexity of the operation depends on the underlying 191 * sequence. 192 */ 193 void push(const value_type & __x)194 push(const value_type& __x) { c.push_back(__x); } 195 196 /** 197 * @brief Removes first element. 198 * 199 * This is a typical %queue operation. It shrinks the %queue by one. 200 * The time complexity of the operation depends on the underlying 201 * sequence. 202 * 203 * Note that no data is returned, and if the first element's data is 204 * needed, it should be retrieved before pop() is called. 205 */ 206 void pop()207 pop() { c.pop_front(); } 208 }; 209 210 211 /** 212 * @brief Queue equality comparison. 213 * @param x A %queue. 214 * @param y A %queue of the same type as @a x. 215 * @return True iff the size and elements of the queues are equal. 216 * 217 * This is an equivalence relation. Complexity and semantics depend on the 218 * underlying sequence type, but the expected rules are: this relation is 219 * linear in the size of the sequences, and queues are considered equivalent 220 * if their sequences compare equal. 221 */ 222 template <typename _Tp, typename _Sequence> 223 inline bool 224 operator==(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y) 225 { return __x.c == __y.c; } 226 227 /** 228 * @brief Queue ordering relation. 229 * @param x A %queue. 230 * @param y A %queue of the same type as @a x. 231 * @return True iff @a x is lexographically less than @a y. 232 * 233 * This is an total ordering relation. Complexity and semantics depend on 234 * the underlying sequence type, but the expected rules are: this relation 235 * is linear in the size of the sequences, the elements must be comparable 236 * with @c <, and std::lexographical_compare() is usually used to make the 237 * determination. 238 */ 239 template <typename _Tp, typename _Sequence> 240 inline bool 241 operator<(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y) 242 { return __x.c < __y.c; } 243 244 /// Based on operator== 245 template <typename _Tp, typename _Sequence> 246 inline bool 247 operator!=(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y) 248 { return !(__x == __y); } 249 250 /// Based on operator< 251 template <typename _Tp, typename _Sequence> 252 inline bool 253 operator>(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y) 254 { return __y < __x; } 255 256 /// Based on operator< 257 template <typename _Tp, typename _Sequence> 258 inline bool 259 operator<=(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y) 260 { return !(__y < __x); } 261 262 /// Based on operator< 263 template <typename _Tp, typename _Sequence> 264 inline bool 265 operator>=(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y) 266 { return !(__x < __y); } 267 268 269 /** 270 * @brief A standard container automatically sorting its contents. 271 * 272 * @ingroup Containers 273 * @ingroup Sequences 274 * 275 * This is not a true container, but an @e adaptor. It holds another 276 * container, and provides a wrapper interface to that container. The 277 * wrapper is what enforces sorting and first-in-first-out %queue behavior. 278 * Very few of the standard container/sequence interface requirements are 279 * met (e.g., iterators). 280 * 281 * The second template parameter defines the type of the underlying 282 * sequence/container. It defaults to std::vector, but it can be any type 283 * that supports @c front(), @c push_back, @c pop_back, and random-access 284 * iterators, such as std::deque or an appropriate user-defined type. 285 * 286 * The third template parameter supplies the means of making priority 287 * comparisons. It defaults to @c less<value_type> but can be anything 288 * defining a strict weak ordering. 289 * 290 * Members not found in "normal" containers are @c container_type, 291 * which is a typedef for the second Sequence parameter, and @c push, 292 * @c pop, and @c top, which are standard %queue/FIFO operations. 293 * 294 * @note No equality/comparison operators are provided for %priority_queue. 295 * 296 * @note Sorting of the elements takes place as they are added to, and 297 * removed from, the %priority_queue using the %priority_queue's 298 * member functions. If you access the elements by other means, and 299 * change their data such that the sorting order would be different, 300 * the %priority_queue will not re-sort the elements for you. (How 301 * could it know to do so?) 302 */ 303 template <typename _Tp, typename _Sequence = vector<_Tp>, 304 typename _Compare = less<typename _Sequence::value_type> > 305 class priority_queue 306 { 307 // concept requirements 308 typedef typename _Sequence::value_type _Sequence_value_type; 309 __glibcpp_class_requires(_Tp, _SGIAssignableConcept) 310 __glibcpp_class_requires(_Sequence, _SequenceConcept) 311 __glibcpp_class_requires(_Sequence, _RandomAccessContainerConcept) 312 __glibcpp_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept) 313 __glibcpp_class_requires4(_Compare, bool, _Tp, _Tp, _BinaryFunctionConcept) 314 315 public: 316 typedef typename _Sequence::value_type value_type; 317 typedef typename _Sequence::reference reference; 318 typedef typename _Sequence::const_reference const_reference; 319 typedef typename _Sequence::size_type size_type; 320 typedef _Sequence container_type; 321 322 protected: 323 // See queue::c for notes on these names. 324 _Sequence c; 325 _Compare comp; 326 327 public: 328 /** 329 * @brief Default constructor creates no elements. 330 */ 331 explicit 332 priority_queue(const _Compare& __x = _Compare(), 333 const _Sequence& __s = _Sequence()) c(__s)334 : c(__s), comp(__x) 335 { make_heap(c.begin(), c.end(), comp); } 336 337 /** 338 * @brief Builds a %queue from a range. 339 * @param first An input iterator. 340 * @param last An input iterator. 341 * @param x A comparison functor describing a strict weak ordering. 342 * @param s An initial sequence with which to start. 343 * 344 * Begins by copying @a s, inserting a copy of the elements from 345 * @a [first,last) into the copy of @a s, then ordering the copy 346 * according to @a x. 347 * 348 * For more information on function objects, see the documentation on 349 * @link s20_3_1_base functor base classes@endlink. 350 */ 351 template <typename _InputIterator> 352 priority_queue(_InputIterator __first, _InputIterator __last, 353 const _Compare& __x = _Compare(), 354 const _Sequence& __s = _Sequence()) c(__s)355 : c(__s), comp(__x) 356 { 357 c.insert(c.end(), __first, __last); 358 make_heap(c.begin(), c.end(), comp); 359 } 360 361 /** 362 * Returns true if the %queue is empty. 363 */ 364 bool empty()365 empty() const { return c.empty(); } 366 367 /** Returns the number of elements in the %queue. */ 368 size_type size()369 size() const { return c.size(); } 370 371 /** 372 * Returns a read-only (constant) reference to the data at the first 373 * element of the %queue. 374 */ 375 const_reference top()376 top() const { return c.front(); } 377 378 /** 379 * @brief Add data to the %queue. 380 * @param x Data to be added. 381 * 382 * This is a typical %queue operation. 383 * The time complexity of the operation depends on the underlying 384 * sequence. 385 */ 386 void push(const value_type & __x)387 push(const value_type& __x) 388 { 389 try 390 { 391 c.push_back(__x); 392 push_heap(c.begin(), c.end(), comp); 393 } 394 catch(...) 395 { 396 c.clear(); 397 __throw_exception_again; 398 } 399 } 400 401 /** 402 * @brief Removes first element. 403 * 404 * This is a typical %queue operation. It shrinks the %queue by one. 405 * The time complexity of the operation depends on the underlying 406 * sequence. 407 * 408 * Note that no data is returned, and if the first element's data is 409 * needed, it should be retrieved before pop() is called. 410 */ 411 void pop()412 pop() 413 { 414 try 415 { 416 pop_heap(c.begin(), c.end(), comp); 417 c.pop_back(); 418 } 419 catch(...) 420 { 421 c.clear(); 422 __throw_exception_again; 423 } 424 } 425 }; 426 427 // No equality/comparison operators are provided for priority_queue. 428 } // namespace std 429 430 #endif /* __GLIBCPP_INTERNAL_QUEUE_H */ 431