home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / stlpt453.zip / STLport-4.5.3 / stlport / stl / _list.c < prev    next >
C/C++ Source or Header  |  2002-02-02  |  6KB  |  211 lines
  1. /*
  2.  *
  3.  *
  4.  * Copyright (c) 1994
  5.  * Hewlett-Packard Company
  6.  *
  7.  * Copyright (c) 1996,1997
  8.  * Silicon Graphics Computer Systems, Inc.
  9.  *
  10.  * Copyright (c) 1997
  11.  * Moscow Center for SPARC Technology
  12.  *
  13.  * Copyright (c) 1999 
  14.  * Boris Fomitchev
  15.  *
  16.  * This material is provided "as is", with absolutely no warranty expressed
  17.  * or implied. Any use is at your own risk.
  18.  *
  19.  * Permission to use or copy this software for any purpose is hereby granted 
  20.  * without fee, provided the above notices are retained on all copies.
  21.  * Permission to modify the code and to distribute modified code is granted,
  22.  * provided the above notices are retained, and a notice that the code was
  23.  * modified is included with the above copyright notice.
  24.  *
  25.  */
  26. #ifndef _STLP_LIST_C
  27. #define _STLP_LIST_C
  28.  
  29. #ifndef _STLP_INTERNAL_LIST_H
  30. # include <stl/_list.h>
  31. #endif
  32.  
  33. #if defined (__WATCOMC__)
  34. #include <vector>
  35. #endif
  36.  
  37. # undef list
  38. # define  list  __WORKAROUND_DBG_RENAME(list)
  39.  
  40. _STLP_BEGIN_NAMESPACE
  41.  
  42. # if defined (_STLP_EXPOSE_GLOBALS_IMPLEMENTATION)
  43.  
  44. template <class _Dummy>
  45. void _STLP_CALL
  46. _List_global<_Dummy>::_Transfer(_List_node_base* __position, 
  47.                 _List_node_base* __first, _List_node_base* __last) {
  48.   if (__position != __last) {
  49.     // Remove [first, last) from its old position.
  50.     ((_Node*) (__last->_M_prev))->_M_next = __position;
  51.     ((_Node*) (__first->_M_prev))->_M_next    = __last;
  52.     ((_Node*) (__position->_M_prev))->_M_next = __first; 
  53.     
  54.     // Splice [first, last) into its new position.
  55.     _Node* __tmp = (_Node*) (__position->_M_prev);
  56.     __position->_M_prev = __last->_M_prev;
  57.     __last->_M_prev      = __first->_M_prev; 
  58.     __first->_M_prev    = __tmp;
  59.   }
  60. }
  61.  
  62. #endif /* defined (__BUILDING_STLPORT) || ! defined (_STLP_OWN_IOSTREAMS) */
  63.  
  64.  
  65. template <class _Tp, class _Alloc>
  66. void 
  67. _List_base<_Tp,_Alloc>::clear() 
  68. {
  69.   _List_node<_Tp>* __cur = (_List_node<_Tp>*) this->_M_node._M_data->_M_next;
  70.   while (__cur != this->_M_node._M_data) {
  71.     _List_node<_Tp>* __tmp = __cur;
  72.     __cur = (_List_node<_Tp>*) __cur->_M_next;
  73.     _Destroy(&__tmp->_M_data);
  74.     this->_M_node.deallocate(__tmp, 1);
  75.   }
  76.   this->_M_node._M_data->_M_next = this->_M_node._M_data;
  77.   this->_M_node._M_data->_M_prev = this->_M_node._M_data;
  78. }
  79.  
  80. # if defined (_STLP_NESTED_TYPE_PARAM_BUG) 
  81. #  define size_type      size_t
  82. # endif
  83.  
  84. template <class _Tp, class _Alloc>
  85. void list<_Tp, _Alloc>::resize(size_type __new_size, const _Tp& __x)
  86. {
  87.   iterator __i = begin();
  88.   size_type __len = 0;
  89.   for ( ; __i != end() && __len < __new_size; ++__i, ++__len);
  90.  
  91.   if (__len == __new_size)
  92.     erase(__i, end());
  93.   else                          // __i == end()
  94.     insert(end(), __new_size - __len, __x);
  95. }
  96.  
  97. template <class _Tp, class _Alloc>
  98. list<_Tp, _Alloc>& list<_Tp, _Alloc>::operator=(const list<_Tp, _Alloc>& __x)
  99. {
  100.   if (this != &__x) {
  101.     iterator __first1 = begin();
  102.     iterator __last1 = end();
  103.     const_iterator __first2 = __x.begin();
  104.     const_iterator __last2 = __x.end();
  105.     while (__first1 != __last1 && __first2 != __last2) 
  106.       *__first1++ = *__first2++;
  107.     if (__first2 == __last2)
  108.       erase(__first1, __last1);
  109.     else
  110.       insert(__last1, __first2, __last2);
  111.   }
  112.   return *this;
  113. }
  114.  
  115. template <class _Tp, class _Alloc>
  116. void list<_Tp, _Alloc>::_M_fill_assign(size_type __n, const _Tp& __val) {
  117.   iterator __i = begin();
  118.   for ( ; __i != end() && __n > 0; ++__i, --__n)
  119.     *__i = __val;
  120.   if (__n > 0)
  121.     insert(end(), __n, __val);
  122.   else
  123.     erase(__i, end());
  124. }
  125.  
  126. template <class _Tp, class _Alloc, class _Predicate> 
  127. void _S_remove_if(list<_Tp, _Alloc>& __that, _Predicate __pred)  {
  128.   typename list<_Tp, _Alloc>::iterator __first = __that.begin();
  129.   typename list<_Tp, _Alloc>::iterator __last = __that.end();
  130.   while (__first != __last) {
  131.     typename list<_Tp, _Alloc>::iterator __next = __first;
  132.     ++__next;
  133.     if (__pred(*__first)) __that.erase(__first);
  134.     __first = __next;
  135.   }
  136. }
  137.  
  138. template <class _Tp, class _Alloc, class _BinaryPredicate>
  139. void _S_unique(list<_Tp, _Alloc>& __that, _BinaryPredicate __binary_pred) {
  140.   typename list<_Tp, _Alloc>::iterator __first = __that.begin();
  141.   typename list<_Tp, _Alloc>::iterator __last = __that.end();
  142.   if (__first == __last) return;
  143.   typename list<_Tp, _Alloc>::iterator __next = __first;
  144.   while (++__next != __last) {
  145.     if (__binary_pred(*__first, *__next))
  146.       __that.erase(__next);
  147.     else
  148.       __first = __next;
  149.     __next = __first;
  150.   }
  151. }
  152.  
  153. template <class _Tp, class _Alloc, class _StrictWeakOrdering>
  154. void _S_merge(list<_Tp, _Alloc>& __that, list<_Tp, _Alloc>& __x,
  155.           _StrictWeakOrdering __comp) {
  156.   typedef typename list<_Tp, _Alloc>::iterator _Literator;
  157.   _Literator __first1 = __that.begin();
  158.   _Literator __last1 = __that.end();
  159.   _Literator __first2 = __x.begin();
  160.   _Literator __last2 = __x.end();
  161.   while (__first1 != __last1 && __first2 != __last2)
  162.     if (__comp(*__first2, *__first1)) {
  163.       _Literator __next = __first2;
  164.       _List_global_inst::_Transfer(__first1._M_node, __first2._M_node, (++__next)._M_node);
  165.       __first2 = __next;
  166.     }
  167.     else
  168.       ++__first1;
  169.   if (__first2 != __last2) _List_global_inst::_Transfer(__last1._M_node, __first2._M_node, __last2._M_node);
  170. }
  171.  
  172. template <class _Tp, class _Alloc, class _StrictWeakOrdering>
  173. void _S_sort(list<_Tp, _Alloc>& __that, _StrictWeakOrdering __comp) {
  174.   // Do nothing if the list has length 0 or 1.
  175.   if (__that._M_node._M_data->_M_next != __that._M_node._M_data &&
  176.       (__that._M_node._M_data->_M_next)->_M_next != __that._M_node._M_data) {
  177.     list<_Tp, _Alloc> __carry;
  178. #if !defined (__WATCOMC__)
  179.     list<_Tp, _Alloc> __counter[64];
  180. #else
  181.     __vector__<list<_Tp, _Alloc>, _Alloc> __counter(64);        
  182. #endif        //*TY 05/25/2000 - 
  183.     int __fill = 0;
  184.     while (!__that.empty()) {
  185.       __carry.splice(__carry.begin(), __that, __that.begin());
  186.       int __i = 0;
  187.       while(__i < __fill && !__counter[__i].empty()) {
  188.     _S_merge(__counter[__i], __carry, __comp);
  189.     __carry.swap(__counter[__i++]);
  190.       }
  191.       __carry.swap(__counter[__i]);         
  192.       if (__i == __fill) ++__fill;
  193.     } 
  194.     
  195.     for (int __i = 1; __i < __fill; ++__i) 
  196.       _S_merge(__counter[__i], __counter[__i-1], __comp);
  197.     __that.swap(__counter[__fill-1]);
  198.   }
  199. }
  200.  
  201. # undef  list
  202. # undef  size_type
  203.  
  204. _STLP_END_NAMESPACE
  205.  
  206. #endif /*  _STLP_LIST_C */
  207.  
  208. // Local Variables:
  209. // mode:C++
  210. // End:
  211.