/*============================================================================= | |
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 |