third_party/boost/include/boost/spirit/home/support/iterators/detail/fixed_size_queue.hpp - webm/webmlive - Git at Google

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