#ifndef _LIST_TCC
#define _LIST_TCC 1
namespace _GLIBCXX_STD
{
template<typename _Tp, typename _Alloc>
void
_List_base<_Tp, _Alloc>::
_M_clear()
{
typedef _List_node<_Tp> _Node;
_Node* __cur = static_cast<_Node*>(this->_M_impl._M_node._M_next);
while (__cur != &this->_M_impl._M_node)
{
_Node* __tmp = __cur;
__cur = static_cast<_Node*>(__cur->_M_next);
this->get_allocator().destroy(&__tmp->_M_data);
_M_put_node(__tmp);
}
}
template<typename _Tp, typename _Alloc>
typename list<_Tp, _Alloc>::iterator
list<_Tp, _Alloc>::
insert(iterator __position, const value_type& __x)
{
_Node* __tmp = _M_create_node(__x);
__tmp->hook(__position._M_node);
return __tmp;
}
template<typename _Tp, typename _Alloc>
typename list<_Tp, _Alloc>::iterator
list<_Tp, _Alloc>::
erase(iterator __position)
{
iterator __ret = __position._M_node->_M_next;
_M_erase(__position);
return __ret;
}
template<typename _Tp, typename _Alloc>
void
list<_Tp, _Alloc>::
resize(size_type __new_size, const value_type& __x)
{
iterator __i = begin();
size_type __len = 0;
for (; __i != end() && __len < __new_size; ++__i, ++__len)
;
if (__len == __new_size)
erase(__i, end());
else insert(end(), __new_size - __len, __x);
}
template<typename _Tp, typename _Alloc>
list<_Tp, _Alloc>&
list<_Tp, _Alloc>::
operator=(const list& __x)
{
if (this != &__x)
{
iterator __first1 = begin();
iterator __last1 = end();
const_iterator __first2 = __x.begin();
const_iterator __last2 = __x.end();
for (; __first1 != __last1 && __first2 != __last2;
++__first1, ++__first2)
*__first1 = *__first2;
if (__first2 == __last2)
erase(__first1, __last1);
else
insert(__last1, __first2, __last2);
}
return *this;
}
template<typename _Tp, typename _Alloc>
void
list<_Tp, _Alloc>::
_M_fill_assign(size_type __n, const value_type& __val)
{
iterator __i = begin();
for (; __i != end() && __n > 0; ++__i, --__n)
*__i = __val;
if (__n > 0)
insert(end(), __n, __val);
else
erase(__i, end());
}
template<typename _Tp, typename _Alloc>
template <typename _InputIterator>
void
list<_Tp, _Alloc>::
_M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
__false_type)
{
iterator __first1 = begin();
iterator __last1 = end();
for (; __first1 != __last1 && __first2 != __last2;
++__first1, ++__first2)
*__first1 = *__first2;
if (__first2 == __last2)
erase(__first1, __last1);
else
insert(__last1, __first2, __last2);
}
template<typename _Tp, typename _Alloc>
void
list<_Tp, _Alloc>::
remove(const value_type& __value)
{
iterator __first = begin();
iterator __last = end();
while (__first != __last)
{
iterator __next = __first;
++__next;
if (*__first == __value)
_M_erase(__first);
__first = __next;
}
}
template<typename _Tp, typename _Alloc>
void
list<_Tp, _Alloc>::
unique()
{
iterator __first = begin();
iterator __last = end();
if (__first == __last)
return;
iterator __next = __first;
while (++__next != __last)
{
if (*__first == *__next)
_M_erase(__next);
else
__first = __next;
__next = __first;
}
}
template<typename _Tp, typename _Alloc>
void
list<_Tp, _Alloc>::
merge(list& __x)
{
if (this != &__x)
{
iterator __first1 = begin();
iterator __last1 = end();
iterator __first2 = __x.begin();
iterator __last2 = __x.end();
while (__first1 != __last1 && __first2 != __last2)
if (*__first2 < *__first1)
{
iterator __next = __first2;
_M_transfer(__first1, __first2, ++__next);
__first2 = __next;
}
else
++__first1;
if (__first2 != __last2)
_M_transfer(__last1, __first2, __last2);
}
}
template<typename _Tp, typename _Alloc>
void
list<_Tp, _Alloc>::
sort()
{
if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
&& this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
{
list __carry;
list __tmp[64];
list * __fill = &__tmp[0];
list * __counter;
do
{
__carry.splice(__carry.begin(), *this, begin());
for(__counter = &__tmp[0];
__counter != __fill && !__counter->empty();
++__counter)
{
__counter->merge(__carry);
__carry.swap(*__counter);
}
__carry.swap(*__counter);
if (__counter == __fill)
++__fill;
}
while ( !empty() );
for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
__counter->merge(*(__counter - 1));
swap( *(__fill - 1) );
}
}
template<typename _Tp, typename _Alloc>
template <typename _Predicate>
void
list<_Tp, _Alloc>::
remove_if(_Predicate __pred)
{
iterator __first = begin();
iterator __last = end();
while (__first != __last)
{
iterator __next = __first;
++__next;
if (__pred(*__first))
_M_erase(__first);
__first = __next;
}
}
template<typename _Tp, typename _Alloc>
template <typename _BinaryPredicate>
void
list<_Tp, _Alloc>::
unique(_BinaryPredicate __binary_pred)
{
iterator __first = begin();
iterator __last = end();
if (__first == __last)
return;
iterator __next = __first;
while (++__next != __last)
{
if (__binary_pred(*__first, *__next))
_M_erase(__next);
else
__first = __next;
__next = __first;
}
}
template<typename _Tp, typename _Alloc>
template <typename _StrictWeakOrdering>
void
list<_Tp, _Alloc>::
merge(list& __x, _StrictWeakOrdering __comp)
{
if (this != &__x)
{
iterator __first1 = begin();
iterator __last1 = end();
iterator __first2 = __x.begin();
iterator __last2 = __x.end();
while (__first1 != __last1 && __first2 != __last2)
if (__comp(*__first2, *__first1))
{
iterator __next = __first2;
_M_transfer(__first1, __first2, ++__next);
__first2 = __next;
}
else
++__first1;
if (__first2 != __last2)
_M_transfer(__last1, __first2, __last2);
}
}
template<typename _Tp, typename _Alloc>
template <typename _StrictWeakOrdering>
void
list<_Tp, _Alloc>::
sort(_StrictWeakOrdering __comp)
{
if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
&& this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
{
list __carry;
list __tmp[64];
list * __fill = &__tmp[0];
list * __counter;
do
{
__carry.splice(__carry.begin(), *this, begin());
for(__counter = &__tmp[0];
__counter != __fill && !__counter->empty();
++__counter)
{
__counter->merge(__carry, __comp);
__carry.swap(*__counter);
}
__carry.swap(*__counter);
if (__counter == __fill)
++__fill;
}
while ( !empty() );
for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
__counter->merge(*(__counter - 1), __comp);
swap(*(__fill - 1));
}
}
}
#endif