Gitiles
Code Review Sign In
gerrit-public.fairphone.software / platform / external / libcxx / bc8d3f97eb5c958007f2713238472e0c1c8fe02c / . / include / queue
blob: 217206d7694825faa066d89a2bad444417defccd [file] [log] [blame]
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame^]1// -*- C++ -*-
2//===--------------------------- queue ------------------------------------===//
3//
4// ÊÊÊÊÊÊÊÊÊÊÊÊÊÊÊÊÊÊÊÊThe LLVM Compiler Infrastructure
5//
6// This file is distributed under the University of Illinois Open Source
7// License. See LICENSE.TXT for details.
8//
9//===----------------------------------------------------------------------===//
10
11#ifndef _LIBCPP_QUEUE
12#define _LIBCPP_QUEUE
13
14/*
15 queue synopsis
16
17namespace std
18{
19
20template <class T, class Container = deque<T>>
21class queue
22{
23public:
24 typedef Container container_type;
25 typedef typename container_type::value_type value_type;
26 typedef typename container_type::reference reference;
27 typedef typename container_type::const_reference const_reference;
28 typedef typename container_type::size_type size_type;
29
30protected:
31 container_type c;
32
33public:
34 queue();
35 explicit queue(const container_type& c);
36 explicit queue(container_type&& c);
37 queue(queue&& q);
38 template <class Alloc>
39 explicit queue(const Alloc& a);
40 template <class Alloc>
41 queue(const container_type& c, const Alloc& a);
42 template <class Alloc>
43 queue(container_type&& c, const Alloc& a);
44 template <class Alloc>
45 queue(queue&& q, const Alloc& a);
46
47 queue& operator=(queue&& q);
48
49 bool empty() const;
50 size_type size() const;
51
52 reference front();
53 const_reference front() const;
54 reference back();
55 const_reference back() const;
56
57 void push(const value_type& v);
58 void push(value_type&& v);
59 template <class... Args> void emplace(Args&&... args);
60 void pop();
61
62 void swap(queue& q);
63};
64
65template <class T, class Container>
66 bool operator==(const queue<T, Container>& x,const queue<T, Container>& y);
67
68template <class T, class Container>
69 bool operator< (const queue<T, Container>& x,const queue<T, Container>& y);
70
71template <class T, class Container>
72 bool operator!=(const queue<T, Container>& x,const queue<T, Container>& y);
73
74template <class T, class Container>
75 bool operator> (const queue<T, Container>& x,const queue<T, Container>& y);
76
77template <class T, class Container>
78 bool operator>=(const queue<T, Container>& x,const queue<T, Container>& y);
79
80template <class T, class Container>
81 bool operator<=(const queue<T, Container>& x,const queue<T, Container>& y);
82
83template <class T, class Container>
84 void swap(queue<T, Container>& x, queue<T, Container>& y);
85
86template <class T, class Container = vector<T>,
87 class Compare = less<typename Container::value_type>>
88class priority_queue
89{
90public:
91 typedef Container container_type;
92 typedef typename container_type::value_type value_type;
93 typedef typename container_type::reference reference;
94 typedef typename container_type::const_reference const_reference;
95 typedef typename container_type::size_type size_type;
96
97protected:
98 container_type c;
99 Compare comp;
100
101public:
102 explicit priority_queue(const Compare& comp = Compare());
103 priority_queue(const Compare& comp, const container_type& c);
104 explicit priority_queue(const Compare& comp, container_type&& c);
105 template <class InputIterator>
106 priority_queue(InputIterator first, InputIterator last,
107 const Compare& comp = Compare());
108 template <class InputIterator>
109 priority_queue(InputIterator first, InputIterator last,
110 const Compare& comp, const container_type& c);
111 template <class InputIterator>
112 priority_queue(InputIterator first, InputIterator last,
113 const Compare& comp, container_type&& c);
114 priority_queue(priority_queue&& q);
115 priority_queue& operator=(priority_queue&& q);
116 template <class Alloc>
117 explicit priority_queue(const Alloc& a);
118 template <class Alloc>
119 priority_queue(const Compare& comp, const Alloc& a);
120 template <class Alloc>
121 priority_queue(const Compare& comp, const container_type& c,
122 const Alloc& a);
123 template <class Alloc>
124 priority_queue(const Compare& comp, container_type&& c,
125 const Alloc& a);
126 template <class Alloc>
127 priority_queue(priority_queue&& q, const Alloc& a);
128
129 bool empty() const;
130 size_type size() const;
131 const_reference top() const;
132
133 void push(const value_type& v);
134 void push(value_type&& v);
135 template <class... Args> void emplace(Args&&... args);
136 void pop();
137
138 void swap(priority_queue& q);
139};
140
141template <class T, class Container, class Compare>
142 void swap(priority_queue<T, Container, Compare>& x,
143 priority_queue<T, Container, Compare>& y);
144
145} // std
146
147*/
148
149#include <__config>
150#include <deque>
151#include <vector>
152#include <functional>
153#include <algorithm>
154
155#pragma GCC system_header
156
157_LIBCPP_BEGIN_NAMESPACE_STD
158
159template <class _Tp, class _Container> class queue;
160
161template <class _Tp, class _Container>
162bool
163operator==(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y);
164
165template <class _Tp, class _Container>
166bool
167operator< (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y);
168
169template <class _Tp, class _Container = deque<_Tp> >
170class queue
171{
172public:
173 typedef _Container container_type;
174 typedef typename container_type::value_type value_type;
175 typedef typename container_type::reference reference;
176 typedef typename container_type::const_reference const_reference;
177 typedef typename container_type::size_type size_type;
178
179protected:
180 container_type c;
181
182public:
183 queue() : c() {}
184 explicit queue(const container_type& __c) : c(__c) {}
185#ifdef _LIBCPP_MOVE
186 explicit queue(container_type&& __c) : c(_STD::move(__c)) {}
187 queue(queue&& __q) : c(_STD::move(__q.c)) {}
188#endif
189 template <class _Alloc>
190 explicit queue(const _Alloc& __a,
191 typename enable_if<uses_allocator<container_type,
192 _Alloc>::value>::type* = 0)
193 : c(__a) {}
194 template <class _Alloc>
195 queue(const queue& __q, const _Alloc& __a,
196 typename enable_if<uses_allocator<container_type,
197 _Alloc>::value>::type* = 0)
198 : c(__q.c, __a) {}
199 template <class _Alloc>
200 queue(const container_type& __c, const _Alloc& __a,
201 typename enable_if<uses_allocator<container_type,
202 _Alloc>::value>::type* = 0)
203 : c(__c, __a) {}
204#ifdef _LIBCPP_MOVE
205 template <class _Alloc>
206 queue(container_type&& __c, const _Alloc& __a,
207 typename enable_if<uses_allocator<container_type,
208 _Alloc>::value>::type* = 0)
209 : c(_STD::move(__c), __a) {}
210 template <class _Alloc>
211 queue(queue&& __q, const _Alloc& __a,
212 typename enable_if<uses_allocator<container_type,
213 _Alloc>::value>::type* = 0)
214 : c(_STD::move(__q.c), __a) {}
215
216 queue& operator=(queue&& __q)
217 {
218 c = _STD::move(__q.c);
219 return *this;
220 }
221#endif
222
223 bool empty() const {return c.empty();}
224 size_type size() const {return c.size();}
225
226 reference front() {return c.front();}
227 const_reference front() const {return c.front();}
228 reference back() {return c.back();}
229 const_reference back() const {return c.back();}
230
231 void push(const value_type& __v) {c.push_back(__v);}
232#ifdef _LIBCPP_MOVE
233 void push(value_type&& __v) {c.push_back(_STD::move(__v));}
234 template <class... _Args>
235 void emplace(_Args&&... __args)
236 {c.emplace_back(_STD::forward<_Args>(__args)...);}
237#endif
238 void pop() {c.pop_front();}
239
240 void swap(queue& __q)
241 {
242 using _STD::swap;
243 swap(c, __q.c);
244 }
245
246 template <class _T1, class _C1>
247 friend
248 bool
249 operator==(const queue<_T1, _C1>& __x,const queue<_T1, _C1>& __y);
250
251 template <class _T1, class _C1>
252 friend
253 bool
254 operator< (const queue<_T1, _C1>& __x,const queue<_T1, _C1>& __y);
255};
256
257template <class _Tp, class _Container>
258inline
259bool
260operator==(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
261{
262 return __x.c == __y.c;
263}
264
265template <class _Tp, class _Container>
266inline
267bool
268operator< (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
269{
270 return __x.c < __y.c;
271}
272
273template <class _Tp, class _Container>
274inline
275bool
276operator!=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
277{
278 return !(__x == __y);
279}
280
281template <class _Tp, class _Container>
282inline
283bool
284operator> (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
285{
286 return __y < __x;
287}
288
289template <class _Tp, class _Container>
290inline
291bool
292operator>=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
293{
294 return !(__x < __y);
295}
296
297template <class _Tp, class _Container>
298inline
299bool
300operator<=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
301{
302 return !(__y < __x);
303}
304
305template <class _Tp, class _Container>
306inline
307void
308swap(queue<_Tp, _Container>& __x, queue<_Tp, _Container>& __y)
309{
310 __x.swap(__y);
311}
312
313template <class _Tp, class _Container, class _Alloc>
314struct uses_allocator<queue<_Tp, _Container>, _Alloc>
315 : public uses_allocator<_Container, _Alloc>
316{
317};
318
319template <class _Tp, class _Container = vector<_Tp>,
320 class _Compare = less<typename _Container::value_type> >
321class priority_queue
322{
323public:
324 typedef _Container container_type;
325 typedef _Compare value_compare;
326 typedef typename container_type::value_type value_type;
327 typedef typename container_type::reference reference;
328 typedef typename container_type::const_reference const_reference;
329 typedef typename container_type::size_type size_type;
330
331protected:
332 container_type c;
333 value_compare comp;
334
335public:
336 explicit priority_queue(const value_compare& __comp = value_compare())
337 : c(), comp(__comp) {}
338 priority_queue(const value_compare& __comp, const container_type& __c);
339#ifdef _LIBCPP_MOVE
340 explicit priority_queue(const value_compare& __comp, container_type&& __c);
341#endif
342 template <class _InputIter>
343 priority_queue(_InputIter __f, _InputIter __l,
344 const value_compare& __comp = value_compare());
345 template <class _InputIter>
346 priority_queue(_InputIter __f, _InputIter __l,
347 const value_compare& __comp, const container_type& __c);
348#ifdef _LIBCPP_MOVE
349 template <class _InputIter>
350 priority_queue(_InputIter __f, _InputIter __l,
351 const value_compare& __comp, container_type&& __c);
352 priority_queue(priority_queue&& __q);
353 priority_queue& operator=(priority_queue&& __q);
354#endif
355 template <class _Alloc>
356 explicit priority_queue(const _Alloc& __a,
357 typename enable_if<uses_allocator<container_type,
358 _Alloc>::value>::type* = 0);
359 template <class _Alloc>
360 priority_queue(const value_compare& __comp, const _Alloc& __a,
361 typename enable_if<uses_allocator<container_type,
362 _Alloc>::value>::type* = 0);
363 template <class _Alloc>
364 priority_queue(const value_compare& __comp, const container_type& __c,
365 const _Alloc& __a,
366 typename enable_if<uses_allocator<container_type,
367 _Alloc>::value>::type* = 0);
368 template <class _Alloc>
369 priority_queue(const priority_queue& __q, const _Alloc& __a,
370 typename enable_if<uses_allocator<container_type,
371 _Alloc>::value>::type* = 0);
372#ifdef _LIBCPP_MOVE
373 template <class _Alloc>
374 priority_queue(const value_compare& __comp, container_type&& __c,
375 const _Alloc& __a,
376 typename enable_if<uses_allocator<container_type,
377 _Alloc>::value>::type* = 0);
378 template <class _Alloc>
379 priority_queue(priority_queue&& __q, const _Alloc& __a,
380 typename enable_if<uses_allocator<container_type,
381 _Alloc>::value>::type* = 0);
382#endif
383
384 bool empty() const {return c.empty();}
385 size_type size() const {return c.size();}
386 const_reference top() const {return c.front();}
387
388 void push(const value_type& __v);
389#ifdef _LIBCPP_MOVE
390 void push(value_type&& __v);
391 template <class... _Args> void emplace(_Args&&... __args);
392#endif
393 void pop();
394
395 void swap(priority_queue& __q);
396};
397
398template <class _Tp, class _Container, class _Compare>
399inline
400priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Compare& __comp,
401 const container_type& __c)
402 : c(__c),
403 comp(__comp)
404{
405 _STD::make_heap(c.begin(), c.end(), comp);
406}
407
408#ifdef _LIBCPP_MOVE
409
410template <class _Tp, class _Container, class _Compare>
411inline
412priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
413 container_type&& __c)
414 : c(_STD::move(__c)),
415 comp(__comp)
416{
417 _STD::make_heap(c.begin(), c.end(), comp);
418}
419
420#endif
421
422template <class _Tp, class _Container, class _Compare>
423template <class _InputIter>
424inline
425priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
426 const value_compare& __comp)
427 : c(__f, __l),
428 comp(__comp)
429{
430 _STD::make_heap(c.begin(), c.end(), comp);
431}
432
433template <class _Tp, class _Container, class _Compare>
434template <class _InputIter>
435inline
436priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
437 const value_compare& __comp,
438 const container_type& __c)
439 : c(__c),
440 comp(__comp)
441{
442 c.insert(c.end(), __f, __l);
443 _STD::make_heap(c.begin(), c.end(), comp);
444}
445
446#ifdef _LIBCPP_MOVE
447
448template <class _Tp, class _Container, class _Compare>
449template <class _InputIter>
450inline
451priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
452 const value_compare& __comp,
453 container_type&& __c)
454 : c(_STD::move(__c)),
455 comp(__comp)
456{
457 c.insert(c.end(), __f, __l);
458 _STD::make_heap(c.begin(), c.end(), comp);
459}
460
461template <class _Tp, class _Container, class _Compare>
462inline
463priority_queue<_Tp, _Container, _Compare>::priority_queue(priority_queue&& __q)
464 : c(_STD::move(__q.c)),
465 comp(_STD::move(__q.comp))
466{
467}
468
469template <class _Tp, class _Container, class _Compare>
470priority_queue<_Tp, _Container, _Compare>&
471priority_queue<_Tp, _Container, _Compare>::operator=(priority_queue&& __q)
472{
473 c = _STD::move(__q.c);
474 comp = _STD::move(__q.comp);
475 return *this;
476}
477
478#endif
479
480template <class _Tp, class _Container, class _Compare>
481template <class _Alloc>
482inline
483priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Alloc& __a,
484 typename enable_if<uses_allocator<container_type,
485 _Alloc>::value>::type*)
486 : c(__a)
487{
488}
489
490template <class _Tp, class _Container, class _Compare>
491template <class _Alloc>
492inline
493priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
494 const _Alloc& __a,
495 typename enable_if<uses_allocator<container_type,
496 _Alloc>::value>::type*)
497 : c(__a),
498 comp(__comp)
499{
500}
501
502template <class _Tp, class _Container, class _Compare>
503template <class _Alloc>
504inline
505priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
506 const container_type& __c,
507 const _Alloc& __a,
508 typename enable_if<uses_allocator<container_type,
509 _Alloc>::value>::type*)
510 : c(__c, __a),
511 comp(__comp)
512{
513 _STD::make_heap(c.begin(), c.end(), comp);
514}
515
516template <class _Tp, class _Container, class _Compare>
517template <class _Alloc>
518inline
519priority_queue<_Tp, _Container, _Compare>::priority_queue(const priority_queue& __q,
520 const _Alloc& __a,
521 typename enable_if<uses_allocator<container_type,
522 _Alloc>::value>::type*)
523 : c(__q.c, __a),
524 comp(__q.comp)
525{
526 _STD::make_heap(c.begin(), c.end(), comp);
527}
528
529#ifdef _LIBCPP_MOVE
530
531template <class _Tp, class _Container, class _Compare>
532template <class _Alloc>
533inline
534priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
535 container_type&& __c,
536 const _Alloc& __a,
537 typename enable_if<uses_allocator<container_type,
538 _Alloc>::value>::type*)
539 : c(_STD::move(__c), __a),
540 comp(__comp)
541{
542 _STD::make_heap(c.begin(), c.end(), comp);
543}
544
545
546template <class _Tp, class _Container, class _Compare>
547template <class _Alloc>
548inline
549priority_queue<_Tp, _Container, _Compare>::priority_queue(priority_queue&& __q,
550 const _Alloc& __a,
551 typename enable_if<uses_allocator<container_type,
552 _Alloc>::value>::type*)
553 : c(_STD::move(__q.c), __a),
554 comp(_STD::move(__q.comp))
555{
556 _STD::make_heap(c.begin(), c.end(), comp);
557}
558
559#endif
560
561template <class _Tp, class _Container, class _Compare>
562inline
563void
564priority_queue<_Tp, _Container, _Compare>::push(const value_type& __v)
565{
566 c.push_back(__v);
567 _STD::push_heap(c.begin(), c.end(), comp);
568}
569
570#ifdef _LIBCPP_MOVE
571
572template <class _Tp, class _Container, class _Compare>
573inline
574void
575priority_queue<_Tp, _Container, _Compare>::push(value_type&& __v)
576{
577 c.push_back(_STD::move(__v));
578 _STD::push_heap(c.begin(), c.end(), comp);
579}
580
581template <class _Tp, class _Container, class _Compare>
582template <class... _Args>
583inline
584void
585priority_queue<_Tp, _Container, _Compare>::emplace(_Args&&... __args)
586{
587 c.emplace_back(_STD::forward<_Args>(__args)...);
588 _STD::push_heap(c.begin(), c.end(), comp);
589}
590
591#endif
592
593template <class _Tp, class _Container, class _Compare>
594inline
595void
596priority_queue<_Tp, _Container, _Compare>::pop()
597{
598 _STD::pop_heap(c.begin(), c.end(), comp);
599 c.pop_back();
600}
601
602template <class _Tp, class _Container, class _Compare>
603inline
604void
605priority_queue<_Tp, _Container, _Compare>::swap(priority_queue& __q)
606{
607 using _STD::swap;
608 swap(c, __q.c);
609 swap(comp, __q.comp);
610}
611
612template <class _Tp, class _Container, class _Compare>
613inline
614void
615swap(priority_queue<_Tp, _Container, _Compare>& __x,
616 priority_queue<_Tp, _Container, _Compare>& __y)
617{
618 __x.swap(__y);
619}
620
621template <class _Tp, class _Container, class _Compare, class _Alloc>
622struct uses_allocator<priority_queue<_Tp, _Container, _Compare>, _Alloc>
623 : public uses_allocator<_Container, _Alloc>
624{
625};
626
627_LIBCPP_END_NAMESPACE_STD
628
629#endif // _LIBCPP_QUEUE