list.tcc

Go to the documentation of this file.
00001 // List implementation (out of line) -*- C++ -*-
00002 
00003 // Copyright (C) 2001, 2002 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 2, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // You should have received a copy of the GNU General Public License along
00017 // with this library; see the file COPYING.  If not, write to the Free
00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
00019 // USA.
00020 
00021 // As a special exception, you may use this file as part of a free software
00022 // library without restriction.  Specifically, if other files instantiate
00023 // templates or use macros or inline functions from this file, or you compile
00024 // this file and link it with other files to produce an executable, this
00025 // file does not by itself cause the resulting executable to be covered by
00026 // the GNU General Public License.  This exception does not however
00027 // invalidate any other reasons why the executable file might be covered by
00028 // the GNU General Public License.
00029 
00030 /*
00031  *
00032  * Copyright (c) 1994
00033  * Hewlett-Packard Company
00034  *
00035  * Permission to use, copy, modify, distribute and sell this software
00036  * and its documentation for any purpose is hereby granted without fee,
00037  * provided that the above copyright notice appear in all copies and
00038  * that both that copyright notice and this permission notice appear
00039  * in supporting documentation.  Hewlett-Packard Company makes no
00040  * representations about the suitability of this software for any
00041  * purpose.  It is provided "as is" without express or implied warranty.
00042  *
00043  *
00044  * Copyright (c) 1996,1997
00045  * Silicon Graphics Computer Systems, Inc.
00046  *
00047  * Permission to use, copy, modify, distribute and sell this software
00048  * and its documentation for any purpose is hereby granted without fee,
00049  * provided that the above copyright notice appear in all copies and
00050  * that both that copyright notice and this permission notice appear
00051  * in supporting documentation.  Silicon Graphics makes no
00052  * representations about the suitability of this software for any
00053  * purpose.  It is provided "as is" without express or implied warranty.
00054  */
00055 
00056 /** @file list.tcc
00057  *  This is an internal header file, included by other library headers.
00058  *  You should not attempt to use it directly.
00059  */
00060 
00061 #ifndef __GLIBCPP_INTERNAL_LIST_TCC
00062 #define __GLIBCPP_INTERNAL_LIST_TCC
00063 
00064 namespace std
00065 {
00066   template<typename _Tp, typename _Alloc>
00067     void
00068     _List_base<_Tp,_Alloc>::
00069     __clear()
00070     {
00071       typedef _List_node<_Tp>  _Node;
00072       _Node* __cur = static_cast<_Node*>(_M_node->_M_next);
00073       while (__cur != _M_node)
00074       {
00075         _Node* __tmp = __cur;
00076         __cur = static_cast<_Node*>(__cur->_M_next);
00077         _Destroy(&__tmp->_M_data);
00078         _M_put_node(__tmp);
00079       }
00080       _M_node->_M_next = _M_node;
00081       _M_node->_M_prev = _M_node;
00082     }
00083   
00084   template<typename _Tp, typename _Alloc>
00085     typename list<_Tp,_Alloc>::iterator
00086     list<_Tp,_Alloc>::
00087     insert(iterator __position, const value_type& __x)
00088     {
00089       _Node* __tmp = _M_create_node(__x);
00090       __tmp->_M_next = __position._M_node;
00091       __tmp->_M_prev = __position._M_node->_M_prev;
00092       __position._M_node->_M_prev->_M_next = __tmp;
00093       __position._M_node->_M_prev = __tmp;
00094       return __tmp;
00095     }
00096   
00097   template<typename _Tp, typename _Alloc>
00098     typename list<_Tp,_Alloc>::iterator
00099     list<_Tp,_Alloc>::
00100     erase(iterator __position)
00101     {
00102       _List_node_base* __next_node = __position._M_node->_M_next;
00103       _List_node_base* __prev_node = __position._M_node->_M_prev;
00104       _Node* __n = static_cast<_Node*>(__position._M_node);
00105       __prev_node->_M_next = __next_node;
00106       __next_node->_M_prev = __prev_node;
00107       _Destroy(&__n->_M_data);
00108       _M_put_node(__n);
00109       return iterator(static_cast<_Node*>(__next_node));
00110     }
00111   
00112   template<typename _Tp, typename _Alloc>
00113     void
00114     list<_Tp,_Alloc>::
00115     resize(size_type __new_size, const value_type& __x)
00116     {
00117       iterator __i = begin();
00118       size_type __len = 0;
00119       for ( ; __i != end() && __len < __new_size; ++__i, ++__len)
00120         ;
00121       if (__len == __new_size)
00122         erase(__i, end());
00123       else                          // __i == end()
00124         insert(end(), __new_size - __len, __x);
00125     }
00126   
00127   template<typename _Tp, typename _Alloc>
00128     list<_Tp,_Alloc>&
00129     list<_Tp,_Alloc>::
00130     operator=(const list& __x)
00131     {
00132       if (this != &__x)
00133       {
00134         iterator __first1 = begin();
00135         iterator __last1 = end();
00136         const_iterator __first2 = __x.begin();
00137         const_iterator __last2 = __x.end();
00138         while (__first1 != __last1 && __first2 != __last2)
00139           *__first1++ = *__first2++;
00140         if (__first2 == __last2)
00141           erase(__first1, __last1);
00142         else
00143           insert(__last1, __first2, __last2);
00144       }
00145       return *this;
00146     }
00147   
00148   template<typename _Tp, typename _Alloc>
00149     void
00150     list<_Tp,_Alloc>::
00151     _M_fill_assign(size_type __n, const value_type& __val)
00152     {
00153       iterator __i = begin();
00154       for ( ; __i != end() && __n > 0; ++__i, --__n)
00155         *__i = __val;
00156       if (__n > 0)
00157         insert(end(), __n, __val);
00158       else
00159         erase(__i, end());
00160     }
00161   
00162   template<typename _Tp, typename _Alloc>
00163     template <typename _InputIter>
00164       void
00165       list<_Tp,_Alloc>::
00166       _M_assign_dispatch(_InputIter __first2, _InputIter __last2, __false_type)
00167       {
00168         iterator __first1 = begin();
00169         iterator __last1 = end();
00170         for (; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2)
00171           *__first1 = *__first2;
00172         if (__first2 == __last2)
00173           erase(__first1, __last1);
00174         else
00175           insert(__last1, __first2, __last2);
00176       }
00177   
00178   template<typename _Tp, typename _Alloc>
00179     void
00180     list<_Tp,_Alloc>::
00181     remove(const value_type& __value)
00182     {
00183       iterator __first = begin();
00184       iterator __last = end();
00185       while (__first != __last)
00186       {
00187         iterator __next = __first;
00188         ++__next;
00189         if (*__first == __value)
00190           erase(__first);
00191         __first = __next;
00192       }
00193     }
00194   
00195   template<typename _Tp, typename _Alloc>
00196     void
00197     list<_Tp,_Alloc>::
00198     unique()
00199     {
00200       iterator __first = begin();
00201       iterator __last = end();
00202       if (__first == __last) return;
00203       iterator __next = __first;
00204       while (++__next != __last)
00205       {
00206         if (*__first == *__next)
00207           erase(__next);
00208         else
00209           __first = __next;
00210         __next = __first;
00211       }
00212     }
00213   
00214   template<typename _Tp, typename _Alloc>
00215     void
00216     list<_Tp,_Alloc>::
00217     merge(list& __x)
00218     {
00219       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00220       // 300. list::merge() specification incomplete    
00221       if (this != &__x)
00222     {
00223       iterator __first1 = begin();
00224       iterator __last1 = end();
00225       iterator __first2 = __x.begin();
00226       iterator __last2 = __x.end();
00227       while (__first1 != __last1 && __first2 != __last2)
00228         if (*__first2 < *__first1)
00229           {
00230         iterator __next = __first2;
00231         _M_transfer(__first1, __first2, ++__next);
00232         __first2 = __next;
00233           }
00234         else
00235           ++__first1;
00236       if (__first2 != __last2)
00237         _M_transfer(__last1, __first2, __last2);
00238     }
00239     }
00240   
00241   // FIXME put this somewhere else
00242   inline void
00243   __List_base_reverse(_List_node_base* __p)
00244   {
00245     _List_node_base* __tmp = __p;
00246     do {
00247       std::swap(__tmp->_M_next, __tmp->_M_prev);
00248       __tmp = __tmp->_M_prev;     // Old next node is now prev.
00249     } while (__tmp != __p);
00250   }
00251   
00252   template<typename _Tp, typename _Alloc>
00253     void
00254     list<_Tp,_Alloc>::
00255     sort()
00256     {
00257       // Do nothing if the list has length 0 or 1.
00258       if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node)
00259       {
00260         list __carry;
00261         list __counter[64];
00262         int __fill = 0;
00263         while (!empty())
00264         {
00265           __carry.splice(__carry.begin(), *this, begin());
00266           int __i = 0;
00267           while(__i < __fill && !__counter[__i].empty())
00268           {
00269             __counter[__i].merge(__carry);
00270             __carry.swap(__counter[__i++]);
00271           }
00272           __carry.swap(__counter[__i]);
00273           if (__i == __fill) ++__fill;
00274         }
00275   
00276         for (int __i = 1; __i < __fill; ++__i)
00277           __counter[__i].merge(__counter[__i-1]);
00278         swap(__counter[__fill-1]);
00279       }
00280     }
00281   
00282   template<typename _Tp, typename _Alloc>
00283     template <typename _Predicate>
00284       void
00285       list<_Tp,_Alloc>::
00286       remove_if(_Predicate __pred)
00287       {
00288         iterator __first = begin();
00289         iterator __last = end();
00290         while (__first != __last)
00291         {
00292           iterator __next = __first;
00293           ++__next;
00294           if (__pred(*__first)) erase(__first);
00295           __first = __next;
00296         }
00297       }
00298   
00299   template<typename _Tp, typename _Alloc>
00300     template <typename _BinaryPredicate>
00301       void
00302       list<_Tp,_Alloc>::
00303       unique(_BinaryPredicate __binary_pred)
00304       {
00305         iterator __first = begin();
00306         iterator __last = end();
00307         if (__first == __last) return;
00308         iterator __next = __first;
00309         while (++__next != __last)
00310         {
00311           if (__binary_pred(*__first, *__next))
00312             erase(__next);
00313           else
00314             __first = __next;
00315           __next = __first;
00316         }
00317       }
00318   
00319   template<typename _Tp, typename _Alloc>
00320     template <typename _StrictWeakOrdering>
00321       void
00322       list<_Tp,_Alloc>::
00323       merge(list& __x, _StrictWeakOrdering __comp)
00324       {
00325     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00326     // 300. list::merge() specification incomplete
00327     if (this != &__x)
00328       { 
00329         iterator __first1 = begin();
00330         iterator __last1 = end();
00331         iterator __first2 = __x.begin();
00332         iterator __last2 = __x.end();
00333         while (__first1 != __last1 && __first2 != __last2)
00334           if (__comp(*__first2, *__first1))
00335         {
00336           iterator __next = __first2;
00337           _M_transfer(__first1, __first2, ++__next);
00338           __first2 = __next;
00339         }
00340           else
00341         ++__first1;
00342         if (__first2 != __last2) _M_transfer(__last1, __first2, __last2);
00343       }
00344       }
00345   
00346   template<typename _Tp, typename _Alloc>
00347     template <typename _StrictWeakOrdering>
00348     void
00349     list<_Tp,_Alloc>::
00350     sort(_StrictWeakOrdering __comp)
00351     {
00352       // Do nothing if the list has length 0 or 1.
00353       if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node)
00354       {
00355         list __carry;
00356         list __counter[64];
00357         int __fill = 0;
00358         while (!empty())
00359         {
00360           __carry.splice(__carry.begin(), *this, begin());
00361           int __i = 0;
00362           while(__i < __fill && !__counter[__i].empty())
00363           {
00364             __counter[__i].merge(__carry, __comp);
00365             __carry.swap(__counter[__i++]);
00366           }
00367           __carry.swap(__counter[__i]);
00368           if (__i == __fill) ++__fill;
00369         }
00370   
00371         for (int __i = 1; __i < __fill; ++__i)
00372           __counter[__i].merge(__counter[__i-1], __comp);
00373         swap(__counter[__fill-1]);
00374       }
00375     }
00376 } // namespace std
00377 
00378 #endif /* __GLIBCPP_INTERNAL_LIST_TCC */

Generated on Thu Feb 10 23:22:56 2005 for libstdc++-v3 Source by  doxygen 1.4.0