home *** CD-ROM | disk | FTP | other *** search
/ Beginning C++ Through Gam…rogramming (2nd Edition) / BCGP2E.ISO / bloodshed / devcpp-4.9.9.2_setup.exe / list.tcc < prev    next >
Text File  |  2005-01-29  |  11KB  |  378 lines
  1. // List implementation (out of line) -*- C++ -*-
  2.  
  3. // Copyright (C) 2001, 2002, 2003, 2004 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.  *
  32.  * Copyright (c) 1994
  33.  * Hewlett-Packard Company
  34.  *
  35.  * Permission to use, copy, modify, distribute and sell this software
  36.  * and its documentation for any purpose is hereby granted without fee,
  37.  * provided that the above copyright notice appear in all copies and
  38.  * that both that copyright notice and this permission notice appear
  39.  * in supporting documentation.  Hewlett-Packard Company makes no
  40.  * representations about the suitability of this software for any
  41.  * purpose.  It is provided "as is" without express or implied warranty.
  42.  *
  43.  *
  44.  * Copyright (c) 1996,1997
  45.  * Silicon Graphics Computer Systems, Inc.
  46.  *
  47.  * Permission to use, copy, modify, distribute and sell this software
  48.  * and its documentation for any purpose is hereby granted without fee,
  49.  * provided that the above copyright notice appear in all copies and
  50.  * that both that copyright notice and this permission notice appear
  51.  * in supporting documentation.  Silicon Graphics makes no
  52.  * representations about the suitability of this software for any
  53.  * purpose.  It is provided "as is" without express or implied warranty.
  54.  */
  55.  
  56. /** @file list.tcc
  57.  *  This is an internal header file, included by other library headers.
  58.  *  You should not attempt to use it directly.
  59.  */
  60.  
  61. #ifndef _LIST_TCC
  62. #define _LIST_TCC 1
  63.  
  64. namespace _GLIBCXX_STD
  65. {
  66.   template<typename _Tp, typename _Alloc>
  67.     void
  68.     _List_base<_Tp,_Alloc>::
  69.     _M_clear()
  70.     {
  71.       typedef _List_node<_Tp>  _Node;
  72.       _Node* __cur = static_cast<_Node*>(this->_M_impl._M_node._M_next);
  73.       while (__cur != &this->_M_impl._M_node)
  74.       {
  75.         _Node* __tmp = __cur;
  76.         __cur = static_cast<_Node*>(__cur->_M_next);
  77.         std::_Destroy(&__tmp->_M_data);
  78.         _M_put_node(__tmp);
  79.       }
  80.     }
  81.  
  82.   template<typename _Tp, typename _Alloc>
  83.     typename list<_Tp,_Alloc>::iterator
  84.     list<_Tp,_Alloc>::
  85.     insert(iterator __position, const value_type& __x)
  86.     {
  87.       _Node* __tmp = _M_create_node(__x);
  88.       __tmp->hook(__position._M_node);
  89.       return __tmp;
  90.     }
  91.  
  92.   template<typename _Tp, typename _Alloc>
  93.     typename list<_Tp,_Alloc>::iterator
  94.     list<_Tp,_Alloc>::
  95.     erase(iterator __position)
  96.     {
  97.       iterator __ret = __position._M_node->_M_next;
  98.       _M_erase(__position);
  99.       return __ret;
  100.     }
  101.  
  102.   template<typename _Tp, typename _Alloc>
  103.     void
  104.     list<_Tp,_Alloc>::
  105.     resize(size_type __new_size, const value_type& __x)
  106.     {
  107.       iterator __i = begin();
  108.       size_type __len = 0;
  109.       for ( ; __i != end() && __len < __new_size; ++__i, ++__len)
  110.         ;
  111.       if (__len == __new_size)
  112.         erase(__i, end());
  113.       else                          // __i == end()
  114.         insert(end(), __new_size - __len, __x);
  115.     }
  116.  
  117.   template<typename _Tp, typename _Alloc>
  118.     list<_Tp,_Alloc>&
  119.     list<_Tp,_Alloc>::
  120.     operator=(const list& __x)
  121.     {
  122.       if (this != &__x)
  123.     {
  124.       iterator __first1 = begin();
  125.       iterator __last1 = end();
  126.       const_iterator __first2 = __x.begin();
  127.       const_iterator __last2 = __x.end();
  128.       while (__first1 != __last1 && __first2 != __last2)
  129.         *__first1++ = *__first2++;
  130.       if (__first2 == __last2)
  131.         erase(__first1, __last1);
  132.       else
  133.         insert(__last1, __first2, __last2);
  134.     }
  135.       return *this;
  136.     }
  137.  
  138.   template<typename _Tp, typename _Alloc>
  139.     void
  140.     list<_Tp,_Alloc>::
  141.     _M_fill_assign(size_type __n, const value_type& __val)
  142.     {
  143.       iterator __i = begin();
  144.       for ( ; __i != end() && __n > 0; ++__i, --__n)
  145.         *__i = __val;
  146.       if (__n > 0)
  147.         insert(end(), __n, __val);
  148.       else
  149.         erase(__i, end());
  150.     }
  151.  
  152.   template<typename _Tp, typename _Alloc>
  153.     template <typename _InputIterator>
  154.       void
  155.       list<_Tp,_Alloc>::
  156.       _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
  157.              __false_type)
  158.       {
  159.         iterator __first1 = begin();
  160.         iterator __last1 = end();
  161.         for (; __first1 != __last1 && __first2 != __last2;
  162.          ++__first1, ++__first2)
  163.           *__first1 = *__first2;
  164.         if (__first2 == __last2)
  165.           erase(__first1, __last1);
  166.         else
  167.           insert(__last1, __first2, __last2);
  168.       }
  169.  
  170.   template<typename _Tp, typename _Alloc>
  171.     void
  172.     list<_Tp,_Alloc>::
  173.     remove(const value_type& __value)
  174.     {
  175.       iterator __first = begin();
  176.       iterator __last = end();
  177.       while (__first != __last)
  178.       {
  179.         iterator __next = __first;
  180.         ++__next;
  181.         if (*__first == __value)
  182.           _M_erase(__first);
  183.         __first = __next;
  184.       }
  185.     }
  186.  
  187.   template<typename _Tp, typename _Alloc>
  188.     void
  189.     list<_Tp,_Alloc>::
  190.     unique()
  191.     {
  192.       iterator __first = begin();
  193.       iterator __last = end();
  194.       if (__first == __last)
  195.     return;
  196.       iterator __next = __first;
  197.       while (++__next != __last)
  198.       {
  199.         if (*__first == *__next)
  200.           _M_erase(__next);
  201.         else
  202.           __first = __next;
  203.         __next = __first;
  204.       }
  205.     }
  206.  
  207.   template<typename _Tp, typename _Alloc>
  208.     void
  209.     list<_Tp,_Alloc>::
  210.     merge(list& __x)
  211.     {
  212.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  213.       // 300. list::merge() specification incomplete
  214.       if (this != &__x)
  215.     {
  216.       iterator __first1 = begin();
  217.       iterator __last1 = end();
  218.       iterator __first2 = __x.begin();
  219.       iterator __last2 = __x.end();
  220.       while (__first1 != __last1 && __first2 != __last2)
  221.         if (*__first2 < *__first1)
  222.           {
  223.         iterator __next = __first2;
  224.         _M_transfer(__first1, __first2, ++__next);
  225.         __first2 = __next;
  226.           }
  227.         else
  228.           ++__first1;
  229.       if (__first2 != __last2)
  230.         _M_transfer(__last1, __first2, __last2);
  231.     }
  232.     }
  233.  
  234.   template<typename _Tp, typename _Alloc>
  235.     void
  236.     list<_Tp,_Alloc>::
  237.     sort()
  238.     {
  239.       // Do nothing if the list has length 0 or 1.
  240.       if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
  241.       && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
  242.       {
  243.         list __carry;
  244.         list __tmp[64];
  245.         list * __fill = &__tmp[0];
  246.         list * __counter;
  247.  
  248.         do
  249.       {
  250.         __carry.splice(__carry.begin(), *this, begin());
  251.  
  252.         for(__counter = &__tmp[0];
  253.         (__counter != __fill) && !__counter->empty();
  254.         ++__counter)
  255.           {
  256.         __counter->merge(__carry);
  257.         __carry.swap(*__counter);
  258.           }
  259.         __carry.swap(*__counter);
  260.         if (__counter == __fill)
  261.           ++__fill;
  262.       }
  263.     while ( !empty() );
  264.  
  265.         for (__counter =  &__tmp[1]; __counter != __fill; ++__counter)
  266.           __counter->merge( *(__counter-1) );
  267.         swap( *(__fill-1) );
  268.       }
  269.     }
  270.  
  271.   template<typename _Tp, typename _Alloc>
  272.     template <typename _Predicate>
  273.       void
  274.       list<_Tp,_Alloc>::
  275.       remove_if(_Predicate __pred)
  276.       {
  277.         iterator __first = begin();
  278.         iterator __last = end();
  279.         while (__first != __last)
  280.         {
  281.           iterator __next = __first;
  282.           ++__next;
  283.           if (__pred(*__first))
  284.         _M_erase(__first);
  285.           __first = __next;
  286.         }
  287.       }
  288.  
  289.   template<typename _Tp, typename _Alloc>
  290.     template <typename _BinaryPredicate>
  291.       void
  292.       list<_Tp,_Alloc>::
  293.       unique(_BinaryPredicate __binary_pred)
  294.       {
  295.         iterator __first = begin();
  296.         iterator __last = end();
  297.         if (__first == __last) return;
  298.         iterator __next = __first;
  299.         while (++__next != __last)
  300.         {
  301.           if (__binary_pred(*__first, *__next))
  302.             _M_erase(__next);
  303.           else
  304.             __first = __next;
  305.           __next = __first;
  306.         }
  307.       }
  308.  
  309.   template<typename _Tp, typename _Alloc>
  310.     template <typename _StrictWeakOrdering>
  311.       void
  312.       list<_Tp,_Alloc>::
  313.       merge(list& __x, _StrictWeakOrdering __comp)
  314.       {
  315.     // _GLIBCXX_RESOLVE_LIB_DEFECTS
  316.     // 300. list::merge() specification incomplete
  317.     if (this != &__x)
  318.       {
  319.         iterator __first1 = begin();
  320.         iterator __last1 = end();
  321.         iterator __first2 = __x.begin();
  322.         iterator __last2 = __x.end();
  323.         while (__first1 != __last1 && __first2 != __last2)
  324.           if (__comp(*__first2, *__first1))
  325.         {
  326.           iterator __next = __first2;
  327.           _M_transfer(__first1, __first2, ++__next);
  328.           __first2 = __next;
  329.         }
  330.           else
  331.         ++__first1;
  332.         if (__first2 != __last2)
  333.           _M_transfer(__last1, __first2, __last2);
  334.       }
  335.       }
  336.  
  337.   template<typename _Tp, typename _Alloc>
  338.     template <typename _StrictWeakOrdering>
  339.       void
  340.       list<_Tp,_Alloc>::
  341.       sort(_StrictWeakOrdering __comp)
  342.       {
  343.     // Do nothing if the list has length 0 or 1.
  344.     if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
  345.         && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
  346.       {
  347.         list __carry;
  348.         list __tmp[64];
  349.         list * __fill = &__tmp[0];
  350.         list * __counter;
  351.  
  352.         do
  353.           {
  354.         __carry.splice(__carry.begin(), *this, begin());
  355.  
  356.         for(__counter = &__tmp[0];
  357.             (__counter != __fill) && !__counter->empty();
  358.             ++__counter)
  359.           {
  360.             __counter->merge(__carry, __comp);
  361.             __carry.swap(*__counter);
  362.           }
  363.         __carry.swap(*__counter);
  364.         if (__counter == __fill)
  365.           ++__fill;
  366.           }
  367.         while ( !empty() );
  368.  
  369.         for (__counter =  &__tmp[1]; __counter != __fill; ++__counter)
  370.           __counter->merge( *(__counter-1), __comp );
  371.         swap( *(__fill-1) );
  372.       }
  373.       }
  374. } // namespace std
  375.  
  376. #endif /* _LIST_TCC */
  377.  
  378.