/***************************************************************************
 *
 * deque - Declaration and definition for the Standard Library deque class
 *
 * $Id: deque,v 1.60 1996/08/28 18:41:26 smithey Exp $
 *
 ***************************************************************************
 *
 * 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-1996 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__
//
//
//  Copyright Digital Equipment Corporation 1996. All rights reserved.
//
//  Restricted Rights: Use, duplication, or disclosure by the U.S.
//  Government is subject to restrictions as set forth in subparagraph
//  (c) (1) (ii) of DFARS 252.227-7013, or in FAR 52.227-19, or in FAR
//  52.227-14 Alt. III, as applicable.
//
//  This software is proprietary to and embodies the confidential
//  technology of Digital Equipment Corporation. Possession, use, or
//  copying of this software and media is authorized only pursuant to a
//  valid written license from Digital or an authorized sublicensor.
//
//

#include <stddefs>

#include <stdcomp>
#ifndef _RWSTD_HEADER_REQUIRES_HPP
#include <functional>
#include <algorithm>
#include <iterator>
#include <memory>
#include <stdexcept>
#else
#include <functional.hpp>
#include <algorithm.hpp>
#include <iterator.hpp>
#include <memory.hpp>
#include <stdexcept.hpp>
#endif

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

#ifndef deque 
#define deque deque
#endif

#ifndef _RWSTD_NO_NAMESPACE
namespace std {
#endif

//
// Note that _RWSTD_SIMPLE_DEFAULT(x)
// will expand to: ' = x', or nothing,
// depending on your compiler's capabilities and/or
// flag settings (see stdcomp).
//
template <class T, class Allocator _RWSTD_SIMPLE_DEFAULT(allocator<T>) >
class  deque
{
  protected:
#ifdef _RWSTD_ALLOCATOR
#if defined(__DECCXX) && !defined(__DECFIXCXXL479)
    typedef _TYPENAME Allocator::_TEMPLATE rebind<T>::other     value_alloc_type;
#else
    typedef _TYPENAME Allocator::rebind<charT>::other     value_alloc_type;
#endif
#else
    typedef allocator_interface<Allocator,T>    value_alloc_type;
#endif

  public:

    class  iterator;
    class  const_iterator;
    friend class iterator;
    friend class const_iterator;

  public:
    //
    // Types.
    //
    typedef T                                          value_type;
    typedef Allocator                                  allocator_type;
    typedef _TYPENAME _RWSTD_ALLOC_SIZE_TYPE             size_type;
    typedef _TYPENAME _RWSTD_ALLOC_DIFF_TYPE             difference_type;

    typedef _TYPENAME value_alloc_type::reference       reference;
    typedef _TYPENAME value_alloc_type::const_reference const_reference;
#if defined(__DECCXX) && !defined(__DECFIXCXXL519)
    typedef _TYPENAME value_alloc_type::pointer          pointer;
    typedef _TYPENAME value_alloc_type::const_pointer    const_pointer;
 
    protected:
#else
  protected:
    typedef _TYPENAME value_alloc_type::pointer          pointer;
    typedef _TYPENAME value_alloc_type::const_pointer    const_pointer;
#endif
#ifdef _RWSTD_ALLOCATOR
    typedef _TYPENAME Allocator::_TEMPLATE rebind<pointer>::other  map_alloc_type;
#else
    typedef allocator_interface<allocator_type,pointer> map_alloc_type;
#endif
    typedef _TYPENAME map_alloc_type::pointer            map_pointer;

    allocator_type          the_allocator;

    static size_type buffer_size ()
    {
        //
        // Each time we allocate memory we reserve space for
        // a chunk of objects of type T.  This is currently tuned to
        // allocate memory in 1K chunks, except for large objects.
        //
        return sizeof(T) >= 1024 ? 1 : 1024 / sizeof(T);
    }

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

      protected:

        pointer     current;
        pointer     first;
        pointer     last;
        map_pointer node;

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

      public:

        iterator () : current(0), first(0), last(0), node(0) {}
        reference operator* () const { return *current; }
	pointer operator->() const { return current; }
        difference_type operator- (const iterator& x) const
        {
            return node == x.node 
                ? current - x.current 
                : difference_type(buffer_size() * (node - x.node - 1) +
                                  (current - first) + (x.last - x.current));
        }
        iterator& operator++ ()
        {
            if (++current == last)
            {
                first = *(++node);
                current = first;
                last = first + buffer_size();
            }
            return *this; 
        }
        iterator operator++ (int)
        {
            iterator tmp = *this; ++*this; return tmp;
        }
        iterator& operator-- ()
        {
            if (current == first)
            {
                first = *(--node);
                last = first + buffer_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 / buffer_size()
                : -((-offset + buffer_size() - 1) / buffer_size());
            if (num_node_to_jump == 0)
                current += n;
            else
            {
                node = node + num_node_to_jump;
                first = *node;
                last = first + buffer_size();
                current = first + (offset - num_node_to_jump * buffer_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 random_access_iterator<T, difference_type>
    {
        friend class deque<T,Allocator>;

      protected:

        pointer     current;
        pointer     first;
        pointer     last;
        map_pointer node;

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

      public:
       
        const_iterator () : current(0), first(0), last(0), node(0) {}
        const_iterator (const iterator& x) 
            : current(x.current), first(x.first), last(x.last), node(x.node) {}     
        const_reference operator* () const { return *current; }
	const_pointer operator->() const { return current; }
        difference_type operator- (const const_iterator& x) const
        {
            return node == x.node 
            ? current - x.current 
            : difference_type(buffer_size() * (node - x.node - 1) +
                  (current - first) + (x.last - x.current));
        }
        const_iterator& operator++ ()
        {
            if (++current == last)
            {
                first = *(++node);
                current = first;
                last = first + buffer_size();
            }
        return *this; 
        }
        const_iterator operator++ (int)
        {
            const_iterator tmp = *this; ++*this; return tmp;
        }
        const_iterator& operator-- ()
        {
            if (current == first)
            {
                first = *(--node);
                last = first + buffer_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 / buffer_size()
                : -((-offset + buffer_size() - 1) / buffer_size());
            if (num_node_to_jump == 0)
                current += n;
            else
            {
                node = node + num_node_to_jump;
                first = *node;
                last = first + buffer_size();
                current = first + (offset - num_node_to_jump * buffer_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.

#if defined(__DECCXX) && !defined(__DECFIXCXXL776)
    typedef _STD::reverse_iterator<const_iterator> const_reverse_iterator;
#else
    typedef _STD::reverse_iterator<const_iterator, value_type, 
            const_reference, const_pointer, difference_type>
            const_reverse_iterator;
#endif
    typedef _STD::reverse_iterator<iterator, value_type, reference, 
                             pointer, difference_type> 
            reverse_iterator;

  protected:

    iterator    start;
    iterator    finish;
    size_type   length;
    map_pointer map;
    size_type   map_size;

    void allocate_at_begin   ();
    void allocate_at_end     ();
    void deallocate_at_begin ();
    void deallocate_at_end   ();

  public:
    //
    // construct/copy/destroy
    //
    _EXPLICIT deque (const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator())) 
      : start(), finish(), length(0), map(0), map_size(0),
        the_allocator(alloc) 
    { ; }

#ifdef _RWSTD_NO_DEFAULT_TEMPLATE_ARGS
    deque (void) 
      : start(), finish(), length(0), map(0), map_size(0),
        the_allocator(Allocator()) 
    { ; }
#endif

    //
    // Build a deque of size n with each element set to default for type T.
    // Requires that T have a default constructor.
    //
    _EXPLICIT deque (size_type n, const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
        : start(), finish(), length(0), map(0), map_size(0),
        the_allocator(alloc) 
    {
        insert(begin(), n, T());
    }

#if defined(__DECCXX) && !defined(__DECFIXCXXL485)
  private:
    void __deque (size_type n, const T& value, __true_category)
    {
        insert(begin(), n, value);
    }

#   if !defined(_RWSTD_NO_MEMBER_TEMPLATES)
       template<class InputIterator>
       void __deque (InputIterator first, InputIterator last, __false_category)
       {
          copy(first, last, back_inserter(*this));
       }
#   endif

 public:
#endif //if defined(__DECCXX) && !defined(__DECFIXCXXL485)

    //
    // 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()))
        : start(), finish(), length(0), map(0), map_size(0),
        the_allocator(alloc) 
    {
#if defined(__DECCXX) && !defined(__DECFIXCXXL485)
        __deque(n, value, __true_category());
#else
        insert(begin(), n, value);
#endif
    }

#ifdef _RWSTD_NO_DEFAULT_TEMPLATE_ARGS
    _EXPLICIT deque (size_type n)
        : start(), finish(), length(0), map(0), map_size(0),
        the_allocator(Allocator()) 
    {
        insert(begin(), n, T());
    }

    deque (size_type n, const T& value)
        : start(), finish(), length(0), map(0), map_size(0),
        the_allocator(Allocator()) 
    {
        insert(begin(), n, value);
    }
#endif

    deque (const deque<T,Allocator>& x)
        : start(), finish(), length(0), map(0), map_size(0)
    {
        the_allocator = x.get_allocator();
        copy(x.begin(), x.end(), back_inserter(*this));
    }


#if !defined(_RWSTD_NO_MEMBER_TEMPLATES)
    template<class InputIterator>
    deque (InputIterator first, InputIterator last, const Allocator& alloc = Allocator())
        : start(), finish(), length(0), map(0), map_size(0),
        the_allocator(alloc) 
    {
#if defined(__DECCXX) && !defined(__DECFIXCXXL485)
        __deque(first, last, __bool_traits<numeric_limits<InputIterator>::is_integer>::__bool_category());
#else
        copy(first, last, back_inserter(*this));
#endif
    }
#else
    deque (const_iterator first, const_iterator last, const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
        : start(), finish(), length(0), map(0), map_size(0),
        the_allocator(alloc) 
    {
        copy(first, last, back_inserter(*this));
    }
    
    deque (const T* first, const T* last, const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
        : start(), finish(), length(0), map(0), map_size(0),
        the_allocator(alloc) 
    {
        copy(first, last, back_inserter(*this));
    }

#ifdef _RWSTD_NO_DEFAULT_TEMPLATE_ARGS
    deque (const_iterator first, const_iterator last)
        : start(), finish(), length(0), map(0), map_size(0),
        the_allocator(Allocator()) 
    {
        copy(first, last, back_inserter(*this));
    }
    
    deque (const T* first, const T* last)
        : start(), finish(), length(0), map(0), map_size(0),
        the_allocator(Allocator()) 
    {
        copy(first, last, back_inserter(*this));
    }
#endif
#endif

    ~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);
    }
    //
    // Assign n copies of default value of type T to vector.
    // This requires that T have a default constructor.
    //
    template<class Size>
    void assign (Size n)
    {
#if defined(__DECCXX) && !defined(__DECFIXCXXL699)
        erase(begin(), end()); insert(begin(), (size_type) n, T());
#else
        erase(begin(), end()); insert(begin(), n, T());
#endif
    }
    //
    // Assign n copies of t to this vector.
    //
#   if defined(__DECCXX) && !defined(__DECFIXCXXL435)
       template<class Size, class U>
       void assign (Size n, const U& u)
       {
#if defined(__DECCXX) && !defined(__DECFIXCXXL699)
          erase(begin(), end()); insert(begin(), (size_type) n, u);
#else
          erase(begin(), end()); insert(begin(), n, u);
#endif
       }
#   else
       template<class Size, class T>
       void assign (Size n, const T& t)
       {
          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 default value of type T to vector.
    // This requires that T have a default constructor.
    //
    void assign (size_type n)
    {
        erase(begin(), end()); insert(begin(), n, T());
    }
    //
    // Assign n copies of t to this vector.
    //
    void assign (size_type n, const T& t)
    {
        erase(begin(), end()); insert(begin(), n, t);
    }
#endif
    allocator_type get_allocator() const
    {
        return the_allocator;
    }

    //
    // Iterators.
    //
    iterator         begin  ()       { return start;  }
    const_iterator   begin  () const { return start;  }
    iterator         end    ()       { return finish; }
    const_iterator   end    () const { return finish; }
    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.
    //
    size_type size     () const { return length;                    }
    size_type max_size () const 
    { return value_alloc_type(the_allocator).max_size(); }
    bool      empty    () const { return length == 0;               }
    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::rwse_OutOfRange);
      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::rwse_OutOfRange);
      return *(begin() + n);
#else
      return *(begin() + n);
#endif
    }
    const_reference at (size_type n)         const 
    { 
      _RWSTD_THROW(n >= size(), out_of_range, __RWSTD::rwse_OutOfRange);
      return *(begin() + n); 
    }
    reference       at (size_type n)
    { 
      _RWSTD_THROW(n >= size(), out_of_range, __RWSTD::rwse_OutOfRange);
      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) allocate_at_begin();
        --start.current;
        value_alloc_type(the_allocator).construct(start.current, x);
        ++length;
    }
    void push_back (const T& x)
    {
        if (empty() || end().current == end().last) allocate_at_end();
        value_alloc_type(the_allocator).construct(finish.current, x);
        ++finish.current;
        ++length;
    }
    //
    // Insert default value of type T at position.
    // Requires that T have a default constructor.
    //
    iterator insert (iterator position);
    //
    // Insert x at position.
    //
    iterator insert (iterator position, const T& x);
    void insert (iterator position, size_type n, const T& x);

#ifndef _RWSTD_NO_MEMBER_TEMPLATES
    template <class InputIterator>
#   if defined(__DECCXX) && !defined(__DECFIXCXXL484)
        void insert(iterator position, InputIterator first, InputIterator last);
#   else
        void insert(iterator position, Iterator first, Iterator last);
#   endif
#else
    void insert (iterator position, const T* first, const T* last);
    void insert (iterator position, const_iterator first, const_iterator last);
#endif

#if defined(__DECCXX) && !defined(__DECFIXCXXL485)
  private:
    void __insert (iterator position, size_type n, const T& x, __true_category);

#   ifndef _RWSTD_NO_MEMBER_TEMPLATES
        template<class InputIterator>
#       if defined(__DECCXX) && !defined(__DECFIXCXXL484)
           void __insert(iterator position, InputIterator first, InputIterator last, __false_category);
#       else
           void __insert(iterator position, Iterator first, Iterator last, __false_category);
#       endif
#   endif

  public:
#endif  //if defined(__DECCXX) && !defined(__DECFIXCXXL485)

    void pop_front ()
    {
        value_alloc_type(the_allocator).destroy(start.current);
        ++start.current;
        --length; 
        if (empty() || begin().current == begin().last) deallocate_at_begin();
    }
    void pop_back ()
    {
        --finish.current;
        value_alloc_type(the_allocator).destroy(finish.current);
        --length; 
        if (empty() || end().current == end().first) deallocate_at_end();
    }
    iterator erase (iterator position);
    iterator erase (iterator first, iterator last);    
    void clear()
    {
        erase(begin(),end());
    }
    void swap (deque<T,Allocator>& x)
    {
#ifndef _RWSTD_NO_NAMESPACE
        std::swap(start,          x.start);
        std::swap(finish,         x.finish);
        std::swap(length,         x.length);
        std::swap(map,            x.map);
        std::swap(map_size,       x.map_size);
        std::swap(the_allocator, x.the_allocator);
#else
        ::swap(start,             x.start);
        ::swap(finish,            x.finish);
        ::swap(length,            x.length);
        ::swap(map,               x.map);
        ::swap(map_size,          x.map_size);
        ::swap(the_allocator,    x.the_allocator);
#endif
    }
};

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);
}
#endif

#ifndef _RWSTD_MS40_NO_OVERLOAD_SWAP
template <class T, class Allocator>
inline void swap(deque<T,Allocator>& a, deque<T,Allocator>& b)
{
    a.swap(b);
}
#endif

#ifndef _RWSTD_NO_NAMESPACE
}
#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__*/