00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00061 #ifndef _ALGOBASE_H
00062 #define _ALGOBASE_H 1
00063
00064 #include <bits/c++config.h>
00065 #include <cstring>
00066 #include <climits>
00067 #include <cstdlib>
00068 #include <cstddef>
00069 #include <iosfwd>
00070 #include <bits/stl_pair.h>
00071 #include <bits/cpp_type_traits.h>
00072 #include <bits/stl_iterator_base_types.h>
00073 #include <bits/stl_iterator_base_funcs.h>
00074 #include <bits/stl_iterator.h>
00075 #include <bits/concept_check.h>
00076 #include <debug/debug.h>
00077
00078 namespace std
00079 {
00080
00090 template<typename _Tp>
00091 inline void
00092 swap(_Tp& __a, _Tp& __b)
00093 {
00094
00095 __glibcxx_function_requires(_SGIAssignableConcept<_Tp>)
00096
00097 _Tp __tmp = __a;
00098 __a = __b;
00099 __b = __tmp;
00100 }
00101
00102
00103
00104
00105 template<bool _BoolType>
00106 struct __iter_swap
00107 {
00108 template<typename _ForwardIterator1, typename _ForwardIterator2>
00109 static void
00110 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
00111 {
00112 typedef typename iterator_traits<_ForwardIterator1>::value_type
00113 _ValueType1;
00114 _ValueType1 __tmp = *__a;
00115 *__a = *__b;
00116 *__b = __tmp;
00117 }
00118 };
00119
00120 template<>
00121 struct __iter_swap<true>
00122 {
00123 template<typename _ForwardIterator1, typename _ForwardIterator2>
00124 static void
00125 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
00126 {
00127 swap(*__a, *__b);
00128 }
00129 };
00130
00140 template<typename _ForwardIterator1, typename _ForwardIterator2>
00141 inline void
00142 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
00143 {
00144 typedef typename iterator_traits<_ForwardIterator1>::value_type
00145 _ValueType1;
00146 typedef typename iterator_traits<_ForwardIterator2>::value_type
00147 _ValueType2;
00148
00149
00150 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
00151 _ForwardIterator1>)
00152 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
00153 _ForwardIterator2>)
00154 __glibcxx_function_requires(_ConvertibleConcept<_ValueType1,
00155 _ValueType2>)
00156 __glibcxx_function_requires(_ConvertibleConcept<_ValueType2,
00157 _ValueType1>)
00158
00159 typedef typename iterator_traits<_ForwardIterator1>::reference
00160 _ReferenceType1;
00161 typedef typename iterator_traits<_ForwardIterator2>::reference
00162 _ReferenceType2;
00163 std::__iter_swap<__are_same<_ValueType1, _ValueType2>::__value &&
00164 __are_same<_ValueType1 &, _ReferenceType1>::__value &&
00165 __are_same<_ValueType2 &, _ReferenceType2>::__value>::
00166 iter_swap(__a, __b);
00167 }
00168
00169 #undef min
00170 #undef max
00171
00182 template<typename _Tp>
00183 inline const _Tp&
00184 min(const _Tp& __a, const _Tp& __b)
00185 {
00186
00187 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
00188
00189 if (__b < __a)
00190 return __b;
00191 return __a;
00192 }
00193
00204 template<typename _Tp>
00205 inline const _Tp&
00206 max(const _Tp& __a, const _Tp& __b)
00207 {
00208
00209 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
00210
00211 if (__a < __b)
00212 return __b;
00213 return __a;
00214 }
00215
00226 template<typename _Tp, typename _Compare>
00227 inline const _Tp&
00228 min(const _Tp& __a, const _Tp& __b, _Compare __comp)
00229 {
00230
00231 if (__comp(__b, __a))
00232 return __b;
00233 return __a;
00234 }
00235
00246 template<typename _Tp, typename _Compare>
00247 inline const _Tp&
00248 max(const _Tp& __a, const _Tp& __b, _Compare __comp)
00249 {
00250
00251 if (__comp(__a, __b))
00252 return __b;
00253 return __a;
00254 }
00255
00256
00257
00258
00259
00260
00261
00262 template<bool, typename>
00263 struct __copy
00264 {
00265 template<typename _II, typename _OI>
00266 static _OI
00267 copy(_II __first, _II __last, _OI __result)
00268 {
00269 for (; __first != __last; ++__result, ++__first)
00270 *__result = *__first;
00271 return __result;
00272 }
00273 };
00274
00275 template<bool _BoolType>
00276 struct __copy<_BoolType, random_access_iterator_tag>
00277 {
00278 template<typename _II, typename _OI>
00279 static _OI
00280 copy(_II __first, _II __last, _OI __result)
00281 {
00282 typedef typename iterator_traits<_II>::difference_type _Distance;
00283 for(_Distance __n = __last - __first; __n > 0; --__n)
00284 {
00285 *__result = *__first;
00286 ++__first;
00287 ++__result;
00288 }
00289 return __result;
00290 }
00291 };
00292
00293 template<>
00294 struct __copy<true, random_access_iterator_tag>
00295 {
00296 template<typename _Tp>
00297 static _Tp*
00298 copy(const _Tp* __first, const _Tp* __last, _Tp* __result)
00299 {
00300 std::memmove(__result, __first, sizeof(_Tp) * (__last - __first));
00301 return __result + (__last - __first);
00302 }
00303 };
00304
00305 template<typename _II, typename _OI>
00306 inline _OI
00307 __copy_aux(_II __first, _II __last, _OI __result)
00308 {
00309 typedef typename iterator_traits<_II>::value_type _ValueTypeI;
00310 typedef typename iterator_traits<_OI>::value_type _ValueTypeO;
00311 typedef typename iterator_traits<_II>::iterator_category _Category;
00312 const bool __simple = (__is_scalar<_ValueTypeI>::__value
00313 && __is_pointer<_II>::__value
00314 && __is_pointer<_OI>::__value
00315 && __are_same<_ValueTypeI, _ValueTypeO>::__value);
00316
00317 return std::__copy<__simple, _Category>::copy(__first, __last, __result);
00318 }
00319
00320 template<bool, bool>
00321 struct __copy_normal
00322 {
00323 template<typename _II, typename _OI>
00324 static _OI
00325 copy_n(_II __first, _II __last, _OI __result)
00326 { return std::__copy_aux(__first, __last, __result); }
00327 };
00328
00329 template<>
00330 struct __copy_normal<true, false>
00331 {
00332 template<typename _II, typename _OI>
00333 static _OI
00334 copy_n(_II __first, _II __last, _OI __result)
00335 { return std::__copy_aux(__first.base(), __last.base(), __result); }
00336 };
00337
00338 template<>
00339 struct __copy_normal<false, true>
00340 {
00341 template<typename _II, typename _OI>
00342 static _OI
00343 copy_n(_II __first, _II __last, _OI __result)
00344 { return _OI(std::__copy_aux(__first, __last, __result.base())); }
00345 };
00346
00347 template<>
00348 struct __copy_normal<true, true>
00349 {
00350 template<typename _II, typename _OI>
00351 static _OI
00352 copy_n(_II __first, _II __last, _OI __result)
00353 { return _OI(std::__copy_aux(__first.base(), __last.base(),
00354 __result.base())); }
00355 };
00356
00373 template<typename _InputIterator, typename _OutputIterator>
00374 inline _OutputIterator
00375 copy(_InputIterator __first, _InputIterator __last,
00376 _OutputIterator __result)
00377 {
00378
00379 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00380 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00381 typename iterator_traits<_InputIterator>::value_type>)
00382 __glibcxx_requires_valid_range(__first, __last);
00383
00384 const bool __in = __is_normal_iterator<_InputIterator>::__value;
00385 const bool __out = __is_normal_iterator<_OutputIterator>::__value;
00386 return std::__copy_normal<__in, __out>::copy_n(__first, __last,
00387 __result);
00388 }
00389
00390 template<bool, typename>
00391 struct __copy_backward
00392 {
00393 template<typename _BI1, typename _BI2>
00394 static _BI2
00395 copy_b(_BI1 __first, _BI1 __last, _BI2 __result)
00396 {
00397 while (__first != __last)
00398 *--__result = *--__last;
00399 return __result;
00400 }
00401 };
00402
00403 template<bool _BoolType>
00404 struct __copy_backward<_BoolType, random_access_iterator_tag>
00405 {
00406 template<typename _BI1, typename _BI2>
00407 static _BI2
00408 copy_b(_BI1 __first, _BI1 __last, _BI2 __result)
00409 {
00410 typename iterator_traits<_BI1>::difference_type __n;
00411 for (__n = __last - __first; __n > 0; --__n)
00412 *--__result = *--__last;
00413 return __result;
00414 }
00415 };
00416
00417 template<>
00418 struct __copy_backward<true, random_access_iterator_tag>
00419 {
00420 template<typename _Tp>
00421 static _Tp*
00422 copy_b(const _Tp* __first, const _Tp* __last, _Tp* __result)
00423 {
00424 const ptrdiff_t _Num = __last - __first;
00425 std::memmove(__result - _Num, __first, sizeof(_Tp) * _Num);
00426 return __result - _Num;
00427 }
00428 };
00429
00430 template<typename _BI1, typename _BI2>
00431 inline _BI2
00432 __copy_backward_aux(_BI1 __first, _BI1 __last, _BI2 __result)
00433 {
00434 typedef typename iterator_traits<_BI1>::value_type _ValueType1;
00435 typedef typename iterator_traits<_BI2>::value_type _ValueType2;
00436 typedef typename iterator_traits<_BI1>::iterator_category _Category;
00437 const bool __simple = (__is_scalar<_ValueType1>::__value
00438 && __is_pointer<_BI1>::__value
00439 && __is_pointer<_BI2>::__value
00440 && __are_same<_ValueType1, _ValueType2>::__value);
00441
00442 return std::__copy_backward<__simple, _Category>::copy_b(__first, __last,
00443 __result);
00444 }
00445
00446 template<bool, bool>
00447 struct __copy_backward_normal
00448 {
00449 template<typename _BI1, typename _BI2>
00450 static _BI2
00451 copy_b_n(_BI1 __first, _BI1 __last, _BI2 __result)
00452 { return std::__copy_backward_aux(__first, __last, __result); }
00453 };
00454
00455 template<>
00456 struct __copy_backward_normal<true, false>
00457 {
00458 template<typename _BI1, typename _BI2>
00459 static _BI2
00460 copy_b_n(_BI1 __first, _BI1 __last, _BI2 __result)
00461 { return std::__copy_backward_aux(__first.base(), __last.base(),
00462 __result); }
00463 };
00464
00465 template<>
00466 struct __copy_backward_normal<false, true>
00467 {
00468 template<typename _BI1, typename _BI2>
00469 static _BI2
00470 copy_b_n(_BI1 __first, _BI1 __last, _BI2 __result)
00471 { return _BI2(std::__copy_backward_aux(__first, __last,
00472 __result.base())); }
00473 };
00474
00475 template<>
00476 struct __copy_backward_normal<true, true>
00477 {
00478 template<typename _BI1, typename _BI2>
00479 static _BI2
00480 copy_b_n(_BI1 __first, _BI1 __last, _BI2 __result)
00481 { return _BI2(std::__copy_backward_aux(__first.base(), __last.base(),
00482 __result.base())); }
00483 };
00484
00502 template <typename _BI1, typename _BI2>
00503 inline _BI2
00504 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
00505 {
00506
00507 __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)
00508 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
00509 __glibcxx_function_requires(_ConvertibleConcept<
00510 typename iterator_traits<_BI1>::value_type,
00511 typename iterator_traits<_BI2>::value_type>)
00512 __glibcxx_requires_valid_range(__first, __last);
00513
00514 const bool __bi1 = __is_normal_iterator<_BI1>::__value;
00515 const bool __bi2 = __is_normal_iterator<_BI2>::__value;
00516 return std::__copy_backward_normal<__bi1, __bi2>::copy_b_n(__first, __last,
00517 __result);
00518 }
00519
00520 template<bool>
00521 struct __fill
00522 {
00523 template<typename _ForwardIterator, typename _Tp>
00524 static void
00525 fill(_ForwardIterator __first, _ForwardIterator __last,
00526 const _Tp& __value)
00527 {
00528 for (; __first != __last; ++__first)
00529 *__first = __value;
00530 }
00531 };
00532
00533 template<>
00534 struct __fill<true>
00535 {
00536 template<typename _ForwardIterator, typename _Tp>
00537 static void
00538 fill(_ForwardIterator __first, _ForwardIterator __last,
00539 const _Tp& __value)
00540 {
00541 const _Tp __tmp = __value;
00542 for (; __first != __last; ++__first)
00543 *__first = __tmp;
00544 }
00545 };
00546
00558 template<typename _ForwardIterator, typename _Tp>
00559 void
00560 fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
00561 {
00562
00563 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
00564 _ForwardIterator>)
00565 __glibcxx_requires_valid_range(__first, __last);
00566
00567 const bool __scalar = __is_scalar<_Tp>::__value;
00568 std::__fill<__scalar>::fill(__first, __last, __value);
00569 }
00570
00571
00572 inline void
00573 fill(unsigned char* __first, unsigned char* __last, const unsigned char& __c)
00574 {
00575 __glibcxx_requires_valid_range(__first, __last);
00576 const unsigned char __tmp = __c;
00577 std::memset(__first, __tmp, __last - __first);
00578 }
00579
00580 inline void
00581 fill(signed char* __first, signed char* __last, const signed char& __c)
00582 {
00583 __glibcxx_requires_valid_range(__first, __last);
00584 const signed char __tmp = __c;
00585 std::memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
00586 }
00587
00588 inline void
00589 fill(char* __first, char* __last, const char& __c)
00590 {
00591 __glibcxx_requires_valid_range(__first, __last);
00592 const char __tmp = __c;
00593 std::memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
00594 }
00595
00596 template<bool>
00597 struct __fill_n
00598 {
00599 template<typename _OutputIterator, typename _Size, typename _Tp>
00600 static _OutputIterator
00601 fill_n(_OutputIterator __first, _Size __n, const _Tp& __value)
00602 {
00603 for (; __n > 0; --__n, ++__first)
00604 *__first = __value;
00605 return __first;
00606 }
00607 };
00608
00609 template<>
00610 struct __fill_n<true>
00611 {
00612 template<typename _OutputIterator, typename _Size, typename _Tp>
00613 static _OutputIterator
00614 fill_n(_OutputIterator __first, _Size __n, const _Tp& __value)
00615 {
00616 const _Tp __tmp = __value;
00617 for (; __n > 0; --__n, ++__first)
00618 *__first = __tmp;
00619 return __first;
00620 }
00621 };
00622
00634 template<typename _OutputIterator, typename _Size, typename _Tp>
00635 _OutputIterator
00636 fill_n(_OutputIterator __first, _Size __n, const _Tp& __value)
00637 {
00638
00639 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, _Tp>)
00640
00641 const bool __scalar = __is_scalar<_Tp>::__value;
00642 return std::__fill_n<__scalar>::fill_n(__first, __n, __value);
00643 }
00644
00645 template<typename _Size>
00646 inline unsigned char*
00647 fill_n(unsigned char* __first, _Size __n, const unsigned char& __c)
00648 {
00649 std::fill(__first, __first + __n, __c);
00650 return __first + __n;
00651 }
00652
00653 template<typename _Size>
00654 inline signed char*
00655 fill_n(char* __first, _Size __n, const signed char& __c)
00656 {
00657 std::fill(__first, __first + __n, __c);
00658 return __first + __n;
00659 }
00660
00661 template<typename _Size>
00662 inline char*
00663 fill_n(char* __first, _Size __n, const char& __c)
00664 {
00665 std::fill(__first, __first + __n, __c);
00666 return __first + __n;
00667 }
00668
00681 template<typename _InputIterator1, typename _InputIterator2>
00682 pair<_InputIterator1, _InputIterator2>
00683 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
00684 _InputIterator2 __first2)
00685 {
00686
00687 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
00688 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
00689 __glibcxx_function_requires(_EqualOpConcept<
00690 typename iterator_traits<_InputIterator1>::value_type,
00691 typename iterator_traits<_InputIterator2>::value_type>)
00692 __glibcxx_requires_valid_range(__first1, __last1);
00693
00694 while (__first1 != __last1 && *__first1 == *__first2)
00695 {
00696 ++__first1;
00697 ++__first2;
00698 }
00699 return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
00700 }
00701
00716 template<typename _InputIterator1, typename _InputIterator2,
00717 typename _BinaryPredicate>
00718 pair<_InputIterator1, _InputIterator2>
00719 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
00720 _InputIterator2 __first2, _BinaryPredicate __binary_pred)
00721 {
00722
00723 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
00724 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
00725 __glibcxx_requires_valid_range(__first1, __last1);
00726
00727 while (__first1 != __last1 && __binary_pred(*__first1, *__first2))
00728 {
00729 ++__first1;
00730 ++__first2;
00731 }
00732 return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
00733 }
00734
00746 template<typename _InputIterator1, typename _InputIterator2>
00747 inline bool
00748 equal(_InputIterator1 __first1, _InputIterator1 __last1,
00749 _InputIterator2 __first2)
00750 {
00751
00752 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
00753 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
00754 __glibcxx_function_requires(_EqualOpConcept<
00755 typename iterator_traits<_InputIterator1>::value_type,
00756 typename iterator_traits<_InputIterator2>::value_type>)
00757 __glibcxx_requires_valid_range(__first1, __last1);
00758
00759 for (; __first1 != __last1; ++__first1, ++__first2)
00760 if (!(*__first1 == *__first2))
00761 return false;
00762 return true;
00763 }
00764
00778 template<typename _InputIterator1, typename _InputIterator2,
00779 typename _BinaryPredicate>
00780 inline bool
00781 equal(_InputIterator1 __first1, _InputIterator1 __last1,
00782 _InputIterator2 __first2,
00783 _BinaryPredicate __binary_pred)
00784 {
00785
00786 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
00787 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
00788 __glibcxx_requires_valid_range(__first1, __last1);
00789
00790 for (; __first1 != __last1; ++__first1, ++__first2)
00791 if (!__binary_pred(*__first1, *__first2))
00792 return false;
00793 return true;
00794 }
00795
00810 template<typename _InputIterator1, typename _InputIterator2>
00811 bool
00812 lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
00813 _InputIterator2 __first2, _InputIterator2 __last2)
00814 {
00815
00816 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
00817 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
00818 __glibcxx_function_requires(_LessThanOpConcept<
00819 typename iterator_traits<_InputIterator1>::value_type,
00820 typename iterator_traits<_InputIterator2>::value_type>)
00821 __glibcxx_function_requires(_LessThanOpConcept<
00822 typename iterator_traits<_InputIterator2>::value_type,
00823 typename iterator_traits<_InputIterator1>::value_type>)
00824 __glibcxx_requires_valid_range(__first1, __last1);
00825 __glibcxx_requires_valid_range(__first2, __last2);
00826
00827 for (; __first1 != __last1 && __first2 != __last2;
00828 ++__first1, ++__first2)
00829 {
00830 if (*__first1 < *__first2)
00831 return true;
00832 if (*__first2 < *__first1)
00833 return false;
00834 }
00835 return __first1 == __last1 && __first2 != __last2;
00836 }
00837
00850 template<typename _InputIterator1, typename _InputIterator2,
00851 typename _Compare>
00852 bool
00853 lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
00854 _InputIterator2 __first2, _InputIterator2 __last2,
00855 _Compare __comp)
00856 {
00857
00858 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
00859 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
00860 __glibcxx_requires_valid_range(__first1, __last1);
00861 __glibcxx_requires_valid_range(__first2, __last2);
00862
00863 for (; __first1 != __last1 && __first2 != __last2;
00864 ++__first1, ++__first2)
00865 {
00866 if (__comp(*__first1, *__first2))
00867 return true;
00868 if (__comp(*__first2, *__first1))
00869 return false;
00870 }
00871 return __first1 == __last1 && __first2 != __last2;
00872 }
00873
00874 inline bool
00875 lexicographical_compare(const unsigned char* __first1,
00876 const unsigned char* __last1,
00877 const unsigned char* __first2,
00878 const unsigned char* __last2)
00879 {
00880 __glibcxx_requires_valid_range(__first1, __last1);
00881 __glibcxx_requires_valid_range(__first2, __last2);
00882
00883 const size_t __len1 = __last1 - __first1;
00884 const size_t __len2 = __last2 - __first2;
00885 const int __result = std::memcmp(__first1, __first2,
00886 std::min(__len1, __len2));
00887 return __result != 0 ? __result < 0 : __len1 < __len2;
00888 }
00889
00890 inline bool
00891 lexicographical_compare(const char* __first1, const char* __last1,
00892 const char* __first2, const char* __last2)
00893 {
00894 __glibcxx_requires_valid_range(__first1, __last1);
00895 __glibcxx_requires_valid_range(__first2, __last2);
00896
00897 #if CHAR_MAX == SCHAR_MAX
00898 return std::lexicographical_compare((const signed char*) __first1,
00899 (const signed char*) __last1,
00900 (const signed char*) __first2,
00901 (const signed char*) __last2);
00902 #else
00903 return std::lexicographical_compare((const unsigned char*) __first1,
00904 (const unsigned char*) __last1,
00905 (const unsigned char*) __first2,
00906 (const unsigned char*) __last2);
00907 #endif
00908 }
00909
00910 }
00911
00912 #endif