1/*
2 *
3 * Copyright (c) 1994
4 * Hewlett-Packard Company
5 *
6 * Copyright (c) 1996,1997
7 * Silicon Graphics Computer Systems, Inc.
8 *
9 * Copyright (c) 1997
10 * Moscow Center for SPARC Technology
11 *
12 * Copyright (c) 1999
13 * Boris Fomitchev
14 *
15 * This material is provided "as is", with absolutely no warranty expressed
16 * or implied. Any use is at your own risk.
17 *
18 * Permission to use or copy this software for any purpose is hereby granted
19 * without fee, provided the above notices are retained on all copies.
20 * Permission to modify the code and to distribute modified code is granted,
21 * provided the above notices are retained, and a notice that the code was
22 * modified is included with the above copyright notice.
23 *
24 */
25
26/* NOTE: This is an internal header file, included by other STL headers.
27 *   You should not attempt to use it directly.
28 */
29
30#ifndef _STLP_INTERNAL_QUEUE_H
31#define _STLP_INTERNAL_QUEUE_H
32
33#ifndef _STLP_INTERNAL_DEQUE_H
34#  include <stl/_deque.h>
35#endif
36
37#ifndef _STLP_INTERNAL_VECTOR_H
38# include <stl/_vector.h>
39#endif
40
41#ifndef _STLP_INTERNAL_HEAP_H
42#  include <stl/_heap.h>
43#endif
44
45#ifndef _STLP_INTERNAL_FUNCTION_BASE_H
46#  include <stl/_function_base.h>
47#endif
48
49_STLP_BEGIN_NAMESPACE
50
51# if ! defined ( _STLP_LIMITED_DEFAULT_TEMPLATES )
52template <class _Tp, class _Sequence = deque<_Tp> >
53# elif defined ( _STLP_MINIMUM_DEFAULT_TEMPLATE_PARAMS )
54#  define _STLP_QUEUE_ARGS _Tp
55template <class _Tp>
56# else
57template <class _Tp, class _Sequence>
58# endif
59class queue
60#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
61#  if defined (_STLP_QUEUE_ARGS)
62            : public __stlport_class<queue<_Tp> >
63#  else
64            : public __stlport_class<queue<_Tp, _Sequence> >
65#  endif
66#endif
67{
68# if defined ( _STLP_QUEUE_ARGS )
69  typedef deque<_Tp> _Sequence;
70  typedef queue<_Tp> _Self;
71# else
72  typedef queue<_Tp, _Sequence> _Self;
73# endif
74public:
75  typedef typename _Sequence::value_type      value_type;
76  typedef typename _Sequence::size_type       size_type;
77  typedef          _Sequence                  container_type;
78
79  typedef typename _Sequence::reference       reference;
80  typedef typename _Sequence::const_reference const_reference;
81
82protected:
83  //c is a Standard name (23.2.3.1), do no make it STLport naming convention compliant.
84  _Sequence c;
85public:
86  queue() : c() {}
87  explicit queue(const _Sequence& __c) : c(__c) {}
88
89#if !defined (_STLP_NO_MOVE_SEMANTIC)
90  queue(__move_source<_Self> src)
91    : c(_STLP_PRIV _AsMoveSource(src.get().c)) {}
92#endif
93
94  bool empty() const { return c.empty(); }
95  size_type size() const { return c.size(); }
96  reference front() { return c.front(); }
97  const_reference front() const { return c.front(); }
98  reference back() { return c.back(); }
99  const_reference back() const { return c.back(); }
100  void push(const value_type& __x) { c.push_back(__x); }
101  void pop() { c.pop_front(); }
102  const _Sequence& _Get_s() const { return c; }
103
104#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
105  void _M_swap_workaround(_Self& __x) {
106    _Sequence __tmp = c;
107    c = __x.c;
108    __x.c = __tmp;
109  }
110#endif
111};
112
113#ifndef _STLP_QUEUE_ARGS
114#  define _STLP_QUEUE_ARGS _Tp, _Sequence
115#  define _STLP_QUEUE_HEADER_ARGS class _Tp, class _Sequence
116#else
117#  define _STLP_QUEUE_HEADER_ARGS class _Tp
118#endif
119
120template < _STLP_QUEUE_HEADER_ARGS >
121inline bool _STLP_CALL
122operator==(const queue<_STLP_QUEUE_ARGS >& __x, const queue<_STLP_QUEUE_ARGS >& __y) {
123  return __x._Get_s() == __y._Get_s();
124}
125
126template < _STLP_QUEUE_HEADER_ARGS >
127inline bool _STLP_CALL
128operator<(const queue<_STLP_QUEUE_ARGS >& __x, const queue<_STLP_QUEUE_ARGS >& __y) {
129  return __x._Get_s() < __y._Get_s();
130}
131
132_STLP_RELOPS_OPERATORS( template < _STLP_QUEUE_HEADER_ARGS >, queue<_STLP_QUEUE_ARGS > )
133
134# if !(defined ( _STLP_LIMITED_DEFAULT_TEMPLATES ) || defined ( _STLP_TEMPLATE_PARAM_SUBTYPE_BUG ))
135template <class _Tp, class _Sequence = vector<_Tp>,
136          class _Compare = less<_STLP_HEADER_TYPENAME _Sequence::value_type> >
137# elif defined ( _STLP_MINIMUM_DEFAULT_TEMPLATE_PARAMS )
138template <class _Tp>
139# else
140template <class _Tp, class _Sequence, class _Compare>
141# endif
142class priority_queue
143#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
144#  if defined (_STLP_MINIMUM_DEFAULT_TEMPLATE_PARAMS)
145            : public __stlport_class<priority_queue<_Tp> >
146#  else
147            : public __stlport_class<priority_queue<_Tp, _Sequence> >
148#  endif
149#endif
150{
151# ifdef _STLP_MINIMUM_DEFAULT_TEMPLATE_PARAMS
152  typedef vector<_Tp> _Sequence;
153  typedef less< typename vector<_Tp>::value_type> _Compare;
154  typedef priority_queue<_Tp> _Self;
155# else
156  typedef priority_queue<_Tp, _Sequence, _Compare> _Self;
157# endif
158public:
159  typedef typename _Sequence::value_type      value_type;
160  typedef typename _Sequence::size_type       size_type;
161  typedef          _Sequence                  container_type;
162
163  typedef typename _Sequence::reference       reference;
164  typedef typename _Sequence::const_reference const_reference;
165protected:
166  //c is a Standard name (23.2.3.2), do no make it STLport naming convention compliant.
167  _Sequence c;
168  _Compare comp;
169public:
170  priority_queue() : c() {}
171  explicit priority_queue(const _Compare& __x) :  c(), comp(__x) {}
172  priority_queue(const _Compare& __x, const _Sequence& __s)
173    : c(__s), comp(__x)
174    { make_heap(c.begin(), c.end(), comp); }
175
176#if !defined (_STLP_NO_MOVE_SEMANTIC)
177  priority_queue(__move_source<_Self> src)
178    : c(_STLP_PRIV _AsMoveSource(src.get().c)),
179      comp(_STLP_PRIV _AsMoveSource(src.get().comp)) {}
180#endif
181
182#ifdef _STLP_MEMBER_TEMPLATES
183  template <class _InputIterator>
184  priority_queue(_InputIterator __first, _InputIterator __last)
185    : c(__first, __last) { make_heap(c.begin(), c.end(), comp); }
186
187  template <class _InputIterator>
188  priority_queue(_InputIterator __first,
189                 _InputIterator __last, const _Compare& __x)
190    : c(__first, __last), comp(__x)
191    { make_heap(c.begin(), c.end(), comp); }
192
193  template <class _InputIterator>
194  priority_queue(_InputIterator __first, _InputIterator __last,
195                 const _Compare& __x, const _Sequence& __s)
196  : c(__s), comp(__x)
197  {
198    c.insert(c.end(), __first, __last);
199    make_heap(c.begin(), c.end(), comp);
200  }
201
202#else /* _STLP_MEMBER_TEMPLATES */
203  priority_queue(const value_type* __first, const value_type* __last)
204    : c(__first, __last) { make_heap(c.begin(), c.end(), comp); }
205
206  priority_queue(const value_type* __first, const value_type* __last,
207                 const _Compare& __x)
208    : c(__first, __last), comp(__x)
209    { make_heap(c.begin(), c.end(), comp); }
210
211  priority_queue(const value_type* __first, const value_type* __last,
212                 const _Compare& __x, const _Sequence& __c)
213    : c(__c), comp(__x)
214  {
215    c.insert(c.end(), __first, __last);
216    make_heap(c.begin(), c.end(), comp);
217  }
218#endif /* _STLP_MEMBER_TEMPLATES */
219
220  bool empty() const { return c.empty(); }
221  size_type size() const { return c.size(); }
222  const_reference top() const { return c.front(); }
223  void push(const value_type& __x) {
224    _STLP_TRY {
225      c.push_back(__x);
226      push_heap(c.begin(), c.end(), comp);
227    }
228    _STLP_UNWIND(c.clear())
229  }
230  void pop() {
231    _STLP_TRY {
232      pop_heap(c.begin(), c.end(), comp);
233      c.pop_back();
234    }
235    _STLP_UNWIND(c.clear())
236  }
237#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
238  void _M_swap_workaround(_Self& __x) {
239    _Sequence __tmp = c;
240    c = __x.c;
241    __x.c = __tmp;
242  }
243#endif
244};
245
246#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) && !defined (_STLP_NO_MOVE_SEMANTIC)
247template <class _Tp, class _Sequence>
248struct __move_traits<queue<_Tp, _Sequence> > :
249  _STLP_PRIV __move_traits_aux<_Sequence>
250{};
251
252template <class _Tp, class _Sequence, class _Compare>
253struct __move_traits<priority_queue<_Tp, _Sequence, _Compare> > :
254  _STLP_PRIV __move_traits_aux2<_Sequence, _Compare>
255{};
256#endif
257
258_STLP_END_NAMESPACE
259
260#undef _STLP_QUEUE_ARGS
261#undef _STLP_QUEUE_HEADER_ARGS
262#undef comp
263
264#endif /* _STLP_INTERNAL_QUEUE_H */
265
266// Local Variables:
267// mode:C++
268// End:
269