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