197403Sobrien// Queue implementation -*- C++ -*- 297403Sobrien 3169691Skan// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 4169691Skan// Free Software Foundation, Inc. 597403Sobrien// 697403Sobrien// This file is part of the GNU ISO C++ Library. This library is free 797403Sobrien// software; you can redistribute it and/or modify it under the 897403Sobrien// terms of the GNU General Public License as published by the 997403Sobrien// Free Software Foundation; either version 2, or (at your option) 1097403Sobrien// any later version. 1197403Sobrien 1297403Sobrien// This library is distributed in the hope that it will be useful, 1397403Sobrien// but WITHOUT ANY WARRANTY; without even the implied warranty of 1497403Sobrien// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1597403Sobrien// GNU General Public License for more details. 1697403Sobrien 1797403Sobrien// You should have received a copy of the GNU General Public License along 1897403Sobrien// with this library; see the file COPYING. If not, write to the Free 19169691Skan// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 2097403Sobrien// USA. 2197403Sobrien 2297403Sobrien// As a special exception, you may use this file as part of a free software 2397403Sobrien// library without restriction. Specifically, if other files instantiate 2497403Sobrien// templates or use macros or inline functions from this file, or you compile 2597403Sobrien// this file and link it with other files to produce an executable, this 2697403Sobrien// file does not by itself cause the resulting executable to be covered by 2797403Sobrien// the GNU General Public License. This exception does not however 2897403Sobrien// invalidate any other reasons why the executable file might be covered by 2997403Sobrien// the GNU General Public License. 3097403Sobrien 3197403Sobrien/* 3297403Sobrien * 3397403Sobrien * Copyright (c) 1994 3497403Sobrien * Hewlett-Packard Company 3597403Sobrien * 3697403Sobrien * Permission to use, copy, modify, distribute and sell this software 3797403Sobrien * and its documentation for any purpose is hereby granted without fee, 3897403Sobrien * provided that the above copyright notice appear in all copies and 3997403Sobrien * that both that copyright notice and this permission notice appear 4097403Sobrien * in supporting documentation. Hewlett-Packard Company makes no 4197403Sobrien * representations about the suitability of this software for any 4297403Sobrien * purpose. It is provided "as is" without express or implied warranty. 4397403Sobrien * 4497403Sobrien * 4597403Sobrien * Copyright (c) 1996,1997 4697403Sobrien * Silicon Graphics Computer Systems, Inc. 4797403Sobrien * 4897403Sobrien * Permission to use, copy, modify, distribute and sell this software 4997403Sobrien * and its documentation for any purpose is hereby granted without fee, 5097403Sobrien * provided that the above copyright notice appear in all copies and 5197403Sobrien * that both that copyright notice and this permission notice appear 5297403Sobrien * in supporting documentation. Silicon Graphics makes no 5397403Sobrien * representations about the suitability of this software for any 5497403Sobrien * purpose. It is provided "as is" without express or implied warranty. 5597403Sobrien */ 5697403Sobrien 5797403Sobrien/** @file stl_queue.h 5897403Sobrien * This is an internal header file, included by other library headers. 5997403Sobrien * You should not attempt to use it directly. 6097403Sobrien */ 6197403Sobrien 62132720Skan#ifndef _QUEUE_H 63132720Skan#define _QUEUE_H 1 6497403Sobrien 6597403Sobrien#include <bits/concept_check.h> 66132720Skan#include <debug/debug.h> 6797403Sobrien 68169691Skan_GLIBCXX_BEGIN_NAMESPACE(std) 69132720Skan 70117397Skan /** 71117397Skan * @brief A standard container giving FIFO behavior. 72117397Skan * 73117397Skan * @ingroup Containers 74117397Skan * @ingroup Sequences 75117397Skan * 76117397Skan * Meets many of the requirements of a 77117397Skan * <a href="tables.html#65">container</a>, 78117397Skan * but does not define anything to do with iterators. Very few of the 79117397Skan * other standard container interfaces are defined. 80117397Skan * 81117397Skan * This is not a true container, but an @e adaptor. It holds another 82117397Skan * container, and provides a wrapper interface to that container. The 83117397Skan * wrapper is what enforces strict first-in-first-out %queue behavior. 84117397Skan * 85117397Skan * The second template parameter defines the type of the underlying 86117397Skan * sequence/container. It defaults to std::deque, but it can be any type 87117397Skan * that supports @c front, @c back, @c push_back, and @c pop_front, 88117397Skan * such as std::list or an appropriate user-defined type. 89117397Skan * 90117397Skan * Members not found in "normal" containers are @c container_type, 91117397Skan * which is a typedef for the second Sequence parameter, and @c push and 92117397Skan * @c pop, which are standard %queue/FIFO operations. 93117397Skan */ 94169691Skan template<typename _Tp, typename _Sequence = deque<_Tp> > 95117397Skan class queue 96132720Skan { 97132720Skan // concept requirements 98132720Skan typedef typename _Sequence::value_type _Sequence_value_type; 99132720Skan __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 100132720Skan __glibcxx_class_requires(_Sequence, _FrontInsertionSequenceConcept) 101132720Skan __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept) 102132720Skan __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept) 103132720Skan 104132720Skan template<typename _Tp1, typename _Seq1> 105132720Skan friend bool 106132720Skan operator==(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&); 107132720Skan 108132720Skan template<typename _Tp1, typename _Seq1> 109132720Skan friend bool 110132720Skan operator<(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&); 111132720Skan 112132720Skan public: 113132720Skan typedef typename _Sequence::value_type value_type; 114132720Skan typedef typename _Sequence::reference reference; 115132720Skan typedef typename _Sequence::const_reference const_reference; 116132720Skan typedef typename _Sequence::size_type size_type; 117132720Skan typedef _Sequence container_type; 118132720Skan 119132720Skan protected: 120132720Skan /** 121132720Skan * 'c' is the underlying container. Maintainers wondering why 122132720Skan * this isn't uglified as per style guidelines should note that 123132720Skan * this name is specified in the standard, [23.2.3.1]. (Why? 124132720Skan * Presumably for the same reason that it's protected instead 125132720Skan * of private: to allow derivation. But none of the other 126132720Skan * containers allow for derivation. Odd.) 127132720Skan */ 128132720Skan _Sequence c; 129132720Skan 130132720Skan public: 131132720Skan /** 132132720Skan * @brief Default constructor creates no elements. 133132720Skan */ 134132720Skan explicit 135132720Skan queue(const _Sequence& __c = _Sequence()) : c(__c) {} 136132720Skan 137132720Skan /** 138132720Skan * Returns true if the %queue is empty. 139132720Skan */ 140132720Skan bool 141132720Skan empty() const 142132720Skan { return c.empty(); } 143132720Skan 144132720Skan /** Returns the number of elements in the %queue. */ 145132720Skan size_type 146132720Skan size() const 147132720Skan { return c.size(); } 148132720Skan 149132720Skan /** 150132720Skan * Returns a read/write reference to the data at the first 151132720Skan * element of the %queue. 152132720Skan */ 153132720Skan reference 154132720Skan front() 155132720Skan { 156132720Skan __glibcxx_requires_nonempty(); 157132720Skan return c.front(); 158132720Skan } 159132720Skan 160132720Skan /** 161132720Skan * Returns a read-only (constant) reference to the data at the first 162132720Skan * element of the %queue. 163132720Skan */ 164132720Skan const_reference 165132720Skan front() const 166132720Skan { 167132720Skan __glibcxx_requires_nonempty(); 168132720Skan return c.front(); 169132720Skan } 170132720Skan 171132720Skan /** 172132720Skan * Returns a read/write reference to the data at the last 173132720Skan * element of the %queue. 174132720Skan */ 175132720Skan reference 176132720Skan back() 177132720Skan { 178132720Skan __glibcxx_requires_nonempty(); 179132720Skan return c.back(); 180132720Skan } 181132720Skan 182132720Skan /** 183132720Skan * Returns a read-only (constant) reference to the data at the last 184132720Skan * element of the %queue. 185132720Skan */ 186132720Skan const_reference 187132720Skan back() const 188132720Skan { 189132720Skan __glibcxx_requires_nonempty(); 190132720Skan return c.back(); 191132720Skan } 192132720Skan 193132720Skan /** 194132720Skan * @brief Add data to the end of the %queue. 195132720Skan * @param x Data to be added. 196132720Skan * 197132720Skan * This is a typical %queue operation. The function creates an 198132720Skan * element at the end of the %queue and assigns the given data 199132720Skan * to it. The time complexity of the operation depends on the 200132720Skan * underlying sequence. 201132720Skan */ 202132720Skan void 203132720Skan push(const value_type& __x) 204132720Skan { c.push_back(__x); } 205132720Skan 206132720Skan /** 207132720Skan * @brief Removes first element. 208132720Skan * 209132720Skan * This is a typical %queue operation. It shrinks the %queue by one. 210132720Skan * The time complexity of the operation depends on the underlying 211132720Skan * sequence. 212132720Skan * 213132720Skan * Note that no data is returned, and if the first element's 214132720Skan * data is needed, it should be retrieved before pop() is 215132720Skan * called. 216132720Skan */ 217132720Skan void 218132720Skan pop() 219132720Skan { 220132720Skan __glibcxx_requires_nonempty(); 221132720Skan c.pop_front(); 222132720Skan } 223132720Skan }; 224132720Skan 225132720Skan 226117397Skan /** 227117397Skan * @brief Queue equality comparison. 228117397Skan * @param x A %queue. 229117397Skan * @param y A %queue of the same type as @a x. 230117397Skan * @return True iff the size and elements of the queues are equal. 231117397Skan * 232117397Skan * This is an equivalence relation. Complexity and semantics depend on the 233117397Skan * underlying sequence type, but the expected rules are: this relation is 234117397Skan * linear in the size of the sequences, and queues are considered equivalent 235117397Skan * if their sequences compare equal. 236117397Skan */ 237169691Skan template<typename _Tp, typename _Seq> 238132720Skan inline bool 239169691Skan operator==(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 240117397Skan { return __x.c == __y.c; } 241132720Skan 242117397Skan /** 243117397Skan * @brief Queue ordering relation. 244117397Skan * @param x A %queue. 245117397Skan * @param y A %queue of the same type as @a x. 246132720Skan * @return True iff @a x is lexicographically less than @a y. 247117397Skan * 248132720Skan * This is an total ordering relation. Complexity and semantics 249132720Skan * depend on the underlying sequence type, but the expected rules 250132720Skan * are: this relation is linear in the size of the sequences, the 251132720Skan * elements must be comparable with @c <, and 252132720Skan * std::lexicographical_compare() is usually used to make the 253117397Skan * determination. 254117397Skan */ 255169691Skan template<typename _Tp, typename _Seq> 256117397Skan inline bool 257169691Skan operator<(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 258117397Skan { return __x.c < __y.c; } 259132720Skan 260117397Skan /// Based on operator== 261169691Skan template<typename _Tp, typename _Seq> 262117397Skan inline bool 263169691Skan operator!=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 264117397Skan { return !(__x == __y); } 265132720Skan 266117397Skan /// Based on operator< 267169691Skan template<typename _Tp, typename _Seq> 268132720Skan inline bool 269169691Skan operator>(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 270117397Skan { return __y < __x; } 271132720Skan 272117397Skan /// Based on operator< 273169691Skan template<typename _Tp, typename _Seq> 274132720Skan inline bool 275169691Skan operator<=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 276117397Skan { return !(__y < __x); } 277132720Skan 278117397Skan /// Based on operator< 279169691Skan template<typename _Tp, typename _Seq> 280132720Skan inline bool 281169691Skan operator>=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 282117397Skan { return !(__x < __y); } 283132720Skan 284117397Skan /** 285117397Skan * @brief A standard container automatically sorting its contents. 286117397Skan * 287117397Skan * @ingroup Containers 288117397Skan * @ingroup Sequences 289117397Skan * 290132720Skan * This is not a true container, but an @e adaptor. It holds 291132720Skan * another container, and provides a wrapper interface to that 292169691Skan * container. The wrapper is what enforces priority-based sorting 293169691Skan * and %queue behavior. Very few of the standard container/sequence 294169691Skan * interface requirements are met (e.g., iterators). 295117397Skan * 296117397Skan * The second template parameter defines the type of the underlying 297132720Skan * sequence/container. It defaults to std::vector, but it can be 298132720Skan * any type that supports @c front(), @c push_back, @c pop_back, 299132720Skan * and random-access iterators, such as std::deque or an 300132720Skan * appropriate user-defined type. 301117397Skan * 302132720Skan * The third template parameter supplies the means of making 303132720Skan * priority comparisons. It defaults to @c less<value_type> but 304132720Skan * can be anything defining a strict weak ordering. 305117397Skan * 306117397Skan * Members not found in "normal" containers are @c container_type, 307132720Skan * which is a typedef for the second Sequence parameter, and @c 308169691Skan * push, @c pop, and @c top, which are standard %queue operations. 309117397Skan * 310132720Skan * @note No equality/comparison operators are provided for 311132720Skan * %priority_queue. 312117397Skan * 313132720Skan * @note Sorting of the elements takes place as they are added to, 314132720Skan * and removed from, the %priority_queue using the 315132720Skan * %priority_queue's member functions. If you access the elements 316132720Skan * by other means, and change their data such that the sorting 317132720Skan * order would be different, the %priority_queue will not re-sort 318132720Skan * the elements for you. (How could it know to do so?) 319117397Skan */ 320132720Skan template<typename _Tp, typename _Sequence = vector<_Tp>, 321132720Skan typename _Compare = less<typename _Sequence::value_type> > 322117397Skan class priority_queue 323132720Skan { 324132720Skan // concept requirements 325132720Skan typedef typename _Sequence::value_type _Sequence_value_type; 326132720Skan __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 327132720Skan __glibcxx_class_requires(_Sequence, _SequenceConcept) 328132720Skan __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept) 329132720Skan __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept) 330169691Skan __glibcxx_class_requires4(_Compare, bool, _Tp, _Tp, 331169691Skan _BinaryFunctionConcept) 332132720Skan 333132720Skan public: 334132720Skan typedef typename _Sequence::value_type value_type; 335132720Skan typedef typename _Sequence::reference reference; 336132720Skan typedef typename _Sequence::const_reference const_reference; 337132720Skan typedef typename _Sequence::size_type size_type; 338132720Skan typedef _Sequence container_type; 339132720Skan 340132720Skan protected: 341132720Skan // See queue::c for notes on these names. 342132720Skan _Sequence c; 343132720Skan _Compare comp; 344132720Skan 345132720Skan public: 346132720Skan /** 347132720Skan * @brief Default constructor creates no elements. 348132720Skan */ 349132720Skan explicit 350132720Skan priority_queue(const _Compare& __x = _Compare(), 351132720Skan const _Sequence& __s = _Sequence()) 352117397Skan : c(__s), comp(__x) 353132720Skan { std::make_heap(c.begin(), c.end(), comp); } 354132720Skan 355132720Skan /** 356132720Skan * @brief Builds a %queue from a range. 357132720Skan * @param first An input iterator. 358132720Skan * @param last An input iterator. 359132720Skan * @param x A comparison functor describing a strict weak ordering. 360132720Skan * @param s An initial sequence with which to start. 361132720Skan * 362132720Skan * Begins by copying @a s, inserting a copy of the elements 363132720Skan * from @a [first,last) into the copy of @a s, then ordering 364132720Skan * the copy according to @a x. 365132720Skan * 366132720Skan * For more information on function objects, see the 367132720Skan * documentation on @link s20_3_1_base functor base 368132720Skan * classes@endlink. 369132720Skan */ 370132720Skan template<typename _InputIterator> 371132720Skan priority_queue(_InputIterator __first, _InputIterator __last, 372132720Skan const _Compare& __x = _Compare(), 373132720Skan const _Sequence& __s = _Sequence()) 374132720Skan : c(__s), comp(__x) 375132720Skan { 376132720Skan __glibcxx_requires_valid_range(__first, __last); 377132720Skan c.insert(c.end(), __first, __last); 378132720Skan std::make_heap(c.begin(), c.end(), comp); 379132720Skan } 380132720Skan 381132720Skan /** 382132720Skan * Returns true if the %queue is empty. 383132720Skan */ 384132720Skan bool 385169691Skan empty() const 386169691Skan { return c.empty(); } 387132720Skan 388132720Skan /** Returns the number of elements in the %queue. */ 389132720Skan size_type 390169691Skan size() const 391169691Skan { return c.size(); } 392132720Skan 393132720Skan /** 394132720Skan * Returns a read-only (constant) reference to the data at the first 395132720Skan * element of the %queue. 396132720Skan */ 397132720Skan const_reference 398132720Skan top() const 399132720Skan { 400132720Skan __glibcxx_requires_nonempty(); 401132720Skan return c.front(); 40297403Sobrien } 403132720Skan 404132720Skan /** 405132720Skan * @brief Add data to the %queue. 406132720Skan * @param x Data to be added. 407132720Skan * 408132720Skan * This is a typical %queue operation. 409132720Skan * The time complexity of the operation depends on the underlying 410132720Skan * sequence. 411132720Skan */ 412132720Skan void 413132720Skan push(const value_type& __x) 414132720Skan { 415169691Skan c.push_back(__x); 416169691Skan std::push_heap(c.begin(), c.end(), comp); 417132720Skan } 418132720Skan 419132720Skan /** 420132720Skan * @brief Removes first element. 421132720Skan * 422132720Skan * This is a typical %queue operation. It shrinks the %queue 423132720Skan * by one. The time complexity of the operation depends on the 424132720Skan * underlying sequence. 425132720Skan * 426132720Skan * Note that no data is returned, and if the first element's 427132720Skan * data is needed, it should be retrieved before pop() is 428132720Skan * called. 429132720Skan */ 430132720Skan void 431132720Skan pop() 432132720Skan { 433132720Skan __glibcxx_requires_nonempty(); 434169691Skan std::pop_heap(c.begin(), c.end(), comp); 435169691Skan c.pop_back(); 436132720Skan } 437132720Skan }; 438132720Skan 439117397Skan // No equality/comparison operators are provided for priority_queue. 44097403Sobrien 441169691Skan_GLIBCXX_END_NAMESPACE 442169691Skan 443132720Skan#endif /* _QUEUE_H */ 444