source: mainline/uspace/lib/cpp/include/__bits/adt/queue.hpp@ 8fd0675f

Last change on this file since 8fd0675f was b57ba05, checked in by Jiří Zárevúcky <zarevucky.jiri@…>, 3 years ago

Update headers in C++ files
  • Property mode set to 100644
File size: 11.2 KB
Line 
1/*
2 * SPDX-FileCopyrightText: 2018 Jaroslav Jindrak
3 *
4 * SPDX-License-Identifier: BSD-3-Clause
5 */
6
7#ifndef LIBCPP_BITS_ADT_QUEUE
8#define LIBCPP_BITS_ADT_QUEUE
9
10#include <algorithm>
11#include <deque>
12#include <memory>
13#include <type_traits>
14#include <utility>
15#include <vector>
16
17namespace std
18{
19 /**
20 * 23.6.3, class template queue:
21 */
22
23 template<class T, class Container = deque<T>>
24 class queue
25 {
26 public:
27 using value_type = typename Container::value_type;
28 using reference = typename Container::reference;
29 using const_reference = typename Container::const_reference;
30 using size_type = typename Container::size_type;
31 using container_type = Container;
32
33 protected:
34 container_type c;
35
36 public:
37 explicit queue(const container_type& cc)
38 : c{cc}
39 { /* DUMMY BODY */ }
40
41 explicit queue(container_type&& cc = container_type{})
42 : c{move(cc)}
43 { /* DUMMY BODY */ }
44
45 template<
46 class Alloc,
47 class = enable_if_t<uses_allocator<container_type, Alloc>::value, void>
48 >
49 explicit queue(const Alloc& alloc)
50 : c{alloc}
51 { /* DUMMY BODY */}
52
53 template<
54 class Alloc,
55 class = enable_if_t<uses_allocator<container_type, Alloc>::value, void>
56 >
57 queue(const container_type& cc, const Alloc& alloc)
58 : c{cc, alloc}
59 { /* DUMMY BODY */}
60
61 template<
62 class Alloc,
63 class = enable_if_t<uses_allocator<container_type, Alloc>::value, void>
64 >
65 queue(container_type&& cc, const Alloc& alloc)
66 : c{move(cc), alloc}
67 { /* DUMMY BODY */}
68
69 template<
70 class Alloc,
71 class = enable_if_t<uses_allocator<container_type, Alloc>::value, void>
72 >
73 queue(const queue& other, const Alloc& alloc)
74 : c{other.c, alloc}
75 { /* DUMMY BODY */}
76
77 template<
78 class Alloc,
79 class = enable_if_t<uses_allocator<container_type, Alloc>::value, void>
80 >
81 queue(queue&& other, const Alloc& alloc)
82 : c{move(other.c), alloc}
83 { /* DUMMY BODY */}
84
85 bool empty() const
86 {
87 return c.empty();
88 }
89
90 size_type size() const
91 {
92 return c.size();
93 }
94
95 reference front()
96 {
97 return c.front();
98 }
99
100 const_reference front() const
101 {
102 return c.front();
103 }
104
105 reference back()
106 {
107 return c.back();
108 }
109
110 const_reference back() const
111 {
112 return c.back();
113 }
114
115 void push(const value_type& val)
116 {
117 c.push_back(val);
118 }
119
120 void push(value_type&& val)
121 {
122 c.push_back(forward<value_type>(val));
123 }
124
125 template<class... Args>
126 void emplace(Args&&... args)
127 {
128 c.emplace_back(forward<Args>(args)...);
129 }
130
131 void pop()
132 {
133 c.pop_front();
134 }
135
136 void swap(queue& other)
137 noexcept(noexcept(swap(c, other.c)))
138 {
139 std::swap(c, other.c);
140 }
141
142 private:
143 template<class U, class C>
144 friend bool operator==(const queue<U, C>&, const queue<U, C>&);
145
146 template<class U, class C>
147 friend bool operator<(const queue<U, C>&, const queue<U, C>&);
148
149 template<class U, class C>
150 friend bool operator!=(const queue<U, C>&, const queue<U, C>&);
151
152 template<class U, class C>
153 friend bool operator>(const queue<U, C>&, const queue<U, C>&);
154
155 template<class U, class C>
156 friend bool operator>=(const queue<U, C>&, const queue<U, C>&);
157
158 template<class U, class C>
159 friend bool operator<=(const queue<U, C>&, const queue<U, C>&);
160 };
161
162 template<class T, class Container, class Alloc>
163 struct uses_allocator<queue<T, Container>, Alloc>
164 : uses_allocator<Container, Alloc>
165 { /* DUMMY BODY */ };
166
167 /**
168 * 23.6.4, class template priority_queue:
169 */
170
171 template<
172 class T, class Container = vector<T>,
173 class Compare = less<typename Container::value_type>
174 >
175 class priority_queue
176 {
177 public:
178 using value_type = typename Container::value_type;
179 using reference = typename Container::reference;
180 using const_reference = typename Container::const_reference;
181 using size_type = typename Container::size_type;
182 using container_type = Container;
183
184 protected:
185 using compare_type = Compare;
186
187 compare_type comp;
188 container_type c;
189
190 public:
191 priority_queue(const compare_type& cmp, const container_type& cc)
192 : comp{cmp}, c{cc}
193 {
194 make_heap(c.begin(), c.end(), comp);
195 }
196
197 explicit priority_queue(const compare_type& cmp = compare_type{},
198 container_type&& cc = container_type{})
199 : comp{cmp}, c{move(cc)}
200 {
201 make_heap(c.begin(), c.end(), comp);
202 }
203
204 template<class InputIterator>
205 priority_queue(InputIterator first, InputIterator last,
206 const compare_type& cmp,
207 const container_type& cc)
208 : comp{cmp}, c{cc}
209 {
210 c.insert(c.end(), first, last);
211 make_heap(c.begin(), c.end(), comp);
212 }
213
214 template<class InputIterator>
215 priority_queue(InputIterator first, InputIterator last,
216 const compare_type& cmp = compare_type{},
217 container_type&& cc = container_type{})
218 : comp{cmp}, c{move(cc)}
219 {
220 c.insert(c.end(), first, last);
221 make_heap(c.begin(), c.end(), comp);
222 }
223
224 template<
225 class Alloc,
226 class = enable_if_t<uses_allocator<container_type, Alloc>::value, void>
227 >
228 explicit priority_queue(const Alloc& alloc)
229 : comp{}, c{alloc}
230 { /* DUMMY BODY */ }
231
232 template<
233 class Alloc,
234 class = enable_if_t<uses_allocator<container_type, Alloc>::value, void>
235 >
236 priority_queue(const compare_type& cmp, const Alloc& alloc)
237 : comp{cmp}, c{alloc}
238 { /* DUMMY BODY */ }
239
240 template<
241 class Alloc,
242 class = enable_if_t<uses_allocator<container_type, Alloc>::value, void>
243 >
244 priority_queue(const compare_type& cmp, const container_type& cc,
245 const Alloc& alloc)
246 : comp{cmp}, c{cc, alloc}
247 { /* DUMMY BODY */ }
248
249 template<
250 class Alloc,
251 class = enable_if_t<uses_allocator<container_type, Alloc>::value, void>
252 >
253 priority_queue(const compare_type& cmp, container_type&& cc,
254 const Alloc& alloc)
255 : comp{cmp}, c{move(cc), alloc}
256 { /* DUMMY BODY */ }
257
258 template<
259 class Alloc,
260 class = enable_if_t<uses_allocator<container_type, Alloc>::value, void>
261 >
262 priority_queue(const priority_queue& other, const Alloc& alloc)
263 : comp{other.comp}, c{other.c, alloc}
264 { /* DUMMY BODY */ }
265
266 template<
267 class Alloc,
268 class = enable_if_t<uses_allocator<container_type, Alloc>::value, void>
269 >
270 priority_queue(priority_queue&& other, const Alloc& alloc)
271 : comp{move(other.comp)}, c{move(other.c), alloc}
272 { /* DUMMY BODY */ }
273
274 bool empty() const
275 {
276 return c.empty();
277 }
278
279 size_type size() const
280 {
281 return c.size();
282 }
283
284 const_reference top() const
285 {
286 return c.front();
287 }
288
289 void push(const value_type& val)
290 {
291 c.push_back(val);
292 push_heap(c.begin(), c.end(), comp);
293 }
294
295 void push(value_type&& val)
296 {
297 c.push_back(forward<value_type>(val));
298 push_heap(c.begin(), c.end(), comp);
299 }
300
301 template<class... Args>
302 void emplace(Args&&... args)
303 {
304 c.emplace_back(forward<Args>(args)...);
305 push_heap(c.begin(), c.end(), comp);
306 }
307
308 void pop()
309 {
310 pop_heap(c.begin(), c.end(), comp);
311 c.pop_back();
312 }
313
314 void swap(priority_queue& other)
315 noexcept(noexcept(swap(c, other.c)) && noexcept(swap(comp, other.comp)))
316 {
317 std::swap(c, other.c);
318 std::swap(comp, other.comp);
319 }
320 };
321
322 template<class T, class Container, class Compare, class Alloc>
323 struct uses_allocator<priority_queue<T, Container, Compare>, Alloc>
324 : uses_allocator<Container, Alloc>
325 { /* DUMMY BODY */ };
326
327 template<class T, class Container>
328 bool operator==(const queue<T, Container>& lhs,
329 const queue<T, Container>& rhs)
330 {
331 return lhs.c == rhs.c;
332 }
333
334 template<class T, class Container>
335 bool operator<(const queue<T, Container>& lhs,
336 const queue<T, Container>& rhs)
337 {
338 return lhs.c < rhs.c;
339 }
340
341 template<class T, class Container>
342 bool operator!=(const queue<T, Container>& lhs,
343 const queue<T, Container>& rhs)
344 {
345 return lhs.c != rhs.c;
346 }
347
348 template<class T, class Container>
349 bool operator>(const queue<T, Container>& lhs,
350 const queue<T, Container>& rhs)
351 {
352 return lhs.c > rhs.c;
353 }
354
355 template<class T, class Container>
356 bool operator>=(const queue<T, Container>& lhs,
357 const queue<T, Container>& rhs)
358 {
359 return lhs.c >= rhs.c;
360 }
361
362 template<class T, class Container>
363 bool operator<=(const queue<T, Container>& lhs,
364 const queue<T, Container>& rhs)
365 {
366 return lhs.c <= rhs.c;
367 }
368
369 template<class T, class Container>
370 void swap(queue<T, Container>& lhs, queue<T, Container>& rhs)
371 noexcept(noexcept(lhs.swap(rhs)))
372 {
373 lhs.swap(rhs);
374 }
375
376 template<class T, class Container, class Compare>
377 void swap(priority_queue<T, Container, Compare>& lhs,
378 priority_queue<T, Container, Compare>& rhs)
379 noexcept(noexcept(lhs.swap(rhs)))
380 {
381 lhs.swap(rhs);
382 }
383}
384
385#endif
Note: See TracBrowser for help on using the repository browser.