// -*- C++ -*-
#ifndef __STD_LIST__
#define __STD_LIST__

/***************************************************************************
 *
 * list - list declarations for the Standard Library
 *
 ***************************************************************************
 *    
 *  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.
 *
 **************************************************************************/


#include <stdcomp>

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

#ifndef list
#define list list
#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 list
  {
  protected:
    struct _RWlist_node;
    struct _RWlist_node_buffer;
    friend struct _RWlist_node;
    friend struct _RWlist_node_buffer;

#ifdef _RWSTD_ALLOCATOR
    typedef _TYPENAME Allocator::template rebind<_RWlist_node>::other  _RWlist_node_alloc_type;
    typedef _TYPENAME Allocator::template rebind<T>::other _RWvalue_alloc_type;
    typedef _TYPENAME Allocator::template rebind<_RWlist_node_buffer>::other  _RWbuffer_alloc_type;
#else
    typedef allocator_interface<Allocator,_RWlist_node>  _RWlist_node_alloc_type;
    typedef allocator_interface<Allocator,T>          _RWvalue_alloc_type;
    typedef allocator_interface<Allocator,_RWlist_node_buffer>   _RWbuffer_alloc_type;
#endif // _RWSTD_ALLOCATOR

  public:
    //
    // types
    //
    typedef _TYPENAME _RWvalue_alloc_type::reference        reference;
    typedef _TYPENAME _RWvalue_alloc_type::const_reference  const_reference;
    typedef _TYPENAME _RWvalue_alloc_type::size_type        size_type;
    typedef _TYPENAME _RWvalue_alloc_type::difference_type  difference_type;
    typedef T                                    value_type;
    typedef Allocator                            allocator_type;
    typedef _TYPENAME _RWvalue_alloc_type::pointer        pointer;
    typedef _TYPENAME _RWvalue_alloc_type::const_pointer  const_pointer;

  protected:
    typedef _TYPENAME _RWlist_node_alloc_type::pointer    _RWlink_type;
    typedef _TYPENAME _RWbuffer_alloc_type::pointer       _RWbuffer_pointer;

    struct _RWlist_node
    {
      ~_RWlist_node() { ; }
      _RWlink_type next;
      _RWlink_type prev;
      T           data;
    };

    struct _RWlist_node_buffer
    {
      ~_RWlist_node_buffer() { ; }
      _RWbuffer_pointer next_buffer;
      size_type        size;
      _RWlink_type      buffer;
    };

    size_type          _RWbuffer_size;    
    __RWSTD::_RWrw_basis<_RWbuffer_pointer,allocator_type>   _RWbuffer_list;
    _RWlink_type        _RWfree_list;
    _RWlink_type        _RWnext_avail;
    _RWlink_type        _RWlast;
    _RWlink_type        _RWnode;
    size_type          _RWlength;
    
    void _RWadd_new_buffer (size_type n)
    {
      _RWbuffer_pointer tmp = 
        _RWbuffer_alloc_type(_RWbuffer_list).allocate(
          _RWSTD_STATIC_CAST(size_type,1),_RWbuffer_list.data());
#ifndef _RWSTD_NO_EXCEPTIONS
      try {
        tmp->buffer = _RWlist_node_alloc_type(_RWbuffer_list).allocate(n,_RWlast);
      } catch(...) {
        _RWbuffer_alloc_type(_RWbuffer_list).deallocate(tmp,1);
        throw;
      }      
#else
      tmp->buffer = _RWlist_node_alloc_type(_RWbuffer_list).allocate(n,_RWlast);
#endif // _RWSTD_NO_EXCEPTIONS
      tmp->next_buffer = _RWbuffer_list;
      tmp->size = n;
      _RWbuffer_list = tmp;
      _RWnext_avail = _RWbuffer_list.data()->buffer;                
      _RWlast = _RWnext_avail + n;
    }
    void _RWdeallocate_buffers ();
    _RWlink_type _RWget_node (size_type n)
    {
      _RWlink_type tmp = _RWfree_list;
      return _RWfree_list ? (_RWfree_list = (_RWlink_type)(_RWfree_list->next), tmp) 
      : (_RWnext_avail == _RWlast ? (_RWadd_new_buffer(n), _RWnext_avail++) 
         : _RWnext_avail++);
    }
    void _RWput_node (_RWlink_type p) { p->next = _RWfree_list; _RWfree_list = p; }

    void _RWinit(size_type n = 0)  
    {
      _RWbuffer_size = max((size_type)1,
                        __RWSTD::_RWrw_allocation_size((value_type*)0,
                                                      (size_type)0,
                                                      (size_type)0));
      _RWnode = _RWget_node(n == 0 ? _RWbuffer_size : n);
      (*_RWnode).next = _RWnode;
      (*_RWnode).prev = _RWnode; 
    }
    void _RWinit(size_type n, value_type value)  
    {
      _RWinit(n);
#ifndef _RWSTD_NO_EXCEPTIONS
      try {
        insert(begin(), n, value);
      } catch(...) {
        _RWdeallocate_buffers();
        throw;
      }
#else
      insert(begin(), n, value);
#endif
    }

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

  public:
    
    class iterator;
    class const_iterator;
    friend class iterator;
    friend class const_iterator;

    class iterator : public _RWit
    {
      friend class list<T,Allocator>;
      friend class const_iterator;

    protected:
      
      _RWlink_type node;
      iterator (_RWlink_type x) : node(x) {}
    
    public:

      iterator () {}
      bool operator== (const iterator& x) const { return node == x.node; }
      bool operator!= (const iterator& x) const { return !(*this == x); }
      reference operator* () const { return (*node).data; } 
#ifndef _RWSTD_NO_NONCLASS_ARROW_RETURN
      pointer operator-> () const { return &(node->data); }
#endif
      iterator& operator++ ()
      { 
        node = (_RWlink_type)((*node).next); return *this;
      }
      iterator operator++ (int)
      {
        iterator tmp = *this; ++*this; return tmp;
      }
      iterator& operator-- ()
      {
        node = (_RWlink_type)((*node).prev); return *this;
      }
      iterator operator-- (int)
      {
        iterator tmp = *this; --*this; return tmp;
      }
    };  // End of definition of iterator class.

    class const_iterator : public _RWcit
    {
      friend class list<T,Allocator>;

    protected:
      
      _RWlink_type node;
      const_iterator (_RWlink_type x) : node(x) {}
    
    public:

      const_iterator () {}
#if defined(__DECCXX) && !defined(__DECFIXCXXL1195)
      const_iterator (const _TYPENAME list<T, Allocator>::iterator& x) : node(x.node) {}
#else
      const_iterator (const iterator& x) : node(x.node) {}
#endif
      bool operator== (const const_iterator& x) const {return node==x.node;}
      bool operator!= (const const_iterator x) const { return !(*this == x); } 
      const_reference operator* () const { return (*node).data; }
#ifndef _RWSTD_NO_NONCLASS_ARROW_RETURN
      const_pointer operator-> () const { return &(node->data); }
#endif
      const_iterator& operator++ ()
      { 
        node = (_RWlink_type)((*node).next); return *this;
      }
      const_iterator operator++ (int)
      {
        const_iterator tmp = *this; ++*this; return tmp;
      }
      const_iterator& operator-- ()
      {
        node = (_RWlink_type)((*node).prev); return *this;
      }
      const_iterator operator-- (int)
      {
        const_iterator tmp = *this;
        --*this;
        return tmp;
      }
    };  // End of definition of const_iterator class.

#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 _RWreverse_bi_iterator<const_iterator, 
      bidirectional_iterator_tag, value_type, 
      const_reference, const_pointer, difference_type>
      const_reverse_iterator;
    typedef _RWreverse_bi_iterator<iterator, 
      bidirectional_iterator_tag, value_type,
      reference, pointer, difference_type>
      reverse_iterator;
#endif

    //
    // construct/copy/destroy
    //
    list (const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator())) 
      : _RWlength(0), _RWbuffer_list(0,alloc),
        _RWfree_list(0), _RWnext_avail(0), _RWlast(0), _RWnode(0)
    {
      _RWinit(1);
    }
    
#ifdef _RWSTD_NO_DEFAULT_TEMPLATE_ARGS  
    list (void) 
      : _RWlength(0), _RWbuffer_list(0,Allocator()),
        _RWfree_list(0), _RWnext_avail(0), _RWlast(0), _RWnode(0)
    {
      _RWinit(1);
    }

    list (size_type n, const T& value)
      : _RWlength(0), _RWbuffer_list(0,Allocator()),
        _RWfree_list(0), _RWnext_avail(0), _RWlast(0), _RWnode(0)
    {
      _RWinit(n,value)
    }
#endif // _RWSTD_NO_DEFAULT_TEMPLATE_ARGS


    _EXPLICIT list (size_type n) 
      : _RWlength(0), _RWbuffer_list(0,Allocator()),
        _RWfree_list(0), _RWnext_avail(0), _RWlast(0), _RWnode(0)
    {
      T value = T();
      _RWinit(n,value);
    }

#ifndef _RWSTD_NO_MEMBER_TEMPLATES
    template<class InputIterator>
    list (InputIterator first, InputIterator locallast,
          const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
      : _RWlength(0), _RWbuffer_list(0,alloc),
        _RWfree_list(0), _RWnext_avail(0), _RWlast(0), _RWnode(0)
    {
      _RWinit();
#ifndef _RWSTD_NO_EXCEPTIONS
      try {
        insert(begin(), first, locallast);
      } catch(...) {
        _RWdeallocate_buffers();
        throw;
      }
#else
      insert(begin(), first, locallast);
#endif
    }
    list (int n, const T& value,
          const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
      :  _RWlength(0), _RWbuffer_list(0,alloc),
        _RWfree_list(0), _RWnext_avail(0), _RWlast(0), _RWnode(0)
    { _RWinit(n, value); }
    list (unsigned int n, const T& value,
          const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
      :  _RWlength(0), _RWbuffer_list(0,alloc),
        _RWfree_list(0), _RWnext_avail(0), _RWlast(0), _RWnode(0)
    { _RWinit(n, value); }
    list (long n, const T& value,
          const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
      :  _RWlength(0), _RWbuffer_list(0,alloc),
        _RWfree_list(0), _RWnext_avail(0), _RWlast(0), _RWnode(0)
    { _RWinit(n, value); }
    list (unsigned long n, const T& value,
          const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
      :  _RWlength(0), _RWbuffer_list(0,alloc),
        _RWfree_list(0), _RWnext_avail(0), _RWlast(0), _RWnode(0)
    { _RWinit(n, value); }
    list (short n, const T& value,
          const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
      :  _RWlength(0), _RWbuffer_list(0,alloc),
        _RWfree_list(0), _RWnext_avail(0), _RWlast(0), _RWnode(0)
    { _RWinit(n, value); }
    list (unsigned short n, const T& value,
          const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
      :  _RWlength(0), _RWbuffer_list(0,alloc),
        _RWfree_list(0), _RWnext_avail(0), _RWlast(0), _RWnode(0)
    { _RWinit(n, value); }
    list (char n, const T& value,
          const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
      :  _RWlength(0), _RWbuffer_list(0,alloc),
        _RWfree_list(0), _RWnext_avail(0), _RWlast(0), _RWnode(0)
    { _RWinit(n, value); }
    list (unsigned char n, const T& value,
          const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
      :  _RWlength(0), _RWbuffer_list(0,alloc),
        _RWfree_list(0), _RWnext_avail(0), _RWlast(0), _RWnode(0)
    { _RWinit(n, value); }
#ifndef _RWSTD_NO_BOOL
    list (bool n, const T& value,
          const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
      :  _RWlength(0), _RWbuffer_list(0,alloc),
        _RWfree_list(0), _RWnext_avail(0), _RWlast(0), _RWnode(0)
    { _RWinit(n, value); }
#endif
#ifndef _RWSTD_NO_OVERLOAD_WCHAR
    list (wchar_t n, const T& value,
          const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
      :  _RWlength(0), _RWbuffer_list(0,alloc),
        _RWfree_list(0), _RWnext_avail(0), _RWlast(0), _RWnode(0)
    { _RWinit(n, value); }
#endif // _RWSTD_NO_OVERLOAD_WCHAR
#else
    //
    // Build a list of size n with each element set to a copy of value.
    //
    list (size_type n, const T& value,
          const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator())) 
      : _RWlength(0), _RWbuffer_list(0,alloc),
       _RWfree_list(0), _RWnext_avail(0), _RWlast(0), _RWnode(0)
    {
      _RWinit(n, value);
    }

    list (const_iterator first, const_iterator locallast,
          const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
      : _RWlength(0), _RWbuffer_list(0,alloc),
        _RWfree_list(0), _RWnext_avail(0), _RWlast(0), _RWnode(0)
    {
      _RWinit();
#ifndef _RWSTD_NO_EXCEPTIONS
      try {
        insert(begin(), first, locallast);
      } catch(...) {
        _RWdeallocate_buffers();
        throw;
      }
#else
      insert(begin(), first, locallast);
#endif
    }
    list (const T* first, const T* locallast,
          const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
      : _RWlength(0), _RWbuffer_list(0,alloc),
       _RWfree_list(0), _RWnext_avail(0), _RWlast(0), _RWnode(0)
    {
      _RWinit();
#ifndef _RWSTD_NO_EXCEPTIONS
      try {
        insert(begin(), first, locallast);
      } catch(...) {
        _RWdeallocate_buffers();
        throw;
      }
#else
      insert(begin(), first, locallast);
#endif
    }

#ifdef _RWSTD_NO_DEFAULT_TEMPLATE_ARGS
    list (const_iterator first, const_iterator locallast)
      : _RWlength(0), _RWbuffer_list(0,Allocator()),
        _RWfree_list(0), _RWnext_avail(0), _RWlast(0), _RWnode(0)
    {
      _RWinit();
#ifndef _RWSTD_NO_EXCEPTIONS
      try {
        insert(begin(), first, locallast);
      } catch(...) {
        _RWdeallocate_buffers();
        throw;
      }
#else
      insert(begin(), first, locallast);
#endif
    }

    list (const T* first, const T* locallast)
      : _RWlength(0), _RWbuffer_list(0,Allocator()),
        _RWfree_list(0), _RWnext_avail(0), _RWlast(0), _RWnode(0)
    {
      _RWinit();
#ifndef _RWSTD_NO_EXCEPTIONS
      try {
        insert(begin(), first, locallast);
      } catch(...) {
        _RWdeallocate_buffers();
        throw;
      }
#else
      insert(begin(), first, locallast);
#endif
    }
#endif // _RWSTD_NO_DEFAULT_TEMPLATE_ARGS
#endif // _RWSTD_NO_MEMBER_TEMPLATES

    list (const list<T,Allocator>& x) : _RWlength(0), _RWbuffer_list(0,x.get_allocator()),
      _RWfree_list(0), _RWnext_avail(0), _RWlast(0), _RWnode(0)
    {
      _RWinit();
#ifndef _RWSTD_NO_EXCEPTIONS
      try {
        insert(begin(), x.begin(), x.end());
      } catch(...) {
        _RWdeallocate_buffers();
        throw;
      }
#else
#if defined(__DECCXX) && !defined(__DECFIXCXXL1115)
      insert(begin(), x.begin(), x.end());
#else
      insert(begin(), first, locallast);
#endif
#endif
    }

    ~list ()
    {
      if (_RWnode)
      {
        erase(begin(), end());
        _RWput_node(_RWnode);
        _RWdeallocate_buffers();
      }
    }
    list<T,Allocator>& operator= (const list<T,Allocator>& x);   

#ifndef _RWSTD_NO_MEMBER_TEMPLATES
    template<class InputIterator>
    void assign (InputIterator first, InputIterator _RWlast)
    { erase(begin(), end()); insert(begin(), first, _RWlast);  }
    //
    // Assign n copies of t to this list.
    //
#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 list.
    //
    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)_RWbuffer_list;
    }

    //
    // Iterators.
    //
    iterator       begin ()       { return _RWSTD_STATIC_CAST(_RWlink_type,((*_RWnode).next)); }
    const_iterator begin () const { return _RWSTD_STATIC_CAST(_RWlink_type,((*_RWnode).next)); }

    iterator       end ()         { return _RWnode;                      }
    const_iterator end ()   const { return _RWnode;                      }
    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 _RWlist_node_alloc_type(_RWbuffer_list).max_size(); }
    void resize (size_type new_size);
    void resize (size_type new_size, T value);

    //
    // Element access.
    //
    reference       front ()       { return *begin();   }
    const_reference front () const { return *begin();   }
    reference       back  ()       { return *(--end()); }
    const_reference back  () const { return *(--end()); }

    //
    // Modifiers.
    //
    //
    void push_front (const T& x) { insert(begin(), x); }
    void push_back  (const T& x) { insert(end(), x);   }
    void pop_front  ()           { erase(begin());     }
    void pop_back   ()           { iterator tmp = end(); erase(--tmp); }

    //
    // Insert x at position.
    //
    iterator insert (iterator position, const T& x)
    {
      _RWvalue_alloc_type va(_RWbuffer_list);
      _RWlink_type tmp = _RWget_node(_RWbuffer_size);
#ifndef _RWSTD_NO_EXCEPTIONS
      try {
       va.construct(va.address((*tmp).data),x);
      } catch(...) {
        _RWput_node(tmp);
        throw;
      }      
#else
      va.construct(va.address((*tmp).data),x);
#endif // _RWSTD_NO_EXCEPTIONS
      (*tmp).next = position.node;
      (*tmp).prev = (*position.node).prev;
      (*(_RWlink_type((*position.node).prev))).next = tmp;
      (*position.node).prev = tmp;
      ++_RWlength;
      return tmp;
    }

#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

    iterator erase (iterator position)
    {
      if (position == end())
        return end();
      iterator tmp = (iterator)(_RWlink_type((*position.node).next));
      (*(_RWlink_type((*position.node).prev))).next = (*position.node).next;
      (*(_RWlink_type((*position.node).next))).prev = (*position.node).prev;
      --_RWlength;
      _RWvalue_alloc_type va(_RWbuffer_list);
      va.destroy(va.address((*position.node).data));
      _RWput_node(position.node);
      return tmp;
    }
    iterator erase      (iterator first, iterator last);
    void swap (list<T,Allocator>& x)
    {
      if((allocator_type)_RWbuffer_list==(allocator_type)x._RWbuffer_list)
      {

#ifndef _RWSTD_NO_NAMESPACE
        std::swap(_RWnode, x._RWnode); 
        std::swap(_RWlength, x._RWlength);
        std::swap(_RWbuffer_list,x._RWbuffer_list);
        std::swap(_RWfree_list,x._RWfree_list);
        std::swap(_RWnext_avail,x._RWnext_avail);
        std::swap(_RWlast,x._RWlast);
#else
        ::swap(_RWnode, x._RWnode); 
        ::swap(_RWlength, x._RWlength);
        ::swap(_RWbuffer_list,x._RWbuffer_list);
        ::swap(_RWfree_list,x._RWfree_list);
        ::swap(_RWnext_avail,x._RWnext_avail);
        ::swap(_RWlast,x._RWlast);
#endif // _RWSTD_NO_NAMESPACE
      }
      else
      {
        list<T,Allocator> _x = *this;
        *this=x;
        x=_x;
      }
    }

    void clear()
    {
      erase(begin(),end());
    }

  protected:
    
    void _RWtransfer (iterator position, iterator first, 
                   iterator last, list<T,Allocator>& x)
    {
      if (this == &x)
      {
        (*(_RWlink_type((*last.node).prev))).next = position.node;
        (*(_RWlink_type((*first.node).prev))).next = last.node;
        (*(_RWlink_type((*position.node).prev))).next = first.node;  
        _RWlink_type tmp = _RWlink_type((*position.node).prev);
        (*position.node).prev = (*last.node).prev;
        (*last.node).prev = (*first.node).prev; 
        (*first.node).prev = tmp;
      }
      else
      {
        insert(position,first,last);
        x.erase(first,last);
      }
    }

    // used by the sort() member function
    void _RWset_allocator(allocator_type a)
    {  
      _RWbuffer_list = a; 
    }
    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:

    //
    // list operations.
    //
    void splice (iterator position, list<T,Allocator>& x)
    {
      if (!x.empty())
        _RWtransfer(position, x.begin(), x.end(), x);
    }
    void splice (iterator position, list<T,Allocator>& x, iterator i)
    { 
      iterator k = i;
      if (k != position && ++k != position)
      {
        iterator j = i;
        _RWtransfer(position, i, ++j, x);
      }
    }
    void splice (iterator position, list<T,Allocator>& x, iterator first, iterator last)
    {
      if (first != last)
      {
        difference_type n;
        _RWinitialize(n, difference_type(0));
        distance(first, last, n);
        _RWtransfer(position, first, last, x);
      }
    }
    void remove  (const T& value);
    void unique  ();
    void merge   (list<T,Allocator>& x);
    void reverse ();
    void sort    ();

#ifndef _RWSTD_NO_MEMBER_TEMPLATES
    template<class Predicate>       void remove_if (Predicate pred);
    template<class BinaryPredicate> void unique    (BinaryPredicate pred);
    template<class Compare>         void merge     (list<T,Allocator>& x, Compare comp);
    template<class Compare>         void sort      (Compare comp);
#endif // _RWSTD_NO_MEMBER_TEMPLATES

#ifndef _RWSTD_STRICT_ANSI
    // Non-standard function for setting buffer allocation size
    size_type allocation_size() { return _RWbuffer_size; }
    size_type allocation_size(size_type new_size) 
    { 
      size_type tmp = _RWbuffer_size; 
      _RWbuffer_size = max((size_type)1,new_size);
      return tmp;
    }
#endif // _RWSTD_STRICT_ANSI
  };

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

  template <class T, class Allocator>
  inline bool operator< (const list<T,Allocator>& x, const list<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 list<T,Allocator>& x, const list<T,Allocator>& y)
  {
    return !(x == y);
  }

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

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

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

  template <class T, class Allocator>
  inline void swap(list<T,Allocator>& a, list<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 <list.cc>
#endif

#undef list

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

#endif /*__STD_LIST__*/
