1 // Queue implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002 Free Software Foundation, Inc.
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)
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.
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,
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.
33 * Hewlett-Packard Company
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.
44 * Copyright (c) 1996,1997
45 * Silicon Graphics Computer Systems, Inc.
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.
57 * This is an internal header file, included by other library headers.
58 * You should not attempt to use it directly.
61 #ifndef __GLIBCPP_INTERNAL_QUEUE_H
62 #define __GLIBCPP_INTERNAL_QUEUE_H
64 #include <bits/concept_check.h>
68 // Forward declarations of operators < and ==, needed for friend declaration.
70 template <typename _Tp
, typename _Sequence
= deque
<_Tp
> >
73 template <typename _Tp
, typename _Seq
>
74 inline bool operator==(const queue
<_Tp
,_Seq
>&, const queue
<_Tp
,_Seq
>&);
76 template <typename _Tp
, typename _Seq
>
77 inline bool operator<(const queue
<_Tp
,_Seq
>&, const queue
<_Tp
,_Seq
>&);
81 * @brief A standard container giving FIFO behavior.
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.
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.
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.
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.
104 template <typename _Tp
, typename _Sequence
>
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
)
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
>&);
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
;
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.)
140 * @brief Default constructor creates no elements.
143 queue(const _Sequence
& __c
= _Sequence())
147 * Returns true if the %queue is empty.
150 empty() const { return c
.empty(); }
152 /** Returns the number of elements in the %queue. */
154 size() const { return c
.size(); }
157 * Returns a read/write reference to the data at the first element of the
161 front() { return c
.front(); }
164 * Returns a read-only (constant) reference to the data at the first
165 * element of the %queue.
168 front() const { return c
.front(); }
171 * Returns a read/write reference to the data at the last element of the
175 back() { return c
.back(); }
178 * Returns a read-only (constant) reference to the data at the last
179 * element of the %queue.
182 back() const { return c
.back(); }
185 * @brief Add data to the end of the %queue.
186 * @param x Data to be added.
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
194 push(const value_type
& __x
) { c
.push_back(__x
); }
197 * @brief Removes first element.
199 * This is a typical %queue operation. It shrinks the %queue by one.
200 * The time complexity of the operation depends on the underlying
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.
207 pop() { c
.pop_front(); }
212 * @brief Queue equality comparison.
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.
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.
222 template <typename _Tp
, typename _Sequence
>
224 operator==(const queue
<_Tp
,_Sequence
>& __x
, const queue
<_Tp
,_Sequence
>& __y
)
225 { return __x
.c
== __y
.c
; }
228 * @brief Queue ordering relation.
230 * @param y A %queue of the same type as @a x.
231 * @return True iff @a x is lexographically less than @a y.
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
239 template <typename _Tp
, typename _Sequence
>
241 operator<(const queue
<_Tp
,_Sequence
>& __x
, const queue
<_Tp
,_Sequence
>& __y
)
242 { return __x
.c
< __y
.c
; }
244 /// Based on operator==
245 template <typename _Tp
, typename _Sequence
>
247 operator!=(const queue
<_Tp
,_Sequence
>& __x
, const queue
<_Tp
,_Sequence
>& __y
)
248 { return !(__x
== __y
); }
250 /// Based on operator<
251 template <typename _Tp
, typename _Sequence
>
253 operator>(const queue
<_Tp
,_Sequence
>& __x
, const queue
<_Tp
,_Sequence
>& __y
)
254 { return __y
< __x
; }
256 /// Based on operator<
257 template <typename _Tp
, typename _Sequence
>
259 operator<=(const queue
<_Tp
,_Sequence
>& __x
, const queue
<_Tp
,_Sequence
>& __y
)
260 { return !(__y
< __x
); }
262 /// Based on operator<
263 template <typename _Tp
, typename _Sequence
>
265 operator>=(const queue
<_Tp
,_Sequence
>& __x
, const queue
<_Tp
,_Sequence
>& __y
)
266 { return !(__x
< __y
); }
270 * @brief A standard container automatically sorting its contents.
272 * @ingroup Containers
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).
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.
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.
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.
294 * @note No equality/comparison operators are provided for %priority_queue.
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?)
303 template <typename _Tp
, typename _Sequence
= vector
<_Tp
>,
304 typename _Compare
= less
<typename
_Sequence::value_type
> >
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
)
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
;
323 // See queue::c for notes on these names.
329 * @brief Default constructor creates no elements.
332 priority_queue(const _Compare
& __x
= _Compare(),
333 const _Sequence
& __s
= _Sequence())
335 { make_heap(c
.begin(), c
.end(), comp
); }
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.
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
348 * For more information on function objects, see the documentation on
349 * @link s20_3_1_base functor base classes@endlink.
351 template <typename _InputIterator
>
352 priority_queue(_InputIterator __first
, _InputIterator __last
,
353 const _Compare
& __x
= _Compare(),
354 const _Sequence
& __s
= _Sequence())
357 c
.insert(c
.end(), __first
, __last
);
358 make_heap(c
.begin(), c
.end(), comp
);
362 * Returns true if the %queue is empty.
365 empty() const { return c
.empty(); }
367 /** Returns the number of elements in the %queue. */
369 size() const { return c
.size(); }
372 * Returns a read-only (constant) reference to the data at the first
373 * element of the %queue.
376 top() const { return c
.front(); }
379 * @brief Add data to the %queue.
380 * @param x Data to be added.
382 * This is a typical %queue operation.
383 * The time complexity of the operation depends on the underlying
387 push(const value_type
& __x
)
392 push_heap(c
.begin(), c
.end(), comp
);
397 __throw_exception_again
;
402 * @brief Removes first element.
404 * This is a typical %queue operation. It shrinks the %queue by one.
405 * The time complexity of the operation depends on the underlying
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.
416 pop_heap(c
.begin(), c
.end(), comp
);
422 __throw_exception_again
;
427 // No equality/comparison operators are provided for priority_queue.
430 #endif /* __GLIBCPP_INTERNAL_QUEUE_H */