home *** CD-ROM | disk | FTP | other *** search
/ Programming Win32 Under the API / ProgrammingWin32UnderTheApiPatVillani.iso / gcc-2.95.2-msvcrt.exe / include / g++-3 / stl_slist.h < prev    next >
C/C++ Source or Header  |  1999-11-07  |  29KB  |  946 lines
  1. /*
  2.  * Copyright (c) 1997
  3.  * Silicon Graphics Computer Systems, Inc.
  4.  *
  5.  * Permission to use, copy, modify, distribute and sell this software
  6.  * and its documentation for any purpose is hereby granted without fee,
  7.  * provided that the above copyright notice appear in all copies and
  8.  * that both that copyright notice and this permission notice appear
  9.  * in supporting documentation.  Silicon Graphics makes no
  10.  * representations about the suitability of this software for any
  11.  * purpose.  It is provided "as is" without express or implied warranty.
  12.  *
  13.  */
  14.  
  15. /* NOTE: This is an internal header file, included by other STL headers.
  16.  *   You should not attempt to use it directly.
  17.  */
  18.  
  19. #ifndef __SGI_STL_INTERNAL_SLIST_H
  20. #define __SGI_STL_INTERNAL_SLIST_H
  21.  
  22.  
  23. __STL_BEGIN_NAMESPACE 
  24.  
  25. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  26. #pragma set woff 1174
  27. #pragma set woff 1375
  28. #endif
  29.  
  30. struct _Slist_node_base
  31. {
  32.   _Slist_node_base* _M_next;
  33. };
  34.  
  35. inline _Slist_node_base*
  36. __slist_make_link(_Slist_node_base* __prev_node,
  37.                   _Slist_node_base* __new_node)
  38. {
  39.   __new_node->_M_next = __prev_node->_M_next;
  40.   __prev_node->_M_next = __new_node;
  41.   return __new_node;
  42. }
  43.  
  44. inline _Slist_node_base* 
  45. __slist_previous(_Slist_node_base* __head,
  46.                  const _Slist_node_base* __node)
  47. {
  48.   while (__head && __head->_M_next != __node)
  49.     __head = __head->_M_next;
  50.   return __head;
  51. }
  52.  
  53. inline const _Slist_node_base* 
  54. __slist_previous(const _Slist_node_base* __head,
  55.                  const _Slist_node_base* __node)
  56. {
  57.   while (__head && __head->_M_next != __node)
  58.     __head = __head->_M_next;
  59.   return __head;
  60. }
  61.  
  62. inline void __slist_splice_after(_Slist_node_base* __pos,
  63.                                  _Slist_node_base* __before_first,
  64.                                  _Slist_node_base* __before_last)
  65. {
  66.   if (__pos != __before_first && __pos != __before_last) {
  67.     _Slist_node_base* __first = __before_first->_M_next;
  68.     _Slist_node_base* __after = __pos->_M_next;
  69.     __before_first->_M_next = __before_last->_M_next;
  70.     __pos->_M_next = __first;
  71.     __before_last->_M_next = __after;
  72.   }
  73. }
  74.  
  75. inline _Slist_node_base* __slist_reverse(_Slist_node_base* __node)
  76. {
  77.   _Slist_node_base* __result = __node;
  78.   __node = __node->_M_next;
  79.   __result->_M_next = 0;
  80.   while(__node) {
  81.     _Slist_node_base* __next = __node->_M_next;
  82.     __node->_M_next = __result;
  83.     __result = __node;
  84.     __node = __next;
  85.   }
  86.   return __result;
  87. }
  88.  
  89. inline size_t __slist_size(_Slist_node_base* __node)
  90. {
  91.   size_t __result = 0;
  92.   for ( ; __node != 0; __node = __node->_M_next)
  93.     ++__result;
  94.   return __result;
  95. }
  96.  
  97. template <class _Tp>
  98. struct _Slist_node : public _Slist_node_base
  99. {
  100.   _Tp _M_data;
  101. };
  102.  
  103. struct _Slist_iterator_base
  104. {
  105.   typedef size_t               size_type;
  106.   typedef ptrdiff_t            difference_type;
  107.   typedef forward_iterator_tag iterator_category;
  108.  
  109.   _Slist_node_base* _M_node;
  110.  
  111.   _Slist_iterator_base(_Slist_node_base* __x) : _M_node(__x) {}
  112.   void _M_incr() { _M_node = _M_node->_M_next; }
  113.  
  114.   bool operator==(const _Slist_iterator_base& __x) const {
  115.     return _M_node == __x._M_node;
  116.   }
  117.   bool operator!=(const _Slist_iterator_base& __x) const {
  118.     return _M_node != __x._M_node;
  119.   }
  120. };
  121.  
  122. template <class _Tp, class _Ref, class _Ptr>
  123. struct _Slist_iterator : public _Slist_iterator_base
  124. {
  125.   typedef _Slist_iterator<_Tp, _Tp&, _Tp*>             iterator;
  126.   typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
  127.   typedef _Slist_iterator<_Tp, _Ref, _Ptr>             _Self;
  128.  
  129.   typedef _Tp              value_type;
  130.   typedef _Ptr             pointer;
  131.   typedef _Ref             reference;
  132.   typedef _Slist_node<_Tp> _Node;
  133.  
  134.   _Slist_iterator(_Node* __x) : _Slist_iterator_base(__x) {}
  135.   _Slist_iterator() : _Slist_iterator_base(0) {}
  136.   _Slist_iterator(const iterator& __x) : _Slist_iterator_base(__x._M_node) {}
  137.  
  138.   reference operator*() const { return ((_Node*) _M_node)->_M_data; }
  139. #ifndef __SGI_STL_NO_ARROW_OPERATOR
  140.   pointer operator->() const { return &(operator*()); }
  141. #endif /* __SGI_STL_NO_ARROW_OPERATOR */
  142.  
  143.   _Self& operator++()
  144.   {
  145.     _M_incr();
  146.     return *this;
  147.   }
  148.   _Self operator++(int)
  149.   {
  150.     _Self __tmp = *this;
  151.     _M_incr();
  152.     return __tmp;
  153.   }
  154. };
  155.  
  156. #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
  157.  
  158. inline ptrdiff_t* distance_type(const _Slist_iterator_base&) {
  159.   return 0;
  160. }
  161.  
  162. inline forward_iterator_tag iterator_category(const _Slist_iterator_base&) {
  163.   return forward_iterator_tag();
  164. }
  165.  
  166. template <class _Tp, class _Ref, class _Ptr> 
  167. inline _Tp* value_type(const _Slist_iterator<_Tp, _Ref, _Ptr>&) {
  168.   return 0;
  169. }
  170.  
  171. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  172.  
  173. // Base class that encapsulates details of allocators.  Three cases:
  174. // an ordinary standard-conforming allocator, a standard-conforming
  175. // allocator with no non-static data, and an SGI-style allocator.
  176. // This complexity is necessary only because we're worrying about backward
  177. // compatibility and because we want to avoid wasting storage on an 
  178. // allocator instance if it isn't necessary.
  179.  
  180. #ifdef __STL_USE_STD_ALLOCATORS
  181.  
  182. // Base for general standard-conforming allocators.
  183. template <class _Tp, class _Allocator, bool _IsStatic>
  184. class _Slist_alloc_base {
  185. public:
  186.   typedef typename _Alloc_traits<_Tp,_Allocator>::allocator_type
  187.           allocator_type;
  188.   allocator_type get_allocator() const { return _M_node_allocator; }
  189.  
  190.   _Slist_alloc_base(const allocator_type& __a) : _M_node_allocator(__a) {}
  191.  
  192. protected:
  193.   _Slist_node<_Tp>* _M_get_node() 
  194.     { return _M_node_allocator.allocate(1); }
  195.   void _M_put_node(_Slist_node<_Tp>* __p) 
  196.     { _M_node_allocator.deallocate(__p, 1); }
  197.  
  198. protected:
  199.   typename _Alloc_traits<_Slist_node<_Tp>,_Allocator>::allocator_type
  200.            _M_node_allocator;
  201.   _Slist_node_base _M_head;
  202. };
  203.  
  204. // Specialization for instanceless allocators.
  205. template <class _Tp, class _Allocator>
  206. class _Slist_alloc_base<_Tp,_Allocator, true> {
  207. public:
  208.   typedef typename _Alloc_traits<_Tp,_Allocator>::allocator_type
  209.           allocator_type;
  210.   allocator_type get_allocator() const { return allocator_type(); }
  211.  
  212.   _Slist_alloc_base(const allocator_type&) {}
  213.  
  214. protected:
  215.   typedef typename _Alloc_traits<_Slist_node<_Tp>, _Allocator>::_Alloc_type
  216.           _Alloc_type;
  217.   _Slist_node<_Tp>* _M_get_node() { return _Alloc_type::allocate(1); }
  218.   void _M_put_node(_Slist_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); }
  219.  
  220. protected:
  221.   _Slist_node_base _M_head;
  222. };
  223.  
  224.  
  225. template <class _Tp, class _Alloc>
  226. struct _Slist_base
  227.   : public _Slist_alloc_base<_Tp, _Alloc,
  228.                              _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
  229. {
  230.   typedef _Slist_alloc_base<_Tp, _Alloc,
  231.                             _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
  232.           _Base;
  233.   typedef typename _Base::allocator_type allocator_type;
  234.  
  235.   _Slist_base(const allocator_type& __a) : _Base(__a) { _M_head._M_next = 0; }
  236.   ~_Slist_base() { _M_erase_after(&_M_head, 0); }
  237.  
  238. protected:
  239.  
  240.   _Slist_node_base* _M_erase_after(_Slist_node_base* __pos)
  241.   {
  242.     _Slist_node<_Tp>* __next = (_Slist_node<_Tp>*) (__pos->_M_next);
  243.     _Slist_node_base* __next_next = __next->_M_next;
  244.     __pos->_M_next = __next_next;
  245.     destroy(&__next->_M_data);
  246.     _M_put_node(__next);
  247.     return __next_next;
  248.   }
  249.   _Slist_node_base* _M_erase_after(_Slist_node_base*, _Slist_node_base*);
  250. };
  251.  
  252. #else /* __STL_USE_STD_ALLOCATORS */
  253.  
  254. template <class _Tp, class _Alloc> 
  255. struct _Slist_base {
  256.   typedef _Alloc allocator_type;
  257.   allocator_type get_allocator() const { return allocator_type(); }
  258.  
  259.   _Slist_base(const allocator_type&) { _M_head._M_next = 0; }
  260.   ~_Slist_base() { _M_erase_after(&_M_head, 0); }
  261.  
  262. protected:
  263.   typedef simple_alloc<_Slist_node<_Tp>, _Alloc> _Alloc_type;
  264.   _Slist_node<_Tp>* _M_get_node() { return _Alloc_type::allocate(1); }
  265.   void _M_put_node(_Slist_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); }
  266.  
  267.   _Slist_node_base* _M_erase_after(_Slist_node_base* __pos)
  268.   {
  269.     _Slist_node<_Tp>* __next = (_Slist_node<_Tp>*) (__pos->_M_next);
  270.     _Slist_node_base* __next_next = __next->_M_next;
  271.     __pos->_M_next = __next_next;
  272.     destroy(&__next->_M_data);
  273.     _M_put_node(__next);
  274.     return __next_next;
  275.   }
  276.   _Slist_node_base* _M_erase_after(_Slist_node_base*, _Slist_node_base*);
  277.  
  278. protected:
  279.   _Slist_node_base _M_head;
  280. };  
  281.  
  282. #endif /* __STL_USE_STD_ALLOCATORS */
  283.  
  284. template <class _Tp, class _Alloc> 
  285. _Slist_node_base*
  286. _Slist_base<_Tp,_Alloc>::_M_erase_after(_Slist_node_base* __before_first,
  287.                                         _Slist_node_base* __last_node) {
  288.   _Slist_node<_Tp>* __cur = (_Slist_node<_Tp>*) (__before_first->_M_next);
  289.   while (__cur != __last_node) {
  290.     _Slist_node<_Tp>* __tmp = __cur;
  291.     __cur = (_Slist_node<_Tp>*) __cur->_M_next;
  292.     destroy(&__tmp->_M_data);
  293.     _M_put_node(__tmp);
  294.   }
  295.   __before_first->_M_next = __last_node;
  296.   return __last_node;
  297. }
  298.  
  299. template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
  300. class slist : private _Slist_base<_Tp,_Alloc>
  301. {
  302. private:
  303.   typedef _Slist_base<_Tp,_Alloc> _Base;
  304. public:
  305.   typedef _Tp                value_type;
  306.   typedef value_type*       pointer;
  307.   typedef const value_type* const_pointer;
  308.   typedef value_type&       reference;
  309.   typedef const value_type& const_reference;
  310.   typedef size_t            size_type;
  311.   typedef ptrdiff_t         difference_type;
  312.  
  313.   typedef _Slist_iterator<_Tp, _Tp&, _Tp*>             iterator;
  314.   typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
  315.  
  316.   typedef typename _Base::allocator_type allocator_type;
  317.   allocator_type get_allocator() const { return _Base::get_allocator(); }
  318.  
  319. private:
  320.   typedef _Slist_node<_Tp>      _Node;
  321.   typedef _Slist_node_base      _Node_base;
  322.   typedef _Slist_iterator_base  _Iterator_base;
  323.  
  324.   _Node* _M_create_node(const value_type& __x) {
  325.     _Node* __node = _M_get_node();
  326.     __STL_TRY {
  327.       construct(&__node->_M_data, __x);
  328.       __node->_M_next = 0;
  329.     }
  330.     __STL_UNWIND(_M_put_node(__node));
  331.     return __node;
  332.   }
  333.   
  334.   _Node* _M_create_node() {
  335.     _Node* __node = _M_get_node();
  336.     __STL_TRY {
  337.       construct(&__node->_M_data);
  338.       __node->_M_next = 0;
  339.     }
  340.     __STL_UNWIND(_M_put_node(__node));
  341.     return __node;
  342.   }
  343.  
  344. private:
  345. #ifdef __STL_USE_NAMESPACES  
  346.   using _Base::_M_get_node;
  347.   using _Base::_M_put_node;
  348.   using _Base::_M_erase_after;
  349.   using _Base::_M_head;
  350. #endif /* __STL_USE_NAMESPACES */
  351.  
  352. public:
  353.   explicit slist(const allocator_type& __a = allocator_type()) : _Base(__a) {}
  354.  
  355.   slist(size_type __n, const value_type& __x,
  356.         const allocator_type& __a =  allocator_type()) : _Base(__a)
  357.     { _M_insert_after_fill(&_M_head, __n, __x); }
  358.  
  359.   explicit slist(size_type __n) : _Base(allocator_type())
  360.     { _M_insert_after_fill(&_M_head, __n, value_type()); }
  361.  
  362. #ifdef __STL_MEMBER_TEMPLATES
  363.   // We don't need any dispatching tricks here, because _M_insert_after_range
  364.   // already does them.
  365.   template <class _InputIterator>
  366.   slist(_InputIterator __first, _InputIterator __last,
  367.         const allocator_type& __a =  allocator_type()) : _Base(__a)
  368.     { _M_insert_after_range(&_M_head, __first, __last); }
  369.  
  370. #else /* __STL_MEMBER_TEMPLATES */
  371.   slist(const_iterator __first, const_iterator __last,
  372.         const allocator_type& __a =  allocator_type()) : _Base(__a)
  373.     { _M_insert_after_range(&_M_head, __first, __last); }
  374.   slist(const value_type* __first, const value_type* __last,
  375.         const allocator_type& __a =  allocator_type()) : _Base(__a)
  376.     { _M_insert_after_range(&_M_head, __first, __last); }
  377. #endif /* __STL_MEMBER_TEMPLATES */
  378.  
  379.   slist(const slist& __x) : _Base(__x.get_allocator())
  380.     { _M_insert_after_range(&_M_head, __x.begin(), __x.end()); }
  381.  
  382.   slist& operator= (const slist& __x);
  383.  
  384.   ~slist() {}
  385.  
  386. public:
  387.   // assign(), a generalized assignment member function.  Two
  388.   // versions: one that takes a count, and one that takes a range.
  389.   // The range version is a member template, so we dispatch on whether
  390.   // or not the type is an integer.
  391.  
  392.   void assign(size_type __n, const _Tp& __val);
  393.  
  394. #ifdef __STL_MEMBER_TEMPLATES
  395.  
  396.   template <class _InputIterator>
  397.   void assign(_InputIterator __first, _InputIterator __last) {
  398.     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
  399.     _M_assign_dispatch(__first, __last, _Integral());
  400.   }
  401.  
  402.   template <class _Integer>
  403.   void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
  404.     { assign((size_type) __n, (_Tp) __val); }
  405.  
  406.   template <class _InputIterator>
  407.   void _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
  408.                           __false_type);
  409.  
  410. #endif /* __STL_MEMBER_TEMPLATES */
  411.  
  412. public:
  413.  
  414.   iterator begin() { return iterator((_Node*)_M_head._M_next); }
  415.   const_iterator begin() const 
  416.     { return const_iterator((_Node*)_M_head._M_next);}
  417.  
  418.   iterator end() { return iterator(0); }
  419.   const_iterator end() const { return const_iterator(0); }
  420.  
  421.   size_type size() const { return __slist_size(_M_head._M_next); }
  422.   
  423.   size_type max_size() const { return size_type(-1); }
  424.  
  425.   bool empty() const { return _M_head._M_next == 0; }
  426.  
  427.   void swap(slist& __x) { __STD::swap(_M_head._M_next, __x._M_head._M_next); }
  428.  
  429. public:
  430.   friend bool operator== __STL_NULL_TMPL_ARGS (const slist<_Tp,_Alloc>& _SL1,
  431.                                                const slist<_Tp,_Alloc>& _SL2);
  432.  
  433. public:
  434.  
  435.   reference front() { return ((_Node*) _M_head._M_next)->_M_data; }
  436.   const_reference front() const 
  437.     { return ((_Node*) _M_head._M_next)->_M_data; }
  438.   void push_front(const value_type& __x)   {
  439.     __slist_make_link(&_M_head, _M_create_node(__x));
  440.   }
  441.   void push_front() { __slist_make_link(&_M_head, _M_create_node());}
  442.   void pop_front() {
  443.     _Node* __node = (_Node*) _M_head._M_next;
  444.     _M_head._M_next = __node->_M_next;
  445.     destroy(&__node->_M_data);
  446.     _M_put_node(__node);
  447.   }
  448.  
  449.   iterator previous(const_iterator __pos) {
  450.     return iterator((_Node*) __slist_previous(&_M_head, __pos._M_node));
  451.   }
  452.   const_iterator previous(const_iterator __pos) const {
  453.     return const_iterator((_Node*) __slist_previous(&_M_head, __pos._M_node));
  454.   }
  455.  
  456. private:
  457.   _Node* _M_insert_after(_Node_base* __pos, const value_type& __x) {
  458.     return (_Node*) (__slist_make_link(__pos, _M_create_node(__x)));
  459.   }
  460.  
  461.   _Node* _M_insert_after(_Node_base* __pos) {
  462.     return (_Node*) (__slist_make_link(__pos, _M_create_node()));
  463.   }
  464.  
  465.   void _M_insert_after_fill(_Node_base* __pos,
  466.                             size_type __n, const value_type& __x) {
  467.     for (size_type __i = 0; __i < __n; ++__i)
  468.       __pos = __slist_make_link(__pos, _M_create_node(__x));
  469.   }
  470.  
  471. #ifdef __STL_MEMBER_TEMPLATES
  472.  
  473.   // Check whether it's an integral type.  If so, it's not an iterator.
  474.   template <class _InIter>
  475.   void _M_insert_after_range(_Node_base* __pos, 
  476.                              _InIter __first, _InIter __last) {
  477.     typedef typename _Is_integer<_InIter>::_Integral _Integral;
  478.     _M_insert_after_range(__pos, __first, __last, _Integral());
  479.   }
  480.  
  481.   template <class _Integer>
  482.   void _M_insert_after_range(_Node_base* __pos, _Integer __n, _Integer __x,
  483.                              __true_type) {
  484.     _M_insert_after_fill(__pos, __n, __x);
  485.   }
  486.  
  487.   template <class _InIter>
  488.   void _M_insert_after_range(_Node_base* __pos,
  489.                              _InIter __first, _InIter __last,
  490.                              __false_type) {
  491.     while (__first != __last) {
  492.       __pos = __slist_make_link(__pos, _M_create_node(*__first));
  493.       ++__first;
  494.     }
  495.   }
  496.  
  497. #else /* __STL_MEMBER_TEMPLATES */
  498.  
  499.   void _M_insert_after_range(_Node_base* __pos,
  500.                              const_iterator __first, const_iterator __last) {
  501.     while (__first != __last) {
  502.       __pos = __slist_make_link(__pos, _M_create_node(*__first));
  503.       ++__first;
  504.     }
  505.   }
  506.   void _M_insert_after_range(_Node_base* __pos,
  507.                              const value_type* __first,
  508.                              const value_type* __last) {
  509.     while (__first != __last) {
  510.       __pos = __slist_make_link(__pos, _M_create_node(*__first));
  511.       ++__first;
  512.     }
  513.   }
  514.  
  515. #endif /* __STL_MEMBER_TEMPLATES */
  516.  
  517. public:
  518.  
  519.   iterator insert_after(iterator __pos, const value_type& __x) {
  520.     return iterator(_M_insert_after(__pos._M_node, __x));
  521.   }
  522.  
  523.   iterator insert_after(iterator __pos) {
  524.     return insert_after(__pos, value_type());
  525.   }
  526.  
  527.   void insert_after(iterator __pos, size_type __n, const value_type& __x) {
  528.     _M_insert_after_fill(__pos._M_node, __n, __x);
  529.   }
  530.  
  531. #ifdef __STL_MEMBER_TEMPLATES
  532.  
  533.   // We don't need any dispatching tricks here, because _M_insert_after_range
  534.   // already does them.
  535.   template <class _InIter>
  536.   void insert_after(iterator __pos, _InIter __first, _InIter __last) {
  537.     _M_insert_after_range(__pos._M_node, __first, __last);
  538.   }
  539.  
  540. #else /* __STL_MEMBER_TEMPLATES */
  541.  
  542.   void insert_after(iterator __pos,
  543.                     const_iterator __first, const_iterator __last) {
  544.     _M_insert_after_range(__pos._M_node, __first, __last);
  545.   }
  546.   void insert_after(iterator __pos,
  547.                     const value_type* __first, const value_type* __last) {
  548.     _M_insert_after_range(__pos._M_node, __first, __last);
  549.   }
  550.  
  551. #endif /* __STL_MEMBER_TEMPLATES */
  552.  
  553.   iterator insert(iterator __pos, const value_type& __x) {
  554.     return iterator(_M_insert_after(__slist_previous(&_M_head, __pos._M_node),
  555.                     __x));
  556.   }
  557.  
  558.   iterator insert(iterator __pos) {
  559.     return iterator(_M_insert_after(__slist_previous(&_M_head, __pos._M_node),
  560.                                     value_type()));
  561.   }
  562.  
  563.   void insert(iterator __pos, size_type __n, const value_type& __x) {
  564.     _M_insert_after_fill(__slist_previous(&_M_head, __pos._M_node), __n, __x);
  565.   } 
  566.     
  567. #ifdef __STL_MEMBER_TEMPLATES
  568.  
  569.   // We don't need any dispatching tricks here, because _M_insert_after_range
  570.   // already does them.
  571.   template <class _InIter>
  572.   void insert(iterator __pos, _InIter __first, _InIter __last) {
  573.     _M_insert_after_range(__slist_previous(&_M_head, __pos._M_node), 
  574.                           __first, __last);
  575.   }
  576.  
  577. #else /* __STL_MEMBER_TEMPLATES */
  578.  
  579.   void insert(iterator __pos, const_iterator __first, const_iterator __last) {
  580.     _M_insert_after_range(__slist_previous(&_M_head, __pos._M_node), 
  581.                           __first, __last);
  582.   }
  583.   void insert(iterator __pos, const value_type* __first, 
  584.                               const value_type* __last) {
  585.     _M_insert_after_range(__slist_previous(&_M_head, __pos._M_node), 
  586.                           __first, __last);
  587.   }
  588.  
  589. #endif /* __STL_MEMBER_TEMPLATES */
  590.  
  591.  
  592. public:
  593.   iterator erase_after(iterator __pos) {
  594.     return iterator((_Node*) _M_erase_after(__pos._M_node));
  595.   }
  596.   iterator erase_after(iterator __before_first, iterator __last) {
  597.     return iterator((_Node*) _M_erase_after(__before_first._M_node, 
  598.                                             __last._M_node));
  599.   } 
  600.  
  601.   iterator erase(iterator __pos) {
  602.     return (_Node*) _M_erase_after(__slist_previous(&_M_head, 
  603.                                                     __pos._M_node));
  604.   }
  605.   iterator erase(iterator __first, iterator __last) {
  606.     return (_Node*) _M_erase_after(
  607.       __slist_previous(&_M_head, __first._M_node), __last._M_node);
  608.   }
  609.  
  610.   void resize(size_type new_size, const _Tp& __x);
  611.   void resize(size_type new_size) { resize(new_size, _Tp()); }
  612.   void clear() { _M_erase_after(&_M_head, 0); }
  613.  
  614. public:
  615.   // Moves the range [__before_first + 1, __before_last + 1) to *this,
  616.   //  inserting it immediately after __pos.  This is constant time.
  617.   void splice_after(iterator __pos, 
  618.                     iterator __before_first, iterator __before_last)
  619.   {
  620.     if (__before_first != __before_last) 
  621.       __slist_splice_after(__pos._M_node, __before_first._M_node, 
  622.                            __before_last._M_node);
  623.   }
  624.  
  625.   // Moves the element that follows __prev to *this, inserting it immediately
  626.   //  after __pos.  This is constant time.
  627.   void splice_after(iterator __pos, iterator __prev)
  628.   {
  629.     __slist_splice_after(__pos._M_node,
  630.                          __prev._M_node, __prev._M_node->_M_next);
  631.   }
  632.  
  633.  
  634.   // Linear in distance(begin(), __pos), and linear in __x.size().
  635.   void splice(iterator __pos, slist& __x) {
  636.     if (__x._M_head._M_next)
  637.       __slist_splice_after(__slist_previous(&_M_head, __pos._M_node),
  638.                            &__x._M_head, __slist_previous(&__x._M_head, 0));
  639.   }
  640.  
  641.   // Linear in distance(begin(), __pos), and in distance(__x.begin(), __i).
  642.   void splice(iterator __pos, slist& __x, iterator __i) {
  643.     __slist_splice_after(__slist_previous(&_M_head, __pos._M_node),
  644.                          __slist_previous(&__x._M_head, __i._M_node),
  645.                          __i._M_node);
  646.   }
  647.  
  648.   // Linear in distance(begin(), __pos), in distance(__x.begin(), __first),
  649.   // and in distance(__first, __last).
  650.   void splice(iterator __pos, slist& __x, iterator __first, iterator __last)
  651.   {
  652.     if (__first != __last)
  653.       __slist_splice_after(__slist_previous(&_M_head, __pos._M_node),
  654.                            __slist_previous(&__x._M_head, __first._M_node),
  655.                            __slist_previous(__first._M_node, __last._M_node));
  656.   }
  657.  
  658. public:
  659.   void reverse() { 
  660.     if (_M_head._M_next)
  661.       _M_head._M_next = __slist_reverse(_M_head._M_next);
  662.   }
  663.  
  664.   void remove(const _Tp& __val); 
  665.   void unique(); 
  666.   void merge(slist& __x);
  667.   void sort();     
  668.  
  669. #ifdef __STL_MEMBER_TEMPLATES
  670.   template <class _Predicate> 
  671.   void remove_if(_Predicate __pred);
  672.  
  673.   template <class _BinaryPredicate> 
  674.   void unique(_BinaryPredicate __pred); 
  675.  
  676.   template <class _StrictWeakOrdering> 
  677.   void merge(slist&, _StrictWeakOrdering);
  678.  
  679.   template <class _StrictWeakOrdering> 
  680.   void sort(_StrictWeakOrdering __comp); 
  681. #endif /* __STL_MEMBER_TEMPLATES */
  682. };
  683.  
  684. template <class _Tp, class _Alloc>
  685. slist<_Tp,_Alloc>& slist<_Tp,_Alloc>::operator=(const slist<_Tp,_Alloc>& __x)
  686. {
  687.   if (&__x != this) {
  688.     _Node_base* __p1 = &_M_head;
  689.     _Node* __n1 = (_Node*) _M_head._M_next;
  690.     const _Node* __n2 = (const _Node*) __x._M_head._M_next;
  691.     while (__n1 && __n2) {
  692.       __n1->_M_data = __n2->_M_data;
  693.       __p1 = __n1;
  694.       __n1 = (_Node*) __n1->_M_next;
  695.       __n2 = (const _Node*) __n2->_M_next;
  696.     }
  697.     if (__n2 == 0)
  698.       _M_erase_after(__p1, 0);
  699.     else
  700.       _M_insert_after_range(__p1, const_iterator((_Node*)__n2), 
  701.                                   const_iterator(0));
  702.   }
  703.   return *this;
  704. }
  705.  
  706. template <class _Tp, class _Alloc>
  707. void slist<_Tp, _Alloc>::assign(size_type __n, const _Tp& __val) {
  708.   _Node_base* __prev = &_M_head;
  709.   _Node* __node = (_Node*) _M_head._M_next;
  710.   for ( ; __node != 0 && __n > 0 ; --__n) {
  711.     __node->_M_data = __val;
  712.     __prev = __node;
  713.     __node = (_Node*) __node->_M_next;
  714.   }
  715.   if (__n > 0)
  716.     _M_insert_after_fill(__prev, __n, __val);
  717.   else
  718.     _M_erase_after(__prev, 0);
  719. }
  720.  
  721. #ifdef __STL_MEMBER_TEMPLATES
  722.  
  723. template <class _Tp, class _Alloc> template <class _InputIter>
  724. void
  725. slist<_Tp, _Alloc>::_M_assign_dispatch(_InputIter __first, _InputIter __last,
  726.                                        __false_type)
  727. {
  728.   _Node_base* __prev = &_M_head;
  729.   _Node* __node = (_Node*) _M_head._M_next;
  730.   while (__node != 0 && __first != __last) {
  731.     __node->_M_data = *__first;
  732.     __prev = __node;
  733.     __node = (_Node*) __node->_M_next;
  734.     ++__first;
  735.   }
  736.   if (__first != __last)
  737.     _M_insert_after_range(__prev, __first, __last);
  738.   else
  739.     _M_erase_after(__prev, 0);
  740. }
  741.  
  742. #endif /* __STL_MEMBER_TEMPLATES */
  743.  
  744. template <class _Tp, class _Alloc>
  745. inline bool 
  746. operator==(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2)
  747. {
  748.   typedef typename slist<_Tp,_Alloc>::_Node _Node;
  749.   _Node* __n1 = (_Node*) _SL1._M_head._M_next;
  750.   _Node* __n2 = (_Node*) _SL2._M_head._M_next;
  751.   while (__n1 && __n2 && __n1->_M_data == __n2->_M_data) {
  752.     __n1 = (_Node*) __n1->_M_next;
  753.     __n2 = (_Node*) __n2->_M_next;
  754.   }
  755.   return __n1 == 0 && __n2 == 0;
  756. }
  757.  
  758. template <class _Tp, class _Alloc>
  759. inline bool operator<(const slist<_Tp,_Alloc>& _SL1,
  760.                       const slist<_Tp,_Alloc>& _SL2)
  761. {
  762.   return lexicographical_compare(_SL1.begin(), _SL1.end(), 
  763.                                  _SL2.begin(), _SL2.end());
  764. }
  765.  
  766. #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
  767.  
  768. template <class _Tp, class _Alloc>
  769. inline void swap(slist<_Tp,_Alloc>& __x, slist<_Tp,_Alloc>& __y) {
  770.   __x.swap(__y);
  771. }
  772.  
  773. #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
  774.  
  775.  
  776. template <class _Tp, class _Alloc>
  777. void slist<_Tp,_Alloc>::resize(size_type __len, const _Tp& __x)
  778. {
  779.   _Node_base* __cur = &_M_head;
  780.   while (__cur->_M_next != 0 && __len > 0) {
  781.     --__len;
  782.     __cur = __cur->_M_next;
  783.   }
  784.   if (__cur->_M_next) 
  785.     _M_erase_after(__cur, 0);
  786.   else
  787.     _M_insert_after_fill(__cur, __len, __x);
  788. }
  789.  
  790. template <class _Tp, class _Alloc>
  791. void slist<_Tp,_Alloc>::remove(const _Tp& __val)
  792. {
  793.   _Node_base* __cur = &_M_head;
  794.   while (__cur && __cur->_M_next) {
  795.     if (((_Node*) __cur->_M_next)->_M_data == __val)
  796.       _M_erase_after(__cur);
  797.     else
  798.       __cur = __cur->_M_next;
  799.   }
  800. }
  801.  
  802. template <class _Tp, class _Alloc> 
  803. void slist<_Tp,_Alloc>::unique()
  804. {
  805.   _Node_base* __cur = _M_head._M_next;
  806.   if (__cur) {
  807.     while (__cur->_M_next) {
  808.       if (((_Node*)__cur)->_M_data == 
  809.           ((_Node*)(__cur->_M_next))->_M_data)
  810.         _M_erase_after(__cur);
  811.       else
  812.         __cur = __cur->_M_next;
  813.     }
  814.   }
  815. }
  816.  
  817. template <class _Tp, class _Alloc>
  818. void slist<_Tp,_Alloc>::merge(slist<_Tp,_Alloc>& __x)
  819. {
  820.   _Node_base* __n1 = &_M_head;
  821.   while (__n1->_M_next && __x._M_head._M_next) {
  822.     if (((_Node*) __x._M_head._M_next)->_M_data < 
  823.         ((_Node*)       __n1->_M_next)->_M_data) 
  824.       __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next);
  825.     __n1 = __n1->_M_next;
  826.   }
  827.   if (__x._M_head._M_next) {
  828.     __n1->_M_next = __x._M_head._M_next;
  829.     __x._M_head._M_next = 0;
  830.   }
  831. }
  832.  
  833. template <class _Tp, class _Alloc>
  834. void slist<_Tp,_Alloc>::sort()
  835. {
  836.   if (_M_head._M_next && _M_head._M_next->_M_next) {
  837.     slist __carry;
  838.     slist __counter[64];
  839.     int __fill = 0;
  840.     while (!empty()) {
  841.       __slist_splice_after(&__carry._M_head, &_M_head, _M_head._M_next);
  842.       int __i = 0;
  843.       while (__i < __fill && !__counter[__i].empty()) {
  844.         __counter[__i].merge(__carry);
  845.         __carry.swap(__counter[__i]);
  846.         ++__i;
  847.       }
  848.       __carry.swap(__counter[__i]);
  849.       if (__i == __fill)
  850.         ++__fill;
  851.     }
  852.  
  853.     for (int __i = 1; __i < __fill; ++__i)
  854.       __counter[__i].merge(__counter[__i-1]);
  855.     this->swap(__counter[__fill-1]);
  856.   }
  857. }
  858.  
  859. #ifdef __STL_MEMBER_TEMPLATES
  860.  
  861. template <class _Tp, class _Alloc> 
  862. template <class _Predicate>
  863. void slist<_Tp,_Alloc>::remove_if(_Predicate __pred)
  864. {
  865.   _Node_base* __cur = &_M_head;
  866.   while (__cur->_M_next) {
  867.     if (__pred(((_Node*) __cur->_M_next)->_M_data))
  868.       _M_erase_after(__cur);
  869.     else
  870.       __cur = __cur->_M_next;
  871.   }
  872. }
  873.  
  874. template <class _Tp, class _Alloc> template <class _BinaryPredicate> 
  875. void slist<_Tp,_Alloc>::unique(_BinaryPredicate __pred)
  876. {
  877.   _Node* __cur = (_Node*) _M_head._M_next;
  878.   if (__cur) {
  879.     while (__cur->_M_next) {
  880.       if (__pred(((_Node*)__cur)->_M_data, 
  881.                  ((_Node*)(__cur->_M_next))->_M_data))
  882.         _M_erase_after(__cur);
  883.       else
  884.         __cur = (_Node*) __cur->_M_next;
  885.     }
  886.   }
  887. }
  888.  
  889. template <class _Tp, class _Alloc> template <class _StrictWeakOrdering>
  890. void slist<_Tp,_Alloc>::merge(slist<_Tp,_Alloc>& __x,
  891.                               _StrictWeakOrdering __comp)
  892. {
  893.   _Node_base* __n1 = &_M_head;
  894.   while (__n1->_M_next && __x._M_head._M_next) {
  895.     if (__comp(((_Node*) __x._M_head._M_next)->_M_data,
  896.                ((_Node*)       __n1->_M_next)->_M_data))
  897.       __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next);
  898.     __n1 = __n1->_M_next;
  899.   }
  900.   if (__x._M_head._M_next) {
  901.     __n1->_M_next = __x._M_head._M_next;
  902.     __x._M_head._M_next = 0;
  903.   }
  904. }
  905.  
  906. template <class _Tp, class _Alloc> template <class _StrictWeakOrdering> 
  907. void slist<_Tp,_Alloc>::sort(_StrictWeakOrdering __comp)
  908. {
  909.   if (_M_head._M_next && _M_head._M_next->_M_next) {
  910.     slist __carry;
  911.     slist __counter[64];
  912.     int __fill = 0;
  913.     while (!empty()) {
  914.       __slist_splice_after(&__carry._M_head, &_M_head, _M_head._M_next);
  915.       int __i = 0;
  916.       while (__i < __fill && !__counter[__i].empty()) {
  917.         __counter[__i].merge(__carry, __comp);
  918.         __carry.swap(__counter[__i]);
  919.         ++__i;
  920.       }
  921.       __carry.swap(__counter[__i]);
  922.       if (__i == __fill)
  923.         ++__fill;
  924.     }
  925.  
  926.     for (int __i = 1; __i < __fill; ++__i)
  927.       __counter[__i].merge(__counter[__i-1], __comp);
  928.     this->swap(__counter[__fill-1]);
  929.   }
  930. }
  931.  
  932. #endif /* __STL_MEMBER_TEMPLATES */
  933.  
  934. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  935. #pragma reset woff 1174
  936. #pragma reset woff 1375
  937. #endif
  938.  
  939. __STL_END_NAMESPACE 
  940.  
  941. #endif /* __SGI_STL_INTERNAL_SLIST_H */
  942.  
  943. // Local Variables:
  944. // mode:C++
  945. // End:
  946.