123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392 |
- // 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
|