boost/spirit/home/classic/iterator/fixed_size_queue.hpp
/*=============================================================================
Copyright (c) 2001, Daniel C. Nuffer
Copyright (c) 2003, Hartmut Kaiser
http://spirit.sourceforge.net/
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)
=============================================================================*/
#ifndef FIXED_SIZE_QUEUE
#define FIXED_SIZE_QUEUE
#include <cstdlib>
#include <iterator>
#include <cstddef>
#include <boost/spirit/home/classic/namespace.hpp>
#include <boost/spirit/home/classic/core/assert.hpp> // for BOOST_SPIRIT_ASSERT
// FIXES for broken compilers
#include <boost/config.hpp>
#include <boost/iterator_adaptors.hpp>
#define BOOST_SPIRIT_ASSERT_FSQ_SIZE \
BOOST_SPIRIT_ASSERT(((m_tail + N + 1) - m_head) % (N+1) == m_size % (N+1)) \
/**/
///////////////////////////////////////////////////////////////////////////////
namespace boost { namespace spirit {
BOOST_SPIRIT_CLASSIC_NAMESPACE_BEGIN
///////////////////////////////////////////////////////////////////////////////
namespace impl {
#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!"
#else // BOOST_ITERATOR_ADAPTORS_VERSION < 0x0200
template <typename QueueT, typename T, typename PointerT>
class fsq_iterator
: public boost::iterator_adaptor<
fsq_iterator<QueueT, T, PointerT>,
PointerT,
T,
std::random_access_iterator_tag
>
{
public:
typedef typename QueueT::position_t position;
typedef boost::iterator_adaptor<
fsq_iterator<QueueT, T, PointerT>, PointerT, T,
std::random_access_iterator_tag
> base_t;
fsq_iterator() {}
fsq_iterator(position const &p_) : p(p_) {}
position const &get_position() const { return p; }
private:
friend class boost::iterator_core_access;
typename base_t::reference dereference() const
{
return p.self->m_queue[p.pos];
}
void increment()
{
++p.pos;
if (p.pos == QueueT::MAX_SIZE+1)
p.pos = 0;
}
void decrement()
{
if (p.pos == 0)
p.pos = QueueT::MAX_SIZE;
else
--p.pos;
}
template <
typename OtherDerivedT, typename OtherIteratorT,
typename V, typename C, typename R, typename D
>
bool equal(iterator_adaptor<OtherDerivedT, OtherIteratorT, V, C, R, D>
const &x) const
{
position const &rhs_pos =
static_cast<OtherDerivedT const &>(x).get_position();
return (p.self == rhs_pos.self) && (p.pos == rhs_pos.pos);
}
template <
typename OtherDerivedT, typename OtherIteratorT,
typename V, typename C, typename R, typename D
>
typename base_t::difference_type distance_to(
iterator_adaptor<OtherDerivedT, OtherIteratorT, V, C, R, D>
const &x) const
{
typedef typename base_t::difference_type diff_t;
position const &p2 =
static_cast<OtherDerivedT const &>(x).get_position();
std::size_t pos1 = p.pos;
std::size_t pos2 = p2.pos;
// Undefined behaviour if the iterators come from different
// containers
BOOST_SPIRIT_ASSERT(p.self == p2.self);
if (pos1 < p.self->m_head)
pos1 += QueueT::MAX_SIZE;
if (pos2 < p2.self->m_head)
pos2 += QueueT::MAX_SIZE;
if (pos2 > pos1)
return diff_t(pos2 - pos1);
else
return -diff_t(pos1 - pos2);
}
void advance(typename base_t::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 behaviour 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 = QueueT::MAX_SIZE+1 - (n - p.pos);
else
p.pos -= n;
}
else
{
p.pos += n;
if (p.pos >= QueueT::MAX_SIZE+1)
p.pos -= QueueT::MAX_SIZE+1;
}
}
private:
position p;
};
#endif // BOOST_ITERATOR_ADAPTORS_VERSION < 0x0200
///////////////////////////////////////////////////////////////////////////////
} /* namespace impl */
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)
{}
};
public:
// Declare the iterators
typedef impl::fsq_iterator<fixed_size_queue<T, N>, T, T*> iterator;
typedef impl::fsq_iterator<fixed_size_queue<T, N>, T const, T const*>
const_iterator;
typedef position position_t;
friend class impl::fsq_iterator<fixed_size_queue<T, N>, T, T*>;
friend class impl::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(this, m_tail));
}
const_iterator end() const
{
return const_iterator(position(this, 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_SPIRIT_ASSERT(m_size <= N+1);
BOOST_SPIRIT_ASSERT_FSQ_SIZE;
BOOST_SPIRIT_ASSERT(m_head <= N+1);
BOOST_SPIRIT_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_SPIRIT_ASSERT(m_size <= N+1);
BOOST_SPIRIT_ASSERT_FSQ_SIZE;
BOOST_SPIRIT_ASSERT(m_head <= N+1);
BOOST_SPIRIT_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_SPIRIT_ASSERT(m_size <= N+1);
BOOST_SPIRIT_ASSERT_FSQ_SIZE;
BOOST_SPIRIT_ASSERT(m_head <= N+1);
BOOST_SPIRIT_ASSERT(m_tail <= N+1);
return *this;
}
template <typename T, std::size_t N>
inline
fixed_size_queue<T, N>::~fixed_size_queue()
{
BOOST_SPIRIT_ASSERT(m_size <= N+1);
BOOST_SPIRIT_ASSERT_FSQ_SIZE;
BOOST_SPIRIT_ASSERT(m_head <= N+1);
BOOST_SPIRIT_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_SPIRIT_ASSERT(m_size <= N+1);
BOOST_SPIRIT_ASSERT_FSQ_SIZE;
BOOST_SPIRIT_ASSERT(m_head <= N+1);
BOOST_SPIRIT_ASSERT(m_tail <= N+1);
BOOST_SPIRIT_ASSERT(!full());
m_queue[m_tail] = e;
++m_size;
++m_tail;
if (m_tail == N+1)
m_tail = 0;
BOOST_SPIRIT_ASSERT(m_size <= N+1);
BOOST_SPIRIT_ASSERT_FSQ_SIZE;
BOOST_SPIRIT_ASSERT(m_head <= N+1);
BOOST_SPIRIT_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_SPIRIT_ASSERT(m_size <= N+1);
BOOST_SPIRIT_ASSERT_FSQ_SIZE;
BOOST_SPIRIT_ASSERT(m_head <= N+1);
BOOST_SPIRIT_ASSERT(m_tail <= N+1);
BOOST_SPIRIT_ASSERT(!full());
if (m_head == 0)
m_head = N;
else
--m_head;
m_queue[m_head] = e;
++m_size;
BOOST_SPIRIT_ASSERT(m_size <= N+1);
BOOST_SPIRIT_ASSERT_FSQ_SIZE;
BOOST_SPIRIT_ASSERT(m_head <= N+1);
BOOST_SPIRIT_ASSERT(m_tail <= N+1);
}
template <typename T, std::size_t N>
inline void
fixed_size_queue<T, N>::serve(T& e)
{
BOOST_SPIRIT_ASSERT(m_size <= N+1);
BOOST_SPIRIT_ASSERT_FSQ_SIZE;
BOOST_SPIRIT_ASSERT(m_head <= N+1);
BOOST_SPIRIT_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_SPIRIT_ASSERT(m_size <= N+1);
BOOST_SPIRIT_ASSERT_FSQ_SIZE;
BOOST_SPIRIT_ASSERT(m_head <= N+1);
BOOST_SPIRIT_ASSERT(m_tail <= N+1);
++m_head;
if (m_head == N+1)
m_head = 0;
--m_size;
BOOST_SPIRIT_ASSERT(m_size <= N+1);
BOOST_SPIRIT_ASSERT_FSQ_SIZE;
BOOST_SPIRIT_ASSERT(m_head <= N+1);
BOOST_SPIRIT_ASSERT(m_tail <= N+1);
}
///////////////////////////////////////////////////////////////////////////////
BOOST_SPIRIT_CLASSIC_NAMESPACE_END
}} // namespace BOOST_SPIRIT_CLASSIC_NS
#undef BOOST_SPIRIT_ASSERT_FSQ_SIZE
#endif
