Work around MinGW mangling of "host:/path"
[msysgit/historical-msysgit.git] / mingw / include / c++ / 3.4.2 / bits / stl_queue.h
blob3583547dbb4db2a668d06ac64f8a225a8bbcbcbf
1 // Queue implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004 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.
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,
19 // USA.
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.
32 * Copyright (c) 1994
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.
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.
61 #ifndef _QUEUE_H
62 #define _QUEUE_H 1
64 #include <bits/concept_check.h>
65 #include <debug/debug.h>
67 namespace std
69 // Forward declarations of operators < and ==, needed for friend declaration.
70 template<typename _Tp, typename _Sequence = deque<_Tp> >
71 class queue;
73 template<typename _Tp, typename _Seq>
74 inline bool
75 operator==(const queue<_Tp,_Seq>&, const queue<_Tp,_Seq>&);
77 template<typename _Tp, typename _Seq>
78 inline bool
79 operator<(const queue<_Tp,_Seq>&, const queue<_Tp,_Seq>&);
81 /**
82 * @brief A standard container giving FIFO behavior.
84 * @ingroup Containers
85 * @ingroup Sequences
87 * Meets many of the requirements of a
88 * <a href="tables.html#65">container</a>,
89 * but does not define anything to do with iterators. Very few of the
90 * other standard container interfaces are defined.
92 * This is not a true container, but an @e adaptor. It holds another
93 * container, and provides a wrapper interface to that container. The
94 * wrapper is what enforces strict first-in-first-out %queue behavior.
96 * The second template parameter defines the type of the underlying
97 * sequence/container. It defaults to std::deque, but it can be any type
98 * that supports @c front, @c back, @c push_back, and @c pop_front,
99 * such as std::list or an appropriate user-defined type.
101 * Members not found in "normal" containers are @c container_type,
102 * which is a typedef for the second Sequence parameter, and @c push and
103 * @c pop, which are standard %queue/FIFO operations.
105 template<typename _Tp, typename _Sequence>
106 class queue
108 // concept requirements
109 typedef typename _Sequence::value_type _Sequence_value_type;
110 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
111 __glibcxx_class_requires(_Sequence, _FrontInsertionSequenceConcept)
112 __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept)
113 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
115 template<typename _Tp1, typename _Seq1>
116 friend bool
117 operator==(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
119 template<typename _Tp1, typename _Seq1>
120 friend bool
121 operator<(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
123 public:
124 typedef typename _Sequence::value_type value_type;
125 typedef typename _Sequence::reference reference;
126 typedef typename _Sequence::const_reference const_reference;
127 typedef typename _Sequence::size_type size_type;
128 typedef _Sequence container_type;
130 protected:
132 * 'c' is the underlying container. Maintainers wondering why
133 * this isn't uglified as per style guidelines should note that
134 * this name is specified in the standard, [23.2.3.1]. (Why?
135 * Presumably for the same reason that it's protected instead
136 * of private: to allow derivation. But none of the other
137 * containers allow for derivation. Odd.)
139 _Sequence c;
141 public:
143 * @brief Default constructor creates no elements.
145 explicit
146 queue(const _Sequence& __c = _Sequence()) : c(__c) {}
149 * Returns true if the %queue is empty.
151 bool
152 empty() const
153 { return c.empty(); }
155 /** Returns the number of elements in the %queue. */
156 size_type
157 size() const
158 { return c.size(); }
161 * Returns a read/write reference to the data at the first
162 * element of the %queue.
164 reference
165 front()
167 __glibcxx_requires_nonempty();
168 return c.front();
172 * Returns a read-only (constant) reference to the data at the first
173 * element of the %queue.
175 const_reference
176 front() const
178 __glibcxx_requires_nonempty();
179 return c.front();
183 * Returns a read/write reference to the data at the last
184 * element of the %queue.
186 reference
187 back()
189 __glibcxx_requires_nonempty();
190 return c.back();
194 * Returns a read-only (constant) reference to the data at the last
195 * element of the %queue.
197 const_reference
198 back() const
200 __glibcxx_requires_nonempty();
201 return c.back();
205 * @brief Add data to the end of the %queue.
206 * @param x Data to be added.
208 * This is a typical %queue operation. The function creates an
209 * element at the end of the %queue and assigns the given data
210 * to it. The time complexity of the operation depends on the
211 * underlying sequence.
213 void
214 push(const value_type& __x)
215 { c.push_back(__x); }
218 * @brief Removes first element.
220 * This is a typical %queue operation. It shrinks the %queue by one.
221 * The time complexity of the operation depends on the underlying
222 * sequence.
224 * Note that no data is returned, and if the first element's
225 * data is needed, it should be retrieved before pop() is
226 * called.
228 void
229 pop()
231 __glibcxx_requires_nonempty();
232 c.pop_front();
238 * @brief Queue equality comparison.
239 * @param x A %queue.
240 * @param y A %queue of the same type as @a x.
241 * @return True iff the size and elements of the queues are equal.
243 * This is an equivalence relation. Complexity and semantics depend on the
244 * underlying sequence type, but the expected rules are: this relation is
245 * linear in the size of the sequences, and queues are considered equivalent
246 * if their sequences compare equal.
248 template<typename _Tp, typename _Sequence>
249 inline bool
250 operator==(const queue<_Tp,_Sequence>& __x,
251 const queue<_Tp,_Sequence>& __y)
252 { return __x.c == __y.c; }
255 * @brief Queue ordering relation.
256 * @param x A %queue.
257 * @param y A %queue of the same type as @a x.
258 * @return True iff @a x is lexicographically less than @a y.
260 * This is an total ordering relation. Complexity and semantics
261 * depend on the underlying sequence type, but the expected rules
262 * are: this relation is linear in the size of the sequences, the
263 * elements must be comparable with @c <, and
264 * std::lexicographical_compare() is usually used to make the
265 * determination.
267 template<typename _Tp, typename _Sequence>
268 inline bool
269 operator<(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y)
270 { return __x.c < __y.c; }
272 /// Based on operator==
273 template<typename _Tp, typename _Sequence>
274 inline bool
275 operator!=(const queue<_Tp,_Sequence>& __x,
276 const queue<_Tp,_Sequence>& __y)
277 { return !(__x == __y); }
279 /// Based on operator<
280 template<typename _Tp, typename _Sequence>
281 inline bool
282 operator>(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y)
283 { return __y < __x; }
285 /// Based on operator<
286 template<typename _Tp, typename _Sequence>
287 inline bool
288 operator<=(const queue<_Tp,_Sequence>& __x,
289 const queue<_Tp,_Sequence>& __y)
290 { return !(__y < __x); }
292 /// Based on operator<
293 template<typename _Tp, typename _Sequence>
294 inline bool
295 operator>=(const queue<_Tp,_Sequence>& __x,
296 const queue<_Tp,_Sequence>& __y)
297 { return !(__x < __y); }
300 * @brief A standard container automatically sorting its contents.
302 * @ingroup Containers
303 * @ingroup Sequences
305 * This is not a true container, but an @e adaptor. It holds
306 * another container, and provides a wrapper interface to that
307 * container. The wrapper is what enforces sorting and
308 * first-in-first-out %queue behavior. Very few of the standard
309 * container/sequence interface requirements are met (e.g.,
310 * iterators).
312 * The second template parameter defines the type of the underlying
313 * sequence/container. It defaults to std::vector, but it can be
314 * any type that supports @c front(), @c push_back, @c pop_back,
315 * and random-access iterators, such as std::deque or an
316 * appropriate user-defined type.
318 * The third template parameter supplies the means of making
319 * priority comparisons. It defaults to @c less<value_type> but
320 * can be anything defining a strict weak ordering.
322 * Members not found in "normal" containers are @c container_type,
323 * which is a typedef for the second Sequence parameter, and @c
324 * push, @c pop, and @c top, which are standard %queue/FIFO
325 * operations.
327 * @note No equality/comparison operators are provided for
328 * %priority_queue.
330 * @note Sorting of the elements takes place as they are added to,
331 * and removed from, the %priority_queue using the
332 * %priority_queue's member functions. If you access the elements
333 * by other means, and change their data such that the sorting
334 * order would be different, the %priority_queue will not re-sort
335 * the elements for you. (How could it know to do so?)
337 template<typename _Tp, typename _Sequence = vector<_Tp>,
338 typename _Compare = less<typename _Sequence::value_type> >
339 class priority_queue
341 // concept requirements
342 typedef typename _Sequence::value_type _Sequence_value_type;
343 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
344 __glibcxx_class_requires(_Sequence, _SequenceConcept)
345 __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept)
346 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
347 __glibcxx_class_requires4(_Compare, bool, _Tp,_Tp,_BinaryFunctionConcept)
349 public:
350 typedef typename _Sequence::value_type value_type;
351 typedef typename _Sequence::reference reference;
352 typedef typename _Sequence::const_reference const_reference;
353 typedef typename _Sequence::size_type size_type;
354 typedef _Sequence container_type;
356 protected:
357 // See queue::c for notes on these names.
358 _Sequence c;
359 _Compare comp;
361 public:
363 * @brief Default constructor creates no elements.
365 explicit
366 priority_queue(const _Compare& __x = _Compare(),
367 const _Sequence& __s = _Sequence())
368 : c(__s), comp(__x)
369 { std::make_heap(c.begin(), c.end(), comp); }
372 * @brief Builds a %queue from a range.
373 * @param first An input iterator.
374 * @param last An input iterator.
375 * @param x A comparison functor describing a strict weak ordering.
376 * @param s An initial sequence with which to start.
378 * Begins by copying @a s, inserting a copy of the elements
379 * from @a [first,last) into the copy of @a s, then ordering
380 * the copy according to @a x.
382 * For more information on function objects, see the
383 * documentation on @link s20_3_1_base functor base
384 * classes@endlink.
386 template<typename _InputIterator>
387 priority_queue(_InputIterator __first, _InputIterator __last,
388 const _Compare& __x = _Compare(),
389 const _Sequence& __s = _Sequence())
390 : c(__s), comp(__x)
392 __glibcxx_requires_valid_range(__first, __last);
393 c.insert(c.end(), __first, __last);
394 std::make_heap(c.begin(), c.end(), comp);
398 * Returns true if the %queue is empty.
400 bool
401 empty() const { return c.empty(); }
403 /** Returns the number of elements in the %queue. */
404 size_type
405 size() const { return c.size(); }
408 * Returns a read-only (constant) reference to the data at the first
409 * element of the %queue.
411 const_reference
412 top() const
414 __glibcxx_requires_nonempty();
415 return c.front();
419 * @brief Add data to the %queue.
420 * @param x Data to be added.
422 * This is a typical %queue operation.
423 * The time complexity of the operation depends on the underlying
424 * sequence.
426 void
427 push(const value_type& __x)
431 c.push_back(__x);
432 std::push_heap(c.begin(), c.end(), comp);
434 catch(...)
436 c.clear();
437 __throw_exception_again;
442 * @brief Removes first element.
444 * This is a typical %queue operation. It shrinks the %queue
445 * by one. The time complexity of the operation depends on the
446 * underlying sequence.
448 * Note that no data is returned, and if the first element's
449 * data is needed, it should be retrieved before pop() is
450 * called.
452 void
453 pop()
455 __glibcxx_requires_nonempty();
458 std::pop_heap(c.begin(), c.end(), comp);
459 c.pop_back();
461 catch(...)
463 c.clear();
464 __throw_exception_again;
469 // No equality/comparison operators are provided for priority_queue.
470 } // namespace std
472 #endif /* _QUEUE_H */