1/*=============================================================================
2 Copyright (c) 2001, Daniel C. Nuffer
3 Copyright (c) 2003, Hartmut Kaiser
4 http://spirit.sourceforge.net/
5
6 Distributed under the Boost Software License, Version 1.0. (See accompanying
7 file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
8=============================================================================*/
9#ifndef BOOST_SPIRIT_CLASSIC_ITERATOR_FIXED_SIZE_QUEUE_HPP
10#define BOOST_SPIRIT_CLASSIC_ITERATOR_FIXED_SIZE_QUEUE_HPP
11
12#include <cstddef>
13#include <cstdlib>
14#include <iterator>
15
16#include <boost/spirit/home/classic/namespace.hpp>
17#include <boost/spirit/home/classic/core/assert.hpp> // for BOOST_SPIRIT_ASSERT
18
19// FIXES for broken compilers
20#include <boost/config.hpp>
21#include <boost/iterator_adaptors.hpp>
22
23#define BOOST_SPIRIT_ASSERT_FSQ_SIZE \
24 BOOST_SPIRIT_ASSERT(((m_tail + N + 1) - m_head) % (N+1) == m_size % (N+1)) \
25 /**/
26
27///////////////////////////////////////////////////////////////////////////////
28namespace boost { namespace spirit {
29
30BOOST_SPIRIT_CLASSIC_NAMESPACE_BEGIN
31
32///////////////////////////////////////////////////////////////////////////////
33namespace impl {
34
35#if !defined(BOOST_ITERATOR_ADAPTORS_VERSION) || \
36 BOOST_ITERATOR_ADAPTORS_VERSION < 0x0200
37#error "Please use at least Boost V1.31.0 while compiling the fixed_size_queue class!"
38#else // BOOST_ITERATOR_ADAPTORS_VERSION < 0x0200
39
40template <typename QueueT, typename T, typename PointerT>
41class fsq_iterator
42: public boost::iterator_adaptor<
43 fsq_iterator<QueueT, T, PointerT>,
44 PointerT,
45 T,
46 std::random_access_iterator_tag
47 >
48{
49public:
50 typedef typename QueueT::position_t position;
51 typedef boost::iterator_adaptor<
52 fsq_iterator<QueueT, T, PointerT>, PointerT, T,
53 std::random_access_iterator_tag
54 > base_t;
55
56 fsq_iterator() {}
57 fsq_iterator(position const &p_) : p(p_) {}
58
59 position const &get_position() const { return p; }
60
61private:
62 friend class boost::iterator_core_access;
63
64 typename base_t::reference dereference() const
65 {
66 return p.self->m_queue[p.pos];
67 }
68
69 void increment()
70 {
71 ++p.pos;
72 if (p.pos == QueueT::MAX_SIZE+1)
73 p.pos = 0;
74 }
75
76 void decrement()
77 {
78 if (p.pos == 0)
79 p.pos = QueueT::MAX_SIZE;
80 else
81 --p.pos;
82 }
83
84 template <
85 typename OtherDerivedT, typename OtherIteratorT,
86 typename V, typename C, typename R, typename D
87 >
88 bool equal(iterator_adaptor<OtherDerivedT, OtherIteratorT, V, C, R, D>
89 const &x) const
90 {
91 position const &rhs_pos =
92 static_cast<OtherDerivedT const &>(x).get_position();
93 return (p.self == rhs_pos.self) && (p.pos == rhs_pos.pos);
94 }
95
96 template <
97 typename OtherDerivedT, typename OtherIteratorT,
98 typename V, typename C, typename R, typename D
99 >
100 typename base_t::difference_type distance_to(
101 iterator_adaptor<OtherDerivedT, OtherIteratorT, V, C, R, D>
102 const &x) const
103 {
104 typedef typename base_t::difference_type diff_t;
105
106 position const &p2 =
107 static_cast<OtherDerivedT const &>(x).get_position();
108 std::size_t pos1 = p.pos;
109 std::size_t pos2 = p2.pos;
110
111 // Undefined behaviour if the iterators come from different
112 // containers
113 BOOST_SPIRIT_ASSERT(p.self == p2.self);
114
115 if (pos1 < p.self->m_head)
116 pos1 += QueueT::MAX_SIZE;
117 if (pos2 < p2.self->m_head)
118 pos2 += QueueT::MAX_SIZE;
119
120 if (pos2 > pos1)
121 return diff_t(pos2 - pos1);
122 else
123 return -diff_t(pos1 - pos2);
124 }
125
126 void advance(typename base_t::difference_type n)
127 {
128 // Notice that we don't care values of n that can
129 // wrap around more than one time, since it would
130 // be undefined behaviour anyway (going outside
131 // the begin/end range). Negative wrapping is a bit
132 // cumbersome because we don't want to case p.pos
133 // to signed.
134 if (n < 0)
135 {
136 n = -n;
137 if (p.pos < (std::size_t)n)
138 p.pos = QueueT::MAX_SIZE+1 - (n - p.pos);
139 else
140 p.pos -= n;
141 }
142 else
143 {
144 p.pos += n;
145 if (p.pos >= QueueT::MAX_SIZE+1)
146 p.pos -= QueueT::MAX_SIZE+1;
147 }
148 }
149
150private:
151 position p;
152};
153
154#endif // BOOST_ITERATOR_ADAPTORS_VERSION < 0x0200
155
156///////////////////////////////////////////////////////////////////////////////
157} /* namespace impl */
158
159template <typename T, std::size_t N>
160class fixed_size_queue
161{
162private:
163 struct position
164 {
165 fixed_size_queue* self;
166 std::size_t pos;
167
168 position() : self(0), pos(0) {}
169
170 // The const_cast here is just to avoid to have two different
171 // position structures for the const and non-const case.
172 // The const semantic is guaranteed by the iterator itself
173 position(const fixed_size_queue* s, std::size_t p)
174 : self(const_cast<fixed_size_queue*>(s)), pos(p)
175 {}
176 };
177
178public:
179 // Declare the iterators
180 typedef impl::fsq_iterator<fixed_size_queue<T, N>, T, T*> iterator;
181 typedef impl::fsq_iterator<fixed_size_queue<T, N>, T const, T const*>
182 const_iterator;
183 typedef position position_t;
184
185 friend class impl::fsq_iterator<fixed_size_queue<T, N>, T, T*>;
186 friend class impl::fsq_iterator<fixed_size_queue<T, N>, T const, T const*>;
187
188 fixed_size_queue();
189 fixed_size_queue(const fixed_size_queue& x);
190 fixed_size_queue& operator=(const fixed_size_queue& x);
191 ~fixed_size_queue();
192
193 void push_back(const T& e);
194 void push_front(const T& e);
195 void serve(T& e);
196 void pop_front();
197
198 bool empty() const
199 {
200 return m_size == 0;
201 }
202
203 bool full() const
204 {
205 return m_size == N;
206 }
207
208 iterator begin()
209 {
210 return iterator(position(this, m_head));
211 }
212
213 const_iterator begin() const
214 {
215 return const_iterator(position(this, m_head));
216 }
217
218 iterator end()
219 {
220 return iterator(position(this, m_tail));
221 }
222
223 const_iterator end() const
224 {
225 return const_iterator(position(this, m_tail));
226 }
227
228 std::size_t size() const
229 {
230 return m_size;
231 }
232
233 T& front()
234 {
235 return m_queue[m_head];
236 }
237
238 const T& front() const
239 {
240 return m_queue[m_head];
241 }
242
243private:
244 // Redefine the template parameters to avoid using partial template
245 // specialization on the iterator policy to extract N.
246 BOOST_STATIC_CONSTANT(std::size_t, MAX_SIZE = N);
247
248 std::size_t m_head;
249 std::size_t m_tail;
250 std::size_t m_size;
251 T m_queue[N+1];
252};
253
254template <typename T, std::size_t N>
255inline
256fixed_size_queue<T, N>::fixed_size_queue()
257 : m_head(0)
258 , m_tail(0)
259 , m_size(0)
260{
261 BOOST_SPIRIT_ASSERT(m_size <= N+1);
262 BOOST_SPIRIT_ASSERT_FSQ_SIZE;
263 BOOST_SPIRIT_ASSERT(m_head <= N+1);
264 BOOST_SPIRIT_ASSERT(m_tail <= N+1);
265}
266
267template <typename T, std::size_t N>
268inline
269fixed_size_queue<T, N>::fixed_size_queue(const fixed_size_queue& x)
270 : m_head(x.m_head)
271 , m_tail(x.m_tail)
272 , m_size(x.m_size)
273{
274 copy(x.begin(), x.end(), begin());
275 BOOST_SPIRIT_ASSERT(m_size <= N+1);
276 BOOST_SPIRIT_ASSERT_FSQ_SIZE;
277 BOOST_SPIRIT_ASSERT(m_head <= N+1);
278 BOOST_SPIRIT_ASSERT(m_tail <= N+1);
279}
280
281template <typename T, std::size_t N>
282inline fixed_size_queue<T, N>&
283fixed_size_queue<T, N>::operator=(const fixed_size_queue& x)
284{
285 if (this != &x)
286 {
287 m_head = x.m_head;
288 m_tail = x.m_tail;
289 m_size = x.m_size;
290 copy(x.begin(), x.end(), begin());
291 }
292 BOOST_SPIRIT_ASSERT(m_size <= N+1);
293 BOOST_SPIRIT_ASSERT_FSQ_SIZE;
294 BOOST_SPIRIT_ASSERT(m_head <= N+1);
295 BOOST_SPIRIT_ASSERT(m_tail <= N+1);
296
297 return *this;
298}
299
300template <typename T, std::size_t N>
301inline
302fixed_size_queue<T, N>::~fixed_size_queue()
303{
304 BOOST_SPIRIT_ASSERT(m_size <= N+1);
305 BOOST_SPIRIT_ASSERT_FSQ_SIZE;
306 BOOST_SPIRIT_ASSERT(m_head <= N+1);
307 BOOST_SPIRIT_ASSERT(m_tail <= N+1);
308}
309
310template <typename T, std::size_t N>
311inline void
312fixed_size_queue<T, N>::push_back(const T& e)
313{
314 BOOST_SPIRIT_ASSERT(m_size <= N+1);
315 BOOST_SPIRIT_ASSERT_FSQ_SIZE;
316 BOOST_SPIRIT_ASSERT(m_head <= N+1);
317 BOOST_SPIRIT_ASSERT(m_tail <= N+1);
318
319 BOOST_SPIRIT_ASSERT(!full());
320
321 m_queue[m_tail] = e;
322 ++m_size;
323 ++m_tail;
324 if (m_tail == N+1)
325 m_tail = 0;
326
327
328 BOOST_SPIRIT_ASSERT(m_size <= N+1);
329 BOOST_SPIRIT_ASSERT_FSQ_SIZE;
330 BOOST_SPIRIT_ASSERT(m_head <= N+1);
331 BOOST_SPIRIT_ASSERT(m_tail <= N+1);
332}
333
334template <typename T, std::size_t N>
335inline void
336fixed_size_queue<T, N>::push_front(const T& e)
337{
338 BOOST_SPIRIT_ASSERT(m_size <= N+1);
339 BOOST_SPIRIT_ASSERT_FSQ_SIZE;
340 BOOST_SPIRIT_ASSERT(m_head <= N+1);
341 BOOST_SPIRIT_ASSERT(m_tail <= N+1);
342
343 BOOST_SPIRIT_ASSERT(!full());
344
345 if (m_head == 0)
346 m_head = N;
347 else
348 --m_head;
349
350 m_queue[m_head] = e;
351 ++m_size;
352
353 BOOST_SPIRIT_ASSERT(m_size <= N+1);
354 BOOST_SPIRIT_ASSERT_FSQ_SIZE;
355 BOOST_SPIRIT_ASSERT(m_head <= N+1);
356 BOOST_SPIRIT_ASSERT(m_tail <= N+1);
357}
358
359
360template <typename T, std::size_t N>
361inline void
362fixed_size_queue<T, N>::serve(T& e)
363{
364 BOOST_SPIRIT_ASSERT(m_size <= N+1);
365 BOOST_SPIRIT_ASSERT_FSQ_SIZE;
366 BOOST_SPIRIT_ASSERT(m_head <= N+1);
367 BOOST_SPIRIT_ASSERT(m_tail <= N+1);
368
369 e = m_queue[m_head];
370 pop_front();
371}
372
373
374
375template <typename T, std::size_t N>
376inline void
377fixed_size_queue<T, N>::pop_front()
378{
379 BOOST_SPIRIT_ASSERT(m_size <= N+1);
380 BOOST_SPIRIT_ASSERT_FSQ_SIZE;
381 BOOST_SPIRIT_ASSERT(m_head <= N+1);
382 BOOST_SPIRIT_ASSERT(m_tail <= N+1);
383
384 ++m_head;
385 if (m_head == N+1)
386 m_head = 0;
387 --m_size;
388
389 BOOST_SPIRIT_ASSERT(m_size <= N+1);
390 BOOST_SPIRIT_ASSERT_FSQ_SIZE;
391 BOOST_SPIRIT_ASSERT(m_head <= N+1);
392 BOOST_SPIRIT_ASSERT(m_tail <= N+1);
393}
394
395///////////////////////////////////////////////////////////////////////////////
396BOOST_SPIRIT_CLASSIC_NAMESPACE_END
397
398}} // namespace BOOST_SPIRIT_CLASSIC_NS
399
400#undef BOOST_SPIRIT_ASSERT_FSQ_SIZE
401
402#endif
403

source code of boost/libs/spirit/include/boost/spirit/home/classic/iterator/fixed_size_queue.hpp