// -*- C++ -*-
/***************************************************************************
 *
 * deque - Declaration and definition for the Standard Library deque class
 *
 ***************************************************************************
 *    
 *  Copyright 2000 Compaq Computer Corporation
 *
 *  COMPAQ Registered in U.S. Patent and Trademark Office.
 *
 *  Confidential computer software. Valid license from Compaq required for
 *  possession, use or copying. Consistent with FAR 12.211 and 12.212,
 *  Commercial Computer Software, Computer Software Documentation, and
 *  Technical Data for Commercial Items are licensed to the U.S. Government
 *  under vendor's standard commercial license.
 *
 ****************************************************************************
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Hewlett-Packard Company makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 *
 ***************************************************************************
 *
 * (c) Copyright 1994, 1998 Rogue Wave Software, Inc.
 * ALL RIGHTS RESERVED
 *
 * The software and information contained herein are proprietary to, and
 * comprise valuable trade secrets of, Rogue Wave Software, Inc., which
 * intends to preserve as trade secrets such software and information.
 * This software is furnished pursuant to a written license agreement and
 * may be used, copied, transmitted, and stored only in accordance with
 * the terms of such license and with the inclusion of the above copyright
 * notice.  This software and information or any other copies thereof may
 * not be provided or otherwise made available to any other person.
 *
 * Notwithstanding any other lease or license that may pertain to, or
 * accompany the delivery of, this computer software and information, the
 * rights of the Government regarding its use, reproduction and disclosure
 * are as set forth in Section 52.227-19 of the FARS Computer
 * Software-Restricted Rights clause.
 * 
 * Use, duplication, or disclosure by the Government is subject to
 * restrictions as set forth in subparagraph (c)(1)(ii) of the Rights in
 * Technical Data and Computer Software clause at DFARS 252.227-7013.
 * Contractor/Manufacturer is Rogue Wave Software, Inc.,
 * P.O. Box 2328, Corvallis, Oregon 97339.
 *
 * This computer software and information is distributed with "restricted
 * rights."  Use, duplication or disclosure is subject to restrictions as
 * set forth in NASA FAR SUP 18-52.227-79 (April 1985) "Commercial
 * Computer Software-Restricted Rights (April 1985)."  If the Clause at
 * 18-52.227-74 "Rights in Data General" is specified in the contract,
 * then the "Alternate III" clause applies.
 *
 **************************************************************************/

#ifndef __STD_DEQUE__
#define __STD_DEQUE__

#include <stddefs>

#include <stdcomp>
#include <algorithm>
#include <iterator>
#include <memory>
#include <stdexcept>


#ifndef deque 
#define deque deque
#endif

#if defined(__DECCXX)
#   ifdef __PRAGMA_ENVIRONMENT
#      pragma __environment __save
#      pragma __environment __cxx_header_defaults
#   endif
#endif

#if defined(__VMS) && defined(__DECCXX) && !defined(__DECFIXCXXL1158)
#pragma __extern_prefix __save
#pragma __extern_prefix "CXXL$" 
#endif


#ifndef _RWSTD_NO_NAMESPACE
namespace std {
#endif

//
// Note that _RWSTD_COMPLEX_DEFAULT(x)
// will expand to: ' = x', or nothing,
// depending on your compiler's capabilities and/or
// flag settings (see stdcomp.h).
//
  template <class T, class Allocator _RWSTD_COMPLEX_DEFAULT(allocator<T>) >
  class  deque
  {
  protected:
#ifdef _RWSTD_ALLOCATOR
    typedef _TYPENAME Allocator::template rebind<T>::other _RWvalue_alloc_type;
#else
    typedef allocator_interface<Allocator,T>    _RWvalue_alloc_type;
#endif

  public:

    //
    // Types.
    //
    class  iterator;
    class  const_iterator;
    friend class iterator;
    friend class const_iterator;
    typedef T                                          value_type;
    typedef Allocator                                  allocator_type;

#ifndef _RWSTD_NO_COMPLICATED_TYPEDEF
    typedef _TYPENAME _RWSTD_ALLOC_SIZE_TYPE              size_type;
    typedef _TYPENAME _RWSTD_ALLOC_DIFF_TYPE              difference_type;
    typedef _TYPENAME _RWvalue_alloc_type::reference       reference;
    typedef _TYPENAME _RWvalue_alloc_type::const_reference const_reference;
    typedef _TYPENAME _RWvalue_alloc_type::pointer         pointer;
    typedef _TYPENAME _RWvalue_alloc_type::const_pointer   const_pointer;
#else
    typedef size_t            size_type;
    typedef ptrdiff_t         difference_type;
    typedef T&                reference;
    typedef const T&          const_reference;
    typedef T*                pointer;
    typedef const T*          const_pointer;
#endif  //_RWSTD_NO_COMPLICATED_TYPEDEF

  protected:
#ifdef _RWSTD_ALLOCATOR
    typedef _TYPENAME Allocator::template rebind<pointer>::other _RWmap_alloc_type;
#else
    typedef allocator_interface<allocator_type,pointer> _RWmap_alloc_type;
#endif
    typedef _TYPENAME _RWmap_alloc_type::pointer         _RWmap_pointer;

    static size_type _RWbuffer_size ();

    typedef _RW_STD::iterator<random_access_iterator_tag, value_type,
                    difference_type, pointer,reference> _RWit;
    typedef _RW_STD::iterator<random_access_iterator_tag, value_type, 
                    difference_type, const_pointer, const_reference> _RWcit;

  public:
    //
    // Definition of our iterator.
    //
    class iterator : public _RWit
    {
      friend class deque<T,Allocator>;
      friend class const_iterator;

    protected:

      pointer     current;
      pointer     first;
      pointer     last;
      _RWmap_pointer node;

      iterator (pointer x, _RWmap_pointer y)
        : current(x), first(*y), last(*y + _RWbuffer_size()), node(y) {}

    public:

      iterator () : current(0), first(0), last(0), node(0) {}
      iterator (const iterator& x) 
        : current(x.current), first(x.first), 
          last(x.last), node(x.node) {}     
      reference operator* () const { return *current; }
#ifndef _RWSTD_NO_NONCLASS_ARROW_RETURN
      pointer operator-> () const { return current; }
#endif
      difference_type operator- (const iterator& x) const
      {
        return node == x.node 
        ? current - x.current 
        : difference_type(_RWbuffer_size() * (node - x.node - 1) +
                          (current - first) + (x.last - x.current));
      }
      iterator& operator++ ()
      {
        if (++current == last)
        {
          first = *(++node);
          current = first;
          last = first + _RWbuffer_size();
        }
        return *this; 
      }
      iterator operator++ (int)
      {
        iterator tmp = *this; ++*this; return tmp;
      }
      iterator& operator-- ()
      {
        if (current == first)
        {
          first = *(--node);
          last = first + _RWbuffer_size();
          current = last;
        }
        --current;
        return *this;
      }
      iterator operator-- (int)
      {
        iterator tmp = *this; --*this; return tmp;
      }
      iterator& operator+= (difference_type n)
      {
        difference_type offset = n + (current - first);
        difference_type num_node_to_jump = offset >= 0
        ? offset / _RWbuffer_size()
        : -(difference_type)((-offset + _RWbuffer_size() - 1) / _RWbuffer_size());
        if (num_node_to_jump == 0)
          current += n;
        else
        {
          node = node + num_node_to_jump;
          first = *node;
          last = first + _RWbuffer_size();
          current = first + (offset - num_node_to_jump * _RWbuffer_size());
        }
        return *this;
      }
      iterator& operator-= (difference_type n) { return *this += -n; }
      iterator operator+ (difference_type n) const
      {
        iterator tmp = *this; return tmp += n;
      }
      iterator operator- (difference_type n) const
      {
        iterator tmp = *this; return tmp -= n;
      }
      reference operator[] (difference_type n) { return *(*this + n); }
      bool operator== (const iterator& x) const
      {
        return current == x.current || 
        ((current == first || x.current == x.first) && 
         *this - x == 0);
      }
      bool operator!= (const iterator& x) const { return !(*this == x); } 
      bool operator< (const iterator& x) const
      {
        return (node == x.node) ? (current < x.current) : (node < x.node);
      } 
      bool operator> (const iterator& x) const
      {
        return x < *this;
      }
      bool operator>= (const iterator& x) const
      {
        return !(*this < x);
      }
      bool operator<= (const iterator& x) const
      {
        return !(*this > x);
      }
    };  // End of nested definiton of iterator.

    //
    // Definition of our constant iterator.
    //
    class const_iterator  : public _RWcit
    {
      friend class deque<T,Allocator>;

    protected:

      pointer     current;
      pointer     first;
      pointer     last;
      _RWmap_pointer node;

      const_iterator (pointer x, _RWmap_pointer y) 
        : current(x), first(*y), last(*y + _RWbuffer_size()), node(y) {}

    public:
       
      const_iterator () : current(0), first(0), last(0), node(0) {}
#if defined(__DECCXX) && !defined(__DECFIXCXXL1195)
      const_iterator (const _TYPENAME deque<T,Allocator>::iterator& x) 
#else
      const_iterator (const iterator& x) 
#endif
        : current(x.current), first(x.first), last(x.last), node(x.node) {}     
      const_reference operator* () const { return *current; }
#ifndef _RWSTD_NO_NONCLASS_ARROW_RETURN
      const_pointer operator-> () const { return current; }
#endif
      difference_type operator- (const const_iterator& x) const
      {
        return node == x.node 
        ? current - x.current 
        : difference_type(_RWbuffer_size() * (node - x.node - 1) +
                          (current - first) + (x.last - x.current));
      }
      const_iterator& operator++ ()
      {
        if (++current == last)
        {
          first = *(++node);
          current = first;
          last = first + _RWbuffer_size();
        }
        return *this; 
      }
      const_iterator operator++ (int)
      {
        const_iterator tmp = *this; ++*this; return tmp;
      }
      const_iterator& operator-- ()
      {
        if (current == first)
        {
          first = *(--node);
          last = first + _RWbuffer_size();
          current = last;
        }
        --current;
        return *this;
      }
      const_iterator operator-- (int)
      {
        const_iterator tmp = *this; --*this; return tmp;
      }
      const_iterator& operator+= (difference_type n)
      {
        difference_type offset = n + (current - first);
        difference_type num_node_to_jump = offset >= 0
        ? offset / _RWbuffer_size()
        : -(difference_type)((-offset + _RWbuffer_size() - 1) / _RWbuffer_size());
        if (num_node_to_jump == 0)
          current += n;
        else
        {
          node = node + num_node_to_jump;
          first = *node;
          last = first + _RWbuffer_size();
          current = first + (offset - num_node_to_jump * _RWbuffer_size());
        }
        return *this;
      }
      const_iterator& operator-= (difference_type n) { return *this += -n; }
      const_iterator operator+ (difference_type n) const
      {
        const_iterator tmp = *this; return tmp += n;
      }
      const_iterator operator- (difference_type n) const
      {
        const_iterator tmp = *this; return tmp -= n;
      }
      const_reference operator[] (difference_type n)
      { 
        return *(*this + n); 
      }
      bool operator== (const const_iterator& x) const
      {
        return current == x.current || 
        ((current == first || x.current == x.first) && 
         *this - x == 0);
      }
      bool operator!= (const const_iterator& x) const { return !(*this == x); }
      bool operator< (const const_iterator& x) const
      {
        return (node == x.node) ? (current < x.current) : (node < x.node);
      } 
      bool operator> (const const_iterator& x) const
      {
        return x < *this;
      }
      bool operator>= (const const_iterator& x) const
      {
        return !(*this < x);
      }
      bool operator<= (const const_iterator& x) const
      {
        return !(*this > x);
      }
    };  // End of nested definiton of const_iterator.

#ifndef _RWSTD_NO_CLASS_PARTIAL_SPEC 
    typedef _RW_STD::reverse_iterator<const_iterator> const_reverse_iterator;
    typedef _RW_STD::reverse_iterator<iterator>  reverse_iterator;
#else
    typedef _RW_STD::reverse_iterator<const_iterator, 
      random_access_iterator_tag, value_type, 
      const_reference, const_pointer, difference_type>
      const_reverse_iterator;
    typedef _RW_STD::reverse_iterator<iterator, 
      random_access_iterator_tag, value_type,
      reference, pointer, difference_type>
      reverse_iterator;
#endif

  protected:

    iterator      _RWstart;
    iterator      _RWfinish;
    size_type     _RWlength;
    _RWmap_pointer _RWmap;
    __RWSTD::_RWrw_basis<size_type,allocator_type>     _RWmap_size;

    void _RWallocate_at_begin   ();    
    void _RWallocate_at_end     ();
    void _RWdeallocate_at_begin ();
    void _RWdeallocate_at_end   ();
    void _RWinsert_aux (iterator position, size_type n, const T& x);

#if defined(__DECCXX) && !defined(__DECFIXCXXL1306)
    template <class InputIterator>
    void _RWinsert_interval_dispatch (iterator position, InputIterator
                         first, InputIterator last, bidirectional_iterator_tag) {
         _RWinsert_aux2(position, first, last);
    }
    template <class InputIterator>
    void _RWinsert_interval_dispatch (iterator position, InputIterator
                         first, InputIterator last, input_iterator_tag)
    {
         while(first != last) {
            position = insert (position,*first);
            ++position;
            ++first;
         }
    }
#endif


  public:
    //
    // construct/copy/destroy
    //
    _EXPLICIT deque (const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator())) 
      : _RWstart(), _RWfinish(), _RWlength(0), _RWmap(0), _RWmap_size(0,alloc) 
    { ; }

#ifdef _RWSTD_NO_DEFAULT_TEMPLATE_ARGS
    deque (void) 
      : _RWstart(), _RWfinish(), _RWlength(0), _RWmap(0), _RWmap_size(0,Allocator()) 
    { ; }

    deque (size_type n, const T& value)
      : _RWstart(), _RWfinish(), _RWlength(0), _RWmap(0), _RWmap_size(0,Allocator()) 
    {
      insert(begin(), n, value);
    }
#endif // _RWSTD_NO_DEFAULT_TEMPLATE_ARGS

    _EXPLICIT deque (size_type n)
      : _RWstart(), _RWfinish(), _RWlength(0), _RWmap(0), _RWmap_size(0,Allocator()) 
    {
      insert(begin(), n, T());
    }

#ifndef _RWSTD_NO_MEMBER_TEMPLATES
    template<class InputIterator>
    deque (InputIterator first, InputIterator last, const Allocator& alloc = Allocator())
      : _RWstart(), _RWfinish(), _RWlength(0), _RWmap(0), _RWmap_size(0,alloc) 
    {
      copy(first, last, back_inserter(*this));
    }
    deque (int n, const T& value,
           const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
      : _RWstart(), _RWfinish(), _RWlength(0), _RWmap(0), _RWmap_size(0,alloc) 
    { insert(begin(), (size_type)n, value); }
    deque (unsigned int n, const T& value,
           const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
      : _RWstart(), _RWfinish(), _RWlength(0), _RWmap(0), _RWmap_size(0,alloc) 
    { insert(begin(), (size_type)n, value); }
    deque (long n, const T& value,
           const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
      : _RWstart(), _RWfinish(), _RWlength(0), _RWmap(0), _RWmap_size(0,alloc) 
    { insert(begin(), (size_type)n, value); }
    deque (unsigned long n, const T& value,
           const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
      : _RWstart(), _RWfinish(), _RWlength(0), _RWmap(0), _RWmap_size(0,alloc) 
    { insert(begin(), (size_type)n, value); }
    deque (short n, const T& value,
           const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
      : _RWstart(), _RWfinish(), _RWlength(0), _RWmap(0), _RWmap_size(0,alloc) 
    { insert(begin(), (size_type)n, value); }
    deque (unsigned short n, const T& value,
           const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
      : _RWstart(), _RWfinish(), _RWlength(0), _RWmap(0), _RWmap_size(0,alloc) 
    { insert(begin(), (size_type)n, value); }
    deque (char n, const T& value,
           const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
      : _RWstart(), _RWfinish(), _RWlength(0), _RWmap(0), _RWmap_size(0,alloc) 
    { insert(begin(), (size_type)n, value); }
    deque (unsigned char n, const T& value,
           const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
      : _RWstart(), _RWfinish(), _RWlength(0), _RWmap(0), _RWmap_size(0,alloc) 
    { insert(begin(), (size_type)n, value); }
#ifndef _RWSTD_NO_BOOL
    deque (bool n, const T& value,
           const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
      : _RWstart(), _RWfinish(), _RWlength(0), _RWmap(0), _RWmap_size(0,alloc) 
    {  insert(begin(), (size_type)n, value); }
#endif
#ifndef _RWSTD_NO_OVERLOAD_WCHAR
    deque (wchar_t n, const T& value,
           const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
      : _RWstart(), _RWfinish(), _RWlength(0), _RWmap(0), _RWmap_size(0,alloc) 
    {  insert(begin(), (size_type)n, value); }
#endif
#else
    //
    // Build a deque of size n with each element set to copy of value.
    //
    deque (size_type n, const T& value,
           const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
      : _RWstart(), _RWfinish(), _RWlength(0), _RWmap(0), _RWmap_size(0,alloc) 
    {
      insert(begin(), n, value);
    }


    deque (const_iterator first, const_iterator last, const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
      : _RWstart(), _RWfinish(), _RWlength(0), _RWmap(0), _RWmap_size(0,alloc) 
    {
      copy(first, last, back_inserter(*this));
    }
    
    deque (const T* first, const T* last, const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
      : _RWstart(), _RWfinish(), _RWlength(0), _RWmap(0), _RWmap_size(0,alloc) 
    {
      copy(first, last, back_inserter(*this));
    }

#ifdef _RWSTD_NO_DEFAULT_TEMPLATE_ARGS
    deque (const_iterator first, const_iterator last)
      : _RWstart(), _RWfinish(), _RWlength(0), _RWmap(0), _RWmap_size(0,Allocator()) 
    {
      copy(first, last, back_inserter(*this));
    }
    
    deque (const T* first, const T* last)
      : _RWstart(), _RWfinish(), _RWlength(0), _RWmap(0), _RWmap_size(0,Allocator()) 
    {
      copy(first, last, back_inserter(*this));
    }
#endif // _RWSTD_NO_DEFAULT_TEMPLATE_ARGS
#endif // _RWSTD_NO_MEMBER_TEMPLATES

    deque (const deque<T,Allocator>& x)
      : _RWstart(), _RWfinish(), _RWlength(0), _RWmap(0), _RWmap_size(0,x.get_allocator())
    {
      copy(x.begin(), x.end(), back_inserter(*this));
    }

    ~deque ();
    deque<T,Allocator>& operator= (const deque<T,Allocator>& x)
    {
      if (!(this == &x))
      {
        if (size() >= x.size()) 
          erase(copy(x.begin(), x.end(), begin()), end());
        else 
          copy(x.begin() + size(), x.end(),
               inserter(*this,copy(x.begin(),x.begin()+size(),begin())));
      }
      return *this;
    }

#ifndef _RWSTD_NO_MEMBER_TEMPLATES
    template<class InputIterator>
    void assign (InputIterator first, InputIterator last)
    { erase(begin(), end()); insert(begin(), first, last); }
#if defined(__DECCXX) && !defined(__DECFIXCXXL1097)
    void assign (int n, const T& t)
#else
    void assign (int n, T t)
#endif
    { erase(begin(), end()); insert(begin(), n, t); }
#if defined(__DECCXX) && !defined(__DECFIXCXXL1097)
    void assign (unsigned int n, const T& t)
#else
    void assign (unsigned int n, T t)
#endif
    { erase(begin(), end()); insert(begin(), n, t); }
#if defined(__DECCXX) && !defined(__DECFIXCXXL1097)
    void assign (long n, const T& t)
#else
    void assign (long n, T t)
#endif
    { erase(begin(), end()); insert(begin(), n, t); }
#if defined(__DECCXX) && !defined(__DECFIXCXXL1097)
    void assign (unsigned long n, const T& t)
#else
    void assign (unsigned long n, T t)
#endif
    { erase(begin(), end()); insert(begin(), n, t); }
#if defined(__DECCXX) && !defined(__DECFIXCXXL1097)
    void assign (short n, const T& t)
#else
    void assign (short n, T t)
#endif
    { erase(begin(), end()); insert(begin(), n, t); }
#if defined(__DECCXX) && !defined(__DECFIXCXXL1097)
    void assign (unsigned short n, const T& t)
#else
    void assign (unsigned short n, T t)
#endif
    { erase(begin(), end()); insert(begin(), n, t); }
#if defined(__DECCXX) && !defined(__DECFIXCXXL1097)
    void assign (char n, const T& t)
#else
    void assign (char n, T t)
#endif
    { erase(begin(), end()); insert(begin(), n, t); }
#if defined(__DECCXX) && !defined(__DECFIXCXXL1097)
    void assign (unsigned char n, const T& t)
#else
    void assign (unsigned char n, T t)
#endif
    { erase(begin(), end()); insert(begin(), n, t); }
#ifndef _RWSTD_NO_OVERLOAD_WCHAR
#if defined(__DECCXX) && !defined(__DECFIXCXXL1097)
    void assign (wchar_t n, const T& t)
#else
    void assign (wchar_t n, T t)
#endif
    { erase(begin(), end()); insert(begin(), n, t); }
#endif
#ifndef _RWSTD_NO_BOOL
#if defined(__DECCXX) && !defined(__DECFIXCXXL1097)
    void assign (bool n, const T& t)
#else
    void assign (bool n, T t)
#endif
    { erase(begin(), end()); insert(begin(), n, t); }
#endif
#else
    void assign (const_iterator first, const_iterator last)
    {
      erase(begin(), end()); insert(begin(), first, last);
    }
    void assign (const T* first, const T* last)
    {
      erase(begin(), end()); insert(begin(), first, last);
    }
    //
    // Assign n copies of t to this vector.
    //
    void assign (size_type n, const T& t)
    {
      erase(begin(), end()); insert(begin(), n, t);
    }
#endif // _RWSTD_NO_MEMBER_TEMPLATES

    allocator_type get_allocator() const
    {
      return (allocator_type)_RWmap_size;
    }

    //
    // Iterators.
    //
    iterator         begin  ()       { return _RWstart;  }
    const_iterator   begin  () const { return _RWstart;  }
    iterator         end    ()       { return _RWfinish; }
    const_iterator   end    () const { return _RWfinish; }
    reverse_iterator rbegin ()
    { 
      reverse_iterator tmp(end()); return tmp;
    }
    const_reverse_iterator rbegin () const
    { 
      const_reverse_iterator tmp(end()); return tmp;
    }
    reverse_iterator rend ()
    { 
      reverse_iterator tmp(begin()); return tmp;
    }
    const_reverse_iterator rend () const
    { 
      const_reverse_iterator tmp(begin()); return tmp;
    }

    //
    // Capacity.
    //
    bool      empty    () const { return _RWlength == 0; }
    size_type size     () const { return _RWlength; }
    size_type max_size () const 
    { return _RWvalue_alloc_type(_RWmap_size).max_size(); }
    void      resize (size_type new_size);
    void      resize (size_type new_size, T value);


    //
    // Element access.
    //
    reference       operator[] (size_type n)
    {
#ifdef _RWSTD_BOUNDS_CHECKING
      _RWSTD_THROW(n >= size(), out_of_range,
        __RWSTD::except_msg_string(__RWSTD::rwse_OutOfRange,
          "deque::operator[](size_t)",n,size()).msgstr());
      return *(begin() + n);
#else
      return *(begin() + n);
#endif
    }
    const_reference operator[] (size_type n) const
    {
#ifdef _RWSTD_BOUNDS_CHECKING
      _RWSTD_THROW(n >= size(), out_of_range,
        __RWSTD::except_msg_string(__RWSTD::rwse_OutOfRange,
          "deque::operator[](size_t) const",n,size()).msgstr());
      return *(begin() + n);
#else
      return *(begin() + n);
#endif
    }
    const_reference at (size_type n) const 
    { 
      _RWSTD_THROW(n >= size(), out_of_range,
        __RWSTD::except_msg_string(__RWSTD::rwse_OutOfRange,
          "deque:: at(size_t) const",n,size()).msgstr());
      return *(begin() + n); 
    }
    reference       at (size_type n)
    { 
      _RWSTD_THROW(n >= size(), out_of_range,
        __RWSTD::except_msg_string(__RWSTD::rwse_OutOfRange,
          "deque:: at(size_t)",n,size()).msgstr());
      return *(begin() + n); 
    }
    reference       front ()                       { return *begin();       }
    const_reference front ()                 const { return *begin();       }
    reference       back ()                        { return *(end() - 1);   }
    const_reference back ()                  const { return *(end() - 1);   }

    //
    // Modifiers.
    //
    void push_front (const T& x)
    {
      if (empty() || begin().current == begin().first) 
        _RWallocate_at_begin();
      _RWvalue_alloc_type(_RWmap_size).construct(_RWstart.current-1, x);
      --_RWstart.current;
      ++_RWlength;
    }
    void push_back (const T& x)
    {
      if (empty() || end().current == end().last) 
        _RWallocate_at_end();
      _RWvalue_alloc_type(_RWmap_size).construct(_RWfinish.current, x);
      ++_RWfinish.current;
      ++_RWlength;
    }

    //
    // Insert x at position.
    //
    iterator insert (iterator position, const T& x);

#ifndef _RWSTD_NO_MEMBER_TEMPLATES
    template <class InputIterator>
    void insert(iterator position, InputIterator first, 
                InputIterator last);
#if defined(__DECCXX) && !defined(__DECFIXCXXL1306)
    template <class InputIterator>
    void _RWinsert_aux2(iterator position, InputIterator first, 
                InputIterator last);
#endif
    void insert (iterator position, int n, const T& value)
    { _RWinsert_aux(position,(size_type)n,value); }
    void insert (iterator position, unsigned int n, const T& value)
    { _RWinsert_aux(position,(size_type)n,value); }
#if defined(__DECCXX) && !defined(__DECFIXCXXL1104)
    void insert (iterator position, long n, const T& value)
#else
    void insert (iterator position, long n, T value)
#endif
    { _RWinsert_aux(position,(size_type)n,value); }
    void insert (iterator position, unsigned long n, const T& value)
    { _RWinsert_aux(position,(size_type)n,value); }
    void insert (iterator position, short n, const T& value)
    { _RWinsert_aux(position,(size_type)n,value); }
    void insert (iterator position, unsigned short n, const T& value)
    { _RWinsert_aux(position,(size_type)n,value); }
    void insert (iterator position, char n, const T& value)
    { _RWinsert_aux(position,(size_type)n,value); }
    void insert (iterator position, unsigned char n, const T& value)
    { _RWinsert_aux(position,(size_type)n,value); }
#ifndef _RWSTD_NO_BOOL
    void insert (iterator position, bool n, const T& value)
    { _RWinsert_aux(position,(size_type)n,value); }
#endif
#ifndef _RWSTD_NO_OVERLOAD_WCHAR
    void insert (iterator position, wchar_t n, const T& value)
    { _RWinsert_aux(position,(size_type)n,value); }
#endif
#else
    void insert (iterator position, size_type n, const T& x)
    { _RWinsert_aux(position,n,x); }
    void insert (iterator position, const T* first, const T* last);
    void insert (iterator position, const_iterator first, const_iterator last);
#endif // _RWSTD_NO_MEMBER_TEMPLATES

    void pop_front ()
    {
      iterator tmp = _RWstart;
      ++_RWstart.current;
      --_RWlength; 
      _RWvalue_alloc_type(_RWmap_size).destroy(tmp.current);
      if (empty() || begin().current == begin().last) 
        _RWdeallocate_at_begin();
    }
    void pop_back ()
    {
      --_RWfinish.current;
      --_RWlength; 
      _RWvalue_alloc_type(_RWmap_size).destroy(_RWfinish.current);
      if (empty() || end().current == end().first) 
        _RWdeallocate_at_end();
    }
    iterator erase (iterator position);
    iterator erase (iterator first, iterator last);    
    void swap (deque<T,Allocator>& x)
    {
      if((allocator_type)_RWmap_size== (allocator_type)x._RWmap_size)
      {
#ifndef _RWSTD_NO_NAMESPACE
        std::swap(_RWstart,          x._RWstart);
        std::swap(_RWfinish,         x._RWfinish);
        std::swap(_RWlength,         x._RWlength);
        std::swap(_RWmap,            x._RWmap);
        std::swap(_RWmap_size,       x._RWmap_size);
#else
        ::swap(_RWstart,             x._RWstart);
        ::swap(_RWfinish,            x._RWfinish);
        ::swap(_RWlength,            x._RWlength);
        ::swap(_RWmap,               x._RWmap);
        ::swap(_RWmap_size,          x._RWmap_size);
#endif // _RWSTD_NO_NAMESPACE
      }
      else
      {
        deque<T,Allocator> _x=*this;
        *this=x;
        x=_x;
      }
    }
    void clear()
    {
      erase(begin(),end());
    }
  };

  template <class T, class Allocator>
  inline bool operator== (const deque<T,Allocator>& x, const deque<T,Allocator>& y)
  {
    return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
  }

  template <class T, class Allocator>
  inline bool operator< (const deque<T,Allocator>& x, const deque<T,Allocator>& y)
  {
    return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
  }

#if !defined(_RWSTD_NO_NAMESPACE) || !defined(_RWSTD_NO_PART_SPEC_OVERLOAD)
  template <class T, class Allocator>
  inline bool operator!= (const deque<T,Allocator>& x, const deque<T,Allocator>& y)
  {
    return !(x == y);
  }

  template <class T, class Allocator>
  inline bool operator> (const deque<T,Allocator>& x, const deque<T,Allocator>& y)
  {
    return y < x;
  }

  template <class T, class Allocator>
  inline bool operator>= (const deque<T,Allocator>& x, const deque<T,Allocator>& y)
  {
    return !(x < y);
  }

  template <class T, class Allocator>
  inline bool operator<= (const deque<T,Allocator>& x, const deque<T,Allocator>& y)
  {
    return !(y <  x);
  }

  template <class T, class Allocator>
  inline void swap(deque<T,Allocator>& a, deque<T,Allocator>& b)
  {
    a.swap(b);
  }
#endif // !defined(_RWSTD_NO_NAMESPACE) || !defined(_RWSTD_NO_PART_SPEC_OVERLOAD)

#ifndef _RWSTD_NO_NAMESPACE
}
#endif

#if defined(__VMS) && defined(__DECCXX) && !defined(__DECFIXCXXL1158)
#   pragma __extern_prefix __restore
#endif

#ifdef _RWSTD_COMPILE_INSTANTIATE
#include <deque.cc>
#endif

#undef deque


#if defined(__DECCXX)
#   ifdef __PRAGMA_ENVIRONMENT
#      pragma __environment __restore
#   endif
#endif

#endif /*__STD_DEQUE__*/
