1 /*=============================================================================
2 Copyright (c) 2001, Daniel C. Nuffer
3 Copyright (c) 2003, Hartmut Kaiser
4 http://spirit.sourceforge.net/
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 FIXED_SIZE_QUEUE
10 #define FIXED_SIZE_QUEUE
16 #include <boost/spirit/home/classic/namespace.hpp>
17 #include <boost/spirit/home/classic/core/assert.hpp> // for BOOST_SPIRIT_ASSERT
19 // FIXES for broken compilers
20 #include <boost/config.hpp>
21 #include <boost/iterator_adaptors.hpp>
23 #define BOOST_SPIRIT_ASSERT_FSQ_SIZE \
24 BOOST_SPIRIT_ASSERT(((m_tail + N + 1) - m_head) % (N+1) == m_size % (N+1)) \
27 ///////////////////////////////////////////////////////////////////////////////
28 namespace boost { namespace spirit {
30 BOOST_SPIRIT_CLASSIC_NAMESPACE_BEGIN
32 ///////////////////////////////////////////////////////////////////////////////
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
40 template <typename QueueT, typename T, typename PointerT>
42 : public boost::iterator_adaptor<
43 fsq_iterator<QueueT, T, PointerT>,
46 std::random_access_iterator_tag
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
57 fsq_iterator(position const &p_) : p(p_) {}
59 position const &get_position() const { return p; }
62 friend class boost::iterator_core_access;
64 typename base_t::reference dereference() const
66 return p.self->m_queue[p.pos];
72 if (p.pos == QueueT::MAX_SIZE+1)
79 p.pos = QueueT::MAX_SIZE;
85 typename OtherDerivedT, typename OtherIteratorT,
86 typename V, typename C, typename R, typename D
88 bool equal(iterator_adaptor<OtherDerivedT, OtherIteratorT, V, C, R, D>
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);
97 typename OtherDerivedT, typename OtherIteratorT,
98 typename V, typename C, typename R, typename D
100 typename base_t::difference_type distance_to(
101 iterator_adaptor<OtherDerivedT, OtherIteratorT, V, C, R, D>
104 typedef typename base_t::difference_type diff_t;
107 static_cast<OtherDerivedT const &>(x).get_position();
108 std::size_t pos1 = p.pos;
109 std::size_t pos2 = p2.pos;
111 // Undefined behaviour if the iterators come from different
113 BOOST_SPIRIT_ASSERT(p.self == p2.self);
115 if (pos1 < p.self->m_head)
116 pos1 += QueueT::MAX_SIZE;
117 if (pos2 < p2.self->m_head)
118 pos2 += QueueT::MAX_SIZE;
121 return diff_t(pos2 - pos1);
123 return -diff_t(pos1 - pos2);
126 void advance(typename base_t::difference_type n)
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
137 if (p.pos < (std::size_t)n)
138 p.pos = QueueT::MAX_SIZE+1 - (n - p.pos);
145 if (p.pos >= QueueT::MAX_SIZE+1)
146 p.pos -= QueueT::MAX_SIZE+1;
154 #endif // BOOST_ITERATOR_ADAPTORS_VERSION < 0x0200
156 ///////////////////////////////////////////////////////////////////////////////
157 } /* namespace impl */
159 template <typename T, std::size_t N>
160 class fixed_size_queue
165 fixed_size_queue* self;
168 position() : self(0), pos(0) {}
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)
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*>
183 typedef position position_t;
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*>;
189 fixed_size_queue(const fixed_size_queue& x);
190 fixed_size_queue& operator=(const fixed_size_queue& x);
193 void push_back(const T& e);
194 void push_front(const T& e);
210 return iterator(position(this, m_head));
213 const_iterator begin() const
215 return const_iterator(position(this, m_head));
220 return iterator(position(this, m_tail));
223 const_iterator end() const
225 return const_iterator(position(this, m_tail));
228 std::size_t size() const
235 return m_queue[m_head];
238 const T& front() const
240 return m_queue[m_head];
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);
254 template <typename T, std::size_t N>
256 fixed_size_queue<T, N>::fixed_size_queue()
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);
267 template <typename T, std::size_t N>
269 fixed_size_queue<T, N>::fixed_size_queue(const fixed_size_queue& x)
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);
281 template <typename T, std::size_t N>
282 inline fixed_size_queue<T, N>&
283 fixed_size_queue<T, N>::operator=(const fixed_size_queue& x)
290 copy(x.begin(), x.end(), begin());
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);
300 template <typename T, std::size_t N>
302 fixed_size_queue<T, N>::~fixed_size_queue()
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);
310 template <typename T, std::size_t N>
312 fixed_size_queue<T, N>::push_back(const T& e)
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);
319 BOOST_SPIRIT_ASSERT(!full());
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);
334 template <typename T, std::size_t N>
336 fixed_size_queue<T, N>::push_front(const T& e)
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);
343 BOOST_SPIRIT_ASSERT(!full());
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);
360 template <typename T, std::size_t N>
362 fixed_size_queue<T, N>::serve(T& e)
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);
375 template <typename T, std::size_t N>
377 fixed_size_queue<T, N>::pop_front()
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);
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);
395 ///////////////////////////////////////////////////////////////////////////////
396 BOOST_SPIRIT_CLASSIC_NAMESPACE_END
398 }} // namespace BOOST_SPIRIT_CLASSIC_NS
400 #undef BOOST_SPIRIT_ASSERT_FSQ_SIZE