home *** CD-ROM | disk | FTP | other *** search
/ PC World 2000 January / PCWorld_2000-01_cd.bin / Software / Servis / Devc / _SETUP.4 / Group3 / stl_algobase.h < prev    next >
C/C++ Source or Header  |  1998-03-08  |  14KB  |  443 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
  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. template <class ForwardIterator1, class ForwardIterator2, class T>
  62. inline void __iter_swap(ForwardIterator1 a, ForwardIterator2 b, T*) {
  63.   T tmp = *a;
  64.   *a = *b;
  65.   *b = tmp;
  66. }
  67.  
  68. template <class ForwardIterator1, class ForwardIterator2>
  69. inline void iter_swap(ForwardIterator1 a, ForwardIterator2 b) {
  70.   __iter_swap(a, b, value_type(a));
  71. }
  72.  
  73. template <class T>
  74. inline void swap(T& a, T& b) {
  75.   T tmp = a;
  76.   a = b;
  77.   b = tmp;
  78. }
  79.  
  80. #ifndef __BORLANDC__
  81.  
  82. #undef min
  83. #undef max
  84.  
  85. template <class T>
  86. inline const T& min(const T& a, const T& b) {
  87.   return b < a ? b : a;
  88. }
  89.  
  90. template <class T>
  91. inline const T& max(const T& a, const T& b) {
  92.   return  a < b ? b : a;
  93. }
  94.  
  95. #endif /* __BORLANDC__ */
  96.  
  97. template <class T, class Compare>
  98. inline const T& min(const T& a, const T& b, Compare comp) {
  99.   return comp(b, a) ? b : a;
  100. }
  101.  
  102. template <class T, class Compare>
  103. inline const T& max(const T& a, const T& b, Compare comp) {
  104.   return comp(a, b) ? b : a;
  105. }
  106.  
  107. template <class InputIterator, class OutputIterator>
  108. inline OutputIterator __copy(InputIterator first, InputIterator last,
  109.                              OutputIterator result, input_iterator_tag)
  110. {
  111.   for ( ; first != last; ++result, ++first)
  112.     *result = *first;
  113.   return result;
  114. }
  115.  
  116. template <class RandomAccessIterator, class OutputIterator, class Distance>
  117. inline OutputIterator
  118. __copy_d(RandomAccessIterator first, RandomAccessIterator last,
  119.          OutputIterator result, Distance*)
  120. {
  121.   for (Distance n = last - first; n > 0; --n, ++result, ++first) 
  122.     *result = *first;
  123.   return result;
  124. }
  125.  
  126. template <class RandomAccessIterator, class OutputIterator>
  127. inline OutputIterator 
  128. __copy(RandomAccessIterator first, RandomAccessIterator last,
  129.        OutputIterator result, random_access_iterator_tag)
  130. {
  131.   return __copy_d(first, last, result, distance_type(first));
  132. }
  133.  
  134. template <class InputIterator, class OutputIterator>
  135. struct __copy_dispatch
  136. {
  137.   OutputIterator operator()(InputIterator first, InputIterator last,
  138.                             OutputIterator result) {
  139.     return __copy(first, last, result, iterator_category(first));
  140.   }
  141. };
  142.  
  143. #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION 
  144.  
  145. template <class T>
  146. inline T* __copy_t(const T* first, const T* last, T* result, __true_type) {
  147.   memmove(result, first, sizeof(T) * (last - first));
  148.   return result + (last - first);
  149. }
  150.  
  151. template <class T>
  152. inline T* __copy_t(const T* first, const T* last, T* result, __false_type) {
  153.   return __copy_d(first, last, result, (ptrdiff_t*) 0);
  154. }
  155.  
  156. template <class T>
  157. struct __copy_dispatch<T*, T*>
  158. {
  159.   T* operator()(T* first, T* last, T* result) {
  160.     typedef typename __type_traits<T>::has_trivial_assignment_operator t; 
  161.     return __copy_t(first, last, result, t());
  162.   }
  163. };
  164.  
  165. template <class T>
  166. struct __copy_dispatch<const T*, T*>
  167. {
  168.   T* operator()(const T* first, const T* last, T* result) {
  169.     typedef typename __type_traits<T>::has_trivial_assignment_operator t; 
  170.     return __copy_t(first, last, result, t());
  171.   }
  172. };
  173.  
  174. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  175.  
  176. template <class InputIterator, class OutputIterator>
  177. inline OutputIterator copy(InputIterator first, InputIterator last,
  178.                            OutputIterator result)
  179. {
  180.   return __copy_dispatch<InputIterator,OutputIterator>()(first, last, result);
  181. }
  182.  
  183. inline char* copy(const char* first, const char* last, char* result) {
  184.   memmove(result, first, last - first);
  185.   return result + (last - first);
  186. }
  187.  
  188. inline wchar_t* copy(const wchar_t* first, const wchar_t* last,
  189.                      wchar_t* result) {
  190.   memmove(result, first, sizeof(wchar_t) * (last - first));
  191.   return result + (last - first);
  192. }
  193.  
  194. template <class BidirectionalIterator1, class BidirectionalIterator2>
  195. inline BidirectionalIterator2 __copy_backward(BidirectionalIterator1 first, 
  196.                                               BidirectionalIterator1 last, 
  197.                                               BidirectionalIterator2 result) {
  198.   while (first != last) *--result = *--last;
  199.   return result;
  200. }
  201.  
  202.  
  203. template <class BidirectionalIterator1, class BidirectionalIterator2>
  204. struct __copy_backward_dispatch
  205. {
  206.   BidirectionalIterator2 operator()(BidirectionalIterator1 first, 
  207.                                     BidirectionalIterator1 last, 
  208.                                     BidirectionalIterator2 result) {
  209.     return __copy_backward(first, last, result);
  210.   }
  211. };
  212.  
  213. #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION 
  214.  
  215. template <class T>
  216. inline T* __copy_backward_t(const T* first, const T* last, T* result,
  217.                             __true_type) {
  218.   const ptrdiff_t N = last - first;
  219.   memmove(result - N, first, sizeof(T) * N);
  220.   return result - N;
  221. }
  222.  
  223. template <class T>
  224. inline T* __copy_backward_t(const T* first, const T* last, T* result,
  225.                             __false_type) {
  226.   return __copy_backward(first, last, result);
  227. }
  228.  
  229. template <class T>
  230. struct __copy_backward_dispatch<T*, T*>
  231. {
  232.   T* operator()(T* first, T* last, T* result) {
  233.     typedef typename __type_traits<T>::has_trivial_assignment_operator t; 
  234.     return __copy_backward_t(first, last, result, t());
  235.   }
  236. };
  237.  
  238. template <class T>
  239. struct __copy_backward_dispatch<const T*, T*>
  240. {
  241.   T* operator()(const T* first, const T* last, T* result) {
  242.     typedef typename __type_traits<T>::has_trivial_assignment_operator t; 
  243.     return __copy_backward_t(first, last, result, t());
  244.   }
  245. };
  246.  
  247. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  248.  
  249. template <class BidirectionalIterator1, class BidirectionalIterator2>
  250. inline BidirectionalIterator2 copy_backward(BidirectionalIterator1 first, 
  251.                                             BidirectionalIterator1 last, 
  252.                                             BidirectionalIterator2 result) {
  253.   return __copy_backward_dispatch<BidirectionalIterator1, 
  254.                                   BidirectionalIterator2>()(first, last, 
  255.                                                             result);
  256. }
  257.  
  258. template <class InputIterator, class Size, class OutputIterator>
  259. pair<InputIterator, OutputIterator> __copy_n(InputIterator first, Size count,
  260.                                              OutputIterator result,
  261.                                              input_iterator_tag) {
  262.   for ( ; count > 0; --count, ++first, ++result)
  263.     *result = *first;
  264.   return pair<InputIterator, OutputIterator>(first, result);
  265. }
  266.  
  267. template <class RandomAccessIterator, class Size, class OutputIterator>
  268. inline pair<RandomAccessIterator, OutputIterator>
  269. __copy_n(RandomAccessIterator first, Size count,
  270.          OutputIterator result,
  271.          random_access_iterator_tag) {
  272.   RandomAccessIterator last = first + count;
  273.   return pair<RandomAccessIterator, OutputIterator>(last,
  274.                                                     copy(first, last, result));
  275. }
  276.  
  277. template <class InputIterator, class Size, class OutputIterator>
  278. inline pair<InputIterator, OutputIterator>
  279. copy_n(InputIterator first, Size count,
  280.        OutputIterator result) {
  281.   return __copy_n(first, count, result, iterator_category(first));
  282. }
  283.  
  284. template <class ForwardIterator, class T>
  285. void fill(ForwardIterator first, ForwardIterator last, const T& value) {
  286.   for ( ; first != last; ++first)
  287.     *first = value;
  288. }
  289.  
  290. template <class OutputIterator, class Size, class T>
  291. OutputIterator fill_n(OutputIterator first, Size n, const T& value) {
  292.   for ( ; n > 0; --n, ++first)
  293.     *first = value;
  294.   return first;
  295. }
  296.  
  297. template <class InputIterator1, class InputIterator2>
  298. pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1,
  299.                           InputIterator1 last1,
  300.                           InputIterator2 first2) {
  301.   while (first1 != last1 && *first1 == *first2) {
  302.     ++first1;
  303.     ++first2;
  304.   }
  305.   return pair<InputIterator1, InputIterator2>(first1, first2);
  306. }
  307.  
  308. template <class InputIterator1, class InputIterator2, class BinaryPredicate>
  309. pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1,
  310.                           InputIterator1 last1,
  311.                           InputIterator2 first2,
  312.                           BinaryPredicate binary_pred) {
  313.   while (first1 != last1 && binary_pred(*first1, *first2)) {
  314.     ++first1;
  315.     ++first2;
  316.   }
  317.   return pair<InputIterator1, InputIterator2>(first1, first2);
  318. }
  319.  
  320. template <class InputIterator1, class InputIterator2>
  321. inline bool equal(InputIterator1 first1, InputIterator1 last1,
  322.           InputIterator2 first2) {
  323.   for ( ; first1 != last1; ++first1, ++first2)
  324.     if (*first1 != *first2)
  325.       return false;
  326.   return true;
  327. }
  328.  
  329. template <class InputIterator1, class InputIterator2, class BinaryPredicate>
  330. inline bool equal(InputIterator1 first1, InputIterator1 last1,
  331.           InputIterator2 first2, BinaryPredicate binary_pred) {
  332.   for ( ; first1 != last1; ++first1, ++first2)
  333.     if (!binary_pred(*first1, *first2))
  334.       return false;
  335.   return true;
  336. }
  337.  
  338. template <class InputIterator1, class InputIterator2>
  339. bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
  340.                  InputIterator2 first2, InputIterator2 last2) {
  341.   for ( ; first1 != last1 && first2 != last2; ++first1, ++first2) {
  342.     if (*first1 < *first2)
  343.       return true;
  344.     if (*first2 < *first1)
  345.       return false;
  346.   }
  347.   return first1 == last1 && first2 != last2;
  348. }
  349.  
  350. template <class InputIterator1, class InputIterator2, class Compare>
  351. bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
  352.                  InputIterator2 first2, InputIterator2 last2,
  353.                  Compare comp) {
  354.   for ( ; first1 != last1 && first2 != last2; ++first1, ++first2) {
  355.     if (comp(*first1, *first2))
  356.       return true;
  357.     if (comp(*first2, *first1))
  358.       return false;
  359.   }
  360.   return first1 == last1 && first2 != last2;
  361. }
  362.  
  363. inline bool 
  364. lexicographical_compare(const unsigned char* first1,
  365.                         const unsigned char* last1,
  366.                         const unsigned char* first2,
  367.                         const unsigned char* last2)
  368. {
  369.   const size_t len1 = last1 - first1;
  370.   const size_t len2 = last2 - first2;
  371.   const int result = memcmp(first1, first2, min(len1, len2));
  372.   return result != 0 ? result < 0 : len1 < len2;
  373. }
  374.  
  375. inline bool lexicographical_compare(const char* first1, const char* last1,
  376.                                     const char* first2, const char* last2)
  377. {
  378. #if CHAR_MAX == SCHAR_MAX
  379.   return lexicographical_compare((const signed char*) first1,
  380.                                  (const signed char*) last1,
  381.                                  (const signed char*) first2,
  382.                                  (const signed char*) last2);
  383. #else
  384.   return lexicographical_compare((const unsigned char*) first1,
  385.                                  (const unsigned char*) last1,
  386.                                  (const unsigned char*) first2,
  387.                                  (const unsigned char*) last2);
  388. #endif
  389. }
  390.  
  391. template <class InputIterator1, class InputIterator2>
  392. int lexicographical_compare_3way(InputIterator1 first1, InputIterator1 last1,
  393.                                  InputIterator2 first2, InputIterator2 last2)
  394. {
  395.   while (first1 != last1 && first2 != last2) {
  396.     if (*first1 < *first2) return -1;
  397.     if (*first2 < *first1) return 1;
  398.     ++first1; ++first2;
  399.   }
  400.   if (first2 == last2) {
  401.     return !(first1 == last1);
  402.   } else {
  403.     return -1;
  404.   }
  405. }
  406.  
  407. inline int
  408. lexicographical_compare_3way(const unsigned char* first1,
  409.                              const unsigned char* last1,
  410.                              const unsigned char* first2,
  411.                              const unsigned char* last2)
  412. {
  413.   const ptrdiff_t len1 = last1 - first1;
  414.   const ptrdiff_t len2 = last2 - first2;
  415.   const int result = memcmp(first1, first2, min(len1, len2));
  416.   return result != 0 ? result : (len1 == len2 ? 0 : (len1 < len2 ? -1 : 1));
  417. }
  418.  
  419. inline int lexicographical_compare_3way(const char* first1, const char* last1,
  420.                                         const char* first2, const char* last2)
  421. {
  422. #if CHAR_MAX == SCHAR_MAX
  423.   return lexicographical_compare_3way(
  424.                 (const signed char*) first1,
  425.                                 (const signed char*) last1,
  426.                                 (const signed char*) first2,
  427.                                 (const signed char*) last2);
  428. #else
  429.   return lexicographical_compare_3way((const unsigned char*) first1,
  430.                                       (const unsigned char*) last1,
  431.                                       (const unsigned char*) first2,
  432.                                       (const unsigned char*) last2);
  433. #endif
  434. }
  435.  
  436. __STL_END_NAMESPACE
  437.  
  438. #endif /* __SGI_STL_INTERNAL_ALGOBASE_H */
  439.  
  440. // Local Variables:
  441. // mode:C++
  442. // End:
  443.