/*

 *

 * Copyright (c) 1994

 * Hewlett-Packard Company

 *

 * Copyright (c) 1996,1997

 * Silicon Graphics Computer Systems, Inc.

 *

 * Copyright (c) 1997

 * Moscow Center for SPARC Technology

 *

 * Copyright (c) 1999

 * Boris Fomitchev

 *

 * This material is provided "as is", with absolutely no warranty expressed

 * or implied. Any use is at your own risk.

 *

 * Permission to use or copy this software for any purpose is hereby granted

 * without fee, provided the above notices are retained on all copies.

 * Permission to modify the code and to distribute modified code is granted,

 * provided the above notices are retained, and a notice that the code was

 * modified is included with the above copyright notice.

 *

 */

#ifndef _STLP_DEQUE

#  define _STLP_DEQUE

#ifndef _STLP_OUTERMOST_HEADER_ID

#  define _STLP_OUTERMOST_HEADER_ID 0x22

#  include <stl/_prolog.h>

#endif

#ifndef _STLP_INTERNAL_ALGOBASE_H

#  include <stl/_algobase.h>

#endif

#ifndef _STLP_INTERNAL_ALLOC_H

#  include <stl/_alloc.h>

#endif

#ifndef _STLP_INTERNAL_ITERATOR_H

#  include <stl/_iterator.h>

#endif

#ifndef _STLP_INTERNAL_UNINITIALIZED_H

#  include <stl/_uninitialized.h>

#endif

#ifndef _STLP_RANGE_ERRORS_H

#  include <stl/_range_errors.h>

#endif

/* Class invariants:

 *  For any nonsingular iterator i:

 *    i.node is the address of an element in the map array.  The

 *      contents of i.node is a pointer to the beginning of a node.

 *    i.first == *(i.node)

 *    i.last  == i.first + node_size

 *    i.cur is a pointer in the range [i.first, i.last).  NOTE:

 *      the implication of this is that i.cur is always a dereferenceable

 *      pointer, even if i is a past-the-end iterator.

 *  Start and Finish are always nonsingular iterators.  NOTE: this means

 *    that an empty deque must have one node, and that a deque

 *    with N elements, where N is the buffer size, must have two nodes.

 *  For every node other than start.node and finish.node, every element

 *    in the node is an initialized object.  If start.node == finish.node,

 *    then [start.cur, finish.cur) are initialized objects, and

 *    the elements outside that range are uninitialized storage.  Otherwise,

 *    [start.cur, start.last) and [finish.first, finish.cur) are initialized

 *    objects, and [start.first, start.cur) and [finish.cur, finish.last)

 *    are uninitialized storage.

 *  [map, map + map_size) is a valid, non-empty range.

 *  [start.node, finish.node] is a valid range contained within

 *    [map, map + map_size).

 *  A pointer in the range [map, map + map_size) points to an allocated node

 *    if and only if the pointer is in the range [start.node, finish.node].

 */

_STLP_BEGIN_NAMESPACE

_STLP_MOVE_TO_PRIV_NAMESPACE

template <class _Tp>

struct _Deque_iterator_base

{

    static size_t _S_buffer_size()

      {

        const size_t blocksize = _MAX_BYTES;

        return (sizeof(_Tp) < blocksize ? (blocksize / sizeof(_Tp)) : 1);

      }

    typedef random_access_iterator_tag iterator_category;

    typedef typename remove_const<_Tp>::type value_type;

    typedef size_t size_type;

    typedef ptrdiff_t difference_type;

    typedef value_type** _Map_pointer;

    value_type* _M_cur;

    value_type* _M_first;

    value_type* _M_last;

    _Map_pointer _M_node;

    _Deque_iterator_base( value_type* __x, _Map_pointer __y ) :

        _M_cur(__x),

        _M_first(*__y),

        _M_last(*__y + _S_buffer_size()),

        _M_node(__y)

      { }

    _Deque_iterator_base() :

        _M_cur(0),

        _M_first(0),

        _M_last(0),

        _M_node(0)

      { }

// see comment in doc/README.evc4 and doc/README.evc8

#if defined (_STLP_MSVC) && (_STLP_MSVC <= 1401) && defined (MIPS) && defined (NDEBUG)

    _Deque_iterator_base(_Deque_iterator_base const& __other) :

        _M_cur(__other._M_cur),

        _M_first(__other._M_first),

        _M_last(__other._M_last),

        _M_node(__other._M_node)

      { }

#endif

    difference_type _M_subtract( const _Deque_iterator_base& __x ) const

      {

        return difference_type(_S_buffer_size()) * (_M_node - __x._M_node - 1) +

          (_M_cur - _M_first) + (__x._M_last - __x._M_cur);

      }

    void _M_increment()

      {

        if ( ++_M_cur == _M_last ) {

          _M_set_node( _M_node + 1 );

          _M_cur = _M_first;

        }

      }

    void _M_decrement()

      {

        if ( _M_cur == _M_first ) {

          _M_set_node( _M_node - 1 );

          _M_cur = _M_last;

        }

        --_M_cur;

      }

    void _M_advance( difference_type __n )

      {

        const size_t buffersize = _S_buffer_size();

        difference_type __offset = __n + (_M_cur - _M_first);

        if ( __offset >= 0 && __offset < difference_type(buffersize) ) {

          _M_cur += __n;

        } else {

          difference_type __node_offset = __offset > 0 ? __offset / buffersize

            : -difference_type((-__offset - 1) / buffersize) - 1;

          _M_set_node(_M_node + __node_offset);

          _M_cur = _M_first + (__offset - __node_offset * difference_type(buffersize));

        }

      }

    void _M_set_node( _Map_pointer __new_node )

      { _M_last = (_M_first = *(_M_node = __new_node)) + difference_type(_S_buffer_size()); }

};

template <class _Tp> struct _Deque_iterator;

template <class _Tp> struct _Deque_iterator<_Tp const>;

template <class _Tp>

struct _Deque_iterator :

    public _Deque_iterator_base<_Tp>

{

    typedef typename remove_const<_Tp>::type value_type;

    typedef value_type* pointer;

    typedef value_type& reference;

    typedef random_access_iterator_tag iterator_category;

    typedef size_t size_type;

    typedef ptrdiff_t difference_type;

    typedef value_type** _Map_pointer;

    typedef _Deque_iterator_base<_Tp> _Base;

    typedef _Deque_iterator<_Tp> _Self;

    _Deque_iterator( value_type* __x, _Map_pointer __y ) :

        _Deque_iterator_base<value_type>(__x,__y)

      { }

    _Deque_iterator()

      { }

    _Deque_iterator( const _Deque_iterator& ) = default;

    _Deque_iterator( _Deque_iterator&& ) = default;

    _Deque_iterator& operator =( const _Deque_iterator& ) = default;

    reference operator *() const

      { return *this->_M_cur; }

    const pointer operator ->() const

      { return &*this->_M_cur; }

    difference_type operator -( const _Deque_iterator& __x ) const

      { return this->_M_subtract(__x); }

    difference_type operator -( const _Deque_iterator<_Tp const>& __x ) const

      { return this->_M_subtract(__x); }

    _Self& operator ++()

      { this->_M_increment(); return *this; }

    _Self operator++(int)

      {

        _Self __tmp = *this;

        ++*this;

        return __tmp;

      }

    _Self& operator --()

      { this->_M_decrement(); return *this; }

    _Self operator--(int)

      {

        _Self __tmp = *this;

        --*this;

        return __tmp;

      }

    _Self& operator +=(difference_type __n)

      { this->_M_advance(__n); return *this; }

    _Self operator+(difference_type __n) const

      {

        _Self __tmp = *this;

        return __tmp += __n;

      }

    _Self& operator -=(difference_type __n)

      { return *this += -__n; }

    _Self operator -(difference_type __n) const

      {

        _Self __tmp = *this;

        return __tmp -= __n;

      }

    reference operator [](difference_type __n) const

      { return *(*this + __n); }

};

template <class _Tp>

struct _Deque_iterator<_Tp const> :

    public _Deque_iterator_base<_Tp>

{

    typedef _Tp value_type;

    typedef value_type const* pointer;

    typedef value_type const& reference;

    typedef random_access_iterator_tag iterator_category;

    typedef size_t size_type;

    typedef ptrdiff_t difference_type;

    typedef value_type** _Map_pointer;

    typedef _Deque_iterator_base<value_type const> _Base;

    typedef _Deque_iterator<value_type const> _Self;

    _Deque_iterator( value_type* __x, _Map_pointer __y ) :

        _Deque_iterator_base<value_type>(__x,__y)

      { }

    _Deque_iterator()

      { }

    _Deque_iterator( const _Deque_iterator& ) = default;

    _Deque_iterator( _Deque_iterator&& ) = default;

    _Deque_iterator( const _Deque_iterator<value_type>& x ) :

        _Deque_iterator_base<value_type>( static_cast<const _Deque_iterator_base<value_type>&>(x) )

      { }

    _Deque_iterator& operator =( const _Deque_iterator& ) = default;

    _Deque_iterator& operator =( const _Deque_iterator<value_type>& x )

      {

        static_cast<_Deque_iterator_base<value_type>&>(*this) = static_cast<const _Deque_iterator_base<value_type>&>(x);

        return *this;

      }

    reference operator *() const

      { return *this->_M_cur; }

    const pointer operator ->() const

      { return &*this->_M_cur; }

    difference_type operator-( const _Deque_iterator& __x ) const

      { return this->_M_subtract(__x); }

    difference_type operator-( const _Deque_iterator<_Tp>& __x ) const

      { return this->_M_subtract(__x); }

    _Self& operator ++()

      { this->_M_increment(); return *this; }

    _Self operator++(int)

      {

        _Self __tmp = *this;

        ++*this;

        return __tmp;

      }

    _Self& operator --()

      { this->_M_decrement(); return *this; }

    _Self operator--(int)

      {

        _Self __tmp = *this;

        --*this;

        return __tmp;

      }

    _Self& operator +=(difference_type __n)

      { this->_M_advance(__n); return *this; }

    _Self operator+(difference_type __n) const

      {

        _Self __tmp = *this;

        return __tmp += __n;

      }

    _Self& operator -=(difference_type __n)

      { return *this += -__n; }

    _Self operator -(difference_type __n) const

      {

        _Self __tmp = *this;

        return __tmp -= __n;

      }

    reference operator [](difference_type __n) const

      { return *(*this + __n); }

};

template <class _Tp>

inline _Deque_iterator<_Tp> _STLP_CALL operator +( ptrdiff_t __n,

                                                   const _Deque_iterator<_Tp>& __x )

{ return __x + __n; }

template <class _Tp>

inline bool _STLP_CALL operator ==( const _Deque_iterator_base<_Tp>& __x,

                                    const _Deque_iterator_base<_Tp>& __y )

{ return __x._M_cur == __y._M_cur; }

template <class _Tp>

inline bool _STLP_CALL operator <( const _Deque_iterator_base<_Tp>& __x,

                                   const _Deque_iterator_base<_Tp>& __y)

{

  return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);

}

template <class _Tp>

inline bool _STLP_CALL operator !=( const _Deque_iterator_base<_Tp>& __x,

                                    const _Deque_iterator_base<_Tp>& __y)

{ return __x._M_cur != __y._M_cur; }

template <class _Tp>

inline bool _STLP_CALL operator >( const _Deque_iterator_base<_Tp>& __x,

                                   const _Deque_iterator_base<_Tp>& __y )

{ return __y < __x; }

template <class _Tp>

inline bool  _STLP_CALL operator >=( const _Deque_iterator_base<_Tp>& __x,

                                     const _Deque_iterator_base<_Tp>& __y )

{ return !(__x < __y); }

template <class _Tp>

inline bool  _STLP_CALL operator <=( const _Deque_iterator_base<_Tp>& __x,

                                     const _Deque_iterator_base<_Tp>& __y )

{ return !(__y < __x); }

#if defined (_STLP_USE_PTR_SPECIALIZATIONS)

#  define deque _STLP_PTR_IMPL_NAME(deque)

#elif defined (_STLP_DEBUG)

#  define deque _STLP_NON_DBG_NAME(deque)

#else

_STLP_MOVE_TO_STD_NAMESPACE

#endif

template <class _Tp, class _Alloc = allocator<_Tp> >

class deque

{

  private:

    typedef deque<_Tp, _Alloc> _Self;

  public:                         // Basic types

    typedef _Tp value_type;

    typedef value_type* pointer;

    typedef const value_type* const_pointer;

    typedef value_type& reference;

    typedef const value_type& const_reference;

    typedef size_t size_type;

    typedef ptrdiff_t difference_type;

    typedef random_access_iterator_tag _Iterator_category;

    typedef _Alloc allocator_type;

  private:

    typedef _STLP_PRIV _STLP_alloc_proxy<size_t, allocator_type> _Alloc_proxy;

    typedef typename _Alloc::template rebind<_Tp*>::other _Map_alloc_type;

    typedef _STLP_PRIV _STLP_alloc_proxy<value_type**, _Map_alloc_type> _Map_alloc_proxy;

  public:                         // Iterators

    typedef _STLP_PRIV _Deque_iterator<typename remove_const<_Tp>::type> iterator;

    typedef _STLP_PRIV _Deque_iterator<typename add_const<_Tp>::type>    const_iterator;

    _STLP_DECLARE_RANDOM_ACCESS_REVERSE_ITERATORS;

  protected:                      // Internal typedefs

    typedef pointer* _Map_pointer;

    iterator _M_start;

    iterator _M_finish;

    _Map_alloc_proxy  _M_map;

    _Alloc_proxy      _M_map_size;

    static size_t _STLP_CALL buffer_size()

      { return _STLP_PRIV _Deque_iterator_base<_Tp>::_S_buffer_size(); }

    void _M_initialize_map(size_t);

    void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);

    void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);

    enum { _S_initial_map_size = 8 };

  public:                         // Basic accessors

    iterator begin()

      { return this->_M_start; }

    iterator end()

      { return this->_M_finish; }

    const_iterator begin() const

      { return const_iterator(this->_M_start); }

    const_iterator end() const

      { return const_iterator(this->_M_finish); }

    reverse_iterator rbegin()

      { return reverse_iterator(this->_M_finish); }

    reverse_iterator rend()

      { return reverse_iterator(this->_M_start); }

    const_reverse_iterator rbegin() const

      { return const_reverse_iterator(this->_M_finish); }

    const_reverse_iterator rend() const

      { return const_reverse_iterator(this->_M_start); }

    reference operator[](size_type __n)

      { return this->_M_start[difference_type(__n)]; }

    const_reference operator[](size_type __n) const

      { return this->_M_start[difference_type(__n)]; }

    void _M_range_check(size_type __n) const

      {

        if (__n >= this->size()) {

          __stl_throw_out_of_range("deque");

        }

      }

    reference at(size_type __n)

      { _M_range_check(__n); return (*this)[__n]; }

    const_reference at(size_type __n) const

      { _M_range_check(__n); return (*this)[__n]; }

    reference front()

      { return *this->_M_start; }

    reference back()

      {

        iterator __tmp = this->_M_finish;

        --__tmp;

        return *__tmp;

      }

    const_reference front() const

      { return *this->_M_start; }

    const_reference back() const

      {

        const_iterator __tmp = this->_M_finish;

        --__tmp;

        return *__tmp;

      }

    size_type size() const

      { return this->_M_finish - this->_M_start; }

    size_type max_size() const

      { return size_type(-1); }

    bool empty() const

      { return this->_M_finish == this->_M_start; }

    allocator_type get_allocator() const

      { return this->_M_map_size; }

  public:                         // Constructor, destructor.

    explicit deque(const allocator_type& __a = allocator_type()) :

        _M_start(),

        _M_finish(),

        _M_map(__a, (value_type**)(0)),

        _M_map_size(__a, (size_t)0)

      { _M_initialize_map(0); }

    deque(const _Self& __x) :

        _M_start(),

        _M_finish(),

        _M_map(__x.get_allocator(), (value_type**)(0)),

        _M_map_size(__x.get_allocator(), (size_t)0)

      {

        _M_initialize_map(__x.size());

        uninitialized_copy(__x.begin(), __x.end(), this->_M_start);

      }

    deque(const _Self& __x, const allocator_type& __a ) :

        _M_start(),

        _M_finish(),

        _M_map(__a, (value_type**)(0)),

        _M_map_size(__a, (size_t)0)

      {

        _M_initialize_map(__x.size());

        uninitialized_copy(__x.begin(), __x.end(), this->_M_start);

      }

    explicit deque(size_type __n) :

        _M_start(),

        _M_finish(),

        _M_map(allocator_type(), (value_type**)(0)),

        _M_map_size(allocator_type(), (size_t)0)

      {

        _M_initialize_map(__n);

        /* _M_initialize(__n); */ _M_fill_initialize( _STLP_DEFAULT_CONSTRUCTED(_Tp) );

      }

    deque( size_type __n, const value_type& __val, const allocator_type& __a = allocator_type()) :

        _M_start(),

        _M_finish(),

        _M_map(__a, (value_type**)(0)),

        _M_map_size(__a, (size_t)0)

      {

        _M_initialize_map(__n);

        _M_fill_initialize( __val );

      }

  protected:

    template <class _Integer>

    void _M_initialize_dispatch( _Integer __n, _Integer __x, const true_type& )

      {

        this->_M_initialize_map(__n);

        _M_fill_initialize( __x );

      }

    template <class _InputIter>

    void _M_initialize_dispatch( _InputIter __first, _InputIter __last, const false_type& )

      { _M_range_initialize(__first, __last, typename iterator_traits<_InputIter>::iterator_category()); }

  public:

    // Check whether it's an integral type.  If so, it's not an iterator.

    template <class _InputIterator>

    deque( _InputIterator __first, _InputIterator __last, const allocator_type& __a = allocator_type() ) :

        _M_start(),

        _M_finish(),

        _M_map(__a, (value_type**)(0)),

        _M_map_size(__a, (size_t)0)

      { _M_initialize_dispatch(__first, __last, typename is_integral<_InputIterator>::type() ); }

    deque( deque&& __x ) :

        _M_start(__x._M_start),

        _M_finish(__x._M_finish),

        _M_map(__x.get_allocator(), (value_type**)(0)),

        _M_map_size(__x.get_allocator(), (size_t)0)

      {

        _STLP_STD::swap( _M_map._M_data, __x._M_map._M_data);

        _STLP_STD::swap( _M_map_size._M_data, __x._M_map_size._M_data);

        __x._M_finish = __x._M_start;

      }

    deque( deque&& __x, const allocator_type& __a ) :

        _M_start(),

        _M_finish(),

        _M_map(__a, (value_type**)(0)),

        _M_map_size(__a, (size_t)0)

      {

        if ( __x.get_allocator() == __a ) {

          _M_start = __x._M_start;

          _M_finish = __x._M_finish;

          _STLP_STD::swap( _M_map._M_data, __x._M_map._M_data);

          _STLP_STD::swap( _M_map_size._M_data, __x._M_map_size._M_data);

          __x._M_finish = __x._M_start;          

        } else {

          _M_initialize_map(__x._M_finish - __x._M_start);

          uninitialized_copy(__x._M_start, __x._M_finish, this->_M_start);

          if (__x._M_map._M_data) {

            __x._M_destroy_nodes(_M_start._M_node, this->_M_finish._M_node + 1);

            __x._M_map.deallocate(__x._M_map._M_data, __x._M_map_size._M_data);

            __x._M_finish = __x._M_start;

            __x._M_map._M_data = 0;

            __x._M_map_size._M_data = 0;

          }

        }

      }

    ~deque()

      {

        _STLP_STD::detail::_Destroy_Range(this->_M_start, this->_M_finish);

        if (_M_map._M_data) {

          _M_destroy_nodes(_M_start._M_node, this->_M_finish._M_node + 1);

          _M_map.deallocate(_M_map._M_data, _M_map_size._M_data);

        }

      }

    _Self& operator =(const _Self& __x);

    _Self& operator =(_Self&& __x);

    void swap(_Self& __x)

      {

        _STLP_STD::swap(this->_M_start, __x._M_start);

        _STLP_STD::swap(this->_M_finish, __x._M_finish);

        // this->_M_map.swap(__x._M_map);

        _STLP_STD::swap( this->_M_map, __x._M_map );

        // this->_M_map_size.swap(__x._M_map_size);

        _STLP_STD::swap( this->_M_map_size, __x._M_map_size );

      }

#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)

    void _M_swap_workaround(_Self& __x)

      { swap(__x); }

#endif

  public:

    // assign(), a generalized assignment member function.  Two

    // versions: one that takes a count, and one that takes a range.

    // The range version is a member template, so we dispatch on whether

    // or not the type is an integer.

    void _M_fill_assign(size_type __n, const _Tp& __val)

      {

        if (__n > size()) {

          _STLP_STD::fill(begin(), end(), __val);

          insert(end(), __n - size(), __val);

        } else {

          erase(begin() + __n, end());

          _STLP_STD::fill(begin(), end(), __val);

        }

      }

    void assign(size_type __n, const _Tp& __val)

      { _M_fill_assign(__n, __val); }

    template <class _InputIterator>

    void assign(_InputIterator __first, _InputIterator __last)

      {

         typedef typename is_integral<_InputIterator>::type _Integral;

         _M_assign_dispatch(__first, __last, _Integral());

      }

  private:                        // helper functions for assign()

    template <class _Integer>

    void _M_assign_dispatch( _Integer __n, _Integer __val, const true_type& /*_IsIntegral*/)

      { _M_fill_assign((size_type) __n, (_Tp) __val); }

    template <class _InputIterator>

    void _M_assign_dispatch( _InputIterator __first, _InputIterator __last,

                             const false_type& /*_IsIntegral*/)

      { _M_assign_aux(__first, __last, typename iterator_traits<_InputIterator>::iterator_category()); }

    template <class _InputIter>

    void _M_assign_aux( _InputIter __first, _InputIter __last, const input_iterator_tag& )

      {

         iterator __cur = begin();

         for ( ; __first != __last && __cur != end(); ++__cur, ++__first) {

           *__cur = *__first;

         }

         if (__first == __last) {

           erase(__cur, end());

         } else {

           insert(end(), __first, __last);

         }

      }

    template <class _ForwardIterator>

    void _M_assign_aux( _ForwardIterator __first, _ForwardIterator __last, const forward_iterator_tag& )

      {

        size_type __len = _STLP_STD::distance(__first, __last);

        if (__len > size()) {

          _ForwardIterator __mid = __first;

          _STLP_STD::advance(__mid, size());

          _STLP_STD::copy(__first, __mid, begin());

          insert(end(), __mid, __last);

        } else {

          erase(_STLP_STD::copy(__first, __last, begin()), end());

        }

      }

  public:                         // push_* and pop_*

    void push_back( const value_type& __t )

      {

        if (this->_M_finish._M_cur != this->_M_finish._M_last - 1) {

          _Self::get_allocator().construct( this->_M_finish._M_cur, __t );

          ++this->_M_finish._M_cur;

        } else {

          _M_push_back_aux_v(__t);

        }

      }

    void push_front( const value_type& __t )

      {

        if (this->_M_start._M_cur != this->_M_start._M_first) {

          _Self::get_allocator().construct( this->_M_start._M_cur - 1, __t );

          --this->_M_start._M_cur;

        } else {

          _M_push_front_aux_v(__t);

        }

      }

    void pop_back()

      {

        if (this->_M_finish._M_cur != this->_M_finish._M_first) {

          --this->_M_finish._M_cur;

          _Self::get_allocator().destroy( this->_M_finish._M_cur );

        } else {

          _M_pop_back_aux();

          _Self::get_allocator().destroy( this->_M_finish._M_cur );

        }

      }

    void pop_front()

      {

        _Self::get_allocator().destroy( this->_M_start._M_cur );

        _M_pop_front_aux();

      }

  public:                         // Insert

    iterator insert( iterator __pos, const value_type& __x )

      {

        if (__pos._M_cur == this->_M_start._M_cur) {

          push_front(__x);

          return this->_M_start;

        } else if (__pos._M_cur == this->_M_finish._M_cur) {

          push_back(__x);

          iterator __tmp = this->_M_finish;

          --__tmp;

          return __tmp;

        } else {

          return _M_fill_insert_aux(__pos, 1, __x, /* _Movable() */ true_type() );

        }

      }

    void insert(iterator __pos, size_type __n, const value_type& __x)

      { _M_fill_insert(__pos, __n, __x); }

  protected:

    iterator _M_fill_insert_aux(iterator __pos, size_type __n, const value_type& __x, const true_type& /*_Movable*/);

    iterator _M_fill_insert_aux(iterator __pos, size_type __n, const value_type& __x, const false_type& /*_Movable*/);

    void _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);

    template <class _Integer>

    void _M_insert_dispatch( iterator __pos, _Integer __n, _Integer __x,

                             const true_type& /*_IsIntegral*/)

      { _M_fill_insert(__pos, (size_type) __n, (value_type) __x); }

    template <class _InputIterator>

    void _M_insert_dispatch( iterator __pos, _InputIterator __first, _InputIterator __last,

                             const false_type& /*_IsIntegral*/)

      { _M_insert(__pos, __first, __last, typename iterator_traits<_InputIterator>::iterator_category()); }

  public:

    // Check whether it's an integral type.  If so, it's not an iterator.

    template <class _InputIterator>

    void insert( iterator __pos, _InputIterator __first, _InputIterator __last )

      {

        typedef typename is_integral<_InputIterator>::type _Integral;

        _M_insert_dispatch(__pos, __first, __last, _Integral());

      }

  public:

    void resize(size_type __new_size, const value_type& __x)

      {

        const size_type __len = size();

        if (__new_size < __len) {

          erase(this->_M_start + __new_size, this->_M_finish);

        } else {

          insert(this->_M_finish, __new_size - __len, __x);

        }

      }

  protected:

    iterator _M_erase(iterator __pos, const true_type& /*_Movable*/);

    iterator _M_erase(iterator __pos, const false_type& /*_Movable*/);

    iterator _M_erase(iterator __first, iterator __last, const true_type& /*_Movable*/);

    iterator _M_erase(iterator __first, iterator __last, const false_type& /*_Movable*/);

  public:                         // Erase

    iterator erase(iterator __pos)

      {

        return _M_erase(__pos, /* _Movable() */ typename is_trivially_move_constructible<value_type>::type() );

      }

    iterator erase(iterator __first, iterator __last)

      {

        if (__first == this->_M_start && __last == this->_M_finish) {

          clear();

          return this->_M_finish;

        } else {

          if (__first == __last) {

            return __first;

          }

          return _M_erase(__first, __last, /* _Movable() */ false_type() );

        }

      }

    void clear();

  protected:                        // Internal construction/destruction

    void _M_fill_initialize( const value_type& __val );

    template <class _InputIterator>

    void _M_range_initialize( _InputIterator __first, _InputIterator __last,

                              const input_iterator_tag& )

      {

        this->_M_initialize_map(0);

        _STLP_TRY {

          for ( ; __first != __last; ++__first) {

            push_back(*__first);

          }

        }

        _STLP_UNWIND(clear())

      }

    template <class _ForwardIterator>

    void  _M_range_initialize( _ForwardIterator __first, _ForwardIterator __last,

                               const forward_iterator_tag& )

      {

        size_type __n = _STLP_STD::distance(__first, __last);

        this->_M_initialize_map(__n);

        _Map_pointer __cur_node = this->_M_start._M_node;

        _STLP_TRY {

          for (; __cur_node < this->_M_finish._M_node; ++__cur_node) {

            _ForwardIterator __mid = __first;

            _STLP_STD::advance(__mid, this->buffer_size());

            _STLP_STD::uninitialized_copy(__first, __mid, *__cur_node);

            __first = __mid;

          }

          _STLP_STD::uninitialized_copy(__first, __last, this->_M_finish._M_first);

        }

        _STLP_UNWIND(_STLP_STD::detail::_Destroy_Range(this->_M_start, iterator(*__cur_node, __cur_node)))

      }

  protected:                        // Internal push_* and pop_*

    void _M_push_back_aux_v(const value_type&);

    void _M_push_front_aux_v(const value_type&);

    void _M_pop_back_aux();

    void _M_pop_front_aux();

  protected:                        // Internal insert functions

    template <class _InputIterator>

    void _M_insert( iterator __pos, _InputIterator __first, _InputIterator __last,

                    const input_iterator_tag& )

      { _STLP_STD::copy(__first, __last, inserter(*this, __pos)); }

    template <class _ForwardIterator>

    void  _M_insert( iterator __pos,

                     _ForwardIterator __first, _ForwardIterator __last,

                     const forward_iterator_tag& )

      {

        size_type __n = _STLP_STD::distance(__first, __last);

        if (__pos._M_cur == this->_M_start._M_cur) {

          iterator __new_start = _M_reserve_elements_at_front(__n);

          _STLP_TRY {

            uninitialized_copy(__first, __last, __new_start);

            this->_M_start = __new_start;

          }

          _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))

        } else if (__pos._M_cur == this->_M_finish._M_cur) {

          iterator __new_finish = _M_reserve_elements_at_back(__n);

          _STLP_TRY {

            uninitialized_copy(__first, __last, this->_M_finish);

            this->_M_finish = __new_finish;

          }

          _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))

        } else {

          _M_insert_range_aux(__pos, __first, __last, __n, /* _Movable() */ true_type() );

        }

      }

    template <class _ForwardIterator>

    void _M_insert_range_aux( iterator __pos,

                              _ForwardIterator __first, _ForwardIterator __last,

                              size_type __n, const false_type& /*_Movable*/)

      {

        const difference_type __elemsbefore = __pos - this->_M_start;

        size_type __length = size();

        if (__elemsbefore <= difference_type(__length / 2)) {

          iterator __new_start = _M_reserve_elements_at_front(__n);

          __pos = this->_M_start + __elemsbefore;

          _STLP_TRY {

            iterator __dst = __new_start;

            iterator __src = this->_M_start;

            for (; __src != __pos; ++__dst, ++__src) {

              _Self::get_allocator().construct( &(*__dst), _STLP_STD::move(*__src) );

              _Self::get_allocator().destroy( &(*__src) );

            }

            this->_M_start = __new_start;

            uninitialized_copy(__first, __last, __dst);

          }

          _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))

        } else {

          iterator __new_finish = _M_reserve_elements_at_back(__n);

          const difference_type __elemsafter = difference_type(__length) - __elemsbefore;

          __pos = this->_M_finish - __elemsafter;

          _STLP_TRY {

            iterator __dst = __new_finish;

            iterator __src = this->_M_finish;

            for (--__src, --__dst; __src >= __pos; --__src, --__dst) {

              _Self::get_allocator().construct( &(*__dst), _STLP_STD::move(*__src) );

              _Self::get_allocator().destroy( &(*__src) );

            }

            this->_M_finish = __new_finish;

            uninitialized_copy(__first, __last, __pos);

          }

          _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))

        }

      }

    template <class _ForwardIterator>

    void _M_insert_range_aux( iterator __pos,

                              _ForwardIterator __first, _ForwardIterator __last,

                              size_type __n, const true_type& /*_Movable*/)

      {

        const difference_type __elemsbefore = __pos - this->_M_start;

        size_type __length = size();

        if (__elemsbefore <= difference_type(__length / 2)) {

          iterator __new_start = _M_reserve_elements_at_front(__n);

          iterator __old_start = this->_M_start;

          __pos = this->_M_start + __elemsbefore;

          _STLP_TRY {

            if (__elemsbefore >= difference_type(__n)) {

              iterator __start_n = this->_M_start + difference_type(__n);

              _STLP_STD::uninitialized_copy(this->_M_start, __start_n, __new_start);

              this->_M_start = __new_start;

              _STLP_STD::copy(__start_n, __pos, __old_start);

              _STLP_STD::copy(__first, __last, __pos - difference_type(__n));

            } else {

              _ForwardIterator __mid = __first;

              _STLP_STD::advance(__mid, difference_type(__n) - __elemsbefore);

              _STLP_PRIV __uninitialized_copy_copy(this->_M_start, __pos, __first, __mid, __new_start);

              this->_M_start = __new_start;

              _STLP_STD::copy(__mid, __last, __old_start);

            }

          }

          _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))

        } else {

          iterator __new_finish = _M_reserve_elements_at_back(__n);

          iterator __old_finish = this->_M_finish;

          const difference_type __elemsafter = difference_type(__length) - __elemsbefore;

          __pos = this->_M_finish - __elemsafter;

          _STLP_TRY {

            if (__elemsafter > difference_type(__n)) {

              iterator __finish_n = this->_M_finish - difference_type(__n);

              _STLP_STD::uninitialized_copy(__finish_n, this->_M_finish, this->_M_finish);

              this->_M_finish = __new_finish;

              _STLP_STD::copy_backward(__pos, __finish_n, __old_finish);

              _STLP_STD::copy(__first, __last, __pos);

            } else {

              _ForwardIterator __mid = __first;

              _STLP_STD::advance(__mid, __elemsafter);

              _STLP_PRIV __uninitialized_copy_copy(__mid, __last, __pos, this->_M_finish, this->_M_finish);

              this->_M_finish = __new_finish;

              _STLP_STD::copy(__first, __mid, __pos);

            }

          }

          _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))

        }

      }

    iterator _M_reserve_elements_at_front(size_type __n)

      {

        size_type __vacancies = this->_M_start._M_cur - this->_M_start._M_first;

        if (__n > __vacancies) {

          _M_new_elements_at_front(__n - __vacancies);

        }

        return this->_M_start - difference_type(__n);

      }

    iterator _M_reserve_elements_at_back(size_type __n)

      {

        size_type __vacancies = (this->_M_finish._M_last - this->_M_finish._M_cur) - 1;

        if (__n > __vacancies) {

          _M_new_elements_at_back(__n - __vacancies);

        }

        return this->_M_finish + difference_type(__n);

      }

    void _M_new_elements_at_front(size_type __new_elements);

    void _M_new_elements_at_back(size_type __new_elements);

  protected:                      // Allocation of _M_map and nodes

    // Makes sure the _M_map has space for new nodes.  Does not actually

    //  add the nodes.  Can invalidate _M_map pointers.  (And consequently,

    //  deque iterators.)

    void _M_reserve_map_at_back (size_type __nodes_to_add = 1)

    {

      if (__nodes_to_add + 1 > this->_M_map_size._M_data - (this->_M_finish._M_node - this->_M_map._M_data)) {

        _M_reallocate_map(__nodes_to_add, false);

      }

    }

    void _M_reserve_map_at_front (size_type __nodes_to_add = 1)

    {

      if (__nodes_to_add > size_type(this->_M_start._M_node - this->_M_map._M_data)) {

        _M_reallocate_map(__nodes_to_add, true);

      }

    }

    void _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);

};

#if defined (deque)

_STLP_MOVE_TO_STD_NAMESPACE

#  undef deque

#endif // deque

_STLP_END_NAMESPACE

#include <stl/_deque.c>

#if defined (_STLP_USE_PTR_SPECIALIZATIONS)

#  include <stl/pointers/_deque.h>

#endif

#if defined (_STLP_DEBUG)

#  include <stl/debug/_deque.h>

#endif

_STLP_BEGIN_NAMESPACE

#define _STLP_TEMPLATE_CONTAINER deque<_Tp, _Alloc>

#define _STLP_TEMPLATE_HEADER    template <class _Tp, class _Alloc>

#include <stl/_relops_cont.h>

#undef _STLP_TEMPLATE_CONTAINER

#undef _STLP_TEMPLATE_HEADER

_STLP_END_NAMESPACE

#if (_STLP_OUTERMOST_HEADER_ID == 0x22)

#  include <stl/_epilog.h>

#  undef _STLP_OUTERMOST_HEADER_ID

#endif

#endif /* _STLP_DEQUE */

// Local Variables:

// mode:C++

// End: