home *** CD-ROM | disk | FTP | other *** search
/ PC Plus SuperCD (UK) 2000 May / PCP163A.iso / Runimage / Cbuilder4 / Include / LIST.H < prev    next >
Encoding:
C/C++ Source or Header  |  1999-01-26  |  29.7 KB  |  895 lines
  1. #ifndef __LIST_H
  2. #define __LIST_H
  3. #pragma option push -b -a8 -pc -Vx- -Ve- -w-inl -w-aus -w-sig
  4. // -*- C++ -*-
  5. #ifndef __STD_LIST__
  6. #define __STD_LIST__
  7.  
  8. /***************************************************************************
  9.  *
  10.  * list - list declarations for the Standard Library
  11.  *
  12.  ***************************************************************************
  13.  *
  14.  * Copyright (c) 1994
  15.  * Hewlett-Packard Company
  16.  *
  17.  * Permission to use, copy, modify, distribute and sell this software
  18.  * and its documentation for any purpose is hereby granted without fee,
  19.  * provided that the above copyright notice appear in all copies and
  20.  * that both that copyright notice and this permission notice appear
  21.  * in supporting documentation.  Hewlett-Packard Company makes no
  22.  * representations about the suitability of this software for any
  23.  * purpose.  It is provided "as is" without express or implied warranty.
  24.  *
  25.  *
  26.  ***************************************************************************
  27.  *
  28.  * (c) Copyright 1994, 1998 Rogue Wave Software, Inc.
  29.  * ALL RIGHTS RESERVED
  30.  *
  31.  * The software and information contained herein are proprietary to, and
  32.  * comprise valuable trade secrets of, Rogue Wave Software, Inc., which
  33.  * intends to preserve as trade secrets such software and information.
  34.  * This software is furnished pursuant to a written license agreement and
  35.  * may be used, copied, transmitted, and stored only in accordance with
  36.  * the terms of such license and with the inclusion of the above copyright
  37.  * notice.  This software and information or any other copies thereof may
  38.  * not be provided or otherwise made available to any other person.
  39.  *
  40.  * Notwithstanding any other lease or license that may pertain to, or
  41.  * accompany the delivery of, this computer software and information, the
  42.  * rights of the Government regarding its use, reproduction and disclosure
  43.  * are as set forth in Section 52.227-19 of the FARS Computer
  44.  * Software-Restricted Rights clause.
  45.  * 
  46.  * Use, duplication, or disclosure by the Government is subject to
  47.  * restrictions as set forth in subparagraph (c)(1)(ii) of the Rights in
  48.  * Technical Data and Computer Software clause at DFARS 252.227-7013.
  49.  * Contractor/Manufacturer is Rogue Wave Software, Inc.,
  50.  * P.O. Box 2328, Corvallis, Oregon 97339.
  51.  *
  52.  * This computer software and information is distributed with "restricted
  53.  * rights."  Use, duplication or disclosure is subject to restrictions as
  54.  * set forth in NASA FAR SUP 18-52.227-79 (April 1985) "Commercial
  55.  * Computer Software-Restricted Rights (April 1985)."  If the Clause at
  56.  * 18-52.227-74 "Rights in Data General" is specified in the contract,
  57.  * then the "Alternate III" clause applies.
  58.  *
  59.  **************************************************************************/
  60. #include <stdcomp.h>
  61.  
  62. #include <algorithm>
  63. #include <iterator>
  64. #include <memory>
  65. #include <stdexcept>
  66.  
  67. #ifndef list
  68. #define list list
  69. #endif
  70. #ifndef _RWSTD_NO_NAMESPACE
  71. namespace std {
  72. #endif
  73.  
  74. //
  75. // Note that _RWSTD_COMPLEX_DEFAULT(x)
  76. // will expand to: ' = x', or nothing,
  77. // depending on your compiler's capabilities and/or
  78. // flag settings (see stdcomp.h).
  79. //
  80.   template <class T, class Allocator _RWSTD_COMPLEX_DEFAULT(allocator<T>) >
  81.   class list
  82.   {
  83.   protected:
  84.     struct __list_node;
  85.     struct __list_node_buffer;
  86.     friend struct __list_node;
  87.     friend struct __list_node_buffer;
  88.  
  89. #ifdef _RWSTD_ALLOCATOR
  90.     typedef _TYPENAME Allocator::template rebind<__list_node>::other  __list_node_alloc_type;
  91.     typedef _TYPENAME Allocator::template rebind<T>::other __value_alloc_type;
  92.     typedef _TYPENAME Allocator::template rebind<__list_node_buffer>::other  __buffer_alloc_type;
  93. #else
  94.     typedef allocator_interface<Allocator,__list_node>  __list_node_alloc_type;
  95.     typedef allocator_interface<Allocator,T>          __value_alloc_type;
  96.     typedef allocator_interface<Allocator,__list_node_buffer>   __buffer_alloc_type;
  97. #endif // _RWSTD_ALLOCATOR
  98.  
  99.   public:
  100.     //
  101.     // types
  102.     //
  103.     typedef _TYPENAME __value_alloc_type::reference        reference;
  104.     typedef _TYPENAME __value_alloc_type::const_reference  const_reference;
  105.     typedef _TYPENAME __value_alloc_type::size_type        size_type;
  106.     typedef _TYPENAME __value_alloc_type::difference_type  difference_type;
  107.     typedef T                                    value_type;
  108.     typedef Allocator                            allocator_type;
  109.     typedef _TYPENAME __value_alloc_type::pointer        pointer;
  110.     typedef _TYPENAME __value_alloc_type::const_pointer  const_pointer;
  111.  
  112.   protected:
  113.     typedef _TYPENAME __list_node_alloc_type::pointer    __link_type;
  114.     typedef _TYPENAME __buffer_alloc_type::pointer       __buffer_pointer;
  115.  
  116.     struct __list_node
  117.     {
  118.       ~__list_node() { ; }
  119.       __link_type next;
  120.       __link_type prev;
  121.       T           data;
  122.     };
  123.  
  124.     struct __list_node_buffer
  125.     {
  126.       ~__list_node_buffer() { ; }
  127.       __buffer_pointer next_buffer;
  128.       size_type        size;
  129.       __link_type      buffer;
  130.     };
  131.  
  132.     size_type          __buffer_size;    
  133.     __RWSTD::__rw_basis<__buffer_pointer,allocator_type>   __buffer_list;
  134.     __link_type        __free_list;
  135.     __link_type        __next_avail;
  136.     __link_type        __last;
  137.     __link_type        __node;
  138.     size_type          __length;
  139.     
  140.     void __add_new_buffer (size_type n)
  141.     {
  142.       __buffer_pointer tmp = 
  143.         __buffer_alloc_type(__buffer_list).allocate(
  144.           _RWSTD_STATIC_CAST(size_type,1),__buffer_list.data());
  145. #ifndef _RWSTD_NO_EXCEPTIONS
  146.       try {
  147.         tmp->buffer = __list_node_alloc_type(__buffer_list).allocate(n,__last);
  148.       } catch(...) {
  149.         __buffer_alloc_type(__buffer_list).deallocate(tmp,1);
  150.         throw;
  151.       }      
  152. #else
  153.       tmp->buffer = __list_node_alloc_type(__buffer_list).allocate(n,__last);
  154. #endif // _RWSTD_NO_EXCEPTIONS
  155.       tmp->next_buffer = __buffer_list;
  156.       tmp->size = n;
  157.       __buffer_list = tmp;
  158.       __next_avail = __buffer_list.data()->buffer;                
  159.       __last = __next_avail + n;
  160.     }
  161.     void __deallocate_buffers ();
  162.     __link_type __get_node (size_type n)
  163.     {
  164.       __link_type tmp = __free_list;
  165.       return __free_list ? (__free_list = (__link_type)(__free_list->next), tmp) 
  166.       : (__next_avail == __last ? (__add_new_buffer(n), __next_avail++) 
  167.          : __next_avail++);
  168.     }
  169.     void __put_node (__link_type p) { p->next = __free_list; __free_list = p; }
  170.  
  171.     void __init(size_type n = 0)  
  172.     {
  173.       __buffer_size = max((size_type)1,
  174.                         __RWSTD::__rw_allocation_size((value_type*)0,
  175.                                                       (size_type)0,
  176.                                                       (size_type)0));
  177.       __node = __get_node(n == 0 ? __buffer_size : n + 1); // RW_BUG fix for bts-41790
  178.       (*__node).next = __node;
  179.       (*__node).prev = __node; 
  180.     }
  181.     void __init(size_type n, value_type value)  
  182.     {
  183.       __init(n);
  184. #ifndef _RWSTD_NO_EXCEPTIONS
  185.       try {
  186.         insert(begin(), n, value);
  187.       } catch(...) {
  188.         __deallocate_buffers();
  189.         throw;
  190.       }
  191. #else
  192.       insert(begin(), n, value);
  193. #endif
  194.     }
  195.  
  196.     typedef _RW_STD::iterator<bidirectional_iterator_tag, value_type,
  197.                     difference_type, pointer,reference> __it;
  198.     typedef _RW_STD::iterator<bidirectional_iterator_tag, value_type, 
  199.                     difference_type, const_pointer, const_reference> __cit;
  200.  
  201.   public:
  202.     
  203.     class iterator;
  204.     class const_iterator;
  205.     friend class iterator;
  206.     friend class const_iterator;
  207.  
  208.     class iterator : public __it
  209.     {
  210.       friend class list<T,Allocator>;
  211.       friend class const_iterator;
  212.  
  213.     protected:
  214.       
  215.       __link_type node;
  216.       iterator (__link_type x) : node(x) {}
  217.     
  218.     public:
  219.  
  220.       iterator () {}
  221.       bool operator== (const iterator& x) const { return node == x.node; }
  222.       bool operator!= (const iterator& x) const { return !(*this == x); }
  223.       reference operator* () const { return (*node).data; } 
  224. #ifndef _RWSTD_NO_NONCLASS_ARROW_RETURN
  225.       pointer operator-> () const { return &(node->data); }
  226. #endif
  227.       iterator& operator++ ()
  228.       { 
  229.         node = (__link_type)((*node).next); return *this;
  230.       }
  231.       iterator operator++ (int)
  232.       {
  233.         iterator tmp = *this; ++*this; return tmp;
  234.       }
  235.       iterator& operator-- ()
  236.       {
  237.         node = (__link_type)((*node).prev); return *this;
  238.       }
  239.       iterator operator-- (int)
  240.       {
  241.         iterator tmp = *this; --*this; return tmp;
  242.       }
  243.     };  // End of definition of iterator class.
  244.  
  245.     class const_iterator : public __cit
  246.     {
  247.       friend class list<T,Allocator>;
  248.  
  249.     protected:
  250.       
  251.       __link_type node;
  252.       const_iterator (__link_type x) : node(x) {}
  253.     
  254.     public:
  255.  
  256.       const_iterator () {}
  257.       const_iterator (const iterator& x) : node(x.node) {}
  258.       bool operator== (const const_iterator& x) const {return node==x.node;}
  259.       bool operator!= (const const_iterator x) const { return !(*this == x); } 
  260.       const_reference operator* () const { return (*node).data; }
  261. #ifndef _RWSTD_NO_NONCLASS_ARROW_RETURN
  262.       const_pointer operator-> () const { return &(node->data); }
  263. #endif
  264.       const_iterator& operator++ ()
  265.       { 
  266.         node = (__link_type)((*node).next); return *this;
  267.       }
  268.       const_iterator operator++ (int)
  269.       {
  270.         const_iterator tmp = *this; ++*this; return tmp;
  271.       }
  272.       const_iterator& operator-- ()
  273.       {
  274.         node = (__link_type)((*node).prev); return *this;
  275.       }
  276.       const_iterator operator-- (int)
  277.       {
  278.         const_iterator tmp = *this;
  279.         --*this;
  280.         return tmp;
  281.       }
  282.     };  // End of definition of const_iterator class.
  283.  
  284. #ifndef _RWSTD_NO_CLASS_PARTIAL_SPEC 
  285.     typedef _RW_STD::reverse_iterator<const_iterator> const_reverse_iterator;
  286.     typedef _RW_STD::reverse_iterator<iterator>  reverse_iterator;
  287. #else
  288.     typedef __reverse_bi_iterator<const_iterator, 
  289.       bidirectional_iterator_tag, value_type, 
  290.       const_reference, const_pointer, difference_type>
  291.       const_reverse_iterator;
  292.     typedef __reverse_bi_iterator<iterator, 
  293.       bidirectional_iterator_tag, value_type,
  294.       reference, pointer, difference_type>
  295.       reverse_iterator;
  296. #endif
  297.  
  298.     //
  299.     // construct/copy/destroy
  300.     //
  301.     list (const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator())) 
  302.       : __length(0), __buffer_list(0,alloc),
  303.         __free_list(0), __next_avail(0), __last(0), __node(0)
  304.     {
  305.       __init(1);
  306.     }
  307.     
  308. #ifdef _RWSTD_NO_DEFAULT_TEMPLATE_ARGS  
  309.     list (void) 
  310.       : __length(0), __buffer_list(0,Allocator()),
  311.         __free_list(0), __next_avail(0), __last(0), __node(0)
  312.     {
  313.       __init(1);
  314.     }
  315.  
  316.     list (size_type n, const T& value)
  317.       : __length(0), __buffer_list(0,Allocator()),
  318.         __free_list(0), __next_avail(0), __last(0), __node(0)
  319.     {
  320.       __init(n,value)
  321.     }
  322. #endif // _RWSTD_NO_DEFAULT_TEMPLATE_ARGS
  323.     _EXPLICIT list (size_type n) 
  324.       : __length(0), __buffer_list(0,Allocator()),
  325.         __free_list(0), __next_avail(0), __last(0), __node(0)
  326.     {
  327.       T value = T();
  328.       __init(n,value);
  329.     }
  330.  
  331. #ifndef _RWSTD_NO_MEMBER_TEMPLATES
  332.     template<class InputIterator>
  333.     list (InputIterator first, InputIterator locallast,
  334.           const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
  335.       : __length(0), __buffer_list(0,alloc),
  336.         __free_list(0), __next_avail(0), __last(0), __node(0)
  337.     {
  338.       __init();
  339. #ifndef _RWSTD_NO_EXCEPTIONS
  340.       try {
  341.         insert(begin(), first, locallast);
  342.       } catch(...) {
  343.         __deallocate_buffers();
  344.         throw;
  345.       }
  346. #else
  347.       insert(begin(), first, locallast);
  348. #endif
  349.     }
  350.     list (int n, const T& value,
  351.           const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
  352.       :  __length(0), __buffer_list(0,alloc),
  353.         __free_list(0), __next_avail(0), __last(0), __node(0)
  354.     { __init(n, value); }
  355.     list (unsigned int n, const T& value,
  356.           const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
  357.       :  __length(0), __buffer_list(0,alloc),
  358.         __free_list(0), __next_avail(0), __last(0), __node(0)
  359.     { __init(n, value); }
  360.     list (long n, const T& value,
  361.           const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
  362.       :  __length(0), __buffer_list(0,alloc),
  363.         __free_list(0), __next_avail(0), __last(0), __node(0)
  364.     { __init(n, value); }
  365.     list (unsigned long n, const T& value,
  366.           const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
  367.       :  __length(0), __buffer_list(0,alloc),
  368.         __free_list(0), __next_avail(0), __last(0), __node(0)
  369.     { __init(n, value); }
  370.     list (short n, const T& value,
  371.           const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
  372.       :  __length(0), __buffer_list(0,alloc),
  373.         __free_list(0), __next_avail(0), __last(0), __node(0)
  374.     { __init(n, value); }
  375.     list (unsigned short n, const T& value,
  376.           const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
  377.       :  __length(0), __buffer_list(0,alloc),
  378.         __free_list(0), __next_avail(0), __last(0), __node(0)
  379.     { __init(n, value); }
  380.     list (char n, const T& value,
  381.           const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
  382.       :  __length(0), __buffer_list(0,alloc),
  383.         __free_list(0), __next_avail(0), __last(0), __node(0)
  384.     { __init(n, value); }
  385.     list (unsigned char n, const T& value,
  386.           const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
  387.       :  __length(0), __buffer_list(0,alloc),
  388.         __free_list(0), __next_avail(0), __last(0), __node(0)
  389.     { __init(n, value); }
  390. #ifndef _RWSTD_NO_BOOL
  391.     list (bool n, const T& value,
  392.           const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
  393.       :  __length(0), __buffer_list(0,alloc),
  394.         __free_list(0), __next_avail(0), __last(0), __node(0)
  395.     { __init(n, value); }
  396. #endif
  397. #ifndef _RWSTD_NO_OVERLOAD_WCHAR
  398.     list (wchar_t n, const T& value,
  399.           const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
  400.       :  __length(0), __buffer_list(0,alloc),
  401.         __free_list(0), __next_avail(0), __last(0), __node(0)
  402.     { __init(n, value); }
  403. #endif // _RWSTD_NO_OVERLOAD_WCHAR
  404. #else
  405.     //
  406.     // Build a list of size n with each element set to a copy of value.
  407.     //
  408.     list (size_type n, const T& value,
  409.           const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator())) 
  410.       : __length(0), __buffer_list(0,alloc),
  411.        __free_list(0), __next_avail(0), __last(0), __node(0)
  412.     {
  413.       __init(n, value);
  414.     }
  415.  
  416.     list (const_iterator first, const_iterator locallast,
  417.           const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
  418.       : __length(0), __buffer_list(0,alloc),
  419.         __free_list(0), __next_avail(0), __last(0), __node(0)
  420.     {
  421.       __init();
  422. #ifndef _RWSTD_NO_EXCEPTIONS
  423.       try {
  424.         insert(begin(), first, locallast);
  425.       } catch(...) {
  426.         __deallocate_buffers();
  427.         throw;
  428.       }
  429. #else
  430.       insert(begin(), first, locallast);
  431. #endif
  432.     }
  433.     list (const T* first, const T* locallast,
  434.           const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
  435.       : __length(0), __buffer_list(0,alloc),
  436.        __free_list(0), __next_avail(0), __last(0), __node(0)
  437.     {
  438.       __init();
  439. #ifndef _RWSTD_NO_EXCEPTIONS
  440.       try {
  441.         insert(begin(), first, locallast);
  442.       } catch(...) {
  443.         __deallocate_buffers();
  444.         throw;
  445.       }
  446. #else
  447.       insert(begin(), first, locallast);
  448. #endif
  449.     }
  450.  
  451. #ifdef _RWSTD_NO_DEFAULT_TEMPLATE_ARGS
  452.     list (const_iterator first, const_iterator locallast)
  453.       : __length(0), __buffer_list(0,Allocator()),
  454.         __free_list(0), __next_avail(0), __last(0), __node(0)
  455.     {
  456.       __init();
  457. #ifndef _RWSTD_NO_EXCEPTIONS
  458.       try {
  459.         insert(begin(), first, locallast);
  460.       } catch(...) {
  461.         __deallocate_buffers();
  462.         throw;
  463.       }
  464. #else
  465.       insert(begin(), first, locallast);
  466. #endif
  467.     }
  468.  
  469.     list (const T* first, const T* locallast)
  470.       : __length(0), __buffer_list(0,Allocator()),
  471.         __free_list(0), __next_avail(0), __last(0), __node(0)
  472.     {
  473.       __init();
  474. #ifndef _RWSTD_NO_EXCEPTIONS
  475.       try {
  476.         insert(begin(), first, locallast);
  477.       } catch(...) {
  478.         __deallocate_buffers();
  479.         throw;
  480.       }
  481. #else
  482.       insert(begin(), first, locallast);
  483. #endif
  484.     }
  485. #endif // _RWSTD_NO_DEFAULT_TEMPLATE_ARGS
  486. #endif // _RWSTD_NO_MEMBER_TEMPLATES
  487.  
  488.     list (const list<T,Allocator>& x) : __length(0), __buffer_list(0,x.get_allocator()),
  489.       __free_list(0), __next_avail(0), __last(0), __node(0)
  490.     {
  491.       __init();
  492. #ifndef _RWSTD_NO_EXCEPTIONS
  493.       try {
  494.         insert(begin(), x.begin(), x.end());
  495.       } catch(...) {
  496.         __deallocate_buffers();
  497.         throw;
  498.       }
  499. #else
  500.       insert(begin(), first, locallast);
  501. #endif
  502.     }
  503.  
  504.     ~list ()
  505.     {
  506.       if (__node)
  507.       {
  508.         erase(begin(), end());
  509.         __put_node(__node);
  510.         __deallocate_buffers();
  511.       }
  512.     }
  513.     list<T,Allocator>& operator= (const list<T,Allocator>& x);   
  514.  
  515. #ifndef _RWSTD_NO_MEMBER_TEMPLATES
  516.     template<class InputIterator>
  517.     void assign (InputIterator first, InputIterator __last)
  518.     { erase(begin(), end()); insert(begin(), first, __last);  }
  519.     //
  520.     // Assign n copies of t to this list.
  521.     //
  522.     void assign (int n, T t)
  523.     { erase(begin(), end()); insert(begin(), n, t); }
  524.     void assign (unsigned int n, T t)
  525.     { erase(begin(), end()); insert(begin(), n, t); }
  526.     void assign (long n, T t)
  527.     { erase(begin(), end()); insert(begin(), n, t); }
  528.     void assign (unsigned long n, T t)
  529.     { erase(begin(), end()); insert(begin(), n, t); }
  530.     void assign (short n, T t)
  531.     { erase(begin(), end()); insert(begin(), n, t); }
  532.     void assign (unsigned short n, T t)
  533.     { erase(begin(), end()); insert(begin(), n, t); }
  534.     void assign (char n, T t)
  535.     { erase(begin(), end()); insert(begin(), n, t); }
  536.     void assign (unsigned char n, T t)
  537.     { erase(begin(), end()); insert(begin(), n, t); }
  538. #ifndef _RWSTD_NO_OVERLOAD_WCHAR
  539.     void assign (wchar_t n, T t)
  540.     { erase(begin(), end()); insert(begin(), n, t); }
  541. #endif
  542. #ifndef _RWSTD_NO_BOOL
  543.     void assign (bool n, T t)
  544.     { erase(begin(), end()); insert(begin(), n, t); }
  545. #endif
  546. #else
  547.     void assign (const_iterator first, const_iterator last)
  548.     { erase(begin(), end()); insert(begin(), first, last); }
  549.     void assign (const T* first, const T* last)
  550.     { erase(begin(), end()); insert(begin(), first, last); }
  551.     //
  552.     // Assign n copies of t to this list.
  553.     //
  554.     void assign (size_type n, const T& t)
  555.     { erase(begin(), end()); insert(begin(), n, t); }
  556. #endif // _RWSTD_NO_MEMBER_TEMPLATES
  557.  
  558.     allocator_type get_allocator() const
  559.     {
  560.       return (allocator_type)__buffer_list;
  561.     }
  562.  
  563.     //
  564.     // Iterators.
  565.     //
  566.     iterator       begin ()       { return _RWSTD_STATIC_CAST(__link_type,((*__node).next)); }
  567.     const_iterator begin () const { return _RWSTD_STATIC_CAST(__link_type,((*__node).next)); }
  568.  
  569.     iterator       end ()         { return __node;                      }
  570.     const_iterator end ()   const { return __node;                      }
  571.     reverse_iterator rbegin ()
  572.     { 
  573.       reverse_iterator tmp(end()); return tmp;
  574.     }
  575.     const_reverse_iterator rbegin () const
  576.     { 
  577.       const_reverse_iterator tmp(end()); return tmp;
  578.     }
  579.     reverse_iterator rend ()
  580.     { 
  581.       reverse_iterator tmp(begin()); return tmp;
  582.     }
  583.     const_reverse_iterator rend () const
  584.     {
  585.       const_reverse_iterator tmp(begin()); return tmp;
  586.     }
  587.  
  588.     //
  589.     // Capacity.
  590.     //
  591.     bool empty ()         const { return __length == 0;                }
  592.     size_type size ()     const { return __length;                     }
  593.     size_type max_size () const 
  594.     { return __list_node_alloc_type(__buffer_list).max_size(); }
  595.     void resize (size_type new_size);
  596.     void resize (size_type new_size, T value);
  597.  
  598.     //
  599.     // Element access.
  600.     //
  601.     reference       front ()       { return *begin();   }
  602.     const_reference front () const { return *begin();   }
  603.     reference       back  ()       { return *(--end()); }
  604.     const_reference back  () const { return *(--end()); }
  605.  
  606.     //
  607.     // Modifiers.
  608.     //
  609.     //
  610.     void push_front (const T& x) { insert(begin(), x); }
  611.     void push_back  (const T& x) { insert(end(), x);   }
  612.     void pop_front  ()           { erase(begin());     }
  613.     void pop_back   ()           { iterator tmp = end(); erase(--tmp); }
  614.  
  615.     //
  616.     // Insert x at position.
  617.     //
  618.     iterator insert (iterator position, const T& x)
  619.     {
  620.       __value_alloc_type va(__buffer_list);
  621.       __link_type tmp = __get_node(__buffer_size);
  622. #ifndef _RWSTD_NO_EXCEPTIONS
  623.       try {
  624.        va.construct(va.address((*tmp).data),x);
  625.       } catch(...) {
  626.         __put_node(tmp);
  627.         throw;
  628.       }      
  629. #else
  630.       va.construct(va.address((*tmp).data),x);
  631. #endif // _RWSTD_NO_EXCEPTIONS
  632.       (*tmp).next = position.node;
  633.       (*tmp).prev = (*position.node).prev;
  634.       (*(__link_type((*position.node).prev))).next = tmp;
  635.       (*position.node).prev = tmp;
  636.       ++__length;
  637.       return tmp;
  638.     }
  639.  
  640. #ifndef _RWSTD_NO_MEMBER_TEMPLATES
  641.     template<class InputIterator>
  642.     void insert (iterator position, InputIterator first,
  643.                  InputIterator last);
  644.     void insert (iterator position, int n, const T& value)
  645.     { __insert_aux(position,(size_type)n,value); }
  646.     void insert (iterator position, int n, int value) // RW_BUG: fix for bts-42473
  647.     { __insert_aux(position,(size_type)n,value); }
  648.  
  649.     void insert (iterator position, unsigned int n, const T& value)
  650.     { __insert_aux(position,(size_type)n,value); }
  651.     void insert (iterator position, unsigned int n, unsigned int value) // RW_BUG: fix for bts-42473
  652.     { __insert_aux(position,(size_type)n,value); }
  653.  
  654.     void insert (iterator position, long n, const T& value) // __BORLANDC__ fix to bts-40275 // RW_BUG: forgot const &
  655.     { __insert_aux(position,(size_type)n,value); }
  656.     void insert (iterator position, long n, long value) // RW_BUG: fix for bts-42473
  657.     { __insert_aux(position,(size_type)n,value); }
  658.  
  659.     void insert (iterator position, unsigned long n, const T& value)
  660.     { __insert_aux(position,(size_type)n,value); }
  661.     void insert (iterator position, unsigned long n, unsigned long value) // RW_BUG: fix for bts-42473
  662.     { __insert_aux(position,(size_type)n,value); }
  663.  
  664.     void insert (iterator position, short n, const T& value)
  665.     { __insert_aux(position,(size_type)n,value); }
  666.     void insert (iterator position, short n, short value) // RW_BUG: fix for bts-42473
  667.     { __insert_aux(position,(size_type)n,value); }
  668.  
  669.     void insert (iterator position, unsigned short n, const T& value)
  670.     { __insert_aux(position,(size_type)n,value); }
  671.     void insert (iterator position, unsigned short n, unsigned short value) // RW_BUG: fix for bts-42473
  672.     { __insert_aux(position,(size_type)n,value); }
  673.  
  674.     void insert (iterator position, char n, const T& value)
  675.     { __insert_aux(position,(size_type)n,value); }
  676.     void insert (iterator position, char n, char value) // RW_BUG: fix for bts-42473
  677.     { __insert_aux(position,(size_type)n,value); }
  678.  
  679.     void insert (iterator position, unsigned char n, const T& value)
  680.     { __insert_aux(position,(size_type)n,value); }
  681.     void insert (iterator position, unsigned char n, unsigned char value) // RW_BUG: fix for bts-42473
  682.     { __insert_aux(position,(size_type)n,value); }
  683.  
  684. #ifndef _RWSTD_NO_BOOL
  685.     void insert (iterator position, bool n, const T& value)
  686.     { __insert_aux(position,(size_type)n,value); }
  687.     void insert (iterator position, bool n, bool value) // RW_BUG: fix for bts-42473
  688.     { __insert_aux(position,(size_type)n,value); }
  689.  
  690. #endif
  691. #ifndef _RWSTD_NO_OVERLOAD_WCHAR
  692.     void insert (iterator position, wchar_t n, const T& value)
  693.     { __insert_aux(position,(size_type)n,value); }
  694.     void insert (iterator position, wchar_t n, wchar_t value) // RW_BUG: fix for bts-42473
  695.     { __insert_aux(position,(size_type)n,value); }
  696.  
  697. #endif
  698. #else
  699.     void insert (iterator position, size_type n, const T& x)
  700.     { __insert_aux(position,n,x); }
  701.     void insert (iterator position, const T* first, const T* last);
  702.     void insert (iterator position, const_iterator first, const_iterator last);
  703. #endif // _RWSTD_NO_MEMBER_TEMPLATES
  704.  
  705.     iterator erase (iterator position)
  706.     {
  707.       if (position == end())
  708.         return end();
  709.       iterator tmp = (iterator)(__link_type((*position.node).next));
  710.       (*(__link_type((*position.node).prev))).next = (*position.node).next;
  711.       (*(__link_type((*position.node).next))).prev = (*position.node).prev;
  712.       --__length;
  713.       __value_alloc_type va(__buffer_list);
  714.       va.destroy(va.address((*position.node).data));
  715.       __put_node(position.node);
  716.       return tmp;
  717.     }
  718.     iterator erase      (iterator first, iterator last);
  719.     void swap (list<T,Allocator>& x)
  720.     {
  721.       if((allocator_type)__buffer_list==(allocator_type)x.__buffer_list)
  722.       {
  723.  
  724. #ifndef _RWSTD_NO_NAMESPACE
  725.         std::swap(__node, x.__node); 
  726.         std::swap(__length, x.__length);
  727.         std::swap(__buffer_list,x.__buffer_list);
  728.         std::swap(__free_list,x.__free_list);
  729.         std::swap(__next_avail,x.__next_avail);
  730.         std::swap(__last,x.__last);
  731. #else
  732.         ::swap(__node, x.__node); 
  733.         ::swap(__length, x.__length);
  734.         ::swap(__buffer_list,x.__buffer_list);
  735.         ::swap(__free_list,x.__free_list);
  736.         ::swap(__next_avail,x.__next_avail);
  737.         ::swap(__last,x.__last);
  738. #endif // _RWSTD_NO_NAMESPACE
  739.       }
  740.       else
  741.       {
  742.         list<T,Allocator> _x = *this;
  743.         *this=x;
  744.         x=_x;
  745.       }
  746.     }
  747.  
  748.     void clear()
  749.     {
  750.       erase(begin(),end());
  751.     }
  752.  
  753.   protected:
  754.     
  755.     void __transfer (iterator position, iterator first, 
  756.                    iterator last, list<T,Allocator>& x)
  757.     {
  758.       if (this == &x)
  759.       {
  760.         (*(__link_type((*last.node).prev))).next = position.node;
  761.         (*(__link_type((*first.node).prev))).next = last.node;
  762.         (*(__link_type((*position.node).prev))).next = first.node;  
  763.         __link_type tmp = __link_type((*position.node).prev);
  764.         (*position.node).prev = (*last.node).prev;
  765.         (*last.node).prev = (*first.node).prev; 
  766.         (*first.node).prev = tmp;
  767.       }
  768.       else
  769.       {
  770.         insert(position,first,last);
  771.         x.erase(first,last);
  772.       }
  773.     }
  774.  
  775.     // used by the sort() member function
  776.     void __set_allocator(allocator_type a)
  777.     {  
  778.       __buffer_list = a; 
  779.     }
  780.     void __insert_aux (iterator position, size_type n, const T& x);
  781.  
  782.   public:
  783.  
  784.     //
  785.     // list operations.
  786.     //
  787.     void splice (iterator position, list<T,Allocator>& x)
  788.     {
  789.       if (!x.empty())
  790.         __transfer(position, x.begin(), x.end(), x);
  791.     }
  792.     void splice (iterator position, list<T,Allocator>& x, iterator i)
  793.     { 
  794.       iterator k = i;
  795.       if (k != position && ++k != position)
  796.       {
  797.         iterator j = i;
  798.         __transfer(position, i, ++j, x);
  799.       }
  800.     }
  801.     void splice (iterator position, list<T,Allocator>& x, iterator first, iterator last)
  802.     {
  803.       if (first != last)
  804.       {
  805.         difference_type n;
  806.         __initialize(n, difference_type(0));
  807.         distance(first, last, n);
  808.         __transfer(position, first, last, x);
  809.       }
  810.     }
  811.     void remove  (const T& value);
  812.     void unique  ();
  813.     void merge   (list<T,Allocator>& x);
  814.     void reverse ();
  815.     void sort    ();
  816.  
  817. #ifndef _RWSTD_NO_MEMBER_TEMPLATES
  818.     template<class Predicate>       void remove_if (Predicate pred);
  819.     template<class BinaryPredicate> void unique    (BinaryPredicate pred);
  820.     template<class Compare>         void merge     (list<T,Allocator>& x, Compare comp);
  821.     template<class Compare>         void sort      (Compare comp);
  822. #endif // _RWSTD_NO_MEMBER_TEMPLATES
  823.  
  824. #ifndef _RWSTD_STRICT_ANSI
  825.     // Non-standard function for setting buffer allocation size
  826.     size_type allocation_size() { return __buffer_size; }
  827.     size_type allocation_size(size_type new_size) 
  828.     { 
  829.       size_type tmp = __buffer_size; 
  830.       __buffer_size = max((size_type)1,new_size);
  831.       return tmp;
  832.     }
  833. #endif // _RWSTD_STRICT_ANSI
  834.   };
  835.  
  836.   template <class T, class Allocator>
  837.   inline bool operator== (const list<T,Allocator>& x, const list<T,Allocator>& y)
  838.   {
  839.     return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
  840.   }
  841.  
  842.   template <class T, class Allocator>
  843.   inline bool operator< (const list<T,Allocator>& x, const list<T,Allocator>& y)
  844.   {
  845.     return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
  846.   }
  847.  
  848. #if !defined(_RWSTD_NO_NAMESPACE) || !defined(_RWSTD_NO_PART_SPEC_OVERLOAD)
  849.   template <class T, class Allocator>
  850.   inline bool operator!= (const list<T,Allocator>& x, const list<T,Allocator>& y)
  851.   {
  852.     return !(x == y);
  853.   }
  854.  
  855.   template <class T, class Allocator>
  856.   inline bool operator> (const list<T,Allocator>& x, const list<T,Allocator>& y)
  857.   {
  858.     return y < x;
  859.   }
  860.  
  861.   template <class T, class Allocator>
  862.   inline bool operator>= (const list<T,Allocator>& x, const list<T,Allocator>& y)
  863.   {
  864.     return !(x < y);
  865.   }
  866.  
  867.   template <class T, class Allocator>
  868.   inline bool operator<= (const list<T,Allocator>& x, const list<T,Allocator>& y)
  869.   {
  870.     return !(y <  x);
  871.   }
  872.  
  873.   template <class T, class Allocator>
  874.   inline void swap(list<T,Allocator>& a, list<T,Allocator>& b)
  875.   {
  876.     a.swap(b);
  877.   }
  878. #endif // !defined(_RWSTD_NO_NAMESPACE) || !defined(_RWSTD_NO_PART_SPEC_OVERLOAD)
  879.  
  880. #ifndef _RWSTD_NO_NAMESPACE
  881. }
  882. #endif
  883.  
  884. #ifdef _RWSTD_NO_TEMPLATE_REPOSITORY
  885. #include <list.cc>
  886. #endif
  887.  
  888. #undef list
  889. #endif /*__STD_LIST__*/
  890. #ifndef __USING_STD_NAMES__
  891.   using namespace std;
  892. #endif
  893. #pragma option pop
  894. #endif /* __LIST_H */
  895.