home *** CD-ROM | disk | FTP | other *** search
/ PC World 2000 November / PCWorld_2000-11_cd.bin / Software / Topware / devc40 / _SETUP.6 / Group14 / stl_algobase.h < prev    next >
C/C++ Source or Header  |  2000-01-21  |  18KB  |  527 lines
  1. /*
  2.  *
  3.  * Copyright (c) 1994
  4.  * Hewlett-Packard Company
  5.  *
  6.  * Permission to use, copy, modify, distribute and sell this software
  7.  * and its documentation for any purpose is hereby granted without fee,
  8.  * provided that the above copyright notice appear in all copies and
  9.  * that both that copyright notice and this permission notice appear
  10.  * in supporting documentation.  Hewlett-Packard Company makes no
  11.  * representations about the suitability of this software for any
  12.  * purpose.  It is provided "as is" without express or implied warranty.
  13.  *
  14.  *
  15.  * Copyright (c) 1996-1998
  16.  * Silicon Graphics Computer Systems, Inc.
  17.  *
  18.  * Permission to use, copy, modify, distribute and sell this software
  19.  * and its documentation for any purpose is hereby granted without fee,
  20.  * provided that the above copyright notice appear in all copies and
  21.  * that both that copyright notice and this permission notice appear
  22.  * in supporting documentation.  Silicon Graphics makes no
  23.  * representations about the suitability of this software for any
  24.  * purpose.  It is provided "as is" without express or implied warranty.
  25.  */
  26.  
  27. /* NOTE: This is an internal header file, included by other STL headers.
  28.  *   You should not attempt to use it directly.
  29.  */
  30.  
  31.  
  32. #ifndef __SGI_STL_INTERNAL_ALGOBASE_H
  33. #define __SGI_STL_INTERNAL_ALGOBASE_H
  34.  
  35. #ifndef __STL_CONFIG_H
  36. #include <stl_config.h>
  37. #endif
  38. #ifndef __SGI_STL_INTERNAL_RELOPS
  39. #include <stl_relops.h>
  40. #endif
  41. #ifndef __SGI_STL_INTERNAL_PAIR_H
  42. #include <stl_pair.h>
  43. #endif
  44. #ifndef __TYPE_TRAITS_H_
  45. #include <type_traits.h>
  46. #endif
  47.  
  48. #include <string.h>
  49. #include <limits.h>
  50. #include <stdlib.h>
  51. #include <stddef.h>
  52. #include <new.h>
  53. #include <iostream.h>
  54.  
  55. #ifndef __SGI_STL_INTERNAL_ITERATOR_H
  56. #include <stl_iterator.h>
  57. #endif
  58.  
  59. __STL_BEGIN_NAMESPACE
  60.  
  61. // swap and iter_swap
  62.  
  63. template <class _ForwardIter1, class _ForwardIter2, class _Tp>
  64. inline void __iter_swap(_ForwardIter1 __a, _ForwardIter2 __b, _Tp*) {
  65.   _Tp __tmp = *__a;
  66.   *__a = *__b;
  67.   *__b = __tmp;
  68. }
  69.  
  70. template <class _ForwardIter1, class _ForwardIter2>
  71. inline void iter_swap(_ForwardIter1 __a, _ForwardIter2 __b) {
  72.   __iter_swap(__a, __b, __VALUE_TYPE(__a));
  73. }
  74.  
  75. template <class _Tp>
  76. inline void swap(_Tp& __a, _Tp& __b) {
  77.   _Tp __tmp = __a;
  78.   __a = __b;
  79.   __b = __tmp;
  80. }
  81.  
  82. //--------------------------------------------------
  83. // min and max
  84.  
  85. #ifndef __BORLANDC__
  86.  
  87. #undef min
  88. #undef max
  89.  
  90. template <class _Tp>
  91. inline const _Tp& min(const _Tp& __a, const _Tp& __b) {
  92.   return __b < __a ? __b : __a;
  93. }
  94.  
  95. template <class _Tp>
  96. inline const _Tp& max(const _Tp& __a, const _Tp& __b) {
  97.   return  __a < __b ? __b : __a;
  98. }
  99.  
  100. #endif /* __BORLANDC__ */
  101.  
  102. template <class _Tp, class _Compare>
  103. inline const _Tp& min(const _Tp& __a, const _Tp& __b, _Compare __comp) {
  104.   return __comp(__b, __a) ? __b : __a;
  105. }
  106.  
  107. template <class _Tp, class _Compare>
  108. inline const _Tp& max(const _Tp& __a, const _Tp& __b, _Compare __comp) {
  109.   return __comp(__a, __b) ? __b : __a;
  110. }
  111.  
  112. //--------------------------------------------------
  113. // copy
  114.  
  115. // All of these auxiliary functions serve two purposes.  (1) Replace
  116. // calls to copy with memmove whenever possible.  (Memmove, not memcpy,
  117. // because the input and output ranges are permitted to overlap.)
  118. // (2) If we're using random access iterators, then write the loop as
  119. // a for loop with an explicit count.  The auxiliary class __copy_dispatch
  120. // is a workaround for compilers that don't support partial ordering of
  121. // function templates.
  122.  
  123. template <class _InputIter, class _OutputIter, class _Distance>
  124. inline _OutputIter __copy(_InputIter __first, _InputIter __last,
  125.                           _OutputIter __result,
  126.                           input_iterator_tag, _Distance*)
  127. {
  128.   for ( ; __first != __last; ++__result, ++__first)
  129.     *__result = *__first;
  130.   return __result;
  131. }
  132.  
  133. template <class _RandomAccessIter, class _OutputIter, class _Distance>
  134. inline _OutputIter
  135. __copy(_RandomAccessIter __first, _RandomAccessIter __last,
  136.        _OutputIter __result, random_access_iterator_tag, _Distance*)
  137. {
  138.   for (_Distance __n = __last - __first; __n > 0; --__n) {
  139.     *__result = *__first;
  140.     ++__first;
  141.     ++__result;
  142.   }
  143.   return __result;
  144. }
  145.  
  146. template <class _Tp>
  147. inline _Tp*
  148. __copy_trivial(const _Tp* __first, const _Tp* __last, _Tp* __result) {
  149.   memmove(__result, __first, sizeof(_Tp) * (__last - __first));
  150.   return __result + (__last - __first);
  151. }
  152.  
  153. #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION 
  154.  
  155. template <class _InputIter, class _OutputIter, class _BoolType>
  156. struct __copy_dispatch {
  157.   static _OutputIter copy(_InputIter __first, _InputIter __last,
  158.                           _OutputIter __result) {
  159.     typedef typename iterator_traits<_InputIter>::iterator_category _Category;
  160.     typedef typename iterator_traits<_InputIter>::difference_type _Distance;
  161.     return __copy(__first, __last, __result, _Category(), (_Distance*) 0);
  162.   }
  163. };
  164.  
  165. template <class _Tp>
  166. struct __copy_dispatch<_Tp*, _Tp*, __true_type>
  167. {
  168.   static _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) {
  169.     return __copy_trivial(__first, __last, __result);
  170.   }
  171. };
  172.  
  173. template <class _Tp>
  174. struct __copy_dispatch<const _Tp*, _Tp*, __true_type>
  175. {
  176.   static _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) {
  177.     return __copy_trivial(__first, __last, __result);
  178.   }
  179. };
  180.  
  181. template <class _InputIter, class _OutputIter>
  182. inline _OutputIter copy(_InputIter __first, _InputIter __last,
  183.                         _OutputIter __result) {
  184.   typedef typename iterator_traits<_InputIter>::value_type _Tp;
  185.   typedef typename __type_traits<_Tp>::has_trivial_assignment_operator
  186.           _Trivial;
  187.   return __copy_dispatch<_InputIter, _OutputIter, _Trivial>
  188.     ::copy(__first, __last, __result);
  189. }
  190.  
  191. #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  192.  
  193. template <class _InputIter, class _OutputIter>
  194. inline _OutputIter copy(_InputIter __first, _InputIter __last,
  195.                         _OutputIter __result)
  196. {
  197.   return __copy(__first, __last, __result,
  198.                 __ITERATOR_CATEGORY(__first),
  199.                 __DISTANCE_TYPE(__first));
  200. }
  201.  
  202. inline char* copy(const char* __first, const char* __last, char* __result) {
  203.   memmove(__result, __first, __last - __first);
  204.   return __result + (__last - __first);
  205. }
  206.  
  207. inline wchar_t* copy(const wchar_t* __first, const wchar_t* __last,
  208.                      wchar_t* __result) {
  209.   memmove(__result, __first, sizeof(wchar_t) * (__last - __first));
  210.   return __result + (__last - __first);
  211. }
  212.  
  213. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  214.  
  215. //--------------------------------------------------
  216. // copy_backward
  217.  
  218. template <class _BidirectionalIter1, class _BidirectionalIter2, 
  219.           class _Distance>
  220. inline _BidirectionalIter2 __copy_backward(_BidirectionalIter1 __first, 
  221.                                            _BidirectionalIter1 __last, 
  222.                                            _BidirectionalIter2 __result,
  223.                                            bidirectional_iterator_tag,
  224.                                            _Distance*)
  225. {
  226.   while (__first != __last)
  227.     *--__result = *--__last;
  228.   return __result;
  229. }
  230.  
  231. template <class _RandomAccessIter, class _BidirectionalIter, class _Distance>
  232. inline _BidirectionalIter __copy_backward(_RandomAccessIter __first, 
  233.                                           _RandomAccessIter __last, 
  234.                                           _BidirectionalIter __result,
  235.                                           random_access_iterator_tag,
  236.                                           _Distance*)
  237. {
  238.   for (_Distance __n = __last - __first; __n > 0; --__n)
  239.     *--__result = *--__last;
  240.   return __result;
  241. }
  242.  
  243. #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION 
  244.  
  245. // This dispatch class is a workaround for compilers that do not 
  246. // have partial ordering of function templates.  All we're doing is
  247. // creating a specialization so that we can turn a call to copy_backward
  248. // into a memmove whenever possible.
  249.  
  250. template <class _BidirectionalIter1, class _BidirectionalIter2,
  251.           class _BoolType>
  252. struct __copy_backward_dispatch
  253. {
  254.   typedef typename iterator_traits<_BidirectionalIter1>::iterator_category 
  255.           _Cat;
  256.   typedef typename iterator_traits<_BidirectionalIter1>::difference_type
  257.           _Distance;
  258.  
  259.   static _BidirectionalIter2 copy(_BidirectionalIter1 __first, 
  260.                                   _BidirectionalIter1 __last, 
  261.                                   _BidirectionalIter2 __result) {
  262.     return __copy_backward(__first, __last, __result, _Cat(), (_Distance*) 0);
  263.   }
  264. };
  265.  
  266. template <class _Tp>
  267. struct __copy_backward_dispatch<_Tp*, _Tp*, __true_type>
  268. {
  269.   static _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) {
  270.     const ptrdiff_t _Num = __last - __first;
  271.     memmove(__result - _Num, __first, sizeof(_Tp) * _Num);
  272.     return __result - _Num;
  273.   }
  274. };
  275.  
  276. template <class _Tp>
  277. struct __copy_backward_dispatch<const _Tp*, _Tp*, __true_type>
  278. {
  279.   static _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) {
  280.     return  __copy_backward_dispatch<_Tp*, _Tp*, __true_type>
  281.       ::copy(__first, __last, __result);
  282.   }
  283. };
  284.  
  285. template <class _BI1, class _BI2>
  286. inline _BI2 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result) {
  287.   typedef typename __type_traits<typename iterator_traits<_BI2>::value_type>
  288.                         ::has_trivial_assignment_operator
  289.           _Trivial;
  290.   return __copy_backward_dispatch<_BI1, _BI2, _Trivial>
  291.               ::copy(__first, __last, __result);
  292. }
  293.  
  294. #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  295.  
  296. template <class _BI1, class _BI2>
  297. inline _BI2 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result) {
  298.   return __copy_backward(__first, __last, __result,
  299.                          __ITERATOR_CATEGORY(__first),
  300.                          __DISTANCE_TYPE(__first));
  301. }
  302.  
  303. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  304.  
  305. //--------------------------------------------------
  306. // copy_n (not part of the C++ standard)
  307.  
  308. template <class _InputIter, class _Size, class _OutputIter>
  309. pair<_InputIter, _OutputIter> __copy_n(_InputIter __first, _Size __count,
  310.                                        _OutputIter __result,
  311.                                        input_iterator_tag) {
  312.   for ( ; __count > 0; --__count) {
  313.     *__result = *__first;
  314.     ++__first;
  315.     ++__result;
  316.   }
  317.   return pair<_InputIter, _OutputIter>(__first, __result);
  318. }
  319.  
  320. template <class _RAIter, class _Size, class _OutputIter>
  321. inline pair<_RAIter, _OutputIter>
  322. __copy_n(_RAIter __first, _Size __count,
  323.          _OutputIter __result,
  324.          random_access_iterator_tag) {
  325.   _RAIter __last = __first + __count;
  326.   return pair<_RAIter, _OutputIter>(__last, copy(__first, __last, __result));
  327. }
  328.  
  329. template <class _InputIter, class _Size, class _OutputIter>
  330. inline pair<_InputIter, _OutputIter>
  331. __copy_n(_InputIter __first, _Size __count, _OutputIter __result) {
  332.   return __copy_n(__first, __count, __result,
  333.                   __ITERATOR_CATEGORY(__first));
  334. }
  335.  
  336. template <class _InputIter, class _Size, class _OutputIter>
  337. inline pair<_InputIter, _OutputIter>
  338. copy_n(_InputIter __first, _Size __count, _OutputIter __result) {
  339.   return __copy_n(__first, __count, __result);
  340. }
  341.  
  342. //--------------------------------------------------
  343. // fill and fill_n
  344.  
  345.  
  346. template <class _ForwardIter, class _Tp>
  347. void fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __value) {
  348.   for ( ; __first != __last; ++__first)
  349.     *__first = __value;
  350. }
  351.  
  352. template <class _OutputIter, class _Size, class _Tp>
  353. _OutputIter fill_n(_OutputIter __first, _Size __n, const _Tp& __value) {
  354.   for ( ; __n > 0; --__n, ++__first)
  355.     *__first = __value;
  356.   return __first;
  357. }
  358.  
  359. //--------------------------------------------------
  360. // equal and mismatch
  361.  
  362. template <class _InputIter1, class _InputIter2>
  363. pair<_InputIter1, _InputIter2> mismatch(_InputIter1 __first1,
  364.                                         _InputIter1 __last1,
  365.                                         _InputIter2 __first2) {
  366.   while (__first1 != __last1 && *__first1 == *__first2) {
  367.     ++__first1;
  368.     ++__first2;
  369.   }
  370.   return pair<_InputIter1, _InputIter2>(__first1, __first2);
  371. }
  372.  
  373. template <class _InputIter1, class _InputIter2, class _BinaryPredicate>
  374. pair<_InputIter1, _InputIter2> mismatch(_InputIter1 __first1,
  375.                                         _InputIter1 __last1,
  376.                                         _InputIter2 __first2,
  377.                                         _BinaryPredicate __binary_pred) {
  378.   while (__first1 != __last1 && __binary_pred(*__first1, *__first2)) {
  379.     ++__first1;
  380.     ++__first2;
  381.   }
  382.   return pair<_InputIter1, _InputIter2>(__first1, __first2);
  383. }
  384.  
  385. template <class _InputIter1, class _InputIter2>
  386. inline bool equal(_InputIter1 __first1, _InputIter1 __last1,
  387.                   _InputIter2 __first2) {
  388.   for ( ; __first1 != __last1; ++__first1, ++__first2)
  389.     if (*__first1 != *__first2)
  390.       return false;
  391.   return true;
  392. }
  393.  
  394. template <class _InputIter1, class _InputIter2, class _BinaryPredicate>
  395. inline bool equal(_InputIter1 __first1, _InputIter1 __last1,
  396.                   _InputIter2 __first2, _BinaryPredicate __binary_pred) {
  397.   for ( ; __first1 != __last1; ++__first1, ++__first2)
  398.     if (!__binary_pred(*__first1, *__first2))
  399.       return false;
  400.   return true;
  401. }
  402.  
  403. //--------------------------------------------------
  404. // lexicographical_compare and lexicographical_compare_3way.
  405. // (the latter is not part of the C++ standard.)
  406.  
  407. template <class _InputIter1, class _InputIter2>
  408. bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
  409.                              _InputIter2 __first2, _InputIter2 __last2) {
  410.   for ( ; __first1 != __last1 && __first2 != __last2
  411.         ; ++__first1, ++__first2) {
  412.     if (*__first1 < *__first2)
  413.       return true;
  414.     if (*__first2 < *__first1)
  415.       return false;
  416.   }
  417.   return __first1 == __last1 && __first2 != __last2;
  418. }
  419.  
  420. template <class _InputIter1, class _InputIter2, class _Compare>
  421. bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
  422.                              _InputIter2 __first2, _InputIter2 __last2,
  423.                              _Compare __comp) {
  424.   for ( ; __first1 != __last1 && __first2 != __last2
  425.         ; ++__first1, ++__first2) {
  426.     if (__comp(*__first1, *__first2))
  427.       return true;
  428.     if (__comp(*__first2, *__first1))
  429.       return false;
  430.   }
  431.   return __first1 == __last1 && __first2 != __last2;
  432. }
  433.  
  434. inline bool 
  435. lexicographical_compare(const unsigned char* __first1,
  436.                         const unsigned char* __last1,
  437.                         const unsigned char* __first2,
  438.                         const unsigned char* __last2)
  439. {
  440.   const size_t __len1 = __last1 - __first1;
  441.   const size_t __len2 = __last2 - __first2;
  442.   const int __result = memcmp(__first1, __first2, min(__len1, __len2));
  443.   return __result != 0 ? __result < 0 : __len1 < __len2;
  444. }
  445.  
  446. inline bool lexicographical_compare(const char* __first1, const char* __last1,
  447.                                     const char* __first2, const char* __last2)
  448. {
  449. #if CHAR_MAX == SCHAR_MAX
  450.   return lexicographical_compare((const signed char*) __first1,
  451.                                  (const signed char*) __last1,
  452.                                  (const signed char*) __first2,
  453.                                  (const signed char*) __last2);
  454. #else /* CHAR_MAX == SCHAR_MAX */
  455.   return lexicographical_compare((const unsigned char*) __first1,
  456.                                  (const unsigned char*) __last1,
  457.                                  (const unsigned char*) __first2,
  458.                                  (const unsigned char*) __last2);
  459. #endif /* CHAR_MAX == SCHAR_MAX */
  460. }
  461.  
  462. template <class _InputIter1, class _InputIter2>
  463. int __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
  464.                                    _InputIter2 __first2, _InputIter2 __last2)
  465. {
  466.   while (__first1 != __last1 && __first2 != __last2) {
  467.     if (*__first1 < *__first2)
  468.       return -1;
  469.     if (*__first2 < *__first1)
  470.       return 1;
  471.     ++__first1;
  472.     ++__first2;
  473.   }
  474.   if (__first2 == __last2) {
  475.     return !(__first1 == __last1);
  476.   }
  477.   else {
  478.     return -1;
  479.   }
  480. }
  481.  
  482. inline int
  483. __lexicographical_compare_3way(const unsigned char* __first1,
  484.                                const unsigned char* __last1,
  485.                                const unsigned char* __first2,
  486.                                const unsigned char* __last2)
  487. {
  488.   const ptrdiff_t __len1 = __last1 - __first1;
  489.   const ptrdiff_t __len2 = __last2 - __first2;
  490.   const int __result = memcmp(__first1, __first2, min(__len1, __len2));
  491.   return __result != 0 ? __result 
  492.                        : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1));
  493. }
  494.  
  495. inline int 
  496. __lexicographical_compare_3way(const char* __first1, const char* __last1,
  497.                                const char* __first2, const char* __last2)
  498. {
  499. #if CHAR_MAX == SCHAR_MAX
  500.   return __lexicographical_compare_3way(
  501.                                 (const signed char*) __first1,
  502.                                 (const signed char*) __last1,
  503.                                 (const signed char*) __first2,
  504.                                 (const signed char*) __last2);
  505. #else
  506.   return __lexicographical_compare_3way((const unsigned char*) __first1,
  507.                                         (const unsigned char*) __last1,
  508.                                         (const unsigned char*) __first2,
  509.                                         (const unsigned char*) __last2);
  510. #endif
  511. }
  512.  
  513. template <class _InputIter1, class _InputIter2>
  514. int lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
  515.                                  _InputIter2 __first2, _InputIter2 __last2)
  516. {
  517.   return __lexicographical_compare_3way(__first1, __last1, __first2, __last2);
  518. }
  519.  
  520. __STL_END_NAMESPACE
  521.  
  522. #endif /* __SGI_STL_INTERNAL_ALGOBASE_H */
  523.  
  524. // Local Variables:
  525. // mode:C++
  526. // End:
  527.