// Implementation of the base circular buffer.

// Copyright (c) 2003-2007 Jan Gaspar

// Use, modification, and distribution is subject to the Boost Software
// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

#if !defined(BOOST_CIRCULAR_BUFFER_BASE_HPP)
#define BOOST_CIRCULAR_BUFFER_BASE_HPP

#if defined(_MSC_VER) && _MSC_VER >= 1200
    #pragma once
#endif

#include <boost/call_traits.hpp>
#include <boost/concept_check.hpp>
#include <boost/limits.hpp>
#include <boost/iterator/reverse_iterator.hpp>
#include <boost/iterator/iterator_traits.hpp>
#include <boost/type_traits/is_stateless.hpp>
#include <boost/type_traits/is_integral.hpp>
#include <algorithm>
#include <utility>
#include <deque>
#if !defined(BOOST_NO_EXCEPTIONS)
    #include <stdexcept>
#endif
#if BOOST_CB_ENABLE_DEBUG
    #include <cstring>
#endif
#if BOOST_WORKAROUND(__MWERKS__, BOOST_TESTED_AT(0x3205))
    #include <stddef.h>
#endif

namespace boost {

/*!
    \class circular_buffer
    \brief Circular buffer - a STL compliant container.
    \param T The type of the elements stored in the <code>circular_buffer</code>.
    \par Type Requirements T
         The <code>T</code> has to be <a href="http://www.sgi.com/tech/stl/Assignable.html">
         SGIAssignable</a> (SGI STL defined combination of <a href="../../utility/Assignable.html">
         Assignable</a> and <a href="../../utility/CopyConstructible.html">CopyConstructible</a>).
         Moreover <code>T</code> has to be <a href="http://www.sgi.com/tech/stl/DefaultConstructible.html">
         DefaultConstructible</a> if supplied as a default parameter when invoking some of the
         <code>circular_buffer</code>'s methods e.g.
         <code>insert(iterator pos, const value_type& item = %value_type())</code>. And
         <a href="http://www.sgi.com/tech/stl/EqualityComparable.html">EqualityComparable</a> and/or
         <a href="../../utility/LessThanComparable.html">LessThanComparable</a> if the <code>circular_buffer</code>
         will be compared with another container.
    \param Alloc The allocator type used for all internal memory management.
    \par Type Requirements Alloc
         The <code>Alloc</code> has to meet the allocator requirements imposed by STL.
    \par Default Alloc
         std::allocator<T>

    For detailed documentation of the circular_buffer visit:
    http://www.boost.org/libs/circular_buffer/doc/circular_buffer.html
*/
template <class T, class Alloc>
class circular_buffer
/*! \cond */
#if BOOST_CB_ENABLE_DEBUG
: public cb_details::debug_iterator_registry
#endif
/*! \endcond */
{

// Requirements
    BOOST_CLASS_REQUIRE(T, boost, SGIAssignableConcept);

public:
// Basic types

    //! The type of elements stored in the <code>circular_buffer</code>.
    typedef typename Alloc::value_type value_type;

    //! A pointer to an element.
    typedef typename Alloc::pointer pointer;

    //! A const pointer to the element.
    typedef typename Alloc::const_pointer const_pointer;

    //! A reference to an element.
    typedef typename Alloc::reference reference;

    //! A const reference to an element.
    typedef typename Alloc::const_reference const_reference;

    //! The distance type.
    /*!
        (A signed integral type used to represent the distance between two iterators.)
    */
    typedef typename Alloc::difference_type difference_type;

    //! The size type.
    /*!
        (An unsigned integral type that can represent any non-negative value of the container's distance type.)
    */
    typedef typename Alloc::size_type size_type;

    //! The type of an allocator used in the <code>circular_buffer</code>.
    typedef Alloc allocator_type;

// Iterators

    //! A const (random access) iterator used to iterate through the <code>circular_buffer</code>.
    typedef cb_details::iterator< circular_buffer<T, Alloc>, cb_details::const_traits<Alloc> > const_iterator;

    //! A (random access) iterator used to iterate through the <code>circular_buffer</code>.
    typedef cb_details::iterator< circular_buffer<T, Alloc>, cb_details::nonconst_traits<Alloc> > iterator;

    //! A const iterator used to iterate backwards through a <code>circular_buffer</code>.
    typedef boost::reverse_iterator<const_iterator> const_reverse_iterator;

    //! An iterator used to iterate backwards through a <code>circular_buffer</code>.
    typedef boost::reverse_iterator<iterator> reverse_iterator;

// Container specific types

    //! An array range.
    /*!
        (A typedef for the <a href="http://www.sgi.com/tech/stl/pair.html"><code>std::pair</code></a> where
        its first element is a pointer to a beginning of an array and its second element represents
        a size of the array.)
    */
    typedef std::pair<pointer, size_type> array_range;

    //! A range of a const array.
    /*!
        (A typedef for the <a href="http://www.sgi.com/tech/stl/pair.html"><code>std::pair</code></a> where
        its first element is a pointer to a beginning of a const array and its second element represents
        a size of the const array.)
    */
    typedef std::pair<const_pointer, size_type> const_array_range;

    //! The capacity type.
    /*!
        (Same as <code>size_type</code> - defined for consistency with the
        <a href="space_optimized.html"><code>circular_buffer_space_optimized</code></a>.)
    */
    typedef size_type capacity_type;

// Helper types

    // A type representing the "best" way to pass the value_type to a method.
    typedef typename call_traits<value_type>::param_type param_value_type;

    // A type representing the "best" way to return the value_type from a const method.
    typedef typename call_traits<value_type>::param_type return_value_type;

private:
// Member variables

    //! The internal buffer used for storing elements in the circular buffer.
    pointer m_buff;

    //! The internal buffer's end (end of the storage space).
    pointer m_end;

    //! The virtual beginning of the circular buffer.
    pointer m_first;

    //! The virtual end of the circular buffer (one behind the last element).
    pointer m_last;

    //! The number of items currently stored in the circular buffer.
    size_type m_size;

    //! The allocator.
    allocator_type m_alloc;

// Friends
#if defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
    friend iterator;
    friend const_iterator;
#else
    template <class Buff, class Traits> friend struct cb_details::iterator;
#endif

public:
// Allocator

    //! Get the allocator.
    /*!
        \return The allocator.
        \throws Nothing.
        \par Exception Safety
             No-throw.
        \par Iterator Invalidation
             Does not invalidate any iterators.
        \par Complexity
             Constant (in the size of the <code>circular_buffer</code>).
        \sa <code>get_allocator()</code> for obtaining an allocator %reference.
    */
    allocator_type get_allocator() const { return m_alloc; }

    //! Get the allocator reference.
    /*!
        \return A reference to the allocator.
        \throws Nothing.
        \par Exception Safety
             No-throw.
        \par Iterator Invalidation
             Does not invalidate any iterators.
        \par Complexity
             Constant (in the size of the <code>circular_buffer</code>).
        \note This method was added in order to optimize obtaining of the allocator with a state,
              although use of stateful allocators in STL is discouraged.
        \sa <code>get_allocator() const</code>
    */
    allocator_type& get_allocator() { return m_alloc; }

// Element access

    //! Get the iterator pointing to the beginning of the <code>circular_buffer</code>.
    /*!
        \return A random access iterator pointing to the first element of the <code>circular_buffer</code>. If the
                <code>circular_buffer</code> is empty it returns an iterator equal to the one returned by
                <code>end()</code>.
        \throws Nothing.
        \par Exception Safety
             No-throw.
        \par Iterator Invalidation
             Does not invalidate any iterators.
        \par Complexity
             Constant (in the size of the <code>circular_buffer</code>).
        \sa <code>end()</code>, <code>rbegin()</code>, <code>rend()</code>
    */
    iterator begin() { return iterator(this, empty() ? 0 : m_first); }

    //! Get the iterator pointing to the end of the <code>circular_buffer</code>.
    /*!
        \return A random access iterator pointing to the element "one behind" the last element of the <code>
                circular_buffer</code>. If the <code>circular_buffer</code> is empty it returns an iterator equal to
                the one returned by <code>begin()</code>.
        \throws Nothing.
        \par Exception Safety
             No-throw.
        \par Iterator Invalidation
             Does not invalidate any iterators.
        \par Complexity
             Constant (in the size of the <code>circular_buffer</code>).
        \sa <code>begin()</code>, <code>rbegin()</code>, <code>rend()</code>
    */
    iterator end() { return iterator(this, 0); }

    //! Get the const iterator pointing to the beginning of the <code>circular_buffer</code>.
    /*!
        \return A const random access iterator pointing to the first element of the <code>circular_buffer</code>. If
                the <code>circular_buffer</code> is empty it returns an iterator equal to the one returned by
                <code>end() const</code>.
        \throws Nothing.
        \par Exception Safety
             No-throw.
        \par Iterator Invalidation
             Does not invalidate any iterators.
        \par Complexity
             Constant (in the size of the <code>circular_buffer</code>).
        \sa <code>end() const</code>, <code>rbegin() const</code>, <code>rend() const</code>
    */
    const_iterator begin() const { return const_iterator(this, empty() ? 0 : m_first); }

    //! Get the const iterator pointing to the end of the <code>circular_buffer</code>.
    /*!
        \return A const random access iterator pointing to the element "one behind" the last element of the <code>
                circular_buffer</code>. If the <code>circular_buffer</code> is empty it returns an iterator equal to
                the one returned by <code>begin() const</code> const.
        \throws Nothing.
        \par Exception Safety
             No-throw.
        \par Iterator Invalidation
             Does not invalidate any iterators.
        \par Complexity
             Constant (in the size of the <code>circular_buffer</code>).
        \sa <code>begin() const</code>, <code>rbegin() const</code>, <code>rend() const</code>
    */
    const_iterator end() const { return const_iterator(this, 0); }

    //! Get the iterator pointing to the beginning of the "reversed" <code>circular_buffer</code>.
    /*!
        \return A reverse random access iterator pointing to the last element of the <code>circular_buffer</code>.
                If the <code>circular_buffer</code> is empty it returns an iterator equal to the one returned by
                <code>rend()</code>.
        \throws Nothing.
        \par Exception Safety
             No-throw.
        \par Iterator Invalidation
             Does not invalidate any iterators.
        \par Complexity
             Constant (in the size of the <code>circular_buffer</code>).
        \sa <code>rend()</code>, <code>begin()</code>, <code>end()</code>
    */
    reverse_iterator rbegin() { return reverse_iterator(end()); }

    //! Get the iterator pointing to the end of the "reversed" <code>circular_buffer</code>.
    /*!
        \return A reverse random access iterator pointing to the element "one before" the first element of the <code>
                circular_buffer</code>. If the <code>circular_buffer</code> is empty it returns an iterator equal to
                the one returned by <code>rbegin()</code>.
        \throws Nothing.
        \par Exception Safety
             No-throw.
        \par Iterator Invalidation
             Does not invalidate any iterators.
        \par Complexity
             Constant (in the size of the <code>circular_buffer</code>).
        \sa <code>rbegin()</code>, <code>begin()</code>, <code>end()</code>
    */
    reverse_iterator rend() { return reverse_iterator(begin()); }

    //! Get the const iterator pointing to the beginning of the "reversed" <code>circular_buffer</code>.
    /*!
        \return A const reverse random access iterator pointing to the last element of the
                <code>circular_buffer</code>. If the <code>circular_buffer</code> is empty it returns an iterator equal
                to the one returned by <code>rend() const</code>.
        \throws Nothing.
        \par Exception Safety
             No-throw.
        \par Iterator Invalidation
             Does not invalidate any iterators.
        \par Complexity
             Constant (in the size of the <code>circular_buffer</code>).
        \sa <code>rend() const</code>, <code>begin() const</code>, <code>end() const</code>
    */
    const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }

    //! Get the const iterator pointing to the end of the "reversed" <code>circular_buffer</code>.
    /*!
        \return A const reverse random access iterator pointing to the element "one before" the first element of the
                <code>circular_buffer</code>. If the <code>circular_buffer</code> is empty it returns an iterator equal
                to the one returned by <code>rbegin() const</code>.
        \throws Nothing.
        \par Exception Safety
             No-throw.
        \par Iterator Invalidation
             Does not invalidate any iterators.
        \par Complexity
             Constant (in the size of the <code>circular_buffer</code>).
        \sa <code>rbegin() const</code>, <code>begin() const</code>, <code>end() const</code>
    */
    const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }

    //! Get the element at the <code>index</code> position.
    /*!
        \pre <code>0 \<= index \&\& index \< size()</code>
        \param index The position of the element.
        \return A reference to the element at the <code>index</code> position.
        \throws Nothing.
        \par Exception Safety
             No-throw.
        \par Iterator Invalidation
             Does not invalidate any iterators.
        \par Complexity
             Constant (in the size of the <code>circular_buffer</code>).
        \sa <code>at()</code>
    */
    reference operator [] (size_type index) {
        BOOST_CB_ASSERT(index < size()); // check for invalid index
        return *add(m_first, index);
    }

    //! Get the element at the <code>index</code> position.
    /*!
        \pre <code>0 \<= index \&\& index \< size()</code>
        \param index The position of the element.
        \return A const reference to the element at the <code>index</code> position.
        \throws Nothing.
        \par Exception Safety
             No-throw.
        \par Iterator Invalidation
             Does not invalidate any iterators.
        \par Complexity
             Constant (in the size of the <code>circular_buffer</code>).
        \sa <code>\link at(size_type)const at() const \endlink</code>
    */
    return_value_type operator [] (size_type index) const {
        BOOST_CB_ASSERT(index < size()); // check for invalid index
        return *add(m_first, index);
    }

    //! Get the element at the <code>index</code> position.
    /*!
        \param index The position of the element.
        \return A reference to the element at the <code>index</code> position.
        \throws <code>std::out_of_range</code> when the <code>index</code> is invalid (when
                <code>index >= size()</code>).
        \par Exception Safety
             Strong.
        \par Iterator Invalidation
             Does not invalidate any iterators.
        \par Complexity
             Constant (in the size of the <code>circular_buffer</code>).
        \sa <code>operator[]</code>
    */
    reference at(size_type index) {
        check_position(index);
        return (*this)[index];
    }

    //! Get the element at the <code>index</code> position.
    /*!
        \param index The position of the element.
        \return A const reference to the element at the <code>index</code> position.
        \throws <code>std::out_of_range</code> when the <code>index</code> is invalid (when
                <code>index >= size()</code>).
        \par Exception Safety
             Strong.
        \par Iterator Invalidation
             Does not invalidate any iterators.
        \par Complexity
             Constant (in the size of the <code>circular_buffer</code>).
        \sa <code>\link operator[](size_type)const operator[] const \endlink</code>
    */
    return_value_type at(size_type index) const {
        check_position(index);
        return (*this)[index];
    }

    //! Get the first element.
    /*!
        \pre <code>!empty()</code>
        \return A reference to the first element of the <code>circular_buffer</code>.
        \throws Nothing.
        \par Exception Safety
             No-throw.
        \par Iterator Invalidation
             Does not invalidate any iterators.
        \par Complexity
             Constant (in the size of the <code>circular_buffer</code>).
        \sa <code>back()</code>
    */
    reference front() {
        BOOST_CB_ASSERT(!empty()); // check for empty buffer (front element not available)
        return *m_first;
    }

    //! Get the last element.
    /*!
        \pre <code>!empty()</code>
        \return A reference to the last element of the <code>circular_buffer</code>.
        \throws Nothing.
        \par Exception Safety
             No-throw.
        \par Iterator Invalidation
             Does not invalidate any iterators.
        \par Complexity
             Constant (in the size of the <code>circular_buffer</code>).
        \sa <code>front()</code>
    */
    reference back() {
        BOOST_CB_ASSERT(!empty()); // check for empty buffer (back element not available)
        return *((m_last == m_buff ? m_end : m_last) - 1);
    }

    //! Get the first element.
    /*!
        \pre <code>!empty()</code>
        \return A const reference to the first element of the <code>circular_buffer</code>.
        \throws Nothing.
        \par Exception Safety
             No-throw.
        \par Iterator Invalidation
             Does not invalidate any iterators.
        \par Complexity
             Constant (in the size of the <code>circular_buffer</code>).
        \sa <code>back() const</code>
    */
    return_value_type front() const {
        BOOST_CB_ASSERT(!empty()); // check for empty buffer (front element not available)
        return *m_first;
    }

    //! Get the last element.
    /*!
        \pre <code>!empty()</code>
        \return A const reference to the last element of the <code>circular_buffer</code>.
        \throws Nothing.
        \par Exception Safety
             No-throw.
        \par Iterator Invalidation
             Does not invalidate any iterators.
        \par Complexity
             Constant (in the size of the <code>circular_buffer</code>).
        \sa <code>front() const</code>
    */
    return_value_type back() const {
        BOOST_CB_ASSERT(!empty()); // check for empty buffer (back element not available)
        return *((m_last == m_buff ? m_end : m_last) - 1);
    }

    //! Get the first continuous array of the internal buffer.
    /*!
        This method in combination with <code>array_two()</code> can be useful when passing the stored data into
        a legacy C API as an array. Suppose there is a <code>circular_buffer</code> of capacity 10, containing 7
        characters <code>'a', 'b', ..., 'g'</code> where <code>buff[0] == 'a'</code>, <code>buff[1] == 'b'</code>,
        ... and <code>buff[6] == 'g'</code>:<br><br>
        <code>circular_buffer<char> buff(10);</code><br><br>
        The internal representation is often not linear and the state of the internal buffer may look like this:<br>
        <br><code>
        |e|f|g| | | |a|b|c|d|<br>
        end ---^<br>
        begin -------^</code><br><br>
        where <code>|a|b|c|d|</code> represents the "array one", <code>|e|f|g|</code> represents the "array two" and
        <code>| | | |</code> is a free space.<br>
        Now consider a typical C style function for writing data into a file:<br><br>
        <code>int write(int file_desc, char* buff, int num_bytes);</code><br><br>
        There are two ways how to write the content of the <code>circular_buffer</code> into a file. Either relying
        on <code>array_one()</code> and <code>array_two()</code> methods and calling the write function twice:<br><br>
        <code>array_range ar = buff.array_one();<br>
        write(file_desc, ar.first, ar.second);<br>
        ar = buff.array_two();<br>
        write(file_desc, ar.first, ar.second);</code><br><br>
        Or relying on the <code>linearize()</code> method:<br><br><code>
        write(file_desc, buff.linearize(), buff.size());</code><br><br>
        Since the complexity of <code>array_one()</code> and <code>array_two()</code> methods is constant the first
        option is suitable when calling the write method is "cheap". On the other hand the second option is more
        suitable when calling the write method is more "expensive" than calling the <code>linearize()</code> method
        whose complexity is linear.
        \return The array range of the first continuous array of the internal buffer. In the case the
                <code>circular_buffer</code> is empty the size of the returned array is <code>0</code>.
        \throws Nothing.
        \par Exception Safety
             No-throw.
        \par Iterator Invalidation
             Does not invalidate any iterators.
        \par Complexity
             Constant (in the size of the <code>circular_buffer</code>).
        \warning In general invoking any method which modifies the internal state of the circular_buffer  may
                 delinearize the internal buffer and invalidate the array ranges returned by <code>array_one()</code>
                 and <code>array_two()</code> (and their const versions).
        \note In the case the internal buffer is linear e.g. <code>|a|b|c|d|e|f|g| | | |</code> the "array one" is
              represented by <code>|a|b|c|d|e|f|g|</code> and the "array two" does not exist (the
              <code>array_two()</code> method returns an array with the size <code>0</code>).
        \sa <code>array_two()</code>, <code>linearize()</code>
    */
    array_range array_one() {
        return array_range(m_first, (m_last <= m_first && !empty() ? m_end : m_last) - m_first);
    }

    //! Get the second continuous array of the internal buffer.
    /*!
        This method in combination with <code>array_one()</code> can be useful when passing the stored data into
        a legacy C API as an array.
        \return The array range of the second continuous array of the internal buffer. In the case the internal buffer
                is linear or the <code>circular_buffer</code> is empty the size of the returned array is
                <code>0</code>.
        \throws Nothing.
        \par Exception Safety
             No-throw.
        \par Iterator Invalidation
             Does not invalidate any iterators.
        \par Complexity
             Constant (in the size of the <code>circular_buffer</code>).
        \sa <code>array_one()</code>
    */
    array_range array_two() {
        return array_range(m_buff, m_last <= m_first && !empty() ? m_last - m_buff : 0);
    }

    //! Get the first continuous array of the internal buffer.
    /*!
        This method in combination with <code>array_two() const</code> can be useful when passing the stored data into
        a legacy C API as an array.
        \return The array range of the first continuous array of the internal buffer. In the case the
                <code>circular_buffer</code> is empty the size of the returned array is <code>0</code>.
        \throws Nothing.
        \par Exception Safety
             No-throw.
        \par Iterator Invalidation
             Does not invalidate any iterators.
        \par Complexity
             Constant (in the size of the <code>circular_buffer</code>).
        \sa <code>array_two() const</code>; <code>array_one()</code> for more details how to pass data into a legacy C
            API.
    */
    const_array_range array_one() const {
        return const_array_range(m_first, (m_last <= m_first && !empty() ? m_end : m_last) - m_first);
    }

    //! Get the second continuous array of the internal buffer.
    /*!
        This method in combination with <code>array_one() const</code> can be useful when passing the stored data into
        a legacy C API as an array.
        \return The array range of the second continuous array of the internal buffer. In the case the internal buffer
                is linear or the <code>circular_buffer</code> is empty the size of the returned array is
                <code>0</code>.
        \throws Nothing.
        \par Exception Safety
             No-throw.
        \par Iterator Invalidation
             Does not invalidate any iterators.
        \par Complexity
             Constant (in the size of the <code>circular_buffer</code>).
        \sa <code>array_one() const</code>
    */
    const_array_range array_two() const {
        return const_array_range(m_buff, m_last <= m_first && !empty() ? m_last - m_buff : 0);
    }

    //! Linearize the internal buffer into a continuous array.
    /*!
        This method can be useful when passing the stored data into a legacy C API as an array.
        \post <code>\&(*this)[0] \< \&(*this)[1] \< ... \< \&(*this)[size() - 1]</code>
        \return A pointer to the beginning of the array or <code>0</code> if empty.
        \throws Whatever <code>T::T(const T&)</code> throws.
        \throws Whatever <code>T::operator = (const T&)</code> throws.
        \par Exception Safety
             Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything.
        \par Iterator Invalidation
             Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
             <code>end()</code>); does not invalidate any iterators if the postcondition (the <i>Effect</i>) is already
             met prior calling this method.
        \par Complexity
             Linear (in the size of the <code>circular_buffer</code>); constant if the postcondition (the
             <i>Effect</i>) is already met.
        \warning In general invoking any method which modifies the internal state of the <code>circular_buffer</code>
                 may delinearize the internal buffer and invalidate the returned pointer.
        \sa <code>array_one()</code> and <code>array_two()</code> for the other option how to pass data into a legacy
            C API.
    */
    pointer linearize() {
        if (empty())
            return 0;
        if (m_first < m_last || m_last == m_buff)
            return m_first;
        pointer src = m_first;
        pointer dest = m_buff;
        size_type moved = 0;
        size_type constructed = 0;
        BOOST_TRY {
            for (pointer first = m_first; dest < src; src = first) {
                for (size_type ii = 0; src < m_end; ++src, ++dest, ++moved, ++ii) {
                    if (moved == size()) {
                        first = dest;
                        break;
                    }
                    if (dest == first) {
                        first += ii;
                        break;
                    }
                    if (is_uninitialized(dest)) {
                        m_alloc.construct(dest, *src);
                        ++constructed;
                    } else {
                        value_type tmp = *src;
                        replace(src, *dest);
                        replace(dest, tmp);
                    }
                }
            }
        } BOOST_CATCH(...) {
            m_last += constructed;
            m_size += constructed;
            BOOST_RETHROW
        }
        BOOST_CATCH_END
        for (src = m_end - constructed; src < m_end; ++src)
            destroy_item(src);
        m_first = m_buff;
        m_last = add(m_buff, size());
#if BOOST_CB_ENABLE_DEBUG
        invalidate_iterators_except(end());
#endif
        return m_buff;
    }

// Size and capacity

    //! Get the number of elements currently stored in the <code>circular_buffer</code>.
    /*!
        \return The number of elements stored in the <code>circular_buffer</code>.
        \throws Nothing.
        \par Exception Safety
             No-throw.
        \par Iterator Invalidation
             Does not invalidate any iterators.
        \par Complexity
             Constant (in the size of the <code>circular_buffer</code>).
        \sa <code>capacity()</code>, <code>max_size()</code>, <code>reserve()</code>,
            <code>\link resize() resize(size_type, const_reference)\endlink</code>
    */
    size_type size() const { return m_size; }

    /*! \brief Get the largest possible size or capacity of the <code>circular_buffer</code>. (It depends on
               allocator's %max_size()).
        \return The maximum size/capacity the <code>circular_buffer</code> can be set to.
        \throws Nothing.
        \par Exception Safety
             No-throw.
        \par Iterator Invalidation
             Does not invalidate any iterators.
        \par Complexity
             Constant (in the size of the <code>circular_buffer</code>).
        \sa <code>size()</code>, <code>capacity()</code>, <code>reserve()</code>
    */
    size_type max_size() const {
        return (std::min<size_type>)(m_alloc.max_size(), (std::numeric_limits<difference_type>::max)());
    }

    //! Is the <code>circular_buffer</code> empty?
    /*!
        \return <code>true</code> if there are no elements stored in the <code>circular_buffer</code>;
                <code>false</code> otherwise.
        \throws Nothing.
        \par Exception Safety
             No-throw.
        \par Iterator Invalidation
             Does not invalidate any iterators.
        \par Complexity
             Constant (in the size of the <code>circular_buffer</code>).
        \sa <code>full()</code>
    */
    bool empty() const { return size() == 0; }

    //! Is the <code>circular_buffer</code> full?
    /*!
        \return <code>true</code> if the number of elements stored in the <code>circular_buffer</code>
                equals the capacity of the <code>circular_buffer</code>; <code>false</code> otherwise.
        \throws Nothing.
        \par Exception Safety
             No-throw.
        \par Iterator Invalidation
             Does not invalidate any iterators.
        \par Complexity
             Constant (in the size of the <code>circular_buffer</code>).
        \sa <code>empty()</code>
    */
    bool full() const { return capacity() == size(); }

    /*! \brief Get the maximum number of elements which can be inserted into the <code>circular_buffer</code> without
               overwriting any of already stored elements.
        \return <code>capacity() - size()</code>
        \throws Nothing.
        \par Exception Safety
             No-throw.
        \par Iterator Invalidation
             Does not invalidate any iterators.
        \par Complexity
             Constant (in the size of the <code>circular_buffer</code>).
        \sa <code>capacity()</code>, <code>size()</code>, <code>max_size()</code>
    */
    size_type reserve() const { return capacity() - size(); }

    //! Get the capacity of the <code>circular_buffer</code>.
    /*!
        \return The maximum number of elements which can be stored in the <code>circular_buffer</code>.
        \throws Nothing.
        \par Exception Safety
             No-throw.
        \par Iterator Invalidation
             Does not invalidate any iterators.
        \par Complexity
             Constant (in the size of the <code>circular_buffer</code>).
        \sa <code>reserve()</code>, <code>size()</code>, <code>max_size()</code>,
            <code>set_capacity(capacity_type)</code>
    */
    capacity_type capacity() const { return m_end - m_buff; }

    //! Change the capacity of the <code>circular_buffer</code>.
    /*!
        \post <code>capacity() == new_capacity \&\& size() \<= new_capacity</code><br><br>
              If the current number of elements stored in the <code>circular_buffer</code> is greater than the desired
              new capacity then number of <code>[size() - new_capacity]</code> <b>last</b> elements will be removed and
              the new size will be equal to <code>new_capacity</code>.
        \param new_capacity The new capacity.
        \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
                used).
        \throws Whatever <code>T::T(const T&)</code> throws.
        \par Exception Safety
             Strong.
        \par Iterator Invalidation
             Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
             <code>end()</code>) if the new capacity is different from the original.
        \par Complexity
             Linear (in <code>min[size(), new_capacity]</code>).
        \sa <code>rset_capacity(capacity_type)</code>,
            <code>\link resize() resize(size_type, const_reference)\endlink</code>
    */
    void set_capacity(capacity_type new_capacity) {
        if (new_capacity == capacity())
            return;
        pointer buff = allocate(new_capacity);
        iterator b = begin();
        BOOST_TRY {
            reset(buff,
                cb_details::uninitialized_copy_with_alloc(b, b + (std::min)(new_capacity, size()), buff, m_alloc),
                new_capacity);
        } BOOST_CATCH(...) {
            deallocate(buff, new_capacity);
            BOOST_RETHROW
        }
        BOOST_CATCH_END
    }

    //! Change the size of the <code>circular_buffer</code>.
    /*!
        \post <code>size() == new_size \&\& capacity() >= new_size</code><br><br>
              If the new size is greater than the current size, copies of <code>item</code> will be inserted at the
              <b>back</b> of the of the <code>circular_buffer</code> in order to achieve the desired size. In the case
              the resulting size exceeds the current capacity the capacity will be set to <code>new_size</code>.<br>
              If the current number of elements stored in the <code>circular_buffer</code> is greater than the desired
              new size then number of <code>[size() - new_size]</code> <b>last</b> elements will be removed. (The
              capacity will remain unchanged.)
        \param new_size The new size.
        \param item The element the <code>circular_buffer</code> will be filled with in order to gain the requested
                    size. (See the <i>Effect</i>.)
        \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
                used).
        \throws Whatever <code>T::T(const T&)</code> throws.
        \par Exception Safety
             Basic.
        \par Iterator Invalidation
             Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
             <code>end()</code>) if the new size is greater than the current capacity. Invalidates iterators pointing
             to the removed elements if the new size is lower that the original size. Otherwise it does not invalidate
             any iterator.
        \par Complexity
             Linear (in the new size of the <code>circular_buffer</code>).
        \sa <code>\link rresize() rresize(size_type, const_reference)\endlink</code>,
            <code>set_capacity(capacity_type)</code>
    */
    void resize(size_type new_size, param_value_type item = value_type()) {
        if (new_size > size()) {
            if (new_size > capacity())
                set_capacity(new_size);
            insert(end(), new_size - size(), item);
        } else {
            iterator e = end();
            erase(e - (size() - new_size), e);
        }
    }

    //! Change the capacity of the <code>circular_buffer</code>.
    /*!
        \post <code>capacity() == new_capacity \&\& size() \<= new_capacity</code><br><br>
              If the current number of elements stored in the <code>circular_buffer</code> is greater than the desired
              new capacity then number of <code>[size() - new_capacity]</code> <b>first</b> elements will be removed
              and the new size will be equal to <code>new_capacity</code>.
        \param new_capacity The new capacity.
        \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
                used).
        \throws Whatever <code>T::T(const T&)</code> throws.
        \par Exception Safety
             Strong.
        \par Iterator Invalidation
             Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
             <code>end()</code>) if the new capacity is different from the original.
        \par Complexity
             Linear (in <code>min[size(), new_capacity]</code>).
        \sa <code>set_capacity(capacity_type)</code>,
            <code>\link rresize() rresize(size_type, const_reference)\endlink</code>
    */
    void rset_capacity(capacity_type new_capacity) {
        if (new_capacity == capacity())
            return;
        pointer buff = allocate(new_capacity);
        iterator e = end();
        BOOST_TRY {
            reset(buff, cb_details::uninitialized_copy_with_alloc(e - (std::min)(new_capacity, size()),
                e, buff, m_alloc), new_capacity);
        } BOOST_CATCH(...) {
            deallocate(buff, new_capacity);
            BOOST_RETHROW
        }
        BOOST_CATCH_END
    }

    //! Change the size of the <code>circular_buffer</code>.
    /*!
        \post <code>size() == new_size \&\& capacity() >= new_size</code><br><br>
              If the new size is greater than the current size, copies of <code>item</code> will be inserted at the
              <b>front</b> of the of the <code>circular_buffer</code> in order to achieve the desired size. In the case
              the resulting size exceeds the current capacity the capacity will be set to <code>new_size</code>.<br>
              If the current number of elements stored in the <code>circular_buffer</code> is greater than the desired
              new size then number of <code>[size() - new_size]</code> <b>first</b> elements will be removed. (The
              capacity will remain unchanged.)
        \param new_size The new size.
        \param item The element the <code>circular_buffer</code> will be filled with in order to gain the requested
                    size. (See the <i>Effect</i>.)
        \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
                used).
        \throws Whatever <code>T::T(const T&)</code> throws.
        \par Exception Safety
             Basic.
        \par Iterator Invalidation
             Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
             <code>end()</code>) if the new size is greater than the current capacity. Invalidates iterators pointing
             to the removed elements if the new size is lower that the original size. Otherwise it does not invalidate
             any iterator.
        \par Complexity
             Linear (in the new size of the <code>circular_buffer</code>).
        \sa <code>\link resize() resize(size_type, const_reference)\endlink</code>,
            <code>rset_capacity(capacity_type)</code>
    */
    void rresize(size_type new_size, param_value_type item = value_type()) {
        if (new_size > size()) {
            if (new_size > capacity())
                set_capacity(new_size);
            rinsert(begin(), new_size - size(), item);
        } else {
            rerase(begin(), end() - new_size);
        }
    }

// Construction/Destruction

    //! Create an empty <code>circular_buffer</code> with a maximum capacity.
    /*!
        \post <code>capacity() == max_size() \&\& size() == 0</code>
        \param alloc The allocator.
        \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
                used).
        \par Complexity
             Constant.
        \warning This constructor has been defined only due to compatibility with the STL container definition. Avoid
                 using it because it may allocate <b>very large</b> amount of memory (depending on allocator's
                 %max_size()).
    */
    explicit circular_buffer(const allocator_type& alloc = allocator_type())
    : m_size(0), m_alloc(alloc) {
        initialize(max_size());
    }

    //! Create an empty <code>circular_buffer</code> with the specified capacity.
    /*!
        \post <code>capacity() == capacity \&\& size() == 0</code>
        \param capacity The maximum number of elements which can be stored in the <code>circular_buffer</code>.
        \param alloc The allocator.
        \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
                used).
        \par Complexity
             Constant.
    */
    explicit circular_buffer(capacity_type capacity, const allocator_type& alloc = allocator_type())
    : m_size(0), m_alloc(alloc) {
        initialize(capacity);
    }

    /*! \brief Create a full <code>circular_buffer</code> with the specified capacity and filled with <code>n</code>
               copies of <code>item</code>.
        \post <code>capacity() == n \&\& full() \&\& (*this)[0] == item \&\& (*this)[1] == item \&\& ... \&\&
              (*this)[n - 1] == item </code>
        \param n The number of elements the created <code>circular_buffer</code> will be filled with.
        \param item The element the created <code>circular_buffer</code> will be filled with.
        \param alloc The allocator.
        \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
                used).
        \throws Whatever <code>T::T(const T&)</code> throws.
        \par Complexity
             Linear (in the <code>n</code>).
    */
    circular_buffer(size_type n, param_value_type item, const allocator_type& alloc = allocator_type())
    : m_size(n), m_alloc(alloc) {
        initialize(n, item);
    }

    /*! \brief Create a <code>circular_buffer</code> with the specified capacity and filled with <code>n</code>
               copies of <code>item</code>.
        \pre <code>capacity >= n</code>
        \post <code>capacity() == capacity \&\& size() == n \&\& (*this)[0] == item \&\& (*this)[1] == item \&\& ...
              \&\& (*this)[n - 1] == item</code>
        \param capacity The capacity of the created <code>circular_buffer</code>.
        \param n The number of elements the created <code>circular_buffer</code> will be filled with.
        \param item The element the created <code>circular_buffer</code> will be filled with.
        \param alloc The allocator.
        \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
                used).
        \throws Whatever <code>T::T(const T&)</code> throws.
        \par Complexity
             Linear (in the <code>n</code>).
    */
    circular_buffer(capacity_type capacity, size_type n, param_value_type item,
        const allocator_type& alloc = allocator_type())
    : m_size(n), m_alloc(alloc) {
        BOOST_CB_ASSERT(capacity >= size()); // check for capacity lower than size
        initialize(capacity, item);
    }

    //! The copy constructor.
    /*!
        Creates a copy of the specified <code>circular_buffer</code>.
        \post <code>*this == cb</code>
        \param cb The <code>circular_buffer</code> to be copied.
        \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
                used).
        \throws Whatever <code>T::T(const T&)</code> throws.
        \par Complexity
             Linear (in the size of <code>cb</code>).
    */
    circular_buffer(const circular_buffer<T, Alloc>& cb)
    : m_size(cb.size()), m_alloc(cb.get_allocator()) {
        m_first = m_last = m_buff = allocate(cb.capacity());
        BOOST_TRY {
            m_end = cb_details::uninitialized_copy_with_alloc(cb.begin(), cb.end(), m_buff, m_alloc);
        } BOOST_CATCH(...) {
            deallocate(m_buff, cb.capacity());
            BOOST_RETHROW
        }
        BOOST_CATCH_END
    }

#if BOOST_WORKAROUND(BOOST_MSVC, < 1300)

    /*! \cond */
    template <class InputIterator>
    circular_buffer(InputIterator first, InputIterator last)
    : m_alloc(allocator_type()) {
        initialize(first, last, is_integral<InputIterator>());
    }

    template <class InputIterator>
    circular_buffer(capacity_type capacity, InputIterator first, InputIterator last)
    : m_alloc(allocator_type()) {
        initialize(capacity, first, last, is_integral<InputIterator>());
    }
    /*! \endcond */

#else

    //! Create a full <code>circular_buffer</code> filled with a copy of the range.
    /*!
        \pre Valid range <code>[first, last)</code>.<br>
             <code>first</code> and <code>last</code> have to meet the requirements of
             <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
        \post <code>capacity() == std::distance(first, last) \&\& full() \&\& (*this)[0]== *first \&\&
              (*this)[1] == *(first + 1) \&\& ... \&\& (*this)[std::distance(first, last) - 1] == *(last - 1)</code>
        \param first The beginning of the range to be copied.
        \param last The end of the range to be copied.
        \param alloc The allocator.
        \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
                used).
        \throws Whatever <code>T::T(const T&)</code> throws.
        \par Complexity
             Linear (in the <code>std::distance(first, last)</code>).
    */
    template <class InputIterator>
    circular_buffer(InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type())
    : m_alloc(alloc) {
        initialize(first, last, is_integral<InputIterator>());
    }

    //! Create a <code>circular_buffer</code> with the specified capacity and filled with a copy of the range.
    /*!
        \pre Valid range <code>[first, last)</code>.<br>
             <code>first</code> and <code>last</code> have to meet the requirements of
             <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
        \post <code>capacity() == capacity \&\& size() \<= std::distance(first, last) \&\&
             (*this)[0]== *(last - capacity) \&\& (*this)[1] == *(last - capacity + 1) \&\& ... \&\&
             (*this)[capacity - 1] == *(last - 1)</code><br><br>
             If the number of items to be copied from the range <code>[first, last)</code> is greater than the
             specified <code>capacity</code> then only elements from the range <code>[last - capacity, last)</code>
             will be copied.
        \param capacity The capacity of the created <code>circular_buffer</code>.
        \param first The beginning of the range to be copied.
        \param last The end of the range to be copied.
        \param alloc The allocator.
        \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
                used).
        \throws Whatever <code>T::T(const T&)</code> throws.
        \par Complexity
             Linear (in <code>std::distance(first, last)</code>; in
             <code>min[capacity, std::distance(first, last)]</code> if the <code>InputIterator</code> is a
             <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>).
    */
    template <class InputIterator>
    circular_buffer(capacity_type capacity, InputIterator first, InputIterator last,
        const allocator_type& alloc = allocator_type())
    : m_alloc(alloc) {
        initialize(capacity, first, last, is_integral<InputIterator>());
    }

#endif // #if BOOST_WORKAROUND(BOOST_MSVC, < 1300)

    //! The destructor.
    /*!
        Destroys the <code>circular_buffer</code>.
        \throws Nothing.
        \par Iterator Invalidation
             Invalidates all iterators pointing to the <code>circular_buffer</code> (including iterators equal to
             <code>end()</code>).
        \par Complexity
             Linear (in the size of the <code>circular_buffer</code>).
        \sa <code>clear()</code>
    */
    ~circular_buffer() {
        destroy();
#if BOOST_CB_ENABLE_DEBUG
        invalidate_all_iterators();
#endif
    }

public:
// Assign methods

    //! The assign operator.
    /*!
        Makes this <code>circular_buffer</code> to become a copy of the specified <code>circular_buffer</code>.
        \post <code>*this == cb</code>
        \param cb The <code>circular_buffer</code> to be copied.
        \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
                used).
        \throws Whatever <code>T::T(const T&)</code> throws.
        \par Exception Safety
             Strong.
        \par Iterator Invalidation
             Invalidates all iterators pointing to this <code>circular_buffer</code> (except iterators equal to
             <code>end()</code>).
        \par Complexity
             Linear (in the size of <code>cb</code>).
        \sa <code>\link assign(size_type, param_value_type) assign(size_type, const_reference)\endlink</code>,
            <code>\link assign(capacity_type, size_type, param_value_type)
            assign(capacity_type, size_type, const_reference)\endlink</code>,
            <code>assign(InputIterator, InputIterator)</code>,
            <code>assign(capacity_type, InputIterator, InputIterator)</code>
    */
    circular_buffer<T, Alloc>& operator = (const circular_buffer<T, Alloc>& cb) {
        if (this == &cb)
            return *this;
        pointer buff = allocate(cb.capacity());
        BOOST_TRY {
            reset(buff, cb_details::uninitialized_copy_with_alloc(cb.begin(), cb.end(), buff, m_alloc), cb.capacity());
        } BOOST_CATCH(...) {
            deallocate(buff, cb.capacity());
            BOOST_RETHROW
        }
        BOOST_CATCH_END
        return *this;
    }

    //! Assign <code>n</code> items into the <code>circular_buffer</code>.
    /*!
        The content of the <code>circular_buffer</code> will be removed and replaced with <code>n</code> copies of the
        <code>item</code>.
        \post <code>capacity() == n \&\& size() == n \&\& (*this)[0] == item \&\& (*this)[1] == item \&\& ... \&\&
              (*this) [n - 1] == item</code>
        \param n The number of elements the <code>circular_buffer</code> will be filled with.
        \param item The element the <code>circular_buffer</code> will be filled with.
        \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
                used).
        \throws Whatever <code>T::T(const T&)</code> throws.
        \par Exception Safety
             Basic.
        \par Iterator Invalidation
             Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
             <code>end()</code>).
        \par Complexity
             Linear (in the <code>n</code>).
        \sa <code>operator=</code>, <code>\link assign(capacity_type, size_type, param_value_type)
            assign(capacity_type, size_type, const_reference)\endlink</code>,
            <code>assign(InputIterator, InputIterator)</code>,
            <code>assign(capacity_type, InputIterator, InputIterator)</code>
    */
    void assign(size_type n, param_value_type item) {
        assign_n(n, n, cb_details::assign_n<param_value_type, allocator_type>(n, item, m_alloc));
    }

    //! Assign <code>n</code> items into the <code>circular_buffer</code> specifying the capacity.
    /*!
        The capacity of the <code>circular_buffer</code> will be set to the specified value and the content of the
        <code>circular_buffer</code> will be removed and replaced with <code>n</code> copies of the <code>item</code>.
        \pre <code>capacity >= n</code>
        \post <code>capacity() == capacity \&\& size() == n \&\& (*this)[0] == item \&\& (*this)[1] == item
              \&\& ... \&\& (*this) [n - 1] == item </code>
        \param capacity The new capacity.
        \param n The number of elements the <code>circular_buffer</code> will be filled with.
        \param item The element the <code>circular_buffer</code> will be filled with.
        \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
                used).
        \throws Whatever <code>T::T(const T&)</code> throws.
        \par Exception Safety
             Basic.
        \par Iterator Invalidation
             Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
             <code>end()</code>).
        \par Complexity
             Linear (in the <code>n</code>).
        \sa <code>operator=</code>, <code>\link assign(size_type, param_value_type)
            assign(size_type, const_reference)\endlink</code>, <code>assign(InputIterator, InputIterator)</code>,
            <code>assign(capacity_type, InputIterator, InputIterator)</code>
    */
    void assign(capacity_type capacity, size_type n, param_value_type item) {
        BOOST_CB_ASSERT(capacity >= n); // check for new capacity lower than n
        assign_n(capacity, n, cb_details::assign_n<param_value_type, allocator_type>(n, item, m_alloc));
    }

    //! Assign a copy of the range into the <code>circular_buffer</code>.
    /*!
        The content of the <code>circular_buffer</code> will be removed and replaced with copies of elements from the
        specified range.
        \pre Valid range <code>[first, last)</code>.<br>
             <code>first</code> and <code>last</code> have to meet the requirements of
             <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
        \post <code>capacity() == std::distance(first, last) \&\& size() == std::distance(first, last) \&\&
             (*this)[0]== *first \&\& (*this)[1] == *(first + 1) \&\& ... \&\& (*this)[std::distance(first, last) - 1]
             == *(last - 1)</code>
        \param first The beginning of the range to be copied.
        \param last The end of the range to be copied.
        \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
                used).
        \throws Whatever <code>T::T(const T&)</code> throws.
        \par Exception Safety
             Basic.
        \par Iterator Invalidation
             Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
             <code>end()</code>).
        \par Complexity
             Linear (in the <code>std::distance(first, last)</code>).
        \sa <code>operator=</code>, <code>\link assign(size_type, param_value_type)
            assign(size_type, const_reference)\endlink</code>,
            <code>\link assign(capacity_type, size_type, param_value_type)
            assign(capacity_type, size_type, const_reference)\endlink</code>,
            <code>assign(capacity_type, InputIterator, InputIterator)</code>
    */
    template <class InputIterator>
    void assign(InputIterator first, InputIterator last) {
        assign(first, last, is_integral<InputIterator>());
    }

    //! Assign a copy of the range into the <code>circular_buffer</code> specifying the capacity.
    /*!
        The capacity of the <code>circular_buffer</code> will be set to the specified value and the content of the
        <code>circular_buffer</code> will be removed and replaced with copies of elements from the specified range.
        \pre Valid range <code>[first, last)</code>.<br>
             <code>first</code> and <code>last</code> have to meet the requirements of
             <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
        \post <code>capacity() == capacity \&\& size() \<= std::distance(first, last) \&\&
             (*this)[0]== *(last - capacity) \&\& (*this)[1] == *(last - capacity + 1) \&\& ... \&\&
             (*this)[capacity - 1] == *(last - 1)</code><br><br>
             If the number of items to be copied from the range <code>[first, last)</code> is greater than the
             specified <code>capacity</code> then only elements from the range <code>[last - capacity, last)</code>
             will be copied.
        \param capacity The new capacity.
        \param first The beginning of the range to be copied.
        \param last The end of the range to be copied.
        \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
                used).
        \throws Whatever <code>T::T(const T&)</code> throws.
        \par Exception Safety
             Basic.
        \par Iterator Invalidation
             Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
             <code>end()</code>).
        \par Complexity
             Linear (in <code>std::distance(first, last)</code>; in
             <code>min[capacity, std::distance(first, last)]</code> if the <code>InputIterator</code> is a
             <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>).
        \sa <code>operator=</code>, <code>\link assign(size_type, param_value_type)
            assign(size_type, const_reference)\endlink</code>,
            <code>\link assign(capacity_type, size_type, param_value_type)
            assign(capacity_type, size_type, const_reference)\endlink</code>,
            <code>assign(InputIterator, InputIterator)</code>
    */
    template <class InputIterator>
    void assign(capacity_type capacity, InputIterator first, InputIterator last) {
        assign(capacity, first, last, is_integral<InputIterator>());
    }

    //! Swap the contents of two <code>circular_buffer</code>s.
    /*!
        \post <code>this</code> contains elements of <code>cb</code> and vice versa; the capacity of <code>this</code>
              equals to the capacity of <code>cb</code> and vice versa.
        \param cb The <code>circular_buffer</code> whose content will be swapped.
        \throws Nothing.
        \par Exception Safety
             No-throw.
        \par Iterator Invalidation
             Invalidates all iterators of both <code>circular_buffer</code>s. (On the other hand the iterators still
             point to the same elements but within another container. If you want to rely on this feature you have to
             turn the <a href="#debug">Debug Support</a> off otherwise an assertion will report an error if such
             invalidated iterator is used.)
        \par Complexity
             Constant (in the size of the <code>circular_buffer</code>).
        \sa <code>swap(circular_buffer<T, Alloc>&, circular_buffer<T, Alloc>&)</code>
    */
    void swap(circular_buffer<T, Alloc>& cb) {
        swap_allocator(cb, is_stateless<allocator_type>());
        std::swap(m_buff, cb.m_buff);
        std::swap(m_end, cb.m_end);
        std::swap(m_first, cb.m_first);
        std::swap(m_last, cb.m_last);
        std::swap(m_size, cb.m_size);
#if BOOST_CB_ENABLE_DEBUG
        invalidate_all_iterators();
        cb.invalidate_all_iterators();
#endif
    }

// push and pop

    //! Insert a new element at the end of the <code>circular_buffer</code>.
    /*!
        \post if <code>capacity() > 0</code> then <code>back() == item</code><br>
              If the <code>circular_buffer</code> is full, the first element will be removed. If the capacity is
              <code>0</code>, nothing will be inserted.
        \param item The element to be inserted.
        \throws Whatever <code>T::T(const T&)</code> throws.
        \par Exception Safety
             Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
        \par Iterator Invalidation
             Does not invalidate any iterators with the exception of iterators pointing to the overwritten element.
        \par Complexity
             Constant (in the size of the <code>circular_buffer</code>).
        \sa <code>\link push_front() push_front(const_reference)\endlink</code>,
            <code>pop_back()</code>, <code>pop_front()</code>
    */
    void push_back(param_value_type item = value_type()) {
        if (full()) {
            if (empty())
                return;
            replace(m_last, item);
            increment(m_last);
            m_first = m_last;
        } else {
            m_alloc.construct(m_last, item);
            increment(m_last);
            ++m_size;
        }
    }

    //! Insert a new element at the beginning of the <code>circular_buffer</code>.
    /*!
        \post if <code>capacity() > 0</code> then <code>front() == item</code><br>
              If the <code>circular_buffer</code> is full, the last element will be removed. If the capacity is
              <code>0</code>, nothing will be inserted.
        \param item The element to be inserted.
        \throws Whatever <code>T::T(const T&)</code> throws.
        \par Exception Safety
             Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
        \par Iterator Invalidation
             Does not invalidate any iterators with the exception of iterators pointing to the overwritten element.
        \par Complexity
             Constant (in the size of the <code>circular_buffer</code>).
        \sa <code>\link push_back() push_back(const_reference)\endlink</code>,
            <code>pop_back()</code>, <code>pop_front()</code>
    */
    void push_front(param_value_type item = value_type()) {
        BOOST_TRY {
            if (full()) {
                if (empty())
                    return;
                decrement(m_first);
                replace(m_first, item);
                m_last = m_first;
            } else {
                decrement(m_first);
                m_alloc.construct(m_first, item);
                ++m_size;
            }
        } BOOST_CATCH(...) {
            increment(m_first);
            BOOST_RETHROW
        }
        BOOST_CATCH_END
    }

    //! Remove the last element from the <code>circular_buffer</code>.
    /*!
        \pre <code>!empty()</code>
        \post The last element is removed from the <code>circular_buffer</code>.
        \throws Nothing.
        \par Exception Safety
             No-throw.
        \par Iterator Invalidation
             Invalidates only iterators pointing to the removed element.
        \par Complexity
             Constant (in the size of the <code>circular_buffer</code>).
        \sa <code>pop_front()</code>, <code>\link push_back() push_back(const_reference)\endlink</code>,
            <code>\link push_front() push_front(const_reference)\endlink</code>
    */
    void pop_back() {
        BOOST_CB_ASSERT(!empty()); // check for empty buffer (back element not available)
        decrement(m_last);
        destroy_item(m_last);
        --m_size;
    }

    //! Remove the first element from the <code>circular_buffer</code>.
    /*!
        \pre <code>!empty()</code>
        \post The first element is removed from the <code>circular_buffer</code>.
        \throws Nothing.
        \par Exception Safety
             No-throw.
        \par Iterator Invalidation
             Invalidates only iterators pointing to the removed element.
        \par Complexity
             Constant (in the size of the <code>circular_buffer</code>).
        \sa <code>pop_back()</code>, <code>\link push_back() push_back(const_reference)\endlink</code>,
            <code>\link push_front() push_front(const_reference)\endlink</code>
    */
    void pop_front() {
        BOOST_CB_ASSERT(!empty()); // check for empty buffer (front element not available)
        destroy_item(m_first);
        increment(m_first);
        --m_size;
    }

public:
// Insert

    //! Insert an element at the specified position.
    /*!
        \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.
        \post The <code>item</code> will be inserted at the position <code>pos</code>.<br>
              If the <code>circular_buffer</code> is full, the first element will be overwritten. If the
              <code>circular_buffer</code> is full and the <code>pos</code> points to <code>begin()</code>, then the
              <code>item</code> will not be inserted. If the capacity is <code>0</code>, nothing will be inserted.
        \param pos An iterator specifying the position where the <code>item</code> will be inserted.
        \param item The element to be inserted.
        \return Iterator to the inserted element or <code>begin()</code> if the <code>item</code> is not inserted. (See
                the <i>Effect</i>.)
        \throws Whatever <code>T::T(const T&)</code> throws.
        \throws Whatever <code>T::operator = (const T&)</code> throws.
        \par Exception Safety
             Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
        \par Iterator Invalidation
             Invalidates iterators pointing to the elements at the insertion point (including <code>pos</code>) and
             iterators behind the insertion point (towards the end; except iterators equal to <code>end()</code>). It
             also invalidates iterators pointing to the overwritten element.
        \par Complexity
             Linear (in <code>std::distance(pos, end())</code>).
        \sa <code>\link insert(iterator, size_type, param_value_type)
            insert(iterator, size_type, value_type)\endlink</code>,
            <code>insert(iterator, InputIterator, InputIterator)</code>,
            <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>,
            <code>\link rinsert(iterator, size_type, param_value_type)
            rinsert(iterator, size_type, value_type)\endlink</code>,
            <code>rinsert(iterator, InputIterator, InputIterator)</code>
    */
    iterator insert(iterator pos, param_value_type item = value_type()) {
        BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator
        iterator b = begin();
        if (full() && pos == b)
            return b;
        return insert_item(pos, item);
    }

    //! Insert <code>n</code> copies of the <code>item</code> at the specified position.
    /*!
        \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.
        \post The number of <code>min[n, (pos - begin()) + reserve()]</code> elements will be inserted at the position
              <code>pos</code>.<br>The number of <code>min[pos - begin(), max[0, n - reserve()]]</code> elements will
              be overwritten at the beginning of the <code>circular_buffer</code>.<br>(See <i>Example</i> for the
              explanation.)
        \param pos An iterator specifying the position where the <code>item</code>s will be inserted.
        \param n The number of <code>item</code>s the to be inserted.
        \param item The element whose copies will be inserted.
        \throws Whatever <code>T::T(const T&)</code> throws.
        \throws Whatever <code>T::operator = (const T&)</code> throws.
        \par Exception Safety
             Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything.
        \par Iterator Invalidation
             Invalidates iterators pointing to the elements at the insertion point (including <code>pos</code>) and
             iterators behind the insertion point (towards the end; except iterators equal to <code>end()</code>). It
             also invalidates iterators pointing to the overwritten elements.
        \par Complexity
             Linear (in <code>min[capacity(), std::distance(pos, end()) + n]</code>).
        \par Example
             Consider a <code>circular_buffer</code> with the capacity of 6 and the size of 4. Its internal buffer may
             look like the one below.<br><br>
             <code>|1|2|3|4| | |</code><br>
             <code>p ---^</code><br><br>After inserting 5 elements at the position <code>p</code>:<br><br>
             <code>insert(p, (size_t)5, 0);</code><br><br>actually only 4 elements get inserted and elements
             <code>1</code> and <code>2</code> are overwritten. This is due to the fact the insert operation preserves
             the capacity. After insertion the internal buffer looks like this:<br><br><code>|0|0|0|0|3|4|</code><br>
             <br>For comparison if the capacity would not be preserved the internal buffer would then result in
             <code>|1|2|0|0|0|0|0|3|4|</code>.
        \sa <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>,
            <code>insert(iterator, InputIterator, InputIterator)</code>,
            <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>,
            <code>\link rinsert(iterator, size_type, param_value_type)
            rinsert(iterator, size_type, value_type)\endlink</code>,
            <code>rinsert(iterator, InputIterator, InputIterator)</code>
    */
    void insert(iterator pos, size_type n, param_value_type item) {
        BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator
        if (n == 0)
            return;
        size_type copy = capacity() - (end() - pos);
        if (copy == 0)
            return;
        if (n > copy)
            n = copy;
        insert_n(pos, n, cb_details::item_wrapper<const_pointer, param_value_type>(item));
    }

    //! Insert the range <code>[first, last)</code> at the specified position.
    /*!
        \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.<br>
             Valid range <code>[first, last)</code> where <code>first</code> and <code>last</code> meet the
             requirements of an <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
        \post Elements from the range
              <code>[first + max[0, distance(first, last) - (pos - begin()) - reserve()], last)</code> will be
              inserted at the position <code>pos</code>.<br>The number of <code>min[pos - begin(), max[0,
              distance(first, last) - reserve()]]</code> elements will be overwritten at the beginning of the
              <code>circular_buffer</code>.<br>(See <i>Example</i> for the explanation.)
        \param pos An iterator specifying the position where the range will be inserted.
        \param first The beginning of the range to be inserted.
        \param last The end of the range to be inserted.
        \throws Whatever <code>T::T(const T&)</code> throws.
        \throws Whatever <code>T::operator = (const T&)</code> throws.
        \par Exception Safety
             Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything.
        \par Iterator Invalidation
             Invalidates iterators pointing to the elements at the insertion point (including <code>pos</code>) and
             iterators behind the insertion point (towards the end; except iterators equal to <code>end()</code>). It
             also invalidates iterators pointing to the overwritten elements.
        \par Complexity
             Linear (in <code>[std::distance(pos, end()) + std::distance(first, last)]</code>; in
             <code>min[capacity(), std::distance(pos, end()) + std::distance(first, last)]</code> if the
             <code>InputIterator</code> is a
             <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>).
        \par Example
             Consider a <code>circular_buffer</code> with the capacity of 6 and the size of 4. Its internal buffer may
             look like the one below.<br><br>
             <code>|1|2|3|4| | |</code><br>
             <code>p ---^</code><br><br>After inserting a range of elements at the position <code>p</code>:<br><br>
             <code>int array[] = { 5, 6, 7, 8, 9 };</code><br><code>insert(p, array, array + 5);</code><br><br>
             actually only elements <code>6</code>, <code>7</code>, <code>8</code> and <code>9</code> from the
             specified range get inserted and elements <code>1</code> and <code>2</code> are overwritten. This is due
             to the fact the insert operation preserves the capacity. After insertion the internal buffer looks like
             this:<br><br><code>|6|7|8|9|3|4|</code><br><br>For comparison if the capacity would not be preserved the
             internal buffer would then result in <code>|1|2|5|6|7|8|9|3|4|</code>.
        \sa <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>,
            <code>\link insert(iterator, size_type, param_value_type)
            insert(iterator, size_type, value_type)\endlink</code>, <code>\link rinsert(iterator, param_value_type)
            rinsert(iterator, value_type)\endlink</code>, <code>\link rinsert(iterator, size_type, param_value_type)
            rinsert(iterator, size_type, value_type)\endlink</code>,
            <code>rinsert(iterator, InputIterator, InputIterator)</code>
    */
    template <class InputIterator>
    void insert(iterator pos, InputIterator first, InputIterator last) {
        BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator
        insert(pos, first, last, is_integral<InputIterator>());
    }

    //! Insert an element before the specified position.
    /*!
        \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.
        \post The <code>item</code> will be inserted before the position <code>pos</code>.<br>
              If the <code>circular_buffer</code> is full, the last element will be overwritten. If the
              <code>circular_buffer</code> is full and the <code>pos</code> points to <code>end()</code>, then the
              <code>item</code> will not be inserted. If the capacity is <code>0</code>, nothing will be inserted.
        \param pos An iterator specifying the position before which the <code>item</code> will be inserted.
        \param item The element to be inserted.
        \return Iterator to the inserted element or <code>end()</code> if the <code>item</code> is not inserted. (See
                the <i>Effect</i>.)
        \throws Whatever <code>T::T(const T&)</code> throws.
        \throws Whatever <code>T::operator = (const T&)</code> throws.
        \par Exception Safety
             Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything.
        \par Iterator Invalidation
             Invalidates iterators pointing to the elements before the insertion point (towards the beginning and
             excluding <code>pos</code>). It also invalidates iterators pointing to the overwritten element.
        \par Complexity
             Linear (in <code>std::distance(begin(), pos)</code>).
        \sa <code>\link rinsert(iterator, size_type, param_value_type)
            rinsert(iterator, size_type, value_type)\endlink</code>,
            <code>rinsert(iterator, InputIterator, InputIterator)</code>,
            <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>,
            <code>\link insert(iterator, size_type, param_value_type)
            insert(iterator, size_type, value_type)\endlink</code>,
            <code>insert(iterator, InputIterator, InputIterator)</code>
    */
    iterator rinsert(iterator pos, param_value_type item = value_type()) {
        BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator
        if (full() && pos.m_it == 0)
            return end();
        if (pos == begin()) {
            BOOST_TRY {
                decrement(m_first);
                construct_or_replace(!full(), m_first, item);
            } BOOST_CATCH(...) {
                increment(m_first);
                BOOST_RETHROW
            }
            BOOST_CATCH_END
            pos.m_it = m_first;
        } else {
            pointer src = m_first;
            pointer dest = m_first;
            decrement(dest);
            pos.m_it = map_pointer(pos.m_it);
            bool construct = !full();
            BOOST_TRY {
                while (src != pos.m_it) {
                    construct_or_replace(construct, dest, *src);
                    increment(src);
                    increment(dest);
                    construct = false;
                }
                decrement(pos.m_it);
                replace(pos.m_it, item);
            } BOOST_CATCH(...) {
                if (!construct && !full()) {
                    decrement(m_first);
                    ++m_size;
                }
                BOOST_RETHROW
            }
            BOOST_CATCH_END
            decrement(m_first);
        }
        if (full())
            m_last = m_first;
        else
            ++m_size;
        return iterator(this, pos.m_it);
    }

    //! Insert <code>n</code> copies of the <code>item</code> before the specified position.
    /*!
        \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.
        \post The number of <code>min[n, (end() - pos) + reserve()]</code> elements will be inserted before the
              position <code>pos</code>.<br>The number of <code>min[end() - pos, max[0, n - reserve()]]</code> elements
              will be overwritten at the end of the <code>circular_buffer</code>.<br>(See <i>Example</i> for the
              explanation.)
        \param pos An iterator specifying the position where the <code>item</code>s will be inserted.
        \param n The number of <code>item</code>s the to be inserted.
        \param item The element whose copies will be inserted.
        \throws Whatever <code>T::T(const T&)</code> throws.
        \throws Whatever <code>T::operator = (const T&)</code> throws.
        \par Exception Safety
             Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything.
        \par Iterator Invalidation
             Invalidates iterators pointing to the elements before the insertion point (towards the beginning and
             excluding <code>pos</code>). It also invalidates iterators pointing to the overwritten elements.
        \par Complexity
             Linear (in <code>min[capacity(), std::distance(begin(), pos) + n]</code>).
        \par Example
             Consider a <code>circular_buffer</code> with the capacity of 6 and the size of 4. Its internal buffer may
             look like the one below.<br><br>
             <code>|1|2|3|4| | |</code><br>
             <code>p ---^</code><br><br>After inserting 5 elements before the position <code>p</code>:<br><br>
             <code>rinsert(p, (size_t)5, 0);</code><br><br>actually only 4 elements get inserted and elements
             <code>3</code> and <code>4</code> are overwritten. This is due to the fact the rinsert operation preserves
             the capacity. After insertion the internal buffer looks like this:<br><br><code>|1|2|0|0|0|0|</code><br>
             <br>For comparison if the capacity would not be preserved the internal buffer would then result in
             <code>|1|2|0|0|0|0|0|3|4|</code>.
        \sa <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>,
            <code>rinsert(iterator, InputIterator, InputIterator)</code>,
            <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>,
            <code>\link insert(iterator, size_type, param_value_type)
            insert(iterator, size_type, value_type)\endlink</code>,
            <code>insert(iterator, InputIterator, InputIterator)</code>
    */
    void rinsert(iterator pos, size_type n, param_value_type item) {
        BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator
        rinsert_n(pos, n, cb_details::item_wrapper<const_pointer, param_value_type>(item));
    }

    //! Insert the range <code>[first, last)</code> before the specified position.
    /*!
        \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.<br>
             Valid range <code>[first, last)</code> where <code>first</code> and <code>last</code> meet the
             requirements of an <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
        \post Elements from the range
              <code>[first, last - max[0, distance(first, last) - (end() - pos) - reserve()])</code> will be inserted
              before the position <code>pos</code>.<br>The number of <code>min[end() - pos, max[0,
              distance(first, last) - reserve()]]</code> elements will be overwritten at the end of the
              <code>circular_buffer</code>.<br>(See <i>Example</i> for the explanation.)
        \param pos An iterator specifying the position where the range will be inserted.
        \param first The beginning of the range to be inserted.
        \param last The end of the range to be inserted.
        \throws Whatever <code>T::T(const T&)</code> throws.
        \throws Whatever <code>T::operator = (const T&)</code> throws.
        \par Exception Safety
             Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything.
        \par Iterator Invalidation
             Invalidates iterators pointing to the elements before the insertion point (towards the beginning and
             excluding <code>pos</code>). It also invalidates iterators pointing to the overwritten elements.
        \par Complexity
             Linear (in <code>[std::distance(begin(), pos) + std::distance(first, last)]</code>; in
             <code>min[capacity(), std::distance(begin(), pos) + std::distance(first, last)]</code> if the
             <code>InputIterator</code> is a
             <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>).
        \par Example
             Consider a <code>circular_buffer</code> with the capacity of 6 and the size of 4. Its internal buffer may
             look like the one below.<br><br>
             <code>|1|2|3|4| | |</code><br>
             <code>p ---^</code><br><br>After inserting a range of elements before the position <code>p</code>:<br><br>
             <code>int array[] = { 5, 6, 7, 8, 9 };</code><br><code>insert(p, array, array + 5);</code><br><br>
             actually only elements <code>5</code>, <code>6</code>, <code>7</code> and <code>8</code> from the
             specified range get inserted and elements <code>3</code> and <code>4</code> are overwritten. This is due
             to the fact the rinsert operation preserves the capacity. After insertion the internal buffer looks like
             this:<br><br><code>|1|2|5|6|7|8|</code><br><br>For comparison if the capacity would not be preserved the
             internal buffer would then result in <code>|1|2|5|6|7|8|9|3|4|</code>.
        \sa <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>,
            <code>\link rinsert(iterator, size_type, param_value_type)
            rinsert(iterator, size_type, value_type)\endlink</code>, <code>\link insert(iterator, param_value_type)
            insert(iterator, value_type)\endlink</code>, <code>\link insert(iterator, size_type, param_value_type)
            insert(iterator, size_type, value_type)\endlink</code>,
            <code>insert(iterator, InputIterator, InputIterator)</code>
    */
    template <class InputIterator>
    void rinsert(iterator pos, InputIterator first, InputIterator last) {
        BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator
        rinsert(pos, first, last, is_integral<InputIterator>());
    }

// Erase

    //! Remove an element at the specified position.
    /*!
        \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> (but not an
             <code>end()</code>).
        \post The element at the position <code>pos</code> is removed.
        \param pos An iterator pointing at the element to be removed.
        \return Iterator to the first element remaining beyond the removed element or <code>end()</code> if no such
                element exists.
        \throws Whatever <code>T::operator = (const T&)</code> throws.
        \par Exception Safety
             Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
        \par Iterator Invalidation
             Invalidates iterators pointing to the erased element and iterators pointing to the elements behind
             the erased element (towards the end; except iterators equal to <code>end()</code>).
        \par Complexity
             Linear (in <code>std::distance(pos, end())</code>).
        \sa <code>erase(iterator, iterator)</code>, <code>rerase(iterator)</code>,
            <code>rerase(iterator, iterator)</code>, <code>clear()</code>
    */
    iterator erase(iterator pos) {
        BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator
        BOOST_CB_ASSERT(pos.m_it != 0);      // check for iterator pointing to end()
        pointer next = pos.m_it;
        increment(next);
        for (pointer p = pos.m_it; next != m_last; p = next, increment(next))
            replace(p, *next);
        decrement(m_last);
        destroy_item(m_last);
        --m_size;
#if BOOST_CB_ENABLE_DEBUG
        return m_last == pos.m_it ? end() : iterator(this, pos.m_it);
#else
        return m_last == pos.m_it ? end() : pos;
#endif
    }

    //! Erase the range <code>[first, last)</code>.
    /*!
        \pre Valid range <code>[first, last)</code>.
        \post The elements from the range <code>[first, last)</code> are removed. (If <code>first == last</code>
              nothing is removed.)
        \param first The beginning of the range to be removed.
        \param last The end of the range to be removed.
        \return Iterator to the first element remaining beyond the removed elements or <code>end()</code> if no such
                element exists.
        \throws Whatever <code>T::operator = (const T&)</code> throws.
        \par Exception Safety
             Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
        \par Iterator Invalidation
             Invalidates iterators pointing to the erased elements and iterators pointing to the elements behind
             the erased range (towards the end; except iterators equal to <code>end()</code>).
        \par Complexity
             Linear (in <code>std::distance(first, end())</code>).
        \sa <code>erase(iterator)</code>, <code>rerase(iterator)</code>, <code>rerase(iterator, iterator)</code>,
            <code>clear()</code>
    */
    iterator erase(iterator first, iterator last) {
        BOOST_CB_ASSERT(first.is_valid(this)); // check for uninitialized or invalidated iterator
        BOOST_CB_ASSERT(last.is_valid(this));  // check for uninitialized or invalidated iterator
        BOOST_CB_ASSERT(first <= last);        // check for wrong range
        if (first == last)
            return first;
        pointer p = first.m_it;
        while (last.m_it != 0)
            replace((first++).m_it, *last++);
        do {
            decrement(m_last);
            destroy_item(m_last);
            --m_size;
        } while(m_last != first.m_it);
        return m_last == p ? end() : iterator(this, p);
    }

    //! Remove an element at the specified position.
    /*!
        \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> (but not an
             <code>end()</code>).
        \post The element at the position <code>pos</code> is removed.
        \param pos An iterator pointing at the element to be removed.
        \return Iterator to the first element remaining in front of the removed element or <code>begin()</code> if no
                such element exists.
        \throws Whatever <code>T::operator = (const T&)</code> throws.
        \par Exception Safety
             Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
        \par Iterator Invalidation
             Invalidates iterators pointing to the erased element and iterators pointing to the elements in front of
             the erased element (towards the beginning).
        \par Complexity
             Linear (in <code>std::distance(begin(), pos)</code>).
        \note This method is symetric to the <code>erase(iterator)</code> method and is more effective than
              <code>erase(iterator)</code> if the iterator <code>pos</code> is close to the beginning of the
              <code>circular_buffer</code>. (See the <i>Complexity</i>.)
        \sa <code>erase(iterator)</code>, <code>erase(iterator, iterator)</code>,
            <code>rerase(iterator, iterator)</code>, <code>clear()</code>
    */
    iterator rerase(iterator pos) {
        BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator
        BOOST_CB_ASSERT(pos.m_it != 0);      // check for iterator pointing to end()
        pointer prev = pos.m_it;
        pointer p = prev;
        for (decrement(prev); p != m_first; p = prev, decrement(prev))
            replace(p, *prev);
        destroy_item(m_first);
        increment(m_first);
        --m_size;
#if BOOST_CB_ENABLE_DEBUG
        return p == pos.m_it ? begin() : iterator(this, pos.m_it);
#else
        return p == pos.m_it ? begin() : pos;
#endif
    }

    //! Erase the range <code>[first, last)</code>.
    /*!
        \pre Valid range <code>[first, last)</code>.
        \post The elements from the range <code>[first, last)</code> are removed. (If <code>first == last</code>
              nothing is removed.)
        \param first The beginning of the range to be removed.
        \param last The end of the range to be removed.
        \return Iterator to the first element remaining in front of the removed elements or <code>begin()</code> if no
                such element exists.
        \throws Whatever <code>T::operator = (const T&)</code> throws.
        \par Exception Safety
             Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
        \par Iterator Invalidation
             Invalidates iterators pointing to the erased elements and iterators pointing to the elements in front of
             the erased range (towards the beginning).
        \par Complexity
             Linear (in <code>std::distance(begin(), last)</code>).
        \note This method is symetric to the <code>erase(iterator, iterator)</code> method and is more effective than
              <code>erase(iterator, iterator)</code> if <code>std::distance(begin(), first)</code> is lower that
              <code>std::distance(last, end())</code>.
        \sa <code>erase(iterator)</code>, <code>erase(iterator, iterator)</code>, <code>rerase(iterator)</code>,
            <code>clear()</code>
    */
    iterator rerase(iterator first, iterator last) {
        BOOST_CB_ASSERT(first.is_valid(this)); // check for uninitialized or invalidated iterator
        BOOST_CB_ASSERT(last.is_valid(this));  // check for uninitialized or invalidated iterator
        BOOST_CB_ASSERT(first <= last);        // check for wrong range
        if (first == last)
            return first;
        pointer p = map_pointer(last.m_it);
        last.m_it = p;
        while (first.m_it != m_first) {
            decrement(first.m_it);
            decrement(p);
            replace(p, *first.m_it);
        }
        do {
            destroy_item(m_first);
            increment(m_first);
            --m_size;
        } while(m_first != p);
        if (m_first == last.m_it)
            return begin();
        decrement(last.m_it);
        return iterator(this, last.m_it);
    }

    //! Remove all stored elements from the <code>circular_buffer</code>.
    /*!
        \post <code>size() == 0</code>
        \throws Nothing.
        \par Exception Safety
             No-throw.
        \par Iterator Invalidation
             Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
             <code>end()</code>).
        \par Complexity
             Linear (in the size of the <code>circular_buffer</code>).
        \sa <code>~circular_buffer()</code>, <code>erase(iterator)</code>, <code>erase(iterator, iterator)</code>,
            <code>rerase(iterator)</code>, <code>rerase(iterator, iterator)</code>
    */
    void clear() {
        destroy_content();
        m_size = 0;
    }

private:
// Helper methods

    //! Check if the <code>index</code> is valid.
    void check_position(size_type index) const {
        if (index >= size())
            throw_exception(std::out_of_range("circular_buffer"));
    }

    //! Increment the pointer.
    template <class Pointer>
    void increment(Pointer& p) const {
        if (++p == m_end)
            p = m_buff;
    }

    //! Decrement the pointer.
    template <class Pointer>
    void decrement(Pointer& p) const {
        if (p == m_buff)
            p = m_end;
        --p;
    }

    //! Add <code>n</code> to the pointer.
    template <class Pointer>
    Pointer add(Pointer p, difference_type n) const {
        return p + (n < (m_end - p) ? n : n - capacity());
    }

    //! Subtract <code>n</code> from the pointer.
    template <class Pointer>
    Pointer sub(Pointer p, difference_type n) const {
        return p - (n > (p - m_buff) ? n - capacity() : n);
    }

    //! Map the null pointer to virtual end of circular buffer.
    pointer map_pointer(pointer p) const { return p == 0 ? m_last : p; }

    //! Allocate memory.
    pointer allocate(size_type n) {
        if (n > max_size())
            throw_exception(std::length_error("circular_buffer"));
#if BOOST_CB_ENABLE_DEBUG
        pointer p = (n == 0) ? 0 : m_alloc.allocate(n, 0);
        ::memset(p, cb_details::UNINITIALIZED, sizeof(value_type) * n);
        return p;
#else
        return (n == 0) ? 0 : m_alloc.allocate(n, 0);
#endif
    }

    //! Deallocate memory.
    void deallocate(pointer p, size_type n) {
        if (p != 0)
            m_alloc.deallocate(p, n);
    }

    //! Does the pointer point to the uninitialized memory?
    bool is_uninitialized(const_pointer p) const {
        return p >= m_last && (m_first < m_last || p < m_first);
    }

    //! Replace an element.
    void replace(pointer pos, param_value_type item) {
        *pos = item;
#if BOOST_CB_ENABLE_DEBUG
        invalidate_iterators(iterator(this, pos));
#endif
    }

    //! Construct or replace an element.
    /*!
        <code>construct</code> has to be set to <code>true</code> if and only if
        <code>pos</code> points to an uninitialized memory.
    */
    void construct_or_replace(bool construct, pointer pos, param_value_type item) {
        if (construct)
            m_alloc.construct(pos, item);
        else
            replace(pos, item);
    }

    //! Destroy an item.
    void destroy_item(pointer p) {
        m_alloc.destroy(p);
#if BOOST_CB_ENABLE_DEBUG
        invalidate_iterators(iterator(this, p));
        ::memset(p, cb_details::UNINITIALIZED, sizeof(value_type));
#endif
    }

    //! Destroy an item only if it has been constructed.
    void destroy_if_constructed(pointer pos) {
        if (is_uninitialized(pos))
            destroy_item(pos);
    }

    //! Destroy the whole content of the circular buffer.
    void destroy_content() {
        for (size_type ii = 0; ii < size(); ++ii, increment(m_first))
            destroy_item(m_first);
    }

    //! Destroy content and free allocated memory.
    void destroy() {
        destroy_content();
        deallocate(m_buff, capacity());
#if BOOST_CB_ENABLE_DEBUG
        m_buff = 0;
        m_first = 0;
        m_last = 0;
        m_end = 0;
#endif
    }

    //! Initialize the circular buffer.
    void initialize(capacity_type capacity) {
        m_first = m_last = m_buff = allocate(capacity);
        m_end = m_buff + capacity;
    }

    //! Initialize the circular buffer.
    void initialize(capacity_type capacity, param_value_type item) {
        initialize(capacity);
        BOOST_TRY {
            cb_details::uninitialized_fill_n_with_alloc(m_buff, size(), item, m_alloc);
        } BOOST_CATCH(...) {
            deallocate(m_buff, size());
            BOOST_RETHROW
        }
        BOOST_CATCH_END
    }

    //! Specialized initialize method.
    template <class IntegralType>
    void initialize(IntegralType n, IntegralType item, const true_type&) {
        m_size = static_cast<size_type>(n);
        initialize(size(), item);
    }

    //! Specialized initialize method.
    template <class Iterator>
    void initialize(Iterator first, Iterator last, const false_type&) {
        BOOST_CB_IS_CONVERTIBLE(Iterator, value_type); // check for invalid iterator type
#if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x581))
        initialize(first, last, BOOST_ITERATOR_CATEGORY<Iterator>::type());
#else
        initialize(first, last, BOOST_DEDUCED_TYPENAME BOOST_ITERATOR_CATEGORY<Iterator>::type());
#endif
    }

    //! Specialized initialize method.
    template <class InputIterator>
    void initialize(InputIterator first, InputIterator last, const std::input_iterator_tag&) {
        BOOST_CB_ASSERT_TEMPLATED_ITERATOR_CONSTRUCTORS // check if the STL provides templated iterator constructors
                                                        // for containers
        std::deque<value_type, allocator_type> tmp(first, last, m_alloc);
        size_type distance = tmp.size();
        initialize(distance, tmp.begin(), tmp.end(), distance);
    }

    //! Specialized initialize method.
    template <class ForwardIterator>
    void initialize(ForwardIterator first, ForwardIterator last, const std::forward_iterator_tag&) {
        BOOST_CB_ASSERT(std::distance(first, last) >= 0); // check for wrong range
        size_type distance = std::distance(first, last);
        initialize(distance, first, last, distance);
    }

    //! Specialized initialize method.
    template <class IntegralType>
    void initialize(capacity_type capacity, IntegralType n, IntegralType item, const true_type&) {
        BOOST_CB_ASSERT(capacity >= static_cast<size_type>(n)); // check for capacity lower than n
        m_size = static_cast<size_type>(n);
        initialize(capacity, item);
    }

    //! Specialized initialize method.
    template <class Iterator>
    void initialize(capacity_type capacity, Iterator first, Iterator last, const false_type&) {
        BOOST_CB_IS_CONVERTIBLE(Iterator, value_type); // check for invalid iterator type
#if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x581))
        initialize(capacity, first, last, BOOST_ITERATOR_CATEGORY<Iterator>::type());
#else
        initialize(capacity, first, last, BOOST_DEDUCED_TYPENAME BOOST_ITERATOR_CATEGORY<Iterator>::type());
#endif
    }

    //! Specialized initialize method.
    template <class InputIterator>
    void initialize(capacity_type capacity,
        InputIterator first,
        InputIterator last,
        const std::input_iterator_tag&) {
        initialize(capacity);
        m_size = 0;
        if (capacity == 0)
            return;
        while (first != last && !full()) {
            m_alloc.construct(m_last, *first++);
            increment(m_last);
            ++m_size;
        }
        while (first != last) {
            replace(m_last, *first++);
            increment(m_last);
            m_first = m_last;
        }
    }

    //! Specialized initialize method.
    template <class ForwardIterator>
    void initialize(capacity_type capacity,
        ForwardIterator first,
        ForwardIterator last,
        const std::forward_iterator_tag&) {
        BOOST_CB_ASSERT(std::distance(first, last) >= 0); // check for wrong range
        initialize(capacity, first, last, std::distance(first, last));
    }

    //! Helper initialize method.
    template <class ForwardIterator>
    void initialize(capacity_type capacity,
        ForwardIterator first,
        ForwardIterator last,
        size_type distance) {
        initialize(capacity);
        if (distance > capacity) {
            std::advance(first, distance - capacity);
            m_size = capacity;
        } else {
            m_size = distance;
            if (distance != capacity)
                m_last = m_buff + size();
        }
        BOOST_TRY {
            cb_details::uninitialized_copy_with_alloc(first, last, m_buff, m_alloc);
        } BOOST_CATCH(...) {
            deallocate(m_buff, capacity);
            BOOST_RETHROW
        }
        BOOST_CATCH_END
    }

    //! Reset the circular buffer.
    void reset(pointer buff, pointer last, capacity_type new_capacity) {
        destroy();
        m_size = last - buff;
        m_first = m_buff = buff;
        m_end = m_buff + new_capacity;
        m_last = last == m_end ? m_buff : last;
    }

    //! Specialized method for swapping the allocator.
    void swap_allocator(circular_buffer<T, Alloc>& cb, const true_type&) {
        // Swap is not needed because allocators have no state.
    }

    //! Specialized method for swapping the allocator.
    void swap_allocator(circular_buffer<T, Alloc>& cb, const false_type&) {
        std::swap(m_alloc, cb.m_alloc);
    }

    //! Specialized assign method.
    template <class IntegralType>
    void assign(IntegralType n, IntegralType item, const true_type&) {
        assign(static_cast<size_type>(n), static_cast<value_type>(item));
    }

    //! Specialized assign method.
    template <class Iterator>
    void assign(Iterator first, Iterator last, const false_type&) {
        BOOST_CB_IS_CONVERTIBLE(Iterator, value_type); // check for invalid iterator type
#if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x581))
        assign(first, last, BOOST_ITERATOR_CATEGORY<Iterator>::type());
#else
        assign(first, last, BOOST_DEDUCED_TYPENAME BOOST_ITERATOR_CATEGORY<Iterator>::type());
#endif
    }

    //! Specialized assign method.
    template <class InputIterator>
    void assign(InputIterator first, InputIterator last, const std::input_iterator_tag&) {
        BOOST_CB_ASSERT_TEMPLATED_ITERATOR_CONSTRUCTORS // check if the STL provides templated iterator constructors
                                                        // for containers
        std::deque<value_type, allocator_type> tmp(first, last, m_alloc);
        size_type distance = tmp.size();
        assign_n(distance, distance,
            cb_details::assign_range<BOOST_DEDUCED_TYPENAME std::deque<value_type, allocator_type>::iterator,
                allocator_type>(tmp.begin(), tmp.end(), m_alloc));
    }

    //! Specialized assign method.
    template <class ForwardIterator>
    void assign(ForwardIterator first, ForwardIterator last, const std::forward_iterator_tag&) {
        BOOST_CB_ASSERT(std::distance(first, last) >= 0); // check for wrong range
        size_type distance = std::distance(first, last);
        assign_n(distance, distance, cb_details::assign_range<ForwardIterator, allocator_type>(first, last, m_alloc));
    }

    //! Specialized assign method.
    template <class IntegralType>
    void assign(capacity_type new_capacity, IntegralType n, IntegralType item, const true_type&) {
        assign(new_capacity, static_cast<size_type>(n), static_cast<value_type>(item));
    }

    //! Specialized assign method.
    template <class Iterator>
    void assign(capacity_type new_capacity, Iterator first, Iterator last, const false_type&) {
        BOOST_CB_IS_CONVERTIBLE(Iterator, value_type); // check for invalid iterator type
#if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x581))
        assign(new_capacity, first, last, BOOST_ITERATOR_CATEGORY<Iterator>::type());
#else
        assign(new_capacity, first, last, BOOST_DEDUCED_TYPENAME BOOST_ITERATOR_CATEGORY<Iterator>::type());
#endif
    }

    //! Specialized assign method.
    template <class InputIterator>
    void assign(capacity_type new_capacity, InputIterator first, InputIterator last, const std::input_iterator_tag&) {
        if (new_capacity == capacity()) {
            clear();
            insert(begin(), first, last);
        } else {
#if BOOST_WORKAROUND(BOOST_MSVC, < 1300)
            circular_buffer<value_type, allocator_type> tmp(new_capacity, m_alloc);
            tmp.insert(begin(), first, last);
#else
            circular_buffer<value_type, allocator_type> tmp(new_capacity, first, last, m_alloc);
#endif
            tmp.swap(*this);
        }
    }

    //! Specialized assign method.
    template <class ForwardIterator>
    void assign(capacity_type new_capacity, ForwardIterator first, ForwardIterator last,
        const std::forward_iterator_tag&) {
        BOOST_CB_ASSERT(std::distance(first, last) >= 0); // check for wrong range
        size_type distance = std::distance(first, last);
        if (distance > new_capacity) {
            std::advance(first, distance - new_capacity);
            distance = new_capacity;
        }
        assign_n(new_capacity, distance,
            cb_details::assign_range<ForwardIterator, allocator_type>(first, last, m_alloc));
    }

    //! Helper assign method.
    template <class Functor>
    void assign_n(capacity_type new_capacity, size_type n, const Functor& fnc) {
        if (new_capacity == capacity()) {
            destroy_content();
            BOOST_TRY {
                fnc(m_buff);
            } BOOST_CATCH(...) {
                m_size = 0;
                BOOST_RETHROW
            }
            BOOST_CATCH_END
        } else {
            pointer buff = allocate(new_capacity);
            BOOST_TRY {
                fnc(buff);
            } BOOST_CATCH(...) {
                deallocate(buff, new_capacity);
                BOOST_RETHROW
            }
            BOOST_CATCH_END
            destroy();
            m_buff = buff;
            m_end = m_buff + new_capacity;
        }
        m_size = n;
        m_first = m_buff;
        m_last = add(m_buff, size());
    }

    //! Helper insert method.
    iterator insert_item(const iterator& pos, param_value_type item) {
        pointer p = pos.m_it;
        if (p == 0) {
            construct_or_replace(!full(), m_last, item);
            p = m_last;
        } else {
            pointer src = m_last;
            pointer dest = m_last;
            bool construct = !full();
            BOOST_TRY {
                while (src != p) {
                    decrement(src);
                    construct_or_replace(construct, dest, *src);
                    decrement(dest);
                    construct = false;
                }
                replace(p, item);
            } BOOST_CATCH(...) {
                if (!construct && !full()) {
                    increment(m_last);
                    ++m_size;
                }
                BOOST_RETHROW
            }
            BOOST_CATCH_END
        }
        increment(m_last);
        if (full())
            m_first = m_last;
        else
            ++m_size;
        return iterator(this, p);
    }

    //! Specialized insert method.
    template <class IntegralType>
    void insert(const iterator& pos, IntegralType n, IntegralType item, const true_type&) {
        insert(pos, static_cast<size_type>(n), static_cast<value_type>(item));
    }

    //! Specialized insert method.
    template <class Iterator>
    void insert(const iterator& pos, Iterator first, Iterator last, const false_type&) {
        BOOST_CB_IS_CONVERTIBLE(Iterator, value_type); // check for invalid iterator type
#if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x581))
        insert(pos, first, last, BOOST_ITERATOR_CATEGORY<Iterator>::type());
#else
        insert(pos, first, last, BOOST_DEDUCED_TYPENAME BOOST_ITERATOR_CATEGORY<Iterator>::type());
#endif
    }

    //! Specialized insert method.
    template <class InputIterator>
    void insert(iterator pos, InputIterator first, InputIterator last, const std::input_iterator_tag&) {
        if (!full() || pos != begin()) {
            for (;first != last; ++pos)
                pos = insert_item(pos, *first++);
        }
    }

    //! Specialized insert method.
    template <class ForwardIterator>
    void insert(const iterator& pos, ForwardIterator first, ForwardIterator last, const std::forward_iterator_tag&) {
        BOOST_CB_ASSERT(std::distance(first, last) >= 0); // check for wrong range
        size_type n = std::distance(first, last);
        if (n == 0)
            return;
        size_type copy = capacity() - (end() - pos);
        if (copy == 0)
            return;
        if (n > copy) {
            std::advance(first, n - copy);
            n = copy;
        }
        insert_n(pos, n, cb_details::iterator_wrapper<ForwardIterator>(first));
    }

    //! Helper insert method.
    template <class Wrapper>
    void insert_n(const iterator& pos, size_type n, const Wrapper& wrapper) {
        size_type construct = reserve();
        if (construct > n)
            construct = n;
        if (pos.m_it == 0) {
            size_type ii = 0;
            pointer p = m_last;
            BOOST_TRY {
                for (; ii < construct; ++ii, increment(p))
                    m_alloc.construct(p, *wrapper());
                for (;ii < n; ++ii, increment(p))
                    replace(p, *wrapper());
            } BOOST_CATCH(...) {
                size_type constructed = (std::min)(ii, construct);
                m_last = add(m_last, constructed);
                m_size += constructed;
                BOOST_RETHROW
            }
            BOOST_CATCH_END
        } else {
            pointer src = m_last;
            pointer dest = add(m_last, n - 1);
            pointer p = pos.m_it;
            size_type ii = 0;
            BOOST_TRY {
                while (src != pos.m_it) {
                    decrement(src);
                    construct_or_replace(is_uninitialized(dest), dest, *src);
                    decrement(dest);
                }
                for (; ii < n; ++ii, increment(p))
                    construct_or_replace(is_uninitialized(p), p, *wrapper());
            } BOOST_CATCH(...) {
                for (p = add(m_last, n - 1); p != dest; decrement(p))
                    destroy_if_constructed(p);
                for (n = 0, p = pos.m_it; n < ii; ++n, increment(p))
                    destroy_if_constructed(p);
                BOOST_RETHROW
            }
            BOOST_CATCH_END
        }
        m_last = add(m_last, n);
        m_first = add(m_first, n - construct);
        m_size += construct;
    }

    //! Specialized rinsert method.
    template <class IntegralType>
    void rinsert(const iterator& pos, IntegralType n, IntegralType item, const true_type&) {
        rinsert(pos, static_cast<size_type>(n), static_cast<value_type>(item));
    }

    //! Specialized rinsert method.
    template <class Iterator>
    void rinsert(const iterator& pos, Iterator first, Iterator last, const false_type&) {
        BOOST_CB_IS_CONVERTIBLE(Iterator, value_type); // check for invalid iterator type
#if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x581))
        rinsert(pos, first, last, BOOST_ITERATOR_CATEGORY<Iterator>::type());
#else
        rinsert(pos, first, last, BOOST_DEDUCED_TYPENAME BOOST_ITERATOR_CATEGORY<Iterator>::type());
#endif
    }

    //! Specialized insert method.
    template <class InputIterator>
    void rinsert(iterator pos, InputIterator first, InputIterator last, const std::input_iterator_tag&) {
        if (!full() || pos.m_it != 0) {
            for (;first != last; ++pos) {
                pos = rinsert(pos, *first++);
                if (pos.m_it == 0)
                    break;
            }
        }
    }

    //! Specialized rinsert method.
    template <class ForwardIterator>
    void rinsert(const iterator& pos, ForwardIterator first, ForwardIterator last, const std::forward_iterator_tag&) {
        BOOST_CB_ASSERT(std::distance(first, last) >= 0); // check for wrong range
        rinsert_n(pos, std::distance(first, last), cb_details::iterator_wrapper<ForwardIterator>(first));
    }

    //! Helper rinsert method.
    template <class Wrapper>
    void rinsert_n(const iterator& pos, size_type n, const Wrapper& wrapper) {
        if (n == 0)
            return;
        iterator b = begin();
        size_type copy = capacity() - (pos - b);
        if (copy == 0)
            return;
        if (n > copy)
            n = copy;
        size_type construct = reserve();
        if (construct > n)
            construct = n;
        if (pos == b) {
            pointer p = sub(m_first, n);
            size_type ii = n;
            BOOST_TRY {
                for (;ii > construct; --ii, increment(p))
                    replace(p, *wrapper());
                for (; ii > 0; --ii, increment(p))
                    m_alloc.construct(p, *wrapper());
            } BOOST_CATCH(...) {
                size_type constructed = ii < construct ? construct - ii : 0;
                m_last = add(m_last, constructed);
                m_size += constructed;
                BOOST_RETHROW
            }
            BOOST_CATCH_END
        } else {
            pointer src = m_first;
            pointer dest = sub(m_first, n);
            pointer p = map_pointer(pos.m_it);
            BOOST_TRY {
                while (src != p) {
                    construct_or_replace(is_uninitialized(dest), dest, *src);
                    increment(src);
                    increment(dest);
                }
                for (size_type ii = 0; ii < n; ++ii, increment(dest))
                    construct_or_replace(is_uninitialized(dest), dest, *wrapper());
            } BOOST_CATCH(...) {
                for (src = sub(m_first, n); src != dest; increment(src))
                    destroy_if_constructed(src);
                BOOST_RETHROW
            }
            BOOST_CATCH_END
        }
        m_first = sub(m_first, n);
        m_last = sub(m_last, n - construct);
        m_size += construct;
    }
};

// Non-member functions

//! Compare two <code>circular_buffer</code>s element-by-element to determine if they are equal.
/*!
    \param lhs The <code>circular_buffer</code> to compare.
    \param rhs The <code>circular_buffer</code> to compare.
    \return <code>lhs.\link circular_buffer::size() size()\endlink == rhs.\link circular_buffer::size() size()\endlink
            && <a href="http://www.sgi.com/tech/stl/equal.html">std::equal</a>(lhs.\link circular_buffer::begin()
            begin()\endlink, lhs.\link circular_buffer::end() end()\endlink,
            rhs.\link circular_buffer::begin() begin()\endlink)</code>
    \throws Nothing.
    \par Complexity
         Linear (in the size of the <code>circular_buffer</code>s).
    \par Iterator Invalidation
         Does not invalidate any iterators.
*/
template <class T, class Alloc>
inline bool operator == (const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs) {
    return lhs.size() == rhs.size() && std::equal(lhs.begin(), lhs.end(), rhs.begin());
}

/*!
    \brief Compare two <code>circular_buffer</code>s element-by-element to determine if the left one is lesser than the
           right one.
    \param lhs The <code>circular_buffer</code> to compare.
    \param rhs The <code>circular_buffer</code> to compare.
    \return <code><a href="http://www.sgi.com/tech/stl/lexicographical_compare.html">
            std::lexicographical_compare</a>(lhs.\link circular_buffer::begin() begin()\endlink,
            lhs.\link circular_buffer::end() end()\endlink, rhs.\link circular_buffer::begin() begin()\endlink,
            rhs.\link circular_buffer::end() end()\endlink)</code>
    \throws Nothing.
    \par Complexity
         Linear (in the size of the <code>circular_buffer</code>s).
    \par Iterator Invalidation
         Does not invalidate any iterators.
*/
template <class T, class Alloc>
inline bool operator < (const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs) {
    return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
}

#if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING) || defined(BOOST_MSVC)

//! Compare two <code>circular_buffer</code>s element-by-element to determine if they are non-equal.
/*!
    \param lhs The <code>circular_buffer</code> to compare.
    \param rhs The <code>circular_buffer</code> to compare.
    \return <code>!(lhs == rhs)</code>
    \throws Nothing.
    \par Complexity
         Linear (in the size of the <code>circular_buffer</code>s).
    \par Iterator Invalidation
         Does not invalidate any iterators.
    \sa <code>operator==(const circular_buffer<T,Alloc>&, const circular_buffer<T,Alloc>&)</code>
*/
template <class T, class Alloc>
inline bool operator != (const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs) {
    return !(lhs == rhs);
}

/*!
    \brief Compare two <code>circular_buffer</code>s element-by-element to determine if the left one is greater than
           the right one.
    \param lhs The <code>circular_buffer</code> to compare.
    \param rhs The <code>circular_buffer</code> to compare.
    \return <code>rhs \< lhs</code>
    \throws Nothing.
    \par Complexity
         Linear (in the size of the <code>circular_buffer</code>s).
    \par Iterator Invalidation
         Does not invalidate any iterators.
    \sa <code>operator<(const circular_buffer<T,Alloc>&, const circular_buffer<T,Alloc>&)</code>
*/
template <class T, class Alloc>
inline bool operator > (const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs) {
    return rhs < lhs;
}

/*!
    \brief Compare two <code>circular_buffer</code>s element-by-element to determine if the left one is lesser or equal
           to the right one.
    \param lhs The <code>circular_buffer</code> to compare.
    \param rhs The <code>circular_buffer</code> to compare.
    \return <code>!(rhs \< lhs)</code>
    \throws Nothing.
    \par Complexity
         Linear (in the size of the <code>circular_buffer</code>s).
    \par Iterator Invalidation
         Does not invalidate any iterators.
    \sa <code>operator<(const circular_buffer<T,Alloc>&, const circular_buffer<T,Alloc>&)</code>
*/
template <class T, class Alloc>
inline bool operator <= (const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs) {
    return !(rhs < lhs);
}

/*!
    \brief Compare two <code>circular_buffer</code>s element-by-element to determine if the left one is greater or
           equal to the right one.
    \param lhs The <code>circular_buffer</code> to compare.
    \param rhs The <code>circular_buffer</code> to compare.
    \return <code>!(lhs < rhs)</code>
    \throws Nothing.
    \par Complexity
         Linear (in the size of the <code>circular_buffer</code>s).
    \par Iterator Invalidation
         Does not invalidate any iterators.
    \sa <code>operator<(const circular_buffer<T,Alloc>&, const circular_buffer<T,Alloc>&)</code>
*/
template <class T, class Alloc>
inline bool operator >= (const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs) {
    return !(lhs < rhs);
}

//! Swap the contents of two <code>circular_buffer</code>s.
/*!
    \post <code>lhs</code> contains elements of <code>rhs</code> and vice versa.
    \param lhs The <code>circular_buffer</code> whose content will be swapped with <code>rhs</code>.
    \param rhs The <code>circular_buffer</code> whose content will be swapped with <code>lhs</code>.
    \throws Nothing.
    \par Complexity
         Constant (in the size of the <code>circular_buffer</code>s).
    \par Iterator Invalidation
         Invalidates all iterators of both <code>circular_buffer</code>s. (On the other hand the iterators still
         point to the same elements but within another container. If you want to rely on this feature you have to
         turn the <a href="#debug">Debug Support</a> off otherwise an assertion will report an error if such
         invalidated iterator is used.)
    \sa <code>\link circular_buffer::swap(circular_buffer<T, Alloc>&) swap(circular_buffer<T, Alloc>&)\endlink</code>
*/
template <class T, class Alloc>
inline void swap(circular_buffer<T, Alloc>& lhs, circular_buffer<T, Alloc>& rhs) {
    lhs.swap(rhs);
}

#endif // #if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING) || defined(BOOST_MSVC)

} // namespace boost

#endif // #if !defined(BOOST_CIRCULAR_BUFFER_BASE_HPP)