Chris@16: // Implementation of the base circular buffer.
Chris@16: 
Chris@16: // Copyright (c) 2003-2008 Jan Gaspar
Chris@16: // Copyright (c) 2013 Paul A. Bristow  // Doxygen comments changed.
Chris@16: // Copyright (c) 2013 Antony Polukhin  // Move semantics implementation.
Chris@101: // Copyright (c) 2014 Glen Fernandes   // C++11 allocator model support.
Chris@16: 
Chris@16: // Use, modification, and distribution is subject to the Boost Software
Chris@16: // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #if !defined(BOOST_CIRCULAR_BUFFER_BASE_HPP)
Chris@16: #define BOOST_CIRCULAR_BUFFER_BASE_HPP
Chris@16: 
Chris@101: #if defined(_MSC_VER)
Chris@16:     #pragma once
Chris@16: #endif
Chris@16: 
Chris@16: #include <boost/config.hpp>
Chris@16: #include <boost/call_traits.hpp>
Chris@16: #include <boost/concept_check.hpp>
Chris@16: #include <boost/limits.hpp>
Chris@101: #include <boost/container/allocator_traits.hpp>
Chris@16: #include <boost/iterator/reverse_iterator.hpp>
Chris@16: #include <boost/iterator/iterator_traits.hpp>
Chris@16: #include <boost/type_traits/is_stateless.hpp>
Chris@16: #include <boost/type_traits/is_integral.hpp>
Chris@16: #include <boost/type_traits/is_scalar.hpp>
Chris@16: #include <boost/type_traits/is_nothrow_move_constructible.hpp>
Chris@16: #include <boost/type_traits/is_nothrow_move_assignable.hpp>
Chris@16: #include <boost/type_traits/is_copy_constructible.hpp>
Chris@16: #include <boost/type_traits/conditional.hpp>
Chris@16: #include <boost/move/move.hpp>
Chris@101: #include <boost/utility/addressof.hpp>
Chris@16: #include <algorithm>
Chris@16: #include <utility>
Chris@16: #include <deque>
Chris@16: #include <stdexcept>
Chris@101: 
Chris@16: #if BOOST_WORKAROUND(__MWERKS__, BOOST_TESTED_AT(0x3205))
Chris@16:     #include <stddef.h>
Chris@16: #endif
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16: /*!
Chris@16:     \class circular_buffer
Chris@16:     \brief Circular buffer - a STL compliant container.
Chris@16:     \tparam T The type of the elements stored in the <code>circular_buffer</code>.
Chris@16:     \par Type Requirements T
Chris@16:          The <code>T</code> has to be <a href="http://www.sgi.com/tech/stl/Assignable.html">
Chris@16:          SGIAssignable</a> (SGI STL defined combination of <a href="../../../utility/Assignable.html">
Chris@16:          Assignable</a> and <a href="../../../utility/CopyConstructible.html">CopyConstructible</a>).
Chris@16:          Moreover <code>T</code> has to be <a href="http://www.sgi.com/tech/stl/DefaultConstructible.html">
Chris@16:          DefaultConstructible</a> if supplied as a default parameter when invoking some of the
Chris@16:          <code>circular_buffer</code>'s methods e.g.
Chris@16:          <code>insert(iterator pos, const value_type& item = %value_type())</code>. And
Chris@16:          <a href="http://www.sgi.com/tech/stl/EqualityComparable.html">EqualityComparable</a> and/or
Chris@16:          <a href="../../../utility/LessThanComparable.html">LessThanComparable</a> if the <code>circular_buffer</code>
Chris@16:          will be compared with another container.
Chris@16:     \tparam Alloc The allocator type used for all internal memory management.
Chris@16:     \par Type Requirements Alloc
Chris@16:          The <code>Alloc</code> has to meet the allocator requirements imposed by STL.
Chris@16:     \par Default Alloc
Chris@16:          std::allocator<T>
Chris@16: 
Chris@16:     For detailed documentation of the circular_buffer visit:
Chris@16:     http://www.boost.org/libs/circular_buffer/doc/circular_buffer.html
Chris@16: */
Chris@16: template <class T, class Alloc>
Chris@16: class circular_buffer
Chris@16: /*! \cond */
Chris@16: #if BOOST_CB_ENABLE_DEBUG
Chris@16: : public cb_details::debug_iterator_registry
Chris@16: #endif
Chris@16: /*! \endcond */
Chris@16: {
Chris@16: 
Chris@16:   // Requirements
Chris@16:     //BOOST_CLASS_REQUIRE(T, boost, SGIAssignableConcept);
Chris@16: 
Chris@16: 
Chris@16:     //BOOST_CONCEPT_ASSERT((Assignable<T>));
Chris@16:     //BOOST_CONCEPT_ASSERT((CopyConstructible<T>));
Chris@16:     //BOOST_CONCEPT_ASSERT((DefaultConstructible<T>));
Chris@16: 
Chris@16:     // Required if the circular_buffer will be compared with anther container.
Chris@16:     //BOOST_CONCEPT_ASSERT((EqualityComparable<T>));
Chris@16:     //BOOST_CONCEPT_ASSERT((LessThanComparable<T>));
Chris@16: 
Chris@16: public:
Chris@16: // Basic types
Chris@16:     
Chris@16:     //! The type of this <code>circular_buffer</code>.
Chris@16:     typedef circular_buffer<T, Alloc> this_type;
Chris@16: 
Chris@16:     //! The type of elements stored in the <code>circular_buffer</code>.
Chris@101:     typedef typename boost::container::allocator_traits<Alloc>::value_type value_type;
Chris@16: 
Chris@16:     //! A pointer to an element.
Chris@101:     typedef typename boost::container::allocator_traits<Alloc>::pointer pointer;
Chris@16: 
Chris@16:     //! A const pointer to the element.
Chris@101:     typedef typename boost::container::allocator_traits<Alloc>::const_pointer const_pointer;
Chris@16: 
Chris@16:     //! A reference to an element.
Chris@101:     typedef typename boost::container::allocator_traits<Alloc>::reference reference;
Chris@16: 
Chris@16:     //! A const reference to an element.
Chris@101:     typedef typename boost::container::allocator_traits<Alloc>::const_reference const_reference;
Chris@16: 
Chris@16:     //! The distance type.
Chris@16:     /*!
Chris@16:         (A signed integral type used to represent the distance between two iterators.)
Chris@16:     */
Chris@101:     typedef typename boost::container::allocator_traits<Alloc>::difference_type difference_type;
Chris@16: 
Chris@16:     //! The size type.
Chris@16:     /*!
Chris@16:         (An unsigned integral type that can represent any non-negative value of the container's distance type.)
Chris@16:     */
Chris@101:     typedef typename boost::container::allocator_traits<Alloc>::size_type size_type;
Chris@16: 
Chris@16:     //! The type of an allocator used in the <code>circular_buffer</code>.
Chris@16:     typedef Alloc allocator_type;
Chris@16: 
Chris@16: // Iterators
Chris@16: 
Chris@16:     //! A const (random access) iterator used to iterate through the <code>circular_buffer</code>.
Chris@101:     typedef cb_details::iterator< circular_buffer<T, Alloc>, cb_details::const_traits<boost::container::allocator_traits<Alloc> > > const_iterator;
Chris@16: 
Chris@16:     //! A (random access) iterator used to iterate through the <code>circular_buffer</code>.
Chris@101:     typedef cb_details::iterator< circular_buffer<T, Alloc>, cb_details::nonconst_traits<boost::container::allocator_traits<Alloc> > > iterator;
Chris@16: 
Chris@16:     //! A const iterator used to iterate backwards through a <code>circular_buffer</code>.
Chris@16:     typedef boost::reverse_iterator<const_iterator> const_reverse_iterator;
Chris@16: 
Chris@16:     //! An iterator used to iterate backwards through a <code>circular_buffer</code>.
Chris@16:     typedef boost::reverse_iterator<iterator> reverse_iterator;
Chris@16: 
Chris@16: // Container specific types
Chris@16: 
Chris@16:     //! An array range.
Chris@16:     /*!
Chris@16:         (A typedef for the <a href="http://www.sgi.com/tech/stl/pair.html"><code>std::pair</code></a> where
Chris@16:         its first element is a pointer to a beginning of an array and its second element represents
Chris@16:         a size of the array.)
Chris@16:     */
Chris@16:     typedef std::pair<pointer, size_type> array_range;
Chris@16: 
Chris@16:     //! A range of a const array.
Chris@16:     /*!
Chris@16:         (A typedef for the <a href="http://www.sgi.com/tech/stl/pair.html"><code>std::pair</code></a> where
Chris@16:         its first element is a pointer to a beginning of a const array and its second element represents
Chris@16:         a size of the const array.)
Chris@16:     */
Chris@16:     typedef std::pair<const_pointer, size_type> const_array_range;
Chris@16: 
Chris@16:     //! The capacity type.
Chris@16:     /*!
Chris@16:         (Same as <code>size_type</code> - defined for consistency with the  __cbso class.
Chris@16: 
Chris@16:     */
Chris@16:     // <a href="space_optimized.html"><code>circular_buffer_space_optimized</code></a>.)
Chris@16: 
Chris@16:     typedef size_type capacity_type;
Chris@16: 
Chris@16: // Helper types
Chris@16: 
Chris@16:     //! A type representing the "best" way to pass the value_type to a method.
Chris@16:     typedef const value_type& param_value_type;
Chris@16: 
Chris@16:     //! A type representing rvalue from param type.
Chris@16:     //! On compilers without rvalue references support this type is the Boost.Moves type used for emulation.
Chris@16:     typedef BOOST_RV_REF(value_type) rvalue_type;
Chris@16: 
Chris@16: private:
Chris@16: // Member variables
Chris@16: 
Chris@16:     //! The internal buffer used for storing elements in the circular buffer.
Chris@16:     pointer m_buff;
Chris@16: 
Chris@16:     //! The internal buffer's end (end of the storage space).
Chris@16:     pointer m_end;
Chris@16: 
Chris@16:     //! The virtual beginning of the circular buffer.
Chris@16:     pointer m_first;
Chris@16: 
Chris@16:     //! The virtual end of the circular buffer (one behind the last element).
Chris@16:     pointer m_last;
Chris@16: 
Chris@16:     //! The number of items currently stored in the circular buffer.
Chris@16:     size_type m_size;
Chris@16: 
Chris@16:     //! The allocator.
Chris@16:     allocator_type m_alloc;
Chris@16: 
Chris@16: // Friends
Chris@16: #if defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
Chris@16:     friend iterator;
Chris@16:     friend const_iterator;
Chris@16: #else
Chris@16:     template <class Buff, class Traits> friend struct cb_details::iterator;
Chris@16: #endif
Chris@16: 
Chris@16: public:
Chris@16: // Allocator
Chris@16: 
Chris@16:     //! Get the allocator.
Chris@16:     /*!
Chris@16:         \return The allocator.
Chris@16:         \throws Nothing.
Chris@16:         \par Exception Safety
Chris@16:              No-throw.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>get_allocator()</code> for obtaining an allocator %reference.
Chris@16:     */
Chris@16:     allocator_type get_allocator() const BOOST_NOEXCEPT { return m_alloc; }
Chris@16: 
Chris@16:     //! Get the allocator reference.
Chris@16:     /*!
Chris@16:         \return A reference to the allocator.
Chris@16:         \throws Nothing.
Chris@16:         \par Exception Safety
Chris@16:              No-throw.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \note This method was added in order to optimize obtaining of the allocator with a state,
Chris@16:               although use of stateful allocators in STL is discouraged.
Chris@16:         \sa <code>get_allocator() const</code>
Chris@16:     */
Chris@16:     allocator_type& get_allocator() BOOST_NOEXCEPT { return m_alloc; }
Chris@16: 
Chris@16: // Element access
Chris@16: 
Chris@16:     //! Get the iterator pointing to the beginning of the <code>circular_buffer</code>.
Chris@16:     /*!
Chris@16:         \return A random access iterator pointing to the first element of the <code>circular_buffer</code>. If the
Chris@16:                 <code>circular_buffer</code> is empty it returns an iterator equal to the one returned by
Chris@16:                 <code>end()</code>.
Chris@16:         \throws Nothing.
Chris@16:         \par Exception Safety
Chris@16:              No-throw.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>end()</code>, <code>rbegin()</code>, <code>rend()</code>
Chris@16:     */
Chris@16:     iterator begin() BOOST_NOEXCEPT { return iterator(this, empty() ? 0 : m_first); }
Chris@16: 
Chris@16:     //! Get the iterator pointing to the end of the <code>circular_buffer</code>.
Chris@16:     /*!
Chris@16:         \return A random access iterator pointing to the element "one behind" the last element of the <code>
Chris@16:                 circular_buffer</code>. If the <code>circular_buffer</code> is empty it returns an iterator equal to
Chris@16:                 the one returned by <code>begin()</code>.
Chris@16:         \throws Nothing.
Chris@16:         \par Exception Safety
Chris@16:              No-throw.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>begin()</code>, <code>rbegin()</code>, <code>rend()</code>
Chris@16:     */
Chris@16:     iterator end() BOOST_NOEXCEPT { return iterator(this, 0); }
Chris@16: 
Chris@16:     //! Get the const iterator pointing to the beginning of the <code>circular_buffer</code>.
Chris@16:     /*!
Chris@16:         \return A const random access iterator pointing to the first element of the <code>circular_buffer</code>. If
Chris@16:                 the <code>circular_buffer</code> is empty it returns an iterator equal to the one returned by
Chris@16:                 <code>end() const</code>.
Chris@16:         \throws Nothing.
Chris@16:         \par Exception Safety
Chris@16:              No-throw.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>end() const</code>, <code>rbegin() const</code>, <code>rend() const</code>
Chris@16:     */
Chris@16:     const_iterator begin() const BOOST_NOEXCEPT { return const_iterator(this, empty() ? 0 : m_first); }
Chris@16: 
Chris@16:     //! Get the const iterator pointing to the end of the <code>circular_buffer</code>.
Chris@16:     /*!
Chris@16:         \return A const random access iterator pointing to the element "one behind" the last element of the <code>
Chris@16:                 circular_buffer</code>. If the <code>circular_buffer</code> is empty it returns an iterator equal to
Chris@16:                 the one returned by <code>begin() const</code> const.
Chris@16:         \throws Nothing.
Chris@16:         \par Exception Safety
Chris@16:              No-throw.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>begin() const</code>, <code>rbegin() const</code>, <code>rend() const</code>
Chris@16:     */
Chris@16:     const_iterator end() const BOOST_NOEXCEPT { return const_iterator(this, 0); }
Chris@16: 
Chris@16:     //! Get the iterator pointing to the beginning of the "reversed" <code>circular_buffer</code>.
Chris@16:     /*!
Chris@16:         \return A reverse random access iterator pointing to the last element of the <code>circular_buffer</code>.
Chris@16:                 If the <code>circular_buffer</code> is empty it returns an iterator equal to the one returned by
Chris@16:                 <code>rend()</code>.
Chris@16:         \throws Nothing.
Chris@16:         \par Exception Safety
Chris@16:              No-throw.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>rend()</code>, <code>begin()</code>, <code>end()</code>
Chris@16:     */
Chris@16:     reverse_iterator rbegin() BOOST_NOEXCEPT { return reverse_iterator(end()); }
Chris@16: 
Chris@16:     //! Get the iterator pointing to the end of the "reversed" <code>circular_buffer</code>.
Chris@16:     /*!
Chris@16:         \return A reverse random access iterator pointing to the element "one before" the first element of the <code>
Chris@16:                 circular_buffer</code>. If the <code>circular_buffer</code> is empty it returns an iterator equal to
Chris@16:                 the one returned by <code>rbegin()</code>.
Chris@16:         \throws Nothing.
Chris@16:         \par Exception Safety
Chris@16:              No-throw.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>rbegin()</code>, <code>begin()</code>, <code>end()</code>
Chris@16:     */
Chris@16:     reverse_iterator rend() BOOST_NOEXCEPT { return reverse_iterator(begin()); }
Chris@16: 
Chris@16:     //! Get the const iterator pointing to the beginning of the "reversed" <code>circular_buffer</code>.
Chris@16:     /*!
Chris@16:         \return A const reverse random access iterator pointing to the last element of the
Chris@16:                 <code>circular_buffer</code>. If the <code>circular_buffer</code> is empty it returns an iterator equal
Chris@16:                 to the one returned by <code>rend() const</code>.
Chris@16:         \throws Nothing.
Chris@16:         \par Exception Safety
Chris@16:              No-throw.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>rend() const</code>, <code>begin() const</code>, <code>end() const</code>
Chris@16:     */
Chris@16:     const_reverse_iterator rbegin() const BOOST_NOEXCEPT { return const_reverse_iterator(end()); }
Chris@16: 
Chris@16:     //! Get the const iterator pointing to the end of the "reversed" <code>circular_buffer</code>.
Chris@16:     /*!
Chris@16:         \return A const reverse random access iterator pointing to the element "one before" the first element of the
Chris@16:                 <code>circular_buffer</code>. If the <code>circular_buffer</code> is empty it returns an iterator equal
Chris@16:                 to the one returned by <code>rbegin() const</code>.
Chris@16:         \throws Nothing.
Chris@16:         \par Exception Safety
Chris@16:              No-throw.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>rbegin() const</code>, <code>begin() const</code>, <code>end() const</code>
Chris@16:     */
Chris@16:     const_reverse_iterator rend() const BOOST_NOEXCEPT { return const_reverse_iterator(begin()); }
Chris@16: 
Chris@16:     //! Get the element at the <code>index</code> position.
Chris@16:     /*!
Chris@16:         \pre <code>0 \<= index \&\& index \< size()</code>
Chris@16:         \param index The position of the element.
Chris@16:         \return A reference to the element at the <code>index</code> position.
Chris@16:         \throws Nothing.
Chris@16:         \par Exception Safety
Chris@16:              No-throw.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>at()</code>
Chris@16:     */
Chris@16:     reference operator [] (size_type index) {
Chris@16:         BOOST_CB_ASSERT(index < size()); // check for invalid index
Chris@16:         return *add(m_first, index);
Chris@16:     }
Chris@16: 
Chris@16:     //! Get the element at the <code>index</code> position.
Chris@16:     /*!
Chris@16:         \pre <code>0 \<= index \&\& index \< size()</code>
Chris@16:         \param index The position of the element.
Chris@16:         \return A const reference to the element at the <code>index</code> position.
Chris@16:         \throws Nothing.
Chris@16:         \par Exception Safety
Chris@16:              No-throw.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>\link at(size_type)const at() const \endlink</code>
Chris@16:     */
Chris@16:     const_reference operator [] (size_type index) const {
Chris@16:         BOOST_CB_ASSERT(index < size()); // check for invalid index
Chris@16:         return *add(m_first, index);
Chris@16:     }
Chris@16: 
Chris@16:     //! Get the element at the <code>index</code> position.
Chris@16:     /*!
Chris@16:         \param index The position of the element.
Chris@16:         \return A reference to the element at the <code>index</code> position.
Chris@16:         \throws <code>std::out_of_range</code> when the <code>index</code> is invalid (when
Chris@16:                 <code>index >= size()</code>).
Chris@16:         \par Exception Safety
Chris@16:              Strong.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>\link operator[](size_type) operator[] \endlink</code>
Chris@16:     */
Chris@16:     reference at(size_type index) {
Chris@16:         check_position(index);
Chris@16:         return (*this)[index];
Chris@16:     }
Chris@16: 
Chris@16:     //! Get the element at the <code>index</code> position.
Chris@16:     /*!
Chris@16:         \param index The position of the element.
Chris@16:         \return A const reference to the element at the <code>index</code> position.
Chris@16:         \throws <code>std::out_of_range</code> when the <code>index</code> is invalid (when
Chris@16:                 <code>index >= size()</code>).
Chris@16:         \par Exception Safety
Chris@16:              Strong.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>\link operator[](size_type)const operator[] const \endlink</code>
Chris@16:     */
Chris@16:     const_reference at(size_type index) const {
Chris@16:         check_position(index);
Chris@16:         return (*this)[index];
Chris@16:     }
Chris@16: 
Chris@16:     //! Get the first element.
Chris@16:     /*!
Chris@16:         \pre <code>!empty()</code>
Chris@16:         \return A reference to the first element of the <code>circular_buffer</code>.
Chris@16:         \throws Nothing.
Chris@16:         \par Exception Safety
Chris@16:              No-throw.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>back()</code>
Chris@16:     */
Chris@16:     reference front() {
Chris@16:         BOOST_CB_ASSERT(!empty()); // check for empty buffer (front element not available)
Chris@16:         return *m_first;
Chris@16:     }
Chris@16: 
Chris@16:     //! Get the last element.
Chris@16:     /*!
Chris@16:         \pre <code>!empty()</code>
Chris@16:         \return A reference to the last element of the <code>circular_buffer</code>.
Chris@16:         \throws Nothing.
Chris@16:         \par Exception Safety
Chris@16:              No-throw.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>front()</code>
Chris@16:     */
Chris@16:     reference back() {
Chris@16:         BOOST_CB_ASSERT(!empty()); // check for empty buffer (back element not available)
Chris@16:         return *((m_last == m_buff ? m_end : m_last) - 1);
Chris@16:     }
Chris@16: 
Chris@16:     //! Get the first element.
Chris@16:     /*!
Chris@16:         \pre <code>!empty()</code>
Chris@16:         \return A const reference to the first element of the <code>circular_buffer</code>.
Chris@16:         \throws Nothing.
Chris@16:         \par Exception Safety
Chris@16:              No-throw.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>back() const</code>
Chris@16:     */
Chris@16:     const_reference front() const {
Chris@16:         BOOST_CB_ASSERT(!empty()); // check for empty buffer (front element not available)
Chris@16:         return *m_first;
Chris@16:     }
Chris@16: 
Chris@16:     //! Get the last element.
Chris@16:     /*!
Chris@16:         \pre <code>!empty()</code>
Chris@16:         \return A const reference to the last element of the <code>circular_buffer</code>.
Chris@16:         \throws Nothing.
Chris@16:         \par Exception Safety
Chris@16:              No-throw.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>front() const</code>
Chris@16:     */
Chris@16:     const_reference back() const {
Chris@16:         BOOST_CB_ASSERT(!empty()); // check for empty buffer (back element not available)
Chris@16:         return *((m_last == m_buff ? m_end : m_last) - 1);
Chris@16:     }
Chris@16: 
Chris@16:     //! Get the first continuous array of the internal buffer.
Chris@16:     /*!
Chris@16:         This method in combination with <code>array_two()</code> can be useful when passing the stored data into
Chris@16:         a legacy C API as an array. Suppose there is a <code>circular_buffer</code> of capacity 10, containing 7
Chris@16:         characters <code>'a', 'b', ..., 'g'</code> where <code>buff[0] == 'a'</code>, <code>buff[1] == 'b'</code>,
Chris@16:         ... and <code>buff[6] == 'g'</code>:<br><br>
Chris@16:         <code>circular_buffer<char> buff(10);</code><br><br>
Chris@16:         The internal representation is often not linear and the state of the internal buffer may look like this:<br>
Chris@16:         <br><code>
Chris@16:         |e|f|g| | | |a|b|c|d|<br>
Chris@16:         end ___^<br>
Chris@16:         begin _______^</code><br><br>
Chris@16: 
Chris@16:         where <code>|a|b|c|d|</code> represents the "array one", <code>|e|f|g|</code> represents the "array two" and
Chris@16:         <code>| | | |</code> is a free space.<br>
Chris@16:         Now consider a typical C style function for writing data into a file:<br><br>
Chris@16:         <code>int write(int file_desc, char* buff, int num_bytes);</code><br><br>
Chris@16:         There are two ways how to write the content of the <code>circular_buffer</code> into a file. Either relying
Chris@16:         on <code>array_one()</code> and <code>array_two()</code> methods and calling the write function twice:<br><br>
Chris@16:         <code>array_range ar = buff.array_one();<br>
Chris@16:         write(file_desc, ar.first, ar.second);<br>
Chris@16:         ar = buff.array_two();<br>
Chris@16:         write(file_desc, ar.first, ar.second);</code><br><br>
Chris@16:         Or relying on the <code>linearize()</code> method:<br><br><code>
Chris@16:         write(file_desc, buff.linearize(), buff.size());</code><br><br>
Chris@16:         Since the complexity of <code>array_one()</code> and <code>array_two()</code> methods is constant the first
Chris@16:         option is suitable when calling the write method is "cheap". On the other hand the second option is more
Chris@16:         suitable when calling the write method is more "expensive" than calling the <code>linearize()</code> method
Chris@16:         whose complexity is linear.
Chris@16:         \return The array range of the first continuous array of the internal buffer. In the case the
Chris@16:                 <code>circular_buffer</code> is empty the size of the returned array is <code>0</code>.
Chris@16:         \throws Nothing.
Chris@16:         \par Exception Safety
Chris@16:              No-throw.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \warning In general invoking any method which modifies the internal state of the circular_buffer  may
Chris@16:                  delinearize the internal buffer and invalidate the array ranges returned by <code>array_one()</code>
Chris@16:                  and <code>array_two()</code> (and their const versions).
Chris@16:         \note In the case the internal buffer is linear e.g. <code>|a|b|c|d|e|f|g| | | |</code> the "array one" is
Chris@16:               represented by <code>|a|b|c|d|e|f|g|</code> and the "array two" does not exist (the
Chris@16:               <code>array_two()</code> method returns an array with the size <code>0</code>).
Chris@16:         \sa <code>array_two()</code>, <code>linearize()</code>
Chris@16:     */
Chris@16:     array_range array_one() {
Chris@16:         return array_range(m_first, (m_last <= m_first && !empty() ? m_end : m_last) - m_first);
Chris@16:     }
Chris@16: 
Chris@16:     //! Get the second continuous array of the internal buffer.
Chris@16:     /*!
Chris@16:         This method in combination with <code>array_one()</code> can be useful when passing the stored data into
Chris@16:         a legacy C API as an array.
Chris@16:         \return The array range of the second continuous array of the internal buffer. In the case the internal buffer
Chris@16:                 is linear or the <code>circular_buffer</code> is empty the size of the returned array is
Chris@16:                 <code>0</code>.
Chris@16:         \throws Nothing.
Chris@16:         \par Exception Safety
Chris@16:              No-throw.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>array_one()</code>
Chris@16:     */
Chris@16:     array_range array_two() {
Chris@16:         return array_range(m_buff, m_last <= m_first && !empty() ? m_last - m_buff : 0);
Chris@16:     }
Chris@16: 
Chris@16:     //! Get the first continuous array of the internal buffer.
Chris@16:     /*!
Chris@16:         This method in combination with <code>array_two() const</code> can be useful when passing the stored data into
Chris@16:         a legacy C API as an array.
Chris@16:         \return The array range of the first continuous array of the internal buffer. In the case the
Chris@16:                 <code>circular_buffer</code> is empty the size of the returned array is <code>0</code>.
Chris@16:         \throws Nothing.
Chris@16:         \par Exception Safety
Chris@16:              No-throw.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>array_two() const</code>; <code>array_one()</code> for more details how to pass data into a legacy C
Chris@16:             API.
Chris@16:     */
Chris@16:     const_array_range array_one() const {
Chris@16:         return const_array_range(m_first, (m_last <= m_first && !empty() ? m_end : m_last) - m_first);
Chris@16:     }
Chris@16: 
Chris@16:     //! Get the second continuous array of the internal buffer.
Chris@16:     /*!
Chris@16:         This method in combination with <code>array_one() const</code> can be useful when passing the stored data into
Chris@16:         a legacy C API as an array.
Chris@16:         \return The array range of the second continuous array of the internal buffer. In the case the internal buffer
Chris@16:                 is linear or the <code>circular_buffer</code> is empty the size of the returned array is
Chris@16:                 <code>0</code>.
Chris@16:         \throws Nothing.
Chris@16:         \par Exception Safety
Chris@16:              No-throw.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>array_one() const</code>
Chris@16:     */
Chris@16:     const_array_range array_two() const {
Chris@16:         return const_array_range(m_buff, m_last <= m_first && !empty() ? m_last - m_buff : 0);
Chris@16:     }
Chris@16: 
Chris@16:     //! Linearize the internal buffer into a continuous array.
Chris@16:     /*!
Chris@16:         This method can be useful when passing the stored data into a legacy C API as an array.
Chris@16:         \post <code>\&(*this)[0] \< \&(*this)[1] \< ... \< \&(*this)[size() - 1]</code>
Chris@16:         \return A pointer to the beginning of the array or <code>0</code> if empty.
Chris@16:         \throws <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
Chris@16:         \par Exception Safety
Chris@16:              Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
Chris@16:              <code>end()</code>); does not invalidate any iterators if the postcondition (the <i>Effect</i>) is already
Chris@16:              met prior calling this method.
Chris@16:         \par Complexity
Chris@16:              Linear (in the size of the <code>circular_buffer</code>); constant if the postcondition (the
Chris@16:              <i>Effect</i>) is already met.
Chris@16:         \warning In general invoking any method which modifies the internal state of the <code>circular_buffer</code>
Chris@16:                  may delinearize the internal buffer and invalidate the returned pointer.
Chris@16:         \sa <code>array_one()</code> and <code>array_two()</code> for the other option how to pass data into a legacy
Chris@16:             C API; <code>is_linearized()</code>, <code>rotate(const_iterator)</code>
Chris@16:     */
Chris@16:     pointer linearize() {
Chris@16:         if (empty())
Chris@16:             return 0;
Chris@16:         if (m_first < m_last || m_last == m_buff)
Chris@16:             return m_first;
Chris@16:         pointer src = m_first;
Chris@16:         pointer dest = m_buff;
Chris@16:         size_type moved = 0;
Chris@16:         size_type constructed = 0;
Chris@16:         BOOST_TRY {
Chris@16:             for (pointer first = m_first; dest < src; src = first) {
Chris@16:                 for (size_type ii = 0; src < m_end; ++src, ++dest, ++moved, ++ii) {
Chris@16:                     if (moved == size()) {
Chris@16:                         first = dest;
Chris@16:                         break;
Chris@16:                     }
Chris@16:                     if (dest == first) {
Chris@16:                         first += ii;
Chris@16:                         break;
Chris@16:                     }
Chris@16:                     if (is_uninitialized(dest)) {
Chris@101:                         boost::container::allocator_traits<Alloc>::construct(m_alloc, boost::addressof(*dest), boost::move_if_noexcept(*src));
Chris@16:                         ++constructed;
Chris@16:                     } else {
Chris@101:                         value_type tmp = boost::move_if_noexcept(*src); 
Chris@101:                         replace(src, boost::move_if_noexcept(*dest));
Chris@16:                         replace(dest, boost::move(tmp));
Chris@16:                     }
Chris@16:                 }
Chris@16:             }
Chris@16:         } BOOST_CATCH(...) {
Chris@16:             m_last += constructed;
Chris@16:             m_size += constructed;
Chris@16:             BOOST_RETHROW
Chris@16:         }
Chris@16:         BOOST_CATCH_END
Chris@16:         for (src = m_end - constructed; src < m_end; ++src)
Chris@16:             destroy_item(src);
Chris@16:         m_first = m_buff;
Chris@16:         m_last = add(m_buff, size());
Chris@16: #if BOOST_CB_ENABLE_DEBUG
Chris@16:         invalidate_iterators_except(end());
Chris@16: #endif
Chris@16:         return m_buff;
Chris@16:     }
Chris@16: 
Chris@16:     //! Is the <code>circular_buffer</code> linearized?
Chris@16:     /*!
Chris@16:         \return <code>true</code> if the internal buffer is linearized into a continuous array (i.e. the
Chris@16:                 <code>circular_buffer</code> meets a condition
Chris@16:                 <code>\&(*this)[0] \< \&(*this)[1] \< ... \< \&(*this)[size() - 1]</code>);
Chris@16:                 <code>false</code> otherwise.
Chris@16:         \throws Nothing.
Chris@16:         \par Exception Safety
Chris@16:              No-throw.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>linearize()</code>, <code>array_one()</code>, <code>array_two()</code>
Chris@16:     */
Chris@16:     bool is_linearized() const BOOST_NOEXCEPT { return m_first < m_last || m_last == m_buff; }
Chris@16: 
Chris@16:     //! Rotate elements in the <code>circular_buffer</code>.
Chris@16:     /*!
Chris@16:         A more effective implementation of
Chris@16:         <code><a href="http://www.sgi.com/tech/stl/rotate.html">std::rotate</a></code>.
Chris@16:         \pre <code>new_begin</code> is a valid iterator pointing to the <code>circular_buffer</code> <b>except</b> its
Chris@16:              end.
Chris@16:         \post Before calling the method suppose:<br><br>
Chris@16:               <code>m == std::distance(new_begin, end())</code><br><code>n == std::distance(begin(), new_begin)</code>
Chris@16:               <br><code>val_0 == *new_begin, val_1 == *(new_begin + 1), ... val_m == *(new_begin + m)</code><br>
Chris@16:               <code>val_r1 == *(new_begin - 1), val_r2 == *(new_begin - 2), ... val_rn == *(new_begin - n)</code><br>
Chris@16:               <br>then after call to the method:<br><br>
Chris@16:               <code>val_0 == (*this)[0] \&\& val_1 == (*this)[1] \&\& ... \&\& val_m == (*this)[m - 1] \&\& val_r1 ==
Chris@16:               (*this)[m + n - 1] \&\& val_r2 == (*this)[m + n - 2] \&\& ... \&\& val_rn == (*this)[m]</code>
Chris@16:         \param new_begin The new beginning.
Chris@16:         \throws See <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
Chris@16:         \par Exception Safety
Chris@16:              Basic; no-throw if the <code>circular_buffer</code> is full or <code>new_begin</code> points to
Chris@16:              <code>begin()</code> or if the operations in the <i>Throws</i> section do not throw anything.
Chris@16:         \par Iterator Invalidation
Chris@16:              If <code>m \< n</code> invalidates iterators pointing to the last <code>m</code> elements
Chris@16:              (<b>including</b> <code>new_begin</code>, but not iterators equal to <code>end()</code>) else invalidates
Chris@16:              iterators pointing to the first <code>n</code> elements; does not invalidate any iterators if the
Chris@16:              <code>circular_buffer</code> is full.
Chris@16:         \par Complexity
Chris@16:              Linear (in <code>(std::min)(m, n)</code>); constant if the <code>circular_buffer</code> is full.
Chris@16:         \sa <code><a href="http://www.sgi.com/tech/stl/rotate.html">std::rotate</a></code>
Chris@16:     */
Chris@16:     void rotate(const_iterator new_begin) {
Chris@16:         BOOST_CB_ASSERT(new_begin.is_valid(this)); // check for uninitialized or invalidated iterator
Chris@16:         BOOST_CB_ASSERT(new_begin.m_it != 0);      // check for iterator pointing to end()
Chris@16:         if (full()) {
Chris@16:             m_first = m_last = const_cast<pointer>(new_begin.m_it);
Chris@16:         } else {
Chris@16:             difference_type m = end() - new_begin;
Chris@16:             difference_type n = new_begin - begin();
Chris@16:             if (m < n) {
Chris@16:                 for (; m > 0; --m) {
Chris@101:                     push_front(boost::move_if_noexcept(back()));
Chris@16:                     pop_back();
Chris@16:                 }
Chris@16:             } else {
Chris@16:                 for (; n > 0; --n) {
Chris@101:                     push_back(boost::move_if_noexcept(front()));
Chris@16:                     pop_front();
Chris@16:                 }
Chris@16:             }
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16: // Size and capacity
Chris@16: 
Chris@16:     //! Get the number of elements currently stored in the <code>circular_buffer</code>.
Chris@16:     /*!
Chris@16:         \return The number of elements stored in the <code>circular_buffer</code>.
Chris@16:         \throws Nothing.
Chris@16:         \par Exception Safety
Chris@16:              No-throw.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>capacity()</code>, <code>max_size()</code>, <code>reserve()</code>,
Chris@16:             <code>\link resize() resize(size_type, const_reference)\endlink</code>
Chris@16:     */
Chris@16:     size_type size() const BOOST_NOEXCEPT { return m_size; }
Chris@16: 
Chris@16:     /*! \brief Get the largest possible size or capacity of the <code>circular_buffer</code>. (It depends on
Chris@16:                allocator's %max_size()).
Chris@16:         \return The maximum size/capacity the <code>circular_buffer</code> can be set to.
Chris@16:         \throws Nothing.
Chris@16:         \par Exception Safety
Chris@16:              No-throw.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>size()</code>, <code>capacity()</code>, <code>reserve()</code>
Chris@16:     */
Chris@16:     size_type max_size() const BOOST_NOEXCEPT {
Chris@101:         return (std::min<size_type>)(boost::container::allocator_traits<Alloc>::max_size(m_alloc), (std::numeric_limits<difference_type>::max)());
Chris@16:     }
Chris@16: 
Chris@16:     //! Is the <code>circular_buffer</code> empty?
Chris@16:     /*!
Chris@16:         \return <code>true</code> if there are no elements stored in the <code>circular_buffer</code>;
Chris@16:                 <code>false</code> otherwise.
Chris@16:         \throws Nothing.
Chris@16:         \par Exception Safety
Chris@16:              No-throw.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>full()</code>
Chris@16:     */
Chris@16:     bool empty() const BOOST_NOEXCEPT { return size() == 0; }
Chris@16: 
Chris@16:     //! Is the <code>circular_buffer</code> full?
Chris@16:     /*!
Chris@16:         \return <code>true</code> if the number of elements stored in the <code>circular_buffer</code>
Chris@16:                 equals the capacity of the <code>circular_buffer</code>; <code>false</code> otherwise.
Chris@16:         \throws Nothing.
Chris@16:         \par Exception Safety
Chris@16:              No-throw.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>empty()</code>
Chris@16:     */
Chris@16:     bool full() const BOOST_NOEXCEPT { return capacity() == size(); }
Chris@16: 
Chris@16:     /*! \brief Get the maximum number of elements which can be inserted into the <code>circular_buffer</code> without
Chris@16:                overwriting any of already stored elements.
Chris@16:         \return <code>capacity() - size()</code>
Chris@16:         \throws Nothing.
Chris@16:         \par Exception Safety
Chris@16:              No-throw.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>capacity()</code>, <code>size()</code>, <code>max_size()</code>
Chris@16:     */
Chris@16:     size_type reserve() const BOOST_NOEXCEPT { return capacity() - size(); }
Chris@16: 
Chris@16:     //! Get the capacity of the <code>circular_buffer</code>.
Chris@16:     /*!
Chris@16:         \return The maximum number of elements which can be stored in the <code>circular_buffer</code>.
Chris@16:         \throws Nothing.
Chris@16:         \par Exception Safety
Chris@16:              No-throw.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>reserve()</code>, <code>size()</code>, <code>max_size()</code>,
Chris@16:             <code>set_capacity(capacity_type)</code>
Chris@16:     */
Chris@16:     capacity_type capacity() const BOOST_NOEXCEPT { return m_end - m_buff; }
Chris@16: 
Chris@16:     //! Change the capacity of the <code>circular_buffer</code>.
Chris@16:     /*! 
Chris@16:         \pre If <code>T</code> is a move only type, then compiler shall support <code>noexcept</code> modifiers
Chris@16:                 and move constructor of <code>T</code> must be marked with it (must not throw exceptions).
Chris@16:         \post <code>capacity() == new_capacity \&\& size() \<= new_capacity</code><br><br>
Chris@16:               If the current number of elements stored in the <code>circular_buffer</code> is greater than the desired
Chris@16:               new capacity then number of <code>[size() - new_capacity]</code> <b>last</b> elements will be removed and
Chris@16:               the new size will be equal to <code>new_capacity</code>.
Chris@16:         \param new_capacity The new capacity.
Chris@16:         \throws "An allocation error" if memory is exhausted, (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept.
Chris@16:         \par Exception Safety
Chris@16:              Strong.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
Chris@16:              <code>end()</code>) if the new capacity is different from the original.
Chris@16:         \par Complexity
Chris@16:              Linear (in <code>min[size(), new_capacity]</code>).
Chris@16:         \sa <code>rset_capacity(capacity_type)</code>,
Chris@16:             <code>\link resize() resize(size_type, const_reference)\endlink</code>
Chris@16:     */
Chris@16:     void set_capacity(capacity_type new_capacity) {
Chris@16:         if (new_capacity == capacity())
Chris@16:             return;
Chris@16:         pointer buff = allocate(new_capacity);
Chris@16:         iterator b = begin();
Chris@16:         BOOST_TRY {
Chris@16:             reset(buff,
Chris@101:                 cb_details::uninitialized_move_if_noexcept(b, b + (std::min)(new_capacity, size()), buff, m_alloc),
Chris@16:                 new_capacity);
Chris@16:         } BOOST_CATCH(...) {
Chris@16:             deallocate(buff, new_capacity);
Chris@16:             BOOST_RETHROW
Chris@16:         }
Chris@16:         BOOST_CATCH_END
Chris@16:     }
Chris@16: 
Chris@16:     //! Change the size of the <code>circular_buffer</code>.
Chris@16:     /*!
Chris@16:         \post <code>size() == new_size \&\& capacity() >= new_size</code><br><br>
Chris@16:               If the new size is greater than the current size, copies of <code>item</code> will be inserted at the
Chris@16:               <b>back</b> of the of the <code>circular_buffer</code> in order to achieve the desired size. In the case
Chris@16:               the resulting size exceeds the current capacity the capacity will be set to <code>new_size</code>.<br>
Chris@16:               If the current number of elements stored in the <code>circular_buffer</code> is greater than the desired
Chris@16:               new size then number of <code>[size() - new_size]</code> <b>last</b> elements will be removed. (The
Chris@16:               capacity will remain unchanged.)
Chris@16:         \param new_size The new size.
Chris@16:         \param item The element the <code>circular_buffer</code> will be filled with in order to gain the requested
Chris@16:                     size. (See the <i>Effect</i>.)
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept.
Chris@16:         \par Exception Safety
Chris@16:              Basic.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
Chris@16:              <code>end()</code>) if the new size is greater than the current capacity. Invalidates iterators pointing
Chris@16:              to the removed elements if the new size is lower that the original size. Otherwise it does not invalidate
Chris@16:              any iterator.
Chris@16:         \par Complexity
Chris@16:              Linear (in the new size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>\link rresize() rresize(size_type, const_reference)\endlink</code>,
Chris@16:             <code>set_capacity(capacity_type)</code>
Chris@16:     */
Chris@16:     void resize(size_type new_size, param_value_type item = value_type()) {
Chris@16:         if (new_size > size()) {
Chris@16:             if (new_size > capacity())
Chris@16:                 set_capacity(new_size);
Chris@16:             insert(end(), new_size - size(), item);
Chris@16:         } else {
Chris@16:             iterator e = end();
Chris@16:             erase(e - (size() - new_size), e);
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     //! Change the capacity of the <code>circular_buffer</code>.
Chris@16:     /*! 
Chris@16:         \pre If <code>T</code> is a move only type, then compiler shall support <code>noexcept</code> modifiers
Chris@16:                 and move constructor of <code>T</code> must be marked with it (must not throw exceptions).
Chris@16:         \post <code>capacity() == new_capacity \&\& size() \<= new_capacity</code><br><br>
Chris@16:               If the current number of elements stored in the <code>circular_buffer</code> is greater than the desired
Chris@16:               new capacity then number of <code>[size() - new_capacity]</code> <b>first</b> elements will be removed
Chris@16:               and the new size will be equal to <code>new_capacity</code>.
Chris@16:         \param new_capacity The new capacity.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept.
Chris@16:         \par Exception Safety
Chris@16:              Strong.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
Chris@16:              <code>end()</code>) if the new capacity is different from the original.
Chris@16:         \par Complexity
Chris@16:              Linear (in <code>min[size(), new_capacity]</code>).
Chris@16:         \sa <code>set_capacity(capacity_type)</code>,
Chris@16:             <code>\link rresize() rresize(size_type, const_reference)\endlink</code>
Chris@16:     */
Chris@16:     void rset_capacity(capacity_type new_capacity) {
Chris@16:         if (new_capacity == capacity())
Chris@16:             return;
Chris@16:         pointer buff = allocate(new_capacity);
Chris@16:         iterator e = end();
Chris@16:         BOOST_TRY {
Chris@101:             reset(buff, cb_details::uninitialized_move_if_noexcept(e - (std::min)(new_capacity, size()),
Chris@101:                 e, buff, m_alloc), new_capacity);
Chris@16:         } BOOST_CATCH(...) {
Chris@16:             deallocate(buff, new_capacity);
Chris@16:             BOOST_RETHROW
Chris@16:         }
Chris@16:         BOOST_CATCH_END
Chris@16:     }
Chris@16: 
Chris@16:     //! Change the size of the <code>circular_buffer</code>.
Chris@16:     /*!
Chris@16:         \post <code>size() == new_size \&\& capacity() >= new_size</code><br><br>
Chris@16:               If the new size is greater than the current size, copies of <code>item</code> will be inserted at the
Chris@16:               <b>front</b> of the of the <code>circular_buffer</code> in order to achieve the desired size. In the case
Chris@16:               the resulting size exceeds the current capacity the capacity will be set to <code>new_size</code>.<br>
Chris@16:               If the current number of elements stored in the <code>circular_buffer</code> is greater than the desired
Chris@16:               new size then number of <code>[size() - new_size]</code> <b>first</b> elements will be removed. (The
Chris@16:               capacity will remain unchanged.)
Chris@16:         \param new_size The new size.
Chris@16:         \param item The element the <code>circular_buffer</code> will be filled with in order to gain the requested
Chris@16:                     size. (See the <i>Effect</i>.)
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept.
Chris@16:         \par Exception Safety
Chris@16:              Basic.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
Chris@16:              <code>end()</code>) if the new size is greater than the current capacity. Invalidates iterators pointing
Chris@16:              to the removed elements if the new size is lower that the original size. Otherwise it does not invalidate
Chris@16:              any iterator.
Chris@16:         \par Complexity
Chris@16:              Linear (in the new size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>\link resize() resize(size_type, const_reference)\endlink</code>,
Chris@16:             <code>rset_capacity(capacity_type)</code>
Chris@16:     */
Chris@16:     void rresize(size_type new_size, param_value_type item = value_type()) {
Chris@16:         if (new_size > size()) {
Chris@16:             if (new_size > capacity())
Chris@16:                 set_capacity(new_size);
Chris@16:             rinsert(begin(), new_size - size(), item);
Chris@16:         } else {
Chris@16:             rerase(begin(), end() - new_size);
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16: // Construction/Destruction
Chris@16: 
Chris@16:     //! Create an empty <code>circular_buffer</code> with zero capacity.
Chris@16:     /*!
Chris@16:         \post <code>capacity() == 0 \&\& size() == 0</code>
Chris@16:         \param alloc The allocator.
Chris@16:         \throws Nothing.
Chris@16:         \par Complexity
Chris@16:              Constant.
Chris@16:         \warning Since Boost version 1.36 the behaviour of this constructor has changed. Now the constructor does not
Chris@16:                  allocate any memory and both capacity and size are set to zero. Also note when inserting an element
Chris@16:                  into a <code>circular_buffer</code> with zero capacity (e.g. by
Chris@16:                  <code>\link push_back() push_back(const_reference)\endlink</code> or
Chris@16:                  <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>) nothing
Chris@16:                  will be inserted and the size (as well as capacity) remains zero.
Chris@16:         \note You can explicitly set the capacity by calling the <code>set_capacity(capacity_type)</code> method or you
Chris@16:               can use the other constructor with the capacity specified.
Chris@16:         \sa <code>circular_buffer(capacity_type, const allocator_type& alloc)</code>,
Chris@16:             <code>set_capacity(capacity_type)</code>
Chris@16:     */
Chris@16:     explicit circular_buffer(const allocator_type& alloc = allocator_type()) BOOST_NOEXCEPT
Chris@16:     : m_buff(0), m_end(0), m_first(0), m_last(0), m_size(0), m_alloc(alloc) {}
Chris@16: 
Chris@16:     //! Create an empty <code>circular_buffer</code> with the specified capacity.
Chris@16:     /*!
Chris@16:         \post <code>capacity() == buffer_capacity \&\& size() == 0</code>
Chris@16:         \param buffer_capacity The maximum number of elements which can be stored in the <code>circular_buffer</code>.
Chris@16:         \param alloc The allocator.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:         \par Complexity
Chris@16:              Constant.
Chris@16:     */
Chris@16:     explicit circular_buffer(capacity_type buffer_capacity, const allocator_type& alloc = allocator_type())
Chris@16:     : m_size(0), m_alloc(alloc) {
Chris@16:         initialize_buffer(buffer_capacity);
Chris@16:         m_first = m_last = m_buff;
Chris@16:     }
Chris@16: 
Chris@16:     /*! \brief Create a full <code>circular_buffer</code> with the specified capacity and filled with <code>n</code>
Chris@16:                copies of <code>item</code>.
Chris@16:         \post <code>capacity() == n \&\& full() \&\& (*this)[0] == item \&\& (*this)[1] == item \&\& ... \&\&
Chris@16:               (*this)[n - 1] == item </code>
Chris@16:         \param n The number of elements the created <code>circular_buffer</code> will be filled with.
Chris@16:         \param item The element the created <code>circular_buffer</code> will be filled with.
Chris@16:         \param alloc The allocator.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T(const T&)</code> throws.
Chris@16:         \par Complexity
Chris@16:              Linear (in the <code>n</code>).
Chris@16:     */
Chris@16:     circular_buffer(size_type n, param_value_type item, const allocator_type& alloc = allocator_type())
Chris@16:     : m_size(n), m_alloc(alloc) {
Chris@16:         initialize_buffer(n, item);
Chris@16:         m_first = m_last = m_buff;
Chris@16:     }
Chris@16: 
Chris@16:     /*! \brief Create a <code>circular_buffer</code> with the specified capacity and filled with <code>n</code>
Chris@16:                copies of <code>item</code>.
Chris@16:         \pre <code>buffer_capacity >= n</code>
Chris@16:         \post <code>capacity() == buffer_capacity \&\& size() == n \&\& (*this)[0] == item \&\& (*this)[1] == item
Chris@16:               \&\& ... \&\& (*this)[n - 1] == item</code>
Chris@16:         \param buffer_capacity The capacity of the created <code>circular_buffer</code>.
Chris@16:         \param n The number of elements the created <code>circular_buffer</code> will be filled with.
Chris@16:         \param item The element the created <code>circular_buffer</code> will be filled with.
Chris@16:         \param alloc The allocator.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T(const T&)</code> throws.
Chris@16:         \par Complexity
Chris@16:              Linear (in the <code>n</code>).
Chris@16:     */
Chris@16:     circular_buffer(capacity_type buffer_capacity, size_type n, param_value_type item,
Chris@16:         const allocator_type& alloc = allocator_type())
Chris@16:     : m_size(n), m_alloc(alloc) {
Chris@16:         BOOST_CB_ASSERT(buffer_capacity >= size()); // check for capacity lower than size
Chris@16:         initialize_buffer(buffer_capacity, item);
Chris@16:         m_first = m_buff;
Chris@16:         m_last = buffer_capacity == n ? m_buff : m_buff + n;
Chris@16:     }
Chris@16: 
Chris@16:     //! The copy constructor.
Chris@16:     /*!
Chris@16:         Creates a copy of the specified <code>circular_buffer</code>.
Chris@16:         \post <code>*this == cb</code>
Chris@16:         \param cb The <code>circular_buffer</code> to be copied.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T(const T&)</code> throws.
Chris@16:         \par Complexity
Chris@16:              Linear (in the size of <code>cb</code>).
Chris@16:     */
Chris@16:     circular_buffer(const circular_buffer<T, Alloc>& cb)
Chris@16:     :
Chris@16: #if BOOST_CB_ENABLE_DEBUG
Chris@16:     debug_iterator_registry(),
Chris@16: #endif
Chris@16:     m_size(cb.size()), m_alloc(cb.get_allocator()) {
Chris@16:         initialize_buffer(cb.capacity());
Chris@16:         m_first = m_buff;
Chris@16:         BOOST_TRY {
Chris@101:             m_last = cb_details::uninitialized_copy(cb.begin(), cb.end(), m_buff, m_alloc);
Chris@16:         } BOOST_CATCH(...) {
Chris@16:             deallocate(m_buff, cb.capacity());
Chris@16:             BOOST_RETHROW
Chris@16:         }
Chris@16:         BOOST_CATCH_END
Chris@16:         if (m_last == m_end)
Chris@16:             m_last = m_buff;
Chris@16:     }
Chris@16:     
Chris@16: #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
Chris@16:     //! The move constructor.
Chris@16:     /*! \brief Move constructs a <code>circular_buffer</code> from <code>cb</code>, leaving <code>cb</code> empty.
Chris@16:         \pre C++ compiler with rvalue references support.
Chris@16:         \post <code>cb.empty()</code>
Chris@16:         \param cb <code>circular_buffer</code> to 'steal' value from.
Chris@16:         \throws Nothing.
Chris@16:         \par Constant.
Chris@16:     */
Chris@16:     circular_buffer(circular_buffer<T, Alloc>&& cb) BOOST_NOEXCEPT
Chris@16:     : m_buff(0), m_end(0), m_first(0), m_last(0), m_size(0), m_alloc(cb.get_allocator()) {
Chris@16:         cb.swap(*this);
Chris@16:     }
Chris@16: #endif // BOOST_NO_CXX11_RVALUE_REFERENCES
Chris@16: 
Chris@16:     //! Create a full <code>circular_buffer</code> filled with a copy of the range.
Chris@16:     /*!
Chris@16:         \pre Valid range <code>[first, last)</code>.<br>
Chris@16:              <code>first</code> and <code>last</code> have to meet the requirements of
Chris@16:              <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
Chris@16:         \post <code>capacity() == std::distance(first, last) \&\& full() \&\& (*this)[0]== *first \&\&
Chris@16:               (*this)[1] == *(first + 1) \&\& ... \&\& (*this)[std::distance(first, last) - 1] == *(last - 1)</code>
Chris@16:         \param first The beginning of the range to be copied.
Chris@16:         \param last The end of the range to be copied.
Chris@16:         \param alloc The allocator.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T(const T&)</code> throws.
Chris@16:         \par Complexity
Chris@16:              Linear (in the <code>std::distance(first, last)</code>).
Chris@16:     */
Chris@16:     template <class InputIterator>
Chris@16:     circular_buffer(InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type())
Chris@16:     : m_alloc(alloc) {
Chris@16:         initialize(first, last, is_integral<InputIterator>());
Chris@16:     }
Chris@16: 
Chris@16:     //! Create a <code>circular_buffer</code> with the specified capacity and filled with a copy of the range.
Chris@16:     /*!
Chris@16:         \pre Valid range <code>[first, last)</code>.<br>
Chris@16:              <code>first</code> and <code>last</code> have to meet the requirements of
Chris@16:              <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
Chris@16:         \post <code>capacity() == buffer_capacity \&\& size() \<= std::distance(first, last) \&\&
Chris@16:              (*this)[0]== *(last - buffer_capacity) \&\& (*this)[1] == *(last - buffer_capacity + 1) \&\& ... \&\&
Chris@16:              (*this)[buffer_capacity - 1] == *(last - 1)</code><br><br>
Chris@16:              If the number of items to be copied from the range <code>[first, last)</code> is greater than the
Chris@16:              specified <code>buffer_capacity</code> then only elements from the range
Chris@16:              <code>[last - buffer_capacity, last)</code> will be copied.
Chris@16:         \param buffer_capacity The capacity of the created <code>circular_buffer</code>.
Chris@16:         \param first The beginning of the range to be copied.
Chris@16:         \param last The end of the range to be copied.
Chris@16:         \param alloc The allocator.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T(const T&)</code> throws.
Chris@16:         \par Complexity
Chris@16:              Linear (in <code>std::distance(first, last)</code>; in
Chris@16:              <code>min[capacity, std::distance(first, last)]</code> if the <code>InputIterator</code> is a
Chris@16:              <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>).
Chris@16:     */
Chris@16:     template <class InputIterator>
Chris@16:     circular_buffer(capacity_type buffer_capacity, InputIterator first, InputIterator last,
Chris@16:         const allocator_type& alloc = allocator_type())
Chris@16:     : m_alloc(alloc) {
Chris@16:         initialize(buffer_capacity, first, last, is_integral<InputIterator>());
Chris@16:     }
Chris@16: 
Chris@16:     //! The destructor.
Chris@16:     /*!
Chris@16:         Destroys the <code>circular_buffer</code>.
Chris@16:         \throws Nothing.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer</code> (including iterators equal to
Chris@16:              <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>) for scalar types; linear for other types.
Chris@16:         \sa <code>clear()</code>
Chris@16:     */
Chris@16:     ~circular_buffer() BOOST_NOEXCEPT {
Chris@16:         destroy();
Chris@16: #if BOOST_CB_ENABLE_DEBUG
Chris@16:         invalidate_all_iterators();
Chris@16: #endif
Chris@16:     }
Chris@16: 
Chris@16: public:
Chris@16: // Assign methods
Chris@16: 
Chris@16:     //! The assign operator.
Chris@16:     /*!
Chris@16:         Makes this <code>circular_buffer</code> to become a copy of the specified <code>circular_buffer</code>.
Chris@16:         \post <code>*this == cb</code>
Chris@16:         \param cb The <code>circular_buffer</code> to be copied.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T(const T&)</code> throws.
Chris@16:         \par Exception Safety
Chris@16:              Strong.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to this <code>circular_buffer</code> (except iterators equal to
Chris@16:              <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in the size of <code>cb</code>).
Chris@16:         \sa <code>\link assign(size_type, param_value_type) assign(size_type, const_reference)\endlink</code>,
Chris@16:             <code>\link assign(capacity_type, size_type, param_value_type)
Chris@16:             assign(capacity_type, size_type, const_reference)\endlink</code>,
Chris@16:             <code>assign(InputIterator, InputIterator)</code>,
Chris@16:             <code>assign(capacity_type, InputIterator, InputIterator)</code>
Chris@16:     */
Chris@16:     circular_buffer<T, Alloc>& operator = (const circular_buffer<T, Alloc>& cb) {
Chris@16:         if (this == &cb)
Chris@16:             return *this;
Chris@16:         pointer buff = allocate(cb.capacity());
Chris@16:         BOOST_TRY {
Chris@101:             reset(buff, cb_details::uninitialized_copy(cb.begin(), cb.end(), buff, m_alloc), cb.capacity());
Chris@16:         } BOOST_CATCH(...) {
Chris@16:             deallocate(buff, cb.capacity());
Chris@16:             BOOST_RETHROW
Chris@16:         }
Chris@16:         BOOST_CATCH_END
Chris@16:         return *this;
Chris@16:     }
Chris@16: 
Chris@16: #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
Chris@16:     /*! \brief Move assigns content of <code>cb</code> to <code>*this</code>, leaving <code>cb</code> empty.
Chris@16:         \pre C++ compiler with rvalue references support.
Chris@16:         \post <code>cb.empty()</code>
Chris@16:         \param cb <code>circular_buffer</code> to 'steal' value from.
Chris@16:         \throws Nothing.
Chris@16:         \par Complexity
Chris@16:              Constant.
Chris@16:     */
Chris@16:     circular_buffer<T, Alloc>& operator = (circular_buffer<T, Alloc>&& cb) BOOST_NOEXCEPT {
Chris@16:         cb.swap(*this); // now `this` holds `cb`
Chris@16:         circular_buffer<T, Alloc>(get_allocator()) // temprary that holds initial `cb` allocator
Chris@16:             .swap(cb); // makes `cb` empty
Chris@16:         return *this;
Chris@16:     }
Chris@16: #endif // BOOST_NO_CXX11_RVALUE_REFERENCES
Chris@16: 
Chris@16:     //! Assign <code>n</code> items into the <code>circular_buffer</code>.
Chris@16:     /*!
Chris@16:         The content of the <code>circular_buffer</code> will be removed and replaced with <code>n</code> copies of the
Chris@16:         <code>item</code>.
Chris@16:         \post <code>capacity() == n \&\& size() == n \&\& (*this)[0] == item \&\& (*this)[1] == item \&\& ... \&\&
Chris@16:               (*this) [n - 1] == item</code>
Chris@16:         \param n The number of elements the <code>circular_buffer</code> will be filled with.
Chris@16:         \param item The element the <code>circular_buffer</code> will be filled with.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T(const T&)</code> throws.
Chris@16:         \par Exception Safety
Chris@16:              Basic.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
Chris@16:              <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in the <code>n</code>).
Chris@16:         \sa <code>\link operator=(const circular_buffer&) operator=\endlink</code>,
Chris@16:             <code>\link assign(capacity_type, size_type, param_value_type)
Chris@16:             assign(capacity_type, size_type, const_reference)\endlink</code>,
Chris@16:             <code>assign(InputIterator, InputIterator)</code>,
Chris@16:             <code>assign(capacity_type, InputIterator, InputIterator)</code>
Chris@16:     */
Chris@16:     void assign(size_type n, param_value_type item) {
Chris@16:         assign_n(n, n, cb_details::assign_n<param_value_type, allocator_type>(n, item, m_alloc));
Chris@16:     }
Chris@16: 
Chris@16:     //! Assign <code>n</code> items into the <code>circular_buffer</code> specifying the capacity.
Chris@16:     /*!
Chris@16:         The capacity of the <code>circular_buffer</code> will be set to the specified value and the content of the
Chris@16:         <code>circular_buffer</code> will be removed and replaced with <code>n</code> copies of the <code>item</code>.
Chris@16:         \pre <code>capacity >= n</code>
Chris@16:         \post <code>capacity() == buffer_capacity \&\& size() == n \&\& (*this)[0] == item \&\& (*this)[1] == item
Chris@16:               \&\& ... \&\& (*this) [n - 1] == item </code>
Chris@16:         \param buffer_capacity The new capacity.
Chris@16:         \param n The number of elements the <code>circular_buffer</code> will be filled with.
Chris@16:         \param item The element the <code>circular_buffer</code> will be filled with.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T(const T&)</code> throws.
Chris@16:         \par Exception Safety
Chris@16:              Basic.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
Chris@16:              <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in the <code>n</code>).
Chris@16:         \sa <code>\link operator=(const circular_buffer&) operator=\endlink</code>,
Chris@16:             <code>\link assign(size_type, param_value_type) assign(size_type, const_reference)\endlink</code>,
Chris@16:             <code>assign(InputIterator, InputIterator)</code>,
Chris@16:             <code>assign(capacity_type, InputIterator, InputIterator)</code>
Chris@16:     */
Chris@16:     void assign(capacity_type buffer_capacity, size_type n, param_value_type item) {
Chris@16:         BOOST_CB_ASSERT(buffer_capacity >= n); // check for new capacity lower than n
Chris@16:         assign_n(buffer_capacity, n, cb_details::assign_n<param_value_type, allocator_type>(n, item, m_alloc));
Chris@16:     }
Chris@16: 
Chris@16:     //! Assign a copy of the range into the <code>circular_buffer</code>.
Chris@16:     /*!
Chris@16:         The content of the <code>circular_buffer</code> will be removed and replaced with copies of elements from the
Chris@16:         specified range.
Chris@16:         \pre Valid range <code>[first, last)</code>.<br>
Chris@16:              <code>first</code> and <code>last</code> have to meet the requirements of
Chris@16:              <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
Chris@16:         \post <code>capacity() == std::distance(first, last) \&\& size() == std::distance(first, last) \&\&
Chris@16:              (*this)[0]== *first \&\& (*this)[1] == *(first + 1) \&\& ... \&\& (*this)[std::distance(first, last) - 1]
Chris@16:              == *(last - 1)</code>
Chris@16:         \param first The beginning of the range to be copied.
Chris@16:         \param last The end of the range to be copied.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T(const T&)</code> throws.
Chris@16:         \par Exception Safety
Chris@16:              Basic.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
Chris@16:              <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in the <code>std::distance(first, last)</code>).
Chris@16:         \sa <code>\link operator=(const circular_buffer&) operator=\endlink</code>,
Chris@16:             <code>\link assign(size_type, param_value_type) assign(size_type, const_reference)\endlink</code>,
Chris@16:             <code>\link assign(capacity_type, size_type, param_value_type)
Chris@16:             assign(capacity_type, size_type, const_reference)\endlink</code>,
Chris@16:             <code>assign(capacity_type, InputIterator, InputIterator)</code>
Chris@16:     */
Chris@16:     template <class InputIterator>
Chris@16:     void assign(InputIterator first, InputIterator last) {
Chris@16:         assign(first, last, is_integral<InputIterator>());
Chris@16:     }
Chris@16: 
Chris@16:     //! Assign a copy of the range into the <code>circular_buffer</code> specifying the capacity.
Chris@16:     /*!
Chris@16:         The capacity of the <code>circular_buffer</code> will be set to the specified value and the content of the
Chris@16:         <code>circular_buffer</code> will be removed and replaced with copies of elements from the specified range.
Chris@16:         \pre Valid range <code>[first, last)</code>.<br>
Chris@16:              <code>first</code> and <code>last</code> have to meet the requirements of
Chris@16:              <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
Chris@16:         \post <code>capacity() == buffer_capacity \&\& size() \<= std::distance(first, last) \&\&
Chris@16:              (*this)[0]== *(last - buffer_capacity) \&\& (*this)[1] == *(last - buffer_capacity + 1) \&\& ... \&\&
Chris@16:              (*this)[buffer_capacity - 1] == *(last - 1)</code><br><br>
Chris@16:              If the number of items to be copied from the range <code>[first, last)</code> is greater than the
Chris@16:              specified <code>buffer_capacity</code> then only elements from the range
Chris@16:              <code>[last - buffer_capacity, last)</code> will be copied.
Chris@16:         \param buffer_capacity The new capacity.
Chris@16:         \param first The beginning of the range to be copied.
Chris@16:         \param last The end of the range to be copied.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T(const T&)</code> throws.
Chris@16:         \par Exception Safety
Chris@16:              Basic.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
Chris@16:              <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in <code>std::distance(first, last)</code>; in
Chris@16:              <code>min[capacity, std::distance(first, last)]</code> if the <code>InputIterator</code> is a
Chris@16:              <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>).
Chris@16:         \sa <code>\link operator=(const circular_buffer&) operator=\endlink</code>,
Chris@16:             <code>\link assign(size_type, param_value_type) assign(size_type, const_reference)\endlink</code>,
Chris@16:             <code>\link assign(capacity_type, size_type, param_value_type)
Chris@16:             assign(capacity_type, size_type, const_reference)\endlink</code>,
Chris@16:             <code>assign(InputIterator, InputIterator)</code>
Chris@16:     */
Chris@16:     template <class InputIterator>
Chris@16:     void assign(capacity_type buffer_capacity, InputIterator first, InputIterator last) {
Chris@16:         assign(buffer_capacity, first, last, is_integral<InputIterator>());
Chris@16:     }
Chris@16: 
Chris@16:     //! Swap the contents of two <code>circular_buffer</code>s.
Chris@16:     /*!
Chris@16:         \post <code>this</code> contains elements of <code>cb</code> and vice versa; the capacity of <code>this</code>
Chris@16:               equals to the capacity of <code>cb</code> and vice versa.
Chris@16:         \param cb The <code>circular_buffer</code> whose content will be swapped.
Chris@16:         \throws Nothing.
Chris@16:         \par Exception Safety
Chris@16:              No-throw.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators of both <code>circular_buffer</code>s. (On the other hand the iterators still
Chris@16:              point to the same elements but within another container. If you want to rely on this feature you have to
Chris@16:              turn the <a href="#debug">Debug Support</a> off otherwise an assertion will report an error if such
Chris@16:              invalidated iterator is used.)
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>swap(circular_buffer<T, Alloc>&, circular_buffer<T, Alloc>&)</code>
Chris@16:     */
Chris@16:     void swap(circular_buffer<T, Alloc>& cb) BOOST_NOEXCEPT {
Chris@16:         swap_allocator(cb, is_stateless<allocator_type>());
Chris@16:         std::swap(m_buff, cb.m_buff);
Chris@16:         std::swap(m_end, cb.m_end);
Chris@16:         std::swap(m_first, cb.m_first);
Chris@16:         std::swap(m_last, cb.m_last);
Chris@16:         std::swap(m_size, cb.m_size);
Chris@16: #if BOOST_CB_ENABLE_DEBUG
Chris@16:         invalidate_all_iterators();
Chris@16:         cb.invalidate_all_iterators();
Chris@16: #endif
Chris@16:     }
Chris@16: 
Chris@16: // push and pop
Chris@16: private:
Chris@16:     template <class ValT>
Chris@16:     void push_back_impl(ValT item) {
Chris@16:         if (full()) {
Chris@16:             if (empty())
Chris@16:                 return;
Chris@16:             replace(m_last, static_cast<ValT>(item));
Chris@16:             increment(m_last);
Chris@16:             m_first = m_last;
Chris@16:         } else {
Chris@101:             boost::container::allocator_traits<Alloc>::construct(m_alloc, boost::addressof(*m_last), static_cast<ValT>(item));
Chris@16:             increment(m_last);
Chris@16:             ++m_size;
Chris@16:         }        
Chris@16:     }
Chris@16: 
Chris@16:     template <class ValT>
Chris@16:     void push_front_impl(ValT item) {
Chris@16:         BOOST_TRY {
Chris@16:             if (full()) {
Chris@16:                 if (empty())
Chris@16:                     return;
Chris@16:                 decrement(m_first);
Chris@16:                 replace(m_first, static_cast<ValT>(item));
Chris@16:                 m_last = m_first;
Chris@16:             } else {
Chris@16:                 decrement(m_first);
Chris@101:                 boost::container::allocator_traits<Alloc>::construct(m_alloc, boost::addressof(*m_first), static_cast<ValT>(item));
Chris@16:                 ++m_size;
Chris@16:             }
Chris@16:         } BOOST_CATCH(...) {
Chris@16:             increment(m_first);
Chris@16:             BOOST_RETHROW
Chris@16:         }
Chris@16:         BOOST_CATCH_END
Chris@16:     }
Chris@16: 
Chris@16: public:
Chris@16:     //! Insert a new element at the end of the <code>circular_buffer</code>.
Chris@16:     /*!
Chris@16:         \post if <code>capacity() > 0</code> then <code>back() == item</code><br>
Chris@16:               If the <code>circular_buffer</code> is full, the first element will be removed. If the capacity is
Chris@16:               <code>0</code>, nothing will be inserted.
Chris@16:         \param item The element to be inserted.
Chris@16:         \throws Whatever <code>T::T(const T&)</code> throws.
Chris@16:                 Whatever <code>T::operator = (const T&)</code> throws.
Chris@16:         \par Exception Safety
Chris@16:              Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators with the exception of iterators pointing to the overwritten element.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>\link push_front() push_front(const_reference)\endlink</code>,
Chris@16:             <code>pop_back()</code>, <code>pop_front()</code>
Chris@16:     */
Chris@16:     void push_back(param_value_type item) {
Chris@16:         push_back_impl<param_value_type>(item);
Chris@16:     }
Chris@16: 
Chris@16:     //! Insert a new element at the end of the <code>circular_buffer</code> using rvalue references or rvalues references emulation.
Chris@16:     /*!
Chris@16:         \post if <code>capacity() > 0</code> then <code>back() == item</code><br>
Chris@16:               If the <code>circular_buffer</code> is full, the first element will be removed. If the capacity is
Chris@16:               <code>0</code>, nothing will be inserted.
Chris@16:         \param item The element to be inserted.
Chris@16:         \throws Whatever <code>T::T(T&&)</code> throws.
Chris@16:                 Whatever <code>T::operator = (T&&)</code> throws.
Chris@16:         \par Exception Safety
Chris@16:              Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators with the exception of iterators pointing to the overwritten element.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>\link push_front() push_front(const_reference)\endlink</code>,
Chris@16:             <code>pop_back()</code>, <code>pop_front()</code>
Chris@16:     */
Chris@16:     void push_back(rvalue_type item) {
Chris@16:         push_back_impl<rvalue_type>(boost::move(item));
Chris@16:     }
Chris@16: 
Chris@16:     //! Insert a new default-constructed element at the end of the <code>circular_buffer</code>.
Chris@16:     /*!
Chris@16:         \post if <code>capacity() > 0</code> then <code>back() == item</code><br>
Chris@16:               If the <code>circular_buffer</code> is full, the first element will be removed. If the capacity is
Chris@16:               <code>0</code>, nothing will be inserted.
Chris@16:         \throws Whatever <code>T::T()</code> throws.
Chris@16:                 Whatever <code>T::T(T&&)</code> throws.
Chris@16:                 Whatever <code>T::operator = (T&&)</code> throws.
Chris@16:         \par Exception Safety
Chris@16:              Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators with the exception of iterators pointing to the overwritten element.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>\link push_front() push_front(const_reference)\endlink</code>,
Chris@16:             <code>pop_back()</code>, <code>pop_front()</code>
Chris@16:     */
Chris@16:     void push_back() {
Chris@16:         value_type temp;
Chris@16:         push_back(boost::move(temp));
Chris@16:     }
Chris@16: 
Chris@16:     //! Insert a new element at the beginning of the <code>circular_buffer</code>.
Chris@16:     /*!
Chris@16:         \post if <code>capacity() > 0</code> then <code>front() == item</code><br>
Chris@16:               If the <code>circular_buffer</code> is full, the last element will be removed. If the capacity is
Chris@16:               <code>0</code>, nothing will be inserted.
Chris@16:         \param item The element to be inserted.
Chris@16:         \throws Whatever <code>T::T(const T&)</code> throws.
Chris@16:                 Whatever <code>T::operator = (const T&)</code> throws.
Chris@16:         \par Exception Safety
Chris@16:              Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators with the exception of iterators pointing to the overwritten element.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>\link push_back() push_back(const_reference)\endlink</code>,
Chris@16:             <code>pop_back()</code>, <code>pop_front()</code>
Chris@16:     */
Chris@16:     void push_front(param_value_type item) {
Chris@16:         push_front_impl<param_value_type>(item);
Chris@16:     }
Chris@16: 
Chris@16:     //! Insert a new element at the beginning of the <code>circular_buffer</code> using rvalue references or rvalues references emulation.
Chris@16:     /*!
Chris@16:         \post if <code>capacity() > 0</code> then <code>front() == item</code><br>
Chris@16:               If the <code>circular_buffer</code> is full, the last element will be removed. If the capacity is
Chris@16:               <code>0</code>, nothing will be inserted.
Chris@16:         \param item The element to be inserted.
Chris@16:         \throws Whatever <code>T::T(T&&)</code> throws.
Chris@16:                 Whatever <code>T::operator = (T&&)</code> throws.
Chris@16:         \par Exception Safety
Chris@16:              Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators with the exception of iterators pointing to the overwritten element.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>\link push_back() push_back(const_reference)\endlink</code>,
Chris@16:             <code>pop_back()</code>, <code>pop_front()</code>
Chris@16:     */
Chris@16:     void push_front(rvalue_type item) {
Chris@16:         push_front_impl<rvalue_type>(boost::move(item));
Chris@16:     }
Chris@16: 
Chris@16:     //! Insert a new default-constructed element at the beginning of the <code>circular_buffer</code>.
Chris@16:     /*!
Chris@16:         \post if <code>capacity() > 0</code> then <code>front() == item</code><br>
Chris@16:               If the <code>circular_buffer</code> is full, the last element will be removed. If the capacity is
Chris@16:               <code>0</code>, nothing will be inserted.
Chris@16:         \throws Whatever <code>T::T()</code> throws.
Chris@16:                 Whatever <code>T::T(T&&)</code> throws.
Chris@16:                 Whatever <code>T::operator = (T&&)</code> throws.
Chris@16:         \par Exception Safety
Chris@16:              Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators with the exception of iterators pointing to the overwritten element.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>\link push_back() push_back(const_reference)\endlink</code>,
Chris@16:             <code>pop_back()</code>, <code>pop_front()</code>
Chris@16:     */
Chris@16:     void push_front() {
Chris@16:         value_type temp;
Chris@16:         push_front(boost::move(temp));
Chris@16:     }
Chris@16: 
Chris@16:     //! Remove the last element from the <code>circular_buffer</code>.
Chris@16:     /*!
Chris@16:         \pre <code>!empty()</code>
Chris@16:         \post The last element is removed from the <code>circular_buffer</code>.
Chris@16:         \throws Nothing.
Chris@16:         \par Exception Safety
Chris@16:              No-throw.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates only iterators pointing to the removed element.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>pop_front()</code>, <code>\link push_back() push_back(const_reference)\endlink</code>,
Chris@16:             <code>\link push_front() push_front(const_reference)\endlink</code>
Chris@16:     */
Chris@16:     void pop_back() {
Chris@16:         BOOST_CB_ASSERT(!empty()); // check for empty buffer (back element not available)
Chris@16:         decrement(m_last);
Chris@16:         destroy_item(m_last);
Chris@16:         --m_size;
Chris@16:     }
Chris@16: 
Chris@16:     //! Remove the first element from the <code>circular_buffer</code>.
Chris@16:     /*!
Chris@16:         \pre <code>!empty()</code>
Chris@16:         \post The first element is removed from the <code>circular_buffer</code>.
Chris@16:         \throws Nothing.
Chris@16:         \par Exception Safety
Chris@16:              No-throw.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates only iterators pointing to the removed element.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>).
Chris@16:         \sa <code>pop_back()</code>, <code>\link push_back() push_back(const_reference)\endlink</code>,
Chris@16:             <code>\link push_front() push_front(const_reference)\endlink</code>
Chris@16:     */
Chris@16:     void pop_front() {
Chris@16:         BOOST_CB_ASSERT(!empty()); // check for empty buffer (front element not available)
Chris@16:         destroy_item(m_first);
Chris@16:         increment(m_first);
Chris@16:         --m_size;
Chris@16:     }
Chris@16: private:
Chris@16:     template <class ValT>
Chris@16:     iterator insert_impl(iterator pos, ValT item) {
Chris@16:         BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator
Chris@16:         iterator b = begin();
Chris@16:         if (full() && pos == b)
Chris@16:             return b;
Chris@16:         return insert_item<ValT>(pos, static_cast<ValT>(item));
Chris@16:     }
Chris@16: 
Chris@16: public:
Chris@16: // Insert
Chris@16: 
Chris@16:     //! Insert an element at the specified position.
Chris@16:     /*!
Chris@16:         \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.
Chris@16:         \post The <code>item</code> will be inserted at the position <code>pos</code>.<br>
Chris@16:               If the <code>circular_buffer</code> is full, the first element will be overwritten. If the
Chris@16:               <code>circular_buffer</code> is full and the <code>pos</code> points to <code>begin()</code>, then the
Chris@16:               <code>item</code> will not be inserted. If the capacity is <code>0</code>, nothing will be inserted.
Chris@16:         \param pos An iterator specifying the position where the <code>item</code> will be inserted.
Chris@16:         \param item The element to be inserted.
Chris@16:         \return Iterator to the inserted element or <code>begin()</code> if the <code>item</code> is not inserted. (See
Chris@16:                 the <i>Effect</i>.)
Chris@16:         \throws Whatever <code>T::T(const T&)</code> throws.
Chris@16:                 Whatever <code>T::operator = (const T&)</code> throws.
Chris@16:                 <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
Chris@16:          
Chris@16:         \par Exception Safety
Chris@16:              Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates iterators pointing to the elements at the insertion point (including <code>pos</code>) and
Chris@16:              iterators behind the insertion point (towards the end; except iterators equal to <code>end()</code>). It
Chris@16:              also invalidates iterators pointing to the overwritten element.
Chris@16:         \par Complexity
Chris@16:              Linear (in <code>std::distance(pos, end())</code>).
Chris@16:         \sa <code>\link insert(iterator, size_type, param_value_type)
Chris@16:             insert(iterator, size_type, value_type)\endlink</code>,
Chris@16:             <code>insert(iterator, InputIterator, InputIterator)</code>,
Chris@16:             <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>,
Chris@16:             <code>\link rinsert(iterator, size_type, param_value_type)
Chris@16:             rinsert(iterator, size_type, value_type)\endlink</code>,
Chris@16:             <code>rinsert(iterator, InputIterator, InputIterator)</code>
Chris@16:     */
Chris@16:     iterator insert(iterator pos, param_value_type item) {
Chris@16:         return insert_impl<param_value_type>(pos, item);
Chris@16:     }
Chris@16: 
Chris@16:     //! Insert an element at the specified position.
Chris@16:     /*!
Chris@16:         \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.
Chris@16:         \post The <code>item</code> will be inserted at the position <code>pos</code>.<br>
Chris@16:               If the <code>circular_buffer</code> is full, the first element will be overwritten. If the
Chris@16:               <code>circular_buffer</code> is full and the <code>pos</code> points to <code>begin()</code>, then the
Chris@16:               <code>item</code> will not be inserted. If the capacity is <code>0</code>, nothing will be inserted.
Chris@16:         \param pos An iterator specifying the position where the <code>item</code> will be inserted.
Chris@16:         \param item The element to be inserted.
Chris@16:         \return Iterator to the inserted element or <code>begin()</code> if the <code>item</code> is not inserted. (See
Chris@16:                 the <i>Effect</i>.)
Chris@16:         \throws Whatever <code>T::T(T&&)</code> throws.
Chris@16:                 Whatever <code>T::operator = (T&&)</code> throws.
Chris@16:                 <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
Chris@16:         \par Exception Safety
Chris@16:              Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates iterators pointing to the elements at the insertion point (including <code>pos</code>) and
Chris@16:              iterators behind the insertion point (towards the end; except iterators equal to <code>end()</code>). It
Chris@16:              also invalidates iterators pointing to the overwritten element.
Chris@16:         \par Complexity
Chris@16:              Linear (in <code>std::distance(pos, end())</code>).
Chris@16:         \sa <code>\link insert(iterator, size_type, param_value_type)
Chris@16:             insert(iterator, size_type, value_type)\endlink</code>,
Chris@16:             <code>insert(iterator, InputIterator, InputIterator)</code>,
Chris@16:             <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>,
Chris@16:             <code>\link rinsert(iterator, size_type, param_value_type)
Chris@16:             rinsert(iterator, size_type, value_type)\endlink</code>,
Chris@16:             <code>rinsert(iterator, InputIterator, InputIterator)</code>
Chris@16:     */
Chris@16:     iterator insert(iterator pos, rvalue_type item) {
Chris@16:         return insert_impl<rvalue_type>(pos, boost::move(item));
Chris@16:     }
Chris@16: 
Chris@16:     //! Insert a default-constructed element at the specified position.
Chris@16:     /*!
Chris@16:         \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.
Chris@16:         \post The <code>item</code> will be inserted at the position <code>pos</code>.<br>
Chris@16:               If the <code>circular_buffer</code> is full, the first element will be overwritten. If the
Chris@16:               <code>circular_buffer</code> is full and the <code>pos</code> points to <code>begin()</code>, then the
Chris@16:               <code>item</code> will not be inserted. If the capacity is <code>0</code>, nothing will be inserted.
Chris@16:         \param pos An iterator specifying the position where the <code>item</code> will be inserted.
Chris@16:         \return Iterator to the inserted element or <code>begin()</code> if the <code>item</code> is not inserted. (See
Chris@16:                 the <i>Effect</i>.)
Chris@16:         \throws Whatever <code>T::T()</code> throws.
Chris@16:                 Whatever <code>T::T(T&&)</code> throws.
Chris@16:                 Whatever <code>T::operator = (T&&)</code> throws.
Chris@16:                 <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
Chris@16:         \par Exception Safety
Chris@16:              Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates iterators pointing to the elements at the insertion point (including <code>pos</code>) and
Chris@16:              iterators behind the insertion point (towards the end; except iterators equal to <code>end()</code>). It
Chris@16:              also invalidates iterators pointing to the overwritten element.
Chris@16:         \par Complexity
Chris@16:              Linear (in <code>std::distance(pos, end())</code>).
Chris@16:         \sa <code>\link insert(iterator, size_type, param_value_type)
Chris@16:             insert(iterator, size_type, value_type)\endlink</code>,
Chris@16:             <code>insert(iterator, InputIterator, InputIterator)</code>,
Chris@16:             <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>,
Chris@16:             <code>\link rinsert(iterator, size_type, param_value_type)
Chris@16:             rinsert(iterator, size_type, value_type)\endlink</code>,
Chris@16:             <code>rinsert(iterator, InputIterator, InputIterator)</code>
Chris@16:     */
Chris@16:     iterator insert(iterator pos) {
Chris@16:         value_type temp;
Chris@16:         return insert(pos, boost::move(temp));
Chris@16:     }
Chris@16: 
Chris@16:     //! Insert <code>n</code> copies of the <code>item</code> at the specified position.
Chris@16:     /*!
Chris@16:         \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.
Chris@16:         \post The number of <code>min[n, (pos - begin()) + reserve()]</code> elements will be inserted at the position
Chris@16:               <code>pos</code>.<br>The number of <code>min[pos - begin(), max[0, n - reserve()]]</code> elements will
Chris@16:               be overwritten at the beginning of the <code>circular_buffer</code>.<br>(See <i>Example</i> for the
Chris@16:               explanation.)
Chris@16:         \param pos An iterator specifying the position where the <code>item</code>s will be inserted.
Chris@16:         \param n The number of <code>item</code>s the to be inserted.
Chris@16:         \param item The element whose copies will be inserted.
Chris@16:         \throws Whatever <code>T::T(const T&)</code> throws.
Chris@16:                 Whatever <code>T::operator = (const T&)</code> throws.
Chris@16:                 <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
Chris@16:         \par Exception Safety
Chris@16:              Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates iterators pointing to the elements at the insertion point (including <code>pos</code>) and
Chris@16:              iterators behind the insertion point (towards the end; except iterators equal to <code>end()</code>). It
Chris@16:              also invalidates iterators pointing to the overwritten elements.
Chris@16:         \par Complexity
Chris@16:              Linear (in <code>min[capacity(), std::distance(pos, end()) + n]</code>).
Chris@16:         \par Example
Chris@16:              Consider a <code>circular_buffer</code> with the capacity of 6 and the size of 4. Its internal buffer may
Chris@16:              look like the one below.<br><br>
Chris@16:              <code>|1|2|3|4| | |</code><br>
Chris@16:              <code>p ___^</code><br><br>After inserting 5 elements at the position <code>p</code>:<br><br>
Chris@16:              <code>insert(p, (size_t)5, 0);</code><br><br>actually only 4 elements get inserted and elements
Chris@16:              <code>1</code> and <code>2</code> are overwritten. This is due to the fact the insert operation preserves
Chris@16:              the capacity. After insertion the internal buffer looks like this:<br><br><code>|0|0|0|0|3|4|</code><br>
Chris@16:              <br>For comparison if the capacity would not be preserved the internal buffer would then result in
Chris@16:              <code>|1|2|0|0|0|0|0|3|4|</code>.
Chris@16:         \sa <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>,
Chris@16:             <code>insert(iterator, InputIterator, InputIterator)</code>,
Chris@16:             <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>,
Chris@16:             <code>\link rinsert(iterator, size_type, param_value_type)
Chris@16:             rinsert(iterator, size_type, value_type)\endlink</code>,
Chris@16:             <code>rinsert(iterator, InputIterator, InputIterator)</code>
Chris@16:     */
Chris@16:     void insert(iterator pos, size_type n, param_value_type item) {
Chris@16:         BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator
Chris@16:         if (n == 0)
Chris@16:             return;
Chris@16:         size_type copy = capacity() - (end() - pos);
Chris@16:         if (copy == 0)
Chris@16:             return;
Chris@16:         if (n > copy)
Chris@16:             n = copy;
Chris@16:         insert_n(pos, n, cb_details::item_wrapper<const_pointer, param_value_type>(item));
Chris@16:     }
Chris@16: 
Chris@16:     //! Insert the range <code>[first, last)</code> at the specified position.
Chris@16:     /*!
Chris@16:         \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.<br>
Chris@16:              Valid range <code>[first, last)</code> where <code>first</code> and <code>last</code> meet the
Chris@16:              requirements of an <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
Chris@16:         \post Elements from the range
Chris@16:               <code>[first + max[0, distance(first, last) - (pos - begin()) - reserve()], last)</code> will be
Chris@16:               inserted at the position <code>pos</code>.<br>The number of <code>min[pos - begin(), max[0,
Chris@16:               distance(first, last) - reserve()]]</code> elements will be overwritten at the beginning of the
Chris@16:               <code>circular_buffer</code>.<br>(See <i>Example</i> for the explanation.)
Chris@16:         \param pos An iterator specifying the position where the range will be inserted.
Chris@16:         \param first The beginning of the range to be inserted.
Chris@16:         \param last The end of the range to be inserted.
Chris@16:         \throws Whatever <code>T::T(const T&)</code> throws if the <code>InputIterator</code> is not a move iterator.
Chris@16:                 Whatever <code>T::operator = (const T&)</code> throws if the <code>InputIterator</code> is not a move iterator.
Chris@16:                 Whatever <code>T::T(T&&)</code> throws if the <code>InputIterator</code> is a move iterator.
Chris@16:                 Whatever <code>T::operator = (T&&)</code> throws if the <code>InputIterator</code> is a move iterator.
Chris@16:         \par Exception Safety
Chris@16:              Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates iterators pointing to the elements at the insertion point (including <code>pos</code>) and
Chris@16:              iterators behind the insertion point (towards the end; except iterators equal to <code>end()</code>). It
Chris@16:              also invalidates iterators pointing to the overwritten elements.
Chris@16:         \par Complexity
Chris@16:              Linear (in <code>[std::distance(pos, end()) + std::distance(first, last)]</code>; in
Chris@16:              <code>min[capacity(), std::distance(pos, end()) + std::distance(first, last)]</code> if the
Chris@16:              <code>InputIterator</code> is a
Chris@16:              <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>).
Chris@16:         \par Example
Chris@16:              Consider a <code>circular_buffer</code> with the capacity of 6 and the size of 4. Its internal buffer may
Chris@16:              look like the one below.<br><br>
Chris@16:              <code>|1|2|3|4| | |</code><br>
Chris@16:              <code>p ___^</code><br><br>After inserting a range of elements at the position <code>p</code>:<br><br>
Chris@16:              <code>int array[] = { 5, 6, 7, 8, 9 };</code><br><code>insert(p, array, array + 5);</code><br><br>
Chris@16:              actually only elements <code>6</code>, <code>7</code>, <code>8</code> and <code>9</code> from the
Chris@16:              specified range get inserted and elements <code>1</code> and <code>2</code> are overwritten. This is due
Chris@16:              to the fact the insert operation preserves the capacity. After insertion the internal buffer looks like
Chris@16:              this:<br><br><code>|6|7|8|9|3|4|</code><br><br>For comparison if the capacity would not be preserved the
Chris@16:              internal buffer would then result in <code>|1|2|5|6|7|8|9|3|4|</code>.
Chris@16:         \sa <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>,
Chris@16:             <code>\link insert(iterator, size_type, param_value_type)
Chris@16:             insert(iterator, size_type, value_type)\endlink</code>, <code>\link rinsert(iterator, param_value_type)
Chris@16:             rinsert(iterator, value_type)\endlink</code>, <code>\link rinsert(iterator, size_type, param_value_type)
Chris@16:             rinsert(iterator, size_type, value_type)\endlink</code>,
Chris@16:             <code>rinsert(iterator, InputIterator, InputIterator)</code>
Chris@16:     */
Chris@16:     template <class InputIterator>
Chris@16:     void insert(iterator pos, InputIterator first, InputIterator last) {
Chris@16:         BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator
Chris@16:         insert(pos, first, last, is_integral<InputIterator>());
Chris@16:     }
Chris@16: 
Chris@16: private:
Chris@16:     template <class ValT>
Chris@16:     iterator rinsert_impl(iterator pos, ValT item) {
Chris@16:         BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator
Chris@16:         if (full() && pos.m_it == 0)
Chris@16:             return end();
Chris@16:         if (pos == begin()) {
Chris@16:             BOOST_TRY {
Chris@16:                 decrement(m_first);
Chris@16:                 construct_or_replace(!full(), m_first, static_cast<ValT>(item));
Chris@16:             } BOOST_CATCH(...) {
Chris@16:                 increment(m_first);
Chris@16:                 BOOST_RETHROW
Chris@16:             }
Chris@16:             BOOST_CATCH_END
Chris@16:             pos.m_it = m_first;
Chris@16:         } else {
Chris@16:             pointer src = m_first;
Chris@16:             pointer dest = m_first;
Chris@16:             decrement(dest);
Chris@16:             pos.m_it = map_pointer(pos.m_it);
Chris@16:             bool construct = !full();
Chris@16:             BOOST_TRY {
Chris@16:                 while (src != pos.m_it) {
Chris@101:                     construct_or_replace(construct, dest, boost::move_if_noexcept(*src));
Chris@16:                     increment(src);
Chris@16:                     increment(dest);
Chris@16:                     construct = false;
Chris@16:                 }
Chris@16:                 decrement(pos.m_it);
Chris@16:                 replace(pos.m_it, static_cast<ValT>(item));
Chris@16:             } BOOST_CATCH(...) {
Chris@16:                 if (!construct && !full()) {
Chris@16:                     decrement(m_first);
Chris@16:                     ++m_size;
Chris@16:                 }
Chris@16:                 BOOST_RETHROW
Chris@16:             }
Chris@16:             BOOST_CATCH_END
Chris@16:             decrement(m_first);
Chris@16:         }
Chris@16:         if (full())
Chris@16:             m_last = m_first;
Chris@16:         else
Chris@16:             ++m_size;
Chris@16:         return iterator(this, pos.m_it);
Chris@16:     }
Chris@16: 
Chris@16: public:
Chris@16:    
Chris@16:     //! Insert an element before the specified position.
Chris@16:     /*!
Chris@16:         \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.
Chris@16:         \post The <code>item</code> will be inserted before the position <code>pos</code>.<br>
Chris@16:               If the <code>circular_buffer</code> is full, the last element will be overwritten. If the
Chris@16:               <code>circular_buffer</code> is full and the <code>pos</code> points to <code>end()</code>, then the
Chris@16:               <code>item</code> will not be inserted. If the capacity is <code>0</code>, nothing will be inserted.
Chris@16:         \param pos An iterator specifying the position before which the <code>item</code> will be inserted.
Chris@16:         \param item The element to be inserted.
Chris@16:         \return Iterator to the inserted element or <code>end()</code> if the <code>item</code> is not inserted. (See
Chris@16:                 the <i>Effect</i>.)
Chris@16:         \throws Whatever <code>T::T(const T&)</code> throws.
Chris@16:                 Whatever <code>T::operator = (const T&)</code> throws.
Chris@16:                 <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
Chris@16:         \par Exception Safety
Chris@16:              Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates iterators pointing to the elements before the insertion point (towards the beginning and
Chris@16:              excluding <code>pos</code>). It also invalidates iterators pointing to the overwritten element.
Chris@16:         \par Complexity
Chris@16:              Linear (in <code>std::distance(begin(), pos)</code>).
Chris@16:         \sa <code>\link rinsert(iterator, size_type, param_value_type)
Chris@16:             rinsert(iterator, size_type, value_type)\endlink</code>,
Chris@16:             <code>rinsert(iterator, InputIterator, InputIterator)</code>,
Chris@16:             <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>,
Chris@16:             <code>\link insert(iterator, size_type, param_value_type)
Chris@16:             insert(iterator, size_type, value_type)\endlink</code>,
Chris@16:             <code>insert(iterator, InputIterator, InputIterator)</code>
Chris@16:     */
Chris@16:     iterator rinsert(iterator pos, param_value_type item) {
Chris@16:         return rinsert_impl<param_value_type>(pos, item);
Chris@16:     }
Chris@16: 
Chris@16:     //! Insert an element before the specified position.
Chris@16:     /*!
Chris@16:         \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.
Chris@16:         \post The <code>item</code> will be inserted before the position <code>pos</code>.<br>
Chris@16:               If the <code>circular_buffer</code> is full, the last element will be overwritten. If the
Chris@16:               <code>circular_buffer</code> is full and the <code>pos</code> points to <code>end()</code>, then the
Chris@16:               <code>item</code> will not be inserted. If the capacity is <code>0</code>, nothing will be inserted.
Chris@16:         \param pos An iterator specifying the position before which the <code>item</code> will be inserted.
Chris@16:         \param item The element to be inserted.
Chris@16:         \return Iterator to the inserted element or <code>end()</code> if the <code>item</code> is not inserted. (See
Chris@16:                 the <i>Effect</i>.)
Chris@16:         \throws Whatever <code>T::T(T&&)</code> throws.
Chris@16:                 Whatever <code>T::operator = (T&&)</code> throws.
Chris@16:                 <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
Chris@16:         \par Exception Safety
Chris@16:              Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates iterators pointing to the elements before the insertion point (towards the beginning and
Chris@16:              excluding <code>pos</code>). It also invalidates iterators pointing to the overwritten element.
Chris@16:         \par Complexity
Chris@16:              Linear (in <code>std::distance(begin(), pos)</code>).
Chris@16:         \sa <code>\link rinsert(iterator, size_type, param_value_type)
Chris@16:             rinsert(iterator, size_type, value_type)\endlink</code>,
Chris@16:             <code>rinsert(iterator, InputIterator, InputIterator)</code>,
Chris@16:             <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>,
Chris@16:             <code>\link insert(iterator, size_type, param_value_type)
Chris@16:             insert(iterator, size_type, value_type)\endlink</code>,
Chris@16:             <code>insert(iterator, InputIterator, InputIterator)</code>
Chris@16:     */
Chris@16:     iterator rinsert(iterator pos, rvalue_type item) {
Chris@16:         return rinsert_impl<rvalue_type>(pos, boost::move(item));
Chris@16:     }
Chris@16: 
Chris@16:     //! Insert an element before the specified position.
Chris@16:     /*!
Chris@16:         \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.
Chris@16:         \post The <code>item</code> will be inserted before the position <code>pos</code>.<br>
Chris@16:               If the <code>circular_buffer</code> is full, the last element will be overwritten. If the
Chris@16:               <code>circular_buffer</code> is full and the <code>pos</code> points to <code>end()</code>, then the
Chris@16:               <code>item</code> will not be inserted. If the capacity is <code>0</code>, nothing will be inserted.
Chris@16:         \param pos An iterator specifying the position before which the <code>item</code> will be inserted.
Chris@16:         \return Iterator to the inserted element or <code>end()</code> if the <code>item</code> is not inserted. (See
Chris@16:                 the <i>Effect</i>.)
Chris@16:         \throws Whatever <code>T::T()</code> throws.
Chris@16:                 Whatever <code>T::T(T&&)</code> throws.
Chris@16:                 Whatever <code>T::operator = (T&&)</code> throws.
Chris@16:                 <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
Chris@16:         \par Exception Safety
Chris@16:              Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates iterators pointing to the elements before the insertion point (towards the beginning and
Chris@16:              excluding <code>pos</code>). It also invalidates iterators pointing to the overwritten element.
Chris@16:         \par Complexity
Chris@16:              Linear (in <code>std::distance(begin(), pos)</code>).
Chris@16:         \sa <code>\link rinsert(iterator, size_type, param_value_type)
Chris@16:             rinsert(iterator, size_type, value_type)\endlink</code>,
Chris@16:             <code>rinsert(iterator, InputIterator, InputIterator)</code>,
Chris@16:             <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>,
Chris@16:             <code>\link insert(iterator, size_type, param_value_type)
Chris@16:             insert(iterator, size_type, value_type)\endlink</code>,
Chris@16:             <code>insert(iterator, InputIterator, InputIterator)</code>
Chris@16:     */
Chris@16:     iterator rinsert(iterator pos) {
Chris@16:         value_type temp;
Chris@16:         return rinsert(pos, boost::move(temp));
Chris@16:     }
Chris@16: 
Chris@16:     //! Insert <code>n</code> copies of the <code>item</code> before the specified position.
Chris@16:     /*!
Chris@16:         \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.
Chris@16:         \post The number of <code>min[n, (end() - pos) + reserve()]</code> elements will be inserted before the
Chris@16:               position <code>pos</code>.<br>The number of <code>min[end() - pos, max[0, n - reserve()]]</code> elements
Chris@16:               will be overwritten at the end of the <code>circular_buffer</code>.<br>(See <i>Example</i> for the
Chris@16:               explanation.)
Chris@16:         \param pos An iterator specifying the position where the <code>item</code>s will be inserted.
Chris@16:         \param n The number of <code>item</code>s the to be inserted.
Chris@16:         \param item The element whose copies will be inserted.
Chris@16:         \throws Whatever <code>T::T(const T&)</code> throws.
Chris@16:                 Whatever <code>T::operator = (const T&)</code> throws.
Chris@16:                 <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
Chris@16:         \par Exception Safety
Chris@16:              Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates iterators pointing to the elements before the insertion point (towards the beginning and
Chris@16:              excluding <code>pos</code>). It also invalidates iterators pointing to the overwritten elements.
Chris@16:         \par Complexity
Chris@16:              Linear (in <code>min[capacity(), std::distance(begin(), pos) + n]</code>).
Chris@16:         \par Example
Chris@16:              Consider a <code>circular_buffer</code> with the capacity of 6 and the size of 4. Its internal buffer may
Chris@16:              look like the one below.<br><br>
Chris@16:              <code>|1|2|3|4| | |</code><br>
Chris@16:              <code>p ___^</code><br><br>After inserting 5 elements before the position <code>p</code>:<br><br>
Chris@16:              <code>rinsert(p, (size_t)5, 0);</code><br><br>actually only 4 elements get inserted and elements
Chris@16:              <code>3</code> and <code>4</code> are overwritten. This is due to the fact the rinsert operation preserves
Chris@16:              the capacity. After insertion the internal buffer looks like this:<br><br><code>|1|2|0|0|0|0|</code><br>
Chris@16:              <br>For comparison if the capacity would not be preserved the internal buffer would then result in
Chris@16:              <code>|1|2|0|0|0|0|0|3|4|</code>.
Chris@16:         \sa <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>,
Chris@16:             <code>rinsert(iterator, InputIterator, InputIterator)</code>,
Chris@16:             <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>,
Chris@16:             <code>\link insert(iterator, size_type, param_value_type)
Chris@16:             insert(iterator, size_type, value_type)\endlink</code>,
Chris@16:             <code>insert(iterator, InputIterator, InputIterator)</code>
Chris@16:     */
Chris@16:     void rinsert(iterator pos, size_type n, param_value_type item) {
Chris@16:         BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator
Chris@16:         rinsert_n(pos, n, cb_details::item_wrapper<const_pointer, param_value_type>(item));
Chris@16:     }
Chris@16: 
Chris@16:     //! Insert the range <code>[first, last)</code> before the specified position.
Chris@16:     /*!
Chris@16:         \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.<br>
Chris@16:              Valid range <code>[first, last)</code> where <code>first</code> and <code>last</code> meet the
Chris@16:              requirements of an <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
Chris@16:         \post Elements from the range
Chris@16:               <code>[first, last - max[0, distance(first, last) - (end() - pos) - reserve()])</code> will be inserted
Chris@16:               before the position <code>pos</code>.<br>The number of <code>min[end() - pos, max[0,
Chris@16:               distance(first, last) - reserve()]]</code> elements will be overwritten at the end of the
Chris@16:               <code>circular_buffer</code>.<br>(See <i>Example</i> for the explanation.)
Chris@16:         \param pos An iterator specifying the position where the range will be inserted.
Chris@16:         \param first The beginning of the range to be inserted.
Chris@16:         \param last The end of the range to be inserted.
Chris@16:         \throws Whatever <code>T::T(const T&)</code> throws if the <code>InputIterator</code> is not a move iterator.
Chris@16:                 Whatever <code>T::operator = (const T&)</code> throws if the <code>InputIterator</code> is not a move iterator.
Chris@16:                 Whatever <code>T::T(T&&)</code> throws if the <code>InputIterator</code> is a move iterator.
Chris@16:                 Whatever <code>T::operator = (T&&)</code> throws if the <code>InputIterator</code> is a move iterator.
Chris@16:         \par Exception Safety
Chris@16:              Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates iterators pointing to the elements before the insertion point (towards the beginning and
Chris@16:              excluding <code>pos</code>). It also invalidates iterators pointing to the overwritten elements.
Chris@16:         \par Complexity
Chris@16:              Linear (in <code>[std::distance(begin(), pos) + std::distance(first, last)]</code>; in
Chris@16:              <code>min[capacity(), std::distance(begin(), pos) + std::distance(first, last)]</code> if the
Chris@16:              <code>InputIterator</code> is a
Chris@16:              <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>).
Chris@16:         \par Example
Chris@16:              Consider a <code>circular_buffer</code> with the capacity of 6 and the size of 4. Its internal buffer may
Chris@16:              look like the one below.<br><br>
Chris@16:              <code>|1|2|3|4| | |</code><br>
Chris@16:              <code>p ___^</code><br><br>After inserting a range of elements before the position <code>p</code>:<br><br>
Chris@16:              <code>int array[] = { 5, 6, 7, 8, 9 };</code><br><code>insert(p, array, array + 5);</code><br><br>
Chris@16:              actually only elements <code>5</code>, <code>6</code>, <code>7</code> and <code>8</code> from the
Chris@16:              specified range get inserted and elements <code>3</code> and <code>4</code> are overwritten. This is due
Chris@16:              to the fact the rinsert operation preserves the capacity. After insertion the internal buffer looks like
Chris@16:              this:<br><br><code>|1|2|5|6|7|8|</code><br><br>For comparison if the capacity would not be preserved the
Chris@16:              internal buffer would then result in <code>|1|2|5|6|7|8|9|3|4|</code>.
Chris@16:         \sa <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>,
Chris@16:             <code>\link rinsert(iterator, size_type, param_value_type)
Chris@16:             rinsert(iterator, size_type, value_type)\endlink</code>, <code>\link insert(iterator, param_value_type)
Chris@16:             insert(iterator, value_type)\endlink</code>, <code>\link insert(iterator, size_type, param_value_type)
Chris@16:             insert(iterator, size_type, value_type)\endlink</code>,
Chris@16:             <code>insert(iterator, InputIterator, InputIterator)</code>
Chris@16:     */
Chris@16:     template <class InputIterator>
Chris@16:     void rinsert(iterator pos, InputIterator first, InputIterator last) {
Chris@16:         BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator
Chris@16:         rinsert(pos, first, last, is_integral<InputIterator>());
Chris@16:     }
Chris@16: 
Chris@16: // Erase
Chris@16: 
Chris@16:     //! Remove an element at the specified position.
Chris@16:     /*!
Chris@16:         \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> (but not an
Chris@16:              <code>end()</code>).
Chris@16:         \post The element at the position <code>pos</code> is removed.
Chris@16:         \param pos An iterator pointing at the element to be removed.
Chris@16:         \return Iterator to the first element remaining beyond the removed element or <code>end()</code> if no such
Chris@16:                 element exists.
Chris@16:         \throws <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
Chris@16:         \par Exception Safety
Chris@16:              Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates iterators pointing to the erased element and iterators pointing to the elements behind
Chris@16:              the erased element (towards the end; except iterators equal to <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in <code>std::distance(pos, end())</code>).
Chris@16:         \sa <code>erase(iterator, iterator)</code>, <code>rerase(iterator)</code>,
Chris@16:             <code>rerase(iterator, iterator)</code>, <code>erase_begin(size_type)</code>,
Chris@16:             <code>erase_end(size_type)</code>, <code>clear()</code>
Chris@16:     */
Chris@16:     iterator erase(iterator pos) {
Chris@16:         BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator
Chris@16:         BOOST_CB_ASSERT(pos.m_it != 0);      // check for iterator pointing to end()
Chris@16:         pointer next = pos.m_it;
Chris@16:         increment(next);
Chris@16:         for (pointer p = pos.m_it; next != m_last; p = next, increment(next))
Chris@101:             replace(p, boost::move_if_noexcept(*next));
Chris@16:         decrement(m_last);
Chris@16:         destroy_item(m_last);
Chris@16:         --m_size;
Chris@16: #if BOOST_CB_ENABLE_DEBUG
Chris@16:         return m_last == pos.m_it ? end() : iterator(this, pos.m_it);
Chris@16: #else
Chris@16:         return m_last == pos.m_it ? end() : pos;
Chris@16: #endif
Chris@16:     }
Chris@16: 
Chris@16:     //! Erase the range <code>[first, last)</code>.
Chris@16:     /*!
Chris@16:         \pre Valid range <code>[first, last)</code>.
Chris@16:         \post The elements from the range <code>[first, last)</code> are removed. (If <code>first == last</code>
Chris@16:               nothing is removed.)
Chris@16:         \param first The beginning of the range to be removed.
Chris@16:         \param last The end of the range to be removed.
Chris@16:         \return Iterator to the first element remaining beyond the removed elements or <code>end()</code> if no such
Chris@16:                 element exists.
Chris@16:         \throws <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
Chris@16:         \par Exception Safety
Chris@16:              Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates iterators pointing to the erased elements and iterators pointing to the elements behind
Chris@16:              the erased range (towards the end; except iterators equal to <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in <code>std::distance(first, end())</code>).
Chris@16:         \sa <code>erase(iterator)</code>, <code>rerase(iterator)</code>, <code>rerase(iterator, iterator)</code>,
Chris@16:             <code>erase_begin(size_type)</code>, <code>erase_end(size_type)</code>, <code>clear()</code>
Chris@16:     */
Chris@16:     iterator erase(iterator first, iterator last) {
Chris@16:         BOOST_CB_ASSERT(first.is_valid(this)); // check for uninitialized or invalidated iterator
Chris@16:         BOOST_CB_ASSERT(last.is_valid(this));  // check for uninitialized or invalidated iterator
Chris@16:         BOOST_CB_ASSERT(first <= last);        // check for wrong range
Chris@16:         if (first == last)
Chris@16:             return first;
Chris@16:         pointer p = first.m_it;
Chris@16:         while (last.m_it != 0)
Chris@101:             replace((first++).m_it, boost::move_if_noexcept(*last++));
Chris@16:         do {
Chris@16:             decrement(m_last);
Chris@16:             destroy_item(m_last);
Chris@16:             --m_size;
Chris@16:         } while(m_last != first.m_it);
Chris@16:         return m_last == p ? end() : iterator(this, p);
Chris@16:     }
Chris@16: 
Chris@16:     //! Remove an element at the specified position.
Chris@16:     /*!
Chris@16:         \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> (but not an
Chris@16:              <code>end()</code>).
Chris@16:         \post The element at the position <code>pos</code> is removed.
Chris@16:         \param pos An iterator pointing at the element to be removed.
Chris@16:         \return Iterator to the first element remaining in front of the removed element or <code>begin()</code> if no
Chris@16:                 such element exists.
Chris@16:         \throws <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
Chris@16:         \par Exception Safety
Chris@16:              Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates iterators pointing to the erased element and iterators pointing to the elements in front of
Chris@16:              the erased element (towards the beginning).
Chris@16:         \par Complexity
Chris@16:              Linear (in <code>std::distance(begin(), pos)</code>).
Chris@16:         \note This method is symetric to the <code>erase(iterator)</code> method and is more effective than
Chris@16:               <code>erase(iterator)</code> if the iterator <code>pos</code> is close to the beginning of the
Chris@16:               <code>circular_buffer</code>. (See the <i>Complexity</i>.)
Chris@16:         \sa <code>erase(iterator)</code>, <code>erase(iterator, iterator)</code>,
Chris@16:             <code>rerase(iterator, iterator)</code>, <code>erase_begin(size_type)</code>,
Chris@16:             <code>erase_end(size_type)</code>, <code>clear()</code>
Chris@16:     */
Chris@16:     iterator rerase(iterator pos) {
Chris@16:         BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator
Chris@16:         BOOST_CB_ASSERT(pos.m_it != 0);      // check for iterator pointing to end()
Chris@16:         pointer prev = pos.m_it;
Chris@16:         pointer p = prev;
Chris@16:         for (decrement(prev); p != m_first; p = prev, decrement(prev))
Chris@101:             replace(p, boost::move_if_noexcept(*prev));
Chris@16:         destroy_item(m_first);
Chris@16:         increment(m_first);
Chris@16:         --m_size;
Chris@16: #if BOOST_CB_ENABLE_DEBUG
Chris@16:         return p == pos.m_it ? begin() : iterator(this, pos.m_it);
Chris@16: #else
Chris@16:         return p == pos.m_it ? begin() : pos;
Chris@16: #endif
Chris@16:     }
Chris@16: 
Chris@16:     //! Erase the range <code>[first, last)</code>.
Chris@16:     /*!
Chris@16:         \pre Valid range <code>[first, last)</code>.
Chris@16:         \post The elements from the range <code>[first, last)</code> are removed. (If <code>first == last</code>
Chris@16:               nothing is removed.)
Chris@16:         \param first The beginning of the range to be removed.
Chris@16:         \param last The end of the range to be removed.
Chris@16:         \return Iterator to the first element remaining in front of the removed elements or <code>begin()</code> if no
Chris@16:                 such element exists.
Chris@16:         \throws <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
Chris@16:         \par Exception Safety
Chris@16:              Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates iterators pointing to the erased elements and iterators pointing to the elements in front of
Chris@16:              the erased range (towards the beginning).
Chris@16:         \par Complexity
Chris@16:              Linear (in <code>std::distance(begin(), last)</code>).
Chris@16:         \note This method is symetric to the <code>erase(iterator, iterator)</code> method and is more effective than
Chris@16:               <code>erase(iterator, iterator)</code> if <code>std::distance(begin(), first)</code> is lower that
Chris@16:               <code>std::distance(last, end())</code>.
Chris@16:         \sa <code>erase(iterator)</code>, <code>erase(iterator, iterator)</code>, <code>rerase(iterator)</code>,
Chris@16:             <code>erase_begin(size_type)</code>, <code>erase_end(size_type)</code>, <code>clear()</code>
Chris@16:     */
Chris@16:     iterator rerase(iterator first, iterator last) {
Chris@16:         BOOST_CB_ASSERT(first.is_valid(this)); // check for uninitialized or invalidated iterator
Chris@16:         BOOST_CB_ASSERT(last.is_valid(this));  // check for uninitialized or invalidated iterator
Chris@16:         BOOST_CB_ASSERT(first <= last);        // check for wrong range
Chris@16:         if (first == last)
Chris@16:             return first;
Chris@16:         pointer p = map_pointer(last.m_it);
Chris@16:         last.m_it = p;
Chris@16:         while (first.m_it != m_first) {
Chris@16:             decrement(first.m_it);
Chris@16:             decrement(p);
Chris@101:             replace(p, boost::move_if_noexcept(*first.m_it));
Chris@16:         }
Chris@16:         do {
Chris@16:             destroy_item(m_first);
Chris@16:             increment(m_first);
Chris@16:             --m_size;
Chris@16:         } while(m_first != p);
Chris@16:         if (m_first == last.m_it)
Chris@16:             return begin();
Chris@16:         decrement(last.m_it);
Chris@16:         return iterator(this, last.m_it);
Chris@16:     }
Chris@16: 
Chris@16:     //! Remove first <code>n</code> elements (with constant complexity for scalar types).
Chris@16:     /*!
Chris@16:         \pre <code>n \<= size()</code>
Chris@16:         \post The <code>n</code> elements at the beginning of the <code>circular_buffer</code> will be removed.
Chris@16:         \param n The number of elements to be removed.
Chris@16:         \throws <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
Chris@16:         \par Exception Safety
Chris@16:              Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything. (I.e. no throw in
Chris@16:              case of scalars.)
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates iterators pointing to the first <code>n</code> erased elements.
Chris@16:         \par Complexity
Chris@16:              Constant (in <code>n</code>) for scalar types; linear for other types.
Chris@16:         \note This method has been specially designed for types which do not require an explicit destructruction (e.g.
Chris@16:               integer, float or a pointer). For these scalar types a call to a destructor is not required which makes
Chris@16:               it possible to implement the "erase from beginning" operation with a constant complexity. For non-sacalar
Chris@16:               types the complexity is linear (hence the explicit destruction is needed) and the implementation is
Chris@16:               actually equivalent to
Chris@16:               <code>\link circular_buffer::rerase(iterator, iterator) rerase(begin(), begin() + n)\endlink</code>.
Chris@16:         \sa <code>erase(iterator)</code>, <code>erase(iterator, iterator)</code>,
Chris@16:             <code>rerase(iterator)</code>, <code>rerase(iterator, iterator)</code>,
Chris@16:             <code>erase_end(size_type)</code>, <code>clear()</code>
Chris@16:     */
Chris@16:     void erase_begin(size_type n) {
Chris@16:         BOOST_CB_ASSERT(n <= size()); // check for n greater than size
Chris@16: #if BOOST_CB_ENABLE_DEBUG
Chris@16:         erase_begin(n, false_type());
Chris@16: #else
Chris@16:         erase_begin(n, is_scalar<value_type>());
Chris@16: #endif
Chris@16:     }
Chris@16: 
Chris@16:     //! Remove last <code>n</code> elements (with constant complexity for scalar types).
Chris@16:     /*!
Chris@16:         \pre <code>n \<= size()</code>
Chris@16:         \post The <code>n</code> elements at the end of the <code>circular_buffer</code> will be removed.
Chris@16:         \param n The number of elements to be removed.
Chris@16:         \throws <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
Chris@16:         \par Exception Safety
Chris@16:              Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything. (I.e. no throw in
Chris@16:              case of scalars.)
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates iterators pointing to the last <code>n</code> erased elements.
Chris@16:         \par Complexity
Chris@16:              Constant (in <code>n</code>) for scalar types; linear for other types.
Chris@16:         \note This method has been specially designed for types which do not require an explicit destructruction (e.g.
Chris@16:               integer, float or a pointer). For these scalar types a call to a destructor is not required which makes
Chris@16:               it possible to implement the "erase from end" operation with a constant complexity. For non-sacalar
Chris@16:               types the complexity is linear (hence the explicit destruction is needed) and the implementation is
Chris@16:               actually equivalent to
Chris@16:               <code>\link circular_buffer::erase(iterator, iterator) erase(end() - n, end())\endlink</code>.
Chris@16:         \sa <code>erase(iterator)</code>, <code>erase(iterator, iterator)</code>,
Chris@16:             <code>rerase(iterator)</code>, <code>rerase(iterator, iterator)</code>,
Chris@16:             <code>erase_begin(size_type)</code>, <code>clear()</code>
Chris@16:     */
Chris@16:     void erase_end(size_type n) {
Chris@16:         BOOST_CB_ASSERT(n <= size()); // check for n greater than size
Chris@16: #if BOOST_CB_ENABLE_DEBUG
Chris@16:         erase_end(n, false_type());
Chris@16: #else
Chris@16:         erase_end(n, is_scalar<value_type>());
Chris@16: #endif
Chris@16:     }
Chris@16: 
Chris@16:     //! Remove all stored elements from the <code>circular_buffer</code>.
Chris@16:     /*!
Chris@16:         \post <code>size() == 0</code>
Chris@16:         \throws Nothing.
Chris@16:         \par Exception Safety
Chris@16:              No-throw.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
Chris@16:              <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer</code>) for scalar types; linear for other types.
Chris@16:         \sa <code>~circular_buffer()</code>, <code>erase(iterator)</code>, <code>erase(iterator, iterator)</code>,
Chris@16:             <code>rerase(iterator)</code>, <code>rerase(iterator, iterator)</code>,
Chris@16:             <code>erase_begin(size_type)</code>, <code>erase_end(size_type)</code>
Chris@16:     */
Chris@16:     void clear() BOOST_NOEXCEPT {
Chris@16:         destroy_content();
Chris@16:         m_size = 0;
Chris@16:     }
Chris@16: 
Chris@16: private:
Chris@16: // Helper methods
Chris@16: 
Chris@16:     //! Check if the <code>index</code> is valid.
Chris@16:     void check_position(size_type index) const {
Chris@16:         if (index >= size())
Chris@16:             throw_exception(std::out_of_range("circular_buffer"));
Chris@16:     }
Chris@16: 
Chris@16:     //! Increment the pointer.
Chris@16:     template <class Pointer>
Chris@16:     void increment(Pointer& p) const {
Chris@16:         if (++p == m_end)
Chris@16:             p = m_buff;
Chris@16:     }
Chris@16: 
Chris@16:     //! Decrement the pointer.
Chris@16:     template <class Pointer>
Chris@16:     void decrement(Pointer& p) const {
Chris@16:         if (p == m_buff)
Chris@16:             p = m_end;
Chris@16:         --p;
Chris@16:     }
Chris@16: 
Chris@16:     //! Add <code>n</code> to the pointer.
Chris@16:     template <class Pointer>
Chris@16:     Pointer add(Pointer p, difference_type n) const {
Chris@16:         return p + (n < (m_end - p) ? n : n - capacity());
Chris@16:     }
Chris@16: 
Chris@16:     //! Subtract <code>n</code> from the pointer.
Chris@16:     template <class Pointer>
Chris@16:     Pointer sub(Pointer p, difference_type n) const {
Chris@16:         return p - (n > (p - m_buff) ? n - capacity() : n);
Chris@16:     }
Chris@16: 
Chris@16:     //! Map the null pointer to virtual end of circular buffer.
Chris@16:     pointer map_pointer(pointer p) const { return p == 0 ? m_last : p; }
Chris@16: 
Chris@16:     //! Allocate memory.
Chris@16:     pointer allocate(size_type n) {
Chris@16:         if (n > max_size())
Chris@16:             throw_exception(std::length_error("circular_buffer"));
Chris@16: #if BOOST_CB_ENABLE_DEBUG
Chris@101:         pointer p = (n == 0) ? 0 : m_alloc.allocate(n);
Chris@101:         cb_details::do_fill_uninitialized_memory(p, sizeof(value_type) * n);
Chris@16:         return p;
Chris@16: #else
Chris@101:         return (n == 0) ? 0 : m_alloc.allocate(n);
Chris@16: #endif
Chris@16:     }
Chris@16: 
Chris@16:     //! Deallocate memory.
Chris@16:     void deallocate(pointer p, size_type n) {
Chris@16:         if (p != 0)
Chris@16:             m_alloc.deallocate(p, n);
Chris@16:     }
Chris@16: 
Chris@16:     //! Does the pointer point to the uninitialized memory?
Chris@16:     bool is_uninitialized(const_pointer p) const BOOST_NOEXCEPT {
Chris@16:         return p >= m_last && (m_first < m_last || p < m_first);
Chris@16:     }
Chris@16: 
Chris@16:     //! Replace an element.
Chris@16:     void replace(pointer pos, param_value_type item) {
Chris@16:         *pos = item;
Chris@16: #if BOOST_CB_ENABLE_DEBUG
Chris@16:         invalidate_iterators(iterator(this, pos));
Chris@16: #endif
Chris@16:     }
Chris@16: 
Chris@16:     //! Replace an element.
Chris@16:     void replace(pointer pos, rvalue_type item) {
Chris@16:         *pos = boost::move(item);
Chris@16: #if BOOST_CB_ENABLE_DEBUG
Chris@16:         invalidate_iterators(iterator(this, pos));
Chris@16: #endif
Chris@16:     }
Chris@16: 
Chris@16:     //! Construct or replace an element.
Chris@16:     /*!
Chris@16:         <code>construct</code> has to be set to <code>true</code> if and only if
Chris@16:         <code>pos</code> points to an uninitialized memory.
Chris@16:     */
Chris@16:     void construct_or_replace(bool construct, pointer pos, param_value_type item) {
Chris@16:         if (construct)
Chris@101:             boost::container::allocator_traits<Alloc>::construct(m_alloc, boost::addressof(*pos), item);
Chris@16:         else
Chris@16:             replace(pos, item);
Chris@16:     }
Chris@16: 
Chris@16:     //! Construct or replace an element.
Chris@16:     /*!
Chris@16:         <code>construct</code> has to be set to <code>true</code> if and only if
Chris@16:         <code>pos</code> points to an uninitialized memory.
Chris@16:     */
Chris@16:     void construct_or_replace(bool construct, pointer pos, rvalue_type item) {
Chris@16:         if (construct)
Chris@101:             boost::container::allocator_traits<Alloc>::construct(m_alloc, boost::addressof(*pos), boost::move(item));
Chris@16:         else
Chris@16:             replace(pos, boost::move(item));
Chris@16:     }
Chris@16: 
Chris@16:     //! Destroy an item.
Chris@16:     void destroy_item(pointer p) {
Chris@101:         boost::container::allocator_traits<Alloc>::destroy(m_alloc, boost::addressof(*p));
Chris@16: #if BOOST_CB_ENABLE_DEBUG
Chris@16:         invalidate_iterators(iterator(this, p));
Chris@101:         cb_details::do_fill_uninitialized_memory(p, sizeof(value_type));
Chris@16: #endif
Chris@16:     }
Chris@16: 
Chris@16:     //! Destroy an item only if it has been constructed.
Chris@16:     void destroy_if_constructed(pointer pos) {
Chris@16:         if (is_uninitialized(pos))
Chris@16:             destroy_item(pos);
Chris@16:     }
Chris@16: 
Chris@16:     //! Destroy the whole content of the circular buffer.
Chris@16:     void destroy_content() {
Chris@16: #if BOOST_CB_ENABLE_DEBUG
Chris@16:         destroy_content(false_type());
Chris@16: #else
Chris@16:         destroy_content(is_scalar<value_type>());
Chris@16: #endif
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized destroy_content method.
Chris@16:     void destroy_content(const true_type&) {
Chris@16:         m_first = add(m_first, size());
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized destroy_content method.
Chris@16:     void destroy_content(const false_type&) {
Chris@16:         for (size_type ii = 0; ii < size(); ++ii, increment(m_first))
Chris@16:             destroy_item(m_first);
Chris@16:     }
Chris@16: 
Chris@16:     //! Destroy content and free allocated memory.
Chris@16:     void destroy() BOOST_NOEXCEPT {
Chris@16:         destroy_content();
Chris@16:         deallocate(m_buff, capacity());
Chris@16: #if BOOST_CB_ENABLE_DEBUG
Chris@16:         m_buff = 0;
Chris@16:         m_first = 0;
Chris@16:         m_last = 0;
Chris@16:         m_end = 0;
Chris@16: #endif
Chris@16:     }
Chris@16: 
Chris@16:     //! Initialize the internal buffer.
Chris@16:     void initialize_buffer(capacity_type buffer_capacity) {
Chris@16:         m_buff = allocate(buffer_capacity);
Chris@16:         m_end = m_buff + buffer_capacity;
Chris@16:     }
Chris@16: 
Chris@16:     //! Initialize the internal buffer.
Chris@16:     void initialize_buffer(capacity_type buffer_capacity, param_value_type item) {
Chris@16:         initialize_buffer(buffer_capacity);
Chris@16:         BOOST_TRY {
Chris@16:             cb_details::uninitialized_fill_n_with_alloc(m_buff, size(), item, m_alloc);
Chris@16:         } BOOST_CATCH(...) {
Chris@16:             deallocate(m_buff, size());
Chris@16:             BOOST_RETHROW
Chris@16:         }
Chris@16:         BOOST_CATCH_END
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized initialize method.
Chris@16:     template <class IntegralType>
Chris@16:     void initialize(IntegralType n, IntegralType item, const true_type&) {
Chris@16:         m_size = static_cast<size_type>(n);
Chris@16:         initialize_buffer(size(), item);
Chris@16:         m_first = m_last = m_buff;
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized initialize method.
Chris@16:     template <class Iterator>
Chris@16:     void initialize(Iterator first, Iterator last, const false_type&) {
Chris@16:         BOOST_CB_IS_CONVERTIBLE(Iterator, value_type); // check for invalid iterator type
Chris@16: #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x581))
Chris@101:         initialize(first, last, iterator_category<Iterator>::type());
Chris@16: #else
Chris@101:         initialize(first, last, BOOST_DEDUCED_TYPENAME iterator_category<Iterator>::type());
Chris@16: #endif
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized initialize method.
Chris@16:     template <class InputIterator>
Chris@16:     void initialize(InputIterator first, InputIterator last, const std::input_iterator_tag&) {
Chris@16:         BOOST_CB_ASSERT_TEMPLATED_ITERATOR_CONSTRUCTORS // check if the STL provides templated iterator constructors
Chris@16:                                                         // for containers
Chris@16:         std::deque<value_type, allocator_type> tmp(first, last, m_alloc);
Chris@16:         size_type distance = tmp.size();
Chris@16:         initialize(distance, boost::make_move_iterator(tmp.begin()), boost::make_move_iterator(tmp.end()), distance);
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized initialize method.
Chris@16:     template <class ForwardIterator>
Chris@16:     void initialize(ForwardIterator first, ForwardIterator last, const std::forward_iterator_tag&) {
Chris@16:         BOOST_CB_ASSERT(std::distance(first, last) >= 0); // check for wrong range
Chris@16:         size_type distance = std::distance(first, last);
Chris@16:         initialize(distance, first, last, distance);
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized initialize method.
Chris@16:     template <class IntegralType>
Chris@16:     void initialize(capacity_type buffer_capacity, IntegralType n, IntegralType item, const true_type&) {
Chris@16:         BOOST_CB_ASSERT(buffer_capacity >= static_cast<size_type>(n)); // check for capacity lower than n
Chris@16:         m_size = static_cast<size_type>(n);
Chris@16:         initialize_buffer(buffer_capacity, item);
Chris@16:         m_first = m_buff;
Chris@16:         m_last = buffer_capacity == size() ? m_buff : m_buff + size();
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized initialize method.
Chris@16:     template <class Iterator>
Chris@16:     void initialize(capacity_type buffer_capacity, Iterator first, Iterator last, const false_type&) {
Chris@16:         BOOST_CB_IS_CONVERTIBLE(Iterator, value_type); // check for invalid iterator type
Chris@16: #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x581))
Chris@101:         initialize(buffer_capacity, first, last, iterator_category<Iterator>::type());
Chris@16: #else
Chris@101:         initialize(buffer_capacity, first, last, BOOST_DEDUCED_TYPENAME iterator_category<Iterator>::type());
Chris@16: #endif
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized initialize method.
Chris@16:     template <class InputIterator>
Chris@16:     void initialize(capacity_type buffer_capacity,
Chris@16:         InputIterator first,
Chris@16:         InputIterator last,
Chris@16:         const std::input_iterator_tag&) {
Chris@16:         initialize_buffer(buffer_capacity);
Chris@16:         m_first = m_last = m_buff;
Chris@16:         m_size = 0;
Chris@16:         if (buffer_capacity == 0)
Chris@16:             return;
Chris@16:         while (first != last && !full()) {
Chris@101:             boost::container::allocator_traits<Alloc>::construct(m_alloc, boost::addressof(*m_last), *first++);
Chris@16:             increment(m_last);
Chris@16:             ++m_size;
Chris@16:         }
Chris@16:         while (first != last) {
Chris@16:             replace(m_last, *first++);
Chris@16:             increment(m_last);
Chris@16:             m_first = m_last;
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized initialize method.
Chris@16:     template <class ForwardIterator>
Chris@16:     void initialize(capacity_type buffer_capacity,
Chris@16:         ForwardIterator first,
Chris@16:         ForwardIterator last,
Chris@16:         const std::forward_iterator_tag&) {
Chris@16:         BOOST_CB_ASSERT(std::distance(first, last) >= 0); // check for wrong range
Chris@16:         initialize(buffer_capacity, first, last, std::distance(first, last));
Chris@16:     }
Chris@16: 
Chris@16:     //! Initialize the circular buffer.
Chris@16:     template <class ForwardIterator>
Chris@16:     void initialize(capacity_type buffer_capacity,
Chris@16:         ForwardIterator first,
Chris@16:         ForwardIterator last,
Chris@16:         size_type distance) {
Chris@16:         initialize_buffer(buffer_capacity);
Chris@16:         m_first = m_buff;
Chris@16:         if (distance > buffer_capacity) {
Chris@16:             std::advance(first, distance - buffer_capacity);
Chris@16:             m_size = buffer_capacity;
Chris@16:         } else {
Chris@16:             m_size = distance;
Chris@16:         }
Chris@16:         BOOST_TRY {
Chris@101:             m_last = cb_details::uninitialized_copy(first, last, m_buff, m_alloc);
Chris@16:         } BOOST_CATCH(...) {
Chris@16:             deallocate(m_buff, buffer_capacity);
Chris@16:             BOOST_RETHROW
Chris@16:         }
Chris@16:         BOOST_CATCH_END
Chris@16:         if (m_last == m_end)
Chris@16:             m_last = m_buff;
Chris@16:     }
Chris@16: 
Chris@16:     //! Reset the circular buffer.
Chris@16:     void reset(pointer buff, pointer last, capacity_type new_capacity) {
Chris@16:         destroy();
Chris@16:         m_size = last - buff;
Chris@16:         m_first = m_buff = buff;
Chris@16:         m_end = m_buff + new_capacity;
Chris@16:         m_last = last == m_end ? m_buff : last;
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized method for swapping the allocator.
Chris@16:     void swap_allocator(circular_buffer<T, Alloc>&, const true_type&) {
Chris@16:         // Swap is not needed because allocators have no state.
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized method for swapping the allocator.
Chris@16:     void swap_allocator(circular_buffer<T, Alloc>& cb, const false_type&) {
Chris@16:         std::swap(m_alloc, cb.m_alloc);
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized assign method.
Chris@16:     template <class IntegralType>
Chris@16:     void assign(IntegralType n, IntegralType item, const true_type&) {
Chris@16:         assign(static_cast<size_type>(n), static_cast<value_type>(item));
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized assign method.
Chris@16:     template <class Iterator>
Chris@16:     void assign(Iterator first, Iterator last, const false_type&) {
Chris@16:         BOOST_CB_IS_CONVERTIBLE(Iterator, value_type); // check for invalid iterator type
Chris@16: #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x581))
Chris@101:         assign(first, last, iterator_category<Iterator>::type());
Chris@16: #else
Chris@101:         assign(first, last, BOOST_DEDUCED_TYPENAME iterator_category<Iterator>::type());
Chris@16: #endif
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized assign method.
Chris@16:     template <class InputIterator>
Chris@16:     void assign(InputIterator first, InputIterator last, const std::input_iterator_tag&) {
Chris@16:         BOOST_CB_ASSERT_TEMPLATED_ITERATOR_CONSTRUCTORS // check if the STL provides templated iterator constructors
Chris@16:                                                         // for containers
Chris@16:         std::deque<value_type, allocator_type> tmp(first, last, m_alloc);
Chris@16:         size_type distance = tmp.size();
Chris@16:         assign_n(distance, distance,
Chris@101:             cb_details::make_assign_range
Chris@101:                 (boost::make_move_iterator(tmp.begin()), boost::make_move_iterator(tmp.end()), m_alloc));
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized assign method.
Chris@16:     template <class ForwardIterator>
Chris@16:     void assign(ForwardIterator first, ForwardIterator last, const std::forward_iterator_tag&) {
Chris@16:         BOOST_CB_ASSERT(std::distance(first, last) >= 0); // check for wrong range
Chris@16:         size_type distance = std::distance(first, last);
Chris@101:         assign_n(distance, distance, cb_details::make_assign_range(first, last, m_alloc));
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized assign method.
Chris@16:     template <class IntegralType>
Chris@16:     void assign(capacity_type new_capacity, IntegralType n, IntegralType item, const true_type&) {
Chris@16:         assign(new_capacity, static_cast<size_type>(n), static_cast<value_type>(item));
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized assign method.
Chris@16:     template <class Iterator>
Chris@16:     void assign(capacity_type new_capacity, Iterator first, Iterator last, const false_type&) {
Chris@16:         BOOST_CB_IS_CONVERTIBLE(Iterator, value_type); // check for invalid iterator type
Chris@16: #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x581))
Chris@101:         assign(new_capacity, first, last, iterator_category<Iterator>::type());
Chris@16: #else
Chris@101:         assign(new_capacity, first, last, BOOST_DEDUCED_TYPENAME iterator_category<Iterator>::type());
Chris@16: #endif
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized assign method.
Chris@16:     template <class InputIterator>
Chris@16:     void assign(capacity_type new_capacity, InputIterator first, InputIterator last, const std::input_iterator_tag&) {
Chris@16:         if (new_capacity == capacity()) {
Chris@16:             clear();
Chris@16:             insert(begin(), first, last);
Chris@16:         } else {
Chris@16:             circular_buffer<value_type, allocator_type> tmp(new_capacity, first, last, m_alloc);
Chris@16:             tmp.swap(*this);
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized assign method.
Chris@16:     template <class ForwardIterator>
Chris@16:     void assign(capacity_type new_capacity, ForwardIterator first, ForwardIterator last,
Chris@16:         const std::forward_iterator_tag&) {
Chris@16:         BOOST_CB_ASSERT(std::distance(first, last) >= 0); // check for wrong range
Chris@16:         size_type distance = std::distance(first, last);
Chris@16:         if (distance > new_capacity) {
Chris@16:             std::advance(first, distance - new_capacity);
Chris@16:             distance = new_capacity;
Chris@16:         }
Chris@16:         assign_n(new_capacity, distance,
Chris@101:             cb_details::make_assign_range(first, last, m_alloc));
Chris@16:     }
Chris@16: 
Chris@16:     //! Helper assign method.
Chris@16:     template <class Functor>
Chris@16:     void assign_n(capacity_type new_capacity, size_type n, const Functor& fnc) {
Chris@16:         if (new_capacity == capacity()) {
Chris@16:             destroy_content();
Chris@16:             BOOST_TRY {
Chris@16:                 fnc(m_buff);
Chris@16:             } BOOST_CATCH(...) {
Chris@16:                 m_size = 0;
Chris@16:                 BOOST_RETHROW
Chris@16:             }
Chris@16:             BOOST_CATCH_END
Chris@16:         } else {
Chris@16:             pointer buff = allocate(new_capacity);
Chris@16:             BOOST_TRY {
Chris@16:                 fnc(buff);
Chris@16:             } BOOST_CATCH(...) {
Chris@16:                 deallocate(buff, new_capacity);
Chris@16:                 BOOST_RETHROW
Chris@16:             }
Chris@16:             BOOST_CATCH_END
Chris@16:             destroy();
Chris@16:             m_buff = buff;
Chris@16:             m_end = m_buff + new_capacity;
Chris@16:         }
Chris@16:         m_size = n;
Chris@16:         m_first = m_buff;
Chris@16:         m_last = add(m_buff, size());
Chris@16:     }
Chris@16: 
Chris@16:     //! Helper insert method.
Chris@16:     template <class ValT>
Chris@16:     iterator insert_item(const iterator& pos, ValT item) {
Chris@16:         pointer p = pos.m_it;
Chris@16:         if (p == 0) {
Chris@16:             construct_or_replace(!full(), m_last, static_cast<ValT>(item));
Chris@16:             p = m_last;
Chris@16:         } else {
Chris@16:             pointer src = m_last;
Chris@16:             pointer dest = m_last;
Chris@16:             bool construct = !full();
Chris@16:             BOOST_TRY {
Chris@16:                 while (src != p) {
Chris@16:                     decrement(src);
Chris@101:                     construct_or_replace(construct, dest, boost::move_if_noexcept(*src));
Chris@16:                     decrement(dest);
Chris@16:                     construct = false;
Chris@16:                 }
Chris@16:                 replace(p, static_cast<ValT>(item));
Chris@16:             } BOOST_CATCH(...) {
Chris@16:                 if (!construct && !full()) {
Chris@16:                     increment(m_last);
Chris@16:                     ++m_size;
Chris@16:                 }
Chris@16:                 BOOST_RETHROW
Chris@16:             }
Chris@16:             BOOST_CATCH_END
Chris@16:         }
Chris@16:         increment(m_last);
Chris@16:         if (full())
Chris@16:             m_first = m_last;
Chris@16:         else
Chris@16:             ++m_size;
Chris@16:         return iterator(this, p);
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized insert method.
Chris@16:     template <class IntegralType>
Chris@16:     void insert(const iterator& pos, IntegralType n, IntegralType item, const true_type&) {
Chris@16:         insert(pos, static_cast<size_type>(n), static_cast<value_type>(item));
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized insert method.
Chris@16:     template <class Iterator>
Chris@16:     void insert(const iterator& pos, Iterator first, Iterator last, const false_type&) {
Chris@16:         BOOST_CB_IS_CONVERTIBLE(Iterator, value_type); // check for invalid iterator type
Chris@16: #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x581))
Chris@101:         insert(pos, first, last, iterator_category<Iterator>::type());
Chris@16: #else
Chris@101:         insert(pos, first, last, BOOST_DEDUCED_TYPENAME iterator_category<Iterator>::type());
Chris@16: #endif
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized insert method.
Chris@16:     template <class InputIterator>
Chris@16:     void insert(iterator pos, InputIterator first, InputIterator last, const std::input_iterator_tag&) {
Chris@16:         if (!full() || pos != begin()) {
Chris@16:             for (;first != last; ++pos)
Chris@16:                 pos = insert(pos, *first++);
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized insert method.
Chris@16:     template <class ForwardIterator>
Chris@16:     void insert(const iterator& pos, ForwardIterator first, ForwardIterator last, const std::forward_iterator_tag&) {
Chris@16:         BOOST_CB_ASSERT(std::distance(first, last) >= 0); // check for wrong range
Chris@16:         size_type n = std::distance(first, last);
Chris@16:         if (n == 0)
Chris@16:             return;
Chris@16:         size_type copy = capacity() - (end() - pos);
Chris@16:         if (copy == 0)
Chris@16:             return;
Chris@16:         if (n > copy) {
Chris@16:             std::advance(first, n - copy);
Chris@16:             n = copy;
Chris@16:         }
Chris@16:         insert_n(pos, n, cb_details::iterator_wrapper<ForwardIterator>(first));
Chris@16:     }
Chris@16: 
Chris@16:     //! Helper insert method.
Chris@16:     template <class Wrapper>
Chris@16:     void insert_n(const iterator& pos, size_type n, const Wrapper& wrapper) {
Chris@16:         size_type construct = reserve();
Chris@16:         if (construct > n)
Chris@16:             construct = n;
Chris@16:         if (pos.m_it == 0) {
Chris@16:             size_type ii = 0;
Chris@16:             pointer p = m_last;
Chris@16:             BOOST_TRY {
Chris@16:                 for (; ii < construct; ++ii, increment(p))
Chris@101:                     boost::container::allocator_traits<Alloc>::construct(m_alloc, boost::addressof(*p), *wrapper());
Chris@16:                 for (;ii < n; ++ii, increment(p))
Chris@16:                     replace(p, *wrapper());
Chris@16:             } BOOST_CATCH(...) {
Chris@16:                 size_type constructed = (std::min)(ii, construct);
Chris@16:                 m_last = add(m_last, constructed);
Chris@16:                 m_size += constructed;
Chris@16:                 BOOST_RETHROW
Chris@16:             }
Chris@16:             BOOST_CATCH_END
Chris@16:         } else {
Chris@16:             pointer src = m_last;
Chris@16:             pointer dest = add(m_last, n - 1);
Chris@16:             pointer p = pos.m_it;
Chris@16:             size_type ii = 0;
Chris@16:             BOOST_TRY {
Chris@16:                 while (src != pos.m_it) {
Chris@16:                     decrement(src);
Chris@16:                     construct_or_replace(is_uninitialized(dest), dest, *src);
Chris@16:                     decrement(dest);
Chris@16:                 }
Chris@16:                 for (; ii < n; ++ii, increment(p))
Chris@16:                     construct_or_replace(is_uninitialized(p), p, *wrapper());
Chris@16:             } BOOST_CATCH(...) {
Chris@16:                 for (p = add(m_last, n - 1); p != dest; decrement(p))
Chris@16:                     destroy_if_constructed(p);
Chris@16:                 for (n = 0, p = pos.m_it; n < ii; ++n, increment(p))
Chris@16:                     destroy_if_constructed(p);
Chris@16:                 BOOST_RETHROW
Chris@16:             }
Chris@16:             BOOST_CATCH_END
Chris@16:         }
Chris@16:         m_last = add(m_last, n);
Chris@16:         m_first = add(m_first, n - construct);
Chris@16:         m_size += construct;
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized rinsert method.
Chris@16:     template <class IntegralType>
Chris@16:     void rinsert(const iterator& pos, IntegralType n, IntegralType item, const true_type&) {
Chris@16:         rinsert(pos, static_cast<size_type>(n), static_cast<value_type>(item));
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized rinsert method.
Chris@16:     template <class Iterator>
Chris@16:     void rinsert(const iterator& pos, Iterator first, Iterator last, const false_type&) {
Chris@16:         BOOST_CB_IS_CONVERTIBLE(Iterator, value_type); // check for invalid iterator type
Chris@16: #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x581))
Chris@101:         rinsert(pos, first, last, iterator_category<Iterator>::type());
Chris@16: #else
Chris@101:         rinsert(pos, first, last, BOOST_DEDUCED_TYPENAME iterator_category<Iterator>::type());
Chris@16: #endif
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized insert method.
Chris@16:     template <class InputIterator>
Chris@16:     void rinsert(iterator pos, InputIterator first, InputIterator last, const std::input_iterator_tag&) {
Chris@16:         if (!full() || pos.m_it != 0) {
Chris@16:             for (;first != last; ++pos) {
Chris@16:                 pos = rinsert(pos, *first++);
Chris@16:                 if (pos.m_it == 0)
Chris@16:                     break;
Chris@16:             }
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized rinsert method.
Chris@16:     template <class ForwardIterator>
Chris@16:     void rinsert(const iterator& pos, ForwardIterator first, ForwardIterator last, const std::forward_iterator_tag&) {
Chris@16:         BOOST_CB_ASSERT(std::distance(first, last) >= 0); // check for wrong range
Chris@16:         rinsert_n(pos, std::distance(first, last), cb_details::iterator_wrapper<ForwardIterator>(first));
Chris@16:     }
Chris@16: 
Chris@16:     //! Helper rinsert method.
Chris@16:     template <class Wrapper>
Chris@16:     void rinsert_n(const iterator& pos, size_type n, const Wrapper& wrapper) {
Chris@16:         if (n == 0)
Chris@16:             return;
Chris@16:         iterator b = begin();
Chris@16:         size_type copy = capacity() - (pos - b);
Chris@16:         if (copy == 0)
Chris@16:             return;
Chris@16:         if (n > copy)
Chris@16:             n = copy;
Chris@16:         size_type construct = reserve();
Chris@16:         if (construct > n)
Chris@16:             construct = n;
Chris@16:         if (pos == b) {
Chris@16:             pointer p = sub(m_first, n);
Chris@16:             size_type ii = n;
Chris@16:             BOOST_TRY {
Chris@16:                 for (;ii > construct; --ii, increment(p))
Chris@16:                     replace(p, *wrapper());
Chris@16:                 for (; ii > 0; --ii, increment(p))
Chris@101:                     boost::container::allocator_traits<Alloc>::construct(m_alloc, boost::addressof(*p), *wrapper());
Chris@16:             } BOOST_CATCH(...) {
Chris@16:                 size_type constructed = ii < construct ? construct - ii : 0;
Chris@16:                 m_last = add(m_last, constructed);
Chris@16:                 m_size += constructed;
Chris@16:                 BOOST_RETHROW
Chris@16:             }
Chris@16:             BOOST_CATCH_END
Chris@16:         } else {
Chris@16:             pointer src = m_first;
Chris@16:             pointer dest = sub(m_first, n);
Chris@16:             pointer p = map_pointer(pos.m_it);
Chris@16:             BOOST_TRY {
Chris@16:                 while (src != p) {
Chris@16:                     construct_or_replace(is_uninitialized(dest), dest, *src);
Chris@16:                     increment(src);
Chris@16:                     increment(dest);
Chris@16:                 }
Chris@16:                 for (size_type ii = 0; ii < n; ++ii, increment(dest))
Chris@16:                     construct_or_replace(is_uninitialized(dest), dest, *wrapper());
Chris@16:             } BOOST_CATCH(...) {
Chris@16:                 for (src = sub(m_first, n); src != dest; increment(src))
Chris@16:                     destroy_if_constructed(src);
Chris@16:                 BOOST_RETHROW
Chris@16:             }
Chris@16:             BOOST_CATCH_END
Chris@16:         }
Chris@16:         m_first = sub(m_first, n);
Chris@16:         m_last = sub(m_last, n - construct);
Chris@16:         m_size += construct;
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized erase_begin method.
Chris@16:     void erase_begin(size_type n, const true_type&) {
Chris@16:         m_first = add(m_first, n);
Chris@16:         m_size -= n;
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized erase_begin method.
Chris@16:     void erase_begin(size_type n, const false_type&) {
Chris@16:         iterator b = begin();
Chris@16:         rerase(b, b + n);
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized erase_end method.
Chris@16:     void erase_end(size_type n, const true_type&) {
Chris@16:         m_last = sub(m_last, n);
Chris@16:         m_size -= n;
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized erase_end method.
Chris@16:     void erase_end(size_type n, const false_type&) {
Chris@16:         iterator e = end();
Chris@16:         erase(e - n, e);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: // Non-member functions
Chris@16: 
Chris@16: //! Compare two <code>circular_buffer</code>s element-by-element to determine if they are equal.
Chris@16: /*!
Chris@16:     \param lhs The <code>circular_buffer</code> to compare.
Chris@16:     \param rhs The <code>circular_buffer</code> to compare.
Chris@16:     \return <code>lhs.\link circular_buffer::size() size()\endlink == rhs.\link circular_buffer::size() size()\endlink
Chris@16:             && <a href="http://www.sgi.com/tech/stl/equal.html">std::equal</a>(lhs.\link circular_buffer::begin()
Chris@16:             begin()\endlink, lhs.\link circular_buffer::end() end()\endlink,
Chris@16:             rhs.\link circular_buffer::begin() begin()\endlink)</code>
Chris@16:     \throws Nothing.
Chris@16:     \par Complexity
Chris@16:          Linear (in the size of the <code>circular_buffer</code>s).
Chris@16:     \par Iterator Invalidation
Chris@16:          Does not invalidate any iterators.
Chris@16: */
Chris@16: template <class T, class Alloc>
Chris@16: inline bool operator == (const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs) {
Chris@16:     return lhs.size() == rhs.size() && std::equal(lhs.begin(), lhs.end(), rhs.begin());
Chris@16: }
Chris@16: 
Chris@16: /*!
Chris@16:     \brief Compare two <code>circular_buffer</code>s element-by-element to determine if the left one is lesser than the
Chris@16:            right one.
Chris@16:     \param lhs The <code>circular_buffer</code> to compare.
Chris@16:     \param rhs The <code>circular_buffer</code> to compare.
Chris@16:     \return <code><a href="http://www.sgi.com/tech/stl/lexicographical_compare.html">
Chris@16:             std::lexicographical_compare</a>(lhs.\link circular_buffer::begin() begin()\endlink,
Chris@16:             lhs.\link circular_buffer::end() end()\endlink, rhs.\link circular_buffer::begin() begin()\endlink,
Chris@16:             rhs.\link circular_buffer::end() end()\endlink)</code>
Chris@16:     \throws Nothing.
Chris@16:     \par Complexity
Chris@16:          Linear (in the size of the <code>circular_buffer</code>s).
Chris@16:     \par Iterator Invalidation
Chris@16:          Does not invalidate any iterators.
Chris@16: */
Chris@16: template <class T, class Alloc>
Chris@16: inline bool operator < (const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs) {
Chris@16:     return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
Chris@16: }
Chris@16: 
Chris@16: #if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING) || defined(BOOST_MSVC)
Chris@16: 
Chris@16: //! Compare two <code>circular_buffer</code>s element-by-element to determine if they are non-equal.
Chris@16: /*!
Chris@16:     \param lhs The <code>circular_buffer</code> to compare.
Chris@16:     \param rhs The <code>circular_buffer</code> to compare.
Chris@16:     \return <code>!(lhs == rhs)</code>
Chris@16:     \throws Nothing.
Chris@16:     \par Complexity
Chris@16:          Linear (in the size of the <code>circular_buffer</code>s).
Chris@16:     \par Iterator Invalidation
Chris@16:          Does not invalidate any iterators.
Chris@16:     \sa <code>operator==(const circular_buffer<T,Alloc>&, const circular_buffer<T,Alloc>&)</code>
Chris@16: */
Chris@16: template <class T, class Alloc>
Chris@16: inline bool operator != (const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs) {
Chris@16:     return !(lhs == rhs);
Chris@16: }
Chris@16: 
Chris@16: /*!
Chris@16:     \brief Compare two <code>circular_buffer</code>s element-by-element to determine if the left one is greater than
Chris@16:            the right one.
Chris@16:     \param lhs The <code>circular_buffer</code> to compare.
Chris@16:     \param rhs The <code>circular_buffer</code> to compare.
Chris@16:     \return <code>rhs \< lhs</code>
Chris@16:     \throws Nothing.
Chris@16:     \par Complexity
Chris@16:          Linear (in the size of the <code>circular_buffer</code>s).
Chris@16:     \par Iterator Invalidation
Chris@16:          Does not invalidate any iterators.
Chris@16:     \sa <code>operator<(const circular_buffer<T,Alloc>&, const circular_buffer<T,Alloc>&)</code>
Chris@16: */
Chris@16: template <class T, class Alloc>
Chris@16: inline bool operator > (const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs) {
Chris@16:     return rhs < lhs;
Chris@16: }
Chris@16: 
Chris@16: /*!
Chris@16:     \brief Compare two <code>circular_buffer</code>s element-by-element to determine if the left one is lesser or equal
Chris@16:            to the right one.
Chris@16:     \param lhs The <code>circular_buffer</code> to compare.
Chris@16:     \param rhs The <code>circular_buffer</code> to compare.
Chris@16:     \return <code>!(rhs \< lhs)</code>
Chris@16:     \throws Nothing.
Chris@16:     \par Complexity
Chris@16:          Linear (in the size of the <code>circular_buffer</code>s).
Chris@16:     \par Iterator Invalidation
Chris@16:          Does not invalidate any iterators.
Chris@16:     \sa <code>operator<(const circular_buffer<T,Alloc>&, const circular_buffer<T,Alloc>&)</code>
Chris@16: */
Chris@16: template <class T, class Alloc>
Chris@16: inline bool operator <= (const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs) {
Chris@16:     return !(rhs < lhs);
Chris@16: }
Chris@16: 
Chris@16: /*!
Chris@16:     \brief Compare two <code>circular_buffer</code>s element-by-element to determine if the left one is greater or
Chris@16:            equal to the right one.
Chris@16:     \param lhs The <code>circular_buffer</code> to compare.
Chris@16:     \param rhs The <code>circular_buffer</code> to compare.
Chris@16:     \return <code>!(lhs < rhs)</code>
Chris@16:     \throws Nothing.
Chris@16:     \par Complexity
Chris@16:          Linear (in the size of the <code>circular_buffer</code>s).
Chris@16:     \par Iterator Invalidation
Chris@16:          Does not invalidate any iterators.
Chris@16:     \sa <code>operator<(const circular_buffer<T,Alloc>&, const circular_buffer<T,Alloc>&)</code>
Chris@16: */
Chris@16: template <class T, class Alloc>
Chris@16: inline bool operator >= (const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs) {
Chris@16:     return !(lhs < rhs);
Chris@16: }
Chris@16: 
Chris@16: //! Swap the contents of two <code>circular_buffer</code>s.
Chris@16: /*!
Chris@16:     \post <code>lhs</code> contains elements of <code>rhs</code> and vice versa.
Chris@16:     \param lhs The <code>circular_buffer</code> whose content will be swapped with <code>rhs</code>.
Chris@16:     \param rhs The <code>circular_buffer</code> whose content will be swapped with <code>lhs</code>.
Chris@16:     \throws Nothing.
Chris@16:     \par Complexity
Chris@16:          Constant (in the size of the <code>circular_buffer</code>s).
Chris@16:     \par Iterator Invalidation
Chris@16:          Invalidates all iterators of both <code>circular_buffer</code>s. (On the other hand the iterators still
Chris@16:          point to the same elements but within another container. If you want to rely on this feature you have to
Chris@16:          turn the <a href="#debug">Debug Support</a> off otherwise an assertion will report an error if such
Chris@16:          invalidated iterator is used.)
Chris@16:     \sa <code>\link circular_buffer::swap(circular_buffer<T, Alloc>&) swap(circular_buffer<T, Alloc>&)\endlink</code>
Chris@16: */
Chris@16: template <class T, class Alloc>
Chris@16: inline void swap(circular_buffer<T, Alloc>& lhs, circular_buffer<T, Alloc>& rhs) BOOST_NOEXCEPT {
Chris@16:     lhs.swap(rhs);
Chris@16: }
Chris@16: 
Chris@16: #endif // #if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING) || defined(BOOST_MSVC)
Chris@16: 
Chris@16: } // namespace boost
Chris@16: 
Chris@16: #endif // #if !defined(BOOST_CIRCULAR_BUFFER_BASE_HPP)