ReactOS  0.4.13-dev-79-gcd489d8
_queue.h
Go to the documentation of this file.
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 
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
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:
86  queue() : c() {}
87  explicit queue(const _Sequence& __c) : c(__c) {}
88 
89 #if !defined (_STLP_NO_MOVE_SEMANTIC)
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 
120 template < _STLP_QUEUE_HEADER_ARGS >
121 inline bool _STLP_CALL
123  return __x._Get_s() == __y._Get_s();
124 }
125 
126 template < _STLP_QUEUE_HEADER_ARGS >
127 inline bool _STLP_CALL
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 ))
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
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
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)
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 
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:
_Compare comp
Definition: _queue.h:168
void push(const value_type &__x)
Definition: _queue.h:100
priority_queue(const value_type *__first, const value_type *__last, const _Compare &__x)
Definition: _queue.h:206
#define _STLP_RELOPS_OPERATORS(_TMPL, _TP)
Definition: features.h:1039
queue(const _Sequence &__c)
Definition: _queue.h:87
_Sequence::const_reference const_reference
Definition: _queue.h:80
_Sequence::reference reference
Definition: _queue.h:163
_Sequence::const_reference const_reference
Definition: _queue.h:164
_Sequence c
Definition: _queue.h:167
_Sequence container_type
Definition: _queue.h:161
void pop()
Definition: _queue.h:230
queue()
Definition: _queue.h:86
void push(const value_type &__x)
Definition: _queue.h:223
#define __c
Definition: schilyio.h:209
_Sequence::reference reference
Definition: _queue.h:79
bool _STLP_CALL operator==(const queue< _STLP_QUEUE_ARGS > &__x, const queue< _STLP_QUEUE_ARGS > &__y)
Definition: _queue.h:122
queue< _Tp, _Sequence > _Self
Definition: _queue.h:72
_Sequence::value_type value_type
Definition: _queue.h:159
reference back()
Definition: _queue.h:98
priority_queue(const value_type *__first, const value_type *__last, const _Compare &__x, const _Sequence &__c)
Definition: _queue.h:211
Definition: _queue.h:59
#define _STLP_UNWIND(action)
Definition: features.h:824
bool empty() const
Definition: _queue.h:94
const _Sequence & _Get_s() const
Definition: _queue.h:102
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
priority_queue()
Definition: _queue.h:170
const_reference front() const
Definition: _queue.h:97
size_type size() const
Definition: _queue.h:95
void get(int argc, const char *argv[])
Definition: cmds.c:480
void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
Definition: _heap.c:138
const_reference back() const
Definition: _queue.h:99
if(!(yy_init))
Definition: macro.lex.yy.c:714
void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
Definition: _heap.c:65
_Sequence container_type
Definition: _queue.h:77
const GLubyte * c
Definition: glext.h:8905
queue(__move_source< _Self > src)
Definition: _queue.h:90
_Sequence::value_type value_type
Definition: _queue.h:75
Definition: _deque.h:400
_Sequence::size_type size_type
Definition: _queue.h:160
GLint reference
Definition: glext.h:11729
#define _STLP_PRIV
Definition: _dm.h:70
priority_queue< _Tp, _Sequence, _Compare > _Self
Definition: _queue.h:156
_STLP_TYPENAME_ON_RETURN_TYPE _MoveSourceTraits< _Tp >::_Type _AsMoveSource(_Tp &src)
GLenum src
Definition: glext.h:6340
reference front()
Definition: _queue.h:96
_Sequence::size_type size_type
Definition: _queue.h:76
void pop()
Definition: _queue.h:101
#define _STLP_END_NAMESPACE
Definition: features.h:503
#define _STLP_TRY
Definition: features.h:817
#define _STLP_QUEUE_ARGS
Definition: _queue.h:114
priority_queue(__move_source< _Self > src)
Definition: _queue.h:177
bool empty() const
Definition: _queue.h:220
_Sequence c
Definition: _queue.h:84
priority_queue(const value_type *__first, const value_type *__last)
Definition: _queue.h:203
void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
Definition: _heap.c:206
#define _STLP_BEGIN_NAMESPACE
Definition: features.h:501
#define _STLP_CALL
Definition: _bc.h:131
size_type size() const
Definition: _queue.h:221
const_reference top() const
Definition: _queue.h:222
priority_queue(const _Compare &__x)
Definition: _queue.h:171
bool _STLP_CALL operator<(const queue< _STLP_QUEUE_ARGS > &__x, const queue< _STLP_QUEUE_ARGS > &__y)
Definition: _queue.h:128
priority_queue(const _Compare &__x, const _Sequence &__s)
Definition: _queue.h:172