1// List implementation (out of line) -*- C++ -*-
2
3// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006
4// Free Software Foundation, Inc.
5//
6// This file is part of the GNU ISO C++ Library.  This library is free
7// software; you can redistribute it and/or modify it under the
8// terms of the GNU General Public License as published by the
9// Free Software Foundation; either version 2, or (at your option)
10// any later version.
11
12// This library is distributed in the hope that it will be useful,
13// but WITHOUT ANY WARRANTY; without even the implied warranty of
14// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15// GNU General Public License for more details.
16
17// You should have received a copy of the GNU General Public License along
18// with this library; see the file COPYING.  If not, write to the Free
19// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
20// USA.
21
22// As a special exception, you may use this file as part of a free software
23// library without restriction.  Specifically, if other files instantiate
24// templates or use macros or inline functions from this file, or you compile
25// this file and link it with other files to produce an executable, this
26// file does not by itself cause the resulting executable to be covered by
27// the GNU General Public License.  This exception does not however
28// invalidate any other reasons why the executable file might be covered by
29// the GNU General Public License.
30
31/*
32 *
33 * Copyright (c) 1994
34 * Hewlett-Packard Company
35 *
36 * Permission to use, copy, modify, distribute and sell this software
37 * and its documentation for any purpose is hereby granted without fee,
38 * provided that the above copyright notice appear in all copies and
39 * that both that copyright notice and this permission notice appear
40 * in supporting documentation.  Hewlett-Packard Company makes no
41 * representations about the suitability of this software for any
42 * purpose.  It is provided "as is" without express or implied warranty.
43 *
44 *
45 * Copyright (c) 1996,1997
46 * Silicon Graphics Computer Systems, Inc.
47 *
48 * Permission to use, copy, modify, distribute and sell this software
49 * and its documentation for any purpose is hereby granted without fee,
50 * provided that the above copyright notice appear in all copies and
51 * that both that copyright notice and this permission notice appear
52 * in supporting documentation.  Silicon Graphics makes no
53 * representations about the suitability of this software for any
54 * purpose.  It is provided "as is" without express or implied warranty.
55 */
56
57/** @file list.tcc
58 *  This is an internal header file, included by other library headers.
59 *  You should not attempt to use it directly.
60 */
61
62#ifndef _LIST_TCC
63#define _LIST_TCC 1
64
65_GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD)
66
67  template<typename _Tp, typename _Alloc>
68    void
69    _List_base<_Tp, _Alloc>::
70    _M_clear()
71    {
72      typedef _List_node<_Tp>  _Node;
73      _Node* __cur = static_cast<_Node*>(this->_M_impl._M_node._M_next);
74      while (__cur != &this->_M_impl._M_node)
75	{
76	  _Node* __tmp = __cur;
77	  __cur = static_cast<_Node*>(__cur->_M_next);
78	  _M_get_Tp_allocator().destroy(&__tmp->_M_data);
79	  _M_put_node(__tmp);
80	}
81    }
82
83  template<typename _Tp, typename _Alloc>
84    typename list<_Tp, _Alloc>::iterator
85    list<_Tp, _Alloc>::
86    insert(iterator __position, const value_type& __x)
87    {
88      _Node* __tmp = _M_create_node(__x);
89      __tmp->hook(__position._M_node);
90      return iterator(__tmp);
91    }
92
93  template<typename _Tp, typename _Alloc>
94    typename list<_Tp, _Alloc>::iterator
95    list<_Tp, _Alloc>::
96    erase(iterator __position)
97    {
98      iterator __ret = iterator(__position._M_node->_M_next);
99      _M_erase(__position);
100      return __ret;
101    }
102
103  template<typename _Tp, typename _Alloc>
104    void
105    list<_Tp, _Alloc>::
106    resize(size_type __new_size, value_type __x)
107    {
108      iterator __i = begin();
109      size_type __len = 0;
110      for (; __i != end() && __len < __new_size; ++__i, ++__len)
111        ;
112      if (__len == __new_size)
113        erase(__i, end());
114      else                          // __i == end()
115        insert(end(), __new_size - __len, __x);
116    }
117
118  template<typename _Tp, typename _Alloc>
119    list<_Tp, _Alloc>&
120    list<_Tp, _Alloc>::
121    operator=(const list& __x)
122    {
123      if (this != &__x)
124	{
125	  iterator __first1 = begin();
126	  iterator __last1 = end();
127	  const_iterator __first2 = __x.begin();
128	  const_iterator __last2 = __x.end();
129	  for (; __first1 != __last1 && __first2 != __last2;
130	       ++__first1, ++__first2)
131	    *__first1 = *__first2;
132	  if (__first2 == __last2)
133	    erase(__first1, __last1);
134	  else
135	    insert(__last1, __first2, __last2);
136	}
137      return *this;
138    }
139
140  template<typename _Tp, typename _Alloc>
141    void
142    list<_Tp, _Alloc>::
143    _M_fill_assign(size_type __n, const value_type& __val)
144    {
145      iterator __i = begin();
146      for (; __i != end() && __n > 0; ++__i, --__n)
147        *__i = __val;
148      if (__n > 0)
149        insert(end(), __n, __val);
150      else
151        erase(__i, end());
152    }
153
154  template<typename _Tp, typename _Alloc>
155    template <typename _InputIterator>
156      void
157      list<_Tp, _Alloc>::
158      _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
159			 __false_type)
160      {
161        iterator __first1 = begin();
162        iterator __last1 = end();
163        for (; __first1 != __last1 && __first2 != __last2;
164	     ++__first1, ++__first2)
165          *__first1 = *__first2;
166        if (__first2 == __last2)
167          erase(__first1, __last1);
168        else
169          insert(__last1, __first2, __last2);
170      }
171
172  template<typename _Tp, typename _Alloc>
173    void
174    list<_Tp, _Alloc>::
175    remove(const value_type& __value)
176    {
177      iterator __first = begin();
178      iterator __last = end();
179      while (__first != __last)
180	{
181	  iterator __next = __first;
182	  ++__next;
183	  if (*__first == __value)
184	    _M_erase(__first);
185	  __first = __next;
186	}
187    }
188
189  template<typename _Tp, typename _Alloc>
190    void
191    list<_Tp, _Alloc>::
192    unique()
193    {
194      iterator __first = begin();
195      iterator __last = end();
196      if (__first == __last)
197	return;
198      iterator __next = __first;
199      while (++__next != __last)
200	{
201	  if (*__first == *__next)
202	    _M_erase(__next);
203	  else
204	    __first = __next;
205	  __next = __first;
206	}
207    }
208
209  template<typename _Tp, typename _Alloc>
210    void
211    list<_Tp, _Alloc>::
212    merge(list& __x)
213    {
214      // _GLIBCXX_RESOLVE_LIB_DEFECTS
215      // 300. list::merge() specification incomplete
216      if (this != &__x)
217	{
218	  _M_check_equal_allocators(__x); 
219
220	  iterator __first1 = begin();
221	  iterator __last1 = end();
222	  iterator __first2 = __x.begin();
223	  iterator __last2 = __x.end();
224	  while (__first1 != __last1 && __first2 != __last2)
225	    if (*__first2 < *__first1)
226	      {
227		iterator __next = __first2;
228		_M_transfer(__first1, __first2, ++__next);
229		__first2 = __next;
230	      }
231	    else
232	      ++__first1;
233	  if (__first2 != __last2)
234	    _M_transfer(__last1, __first2, __last2);
235	}
236    }
237
238  template<typename _Tp, typename _Alloc>
239    template <typename _StrictWeakOrdering>
240      void
241      list<_Tp, _Alloc>::
242      merge(list& __x, _StrictWeakOrdering __comp)
243      {
244	// _GLIBCXX_RESOLVE_LIB_DEFECTS
245	// 300. list::merge() specification incomplete
246	if (this != &__x)
247	  {
248	    _M_check_equal_allocators(__x);
249
250	    iterator __first1 = begin();
251	    iterator __last1 = end();
252	    iterator __first2 = __x.begin();
253	    iterator __last2 = __x.end();
254	    while (__first1 != __last1 && __first2 != __last2)
255	      if (__comp(*__first2, *__first1))
256		{
257		  iterator __next = __first2;
258		  _M_transfer(__first1, __first2, ++__next);
259		  __first2 = __next;
260		}
261	      else
262		++__first1;
263	    if (__first2 != __last2)
264	      _M_transfer(__last1, __first2, __last2);
265	  }
266      }
267
268  template<typename _Tp, typename _Alloc>
269    void
270    list<_Tp, _Alloc>::
271    sort()
272    {
273      // Do nothing if the list has length 0 or 1.
274      if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
275	  && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
276      {
277        list __carry;
278        list __tmp[64];
279        list * __fill = &__tmp[0];
280        list * __counter;
281
282        do
283	  {
284	    __carry.splice(__carry.begin(), *this, begin());
285
286	    for(__counter = &__tmp[0];
287		__counter != __fill && !__counter->empty();
288		++__counter)
289	      {
290		__counter->merge(__carry);
291		__carry.swap(*__counter);
292	      }
293	    __carry.swap(*__counter);
294	    if (__counter == __fill)
295	      ++__fill;
296	  }
297	while ( !empty() );
298
299        for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
300          __counter->merge(*(__counter - 1));
301        swap( *(__fill - 1) );
302      }
303    }
304
305  template<typename _Tp, typename _Alloc>
306    template <typename _Predicate>
307      void
308      list<_Tp, _Alloc>::
309      remove_if(_Predicate __pred)
310      {
311        iterator __first = begin();
312        iterator __last = end();
313        while (__first != __last)
314	  {
315	    iterator __next = __first;
316	    ++__next;
317	    if (__pred(*__first))
318	      _M_erase(__first);
319	    __first = __next;
320	  }
321      }
322
323  template<typename _Tp, typename _Alloc>
324    template <typename _BinaryPredicate>
325      void
326      list<_Tp, _Alloc>::
327      unique(_BinaryPredicate __binary_pred)
328      {
329        iterator __first = begin();
330        iterator __last = end();
331        if (__first == __last)
332	  return;
333        iterator __next = __first;
334        while (++__next != __last)
335	  {
336	    if (__binary_pred(*__first, *__next))
337	      _M_erase(__next);
338	    else
339	      __first = __next;
340	    __next = __first;
341	  }
342      }
343
344  template<typename _Tp, typename _Alloc>
345    template <typename _StrictWeakOrdering>
346      void
347      list<_Tp, _Alloc>::
348      sort(_StrictWeakOrdering __comp)
349      {
350	// Do nothing if the list has length 0 or 1.
351	if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
352	    && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
353	  {
354	    list __carry;
355	    list __tmp[64];
356	    list * __fill = &__tmp[0];
357	    list * __counter;
358
359	    do
360	      {
361		__carry.splice(__carry.begin(), *this, begin());
362
363		for(__counter = &__tmp[0];
364		    __counter != __fill && !__counter->empty();
365		    ++__counter)
366		  {
367		    __counter->merge(__carry, __comp);
368		    __carry.swap(*__counter);
369		  }
370		__carry.swap(*__counter);
371		if (__counter == __fill)
372		  ++__fill;
373	      }
374	    while ( !empty() );
375
376	    for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
377	      __counter->merge(*(__counter - 1), __comp);
378	    swap(*(__fill - 1));
379	  }
380      }
381
382_GLIBCXX_END_NESTED_NAMESPACE
383
384#endif /* _LIST_TCC */
385
386