home *** CD-ROM | disk | FTP | other *** search
/ Beginning C++ Through Gam…rogramming (2nd Edition) / BCGP2E.ISO / bloodshed / devcpp-4.9.9.2_setup.exe / slist < prev    next >
Text File  |  2005-01-29  |  28KB  |  907 lines

  1. // Singly-linked list implementation -*- C++ -*-
  2.  
  3. // Copyright (C) 2001, 2002 Free Software Foundation, Inc.
  4. //
  5. // This file is part of the GNU ISO C++ Library.  This library is free
  6. // software; you can redistribute it and/or modify it under the
  7. // terms of the GNU General Public License as published by the
  8. // Free Software Foundation; either version 2, or (at your option)
  9. // any later version.
  10.  
  11. // This library is distributed in the hope that it will be useful,
  12. // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. // GNU General Public License for more details.
  15.  
  16. // You should have received a copy of the GNU General Public License along
  17. // with this library; see the file COPYING.  If not, write to the Free
  18. // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  19. // USA.
  20.  
  21. // As a special exception, you may use this file as part of a free software
  22. // library without restriction.  Specifically, if other files instantiate
  23. // templates or use macros or inline functions from this file, or you compile
  24. // this file and link it with other files to produce an executable, this
  25. // file does not by itself cause the resulting executable to be covered by
  26. // the GNU General Public License.  This exception does not however
  27. // invalidate any other reasons why the executable file might be covered by
  28. // the GNU General Public License.
  29.  
  30. /*
  31.  * Copyright (c) 1997
  32.  * Silicon Graphics Computer Systems, Inc.
  33.  *
  34.  * Permission to use, copy, modify, distribute and sell this software
  35.  * and its documentation for any purpose is hereby granted without fee,
  36.  * provided that the above copyright notice appear in all copies and
  37.  * that both that copyright notice and this permission notice appear
  38.  * in supporting documentation.  Silicon Graphics makes no
  39.  * representations about the suitability of this software for any
  40.  * purpose.  It is provided "as is" without express or implied warranty.
  41.  *
  42.  */
  43.  
  44. /** @file ext/slist
  45.  *  This file is a GNU extension to the Standard C++ Library (possibly
  46.  *  containing extensions from the HP/SGI STL subset).  You should only
  47.  *  include this header if you are using GCC 3 or later.
  48.  */
  49.  
  50. #ifndef _SLIST
  51. #define _SLIST 1
  52.  
  53. #include <bits/stl_algobase.h>
  54. #include <bits/allocator.h>
  55. #include <bits/stl_construct.h>
  56. #include <bits/stl_uninitialized.h>
  57. #include <bits/concept_check.h>
  58.  
  59. namespace __gnu_cxx
  60. {
  61. using std::size_t;
  62. using std::ptrdiff_t;
  63. using std::_Construct;
  64. using std::_Destroy;
  65. using std::allocator;
  66.  
  67. struct _Slist_node_base
  68. {
  69.   _Slist_node_base* _M_next;
  70. };
  71.  
  72. inline _Slist_node_base*
  73. __slist_make_link(_Slist_node_base* __prev_node,
  74.                   _Slist_node_base* __new_node)
  75. {
  76.   __new_node->_M_next = __prev_node->_M_next;
  77.   __prev_node->_M_next = __new_node;
  78.   return __new_node;
  79. }
  80.  
  81. inline _Slist_node_base*
  82. __slist_previous(_Slist_node_base* __head,
  83.                  const _Slist_node_base* __node)
  84. {
  85.   while (__head && __head->_M_next != __node)
  86.     __head = __head->_M_next;
  87.   return __head;
  88. }
  89.  
  90. inline const _Slist_node_base*
  91. __slist_previous(const _Slist_node_base* __head,
  92.                  const _Slist_node_base* __node)
  93. {
  94.   while (__head && __head->_M_next != __node)
  95.     __head = __head->_M_next;
  96.   return __head;
  97. }
  98.  
  99. inline void __slist_splice_after(_Slist_node_base* __pos,
  100.                                  _Slist_node_base* __before_first,
  101.                                  _Slist_node_base* __before_last)
  102. {
  103.   if (__pos != __before_first && __pos != __before_last) {
  104.     _Slist_node_base* __first = __before_first->_M_next;
  105.     _Slist_node_base* __after = __pos->_M_next;
  106.     __before_first->_M_next = __before_last->_M_next;
  107.     __pos->_M_next = __first;
  108.     __before_last->_M_next = __after;
  109.   }
  110. }
  111.  
  112. inline void
  113. __slist_splice_after(_Slist_node_base* __pos, _Slist_node_base* __head)
  114. {
  115.   _Slist_node_base* __before_last = __slist_previous(__head, 0);
  116.   if (__before_last != __head) {
  117.     _Slist_node_base* __after = __pos->_M_next;
  118.     __pos->_M_next = __head->_M_next;
  119.     __head->_M_next = 0;
  120.     __before_last->_M_next = __after;
  121.   }
  122. }
  123.  
  124. inline _Slist_node_base* __slist_reverse(_Slist_node_base* __node)
  125. {
  126.   _Slist_node_base* __result = __node;
  127.   __node = __node->_M_next;
  128.   __result->_M_next = 0;
  129.   while(__node) {
  130.     _Slist_node_base* __next = __node->_M_next;
  131.     __node->_M_next = __result;
  132.     __result = __node;
  133.     __node = __next;
  134.   }
  135.   return __result;
  136. }
  137.  
  138. inline size_t __slist_size(_Slist_node_base* __node)
  139. {
  140.   size_t __result = 0;
  141.   for ( ; __node != 0; __node = __node->_M_next)
  142.     ++__result;
  143.   return __result;
  144. }
  145.  
  146. template <class _Tp>
  147. struct _Slist_node : public _Slist_node_base
  148. {
  149.   _Tp _M_data;
  150. };
  151.  
  152. struct _Slist_iterator_base
  153. {
  154.   typedef size_t                    size_type;
  155.   typedef ptrdiff_t                 difference_type;
  156.   typedef std::forward_iterator_tag iterator_category;
  157.  
  158.   _Slist_node_base* _M_node;
  159.  
  160.   _Slist_iterator_base(_Slist_node_base* __x) : _M_node(__x) {}
  161.   void _M_incr() { _M_node = _M_node->_M_next; }
  162.  
  163.   bool operator==(const _Slist_iterator_base& __x) const {
  164.     return _M_node == __x._M_node;
  165.   }
  166.   bool operator!=(const _Slist_iterator_base& __x) const {
  167.     return _M_node != __x._M_node;
  168.   }
  169. };
  170.  
  171. template <class _Tp, class _Ref, class _Ptr>
  172. struct _Slist_iterator : public _Slist_iterator_base
  173. {
  174.   typedef _Slist_iterator<_Tp, _Tp&, _Tp*>             iterator;
  175.   typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
  176.   typedef _Slist_iterator<_Tp, _Ref, _Ptr>             _Self;
  177.  
  178.   typedef _Tp              value_type;
  179.   typedef _Ptr             pointer;
  180.   typedef _Ref             reference;
  181.   typedef _Slist_node<_Tp> _Node;
  182.  
  183.   _Slist_iterator(_Node* __x) : _Slist_iterator_base(__x) {}
  184.   _Slist_iterator() : _Slist_iterator_base(0) {}
  185.   _Slist_iterator(const iterator& __x) : _Slist_iterator_base(__x._M_node) {}
  186.  
  187.   reference operator*() const { return ((_Node*) _M_node)->_M_data; }
  188.   pointer operator->() const { return &(operator*()); }
  189.  
  190.   _Self& operator++()
  191.   {
  192.     _M_incr();
  193.     return *this;
  194.   }
  195.   _Self operator++(int)
  196.   {
  197.     _Self __tmp = *this;
  198.     _M_incr();
  199.     return __tmp;
  200.   }
  201. };
  202.  
  203. template <class _Tp, class _Alloc>
  204. struct _Slist_base
  205.   : public _Alloc::template rebind<_Slist_node<_Tp> >::other
  206. {
  207.   typedef typename _Alloc::template rebind<_Slist_node<_Tp> >::other _Node_alloc;
  208.   typedef _Alloc allocator_type;
  209.   allocator_type get_allocator() const {
  210.     return *static_cast<const _Node_alloc*>(this);
  211.   }
  212.  
  213.   _Slist_base(const allocator_type& __a)
  214.     : _Node_alloc(__a) { this->_M_head._M_next = 0; }
  215.   ~_Slist_base() { _M_erase_after(&this->_M_head, 0); }
  216.  
  217. protected:
  218.   _Slist_node_base _M_head;
  219.  
  220.   _Slist_node<_Tp>* _M_get_node() { return _Node_alloc::allocate(1); }
  221.   void _M_put_node(_Slist_node<_Tp>* __p) { _Node_alloc::deallocate(__p, 1); }
  222.  
  223. protected:
  224.   _Slist_node_base* _M_erase_after(_Slist_node_base* __pos)
  225.   {
  226.     _Slist_node<_Tp>* __next = (_Slist_node<_Tp>*) (__pos->_M_next);
  227.     _Slist_node_base* __next_next = __next->_M_next;
  228.     __pos->_M_next = __next_next;
  229.     _Destroy(&__next->_M_data);
  230.     _M_put_node(__next);
  231.     return __next_next;
  232.   }
  233.   _Slist_node_base* _M_erase_after(_Slist_node_base*, _Slist_node_base*);
  234. };
  235.  
  236. template <class _Tp, class _Alloc>
  237. _Slist_node_base*
  238. _Slist_base<_Tp,_Alloc>::_M_erase_after(_Slist_node_base* __before_first,
  239.                                         _Slist_node_base* __last_node) {
  240.   _Slist_node<_Tp>* __cur = (_Slist_node<_Tp>*) (__before_first->_M_next);
  241.   while (__cur != __last_node) {
  242.     _Slist_node<_Tp>* __tmp = __cur;
  243.     __cur = (_Slist_node<_Tp>*) __cur->_M_next;
  244.     _Destroy(&__tmp->_M_data);
  245.     _M_put_node(__tmp);
  246.   }
  247.   __before_first->_M_next = __last_node;
  248.   return __last_node;
  249. }
  250.  
  251. /**
  252.  *  This is an SGI extension.
  253.  *  @ingroup SGIextensions
  254.  *  @doctodo
  255. */
  256. template <class _Tp, class _Alloc = allocator<_Tp> >
  257. class slist : private _Slist_base<_Tp,_Alloc>
  258. {
  259.   // concept requirements
  260.   __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
  261.  
  262. private:
  263.   typedef _Slist_base<_Tp,_Alloc> _Base;
  264. public:
  265.   typedef _Tp               value_type;
  266.   typedef value_type*       pointer;
  267.   typedef const value_type* const_pointer;
  268.   typedef value_type&       reference;
  269.   typedef const value_type& const_reference;
  270.   typedef size_t            size_type;
  271.   typedef ptrdiff_t         difference_type;
  272.  
  273.   typedef _Slist_iterator<_Tp, _Tp&, _Tp*>             iterator;
  274.   typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
  275.  
  276.   typedef typename _Base::allocator_type allocator_type;
  277.   allocator_type get_allocator() const { return _Base::get_allocator(); }
  278.  
  279. private:
  280.   typedef _Slist_node<_Tp>      _Node;
  281.   typedef _Slist_node_base      _Node_base;
  282.   typedef _Slist_iterator_base  _Iterator_base;
  283.  
  284.   _Node* _M_create_node(const value_type& __x) {
  285.     _Node* __node = this->_M_get_node();
  286.     try {
  287.       _Construct(&__node->_M_data, __x);
  288.       __node->_M_next = 0;
  289.     }
  290.     catch(...)
  291.       {
  292.     this->_M_put_node(__node);
  293.     __throw_exception_again;
  294.       }
  295.     return __node;
  296.   }
  297.  
  298.   _Node* _M_create_node() {
  299.     _Node* __node = this->_M_get_node();
  300.     try {
  301.       _Construct(&__node->_M_data);
  302.       __node->_M_next = 0;
  303.     }
  304.     catch(...)
  305.       {
  306.     this->_M_put_node(__node);
  307.     __throw_exception_again;
  308.       }
  309.     return __node;
  310.   }
  311.  
  312. public:
  313.   explicit slist(const allocator_type& __a = allocator_type()) : _Base(__a) {}
  314.  
  315.   slist(size_type __n, const value_type& __x,
  316.         const allocator_type& __a =  allocator_type()) : _Base(__a)
  317.     { _M_insert_after_fill(&this->_M_head, __n, __x); }
  318.  
  319.   explicit slist(size_type __n) : _Base(allocator_type())
  320.     { _M_insert_after_fill(&this->_M_head, __n, value_type()); }
  321.  
  322.   // We don't need any dispatching tricks here, because _M_insert_after_range
  323.   // already does them.
  324.   template <class _InputIterator>
  325.   slist(_InputIterator __first, _InputIterator __last,
  326.         const allocator_type& __a =  allocator_type()) : _Base(__a)
  327.     { _M_insert_after_range(&this->_M_head, __first, __last); }
  328.  
  329.   slist(const slist& __x) : _Base(__x.get_allocator())
  330.     { _M_insert_after_range(&this->_M_head, __x.begin(), __x.end()); }
  331.  
  332.   slist& operator= (const slist& __x);
  333.  
  334.   ~slist() {}
  335.  
  336. public:
  337.   // assign(), a generalized assignment member function.  Two
  338.   // versions: one that takes a count, and one that takes a range.
  339.   // The range version is a member template, so we dispatch on whether
  340.   // or not the type is an integer.
  341.  
  342.   void assign(size_type __n, const _Tp& __val)
  343.     { _M_fill_assign(__n, __val); }
  344.  
  345.   void _M_fill_assign(size_type __n, const _Tp& __val);
  346.  
  347.   template <class _InputIterator>
  348.   void assign(_InputIterator __first, _InputIterator __last) {
  349.     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
  350.     _M_assign_dispatch(__first, __last, _Integral());
  351.   }
  352.  
  353.   template <class _Integer>
  354.   void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
  355.     { _M_fill_assign((size_type) __n, (_Tp) __val); }
  356.  
  357.   template <class _InputIterator>
  358.   void _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
  359.                           __false_type);
  360.  
  361. public:
  362.  
  363.   iterator begin() { return iterator((_Node*)this->_M_head._M_next); }
  364.   const_iterator begin() const
  365.     { return const_iterator((_Node*)this->_M_head._M_next);}
  366.  
  367.   iterator end() { return iterator(0); }
  368.   const_iterator end() const { return const_iterator(0); }
  369.  
  370.   // Experimental new feature: before_begin() returns a
  371.   // non-dereferenceable iterator that, when incremented, yields
  372.   // begin().  This iterator may be used as the argument to
  373.   // insert_after, erase_after, etc.  Note that even for an empty
  374.   // slist, before_begin() is not the same iterator as end().  It
  375.   // is always necessary to increment before_begin() at least once to
  376.   // obtain end().
  377.   iterator before_begin() { return iterator((_Node*) &this->_M_head); }
  378.   const_iterator before_begin() const
  379.     { return const_iterator((_Node*) &this->_M_head); }
  380.  
  381.   size_type size() const { return __slist_size(this->_M_head._M_next); }
  382.  
  383.   size_type max_size() const { return size_type(-1); }
  384.  
  385.   bool empty() const { return this->_M_head._M_next == 0; }
  386.  
  387.   void swap(slist& __x)
  388.     { std::swap(this->_M_head._M_next, __x._M_head._M_next); }
  389.  
  390. public:
  391.  
  392.   reference front() { return ((_Node*) this->_M_head._M_next)->_M_data; }
  393.   const_reference front() const
  394.     { return ((_Node*) this->_M_head._M_next)->_M_data; }
  395.   void push_front(const value_type& __x)   {
  396.     __slist_make_link(&this->_M_head, _M_create_node(__x));
  397.   }
  398.   void push_front() { __slist_make_link(&this->_M_head, _M_create_node()); }
  399.   void pop_front() {
  400.     _Node* __node = (_Node*) this->_M_head._M_next;
  401.     this->_M_head._M_next = __node->_M_next;
  402.     _Destroy(&__node->_M_data);
  403.     this->_M_put_node(__node);
  404.   }
  405.  
  406.   iterator previous(const_iterator __pos) {
  407.     return iterator((_Node*) __slist_previous(&this->_M_head, __pos._M_node));
  408.   }
  409.   const_iterator previous(const_iterator __pos) const {
  410.     return const_iterator((_Node*) __slist_previous(&this->_M_head,
  411.                                                     __pos._M_node));
  412.   }
  413.  
  414. private:
  415.   _Node* _M_insert_after(_Node_base* __pos, const value_type& __x) {
  416.     return (_Node*) (__slist_make_link(__pos, _M_create_node(__x)));
  417.   }
  418.  
  419.   _Node* _M_insert_after(_Node_base* __pos) {
  420.     return (_Node*) (__slist_make_link(__pos, _M_create_node()));
  421.   }
  422.  
  423.   void _M_insert_after_fill(_Node_base* __pos,
  424.                             size_type __n, const value_type& __x) {
  425.     for (size_type __i = 0; __i < __n; ++__i)
  426.       __pos = __slist_make_link(__pos, _M_create_node(__x));
  427.   }
  428.  
  429.   // Check whether it's an integral type.  If so, it's not an iterator.
  430.   template <class _InIterator>
  431.   void _M_insert_after_range(_Node_base* __pos,
  432.                              _InIterator __first, _InIterator __last) {
  433.     typedef typename _Is_integer<_InIterator>::_Integral _Integral;
  434.     _M_insert_after_range(__pos, __first, __last, _Integral());
  435.   }
  436.  
  437.   template <class _Integer>
  438.   void _M_insert_after_range(_Node_base* __pos, _Integer __n, _Integer __x,
  439.                              __true_type) {
  440.     _M_insert_after_fill(__pos, __n, __x);
  441.   }
  442.  
  443.   template <class _InIterator>
  444.   void _M_insert_after_range(_Node_base* __pos,
  445.                              _InIterator __first, _InIterator __last,
  446.                              __false_type) {
  447.     while (__first != __last) {
  448.       __pos = __slist_make_link(__pos, _M_create_node(*__first));
  449.       ++__first;
  450.     }
  451.   }
  452.  
  453. public:
  454.  
  455.   iterator insert_after(iterator __pos, const value_type& __x) {
  456.     return iterator(_M_insert_after(__pos._M_node, __x));
  457.   }
  458.  
  459.   iterator insert_after(iterator __pos) {
  460.     return insert_after(__pos, value_type());
  461.   }
  462.  
  463.   void insert_after(iterator __pos, size_type __n, const value_type& __x) {
  464.     _M_insert_after_fill(__pos._M_node, __n, __x);
  465.   }
  466.  
  467.   // We don't need any dispatching tricks here, because _M_insert_after_range
  468.   // already does them.
  469.   template <class _InIterator>
  470.   void insert_after(iterator __pos, _InIterator __first, _InIterator __last) {
  471.     _M_insert_after_range(__pos._M_node, __first, __last);
  472.   }
  473.  
  474.   iterator insert(iterator __pos, const value_type& __x) {
  475.     return iterator(_M_insert_after(__slist_previous(&this->_M_head,
  476.                                                      __pos._M_node),
  477.                     __x));
  478.   }
  479.  
  480.   iterator insert(iterator __pos) {
  481.     return iterator(_M_insert_after(__slist_previous(&this->_M_head,
  482.                                                      __pos._M_node),
  483.                                     value_type()));
  484.   }
  485.  
  486.   void insert(iterator __pos, size_type __n, const value_type& __x) {
  487.     _M_insert_after_fill(__slist_previous(&this->_M_head, __pos._M_node),
  488.                          __n, __x);
  489.   }
  490.  
  491.   // We don't need any dispatching tricks here, because _M_insert_after_range
  492.   // already does them.
  493.   template <class _InIterator>
  494.   void insert(iterator __pos, _InIterator __first, _InIterator __last) {
  495.     _M_insert_after_range(__slist_previous(&this->_M_head, __pos._M_node),
  496.                           __first, __last);
  497.   }
  498.  
  499. public:
  500.   iterator erase_after(iterator __pos) {
  501.     return iterator((_Node*) this->_M_erase_after(__pos._M_node));
  502.   }
  503.   iterator erase_after(iterator __before_first, iterator __last) {
  504.     return iterator((_Node*) this->_M_erase_after(__before_first._M_node,
  505.                                                   __last._M_node));
  506.   }
  507.  
  508.   iterator erase(iterator __pos) {
  509.     return (_Node*) this->_M_erase_after(__slist_previous(&this->_M_head,
  510.                                                           __pos._M_node));
  511.   }
  512.   iterator erase(iterator __first, iterator __last) {
  513.     return (_Node*) this->_M_erase_after(
  514.       __slist_previous(&this->_M_head, __first._M_node), __last._M_node);
  515.   }
  516.  
  517.   void resize(size_type new_size, const _Tp& __x);
  518.   void resize(size_type new_size) { resize(new_size, _Tp()); }
  519.   void clear() { this->_M_erase_after(&this->_M_head, 0); }
  520.  
  521. public:
  522.   // Moves the range [__before_first + 1, __before_last + 1) to *this,
  523.   //  inserting it immediately after __pos.  This is constant time.
  524.   void splice_after(iterator __pos,
  525.                     iterator __before_first, iterator __before_last)
  526.   {
  527.     if (__before_first != __before_last)
  528.       __slist_splice_after(__pos._M_node, __before_first._M_node,
  529.                            __before_last._M_node);
  530.   }
  531.  
  532.   // Moves the element that follows __prev to *this, inserting it immediately
  533.   //  after __pos.  This is constant time.
  534.   void splice_after(iterator __pos, iterator __prev)
  535.   {
  536.     __slist_splice_after(__pos._M_node,
  537.                          __prev._M_node, __prev._M_node->_M_next);
  538.   }
  539.  
  540.  
  541.   // Removes all of the elements from the list __x to *this, inserting
  542.   // them immediately after __pos.  __x must not be *this.  Complexity:
  543.   // linear in __x.size().
  544.   void splice_after(iterator __pos, slist& __x)
  545.   {
  546.     __slist_splice_after(__pos._M_node, &__x._M_head);
  547.   }
  548.  
  549.   // Linear in distance(begin(), __pos), and linear in __x.size().
  550.   void splice(iterator __pos, slist& __x) {
  551.     if (__x._M_head._M_next)
  552.       __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node),
  553.                            &__x._M_head, __slist_previous(&__x._M_head, 0));
  554.   }
  555.  
  556.   // Linear in distance(begin(), __pos), and in distance(__x.begin(), __i).
  557.   void splice(iterator __pos, slist& __x, iterator __i) {
  558.     __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node),
  559.                          __slist_previous(&__x._M_head, __i._M_node),
  560.                          __i._M_node);
  561.   }
  562.  
  563.   // Linear in distance(begin(), __pos), in distance(__x.begin(), __first),
  564.   // and in distance(__first, __last).
  565.   void splice(iterator __pos, slist& __x, iterator __first, iterator __last)
  566.   {
  567.     if (__first != __last)
  568.       __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node),
  569.                            __slist_previous(&__x._M_head, __first._M_node),
  570.                            __slist_previous(__first._M_node, __last._M_node));
  571.   }
  572.  
  573. public:
  574.   void reverse() {
  575.     if (this->_M_head._M_next)
  576.       this->_M_head._M_next = __slist_reverse(this->_M_head._M_next);
  577.   }
  578.  
  579.   void remove(const _Tp& __val);
  580.   void unique();
  581.   void merge(slist& __x);
  582.   void sort();
  583.  
  584.   template <class _Predicate>
  585.   void remove_if(_Predicate __pred);
  586.  
  587.   template <class _BinaryPredicate>
  588.   void unique(_BinaryPredicate __pred);
  589.  
  590.   template <class _StrictWeakOrdering>
  591.   void merge(slist&, _StrictWeakOrdering);
  592.  
  593.   template <class _StrictWeakOrdering>
  594.   void sort(_StrictWeakOrdering __comp);
  595. };
  596.  
  597. template <class _Tp, class _Alloc>
  598. slist<_Tp,_Alloc>& slist<_Tp,_Alloc>::operator=(const slist<_Tp,_Alloc>& __x)
  599. {
  600.   if (&__x != this) {
  601.     _Node_base* __p1 = &this->_M_head;
  602.     _Node* __n1 = (_Node*) this->_M_head._M_next;
  603.     const _Node* __n2 = (const _Node*) __x._M_head._M_next;
  604.     while (__n1 && __n2) {
  605.       __n1->_M_data = __n2->_M_data;
  606.       __p1 = __n1;
  607.       __n1 = (_Node*) __n1->_M_next;
  608.       __n2 = (const _Node*) __n2->_M_next;
  609.     }
  610.     if (__n2 == 0)
  611.       this->_M_erase_after(__p1, 0);
  612.     else
  613.       _M_insert_after_range(__p1, const_iterator((_Node*)__n2),
  614.                                   const_iterator(0));
  615.   }
  616.   return *this;
  617. }
  618.  
  619. template <class _Tp, class _Alloc>
  620. void slist<_Tp, _Alloc>::_M_fill_assign(size_type __n, const _Tp& __val) {
  621.   _Node_base* __prev = &this->_M_head;
  622.   _Node* __node = (_Node*) this->_M_head._M_next;
  623.   for ( ; __node != 0 && __n > 0 ; --__n) {
  624.     __node->_M_data = __val;
  625.     __prev = __node;
  626.     __node = (_Node*) __node->_M_next;
  627.   }
  628.   if (__n > 0)
  629.     _M_insert_after_fill(__prev, __n, __val);
  630.   else
  631.     this->_M_erase_after(__prev, 0);
  632. }
  633.  
  634. template <class _Tp, class _Alloc> template <class _InputIterator>
  635. void
  636. slist<_Tp, _Alloc>::_M_assign_dispatch(_InputIterator __first, _InputIterator __last,
  637.                                        __false_type)
  638. {
  639.   _Node_base* __prev = &this->_M_head;
  640.   _Node* __node = (_Node*) this->_M_head._M_next;
  641.   while (__node != 0 && __first != __last) {
  642.     __node->_M_data = *__first;
  643.     __prev = __node;
  644.     __node = (_Node*) __node->_M_next;
  645.     ++__first;
  646.   }
  647.   if (__first != __last)
  648.     _M_insert_after_range(__prev, __first, __last);
  649.   else
  650.     this->_M_erase_after(__prev, 0);
  651. }
  652.  
  653. template <class _Tp, class _Alloc>
  654. inline bool
  655. operator==(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2)
  656. {
  657.   typedef typename slist<_Tp,_Alloc>::const_iterator const_iterator;
  658.   const_iterator __end1 = _SL1.end();
  659.   const_iterator __end2 = _SL2.end();
  660.  
  661.   const_iterator __i1 = _SL1.begin();
  662.   const_iterator __i2 = _SL2.begin();
  663.   while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) {
  664.     ++__i1;
  665.     ++__i2;
  666.   }
  667.   return __i1 == __end1 && __i2 == __end2;
  668. }
  669.  
  670.  
  671. template <class _Tp, class _Alloc>
  672. inline bool
  673. operator<(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2)
  674. {
  675.   return std::lexicographical_compare(_SL1.begin(), _SL1.end(),
  676.                       _SL2.begin(), _SL2.end());
  677. }
  678.  
  679. template <class _Tp, class _Alloc>
  680. inline bool
  681. operator!=(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) {
  682.   return !(_SL1 == _SL2);
  683. }
  684.  
  685. template <class _Tp, class _Alloc>
  686. inline bool
  687. operator>(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) {
  688.   return _SL2 < _SL1;
  689. }
  690.  
  691. template <class _Tp, class _Alloc>
  692. inline bool
  693. operator<=(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) {
  694.   return !(_SL2 < _SL1);
  695. }
  696.  
  697. template <class _Tp, class _Alloc>
  698. inline bool
  699. operator>=(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) {
  700.   return !(_SL1 < _SL2);
  701. }
  702.  
  703. template <class _Tp, class _Alloc>
  704. inline void swap(slist<_Tp,_Alloc>& __x, slist<_Tp,_Alloc>& __y) {
  705.   __x.swap(__y);
  706. }
  707.  
  708.  
  709. template <class _Tp, class _Alloc>
  710. void slist<_Tp,_Alloc>::resize(size_type __len, const _Tp& __x)
  711. {
  712.   _Node_base* __cur = &this->_M_head;
  713.   while (__cur->_M_next != 0 && __len > 0) {
  714.     --__len;
  715.     __cur = __cur->_M_next;
  716.   }
  717.   if (__cur->_M_next)
  718.     this->_M_erase_after(__cur, 0);
  719.   else
  720.     _M_insert_after_fill(__cur, __len, __x);
  721. }
  722.  
  723. template <class _Tp, class _Alloc>
  724. void slist<_Tp,_Alloc>::remove(const _Tp& __val)
  725. {
  726.   _Node_base* __cur = &this->_M_head;
  727.   while (__cur && __cur->_M_next) {
  728.     if (((_Node*) __cur->_M_next)->_M_data == __val)
  729.       this->_M_erase_after(__cur);
  730.     else
  731.       __cur = __cur->_M_next;
  732.   }
  733. }
  734.  
  735. template <class _Tp, class _Alloc>
  736. void slist<_Tp,_Alloc>::unique()
  737. {
  738.   _Node_base* __cur = this->_M_head._M_next;
  739.   if (__cur) {
  740.     while (__cur->_M_next) {
  741.       if (((_Node*)__cur)->_M_data ==
  742.           ((_Node*)(__cur->_M_next))->_M_data)
  743.         this->_M_erase_after(__cur);
  744.       else
  745.         __cur = __cur->_M_next;
  746.     }
  747.   }
  748. }
  749.  
  750. template <class _Tp, class _Alloc>
  751. void slist<_Tp,_Alloc>::merge(slist<_Tp,_Alloc>& __x)
  752. {
  753.   _Node_base* __n1 = &this->_M_head;
  754.   while (__n1->_M_next && __x._M_head._M_next) {
  755.     if (((_Node*) __x._M_head._M_next)->_M_data <
  756.         ((_Node*)       __n1->_M_next)->_M_data)
  757.       __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next);
  758.     __n1 = __n1->_M_next;
  759.   }
  760.   if (__x._M_head._M_next) {
  761.     __n1->_M_next = __x._M_head._M_next;
  762.     __x._M_head._M_next = 0;
  763.   }
  764. }
  765.  
  766. template <class _Tp, class _Alloc>
  767. void slist<_Tp,_Alloc>::sort()
  768. {
  769.   if (this->_M_head._M_next && this->_M_head._M_next->_M_next) {
  770.     slist __carry;
  771.     slist __counter[64];
  772.     int __fill = 0;
  773.     while (!empty()) {
  774.       __slist_splice_after(&__carry._M_head,
  775.                            &this->_M_head, this->_M_head._M_next);
  776.       int __i = 0;
  777.       while (__i < __fill && !__counter[__i].empty()) {
  778.         __counter[__i].merge(__carry);
  779.         __carry.swap(__counter[__i]);
  780.         ++__i;
  781.       }
  782.       __carry.swap(__counter[__i]);
  783.       if (__i == __fill)
  784.         ++__fill;
  785.     }
  786.  
  787.     for (int __i = 1; __i < __fill; ++__i)
  788.       __counter[__i].merge(__counter[__i-1]);
  789.     this->swap(__counter[__fill-1]);
  790.   }
  791. }
  792.  
  793. template <class _Tp, class _Alloc>
  794. template <class _Predicate>
  795. void slist<_Tp,_Alloc>::remove_if(_Predicate __pred)
  796. {
  797.   _Node_base* __cur = &this->_M_head;
  798.   while (__cur->_M_next) {
  799.     if (__pred(((_Node*) __cur->_M_next)->_M_data))
  800.       this->_M_erase_after(__cur);
  801.     else
  802.       __cur = __cur->_M_next;
  803.   }
  804. }
  805.  
  806. template <class _Tp, class _Alloc> template <class _BinaryPredicate>
  807. void slist<_Tp,_Alloc>::unique(_BinaryPredicate __pred)
  808. {
  809.   _Node* __cur = (_Node*) this->_M_head._M_next;
  810.   if (__cur) {
  811.     while (__cur->_M_next) {
  812.       if (__pred(((_Node*)__cur)->_M_data,
  813.                  ((_Node*)(__cur->_M_next))->_M_data))
  814.         this->_M_erase_after(__cur);
  815.       else
  816.         __cur = (_Node*) __cur->_M_next;
  817.     }
  818.   }
  819. }
  820.  
  821. template <class _Tp, class _Alloc> template <class _StrictWeakOrdering>
  822. void slist<_Tp,_Alloc>::merge(slist<_Tp,_Alloc>& __x,
  823.                               _StrictWeakOrdering __comp)
  824. {
  825.   _Node_base* __n1 = &this->_M_head;
  826.   while (__n1->_M_next && __x._M_head._M_next) {
  827.     if (__comp(((_Node*) __x._M_head._M_next)->_M_data,
  828.                ((_Node*)       __n1->_M_next)->_M_data))
  829.       __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next);
  830.     __n1 = __n1->_M_next;
  831.   }
  832.   if (__x._M_head._M_next) {
  833.     __n1->_M_next = __x._M_head._M_next;
  834.     __x._M_head._M_next = 0;
  835.   }
  836. }
  837.  
  838. template <class _Tp, class _Alloc> template <class _StrictWeakOrdering>
  839. void slist<_Tp,_Alloc>::sort(_StrictWeakOrdering __comp)
  840. {
  841.   if (this->_M_head._M_next && this->_M_head._M_next->_M_next) {
  842.     slist __carry;
  843.     slist __counter[64];
  844.     int __fill = 0;
  845.     while (!empty()) {
  846.       __slist_splice_after(&__carry._M_head,
  847.                            &this->_M_head, this->_M_head._M_next);
  848.       int __i = 0;
  849.       while (__i < __fill && !__counter[__i].empty()) {
  850.         __counter[__i].merge(__carry, __comp);
  851.         __carry.swap(__counter[__i]);
  852.         ++__i;
  853.       }
  854.       __carry.swap(__counter[__i]);
  855.       if (__i == __fill)
  856.         ++__fill;
  857.     }
  858.  
  859.     for (int __i = 1; __i < __fill; ++__i)
  860.       __counter[__i].merge(__counter[__i-1], __comp);
  861.     this->swap(__counter[__fill-1]);
  862.   }
  863. }
  864.  
  865. } // namespace __gnu_cxx
  866.  
  867. namespace std
  868. {
  869. // Specialization of insert_iterator so that insertions will be constant
  870. // time rather than linear time.
  871.  
  872. template <class _Tp, class _Alloc>
  873. class insert_iterator<__gnu_cxx::slist<_Tp, _Alloc> > {
  874. protected:
  875.   typedef __gnu_cxx::slist<_Tp, _Alloc> _Container;
  876.   _Container* container;
  877.   typename _Container::iterator iter;
  878. public:
  879.   typedef _Container          container_type;
  880.   typedef output_iterator_tag iterator_category;
  881.   typedef void                value_type;
  882.   typedef void                difference_type;
  883.   typedef void                pointer;
  884.   typedef void                reference;
  885.  
  886.   insert_iterator(_Container& __x, typename _Container::iterator __i)
  887.     : container(&__x) {
  888.     if (__i == __x.begin())
  889.       iter = __x.before_begin();
  890.     else
  891.       iter = __x.previous(__i);
  892.   }
  893.  
  894.   insert_iterator<_Container>&
  895.   operator=(const typename _Container::value_type& __value) {
  896.     iter = container->insert_after(iter, __value);
  897.     return *this;
  898.   }
  899.   insert_iterator<_Container>& operator*() { return *this; }
  900.   insert_iterator<_Container>& operator++() { return *this; }
  901.   insert_iterator<_Container>& operator++(int) { return *this; }
  902. };
  903.  
  904. } // namespace std
  905.  
  906. #endif
  907.