1 // Copyright (c) 2001 Daniel C. Nuffer
2 // Copyright (c) 2001-2010 Hartmut Kaiser
4 // Distributed under the Boost Software License, Version 1.0. (See accompanying
5 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
7 #if !defined(BOOST_SPIRIT_ITERATOR_FIXED_SIZE_QUEUE_MAR_16_2007_1137AM)
8 #define BOOST_SPIRIT_ITERATOR_FIXED_SIZE_QUEUE_MAR_16_2007_1137AM
14 #include <boost/config.hpp>
15 #include <boost/assert.hpp> // for BOOST_ASSERT
16 #include <boost/iterator_adaptors.hpp>
18 ///////////////////////////////////////////////////////////////////////////////
19 // Make sure we're using a decent version of the Boost.IteratorAdaptors lib
20 #if !defined(BOOST_ITERATOR_ADAPTORS_VERSION) || \
21 BOOST_ITERATOR_ADAPTORS_VERSION < 0x0200
22 #error "Please use at least Boost V1.31.0 while compiling the fixed_size_queue class!"
25 ///////////////////////////////////////////////////////////////////////////////
26 #define BOOST_SPIRIT_ASSERT_FSQ_SIZE \
27 BOOST_ASSERT(((m_tail + N + 1) - m_head) % (N+1) == m_size % (N+1)) \
30 ///////////////////////////////////////////////////////////////////////////////
31 namespace boost { namespace spirit { namespace detail
33 ///////////////////////////////////////////////////////////////////////////
34 template <typename Queue, typename T, typename Pointer>
36 : public boost::iterator_facade<
37 fsq_iterator<Queue, T, Pointer>, T,
38 std::random_access_iterator_tag
42 typedef typename Queue::position_type position_type;
43 typedef boost::iterator_facade<
44 fsq_iterator<Queue, T, Pointer>, T,
45 std::random_access_iterator_tag
49 fsq_iterator(position_type const &p_) : p(p_) {}
51 position_type &get_position() { return p; }
52 position_type const &get_position() const { return p; }
55 friend class boost::iterator_core_access;
57 typename base_type::reference dereference() const
59 return p.self->m_queue[p.pos];
65 if (p.pos == Queue::MAX_SIZE+1)
72 p.pos = Queue::MAX_SIZE;
79 return p.self == 0 || p.pos == p.self->size();
82 template <typename Q, typename T_, typename P>
83 bool equal(fsq_iterator<Q, T_, P> const &x) const
90 position_type const &rhs_pos = x.get_position();
91 return (p.self == rhs_pos.self) && (p.pos == rhs_pos.pos);
94 template <typename Q, typename T_, typename P>
95 typename base_type::difference_type distance_to(
96 fsq_iterator<Q, T_, P> const &x) const
98 typedef typename base_type::difference_type difference_type;
100 position_type const &p2 = x.get_position();
101 std::size_t pos1 = p.pos;
102 std::size_t pos2 = p2.pos;
104 // Undefined behavior if the iterators come from different
106 BOOST_ASSERT(p.self == p2.self);
108 if (pos1 < p.self->m_head)
109 pos1 += Queue::MAX_SIZE;
110 if (pos2 < p2.self->m_head)
111 pos2 += Queue::MAX_SIZE;
114 return difference_type(pos2 - pos1);
116 return -difference_type(pos1 - pos2);
119 void advance(typename base_type::difference_type n)
121 // Notice that we don't care values of n that can
122 // wrap around more than one time, since it would
123 // be undefined behavior anyway (going outside
124 // the begin/end range). Negative wrapping is a bit
125 // cumbersome because we don't want to case p.pos
130 if (p.pos < (std::size_t)n)
131 p.pos = Queue::MAX_SIZE+1 - (n - p.pos);
138 if (p.pos >= Queue::MAX_SIZE+1)
139 p.pos -= Queue::MAX_SIZE+1;
147 ///////////////////////////////////////////////////////////////////////////
148 template <typename T, std::size_t N>
149 class fixed_size_queue
154 fixed_size_queue* self;
157 position() : self(0), pos(0) {}
159 // The const_cast here is just to avoid to have two different
160 // position structures for the const and non-const case.
161 // The const semantic is guaranteed by the iterator itself
162 position(const fixed_size_queue* s, std::size_t p)
163 : self(const_cast<fixed_size_queue*>(s)), pos(p)
166 bool is_initialized() const { return self != 0; }
167 void set_queue(fixed_size_queue* q) { self = q; }
171 // Declare the iterators
172 typedef fsq_iterator<fixed_size_queue<T, N>, T, T*> iterator;
174 fsq_iterator<fixed_size_queue<T, N>, T const, T const*>
176 typedef position position_type;
178 friend class fsq_iterator<fixed_size_queue<T, N>, T, T*>;
179 friend class fsq_iterator<fixed_size_queue<T, N>, T const, T const*>;
182 fixed_size_queue(const fixed_size_queue& x);
183 fixed_size_queue& operator=(const fixed_size_queue& x);
186 void push_back(const T& e);
187 void push_front(const T& e);
203 return iterator(position(this, m_head));
206 const_iterator begin() const
208 return const_iterator(position(this, m_head));
213 return iterator(position(0, m_tail));
216 const_iterator end() const
218 return const_iterator(position(0, m_tail));
221 std::size_t size() const
228 return m_queue[m_head];
231 const T& front() const
233 return m_queue[m_head];
237 // Redefine the template parameters to avoid using partial template
238 // specialization on the iterator policy to extract N.
239 BOOST_STATIC_CONSTANT(std::size_t, MAX_SIZE = N);
247 template <typename T, std::size_t N>
249 fixed_size_queue<T, N>::fixed_size_queue()
254 BOOST_ASSERT(m_size <= N+1);
255 BOOST_SPIRIT_ASSERT_FSQ_SIZE;
256 BOOST_ASSERT(m_head <= N+1);
257 BOOST_ASSERT(m_tail <= N+1);
260 template <typename T, std::size_t N>
262 fixed_size_queue<T, N>::fixed_size_queue(const fixed_size_queue& x)
267 copy(x.begin(), x.end(), begin());
268 BOOST_ASSERT(m_size <= N+1);
269 BOOST_SPIRIT_ASSERT_FSQ_SIZE;
270 BOOST_ASSERT(m_head <= N+1);
271 BOOST_ASSERT(m_tail <= N+1);
274 template <typename T, std::size_t N>
275 inline fixed_size_queue<T, N>&
276 fixed_size_queue<T, N>::operator=(const fixed_size_queue& x)
283 copy(x.begin(), x.end(), begin());
285 BOOST_ASSERT(m_size <= N+1);
286 BOOST_SPIRIT_ASSERT_FSQ_SIZE;
287 BOOST_ASSERT(m_head <= N+1);
288 BOOST_ASSERT(m_tail <= N+1);
293 template <typename T, std::size_t N>
295 fixed_size_queue<T, N>::~fixed_size_queue()
297 BOOST_ASSERT(m_size <= N+1);
298 BOOST_SPIRIT_ASSERT_FSQ_SIZE;
299 BOOST_ASSERT(m_head <= N+1);
300 BOOST_ASSERT(m_tail <= N+1);
303 template <typename T, std::size_t N>
305 fixed_size_queue<T, N>::push_back(const T& e)
307 BOOST_ASSERT(m_size <= N+1);
308 BOOST_SPIRIT_ASSERT_FSQ_SIZE;
309 BOOST_ASSERT(m_head <= N+1);
310 BOOST_ASSERT(m_tail <= N+1);
312 BOOST_ASSERT(!full());
321 BOOST_ASSERT(m_size <= N+1);
322 BOOST_SPIRIT_ASSERT_FSQ_SIZE;
323 BOOST_ASSERT(m_head <= N+1);
324 BOOST_ASSERT(m_tail <= N+1);
327 template <typename T, std::size_t N>
329 fixed_size_queue<T, N>::push_front(const T& e)
331 BOOST_ASSERT(m_size <= N+1);
332 BOOST_SPIRIT_ASSERT_FSQ_SIZE;
333 BOOST_ASSERT(m_head <= N+1);
334 BOOST_ASSERT(m_tail <= N+1);
336 BOOST_ASSERT(!full());
346 BOOST_ASSERT(m_size <= N+1);
347 BOOST_SPIRIT_ASSERT_FSQ_SIZE;
348 BOOST_ASSERT(m_head <= N+1);
349 BOOST_ASSERT(m_tail <= N+1);
353 template <typename T, std::size_t N>
355 fixed_size_queue<T, N>::serve(T& e)
357 BOOST_ASSERT(m_size <= N+1);
358 BOOST_SPIRIT_ASSERT_FSQ_SIZE;
359 BOOST_ASSERT(m_head <= N+1);
360 BOOST_ASSERT(m_tail <= N+1);
368 template <typename T, std::size_t N>
370 fixed_size_queue<T, N>::pop_front()
372 BOOST_ASSERT(m_size <= N+1);
373 BOOST_SPIRIT_ASSERT_FSQ_SIZE;
374 BOOST_ASSERT(m_head <= N+1);
375 BOOST_ASSERT(m_tail <= N+1);
382 BOOST_ASSERT(m_size <= N+1);
383 BOOST_SPIRIT_ASSERT_FSQ_SIZE;
384 BOOST_ASSERT(m_head <= N+1);
385 BOOST_ASSERT(m_tail <= N+1);
390 #undef BOOST_SPIRIT_ASSERT_FSQ_SIZE