#ifndef __STD_LIST__
#define __STD_LIST__
//
//
//  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.
//
//

/***************************************************************************
 *
 * list - list declarations for the Standard Library
 *
 * $Id: list,v 1.71 1996/09/30 02:28:53 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.
 *
 **************************************************************************/


#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 

#ifndef list
#define list list
#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 list
{
  __DECPROTECTED:
    struct list_node;
    friend struct list_node;

#ifdef _RWSTD_ALLOCATOR
    typedef _TYPENAME Allocator::rebind<void>::other::pointer  void_pointer;
#else
    typedef allocator_interface<Allocator,T>::void_pointer void_pointer;
#endif

    struct list_node
    {
        ~list_node() { ; }
        void_pointer next;
        void_pointer prev;
        T            data;
    };

    struct list_node_buffer;
    friend struct list_node_buffer;


#ifdef _RWSTD_ALLOCATOR
    typedef _TYPENAME Allocator::rebind<list_node>::other list_node_alloc_type;
    typedef _TYPENAME Allocator::rebind<charT>::other     value_alloc_type;
#if defined (__DECCXX) && (__CFRONT || __MS) // CXXC_BUGS 3881
#else
    typedef _TYPENAME Allocator::rebind<list_node_buffer>::other buffer_alloc_type;
#endif
#else
    typedef allocator_interface<Allocator,list_node>  list_node_alloc_type;
    typedef allocator_interface<Allocator,T>          value_alloc_type;
#if defined (__DECCXX) && (__CFRONT || __MS) // CXXC_BUGS 3881
#else
    typedef allocator_interface<Allocator,list_node_buffer>   buffer_alloc_type;
#endif
#endif
    typedef _TYPENAME list_node_alloc_type::pointer       link_type;

    Allocator the_allocator;


  public:
    //
    // types
    //
    typedef Allocator                          allocator_type;
    typedef T                                  value_type;
    typedef value_alloc_type::size_type        size_type;
    typedef value_alloc_type::difference_type  difference_type;
    typedef value_alloc_type::reference        reference;
    typedef value_alloc_type::const_reference  const_reference;

  protected:

    static size_type buffer_size ()
    {
        //
        // Each time we allocate memory we reserve space for
        // this many nodes.  This is currently tuned to
        // allocate memory in 1K chunks, except for large objects.
        //
        return sizeof(list_node) >= 1024 ? 1 : 1024 / sizeof(list_node);
    };
    
    struct list_node_buffer
    {
        ~list_node_buffer() { ; }
        void_pointer next_buffer;
        link_type    buffer;
    };


#ifdef _RWSTD_ALLOCATOR
#if defined (__DECCXX) && (__CFRONT || __MS) // CXXC_BUGS 3881
    typedef _TYPENAME Allocator::rebind<list_node_buffer>::other buffer_alloc_type;
#endif
#else
#if defined (__DECCXX) && (__CFRONT || __MS) // CXXC_BUGS 3881
    typedef allocator_interface<Allocator,list_node_buffer>   buffer_alloc_type;
#endif
#endif

    
  protected:

    typedef _TYPENAME value_alloc_type::pointer        pointer;
    typedef _TYPENAME value_alloc_type::const_pointer  const_pointer;
    typedef _TYPENAME buffer_alloc_type::pointer       buffer_pointer;

    buffer_pointer                buffer_list;
    link_type                     free_list;
    link_type                     next_avail;
    link_type                     last;
    
    void add_new_buffer (size_type n = buffer_size())
    {
        buffer_pointer tmp = 
                     buffer_alloc_type(the_allocator).allocate(
                     _RWSTD_STATIC_CAST(size_type,1),buffer_list);
        tmp->buffer = list_node_alloc_type(the_allocator).allocate(n,last);
        tmp->next_buffer = buffer_list;
        buffer_list = tmp;
        next_avail = buffer_list->buffer;                
        last = next_avail + n;
    }
    void deallocate_buffers ();
    link_type get_node (size_type n = buffer_size())
    {
        link_type tmp = free_list;
        return free_list ? (free_list = (link_type)(free_list->next), tmp) 
            : (next_avail == last ? (add_new_buffer(n), next_avail++) 
               : next_avail++);
    }
    void put_node (link_type p) { p->next = free_list; free_list = p; }


  protected:
    
    link_type node;
    size_type length;

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

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

      __DECPROTECTED:
      
        link_type node;
        iterator (link_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; }
        pointer operator->() const { return &operator*(); } 
        iterator& operator++ ()
        { 
            node = (link_type)((*node).next); return *this;
        }
        iterator operator++ (int)
        {
            iterator tmp = *this; ++*this; return tmp;
        }
        iterator& operator-- ()
        {
            node = (link_type)((*node).prev); return *this;
        }
        iterator operator-- (int)
        {
            iterator tmp = *this; --*this; return tmp;
        }
    };  // End of definition of iterator class.

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

      __DECPROTECTED:
      
        link_type node;
        const_iterator (link_type x) : node(x) {}
    
      public:

        const_iterator () {}
        const_iterator (const iterator& x) : node(x.node) {}
        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; }
	const_pointer operator->() const { return (const_pointer) &operator*(); }
        const_iterator& operator++ ()
        { 
            node = (link_type)((*node).next); return *this;
        }
        const_iterator operator++ (int)
        {
            const_iterator tmp = *this; ++*this; return tmp;
        }
        const_iterator& operator-- ()
        {
            node = (link_type)((*node).prev); return *this;
        }
        const_iterator operator-- (int)
        {
            const_iterator tmp = *this;
            --*this;
            return tmp;
        }
    };  // End of definition of const_iterator class.

    typedef _STD::reverse_bidirectional_iterator<const_iterator, value_type,
                                const_reference, const_pointer, difference_type>
            const_reverse_iterator;
    typedef _STD::reverse_bidirectional_iterator<iterator, value_type, reference,
                                           pointer,difference_type>
            reverse_iterator;

    //
    // construct/copy/destroy
    //
    list (const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator())) 
         : length(0), the_allocator(alloc), buffer_list(0),
           free_list(0), next_avail(0), last(0)
    {
        node = get_node(1);
        (*node).next = node;
        (*node).prev = node;
    }
    
#ifdef _RWSTD_NO_DEFAULT_TEMPLATE_ARGS	
    list (void) 
         : length(0), the_allocator(Allocator()), buffer_list(0),
           free_list(0), next_avail(0), last(0)
    {
        node = get_node(1);
        (*node).next = node;
        (*node).prev = node;
    }
#endif
    //
    // Build a list of size n with each element set to default for type T.
    // This requires that T have a default constructor.
    //
    _EXPLICIT list (size_type n, const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator())) 
         : length(0), the_allocator(alloc), buffer_list(0),
           free_list(0), next_avail(0), last(0)
    {
        node = get_node(n);
        (*node).next = node;
        (*node).prev = node;
        T value;
        insert(begin(), n, value);
    }

    //
    // 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())) 
         : length(0), the_allocator(alloc), buffer_list(0),
           free_list(0), next_avail(0), last(0)
    {
        node = get_node(n);
        (*node).next = node;
        (*node).prev = node;
        insert(begin(), n, value);
    }

#ifdef _RWSTD_NO_DEFAULT_TEMPLATE_ARGS
    _EXPLICIT list (size_type n) 
         : length(0), the_allocator(Allocator()), buffer_list(0),
           free_list(0), next_avail(0), last(0)
    {
        T value;
        node        = get_node(n);
        (*node).next = node;
        (*node).prev = node;
        insert(begin(), n, value);
    }

    list (size_type n, const T& value)
         : length(0), the_allocator(Allocator()), buffer_list(0),
           free_list(0), next_avail(0), last(0)
    {
        node        = get_node(n);
        (*node).next = node;
        (*node).prev = node;
        insert(begin(), n, value);
    }
#endif

#ifndef _RWSTD_NO_MEMBER_TEMPLATES
    template<class InputIterator>
    list (InputIterator first, InputIterator locallast,
                    const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
         : length(0), the_allocator(alloc), buffer_list(0),
           free_list(0), next_avail(0), last(0)
    {
        node = get_node();
        (*node).next = node;
        (*node).prev = node;
        insert(begin(), first, locallast);
    }
#else
    list (const_iterator first, const_iterator locallast,
                  const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
         : length(0), the_allocator(alloc), buffer_list(0),
           free_list(0), next_avail(0), last(0)
    {
        node = get_node();
        (*node).next = node;
        (*node).prev = node;
        insert(begin(), first, locallast);
    }
    list (const T* first, const T* locallast,
                  const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
         : length(0), the_allocator(alloc), buffer_list(0),
           free_list(0), next_avail(0), last(0)
    {
        node = get_node();
        (*node).next = node;
        (*node).prev = node;
        insert(begin(), first, locallast);
    }

#ifdef _RWSTD_NO_DEFAULT_TEMPLATE_ARGS
    list (const_iterator first, const_iterator locallast)
         : length(0), the_allocator(Allocator()), buffer_list(0),
           free_list(0), next_avail(0), last(0)
    {
        node = get_node();
        (*node).next = node;
        (*node).prev = node;
        insert(begin(), first, locallast);
    }
    list (const T* first, const T* locallast)
         : length(0), the_allocator(Allocator()), buffer_list(0),
           free_list(0), next_avail(0), last(0)
    {
        node = get_node();
        (*node).next = node;
        (*node).prev = node;
        insert(begin(), first, locallast);
    }
#endif
#endif

    list (const list<T,Allocator>& x) : length(0), buffer_list(0),
           free_list(0), next_avail(0), last(0)
    {
        the_allocator = x.get_allocator();
        node = get_node();
        (*node).next = node;
        (*node).prev = node;
        insert(begin(), x.begin(), x.end());
    }
    ~list ()
    {
        erase(begin(), end());
        put_node(node);
	deallocate_buffers();
    }
    list<T,Allocator>& operator= (const list<T,Allocator>& x);   

#ifndef _RWSTD_NO_MEMBER_TEMPLATES
    template<class InputIterator>
    void assign (InputIterator first, InputIterator last)
    {
        erase(begin(), end()); insert(begin(), first, last);
    }
#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);
    }
#endif
    //
    // Assign n copies of default value of type T to list.
    // This requires that T have a default constructor.
    //
#ifndef _RWSTD_NO_MEMBER_TEMPLATES
    template<class Size, class T>
    void assign (Size n)
#else
    void assign (size_type n)
#endif
    {
        erase(begin(), end()); insert(begin(), n, T());
    }
    //
    // Assign n copies of t to this list.
    //
#ifndef _RWSTD_NO_MEMBER_TEMPLATES
    template<class Size, class T>
    void assign (Size n, const T& t)
#else
    void assign (size_type n, const T& t)
#endif
    {
        erase(begin(), end()); insert(begin(), n, t);
    }
    allocator_type get_allocator() const
    {
        return the_allocator;
    }

    public:

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

    iterator       end ()         { return node;                      }
    const_iterator end ()   const { return node;                      }
    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 length == 0;                }
    size_type size ()     const { return length;                     }
    size_type max_size () const 
    { return list_node_alloc_type(the_allocator).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.
    //
    //
    // Insert default value of type T at position.
    // Requires that T have a default constructor.
    //
    iterator insert (iterator position)
    {
        value_alloc_type va(the_allocator);
        link_type tmp = get_node();
        va.construct(va.address((*tmp).data),T());
        (*tmp).next = position.node;
        (*tmp).prev = (*position.node).prev;
        (*(link_type((*position.node).prev))).next = tmp;
        (*position.node).prev = tmp;
        ++length;
        return tmp;
    }
    //
    // Insert x at position.
    //
    iterator insert (iterator position, const T& x)
    {
        value_alloc_type va(the_allocator);
        link_type tmp = get_node();
        va.construct(va.address((*tmp).data),x);
        (*tmp).next = position.node;
        (*tmp).prev = (*position.node).prev;
        (*(link_type((*position.node).prev))).next = tmp;
        (*position.node).prev = tmp;
        ++length;
        return tmp;
    }
    void insert (iterator position, size_type n, const T& x);

#ifndef _RWSTD_NO_MEMBER_TEMPLATES
    template<class InputIterator>
    void insert (iterator position, InputIterator first, InputIterator last);
#else
    void insert (iterator position, const T* first, const T* last);
    void insert (iterator position, const_iterator first, const_iterator last);
#endif

    iterator erase (iterator position)
    {
        if (position == end())
           return end();
        iterator tmp = (iterator)(link_type((*position.node).next));
        (*(link_type((*position.node).prev))).next = (*position.node).next;
        (*(link_type((*position.node).next))).prev = (*position.node).prev;
        value_alloc_type va(the_allocator);
        va.destroy(va.address((*position.node).data));
        put_node(position.node);
        --length;
        return tmp;
    }
    iterator erase      (iterator first, iterator last);
    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); }
    void swap (list<T,Allocator>& x)
    {
#ifndef _RWSTD_NO_NAMESPACE
        std::swap(node, x.node); 
        std::swap(length, x.length);
        std::swap(buffer_list,x.buffer_list);
        std::swap(free_list,x.free_list);
        std::swap(next_avail,x.next_avail);
        std::swap(the_allocator,x.the_allocator);
        std::swap(last,x.last);
#else
        ::swap(node, x.node); 
        ::swap(length, x.length);
        ::swap(buffer_list,x.buffer_list);
        ::swap(free_list,x.free_list);
        ::swap(next_avail,x.next_avail);
        ::swap(the_allocator,x.the_allocator);
        ::swap(last,x.last);
#endif
    }
    void clear()
    {
        erase(begin(),end());
    }

  protected:
    
    void transfer (iterator position, iterator first, 
                   iterator last, list<T,Allocator>& x)
    {
      if (this == &x)
      {
        (*(link_type((*last.node).prev))).next = position.node;
        (*(link_type((*first.node).prev))).next = last.node;
        (*(link_type((*position.node).prev))).next = first.node;  
        link_type tmp = link_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 set_allocator(allocator_type a)
    {  
        the_allocator = a; 
    }

  public:

    //
    // list operations.
    //
    void splice (iterator position, list<T,Allocator>& x)
    {
        if (!x.empty())
            transfer(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;
          transfer(position, i, ++j, x);
        }
    }
    void splice (iterator position, list<T,Allocator>& x, iterator first, iterator last)
    {
        if (first != last)
        {
            difference_type n;
            __initialize(n, difference_type(0));
            distance(first, last, n);
            transfer(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
};

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


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

#ifndef _RWSTD_NO_NAMESPACE
}
#endif


/***************************************************************************
 *
 * list.cc - Non-nline list definitions for the Standard Library
 *
 * $Id: list.cc,v 1.4 1996/08/28 18:42:09 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.
 *
 **************************************************************************/

#include <stdcomp>

#define _RWSTD_LIST_SORT_COUNTERS 64

#ifndef _RWSTD_NO_NAMESPACE
namespace std {
#endif

template <class T, class Allocator>
void list<T,Allocator>::deallocate_buffers ()
{
    while (buffer_list)
    {
        buffer_pointer tmp = buffer_list;
        buffer_list = (buffer_pointer)(buffer_list->next_buffer);
        list_node_alloc_type(the_allocator).deallocate(tmp->buffer);
        buffer_alloc_type(the_allocator).deallocate(tmp);
    }
    free_list = 0;
    next_avail = 0;
    last = 0;
}

//
// This requires that T have a default constructor.
//

template <class T, class Allocator>
void list<T,Allocator>::resize (size_type new_size)
{
    T value;
    if (new_size > size())
        insert(end(), new_size - size(), value);
    else if (new_size < size())
    {
        iterator tmp = begin();
        advance(tmp, (difference_type) new_size);
        erase(tmp, end());
    }
}

template <class T, class Allocator>
void list<T,Allocator>::resize (size_type new_size, T value)
{
    if (new_size > size())
        insert(end(), new_size - size(), value);
    else if (new_size < size())
    {
        iterator tmp = begin();
        advance(tmp, (difference_type) new_size);
        erase(tmp, end());
    }
}

#ifndef _RWSTD_NO_MEMBER_TEMPLATES
template <class T, class Allocator>   
template<class InputIterator>
void list<T,Allocator>::insert (iterator position, InputIterator first,
                      InputIterator locallast)
{
    while (first != locallast) insert(position, *first++);
}
#else
template <class T, class Allocator>   
void list<T, Allocator>::insert (list<T, Allocator>::iterator position, 
                       list<T, Allocator>::const_iterator first,
                       list<T, Allocator>::const_iterator locallast)
{
    while (first != locallast) insert(position, *first++);
}
template <class T, class Allocator>
void list<T, Allocator>::insert (list<T, Allocator>::iterator position, 
                                 const T* first, const T* locallast)
{
    while (first != locallast) insert(position, *first++);
}
#endif

template <class T, class Allocator>
void list<T, Allocator>::insert (list<T, Allocator>::iterator position, 
                                 size_type n, const T& x)
{
    while (n--) insert(position, x);
}

template <class T, class Allocator>
_TYPENAME list<T, Allocator>::iterator 
list<T, Allocator>::erase (list<T, Allocator>::iterator first, 
                           list<T, Allocator>::iterator locallast)
{
    iterator tmp = end();
    while (first != locallast) 
    {
      tmp = erase(first++);
    }
    return tmp;
}

template <class T, class Allocator>
list<T, Allocator>& list<T, Allocator>::operator= (const list<T, Allocator>& x)
{
    if (this != &x)
    {
        iterator first1 = begin();
        iterator last1 = end();
        const_iterator first2 = x.begin();
        const_iterator last2 = x.end();
        while (first1 != last1 && first2 != last2) *first1++ = *first2++;
        if (first2 == last2)
            erase(first1, last1);
        else
            insert(last1, first2, last2);
    }
    return *this;
}

template <class T, class Allocator>
void list<T, Allocator>::remove (const T& value)
{
    iterator first = begin();
    iterator last = end();
    while (first != last)
    {
        iterator next = first;
        ++next;
        if (*first == value) erase(first);
        first = next;
    }
}

template <class T, class Allocator>
void list<T, Allocator>::unique ()
{
    iterator first = begin();
    iterator last = end();
    if (first == last) return;
    iterator next = first;
    while (++next != last)
    {
        if (*first == *next)
            erase(next);
        else
            first = next;
        next = first;
    }
}

template <class T, class Allocator>
void list<T, Allocator>::merge (list<T, Allocator>& x)
{
    iterator first1 = begin();
    iterator last1 = end();
    iterator first2 = x.begin();
    iterator last2 = x.end();
    while (first1 != last1 && first2 != last2)
    {
        if (*first2 < *first1)
        {
            iterator next = first2;
            transfer(first1, first2, ++next, x);
            first2 = next;
        }
        else
            first1++;
    }
    if (first2 != last2) 
        transfer(last1, first2, last2, x);
}

template <class T, class Allocator>
void list<T, Allocator>::reverse ()
{
    if (size() < 2) return;
    for (iterator first = ++begin(); first != end();)
    {
        iterator old = first++;
        transfer(begin(), old, first, *this);
    }
}    


template <class T, class Allocator>
void list<T, Allocator>::sort ()
{
    if (size() < 2) return;

    list<T, Allocator> carry(get_allocator());
    list<T, Allocator> counter[_RWSTD_LIST_SORT_COUNTERS];
    for (int i = 0; i < _RWSTD_LIST_SORT_COUNTERS; i++)
      counter[i].set_allocator(get_allocator());

    int fill = 0;
    while (!empty())
    {
        carry.splice(carry.begin(), *this, begin());

        int i = 0;
        while (i < fill && !counter[i].empty())
        {
            counter[i].merge(carry);
            carry.swap(counter[i++]);
        }
        carry.swap(counter[i]);         
        if (i == fill) ++fill;
    } 
    while (fill--) 
    {  
      merge(counter[fill]);
    }
}

#ifndef _RWSTD_NO_MEMBER_TEMPLATES
template<class T, class Allocator>
template<class Predicate> void list<T, Allocator>::remove_if (Predicate pred)
{
    iterator first = begin();
    iterator last = end();
    while (first != last)
    {
        iterator next = first;
        ++next;
        if (pred(*first)) erase(first);
        first = next;
    }
}

template<class T, class Allocator>
template<class BinaryPredicate> void list<T, Allocator>::unique (BinaryPredicate pred)
{
    iterator first = begin();
    iterator last = end();
    if (first == last) return;
    iterator next = first;
    while (++next != last)
    {
        if (pred(*first, *next))
            erase(next);
        else
            first = next;
        next = first;
    }
}

template<class T, class Allocator>
template<class Compare> void list<T, Allocator>::merge (list<T, Allocator>& x, Compare comp)
{
    iterator first1 = begin();
    iterator last1  = end();
    iterator first2 = x.begin();
    iterator last2  = x.end();
    while (first1 != last1 && first2 != last2)
    {
        if (comp(*first2, *first1))
        {
            iterator next = first2;
            transfer(first1, first2, ++next, x);
            first2 = next;
        }
        else
            first1++;
    }
    if (first2 != last2) 
        transfer(last1, first2, last2, x);
}

template<class T, class Allocator>
template<class Compare> void list<T, Allocator>::sort (Compare comp)
{
    if (size() < 2) return;

    list<T, Allocator> carry(get_allocator());
    list<T, Allocator> counter[ _RWSTD_LIST_SORT_COUNTERS];
    for (int i = 0; i < _RWSTD_LIST_SORT_COUNTERS; i++)
      counter[i].set_allocator(get_allocator());
    int fill = 0;
    while (!empty())
    {
        carry.splice(carry.begin(), *this, begin());
        int i = 0;
        while (i < fill && !counter[i].empty())
        {
            counter[i].merge(carry, comp);
            carry.swap(counter[i++]);
        }
        carry.swap(counter[i]);         
        if (i == fill) ++fill;
    } 
    while (fill--) merge(counter[fill]);
}
#endif /*_RWSTD_NO_MEMBER_TEMPLATES*/

#undef _RWSTD_LIST_SORT_COUNTERS

#ifndef _RWSTD_NO_NAMESPACE
}
#endif

#undef list


#endif /*__STD_LIST__*/