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