Chris@16: // Implementation of the circular buffer adaptor.
Chris@16: 
Chris@16: // Copyright (c) 2003-2008 Jan Gaspar
Chris@16: // Copyright (c) 2013  Paul A. Bristow // Doxygen comments changed for new version of documentation.
Chris@16: // Copyright (c) 2013  Antony Polukhin // Move semantics implementation.
Chris@16: 
Chris@16: // Use, modification, and distribution is subject to the Boost Software
Chris@16: // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #if !defined(BOOST_CIRCULAR_BUFFER_SPACE_OPTIMIZED_HPP)
Chris@16: #define BOOST_CIRCULAR_BUFFER_SPACE_OPTIMIZED_HPP
Chris@16: 
Chris@101: #if defined(_MSC_VER)
Chris@16:     #pragma once
Chris@16: #endif
Chris@16: 
Chris@16: #include <boost/type_traits/is_same.hpp>
Chris@16: #include <boost/detail/workaround.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16: /*!
Chris@16:     \class circular_buffer_space_optimized
Chris@16:     \brief Space optimized circular buffer container adaptor. 
Chris@16:            <code>T</code> must be a copyable class or must have an noexcept move constructor
Chris@16:            and move assignment operator.
Chris@16: */
Chris@16: template <class T, class Alloc>
Chris@16: class circular_buffer_space_optimized :
Chris@16: /*! \cond */
Chris@16: #if BOOST_CB_ENABLE_DEBUG
Chris@16: public
Chris@16: #endif
Chris@16: /*! \endcond */
Chris@16: circular_buffer<T, Alloc> {
Chris@16: public:
Chris@16: // Typedefs
Chris@16: 
Chris@16:     typedef typename circular_buffer<T, Alloc>::value_type value_type;
Chris@16:     typedef typename circular_buffer<T, Alloc>::pointer pointer;
Chris@16:     typedef typename circular_buffer<T, Alloc>::const_pointer const_pointer;
Chris@16:     typedef typename circular_buffer<T, Alloc>::reference reference;
Chris@16:     typedef typename circular_buffer<T, Alloc>::const_reference const_reference;
Chris@16:     typedef typename circular_buffer<T, Alloc>::size_type size_type;
Chris@16:     typedef typename circular_buffer<T, Alloc>::difference_type difference_type;
Chris@16:     typedef typename circular_buffer<T, Alloc>::allocator_type allocator_type;
Chris@16:     typedef typename circular_buffer<T, Alloc>::const_iterator const_iterator;
Chris@16:     typedef typename circular_buffer<T, Alloc>::iterator iterator;
Chris@16:     typedef typename circular_buffer<T, Alloc>::const_reverse_iterator const_reverse_iterator;
Chris@16:     typedef typename circular_buffer<T, Alloc>::reverse_iterator reverse_iterator;
Chris@16:     typedef typename circular_buffer<T, Alloc>::array_range array_range;
Chris@16:     typedef typename circular_buffer<T, Alloc>::const_array_range const_array_range;
Chris@16:     typedef typename circular_buffer<T, Alloc>::param_value_type param_value_type;
Chris@16:     typedef typename circular_buffer<T, Alloc>::rvalue_type rvalue_type;
Chris@16:     //typedef typename circular_buffer<T, Alloc>::return_value_type return_value_type;
Chris@16: 
Chris@16: /* <pre> is not passed through to html or pdf. So <br> is used in code section below.  Ugly :-(
Chris@16: Ideally want a link to capacity_control, but this would require include details
Chris@16: and this would expose all the functions in details.
Chris@16: There must be a better way of doing this.
Chris@16: */
Chris@16: 
Chris@16:     /*! Capacity controller of the space optimized circular buffer.
Chris@16: 
Chris@16:     \see capacity_control in details.hpp.
Chris@16: <p>
Chris@16: <code>
Chris@16: class capacity_control<br>
Chris@16: {<br>
Chris@16:    size_type m_capacity;  // Available capacity.<br>
Chris@16:    size_type m_min_capacity; // Minimum capacity.<br>
Chris@16: public:<br>
Chris@16:    capacity_control(size_type capacity, size_type min_capacity = 0)<br>
Chris@16:    : m_capacity(capacity), m_min_capacity(min_capacity)<br>
Chris@16:      {};<br>
Chris@16:    size_type %capacity() const { return m_capacity; }<br>
Chris@16:    size_type min_capacity() const { return m_min_capacity; }<br>
Chris@16:    operator size_type() const { return m_capacity; }<br>
Chris@16: };<br>
Chris@16: </code>
Chris@16: </p>
Chris@16: 
Chris@16: 
Chris@16:   <p>Always
Chris@16:     <code>capacity >= min_capacity</code>.
Chris@16:   </p>
Chris@16:   <p>
Chris@16:     The <code>capacity()</code> represents the capacity
Chris@16:     of the <code>circular_buffer_space_optimized</code> and
Chris@16:     the <code>min_capacity()</code> determines the minimal allocated size of its internal buffer.
Chris@16:  </p>
Chris@16:  <p>The converting constructor of the <code>capacity_control</code> allows implicit conversion from
Chris@16:   <code>size_type</code>-like types which ensures compatibility of creating an instance of the
Chris@16:   <code>circular_buffer_space_optimized</code> with other STL containers.
Chris@16: 
Chris@16:   On the other hand the operator <code>%size_type()</code>
Chris@16:   provides implicit conversion to the <code>size_type</code> which allows to treat the
Chris@16:   capacity of the <code>circular_buffer_space_optimized</code> the same way as in the
Chris@16:   <code>circular_buffer</a></code>.
Chris@16: </p>
Chris@16:     */
Chris@16:     typedef cb_details::capacity_control<size_type> capacity_type;
Chris@16: 
Chris@16: // Inherited
Chris@16: 
Chris@16:     using circular_buffer<T, Alloc>::get_allocator;
Chris@16:     using circular_buffer<T, Alloc>::begin;
Chris@16:     using circular_buffer<T, Alloc>::end;
Chris@16:     using circular_buffer<T, Alloc>::rbegin;
Chris@16:     using circular_buffer<T, Alloc>::rend;
Chris@16:     using circular_buffer<T, Alloc>::at;
Chris@16:     using circular_buffer<T, Alloc>::front;
Chris@16:     using circular_buffer<T, Alloc>::back;
Chris@16:     using circular_buffer<T, Alloc>::array_one;
Chris@16:     using circular_buffer<T, Alloc>::array_two;
Chris@16:     using circular_buffer<T, Alloc>::linearize;
Chris@16:     using circular_buffer<T, Alloc>::is_linearized;
Chris@16:     using circular_buffer<T, Alloc>::rotate;
Chris@16:     using circular_buffer<T, Alloc>::size;
Chris@16:     using circular_buffer<T, Alloc>::max_size;
Chris@16:     using circular_buffer<T, Alloc>::empty;
Chris@16: 
Chris@16: #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564))
Chris@16:     reference operator [] (size_type n) { return circular_buffer<T, Alloc>::operator[](n); }
Chris@16:     const_reference operator [] (size_type n) const { return circular_buffer<T, Alloc>::operator[](n); }
Chris@16: #else
Chris@16:     using circular_buffer<T, Alloc>::operator[];
Chris@16: #endif
Chris@16: 
Chris@16: private:
Chris@16: // Member variables
Chris@16: 
Chris@16:     //! The capacity controller of the space optimized circular buffer.
Chris@16:     capacity_type m_capacity_ctrl;
Chris@16: 
Chris@16: public:
Chris@16: // Overridden
Chris@16: 
Chris@16:     //! Is the <code>circular_buffer_space_optimized</code> full?
Chris@16:     /*!
Chris@16:         \return <code>true</code> if the number of elements stored in the <code>circular_buffer_space_optimized</code>
Chris@16:                 equals the capacity of the <code>circular_buffer_space_optimized</code>; <code>false</code> otherwise.
Chris@16:         \throws Nothing.
Chris@16:         \par Exception Safety
Chris@16:              No-throw.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer_space_optimized</code>).
Chris@16:         \sa <code>empty()</code>
Chris@16:     */
Chris@16:     bool full() const BOOST_NOEXCEPT { return m_capacity_ctrl == size(); }
Chris@16: 
Chris@16:     /*! \brief Get the maximum number of elements which can be inserted into the
Chris@16:                <code>circular_buffer_space_optimized</code> without overwriting any of already stored elements.
Chris@16:         \return <code>capacity().%capacity() - size()</code>
Chris@16:         \throws Nothing.
Chris@16:         \par Exception Safety
Chris@16:              No-throw.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer_space_optimized</code>).
Chris@16:         \sa <code>capacity()</code>, <code>size()</code>, <code>max_size()</code>
Chris@16:     */
Chris@16:     size_type reserve() const BOOST_NOEXCEPT { return m_capacity_ctrl - size(); }
Chris@16: 
Chris@16:     //! Get the capacity of the <code>circular_buffer_space_optimized</code>.
Chris@16:     /*!
Chris@16:         \return The capacity controller representing the maximum number of elements which can be stored in the
Chris@16:                 <code>circular_buffer_space_optimized</code> and the minimal allocated size of the internal buffer.
Chris@16:         \throws Nothing.
Chris@16:         \par Exception Safety
Chris@16:              No-throw.
Chris@16:         \par Iterator Invalidation
Chris@16:              Does not invalidate any iterators.
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer_space_optimized</code>).
Chris@16:         \sa <code>reserve()</code>, <code>size()</code>, <code>max_size()</code>,
Chris@16:             <code>set_capacity(const capacity_type&)</code>
Chris@16:     */
Chris@16:     const capacity_type& capacity() const BOOST_NOEXCEPT { return m_capacity_ctrl; }
Chris@16: 
Chris@16: #if defined(BOOST_CB_TEST)
Chris@16: 
Chris@16:     // Return the current capacity of the adapted circular buffer.
Chris@16:     /*
Chris@16:        \note This method is not intended to be used directly by the user.
Chris@16:              It is defined only for testing purposes.
Chris@16:     */
Chris@16:     size_type internal_capacity() const BOOST_NOEXCEPT { return circular_buffer<T, Alloc>::capacity(); }
Chris@16: 
Chris@16: #endif // #if defined(BOOST_CB_TEST)
Chris@16: 
Chris@16:     /*! \brief Change the capacity (and the minimal guaranteed amount of allocated memory) of the
Chris@16:                <code>circular_buffer_space_optimized</code>.
Chris@16:         \post <code>capacity() == capacity_ctrl \&\& size() \<= capacity_ctrl.capacity()</code><br><br>
Chris@16:               If the current number of elements stored in the <code>circular_buffer_space_optimized</code> is greater
Chris@16:               than the desired new capacity then number of <code>[size() - capacity_ctrl.capacity()]</code> <b>last</b>
Chris@16:               elements will be removed and the new size will be equal to <code>capacity_ctrl.capacity()</code>.<br><br>
Chris@16:               If the current number of elements stored in the <code>circular_buffer_space_optimized</code> is lower
Chris@16:               than the new capacity then the amount of allocated memory in the internal buffer may be accommodated as
Chris@16:               necessary but it will never drop below <code>capacity_ctrl.min_capacity()</code>.
Chris@16:         \param capacity_ctrl The new capacity controller.
Chris@16:         \throws "An allocation error" if memory is exhausted, (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept.
Chris@16:         \par Exception Safety
Chris@16:              Strong.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
Chris@16:              equal to <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in <code>min[size(), capacity_ctrl.%capacity()]</code>).
Chris@16:         \note To explicitly clear the extra allocated memory use the <b>shrink-to-fit</b> technique:<br><br>
Chris@16:               <code>%boost::%circular_buffer_space_optimized\<int\> cb(1000);<br>
Chris@16:               ...<br>
Chris@16:               %boost::%circular_buffer_space_optimized\<int\>(cb).swap(cb);</code><br><br>
Chris@16:               For more information about the shrink-to-fit technique in STL see
Chris@16:               <a href="http://www.gotw.ca/gotw/054.htm">http://www.gotw.ca/gotw/054.htm</a>.
Chris@16:         \sa <code>rset_capacity(const capacity_type&)</code>,
Chris@16:             <code>\link resize() resize(size_type, const_reference)\endlink</code>
Chris@16:     */
Chris@16:     void set_capacity(const capacity_type& capacity_ctrl) {
Chris@16:         m_capacity_ctrl = capacity_ctrl;
Chris@16:         if (capacity_ctrl < size()) {
Chris@16:             iterator e = end();
Chris@16:             circular_buffer<T, Alloc>::erase(e - (size() - capacity_ctrl), e);
Chris@16:         }
Chris@16:         adjust_min_capacity();
Chris@16:     }
Chris@16: 
Chris@16:     //! Change the size of the <code>circular_buffer_space_optimized</code>.
Chris@16:     /*!
Chris@16:         \post <code>size() == new_size \&\& capacity().%capacity() >= new_size</code><br><br>
Chris@16:               If the new size is greater than the current size, copies of <code>item</code> will be inserted at the
Chris@16:               <b>back</b> of the of the <code>circular_buffer_space_optimized</code> in order to achieve the desired
Chris@16:               size. In the case the resulting size exceeds the current capacity the capacity will be set to
Chris@16:               <code>new_size</code>.<br><br>
Chris@16:               If the current number of elements stored in the <code>circular_buffer_space_optimized</code> is greater
Chris@16:               than the desired new size then number of <code>[size() - new_size]</code> <b>last</b> elements will be
Chris@16:               removed. (The capacity will remain unchanged.)<br><br>
Chris@16:               The amount of allocated memory in the internal buffer may be accommodated as necessary.
Chris@16:         \param new_size The new size.
Chris@16:         \param item The element the <code>circular_buffer_space_optimized</code> will be filled with in order to gain
Chris@16:                     the requested size. (See the <i>Effect</i>.)
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T(const T&)</code> throws.
Chris@16:         \par Exception Safety
Chris@16:              Basic.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
Chris@16:              equal to <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in the new size of the <code>circular_buffer_space_optimized</code>).
Chris@16:         \sa <code>\link rresize() rresize(size_type, const_reference)\endlink</code>,
Chris@16:             <code>set_capacity(const capacity_type&)</code>
Chris@16:     */
Chris@16:     void resize(size_type new_size, param_value_type item = value_type()) {
Chris@16:         if (new_size > size()) {
Chris@16:             if (new_size > m_capacity_ctrl)
Chris@16:                 m_capacity_ctrl = capacity_type(new_size, m_capacity_ctrl.min_capacity());
Chris@16:             insert(end(), new_size - size(), item);
Chris@16:         } else {
Chris@16:             iterator e = end();
Chris@16:             erase(e - (size() - new_size), e);
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     /*! \brief Change the capacity (and the minimal guaranteed amount of allocated memory) of the
Chris@16:                <code>circular_buffer_space_optimized</code>.
Chris@16:         \post <code>capacity() == capacity_ctrl \&\& size() \<= capacity_ctrl</code><br><br>
Chris@16:               If the current number of elements stored in the <code>circular_buffer_space_optimized</code> is greater
Chris@16:               than the desired new capacity then number of <code>[size() - capacity_ctrl.capacity()]</code>
Chris@16:               <b>first</b> elements will be removed and the new size will be equal to
Chris@16:               <code>capacity_ctrl.capacity()</code>.<br><br>
Chris@16:               If the current number of elements stored in the <code>circular_buffer_space_optimized</code> is lower
Chris@16:               than the new capacity then the amount of allocated memory in the internal buffer may be accommodated as
Chris@16:               necessary but it will never drop below <code>capacity_ctrl.min_capacity()</code>.
Chris@16:         \param capacity_ctrl The new capacity controller.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept.
Chris@16:         \par Exception Safety
Chris@16:              Strong.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
Chris@16:              equal to <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in <code>min[size(), capacity_ctrl.%capacity()]</code>).
Chris@16:         \sa <code>set_capacity(const capacity_type&)</code>,
Chris@16:             <code>\link rresize() rresize(size_type, const_reference)\endlink</code>
Chris@16:     */
Chris@16:     void rset_capacity(const capacity_type& capacity_ctrl) {
Chris@16:         m_capacity_ctrl = capacity_ctrl;
Chris@16:         if (capacity_ctrl < size()) {
Chris@16:             iterator b = begin();
Chris@16:             circular_buffer<T, Alloc>::rerase(b, b + (size() - capacity_ctrl));
Chris@16:         }
Chris@16:         adjust_min_capacity();
Chris@16:     }
Chris@16: 
Chris@16:     //! Change the size of the <code>circular_buffer_space_optimized</code>.
Chris@16:     /*!
Chris@16:         \post <code>size() == new_size \&\& capacity().%capacity() >= new_size</code><br><br>
Chris@16:               If the new size is greater than the current size, copies of <code>item</code> will be inserted at the
Chris@16:               <b>front</b> of the of the <code>circular_buffer_space_optimized</code> in order to achieve the desired
Chris@16:               size. In the case the resulting size exceeds the current capacity the capacity will be set to
Chris@16:               <code>new_size</code>.<br><br>
Chris@16:               If the current number of elements stored in the <code>circular_buffer_space_optimized</code> is greater
Chris@16:               than the desired new size then number of <code>[size() - new_size]</code> <b>first</b> elements will be
Chris@16:               removed. (The capacity will remain unchanged.)<br><br>
Chris@16:               The amount of allocated memory in the internal buffer may be accommodated as necessary.
Chris@16:         \param new_size The new size.
Chris@16:         \param item The element the <code>circular_buffer_space_optimized</code> will be filled with in order to gain
Chris@16:                     the requested size. (See the <i>Effect</i>.)
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T(const T&)</code> throws.
Chris@16:         \par Exception Safety
Chris@16:              Basic.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
Chris@16:              equal to <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in the new size of the <code>circular_buffer_space_optimized</code>).
Chris@16:         \sa <code>\link resize() resize(size_type, const_reference)\endlink</code>,
Chris@16:             <code>rset_capacity(const capacity_type&)</code>
Chris@16:     */
Chris@16:     void rresize(size_type new_size, param_value_type item = value_type()) {
Chris@16:         if (new_size > size()) {
Chris@16:             if (new_size > m_capacity_ctrl)
Chris@16:                 m_capacity_ctrl = capacity_type(new_size, m_capacity_ctrl.min_capacity());
Chris@16:             rinsert(begin(), new_size - size(), item);
Chris@16:         } else {
Chris@16:             rerase(begin(), end() - new_size);
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     //! Create an empty space optimized circular buffer with zero capacity.
Chris@16:     /*!
Chris@16:         \post <code>capacity().%capacity() == 0 \&\& capacity().min_capacity() == 0 \&\& size() == 0</code>
Chris@16:         \param alloc The allocator.
Chris@16:         \throws Nothing.
Chris@16:         \par Complexity
Chris@16:              Constant.
Chris@16:         \warning Since Boost version 1.36 the behaviour of this constructor has changed. Now it creates a space
Chris@16:                  optimized circular buffer with zero capacity.
Chris@16:     */
Chris@16:     explicit circular_buffer_space_optimized(const allocator_type& alloc = allocator_type()) BOOST_NOEXCEPT
Chris@16:     : circular_buffer<T, Alloc>(0, alloc)
Chris@16:     , m_capacity_ctrl(0) {}
Chris@16: 
Chris@16:     //! Create an empty space optimized circular buffer with the specified capacity.
Chris@16:     /*!
Chris@16:         \post <code>capacity() == capacity_ctrl \&\& size() == 0</code><br><br>
Chris@16:               The amount of allocated memory in the internal buffer is <code>capacity_ctrl.min_capacity()</code>.
Chris@16:         \param capacity_ctrl The capacity controller representing the maximum number of elements which can be stored in
Chris@16:                              the <code>circular_buffer_space_optimized</code> and the minimal allocated size of the
Chris@16:                              internal buffer.
Chris@16:         \param alloc The allocator.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:         \par Complexity
Chris@16:              Constant.
Chris@16:     */
Chris@16:     explicit circular_buffer_space_optimized(capacity_type capacity_ctrl,
Chris@16:         const allocator_type& alloc = allocator_type())
Chris@16:     : circular_buffer<T, Alloc>(capacity_ctrl.min_capacity(), alloc)
Chris@16:     , m_capacity_ctrl(capacity_ctrl) {}
Chris@16: 
Chris@16:     /*! \brief Create a full space optimized circular buffer with the specified capacity filled with
Chris@16:                <code>capacity_ctrl.%capacity()</code> copies of <code>item</code>.
Chris@16:         \post <code>capacity() == capacity_ctrl \&\& full() \&\& (*this)[0] == item \&\& (*this)[1] == item \&\& ...
Chris@16:               \&\& (*this) [capacity_ctrl.%capacity() - 1] == item </code><br><br>
Chris@16:               The amount of allocated memory in the internal buffer is <code>capacity_ctrl.capacity()</code>.
Chris@16:         \param capacity_ctrl The capacity controller representing the maximum number of elements which can be stored in
Chris@16:                              the <code>circular_buffer_space_optimized</code> and the minimal allocated size of the
Chris@16:                              internal buffer.
Chris@16:         \param item The element the created <code>circular_buffer_space_optimized</code> will be filled with.
Chris@16:         \param alloc The allocator.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:         \throws Whatever <code>T::T(const T&)</code> throws.
Chris@16:         \par Complexity
Chris@16:              Linear (in the <code>capacity_ctrl.%capacity()</code>).
Chris@16:     */
Chris@16:     circular_buffer_space_optimized(capacity_type capacity_ctrl, param_value_type item,
Chris@16:         const allocator_type& alloc = allocator_type())
Chris@16:     : circular_buffer<T, Alloc>(capacity_ctrl.capacity(), item, alloc)
Chris@16:     , m_capacity_ctrl(capacity_ctrl) {}
Chris@16: 
Chris@16:     /*! \brief Create a space optimized circular buffer with the specified capacity filled with <code>n</code> copies
Chris@16:                of <code>item</code>.
Chris@16:         \pre <code>capacity_ctrl.%capacity() >= n</code>
Chris@16:         \post <code>capacity() == capacity_ctrl \&\& size() == n \&\& (*this)[0] == item \&\& (*this)[1] == item
Chris@16:               \&\& ... \&\& (*this)[n - 1] == item</code><br><br>
Chris@16:               The amount of allocated memory in the internal buffer is
Chris@16:               <code>max[n, capacity_ctrl.min_capacity()]</code>.
Chris@16:         \param capacity_ctrl The capacity controller representing the maximum number of elements which can be stored in
Chris@16:                              the <code>circular_buffer_space_optimized</code> and the minimal allocated size of the
Chris@16:                              internal buffer.
Chris@16:         \param n The number of elements the created <code>circular_buffer_space_optimized</code> will be filled with.
Chris@16:         \param item The element the created <code>circular_buffer_space_optimized</code> will be filled with.
Chris@16:         \param alloc The allocator.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T(const T&)</code> throws.
Chris@16:         \par Complexity
Chris@16:              Linear (in the <code>n</code>).
Chris@16:     */
Chris@16:     circular_buffer_space_optimized(capacity_type capacity_ctrl, size_type n, param_value_type item,
Chris@16:         const allocator_type& alloc = allocator_type())
Chris@16:     : circular_buffer<T, Alloc>(init_capacity(capacity_ctrl, n), n, item, alloc)
Chris@16:     , m_capacity_ctrl(capacity_ctrl) {}
Chris@16: 
Chris@16:     //! The copy constructor.
Chris@16:     /*!
Chris@16:         Creates a copy of the specified <code>circular_buffer_space_optimized</code>.
Chris@16:         \post <code>*this == cb</code><br><br>
Chris@16:               The amount of allocated memory in the internal buffer is <code>cb.size()</code>.
Chris@16:         \param cb The <code>circular_buffer_space_optimized</code> to be copied.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T(const T&)</code> throws.
Chris@16:         \par Complexity
Chris@16:              Linear (in the size of <code>cb</code>).
Chris@16:     */
Chris@16:     circular_buffer_space_optimized(const circular_buffer_space_optimized<T, Alloc>& cb)
Chris@16:     : circular_buffer<T, Alloc>(cb.begin(), cb.end(), cb.get_allocator())
Chris@16:     , m_capacity_ctrl(cb.m_capacity_ctrl) {}
Chris@16: 
Chris@16: #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
Chris@16:     //! The move constructor.
Chris@16:     /*! \brief Move constructs a <code>circular_buffer_space_optimized</code> from <code>cb</code>, 
Chris@16:                 leaving <code>cb</code> empty.
Chris@16:         \pre C++ compiler with rvalue references support.
Chris@16:         \post <code>cb.empty()</code>
Chris@16:         \param cb <code>circular_buffer</code> to 'steal' value from.
Chris@16:         \throws Nothing.
Chris@16:         \par Constant.
Chris@16:     */
Chris@16:     circular_buffer_space_optimized(circular_buffer_space_optimized<T, Alloc>&& cb) BOOST_NOEXCEPT
Chris@16:     : circular_buffer<T, Alloc>()
Chris@16:     , m_capacity_ctrl(0) {
Chris@16:         cb.swap(*this);
Chris@16:     }
Chris@16: #endif // BOOST_NO_CXX11_RVALUE_REFERENCES
Chris@16: 
Chris@16:     //! Create a full space optimized circular buffer filled with a copy of the range.
Chris@16:     /*!
Chris@16:         \pre Valid range <code>[first, last)</code>.<br>
Chris@16:              <code>first</code> and <code>last</code> have to meet the requirements of
Chris@16:              <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
Chris@16:         \post <code>capacity().%capacity() == std::distance(first, last) \&\& capacity().min_capacity() == 0 \&\&
Chris@16:               full() \&\& (*this)[0]== *first \&\& (*this)[1] == *(first + 1) \&\& ... \&\&
Chris@16:               (*this)[std::distance(first, last) - 1] == *(last - 1)</code><br><br>
Chris@16:               The amount of allocated memory in the internal buffer is <code>std::distance(first, last)</code>.
Chris@16:         \param first The beginning of the range to be copied.
Chris@16:         \param last The end of the range to be copied.
Chris@16:         \param alloc The allocator.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept 
Chris@16:                 and <code>InputIterator</code> is a move iterator.
Chris@16:         \par Complexity
Chris@16:              Linear (in the <code>std::distance(first, last)</code>).
Chris@16:     */
Chris@16:     template <class InputIterator>
Chris@16:     circular_buffer_space_optimized(InputIterator first, InputIterator last,
Chris@16:         const allocator_type& alloc = allocator_type())
Chris@16:     : circular_buffer<T, Alloc>(first, last, alloc)
Chris@16:     , m_capacity_ctrl(circular_buffer<T, Alloc>::capacity()) {}
Chris@16: 
Chris@16:     /*! \brief Create a space optimized circular buffer with the specified capacity (and the minimal guaranteed amount
Chris@16:                of allocated memory) filled with a copy of the range.
Chris@16:         \pre Valid range <code>[first, last)</code>.<br>
Chris@16:              <code>first</code> and <code>last</code> have to meet the requirements of
Chris@16:              <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
Chris@16:         \post <code>capacity() == capacity_ctrl \&\& size() \<= std::distance(first, last) \&\& (*this)[0]==
Chris@16:               *(last - capacity_ctrl.%capacity()) \&\& (*this)[1] == *(last - capacity_ctrl.%capacity() + 1) \&\& ...
Chris@16:               \&\& (*this)[capacity_ctrl.%capacity() - 1] == *(last - 1)</code><br><br>
Chris@16:               If the number of items to be copied from the range <code>[first, last)</code> is greater than the
Chris@16:               specified <code>capacity_ctrl.%capacity()</code> then only elements from the range
Chris@16:               <code>[last - capacity_ctrl.%capacity(), last)</code> will be copied.<br><br>
Chris@16:               The amount of allocated memory in the internal buffer is <code>max[capacity_ctrl.min_capacity(),
Chris@16:               min[capacity_ctrl.%capacity(), std::distance(first, last)]]</code>.
Chris@16:         \param capacity_ctrl The capacity controller representing the maximum number of elements which can be stored in
Chris@16:                              the <code>circular_buffer_space_optimized</code> and the minimal allocated size of the
Chris@16:                              internal buffer.
Chris@16:         \param first The beginning of the range to be copied.
Chris@16:         \param last The end of the range to be copied.
Chris@16:         \param alloc The allocator.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T(const T&)</code> throws.
Chris@16:         \par Complexity
Chris@16:              Linear (in <code>std::distance(first, last)</code>; in
Chris@16:              <code>min[capacity_ctrl.%capacity(), std::distance(first, last)]</code> if the <code>InputIterator</code>
Chris@16:              is a <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>).
Chris@16:     */
Chris@16:     template <class InputIterator>
Chris@16:     circular_buffer_space_optimized(capacity_type capacity_ctrl, InputIterator first, InputIterator last,
Chris@16:         const allocator_type& alloc = allocator_type())
Chris@16:     : circular_buffer<T, Alloc>(
Chris@16:         init_capacity(capacity_ctrl, first, last, is_integral<InputIterator>()),
Chris@16:         first, last, alloc)
Chris@16:     , m_capacity_ctrl(capacity_ctrl) {
Chris@16:         reduce_capacity(
Chris@101:             is_same< BOOST_DEDUCED_TYPENAME iterator_category<InputIterator>::type, std::input_iterator_tag >());
Chris@16:     }
Chris@16: 
Chris@16: #if defined(BOOST_CB_NEVER_DEFINED)
Chris@16: // This section will never be compiled - the default destructor will be generated instead.
Chris@16: // Declared only for documentation purpose.
Chris@16: 
Chris@16:     //! The destructor.
Chris@16:     /*!
Chris@16:         Destroys the <code>circular_buffer_space_optimized</code>.
Chris@16:         \throws Nothing.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (including
Chris@16:              iterators equal to <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in the size of the <code>circular_buffer_space_optimized</code>).
Chris@16:         \sa <code>clear()</code>
Chris@16:     */
Chris@16:     ~circular_buffer_space_optimized();
Chris@16: 
Chris@16:     //! no-comment
Chris@16:     void erase_begin(size_type n);
Chris@16: 
Chris@16:     //! no-comment
Chris@16:     void erase_end(size_type n);
Chris@16: 
Chris@16: #endif // #if defined(BOOST_CB_NEVER_DEFINED)
Chris@16: 
Chris@16:     //! The assign operator.
Chris@16:     /*!
Chris@16:         Makes this <code>circular_buffer_space_optimized</code> to become a copy of the specified
Chris@16:         <code>circular_buffer_space_optimized</code>.
Chris@16:         \post <code>*this == cb</code><br><br>
Chris@16:               The amount of allocated memory in the internal buffer is <code>cb.size()</code>.
Chris@16:         \param cb The <code>circular_buffer_space_optimized</code> to be copied.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:         \throws Whatever <code>T::T(const T&)</code> throws.
Chris@16:         \par Exception Safety
Chris@16:              Strong.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to this <code>circular_buffer_space_optimized</code> (except iterators
Chris@16:              equal to <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in the size of <code>cb</code>).
Chris@16:         \sa <code>\link assign(size_type, param_value_type) assign(size_type, const_reference)\endlink</code>,
Chris@16:             <code>\link assign(capacity_type, size_type, param_value_type)
Chris@16:             assign(capacity_type, size_type, const_reference)\endlink</code>,
Chris@16:             <code>assign(InputIterator, InputIterator)</code>,
Chris@16:             <code>assign(capacity_type, InputIterator, InputIterator)</code>
Chris@16:     */
Chris@16:     circular_buffer_space_optimized<T, Alloc>& operator = (const circular_buffer_space_optimized<T, Alloc>& cb) {
Chris@16:         if (this == &cb)
Chris@16:             return *this;
Chris@16:         circular_buffer<T, Alloc>::assign(cb.begin(), cb.end());
Chris@16:         m_capacity_ctrl = cb.m_capacity_ctrl;
Chris@16:         return *this;
Chris@16:     }
Chris@16: 
Chris@16: #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
Chris@16:     /*! \brief Move assigns content of <code>cb</code> to <code>*this</code>, leaving <code>cb</code> empty.
Chris@16:         \pre C++ compiler with rvalue references support.
Chris@16:         \post <code>cb.empty()</code>
Chris@16:         \param cb <code>circular_buffer</code> to 'steal' value from.
Chris@16:         \throws Nothing.
Chris@16:         \par Complexity
Chris@16:              Constant.
Chris@16:     */
Chris@16:     circular_buffer_space_optimized<T, Alloc>& operator = (circular_buffer_space_optimized<T, Alloc>&& cb) BOOST_NOEXCEPT {
Chris@16:         cb.swap(*this); // now `this` holds `cb`
Chris@16:         circular_buffer<T, Alloc>(get_allocator()) // temprary that holds initial `cb` allocator
Chris@16:             .swap(cb); // makes `cb` empty
Chris@16:         return *this;
Chris@16:     }
Chris@16: #endif // BOOST_NO_CXX11_RVALUE_REFERENCES
Chris@16: 
Chris@16: 
Chris@16:     //! Assign <code>n</code> items into the space optimized circular buffer.
Chris@16:     /*!
Chris@16:         The content of the <code>circular_buffer_space_optimized</code> will be removed and replaced with
Chris@16:         <code>n</code> copies of the <code>item</code>.
Chris@16:         \post <code>capacity().%capacity() == n \&\& capacity().min_capacity() == 0 \&\& size() == n \&\& (*this)[0] ==
Chris@16:               item \&\& (*this)[1] == item \&\& ... \&\& (*this) [n - 1] == item</code><br><br>
Chris@16:               The amount of allocated memory in the internal buffer is <code>n</code>.
Chris@16:         \param n The number of elements the <code>circular_buffer_space_optimized</code> will be filled with.
Chris@16:         \param item The element the <code>circular_buffer_space_optimized</code> will be filled with.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T(const T&)</code> throws.
Chris@16:         \par Exception Safety
Chris@16:              Basic.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
Chris@16:              equal to <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in the <code>n</code>).
Chris@16:         \sa <code>\link operator=(const circular_buffer_space_optimized&) operator=\endlink</code>,
Chris@16:             <code>\link assign(capacity_type, size_type, param_value_type)
Chris@16:             assign(capacity_type, size_type, const_reference)\endlink</code>,
Chris@16:             <code>assign(InputIterator, InputIterator)</code>,
Chris@16:             <code>assign(capacity_type, InputIterator, InputIterator)</code>
Chris@16:     */
Chris@16:     void assign(size_type n, param_value_type item) {
Chris@16:         circular_buffer<T, Alloc>::assign(n, item);
Chris@16:         m_capacity_ctrl = capacity_type(n);
Chris@16:     }
Chris@16: 
Chris@16:     //! Assign <code>n</code> items into the space optimized circular buffer specifying the capacity.
Chris@16:     /*!
Chris@16:         The capacity of the <code>circular_buffer_space_optimized</code> will be set to the specified value and the
Chris@16:         content of the <code>circular_buffer_space_optimized</code> will be removed and replaced with <code>n</code>
Chris@16:         copies of the <code>item</code>.
Chris@16:         \pre <code>capacity_ctrl.%capacity() >= n</code>
Chris@16:         \post <code>capacity() == capacity_ctrl \&\& size() == n \&\& (*this)[0] == item \&\& (*this)[1] == item
Chris@16:               \&\& ... \&\& (*this) [n - 1] == item </code><br><br>
Chris@16:               The amount of allocated memory will be <code>max[n, capacity_ctrl.min_capacity()]</code>.
Chris@16:         \param capacity_ctrl The new capacity controller.
Chris@16:         \param n The number of elements the <code>circular_buffer_space_optimized</code> will be filled with.
Chris@16:         \param item The element the <code>circular_buffer_space_optimized</code> will be filled with.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T(const T&)</code> throws.
Chris@16:         \par Exception Safety
Chris@16:              Basic.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
Chris@16:              equal to <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in the <code>n</code>).
Chris@16:         \sa <code>\link operator=(const circular_buffer_space_optimized&) operator=\endlink</code>,
Chris@16:             <code>\link assign(size_type, param_value_type) assign(size_type, const_reference)\endlink</code>,
Chris@16:             <code>assign(InputIterator, InputIterator)</code>,
Chris@16:             <code>assign(capacity_type, InputIterator, InputIterator)</code>
Chris@16:     */
Chris@16:     void assign(capacity_type capacity_ctrl, size_type n, param_value_type item) {
Chris@16:        BOOST_CB_ASSERT(capacity_ctrl.capacity() >= n); // check for new capacity lower than n
Chris@16:        circular_buffer<T, Alloc>::assign((std::max)(capacity_ctrl.min_capacity(), n), n, item);
Chris@16:        m_capacity_ctrl = capacity_ctrl;
Chris@16:     }
Chris@16: 
Chris@16:     //! Assign a copy of the range into the space optimized circular buffer.
Chris@16:     /*!
Chris@16:         The content of the <code>circular_buffer_space_optimized</code> will be removed and replaced with copies of
Chris@16:         elements from the specified range.
Chris@16:         \pre Valid range <code>[first, last)</code>.<br>
Chris@16:              <code>first</code> and <code>last</code> have to meet the requirements of
Chris@16:              <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
Chris@16:         \post <code>capacity().%capacity() == std::distance(first, last) \&\& capacity().min_capacity() == 0 \&\&
Chris@16:               size() == std::distance(first, last) \&\& (*this)[0]== *first \&\& (*this)[1] == *(first + 1) \&\& ...
Chris@16:               \&\& (*this)[std::distance(first, last) - 1] == *(last - 1)</code><br><br>
Chris@16:               The amount of allocated memory in the internal buffer is <code>std::distance(first, last)</code>.
Chris@16:         \param first The beginning of the range to be copied.
Chris@16:         \param last The end of the range to be copied.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept and 
Chris@16:                 <code>InputIterator</code> is a move iterator.
Chris@16:         \par Exception Safety
Chris@16:              Basic.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
Chris@16:              equal to <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in the <code>std::distance(first, last)</code>).
Chris@16:         \sa <code>\link operator=(const circular_buffer_space_optimized&) operator=\endlink</code>,
Chris@16:             <code>\link assign(size_type, param_value_type) assign(size_type, const_reference)\endlink</code>,
Chris@16:             <code>\link assign(capacity_type, size_type, param_value_type)
Chris@16:             assign(capacity_type, size_type, const_reference)\endlink</code>,
Chris@16:             <code>assign(capacity_type, InputIterator, InputIterator)</code>
Chris@16:     */
Chris@16:     template <class InputIterator>
Chris@16:     void assign(InputIterator first, InputIterator last) {
Chris@16:         circular_buffer<T, Alloc>::assign(first, last);
Chris@16:         m_capacity_ctrl = capacity_type(circular_buffer<T, Alloc>::capacity());
Chris@16:     }
Chris@16: 
Chris@16:     //! Assign a copy of the range into the space optimized circular buffer specifying the capacity.
Chris@16:     /*!
Chris@16:         The capacity of the <code>circular_buffer_space_optimized</code> will be set to the specified value and the
Chris@16:         content of the <code>circular_buffer_space_optimized</code> will be removed and replaced with copies of
Chris@16:         elements from the specified range.
Chris@16:         \pre Valid range <code>[first, last)</code>.<br>
Chris@16:              <code>first</code> and <code>last</code> have to meet the requirements of
Chris@16:              <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
Chris@16:         \post <code>capacity() == capacity_ctrl \&\& size() \<= std::distance(first, last) \&\&
Chris@16:              (*this)[0]== *(last - capacity) \&\& (*this)[1] == *(last - capacity + 1) \&\& ... \&\&
Chris@16:              (*this)[capacity - 1] == *(last - 1)</code><br><br>
Chris@16:              If the number of items to be copied from the range <code>[first, last)</code> is greater than the
Chris@16:              specified <code>capacity</code> then only elements from the range <code>[last - capacity, last)</code>
Chris@16:              will be copied.<br><br> The amount of allocated memory in the internal buffer is
Chris@16:              <code>max[std::distance(first, last), capacity_ctrl.min_capacity()]</code>.
Chris@16:         \param capacity_ctrl The new capacity controller.
Chris@16:         \param first The beginning of the range to be copied.
Chris@16:         \param last The end of the range to be copied.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept and 
Chris@16:                 <code>InputIterator</code> is a move iterator.
Chris@16:         \par Exception Safety
Chris@16:              Basic.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
Chris@16:              equal to <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in <code>std::distance(first, last)</code>; in
Chris@16:              <code>min[capacity_ctrl.%capacity(), std::distance(first, last)]</code> if the <code>InputIterator</code>
Chris@16:              is a <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>).
Chris@16:         \sa <code>\link operator=(const circular_buffer_space_optimized&) operator=\endlink</code>,
Chris@16:             <code>\link assign(size_type, param_value_type) assign(size_type, const_reference)\endlink</code>,
Chris@16:             <code>\link assign(capacity_type, size_type, param_value_type)
Chris@16:             assign(capacity_type, size_type, const_reference)\endlink</code>,
Chris@16:             <code>assign(InputIterator, InputIterator)</code>
Chris@16:     */
Chris@16:     template <class InputIterator>
Chris@16:     void assign(capacity_type capacity_ctrl, InputIterator first, InputIterator last) {
Chris@16:        m_capacity_ctrl = capacity_ctrl;
Chris@16:        circular_buffer<T, Alloc>::assign(capacity_ctrl, first, last);
Chris@16:     }
Chris@16: 
Chris@16:     //! Swap the contents of two space-optimized circular-buffers.
Chris@16:     /*!
Chris@16:         \post <code>this</code> contains elements of <code>cb</code> and vice versa; the capacity and the amount of
Chris@16:               allocated memory in the internal buffer of <code>this</code> equal to the capacity and the amount of
Chris@16:               allocated memory of <code>cb</code> and vice versa.
Chris@16:         \param cb The <code>circular_buffer_space_optimized</code> whose content will be swapped.
Chris@16:         \throws Nothing.
Chris@16:         \par Exception Safety
Chris@16:              No-throw.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators of both <code>circular_buffer_space_optimized</code> containers. (On the other
Chris@16:              hand the iterators still point to the same elements but within another container. If you want to rely on
Chris@16:              this feature you have to turn the __debug_support off by defining macro BOOST_CB_DISABLE_DEBUG,
Chris@16:              otherwise an assertion will report an error if such invalidated iterator is used.)
Chris@16:         \par Complexity
Chris@16:              Constant (in the size of the <code>circular_buffer_space_optimized</code>).
Chris@16:         \sa <code>swap(circular_buffer<T, Alloc>&, circular_buffer<T, Alloc>&)</code>, 
Chris@16:             <code>swap(circular_buffer_space_optimized<T, Alloc>&, circular_buffer_space_optimized<T, Alloc>&)</code>
Chris@16: 
Chris@16: 
Chris@16:     */
Chris@16:     // Note link does not work right.  Asked on Doxygen forum for advice 23 May 2103.
Chris@16: 
Chris@16:     void swap(circular_buffer_space_optimized<T, Alloc>& cb) BOOST_NOEXCEPT {
Chris@16:         std::swap(m_capacity_ctrl, cb.m_capacity_ctrl);
Chris@16:         circular_buffer<T, Alloc>::swap(cb);
Chris@16:     }
Chris@16: 
Chris@16:     //! Insert a new element at the end of the space optimized circular buffer.
Chris@16:     /*!
Chris@16:         \post if <code>capacity().%capacity() > 0</code> then <code>back() == item</code><br>
Chris@16:               If the <code>circular_buffer_space_optimized</code> is full, the first element will be removed. If the
Chris@16:               capacity is <code>0</code>, nothing will be inserted.<br><br>
Chris@16:               The amount of allocated memory in the internal buffer may be predictively increased.
Chris@16:         \param item The element to be inserted.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T(const T&)</code> throws.
Chris@16:         \par Exception Safety
Chris@16:              Basic.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
Chris@16:              equal to <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in the size of the <code>circular_buffer_space_optimized</code>).
Chris@16:         \sa <code>\link push_front() push_front(const_reference)\endlink</code>, <code>pop_back()</code>,
Chris@16:             <code>pop_front()</code>
Chris@16:     */
Chris@16:     void push_back(param_value_type item) {
Chris@16:         check_low_capacity();
Chris@16:         circular_buffer<T, Alloc>::push_back(item);
Chris@16:     }
Chris@16: 
Chris@16:     //! Insert a new element at the end of the space optimized circular buffer.
Chris@16:     /*!
Chris@16:         \post if <code>capacity().%capacity() > 0</code> then <code>back() == item</code><br>
Chris@16:               If the <code>circular_buffer_space_optimized</code> is full, the first element will be removed. If the
Chris@16:               capacity is <code>0</code>, nothing will be inserted.<br><br>
Chris@16:               The amount of allocated memory in the internal buffer may be predictively increased.
Chris@16:         \param item The element to be inserted.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:         \par Exception Safety
Chris@16:              Basic.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
Chris@16:              equal to <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in the size of the <code>circular_buffer_space_optimized</code>).
Chris@16:         \sa <code>\link push_front() push_front(const_reference)\endlink</code>, <code>pop_back()</code>,
Chris@16:             <code>pop_front()</code>
Chris@16:     */
Chris@16:     void push_back(rvalue_type item) {
Chris@16:         check_low_capacity();
Chris@16:         circular_buffer<T, Alloc>::push_back(boost::move(item));
Chris@16:     }
Chris@16: 
Chris@16:     //! Insert a new element at the end of the space optimized circular buffer.
Chris@16:     /*!
Chris@16:         \post if <code>capacity().%capacity() > 0</code> then <code>back() == item</code><br>
Chris@16:               If the <code>circular_buffer_space_optimized</code> is full, the first element will be removed. If the
Chris@16:               capacity is <code>0</code>, nothing will be inserted.<br><br>
Chris@16:               The amount of allocated memory in the internal buffer may be predictively increased.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T()</code> throws. 
Chris@16:                 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept.
Chris@16:         \par Exception Safety
Chris@16:              Basic.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
Chris@16:              equal to <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in the size of the <code>circular_buffer_space_optimized</code>).
Chris@16:         \sa <code>\link push_front() push_front(const_reference)\endlink</code>, <code>pop_back()</code>,
Chris@16:             <code>pop_front()</code>
Chris@16:     */
Chris@16:     void push_back() {
Chris@16:         check_low_capacity();
Chris@16:         circular_buffer<T, Alloc>::push_back();
Chris@16:     }
Chris@16: 
Chris@16:     //! Insert a new element at the beginning of the space optimized circular buffer.
Chris@16:     /*!
Chris@16:         \post if <code>capacity().%capacity() > 0</code> then <code>front() == item</code><br>
Chris@16:               If the <code>circular_buffer_space_optimized</code> is full, the last element will be removed. If the
Chris@16:               capacity is <code>0</code>, nothing will be inserted.<br><br>
Chris@16:               The amount of allocated memory in the internal buffer may be predictively increased.
Chris@16:         \param item The element to be inserted.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T(const T&)</code> throws.
Chris@16:         \par Exception Safety
Chris@16:              Basic.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
Chris@16:              equal to <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in the size of the <code>circular_buffer_space_optimized</code>).
Chris@16:         \sa <code>\link push_back() push_back(const_reference)\endlink</code>, <code>pop_back()</code>,
Chris@16:             <code>pop_front()</code>
Chris@16:     */
Chris@16:     void push_front(param_value_type item) {
Chris@16:         check_low_capacity();
Chris@16:         circular_buffer<T, Alloc>::push_front(item);
Chris@16:     }
Chris@16: 
Chris@16:     //! Insert a new element at the beginning of the space optimized circular buffer.
Chris@16:     /*!
Chris@16:         \post if <code>capacity().%capacity() > 0</code> then <code>front() == item</code><br>
Chris@16:               If the <code>circular_buffer_space_optimized</code> is full, the last element will be removed. If the
Chris@16:               capacity is <code>0</code>, nothing will be inserted.<br><br>
Chris@16:               The amount of allocated memory in the internal buffer may be predictively increased.
Chris@16:         \param item The element to be inserted.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept.
Chris@16:         \par Exception Safety
Chris@16:              Basic.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
Chris@16:              equal to <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in the size of the <code>circular_buffer_space_optimized</code>).
Chris@16:         \sa <code>\link push_back() push_back(const_reference)\endlink</code>, <code>pop_back()</code>,
Chris@16:             <code>pop_front()</code>
Chris@16:     */
Chris@16:     void push_front(rvalue_type item) {
Chris@16:         check_low_capacity();
Chris@16:         circular_buffer<T, Alloc>::push_front(boost::move(item));
Chris@16:     }
Chris@16: 
Chris@16:     //! Insert a new element at the beginning of the space optimized circular buffer.
Chris@16:     /*!
Chris@16:         \post if <code>capacity().%capacity() > 0</code> then <code>front() == item</code><br>
Chris@16:               If the <code>circular_buffer_space_optimized</code> is full, the last element will be removed. If the
Chris@16:               capacity is <code>0</code>, nothing will be inserted.<br><br>
Chris@16:               The amount of allocated memory in the internal buffer may be predictively increased.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T()</code> throws.
Chris@16:                 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept.
Chris@16:         \par Exception Safety
Chris@16:              Basic.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
Chris@16:              equal to <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in the size of the <code>circular_buffer_space_optimized</code>).
Chris@16:         \sa <code>\link push_back() push_back(const_reference)\endlink</code>, <code>pop_back()</code>,
Chris@16:             <code>pop_front()</code>
Chris@16:     */
Chris@16:     void push_front() {
Chris@16:         check_low_capacity();
Chris@16:         circular_buffer<T, Alloc>::push_front();
Chris@16:     }
Chris@16: 
Chris@16:     //! Remove the last element from the space optimized circular buffer.
Chris@16:     /*!
Chris@16:         \pre <code>!empty()</code>
Chris@16:         \post The last element is removed from the <code>circular_buffer_space_optimized</code>.<br><br>
Chris@16:               The amount of allocated memory in the internal buffer may be predictively decreased.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:         \par Exception Safety
Chris@16:              Basic.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
Chris@16:              equal to <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in the size of the <code>circular_buffer_space_optimized</code>).
Chris@16:         \sa <code>pop_front()</code>, <code>\link push_back() push_back(const_reference)\endlink</code>,
Chris@16:             <code>\link push_front() push_front(const_reference)\endlink</code>
Chris@16:     */
Chris@16:     void pop_back() {
Chris@16:         circular_buffer<T, Alloc>::pop_back();
Chris@16:         check_high_capacity();
Chris@16:     }
Chris@16: 
Chris@16:     //! Remove the first element from the space optimized circular buffer.
Chris@16:     /*!
Chris@16:         \pre <code>!empty()</code>
Chris@16:         \post The first element is removed from the <code>circular_buffer_space_optimized</code>.<br><br>
Chris@16:               The amount of allocated memory in the internal buffer may be predictively decreased.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:         \par Exception Safety
Chris@16:              Basic.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
Chris@16:              equal to <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in the size of the <code>circular_buffer_space_optimized</code>).
Chris@16:         \sa <code>pop_back()</code>, <code>\link push_back() push_back(const_reference)\endlink</code>,
Chris@16:             <code>\link push_front() push_front(const_reference)\endlink</code>
Chris@16:     */
Chris@16:     void pop_front() {
Chris@16:         circular_buffer<T, Alloc>::pop_front();
Chris@16:         check_high_capacity();
Chris@16:     }
Chris@16: 
Chris@16:     //! Insert an element at the specified position.
Chris@16:     /*!
Chris@16:         \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> or its
Chris@16:              end.
Chris@16:         \post The <code>item</code> will be inserted at the position <code>pos</code>.<br>
Chris@16:               If the <code>circular_buffer_space_optimized</code> is full, the first element will be overwritten. If
Chris@16:               the <code>circular_buffer_space_optimized</code> is full and the <code>pos</code> points to
Chris@16:               <code>begin()</code>, then the <code>item</code> will not be inserted. If the capacity is <code>0</code>,
Chris@16:               nothing will be inserted.<br><br>
Chris@16:               The amount of allocated memory in the internal buffer may be predictively increased.
Chris@16:         \param pos An iterator specifying the position where the <code>item</code> will be inserted.
Chris@16:         \param item The element to be inserted.
Chris@16:         \return Iterator to the inserted element or <code>begin()</code> if the <code>item</code> is not inserted. (See
Chris@16:                 the <i>Effect</i>.)
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T(const T&)</code> throws.
Chris@16:                 Whatever <code>T::operator = (const T&)</code> throws.
Chris@16:         \par Exception Safety
Chris@16:              Basic.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
Chris@16:              equal to <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in the size of the <code>circular_buffer_space_optimized</code>).
Chris@16:         \sa <code>\link insert(iterator, size_type, param_value_type)
Chris@16:             insert(iterator, size_type, value_type)\endlink</code>,
Chris@16:             <code>insert(iterator, InputIterator, InputIterator)</code>,
Chris@16:             <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>,
Chris@16:             <code>\link rinsert(iterator, size_type, param_value_type)
Chris@16:             rinsert(iterator, size_type, value_type)\endlink</code>,
Chris@16:             <code>rinsert(iterator, InputIterator, InputIterator)</code>
Chris@16:     */
Chris@16:     iterator insert(iterator pos, param_value_type item) {
Chris@16:         size_type index = pos - begin();
Chris@16:         check_low_capacity();
Chris@16:         return circular_buffer<T, Alloc>::insert(begin() + index, item);
Chris@16:     }
Chris@16: 
Chris@16:     //! Insert an element at the specified position.
Chris@16:     /*!
Chris@16:         \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> or its
Chris@16:              end.
Chris@16:         \post The <code>item</code> will be inserted at the position <code>pos</code>.<br>
Chris@16:               If the <code>circular_buffer_space_optimized</code> is full, the first element will be overwritten. If
Chris@16:               the <code>circular_buffer_space_optimized</code> is full and the <code>pos</code> points to
Chris@16:               <code>begin()</code>, then the <code>item</code> will not be inserted. If the capacity is <code>0</code>,
Chris@16:               nothing will be inserted.<br><br>
Chris@16:               The amount of allocated memory in the internal buffer may be predictively increased.
Chris@16:         \param pos An iterator specifying the position where the <code>item</code> will be inserted.
Chris@16:         \param item The element to be inserted.
Chris@16:         \return Iterator to the inserted element or <code>begin()</code> if the <code>item</code> is not inserted. (See
Chris@16:                 the <i>Effect</i>.)
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept.
Chris@16:         \par Exception Safety
Chris@16:              Basic.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
Chris@16:              equal to <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in the size of the <code>circular_buffer_space_optimized</code>).
Chris@16:         \sa <code>\link insert(iterator, size_type, param_value_type)
Chris@16:             insert(iterator, size_type, value_type)\endlink</code>,
Chris@16:             <code>insert(iterator, InputIterator, InputIterator)</code>,
Chris@16:             <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>,
Chris@16:             <code>\link rinsert(iterator, size_type, param_value_type)
Chris@16:             rinsert(iterator, size_type, value_type)\endlink</code>,
Chris@16:             <code>rinsert(iterator, InputIterator, InputIterator)</code>
Chris@16:     */
Chris@16:     iterator insert(iterator pos, rvalue_type item) {
Chris@16:         size_type index = pos - begin();
Chris@16:         check_low_capacity();
Chris@16:         return circular_buffer<T, Alloc>::insert(begin() + index, boost::move(item));
Chris@16:     }
Chris@16: 
Chris@16:     //! Insert an element at the specified position.
Chris@16:     /*!
Chris@16:         \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> or its
Chris@16:              end.
Chris@16:         \post The <code>item</code> will be inserted at the position <code>pos</code>.<br>
Chris@16:               If the <code>circular_buffer_space_optimized</code> is full, the first element will be overwritten. If
Chris@16:               the <code>circular_buffer_space_optimized</code> is full and the <code>pos</code> points to
Chris@16:               <code>begin()</code>, then the <code>item</code> will not be inserted. If the capacity is <code>0</code>,
Chris@16:               nothing will be inserted.<br><br>
Chris@16:               The amount of allocated memory in the internal buffer may be predictively increased.
Chris@16:         \param pos An iterator specifying the position where the <code>item</code> will be inserted.
Chris@16:         \return Iterator to the inserted element or <code>begin()</code> if the <code>item</code> is not inserted. (See
Chris@16:                 the <i>Effect</i>.)
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T()</code> throws.
Chris@16:                 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept.
Chris@16:         \par Exception Safety
Chris@16:              Basic.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
Chris@16:              equal to <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in the size of the <code>circular_buffer_space_optimized</code>).
Chris@16:         \sa <code>\link insert(iterator, size_type, param_value_type)
Chris@16:             insert(iterator, size_type, value_type)\endlink</code>,
Chris@16:             <code>insert(iterator, InputIterator, InputIterator)</code>,
Chris@16:             <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>,
Chris@16:             <code>\link rinsert(iterator, size_type, param_value_type)
Chris@16:             rinsert(iterator, size_type, value_type)\endlink</code>,
Chris@16:             <code>rinsert(iterator, InputIterator, InputIterator)</code>
Chris@16:     */
Chris@16:     iterator insert(iterator pos) {
Chris@16:         size_type index = pos - begin();
Chris@16:         check_low_capacity();
Chris@16:         return circular_buffer<T, Alloc>::insert(begin() + index);
Chris@16:     }
Chris@16: 
Chris@16:     //! Insert <code>n</code> copies of the <code>item</code> at the specified position.
Chris@16:     /*!
Chris@16:         \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> or its
Chris@16:              end.
Chris@16:         \post The number of <code>min[n, (pos - begin()) + reserve()]</code> elements will be inserted at the position
Chris@16:               <code>pos</code>.<br>The number of <code>min[pos - begin(), max[0, n - reserve()]]</code> elements will
Chris@16:               be overwritten at the beginning of the <code>circular_buffer_space_optimized</code>.<br>(See
Chris@16:               <i>Example</i> for the explanation.)<br><br>
Chris@16:               The amount of allocated memory in the internal buffer may be predictively increased.
Chris@16:         \param pos An iterator specifying the position where the <code>item</code>s will be inserted.
Chris@16:         \param n The number of <code>item</code>s the to be inserted.
Chris@16:         \param item The element whose copies will be inserted.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T(const T&)</code> throws.
Chris@16:                 Whatever <code>T::operator = (const T&)</code> throws.
Chris@16:         \par Exception Safety
Chris@16:              Basic.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
Chris@16:              equal to <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in <code>min[capacity().%capacity(), size() + n]</code>).
Chris@16:         \par Example
Chris@16:              Consider a <code>circular_buffer_space_optimized</code> with the capacity of 6 and the size of 4. Its
Chris@16:              internal buffer may look like the one below.<br><br>
Chris@16:              <code>|1|2|3|4| | |</code><br>
Chris@16:              <code>p ___^</code><br><br>After inserting 5 elements at the position <code>p</code>:<br><br>
Chris@16:              <code>insert(p, (size_t)5, 0);</code><br><br>actually only 4 elements get inserted and elements
Chris@16:              <code>1</code> and <code>2</code> are overwritten. This is due to the fact the insert operation preserves
Chris@16:              the capacity. After insertion the internal buffer looks like this:<br><br><code>|0|0|0|0|3|4|</code><br>
Chris@16:              <br>For comparison if the capacity would not be preserved the internal buffer would then result in
Chris@16:              <code>|1|2|0|0|0|0|0|3|4|</code>.
Chris@16:         \sa <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>,
Chris@16:             <code>insert(iterator, InputIterator, InputIterator)</code>,
Chris@16:             <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>,
Chris@16:             <code>\link rinsert(iterator, size_type, param_value_type)
Chris@16:             rinsert(iterator, size_type, value_type)\endlink</code>,
Chris@16:             <code>rinsert(iterator, InputIterator, InputIterator)</code>
Chris@16:     */
Chris@16:     void insert(iterator pos, size_type n, param_value_type item) {
Chris@16:         size_type index = pos - begin();
Chris@16:         check_low_capacity(n);
Chris@16:         circular_buffer<T, Alloc>::insert(begin() + index, n, item);
Chris@16:     }
Chris@16: 
Chris@16:     //! Insert the range <code>[first, last)</code> at the specified position.
Chris@16:     /*!
Chris@16:         \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> or its
Chris@16:              end.<br>Valid range <code>[first, last)</code> where <code>first</code> and <code>last</code> meet the
Chris@16:              requirements of an <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
Chris@16:         \post Elements from the range
Chris@16:               <code>[first + max[0, distance(first, last) - (pos - begin()) - reserve()], last)</code> will be
Chris@16:               inserted at the position <code>pos</code>.<br>The number of <code>min[pos - begin(), max[0,
Chris@16:               distance(first, last) - reserve()]]</code> elements will be overwritten at the beginning of the
Chris@16:               <code>circular_buffer_space_optimized</code>.<br>(See <i>Example</i> for the explanation.)<br><br>
Chris@16:               The amount of allocated memory in the internal buffer may be predictively increased.
Chris@16:         \param pos An iterator specifying the position where the range will be inserted.
Chris@16:         \param first The beginning of the range to be inserted.
Chris@16:         \param last The end of the range to be inserted.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept.
Chris@16:         \par Exception Safety
Chris@16:              Basic.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
Chris@16:              equal to <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in <code>[size() + std::distance(first, last)]</code>; in
Chris@16:              <code>min[capacity().%capacity(), size() + std::distance(first, last)]</code> if the
Chris@16:              <code>InputIterator</code> is a
Chris@16:              <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>).
Chris@16:         \par Example
Chris@16:              Consider a <code>circular_buffer_space_optimized</code> with the capacity of 6 and the size of 4. Its
Chris@16:              internal buffer may look like the one below.<br><br>
Chris@16:              <code>|1|2|3|4| | |</code><br>
Chris@16:              <code>p ___^</code><br><br>After inserting a range of elements at the position <code>p</code>:<br><br>
Chris@16:              <code>int array[] = { 5, 6, 7, 8, 9 };</code><br><code>insert(p, array, array + 5);</code><br><br>
Chris@16:              actually only elements <code>6</code>, <code>7</code>, <code>8</code> and <code>9</code> from the
Chris@16:              specified range get inserted and elements <code>1</code> and <code>2</code> are overwritten. This is due
Chris@16:              to the fact the insert operation preserves the capacity. After insertion the internal buffer looks like
Chris@16:              this:<br><br><code>|6|7|8|9|3|4|</code><br><br>For comparison if the capacity would not be preserved the
Chris@16:              internal buffer would then result in <code>|1|2|5|6|7|8|9|3|4|</code>.
Chris@16:         \sa <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>,
Chris@16:             <code>\link insert(iterator, size_type, param_value_type)
Chris@16:             insert(iterator, size_type, value_type)\endlink</code>, <code>\link rinsert(iterator, param_value_type)
Chris@16:             rinsert(iterator, value_type)\endlink</code>, <code>\link rinsert(iterator, size_type, param_value_type)
Chris@16:             rinsert(iterator, size_type, value_type)\endlink</code>,
Chris@16:             <code>rinsert(iterator, InputIterator, InputIterator)</code>
Chris@16:     */
Chris@16:     template <class InputIterator>
Chris@16:     void insert(iterator pos, InputIterator first, InputIterator last) {
Chris@16:         insert(pos, first, last, is_integral<InputIterator>());
Chris@16:     }
Chris@16: 
Chris@16:     //! Insert an element before the specified position.
Chris@16:     /*!
Chris@16:         \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> or its
Chris@16:              end.
Chris@16:         \post The <code>item</code> will be inserted before the position <code>pos</code>.<br>
Chris@16:               If the <code>circular_buffer_space_optimized</code> is full, the last element will be overwritten. If the
Chris@16:               <code>circular_buffer_space_optimized</code> is full and the <code>pos</code> points to
Chris@16:               <code>end()</code>, then the <code>item</code> will not be inserted. If the capacity is <code>0</code>,
Chris@16:               nothing will be inserted.<br><br>
Chris@16:               The amount of allocated memory in the internal buffer may be predictively increased.
Chris@16:         \param pos An iterator specifying the position before which the <code>item</code> will be inserted.
Chris@16:         \param item The element to be inserted.
Chris@16:         \return Iterator to the inserted element or <code>end()</code> if the <code>item</code> is not inserted. (See
Chris@16:                 the <i>Effect</i>.)
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T(const T&)</code> throws.
Chris@16:                 Whatever <code>T::operator = (const T&)</code> throws.
Chris@16:         \par Exception Safety
Chris@16:              Basic.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
Chris@16:              equal to <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in the size of the <code>circular_buffer_space_optimized</code>).
Chris@16:         \sa <code>\link rinsert(iterator, size_type, param_value_type)
Chris@16:             rinsert(iterator, size_type, value_type)\endlink</code>,
Chris@16:             <code>rinsert(iterator, InputIterator, InputIterator)</code>,
Chris@16:             <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>,
Chris@16:             <code>\link insert(iterator, size_type, param_value_type)
Chris@16:             insert(iterator, size_type, value_type)\endlink</code>,
Chris@16:             <code>insert(iterator, InputIterator, InputIterator)</code>
Chris@16:     */
Chris@16:     iterator rinsert(iterator pos, param_value_type item) {
Chris@16:         size_type index = pos - begin();
Chris@16:         check_low_capacity();
Chris@16:         return circular_buffer<T, Alloc>::rinsert(begin() + index, item);
Chris@16:     }
Chris@16: 
Chris@16:     //! Insert an element before the specified position.
Chris@16:     /*!
Chris@16:         \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> or its
Chris@16:              end.
Chris@16:         \post The <code>item</code> will be inserted before the position <code>pos</code>.<br>
Chris@16:               If the <code>circular_buffer_space_optimized</code> is full, the last element will be overwritten. If the
Chris@16:               <code>circular_buffer_space_optimized</code> is full and the <code>pos</code> points to
Chris@16:               <code>end()</code>, then the <code>item</code> will not be inserted. If the capacity is <code>0</code>,
Chris@16:               nothing will be inserted.<br><br>
Chris@16:               The amount of allocated memory in the internal buffer may be predictively increased.
Chris@16:         \param pos An iterator specifying the position before which the <code>item</code> will be inserted.
Chris@16:         \param item The element to be inserted.
Chris@16:         \return Iterator to the inserted element or <code>end()</code> if the <code>item</code> is not inserted. (See
Chris@16:                 the <i>Effect</i>.)
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept.
Chris@16:         \par Exception Safety
Chris@16:              Basic.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
Chris@16:              equal to <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in the size of the <code>circular_buffer_space_optimized</code>).
Chris@16:         \sa <code>\link rinsert(iterator, size_type, param_value_type)
Chris@16:             rinsert(iterator, size_type, value_type)\endlink</code>,
Chris@16:             <code>rinsert(iterator, InputIterator, InputIterator)</code>,
Chris@16:             <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>,
Chris@16:             <code>\link insert(iterator, size_type, param_value_type)
Chris@16:             insert(iterator, size_type, value_type)\endlink</code>,
Chris@16:             <code>insert(iterator, InputIterator, InputIterator)</code>
Chris@16:     */
Chris@16:     iterator rinsert(iterator pos, rvalue_type item) {
Chris@16:         size_type index = pos - begin();
Chris@16:         check_low_capacity();
Chris@16:         return circular_buffer<T, Alloc>::rinsert(begin() + index, boost::move(item));
Chris@16:     }
Chris@16: 
Chris@16:     //! Insert an element before the specified position.
Chris@16:     /*!
Chris@16:         \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> or its
Chris@16:              end.
Chris@16:         \post The <code>item</code> will be inserted before the position <code>pos</code>.<br>
Chris@16:               If the <code>circular_buffer_space_optimized</code> is full, the last element will be overwritten. If the
Chris@16:               <code>circular_buffer_space_optimized</code> is full and the <code>pos</code> points to
Chris@16:               <code>end()</code>, then the <code>item</code> will not be inserted. If the capacity is <code>0</code>,
Chris@16:               nothing will be inserted.<br><br>
Chris@16:               The amount of allocated memory in the internal buffer may be predictively increased.
Chris@16:         \param pos An iterator specifying the position before which the <code>item</code> will be inserted.
Chris@16:         \return Iterator to the inserted element or <code>end()</code> if the <code>item</code> is not inserted. (See
Chris@16:                 the <i>Effect</i>.)
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T()</code> throws.
Chris@16:                 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept.
Chris@16:         \par Exception Safety
Chris@16:              Basic.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
Chris@16:              equal to <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in the size of the <code>circular_buffer_space_optimized</code>).
Chris@16:         \sa <code>\link rinsert(iterator, size_type, param_value_type)
Chris@16:             rinsert(iterator, size_type, value_type)\endlink</code>,
Chris@16:             <code>rinsert(iterator, InputIterator, InputIterator)</code>,
Chris@16:             <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>,
Chris@16:             <code>\link insert(iterator, size_type, param_value_type)
Chris@16:             insert(iterator, size_type, value_type)\endlink</code>,
Chris@16:             <code>insert(iterator, InputIterator, InputIterator)</code>
Chris@16:     */
Chris@16:     iterator rinsert(iterator pos) {
Chris@16:         size_type index = pos - begin();
Chris@16:         check_low_capacity();
Chris@16:         return circular_buffer<T, Alloc>::rinsert(begin() + index);
Chris@16:     }
Chris@16: 
Chris@16:     //! Insert <code>n</code> copies of the <code>item</code> before the specified position.
Chris@16:     /*!
Chris@16:         \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> or its
Chris@16:              end.
Chris@16:         \post The number of <code>min[n, (end() - pos) + reserve()]</code> elements will be inserted before the
Chris@16:               position <code>pos</code>.<br>The number of <code>min[end() - pos, max[0, n - reserve()]]</code> elements
Chris@16:               will be overwritten at the end of the <code>circular_buffer_space_optimized</code>.<br>(See
Chris@16:               <i>Example</i> for the explanation.)<br><br>
Chris@16:               The amount of allocated memory in the internal buffer may be predictively increased.
Chris@16:         \param pos An iterator specifying the position where the <code>item</code>s will be inserted.
Chris@16:         \param n The number of <code>item</code>s the to be inserted.
Chris@16:         \param item The element whose copies will be inserted.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T(const T&)</code> throws.
Chris@16:                 Whatever <code>T::operator = (const T&)</code> throws.
Chris@16:         \par Exception Safety
Chris@16:              Basic.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
Chris@16:              equal to <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in <code>min[capacity().%capacity(), size() + n]</code>).
Chris@16:         \par Example
Chris@16:              Consider a <code>circular_buffer_space_optimized</code> with the capacity of 6 and the size of 4. Its
Chris@16:              internal buffer may look like the one below.<br><br>
Chris@16:              <code>|1|2|3|4| | |</code><br>
Chris@16:              <code>p ___^</code><br><br>After inserting 5 elements before the position <code>p</code>:<br><br>
Chris@16:              <code>rinsert(p, (size_t)5, 0);</code><br><br>actually only 4 elements get inserted and elements
Chris@16:              <code>3</code> and <code>4</code> are overwritten. This is due to the fact the rinsert operation preserves
Chris@16:              the capacity. After insertion the internal buffer looks like this:<br><br><code>|1|2|0|0|0|0|</code><br>
Chris@16:              <br>For comparison if the capacity would not be preserved the internal buffer would then result in
Chris@16:              <code>|1|2|0|0|0|0|0|3|4|</code>.
Chris@16:         \sa <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>,
Chris@16:             <code>rinsert(iterator, InputIterator, InputIterator)</code>,
Chris@16:             <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>,
Chris@16:             <code>\link insert(iterator, size_type, param_value_type)
Chris@16:             insert(iterator, size_type, value_type)\endlink</code>,
Chris@16:             <code>insert(iterator, InputIterator, InputIterator)</code>
Chris@16:     */
Chris@16:     void rinsert(iterator pos, size_type n, param_value_type item) {
Chris@16:         size_type index = pos - begin();
Chris@16:         check_low_capacity(n);
Chris@16:         circular_buffer<T, Alloc>::rinsert(begin() + index, n, item);
Chris@16:     }
Chris@16: 
Chris@16:         //! Insert the range <code>[first, last)</code> before the specified position.
Chris@16:     /*!
Chris@16:         \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> or its
Chris@16:              end.<br>
Chris@16:              Valid range <code>[first, last)</code> where <code>first</code> and <code>last</code> meet the
Chris@16:              requirements of an <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
Chris@16:         \post Elements from the range
Chris@16:               <code>[first, last - max[0, distance(first, last) - (end() - pos) - reserve()])</code> will be inserted
Chris@16:               before the position <code>pos</code>.<br>The number of <code>min[end() - pos, max[0,
Chris@16:               distance(first, last) - reserve()]]</code> elements will be overwritten at the end of the
Chris@16:               <code>circular_buffer</code>.<br>(See <i>Example</i> for the explanation.)<br><br>
Chris@16:               The amount of allocated memory in the internal buffer may be predictively increased.
Chris@16:         \param pos An iterator specifying the position where the range will be inserted.
Chris@16:         \param first The beginning of the range to be inserted.
Chris@16:         \param last The end of the range to be inserted.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::T(const T&)</code> throws.
Chris@16:                 Whatever <code>T::operator = (const T&)</code> throws.
Chris@16:         \par Exception Safety
Chris@16:              Basic.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
Chris@16:              equal to <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in <code>[size() + std::distance(first, last)]</code>; in
Chris@16:              <code>min[capacity().%capacity(), size() + std::distance(first, last)]</code> if the
Chris@16:              <code>InputIterator</code> is a
Chris@16:              <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>).
Chris@16:         \par Example
Chris@16:              Consider a <code>circular_buffer_space_optimized</code> with the capacity of 6 and the size of 4. Its
Chris@16:              internal buffer may look like the one below.<br><br>
Chris@16:              <code>|1|2|3|4| | |</code><br>
Chris@16:              <code>p ___^</code><br><br>After inserting a range of elements before the position <code>p</code>:<br><br>
Chris@16:              <code>int array[] = { 5, 6, 7, 8, 9 };</code><br><code>insert(p, array, array + 5);</code><br><br>
Chris@16:              actually only elements <code>5</code>, <code>6</code>, <code>7</code> and <code>8</code> from the
Chris@16:              specified range get inserted and elements <code>3</code> and <code>4</code> are overwritten. This is due
Chris@16:              to the fact the rinsert operation preserves the capacity. After insertion the internal buffer looks like
Chris@16:              this:<br><br><code>|1|2|5|6|7|8|</code><br><br>For comparison if the capacity would not be preserved the
Chris@16:              internal buffer would then result in <code>|1|2|5|6|7|8|9|3|4|</code>.
Chris@16:         \sa <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>,
Chris@16:             <code>\link rinsert(iterator, size_type, param_value_type)
Chris@16:             rinsert(iterator, size_type, value_type)\endlink</code>, <code>\link insert(iterator, param_value_type)
Chris@16:             insert(iterator, value_type)\endlink</code>, <code>\link insert(iterator, size_type, param_value_type)
Chris@16:             insert(iterator, size_type, value_type)\endlink</code>,
Chris@16:             <code>insert(iterator, InputIterator, InputIterator)</code>
Chris@16:     */
Chris@16:     template <class InputIterator>
Chris@16:     void rinsert(iterator pos, InputIterator first, InputIterator last) {
Chris@16:         rinsert(pos, first, last, is_integral<InputIterator>());
Chris@16:     }
Chris@16: 
Chris@16:     //! Remove an element at the specified position.
Chris@16:     /*!
Chris@16:         \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> (but not
Chris@16:              an <code>end()</code>).
Chris@16:         \post The element at the position <code>pos</code> is removed.<br><br>
Chris@16:               The amount of allocated memory in the internal buffer may be predictively decreased.
Chris@16:         \param pos An iterator pointing at the element to be removed.
Chris@16:         \return Iterator to the first element remaining beyond the removed element or <code>end()</code> if no such
Chris@16:                 element exists.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::operator = (const T&)</code> throws or 
Chris@16:                 nothing if <code>T::operator = (T&&)</code> is noexcept.
Chris@16:         \par Exception Safety
Chris@16:              Basic.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
Chris@16:              equal to <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in the size of the <code>circular_buffer_space_optimized</code>).
Chris@16:         \sa <code>erase(iterator, iterator)</code>, <code>rerase(iterator)</code>,
Chris@16:             <code>rerase(iterator, iterator)</code>, <code>clear()</code>
Chris@16:     */
Chris@16:     iterator erase(iterator pos) {
Chris@16:         iterator it = circular_buffer<T, Alloc>::erase(pos);
Chris@16:         size_type index = it - begin();
Chris@16:         check_high_capacity();
Chris@16:         return begin() + index;
Chris@16:     }
Chris@16: 
Chris@16:     //! Erase the range <code>[first, last)</code>.
Chris@16:     /*!
Chris@16:         \pre Valid range <code>[first, last)</code>.
Chris@16:         \post The elements from the range <code>[first, last)</code> are removed. (If <code>first == last</code>
Chris@16:               nothing is removed.)<br><br>
Chris@16:               The amount of allocated memory in the internal buffer may be predictively decreased.
Chris@16:         \param first The beginning of the range to be removed.
Chris@16:         \param last The end of the range to be removed.
Chris@16:         \return Iterator to the first element remaining beyond the removed elements or <code>end()</code> if no such
Chris@16:                 element exists.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::operator = (const T&)</code> throws or 
Chris@16:                 nothing if <code>T::operator = (T&&)</code> is noexcept.
Chris@16:         \par Exception Safety
Chris@16:              Basic.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
Chris@16:              equal to <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in the size of the <code>circular_buffer_space_optimized</code>).
Chris@16:         \sa <code>erase(iterator)</code>, <code>rerase(iterator)</code>, <code>rerase(iterator, iterator)</code>,
Chris@16:             <code>clear()</code>
Chris@16:     */
Chris@16:     iterator erase(iterator first, iterator last) {
Chris@16:         iterator it = circular_buffer<T, Alloc>::erase(first, last);
Chris@16:         size_type index = it - begin();
Chris@16:         check_high_capacity();
Chris@16:         return begin() + index;
Chris@16:     }
Chris@16: 
Chris@16:     //! Remove an element at the specified position.
Chris@16:     /*!
Chris@16:         \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> (but not
Chris@16:              an <code>end()</code>).<br><br>
Chris@16:               The amount of allocated memory in the internal buffer may be predictively decreased.
Chris@16:         \post The element at the position <code>pos</code> is removed.
Chris@16:         \param pos An iterator pointing at the element to be removed.
Chris@16:         \return Iterator to the first element remaining in front of the removed element or <code>begin()</code> if no
Chris@16:                 such element exists.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::operator = (const T&)</code> throws or 
Chris@16:                 nothing if <code>T::operator = (T&&)</code> is noexcept.
Chris@16:         \par Exception Safety
Chris@16:              Basic.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
Chris@16:              equal to <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in the size of the <code>circular_buffer_space_optimized</code>).
Chris@16:         \note Basically there is no difference between <code>erase(iterator)</code> and this method. It is implemented
Chris@16:               only for consistency with the base <code>circular_buffer</code>.
Chris@16:         \sa <code>erase(iterator)</code>, <code>erase(iterator, iterator)</code>,
Chris@16:             <code>rerase(iterator, iterator)</code>, <code>clear()</code>
Chris@16:     */
Chris@16:     iterator rerase(iterator pos) {
Chris@16:         iterator it = circular_buffer<T, Alloc>::rerase(pos);
Chris@16:         size_type index = it - begin();
Chris@16:         check_high_capacity();
Chris@16:         return begin() + index;
Chris@16:     }
Chris@16: 
Chris@16:     //! Erase the range <code>[first, last)</code>.
Chris@16:     /*!
Chris@16:         \pre Valid range <code>[first, last)</code>.
Chris@16:         \post The elements from the range <code>[first, last)</code> are removed. (If <code>first == last</code>
Chris@16:               nothing is removed.)<br><br>
Chris@16:               The amount of allocated memory in the internal buffer may be predictively decreased.
Chris@16:         \param first The beginning of the range to be removed.
Chris@16:         \param last The end of the range to be removed.
Chris@16:         \return Iterator to the first element remaining in front of the removed elements or <code>begin()</code> if no
Chris@16:                 such element exists.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:                 Whatever <code>T::operator = (const T&)</code> throws or 
Chris@16:                 nothing if <code>T::operator = (T&&)</code> is noexcept.
Chris@16:         \par Exception Safety
Chris@16:              Basic.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
Chris@16:              equal to <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in the size of the <code>circular_buffer_space_optimized</code>).
Chris@16:         \note Basically there is no difference between <code>erase(iterator, iterator)</code> and this method. It is
Chris@16:               implemented only for consistency with the base
Chris@16:               <code><circular_buffer</code>.
Chris@16:         \sa <code>erase(iterator)</code>, <code>erase(iterator, iterator)</code>, <code>rerase(iterator)</code>,
Chris@16:             <code>clear()</code>
Chris@16:     */
Chris@16:     iterator rerase(iterator first, iterator last) {
Chris@16:         iterator it = circular_buffer<T, Alloc>::rerase(first, last);
Chris@16:         size_type index = it - begin();
Chris@16:         check_high_capacity();
Chris@16:         return begin() + index;
Chris@16:     }
Chris@16: 
Chris@16:     //! Remove all stored elements from the space optimized circular buffer.
Chris@16:     /*!
Chris@16:         \post <code>size() == 0</code><br><br>
Chris@16:               The amount of allocated memory in the internal buffer may be predictively decreased.
Chris@16:         \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
Chris@16:                 used).
Chris@16:         \par Exception Safety
Chris@16:              Basic.
Chris@16:         \par Iterator Invalidation
Chris@16:              Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
Chris@16:              equal to <code>end()</code>).
Chris@16:         \par Complexity
Chris@16:              Linear (in the size of the <code>circular_buffer_space_optimized</code>).
Chris@16:         \sa <code>~circular_buffer_space_optimized()</code>, <code>erase(iterator)</code>,
Chris@16:             <code>erase(iterator, iterator)</code>, <code>rerase(iterator)</code>,
Chris@16:             <code>rerase(iterator, iterator)</code>
Chris@16:     */
Chris@16:     void clear() { erase(begin(), end()); }
Chris@16: 
Chris@16: private:
Chris@16: // Helper methods
Chris@16: 
Chris@16:     //! Adjust the amount of allocated memory.
Chris@16:     void adjust_min_capacity() {
Chris@16:         if (m_capacity_ctrl.min_capacity() > circular_buffer<T, Alloc>::capacity())
Chris@16:             circular_buffer<T, Alloc>::set_capacity(m_capacity_ctrl.min_capacity());
Chris@16:         else
Chris@16:             check_high_capacity();
Chris@16:     }
Chris@16: 
Chris@16:     //! Ensure the reserve for possible growth up.
Chris@16:     size_type ensure_reserve(size_type new_capacity, size_type buffer_size) const {
Chris@16:         if (buffer_size + new_capacity / 5 >= new_capacity)
Chris@16:             new_capacity *= 2; // ensure at least 20% reserve
Chris@16:         if (new_capacity > m_capacity_ctrl)
Chris@16:             return m_capacity_ctrl;
Chris@16:         return new_capacity;
Chris@16:     }
Chris@16: 
Chris@16:     //! Check for low capacity.
Chris@16:     /*
Chris@16:         \post If the capacity is low it will be increased.
Chris@16:     */
Chris@16:     void check_low_capacity(size_type n = 1) {
Chris@16:         size_type new_size = size() + n;
Chris@16:         size_type new_capacity = circular_buffer<T, Alloc>::capacity();
Chris@16:         if (new_size > new_capacity) {
Chris@16:             if (new_capacity == 0)
Chris@16:                 new_capacity = 1;
Chris@16:             for (; new_size > new_capacity; new_capacity *= 2) {}
Chris@16:             circular_buffer<T, Alloc>::set_capacity(
Chris@16:                 ensure_reserve(new_capacity, new_size));
Chris@16:         }
Chris@16: #if BOOST_CB_ENABLE_DEBUG
Chris@16:         this->invalidate_iterators_except(end());
Chris@16: #endif
Chris@16:     }
Chris@16: 
Chris@16:     //! Check for high capacity.
Chris@16:     /*
Chris@16:         \post If the capacity is high it will be decreased.
Chris@16:     */
Chris@16:     void check_high_capacity() {
Chris@16:         size_type new_capacity = circular_buffer<T, Alloc>::capacity();
Chris@16:         while (new_capacity / 3 >= size()) { // (new_capacity / 3) -> avoid oscillations
Chris@16:             new_capacity /= 2;
Chris@16:             if (new_capacity <= m_capacity_ctrl.min_capacity()) {
Chris@16:                 new_capacity = m_capacity_ctrl.min_capacity();
Chris@16:                 break;
Chris@16:             }
Chris@16:         }
Chris@16:         circular_buffer<T, Alloc>::set_capacity(
Chris@16:             ensure_reserve(new_capacity, size()));
Chris@16: #if BOOST_CB_ENABLE_DEBUG
Chris@16:         this->invalidate_iterators_except(end());
Chris@16: #endif
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized method for reducing the capacity.
Chris@16:     void reduce_capacity(const true_type&) {
Chris@16:         circular_buffer<T, Alloc>::set_capacity((std::max)(m_capacity_ctrl.min_capacity(), size()));
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized method for reducing the capacity.
Chris@16:     void reduce_capacity(const false_type&) {}
Chris@16: 
Chris@16:     //! Determine the initial capacity.
Chris@16:     static size_type init_capacity(const capacity_type& capacity_ctrl, size_type n) {
Chris@16:         BOOST_CB_ASSERT(capacity_ctrl.capacity() >= n); // check for capacity lower than n
Chris@16:         return (std::max)(capacity_ctrl.min_capacity(), n);
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized method for determining the initial capacity.
Chris@16:     template <class IntegralType>
Chris@16:     static size_type init_capacity(const capacity_type& capacity_ctrl, IntegralType n, IntegralType,
Chris@16:         const true_type&) {
Chris@16:         return init_capacity(capacity_ctrl, static_cast<size_type>(n));
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized method for determining the initial capacity.
Chris@16:     template <class Iterator>
Chris@16:     static size_type init_capacity(const capacity_type& capacity_ctrl, Iterator first, Iterator last,
Chris@16:         const false_type&) {
Chris@16:         BOOST_CB_IS_CONVERTIBLE(Iterator, value_type); // check for invalid iterator type
Chris@16: #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x581))
Chris@101:         return init_capacity(capacity_ctrl, first, last, iterator_category<Iterator>::type());
Chris@16: #else
Chris@16:         return init_capacity(
Chris@101:             capacity_ctrl, first, last, BOOST_DEDUCED_TYPENAME iterator_category<Iterator>::type());
Chris@16: #endif
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized method for determining the initial capacity.
Chris@16:     template <class InputIterator>
Chris@16:     static size_type init_capacity(const capacity_type& capacity_ctrl, InputIterator, InputIterator,
Chris@16:         const std::input_iterator_tag&) {
Chris@16:         return capacity_ctrl.capacity();
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized method for determining the initial capacity.
Chris@16:     template <class ForwardIterator>
Chris@16:     static size_type init_capacity(const capacity_type& capacity_ctrl, ForwardIterator first, ForwardIterator last,
Chris@16:         const std::forward_iterator_tag&) {
Chris@16:         BOOST_CB_ASSERT(std::distance(first, last) >= 0); // check for wrong range
Chris@16:         return (std::max)(capacity_ctrl.min_capacity(),
Chris@16:             (std::min)(capacity_ctrl.capacity(), static_cast<size_type>(std::distance(first, last))));
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized insert method.
Chris@16:     template <class IntegralType>
Chris@16:     void insert(const iterator& pos, IntegralType n, IntegralType item, const true_type&) {
Chris@16:         insert(pos, static_cast<size_type>(n), static_cast<value_type>(item));
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized insert method.
Chris@16:     template <class Iterator>
Chris@16:     void insert(const iterator& pos, Iterator first, Iterator last, const false_type&) {
Chris@16:         size_type index = pos - begin();
Chris@16:         check_low_capacity(std::distance(first, last));
Chris@16:         circular_buffer<T, Alloc>::insert(begin() + index, first, last);
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized rinsert method.
Chris@16:     template <class IntegralType>
Chris@16:     void rinsert(const iterator& pos, IntegralType n, IntegralType item, const true_type&) {
Chris@16:         rinsert(pos, static_cast<size_type>(n), static_cast<value_type>(item));
Chris@16:     }
Chris@16: 
Chris@16:     //! Specialized rinsert method.
Chris@16:     template <class Iterator>
Chris@16:     void rinsert(const iterator& pos, Iterator first, Iterator last, const false_type&) {
Chris@16:         size_type index = pos - begin();
Chris@16:         check_low_capacity(std::distance(first, last));
Chris@16:         circular_buffer<T, Alloc>::rinsert(begin() + index, first, last);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: // Non-member functions
Chris@16: 
Chris@16: //! Test two space optimized circular buffers for equality.
Chris@16: template <class T, class Alloc>
Chris@16: inline bool operator == (const circular_buffer_space_optimized<T, Alloc>& lhs,
Chris@16:     const circular_buffer_space_optimized<T, Alloc>& rhs) {
Chris@16:     return lhs.size() == rhs.size() &&
Chris@16:         std::equal(lhs.begin(), lhs.end(), rhs.begin());
Chris@16: }
Chris@16: 
Chris@16: //! Lexicographical comparison.
Chris@16: template <class T, class Alloc>
Chris@16: inline bool operator < (const circular_buffer_space_optimized<T, Alloc>& lhs,
Chris@16:     const circular_buffer_space_optimized<T, Alloc>& rhs) {
Chris@16:     return std::lexicographical_compare(
Chris@16:         lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
Chris@16: }
Chris@16: 
Chris@16: #if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING) || BOOST_WORKAROUND(BOOST_MSVC, BOOST_TESTED_AT(1310))
Chris@16: 
Chris@16: //! Test two space optimized circular buffers for non-equality.
Chris@16: template <class T, class Alloc>
Chris@16: inline bool operator != (const circular_buffer_space_optimized<T, Alloc>& lhs,
Chris@16:     const circular_buffer_space_optimized<T, Alloc>& rhs) {
Chris@16:     return !(lhs == rhs);
Chris@16: }
Chris@16: 
Chris@16: //! Lexicographical comparison.
Chris@16: template <class T, class Alloc>
Chris@16: inline bool operator > (const circular_buffer_space_optimized<T, Alloc>& lhs,
Chris@16:     const circular_buffer_space_optimized<T, Alloc>& rhs) {
Chris@16:     return rhs < lhs;
Chris@16: }
Chris@16: 
Chris@16: //! Lexicographical comparison.
Chris@16: template <class T, class Alloc>
Chris@16: inline bool operator <= (const circular_buffer_space_optimized<T, Alloc>& lhs,
Chris@16:     const circular_buffer_space_optimized<T, Alloc>& rhs) {
Chris@16:     return !(rhs < lhs);
Chris@16: }
Chris@16: 
Chris@16: //! Lexicographical comparison.
Chris@16: template <class T, class Alloc>
Chris@16: inline bool operator >= (const circular_buffer_space_optimized<T, Alloc>& lhs,
Chris@16:     const circular_buffer_space_optimized<T, Alloc>& rhs) {
Chris@16:     return !(lhs < rhs);
Chris@16: }
Chris@16: 
Chris@16: //! Swap the contents of two space optimized circular buffers.
Chris@16: template <class T, class Alloc>
Chris@16: inline void swap(circular_buffer_space_optimized<T, Alloc>& lhs,
Chris@16:     circular_buffer_space_optimized<T, Alloc>& rhs) BOOST_NOEXCEPT {
Chris@16:     lhs.swap(rhs);
Chris@16: }
Chris@16: 
Chris@16: #endif // #if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING) || BOOST_WORKAROUND(BOOST_MSVC, BOOST_TESTED_AT(1310))
Chris@16: 
Chris@16: } // namespace boost
Chris@16: 
Chris@16: #endif // #if !defined(BOOST_CIRCULAR_BUFFER_SPACE_OPTIMIZED_HPP)