boost/spirit/home/support/iterators/detail/fixed_size_queue.hpp
// Copyright (c) 2001 Daniel C. Nuffer
// Copyright (c) 2001-2011 Hartmut Kaiser
//
// Distributed under the Boost Software License, Version 1.0. (See accompanying
// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
#if !defined(BOOST_SPIRIT_ITERATOR_FIXED_SIZE_QUEUE_MAR_16_2007_1137AM)
#define BOOST_SPIRIT_ITERATOR_FIXED_SIZE_QUEUE_MAR_16_2007_1137AM
#include <cstdlib>
#include <iterator>
#include <cstddef>
#include <boost/config.hpp>
#include <boost/assert.hpp> // for BOOST_ASSERT
#include <boost/iterator_adaptors.hpp>
///////////////////////////////////////////////////////////////////////////////
// Make sure we're using a decent version of the Boost.IteratorAdaptors lib
#if !defined(BOOST_ITERATOR_ADAPTORS_VERSION) || \
BOOST_ITERATOR_ADAPTORS_VERSION < 0x0200
#error "Please use at least Boost V1.31.0 while compiling the fixed_size_queue class!"
#endif
///////////////////////////////////////////////////////////////////////////////
#define BOOST_SPIRIT_ASSERT_FSQ_SIZE \
BOOST_ASSERT(((m_tail + N + 1) - m_head) % (N+1) == m_size % (N+1)) \
/**/
///////////////////////////////////////////////////////////////////////////////
namespace boost { namespace spirit { namespace detail
{
///////////////////////////////////////////////////////////////////////////
template <typename Queue, typename T, typename Pointer>
class fsq_iterator
: public boost::iterator_facade<
fsq_iterator<Queue, T, Pointer>, T,
std::random_access_iterator_tag
>
{
public:
typedef typename Queue::position_type position_type;
typedef boost::iterator_facade<
fsq_iterator<Queue, T, Pointer>, T,
std::random_access_iterator_tag
> base_type;
fsq_iterator() {}
fsq_iterator(position_type const &p_) : p(p_) {}
position_type &get_position() { return p; }
position_type const &get_position() const { return p; }
private:
friend class boost::iterator_core_access;
typename base_type::reference dereference() const
{
return p.self->m_queue[p.pos];
}
void increment()
{
++p.pos;
if (p.pos == Queue::MAX_SIZE+1)
p.pos = 0;
}
void decrement()
{
if (p.pos == 0)
p.pos = Queue::MAX_SIZE;
else
--p.pos;
}
bool is_eof() const
{
return p.self == 0 || p.pos == p.self->size();
}
template <typename Q, typename T_, typename P>
bool equal(fsq_iterator<Q, T_, P> const &x) const
{
if (is_eof())
return x.is_eof();
if (x.is_eof())
return false;
position_type const &rhs_pos = x.get_position();
return (p.self == rhs_pos.self) && (p.pos == rhs_pos.pos);
}
template <typename Q, typename T_, typename P>
typename base_type::difference_type distance_to(
fsq_iterator<Q, T_, P> const &x) const
{
typedef typename base_type::difference_type difference_type;
position_type const &p2 = x.get_position();
std::size_t pos1 = p.pos;
std::size_t pos2 = p2.pos;
// Undefined behavior if the iterators come from different
// containers
BOOST_ASSERT(p.self == p2.self);
if (pos1 < p.self->m_head)
pos1 += Queue::MAX_SIZE;
if (pos2 < p2.self->m_head)
pos2 += Queue::MAX_SIZE;
if (pos2 > pos1)
return difference_type(pos2 - pos1);
else
return -difference_type(pos1 - pos2);
}
void advance(typename base_type::difference_type n)
{
// Notice that we don't care values of n that can
// wrap around more than one time, since it would
// be undefined behavior anyway (going outside
// the begin/end range). Negative wrapping is a bit
// cumbersome because we don't want to case p.pos
// to signed.
if (n < 0)
{
n = -n;
if (p.pos < (std::size_t)n)
p.pos = Queue::MAX_SIZE+1 - (n - p.pos);
else
p.pos -= n;
}
else
{
p.pos += n;
if (p.pos >= Queue::MAX_SIZE+1)
p.pos -= Queue::MAX_SIZE+1;
}
}
private:
position_type p;
};
///////////////////////////////////////////////////////////////////////////
template <typename T, std::size_t N>
class fixed_size_queue
{
private:
struct position
{
fixed_size_queue* self;
std::size_t pos;
position() : self(0), pos(0) {}
// The const_cast here is just to avoid to have two different
// position structures for the const and non-const case.
// The const semantic is guaranteed by the iterator itself
position(const fixed_size_queue* s, std::size_t p)
: self(const_cast<fixed_size_queue*>(s)), pos(p)
{}
bool is_initialized() const { return self != 0; }
void set_queue(fixed_size_queue* q) { self = q; }
};
public:
// Declare the iterators
typedef fsq_iterator<fixed_size_queue<T, N>, T, T*> iterator;
typedef
fsq_iterator<fixed_size_queue<T, N>, T const, T const*>
const_iterator;
typedef position position_type;
friend class fsq_iterator<fixed_size_queue<T, N>, T, T*>;
friend class fsq_iterator<fixed_size_queue<T, N>, T const, T const*>;
fixed_size_queue();
fixed_size_queue(const fixed_size_queue& x);
fixed_size_queue& operator=(const fixed_size_queue& x);
~fixed_size_queue();
void push_back(const T& e);
void push_front(const T& e);
void serve(T& e);
void pop_front();
bool empty() const
{
return m_size == 0;
}
bool full() const
{
return m_size == N;
}
iterator begin()
{
return iterator(position(this, m_head));
}
const_iterator begin() const
{
return const_iterator(position(this, m_head));
}
iterator end()
{
return iterator(position(0, m_tail));
}
const_iterator end() const
{
return const_iterator(position(0, m_tail));
}
std::size_t size() const
{
return m_size;
}
T& front()
{
return m_queue[m_head];
}
const T& front() const
{
return m_queue[m_head];
}
private:
// Redefine the template parameters to avoid using partial template
// specialization on the iterator policy to extract N.
BOOST_STATIC_CONSTANT(std::size_t, MAX_SIZE = N);
std::size_t m_head;
std::size_t m_tail;
std::size_t m_size;
T m_queue[N+1];
};
template <typename T, std::size_t N>
inline
fixed_size_queue<T, N>::fixed_size_queue()
: m_head(0)
, m_tail(0)
, m_size(0)
{
BOOST_ASSERT(m_size <= N+1);
BOOST_SPIRIT_ASSERT_FSQ_SIZE;
BOOST_ASSERT(m_head <= N+1);
BOOST_ASSERT(m_tail <= N+1);
}
template <typename T, std::size_t N>
inline
fixed_size_queue<T, N>::fixed_size_queue(const fixed_size_queue& x)
: m_head(x.m_head)
, m_tail(x.m_tail)
, m_size(x.m_size)
{
copy(x.begin(), x.end(), begin());
BOOST_ASSERT(m_size <= N+1);
BOOST_SPIRIT_ASSERT_FSQ_SIZE;
BOOST_ASSERT(m_head <= N+1);
BOOST_ASSERT(m_tail <= N+1);
}
template <typename T, std::size_t N>
inline fixed_size_queue<T, N>&
fixed_size_queue<T, N>::operator=(const fixed_size_queue& x)
{
if (this != &x)
{
m_head = x.m_head;
m_tail = x.m_tail;
m_size = x.m_size;
copy(x.begin(), x.end(), begin());
}
BOOST_ASSERT(m_size <= N+1);
BOOST_SPIRIT_ASSERT_FSQ_SIZE;
BOOST_ASSERT(m_head <= N+1);
BOOST_ASSERT(m_tail <= N+1);
return *this;
}
template <typename T, std::size_t N>
inline
fixed_size_queue<T, N>::~fixed_size_queue()
{
BOOST_ASSERT(m_size <= N+1);
BOOST_SPIRIT_ASSERT_FSQ_SIZE;
BOOST_ASSERT(m_head <= N+1);
BOOST_ASSERT(m_tail <= N+1);
}
template <typename T, std::size_t N>
inline void
fixed_size_queue<T, N>::push_back(const T& e)
{
BOOST_ASSERT(m_size <= N+1);
BOOST_SPIRIT_ASSERT_FSQ_SIZE;
BOOST_ASSERT(m_head <= N+1);
BOOST_ASSERT(m_tail <= N+1);
BOOST_ASSERT(!full());
m_queue[m_tail] = e;
++m_size;
++m_tail;
if (m_tail == N+1)
m_tail = 0;
BOOST_ASSERT(m_size <= N+1);
BOOST_SPIRIT_ASSERT_FSQ_SIZE;
BOOST_ASSERT(m_head <= N+1);
BOOST_ASSERT(m_tail <= N+1);
}
template <typename T, std::size_t N>
inline void
fixed_size_queue<T, N>::push_front(const T& e)
{
BOOST_ASSERT(m_size <= N+1);
BOOST_SPIRIT_ASSERT_FSQ_SIZE;
BOOST_ASSERT(m_head <= N+1);
BOOST_ASSERT(m_tail <= N+1);
BOOST_ASSERT(!full());
if (m_head == 0)
m_head = N;
else
--m_head;
m_queue[m_head] = e;
++m_size;
BOOST_ASSERT(m_size <= N+1);
BOOST_SPIRIT_ASSERT_FSQ_SIZE;
BOOST_ASSERT(m_head <= N+1);
BOOST_ASSERT(m_tail <= N+1);
}
template <typename T, std::size_t N>
inline void
fixed_size_queue<T, N>::serve(T& e)
{
BOOST_ASSERT(m_size <= N+1);
BOOST_SPIRIT_ASSERT_FSQ_SIZE;
BOOST_ASSERT(m_head <= N+1);
BOOST_ASSERT(m_tail <= N+1);
e = m_queue[m_head];
pop_front();
}
template <typename T, std::size_t N>
inline void
fixed_size_queue<T, N>::pop_front()
{
BOOST_ASSERT(m_size <= N+1);
BOOST_SPIRIT_ASSERT_FSQ_SIZE;
BOOST_ASSERT(m_head <= N+1);
BOOST_ASSERT(m_tail <= N+1);
++m_head;
if (m_head == N+1)
m_head = 0;
--m_size;
BOOST_ASSERT(m_size <= N+1);
BOOST_SPIRIT_ASSERT_FSQ_SIZE;
BOOST_ASSERT(m_head <= N+1);
BOOST_ASSERT(m_tail <= N+1);
}
}}}
#undef BOOST_SPIRIT_ASSERT_FSQ_SIZE
#endif