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       iterator __first1 = begin();
00220       iterator __last1 = end();
00221       iterator __first2 = __x.begin();
00222       iterator __last2 = __x.end();
00223       while (__first1 != __last1 && __first2 != __last2)
00224         if (*__first2 < *__first1)
00225         {
00226           iterator __next = __first2;
00227           _M_transfer(__first1, __first2, ++__next);
00228           __first2 = __next;
00229         }
00230         else
00231           ++__first1;
00232       if (__first2 != __last2)
00233         _M_transfer(__last1, __first2, __last2);
00234     }
00235   
00236   // FIXME put this somewhere else
00237   inline void
00238   __List_base_reverse(_List_node_base* __p)
00239   {
00240     _List_node_base* __tmp = __p;
00241     do {
00242       std::swap(__tmp->_M_next, __tmp->_M_prev);
00243       __tmp = __tmp->_M_prev;     // Old next node is now prev.
00244     } while (__tmp != __p);
00245   }
00246   
00247   template<typename _Tp, typename _Alloc>
00248     void
00249     list<_Tp,_Alloc>::
00250     sort()
00251     {
00252       // Do nothing if the list has length 0 or 1.
00253       if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node)
00254       {
00255         list __carry;
00256         list __counter[64];
00257         int __fill = 0;
00258         while (!empty())
00259         {
00260           __carry.splice(__carry.begin(), *this, begin());
00261           int __i = 0;
00262           while(__i < __fill && !__counter[__i].empty())
00263           {
00264             __counter[__i].merge(__carry);
00265             __carry.swap(__counter[__i++]);
00266           }
00267           __carry.swap(__counter[__i]);
00268           if (__i == __fill) ++__fill;
00269         }
00270   
00271         for (int __i = 1; __i < __fill; ++__i)
00272           __counter[__i].merge(__counter[__i-1]);
00273         swap(__counter[__fill-1]);
00274       }
00275     }
00276   
00277   template<typename _Tp, typename _Alloc>
00278     template <typename _Predicate>
00279       void
00280       list<_Tp,_Alloc>::
00281       remove_if(_Predicate __pred)
00282       {
00283         iterator __first = begin();
00284         iterator __last = end();
00285         while (__first != __last)
00286         {
00287           iterator __next = __first;
00288           ++__next;
00289           if (__pred(*__first)) erase(__first);
00290           __first = __next;
00291         }
00292       }
00293   
00294   template<typename _Tp, typename _Alloc>
00295     template <typename _BinaryPredicate>
00296       void
00297       list<_Tp,_Alloc>::
00298       unique(_BinaryPredicate __binary_pred)
00299       {
00300         iterator __first = begin();
00301         iterator __last = end();
00302         if (__first == __last) return;
00303         iterator __next = __first;
00304         while (++__next != __last)
00305         {
00306           if (__binary_pred(*__first, *__next))
00307             erase(__next);
00308           else
00309             __first = __next;
00310           __next = __first;
00311         }
00312       }
00313   
00314   template<typename _Tp, typename _Alloc>
00315     template <typename _StrictWeakOrdering>
00316       void
00317       list<_Tp,_Alloc>::
00318       merge(list& __x, _StrictWeakOrdering __comp)
00319       {
00320         iterator __first1 = begin();
00321         iterator __last1 = end();
00322         iterator __first2 = __x.begin();
00323         iterator __last2 = __x.end();
00324         while (__first1 != __last1 && __first2 != __last2)
00325           if (__comp(*__first2, *__first1))
00326           {
00327             iterator __next = __first2;
00328             _M_transfer(__first1, __first2, ++__next);
00329             __first2 = __next;
00330           }
00331           else
00332             ++__first1;
00333         if (__first2 != __last2) _M_transfer(__last1, __first2, __last2);
00334       }
00335   
00336   template<typename _Tp, typename _Alloc>
00337     template <typename _StrictWeakOrdering>
00338     void
00339     list<_Tp,_Alloc>::
00340     sort(_StrictWeakOrdering __comp)
00341     {
00342       // Do nothing if the list has length 0 or 1.
00343       if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node)
00344       {
00345         list __carry;
00346         list __counter[64];
00347         int __fill = 0;
00348         while (!empty())
00349         {
00350           __carry.splice(__carry.begin(), *this, begin());
00351           int __i = 0;
00352           while(__i < __fill && !__counter[__i].empty())
00353           {
00354             __counter[__i].merge(__carry, __comp);
00355             __carry.swap(__counter[__i++]);
00356           }
00357           __carry.swap(__counter[__i]);
00358           if (__i == __fill) ++__fill;
00359         }
00360   
00361         for (int __i = 1; __i < __fill; ++__i)
00362           __counter[__i].merge(__counter[__i-1], __comp);
00363         swap(__counter[__fill-1]);
00364       }
00365     }
00366 } // namespace std
00367 
00368 #endif /* __GLIBCPP_INTERNAL_LIST_TCC */

Generated on Sat Jan 10 15:26:31 2004 for libstdc++-v3 Source by doxygen 1.3.4