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 )
52 template <class _Tp, class _Sequence = deque<_Tp> >
53 # elif defined ( _STLP_MINIMUM_DEFAULT_TEMPLATE_PARAMS )
54 # define _STLP_QUEUE_ARGS _Tp
55 template <class _Tp>
56 # else
57 template <class _Tp, class _Sequence>
58 # endif
59 class 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
74 public:
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
82 protected:
83 //c is a Standard name (23.2.3.1), do no make it STLport naming convention compliant.
84 _Sequence c;
85 public:
queue()86 queue() : c() {}
queue(const _Sequence & __c)87 explicit queue(const _Sequence& __c) : c(__c) {}
88
89 #if !defined (_STLP_NO_MOVE_SEMANTIC)
queue(__move_source<_Self> src)90 queue(__move_source<_Self> src)
91 : c(_STLP_PRIV _AsMoveSource(src.get().c)) {}
92 #endif
93
empty()94 bool empty() const { return c.empty(); }
size()95 size_type size() const { return c.size(); }
front()96 reference front() { return c.front(); }
front()97 const_reference front() const { return c.front(); }
back()98 reference back() { return c.back(); }
back()99 const_reference back() const { return c.back(); }
push(const value_type & __x)100 void push(const value_type& __x) { c.push_back(__x); }
pop()101 void pop() { c.pop_front(); }
_Get_s()102 const _Sequence& _Get_s() const { return c; }
103
104 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
_M_swap_workaround(_Self & __x)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
120 template < _STLP_QUEUE_HEADER_ARGS >
121 inline bool _STLP_CALL
122 operator==(const queue<_STLP_QUEUE_ARGS >& __x, const queue<_STLP_QUEUE_ARGS >& __y) {
123 return __x._Get_s() == __y._Get_s();
124 }
125
126 template < _STLP_QUEUE_HEADER_ARGS >
127 inline bool _STLP_CALL
128 operator<(const queue<_STLP_QUEUE_ARGS >& __x, const queue<_STLP_QUEUE_ARGS >& __y) {
129 return __x._Get_s() < __y._Get_s();
130 }
131
_STLP_RELOPS_OPERATORS(template<_STLP_QUEUE_HEADER_ARGS>,queue<_STLP_QUEUE_ARGS>)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 ))
135 template <class _Tp, class _Sequence = vector<_Tp>,
136 class _Compare = less<_STLP_HEADER_TYPENAME _Sequence::value_type> >
137 # elif defined ( _STLP_MINIMUM_DEFAULT_TEMPLATE_PARAMS )
138 template <class _Tp>
139 # else
140 template <class _Tp, class _Sequence, class _Compare>
141 # endif
142 class 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
158 public:
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;
165 protected:
166 //c is a Standard name (23.2.3.2), do no make it STLport naming convention compliant.
167 _Sequence c;
168 _Compare comp;
169 public:
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)
247 template <class _Tp, class _Sequence>
248 struct __move_traits<queue<_Tp, _Sequence> > :
249 _STLP_PRIV __move_traits_aux<_Sequence>
250 {};
251
252 template <class _Tp, class _Sequence, class _Compare>
253 struct __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