104 #ifndef EASTL_ALGORITHM_H 105 #define EASTL_ALGORITHM_H 108 #include <stk_util/util/config_eastl.h> 109 #include <stk_util/util/utility_eastl.h> 110 #include <stk_util/util/iterator_eastl.h> 111 #include <stk_util/util/functional_eastl.h> 112 #include <stk_util/util/generic_iterator_eastl.h> 113 #include <stk_util/util/type_traits_eastl.h> 116 #pragma warning(push, 0) 120 #include <../Include/string.h> 151 #if EASTL_MINMAX_ENABLED 167 template <
typename T>
169 min(
const T& a,
const T& b)
171 return b < a ? b : a;
173 #endif // EASTL_MINMAX_ENABLED 183 template <
typename T>
187 return b < a ? b : a;
190 #if EASTL_MINMAX_ENABLED 191 template <
typename T,
typename Compare>
217 min(
const T& a,
const T& b, Compare compare)
219 return compare(b, a) ? b : a;
222 #endif // EASTL_MINMAX_ENABLED 232 template <
typename T,
typename Compare>
234 min_alt(
const T& a,
const T& b, Compare compare)
236 return compare(b, a) ? b : a;
240 #if EASTL_MINMAX_ENABLED 241 template <
typename T>
257 max(
const T& a,
const T& b)
259 return a < b ? b : a;
261 #endif // EASTL_MINMAX_ENABLED 269 template <
typename T>
273 return a < b ? b : a;
276 #if EASTL_MINMAX_ENABLED 277 template <
typename T,
typename Compare>
287 max(
const T& a,
const T& b, Compare compare)
289 return compare(a, b) ? b : a;
300 template <
typename T,
typename Compare>
302 max_alt(
const T& a,
const T& b, Compare compare)
304 return compare(a, b) ? b : a;
323 template <
typename ForwardIterator>
324 ForwardIterator
min_element(ForwardIterator first, ForwardIterator last)
328 ForwardIterator currentMin = first;
330 while(++first != last)
332 if(*first < *currentMin)
355 template <
typename ForwardIterator,
typename Compare>
356 ForwardIterator
min_element(ForwardIterator first, ForwardIterator last, Compare compare)
360 ForwardIterator currentMin = first;
362 while(++first != last)
364 if(compare(*first, *currentMin))
387 template <
typename ForwardIterator>
388 ForwardIterator
max_element(ForwardIterator first, ForwardIterator last)
392 ForwardIterator currentMax = first;
394 while(++first != last)
396 if(*currentMax < *first)
419 template <
typename ForwardIterator,
typename Compare>
420 ForwardIterator
max_element(ForwardIterator first, ForwardIterator last, Compare compare)
424 ForwardIterator currentMax = first;
426 while(++first != last)
428 if(compare(*currentMax, *first))
445 template <
typename T>
446 inline const T&
median(
const T& a,
const T& b,
const T& c)
473 template <
typename T,
typename Compare>
474 inline const T&
median(
const T& a,
const T& b,
const T& c, Compare compare)
480 else if(compare(a, c))
485 else if(compare(a, c))
487 else if(compare(b, c))
505 template <
typename T>
517 template <
bool bTypesAreEqual>
518 struct iter_swap_impl
520 template <
typename ForwardIterator1,
typename ForwardIterator2>
521 static void iter_swap(ForwardIterator1 a, ForwardIterator2 b)
523 typedef typename eastl::iterator_traits<ForwardIterator1>::value_type value_type_a;
525 value_type_a temp(*a);
532 struct iter_swap_impl<true>
534 template <
typename ForwardIterator1,
typename ForwardIterator2>
535 static void iter_swap(ForwardIterator1 a, ForwardIterator2 b)
551 template <
typename ForwardIterator1,
typename ForwardIterator2>
552 inline void iter_swap(ForwardIterator1 a, ForwardIterator2 b)
554 typedef typename eastl::iterator_traits<ForwardIterator1>::value_type value_type_a;
555 typedef typename eastl::iterator_traits<ForwardIterator2>::value_type value_type_b;
556 typedef typename eastl::iterator_traits<ForwardIterator1>::reference reference_a;
557 typedef typename eastl::iterator_traits<ForwardIterator2>::reference reference_b;
559 iter_swap_impl<type_and<is_same<value_type_a, value_type_b>::value, is_same<value_type_a&, reference_a>::value, is_same<value_type_b&, reference_b>::value >::value >
::iter_swap(a, b);
579 template <
typename ForwardIterator1,
typename ForwardIterator2>
580 inline ForwardIterator2
581 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2)
583 for(; first1 != last1; ++first1, ++first2)
598 template <
typename ForwardIterator>
599 inline ForwardIterator
604 ForwardIterator i = first;
606 for(++i; i != last; ++i)
626 template <
typename ForwardIterator,
typename BinaryPredicate>
627 inline ForwardIterator
628 adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate predicate)
632 ForwardIterator i = first;
634 for(++i; i != last; ++i)
636 if(predicate(*first, *i))
653 template <
bool bHasTrivialCopy,
typename IteratorTag>
656 template <
typename InputIterator,
typename OutputIterator>
657 static OutputIterator do_copy(InputIterator first, InputIterator last, OutputIterator result)
659 for(; first != last; ++result, ++first)
666 struct copy_impl<true, EASTL_ITC_NS::random_access_iterator_tag>
668 template <
typename T>
669 static T* do_copy(
const T* first,
const T* last, T* result)
674 return (T*)memmove(result, first, (
size_t)((uintptr_t)last - (uintptr_t)first)) + (last - first);
680 template <
typename InputIterator,
typename OutputIterator>
681 inline OutputIterator
682 copy_chooser(InputIterator first, InputIterator last, OutputIterator result)
684 typedef typename eastl::iterator_traits<InputIterator>::iterator_category IC;
685 typedef typename eastl::iterator_traits<InputIterator>::value_type value_type_input;
686 typedef typename eastl::iterator_traits<OutputIterator>::value_type value_type_output;
688 const bool bHasTrivialCopy = type_and<has_trivial_assign<value_type_input>::value,
689 is_pointer<InputIterator>::value,
690 is_pointer<OutputIterator>::value,
691 is_same<value_type_input, value_type_output>::value>::value;
693 return eastl::copy_impl<bHasTrivialCopy, IC>::do_copy(first, last, result);
703 template <
bool bInputIsGenericIterator,
bool bOutputIsGenericIterator>
704 struct copy_generic_iterator
706 template <
typename InputIterator,
typename OutputIterator>
707 static OutputIterator do_copy(InputIterator first, InputIterator last, OutputIterator result)
709 return eastl::copy_chooser(first, last, result);
714 struct copy_generic_iterator<true, false>
716 template <
typename InputIterator,
typename OutputIterator>
717 static OutputIterator do_copy(InputIterator first, InputIterator last, OutputIterator result)
719 return eastl::copy_chooser(first.base(), last.base(), result);
724 struct copy_generic_iterator<false, true>
726 template <
typename InputIterator,
typename OutputIterator>
727 static OutputIterator do_copy(InputIterator first, InputIterator last, OutputIterator result)
729 return OutputIterator(eastl::copy_chooser(first, last, result.base()));
734 struct copy_generic_iterator<true, true>
736 template <
typename InputIterator,
typename OutputIterator>
737 static OutputIterator do_copy(InputIterator first, InputIterator last, OutputIterator result)
739 return OutputIterator(eastl::copy_chooser(first.base(), last.base(), result.base()));
759 template <
typename InputIterator,
typename OutputIterator>
760 inline OutputIterator
761 copy(InputIterator first, InputIterator last, OutputIterator result)
768 return eastl::copy_generic_iterator<bInputIsGenericIterator, bOutputIsGenericIterator>::do_copy(first, last, result);
781 template <
bool bHasTrivialCopy,
typename IteratorTag>
782 struct copy_backward_impl
784 template <
typename B
idirectionalIterator1,
typename B
idirectionalIterator2>
785 static BidirectionalIterator2 do_copy(BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 result)
794 struct copy_backward_impl<true, EASTL_ITC_NS::random_access_iterator_tag>
796 template <
typename T>
797 static T* do_copy(
const T* first,
const T* last, T* result)
799 return (T*)memmove(result - (last - first), first, (
size_t)((uintptr_t)last - (uintptr_t)first));
805 template <
typename InputIterator,
typename OutputIterator>
806 inline OutputIterator
807 copy_backward_chooser(InputIterator first, InputIterator last, OutputIterator result)
809 typedef typename eastl::iterator_traits<InputIterator>::iterator_category IC;
810 typedef typename eastl::iterator_traits<InputIterator>::value_type value_type_input;
811 typedef typename eastl::iterator_traits<OutputIterator>::value_type value_type_output;
813 const bool bHasTrivialCopy = type_and<has_trivial_assign<value_type_input>::value,
814 is_pointer<InputIterator>::value,
815 is_pointer<OutputIterator>::value,
816 is_same<value_type_input, value_type_output>::value>::value;
818 return eastl::copy_backward_impl<bHasTrivialCopy, IC>::do_copy(first, last, result);
828 template <
bool bInputIsGenericIterator,
bool bOutputIsGenericIterator>
829 struct copy_backward_generic_iterator
831 template <
typename InputIterator,
typename OutputIterator>
832 static OutputIterator do_copy(InputIterator first, InputIterator last, OutputIterator result)
834 return eastl::copy_backward_chooser(first, last, result);
839 struct copy_backward_generic_iterator<true, false>
841 template <
typename InputIterator,
typename OutputIterator>
842 static OutputIterator do_copy(InputIterator first, InputIterator last, OutputIterator result)
844 return eastl::copy_backward_chooser(first.base(), last.base(), result);
849 struct copy_backward_generic_iterator<false, true>
851 template <
typename InputIterator,
typename OutputIterator>
852 static OutputIterator do_copy(InputIterator first, InputIterator last, OutputIterator result)
854 return OutputIterator(eastl::copy_backward_chooser(first, last, result.base()));
859 struct copy_backward_generic_iterator<true, true>
861 template <
typename InputIterator,
typename OutputIterator>
862 static OutputIterator do_copy(InputIterator first, InputIterator last, OutputIterator result)
864 return OutputIterator(eastl::copy_backward_chooser(first.base(), last.base(), result.base()));
882 template <
typename B
idirectionalIterator1,
typename B
idirectionalIterator2>
883 inline BidirectionalIterator2
884 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 result)
889 return eastl::copy_backward_generic_iterator<bInputIsGenericIterator, bOutputIsGenericIterator>::do_copy(first, last, result);
906 template <
typename InputIterator,
typename T>
907 inline typename eastl::iterator_traits<InputIterator>::difference_type
908 count(InputIterator first, InputIterator last,
const T& value)
910 typename eastl::iterator_traits<InputIterator>::difference_type result = 0;
912 for(; first != last; ++first)
934 template <
typename InputIterator,
typename Predicate>
935 inline typename eastl::iterator_traits<InputIterator>::difference_type
936 count_if(InputIterator first, InputIterator last, Predicate predicate)
938 typename eastl::iterator_traits<InputIterator>::difference_type result = 0;
940 for(; first != last; ++first)
942 if(predicate(*first))
955 template <
bool bIsScalar>
958 template <
typename ForwardIterator,
typename T>
959 static void do_fill(ForwardIterator first, ForwardIterator last,
const T& value)
963 for(; first != last; ++first)
969 struct fill_imp<true>
971 template <
typename ForwardIterator,
typename T>
972 static void do_fill(ForwardIterator first, ForwardIterator last,
const T& value)
977 for(
const T temp(value); first != last; ++first)
998 template <
typename ForwardIterator,
typename T>
999 inline void fill(ForwardIterator first, ForwardIterator last,
const T& value)
1001 eastl::fill_imp< is_scalar<T>::value >::do_fill(first, last, value);
1012 inline void fill(
char* first,
char* last,
const char& c)
1014 memset(first, (
unsigned char)c, (
size_t)(last - first));
1017 inline void fill(
char* first,
char* last,
const int c)
1019 memset(first, (
unsigned char)c, (
size_t)(last - first));
1022 inline void fill(
unsigned char* first,
unsigned char* last,
const unsigned char& c)
1024 memset(first, (
unsigned char)c, (
size_t)(last - first));
1027 inline void fill(
unsigned char* first,
unsigned char* last,
const int c)
1029 memset(first, (
unsigned char)c, (
size_t)(last - first));
1032 inline void fill(
signed char* first,
signed char* last,
const signed char& c)
1034 memset(first, (
unsigned char)c, (
size_t)(last - first));
1037 inline void fill(
signed char* first,
signed char* last,
const int c)
1039 memset(first, (
unsigned char)c, (
size_t)(last - first));
1042 #if defined(_MSC_VER) || defined(__BORLANDC__) || defined(__SNC__) || defined(__ICL) || defined(__PPU__) || defined(__SPU__) // SN = SN compiler, ICL = Intel compiler, PPU == PS3 processor, SPU = PS3 cell processor 1043 inline void fill(
bool* first,
bool* last,
const bool& b)
1045 memset(first, (
char)b, (
size_t)(last - first));
1057 template <
bool bIsScalar>
1060 template <
typename OutputIterator,
typename Size,
typename T>
1061 static OutputIterator do_fill(OutputIterator first, Size n,
const T& value)
1063 for(; n-- > 0; ++first)
1070 struct fill_n_imp<true>
1072 template <
typename OutputIterator,
typename Size,
typename T>
1073 static OutputIterator do_fill(OutputIterator first, Size n,
const T& value)
1078 for(
const T temp = value; n-- > 0; ++first)
1094 template <
typename OutputIterator,
typename Size,
typename T>
1095 OutputIterator
fill_n(OutputIterator first, Size n,
const T& value)
1097 #ifdef _MSC_VER // VC++ up to and including VC8 blow up when you pass a 64 bit scalar to the do_fill function. 1098 return eastl::fill_n_imp< is_scalar<T>::value && (
sizeof(T) <=
sizeof(uint32_t)) >::do_fill(first, n, value);
1100 return eastl::fill_n_imp< is_scalar<T>::value >::do_fill(first, n, value);
1104 template <
typename Size>
1105 inline char*
fill_n(
char* first, Size n,
const char& c)
1107 return (
char*)memset(first, (
char)c, (
size_t)n) + n;
1110 template <
typename Size>
1111 inline unsigned char*
fill_n(
unsigned char* first, Size n,
const unsigned char& c)
1113 return (
unsigned char*)memset(first, (
unsigned char)c, (
size_t)n) + n;
1116 template <
typename Size>
1117 inline signed char*
fill_n(
signed char* first, Size n,
const signed char& c)
1119 return (
signed char*)memset(first, (
signed char)c, n) + (size_t)n;
1122 #if defined(_MSC_VER) || defined(__BORLANDC__) || defined(__SNC__) || defined(__ICL) || defined(__PPU__) || defined(__SPU__) // SN = SN compiler, ICL = Intel compiler, PU == PS3 processor, SPU = PS3 cell processor 1123 template <
typename Size>
1124 inline bool*
fill_n(
bool* first, Size n,
const bool& b)
1126 return (
bool*)memset(first, (
char)b, n) + (size_t)n;
1146 template <
typename InputIterator,
typename T>
1147 inline InputIterator
1148 find(InputIterator first, InputIterator last,
const T& value)
1150 while((first != last) && !(*first == value))
1172 template <
typename InputIterator,
typename Predicate>
1173 inline InputIterator
1174 find_if(InputIterator first, InputIterator last, Predicate predicate)
1176 while((first != last) && !predicate(*first))
1203 template <
typename ForwardIterator1,
typename ForwardIterator2>
1206 ForwardIterator2 first2, ForwardIterator2 last2)
1208 for(; first1 != last1; ++first1)
1210 for(ForwardIterator2 i = first2; i != last2; ++i)
1238 template <
typename ForwardIterator1,
typename ForwardIterator2,
typename BinaryPredicate>
1241 ForwardIterator2 first2, ForwardIterator2 last2,
1242 BinaryPredicate predicate)
1244 for(; first1 != last1; ++first1)
1246 for(ForwardIterator2 i = first2; i != last2; ++i)
1248 if(predicate(*first1, *i))
1268 template<
class ForwardIterator1,
class ForwardIterator2>
1271 ForwardIterator2 first2, ForwardIterator2 last2)
1273 for(; first1 != last1; ++first1)
1296 template<
class ForwardIterator1,
class ForwardIterator2,
class BinaryPredicate>
1297 inline ForwardIterator1
1299 ForwardIterator2 first2, ForwardIterator2 last2,
1300 BinaryPredicate predicate)
1302 typedef typename eastl::iterator_traits<ForwardIterator1>::value_type value_type;
1304 for(; first1 != last1; ++first1)
1306 if(
eastl::find_if(first2, last2, eastl::bind1st<BinaryPredicate, value_type>(predicate, *first1)) == last2)
1314 template<
class B
idirectionalIterator1,
class ForwardIterator2>
1315 inline BidirectionalIterator1
1316 find_last_of(BidirectionalIterator1 first1, BidirectionalIterator1 last1,
1317 ForwardIterator2 first2, ForwardIterator2 last2)
1319 if((first1 != last1) && (first2 != last2))
1321 BidirectionalIterator1 it1(last1);
1323 while((--it1 != first1) && (
eastl::find(first2, last2, *it1) == last2))
1326 if((it1 != first1) || (
eastl::find(first2, last2, *it1) != last2))
1334 template<
class B
idirectionalIterator1,
class ForwardIterator2,
class BinaryPredicate>
1335 BidirectionalIterator1
1336 find_last_of(BidirectionalIterator1 first1, BidirectionalIterator1 last1,
1337 ForwardIterator2 first2, ForwardIterator2 last2,
1338 BinaryPredicate predicate)
1340 typedef typename eastl::iterator_traits<BidirectionalIterator1>::value_type value_type;
1342 if((first1 != last1) && (first2 != last2))
1344 BidirectionalIterator1 it1(last1);
1346 while((--it1 != first1) && (
eastl::find_if(first2, last2, eastl::bind1st<BinaryPredicate, value_type>(predicate, *it1)) == last2))
1349 if((it1 != first1) || (
eastl::find_if(first2, last2, eastl::bind1st<BinaryPredicate, value_type>(predicate, *it1)) != last2))
1357 template<
class B
idirectionalIterator1,
class ForwardIterator2>
1358 inline BidirectionalIterator1
1359 find_last_not_of(BidirectionalIterator1 first1, BidirectionalIterator1 last1,
1360 ForwardIterator2 first2, ForwardIterator2 last2)
1362 if((first1 != last1) && (first2 != last2))
1364 BidirectionalIterator1 it1(last1);
1366 while((--it1 != first1) && (
eastl::find(first2, last2, *it1) != last2))
1369 if((it1 != first1) || (
eastl::find( first2, last2, *it1) == last2))
1377 template<
class B
idirectionalIterator1,
class ForwardIterator2,
class BinaryPredicate>
1378 inline BidirectionalIterator1
1379 find_last_not_of(BidirectionalIterator1 first1, BidirectionalIterator1 last1,
1380 ForwardIterator2 first2, ForwardIterator2 last2,
1381 BinaryPredicate predicate)
1383 typedef typename eastl::iterator_traits<BidirectionalIterator1>::value_type value_type;
1385 if((first1 != last1) && (first2 != last2))
1387 BidirectionalIterator1 it1(last1);
1389 while((--it1 != first1) && (
eastl::find_if(first2, last2, eastl::bind1st<BinaryPredicate, value_type>(predicate, *it1)) != last2))
1392 if((it1 != first1) || (
eastl::find_if(first2, last2, eastl::bind1st<BinaryPredicate, value_type>(predicate, *it1))) != last2)
1416 template <
typename InputIterator,
typename Function>
1418 for_each(InputIterator first, InputIterator last, Function
function)
1420 for(; first != last; ++first)
1434 template <
typename ForwardIterator,
typename Generator>
1436 generate(ForwardIterator first, ForwardIterator last, Generator generator)
1438 for(; first != last; ++first)
1439 *first = generator();
1451 template <
typename OutputIterator,
typename Size,
typename Generator>
1452 inline OutputIterator
1455 for(; n > 0; --n, ++first)
1456 *first = generator();
1477 template <
typename InputIterator,
typename OutputIterator,
typename UnaryOperation>
1478 inline OutputIterator
1479 transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation unaryOperation)
1481 for(; first != last; ++first, ++result)
1482 *result = unaryOperation(*first);
1503 template <
typename InputIterator1,
typename InputIterator2,
typename OutputIterator,
typename BinaryOperation>
1504 inline OutputIterator
1505 transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryOperation binaryOperation)
1507 for(; first1 != last1; ++first1, ++first2, ++result)
1508 *result = binaryOperation(*first1, *first2);
1525 template <
typename InputIterator1,
typename InputIterator2>
1527 equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2)
1529 for(; first1 != last1; ++first1, ++first2)
1531 if(!(*first1 == *first2))
1545 template <
typename InputIterator1,
typename InputIterator2,
typename BinaryPredicate>
1547 equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate predicate)
1549 for(; first1 != last1; ++first1, ++first2)
1551 if(!predicate(*first1, *first2))
1578 template <
typename InputIterator1,
typename InputIterator2>
1580 InputIterator2 first2, InputIterator2 last2)
1582 while((first1 != last1) && (first2 != last2) && (*first1 == *first2))
1587 return (first1 == last1) && (first2 == last2);
1593 template <
typename InputIterator1,
typename InputIterator2,
typename BinaryPredicate>
1595 InputIterator2 first2, InputIterator2 last2, BinaryPredicate predicate)
1597 while((first1 != last1) && (first2 != last2) && predicate(*first1, *first2))
1602 return (first1 == last1) && (first2 == last2);
1623 template <
typename InputIterator1,
typename InputIterator2>
1627 for(; (first1 != last1) && (first2 != last2); ++first1, ++first2)
1629 if(*first1 < *first2)
1631 if(*first2 < *first1)
1634 return (first1 == last1) && (first2 != last2);
1640 const ptrdiff_t n1(last1 - first1), n2(last2 - first2);
1641 const int result = memcmp(first1, first2, (
size_t)
eastl::min_alt(n1, n2));
1642 return result ? (result < 0) : (n1 < n2);
1648 const ptrdiff_t n1(last1 - first1), n2(last2 - first2);
1649 const int result = memcmp(first1, first2, (
size_t)
eastl::min_alt(n1, n2));
1650 return result ? (result < 0) : (n1 < n2);
1654 lexicographical_compare(
const unsigned char* first1,
const unsigned char* last1,
const unsigned char* first2,
const unsigned char* last2)
1656 const ptrdiff_t n1(last1 - first1), n2(last2 - first2);
1657 const int result = memcmp(first1, first2, (
size_t)
eastl::min_alt(n1, n2));
1658 return result ? (result < 0) : (n1 < n2);
1662 lexicographical_compare(
unsigned char* first1,
unsigned char* last1,
unsigned char* first2,
unsigned char* last2)
1664 const ptrdiff_t n1(last1 - first1), n2(last2 - first2);
1665 const int result = memcmp(first1, first2, (
size_t)
eastl::min_alt(n1, n2));
1666 return result ? (result < 0) : (n1 < n2);
1670 lexicographical_compare(
const signed char* first1,
const signed char* last1,
const signed char* first2,
const signed char* last2)
1672 const ptrdiff_t n1(last1 - first1), n2(last2 - first2);
1673 const int result = memcmp(first1, first2, (
size_t)
eastl::min_alt(n1, n2));
1674 return result ? (result < 0) : (n1 < n2);
1680 const ptrdiff_t n1(last1 - first1), n2(last2 - first2);
1681 const int result = memcmp(first1, first2, (
size_t)
eastl::min_alt(n1, n2));
1682 return result ? (result < 0) : (n1 < n2);
1685 #if defined(_MSC_VER) // If using the VC++ compiler (and thus bool is known to be a single byte)... 1729 template <
typename InputIterator1,
typename InputIterator2,
typename Compare>
1732 InputIterator2 first2, InputIterator2 last2, Compare compare)
1734 for(; (first1 != last1) && (first2 != last2); ++first1, ++first2)
1736 if(compare(*first1, *first2))
1738 if(compare(*first2, *first1))
1741 return (first1 == last1) && (first2 != last2);
1764 template <
typename ForwardIterator,
typename T>
1766 lower_bound(ForwardIterator first, ForwardIterator last,
const T& value)
1768 typedef typename eastl::iterator_traits<ForwardIterator>::difference_type DifferenceType;
1770 DifferenceType d = eastl::distance(first, last);
1774 ForwardIterator i = first;
1775 DifferenceType d2 = d >> 1;
1777 eastl::advance(i, d2);
1812 template <
typename ForwardIterator,
typename T,
typename Compare>
1814 lower_bound(ForwardIterator first, ForwardIterator last,
const T& value, Compare compare)
1816 typedef typename eastl::iterator_traits<ForwardIterator>::difference_type DifferenceType;
1818 DifferenceType d = eastl::distance(first, last);
1822 ForwardIterator i = first;
1823 DifferenceType d2 = d >> 1;
1825 eastl::advance(i, d2);
1827 if(compare(*i, value))
1855 template <
typename ForwardIterator,
typename T>
1857 upper_bound(ForwardIterator first, ForwardIterator last,
const T& value)
1859 typedef typename eastl::iterator_traits<ForwardIterator>::difference_type DifferenceType;
1861 DifferenceType len = eastl::distance(first, last);
1865 ForwardIterator i = first;
1866 DifferenceType len2 = len >> 1;
1868 eastl::advance(i, len2);
1901 template <
typename ForwardIterator,
typename T,
typename Compare>
1903 upper_bound(ForwardIterator first, ForwardIterator last,
const T& value, Compare compare)
1905 typedef typename eastl::iterator_traits<ForwardIterator>::difference_type DifferenceType;
1907 DifferenceType len = eastl::distance(first, last);
1911 ForwardIterator i = first;
1912 DifferenceType len2 = len >> 1;
1914 eastl::advance(i, len2);
1916 if(!compare(value, *i))
1939 template <
typename ForwardIterator,
typename T>
1940 pair<ForwardIterator, ForwardIterator>
1941 equal_range(ForwardIterator first, ForwardIterator last,
const T& value)
1944 typedef typename eastl::iterator_traits<ForwardIterator>::difference_type DifferenceType;
1946 DifferenceType d = eastl::distance(first, last);
1950 ForwardIterator i(first);
1951 DifferenceType d2 = d >> 1;
1953 eastl::advance(i, d2);
1957 EASTL_VALIDATE_COMPARE(!(value < *i));
1963 EASTL_VALIDATE_COMPARE(!(*i < value));
1969 ForwardIterator j(i);
1975 return ResultType(first, first);
1987 template <
typename ForwardIterator,
typename T,
typename Compare>
1988 pair<ForwardIterator, ForwardIterator>
1989 equal_range(ForwardIterator first, ForwardIterator last,
const T& value, Compare compare)
1992 typedef typename eastl::iterator_traits<ForwardIterator>::difference_type DifferenceType;
1994 DifferenceType d = eastl::distance(first, last);
1998 ForwardIterator i(first);
1999 DifferenceType d2 = d >> 1;
2001 eastl::advance(i, d2);
2003 if(compare(*i, value))
2005 EASTL_VALIDATE_COMPARE(!compare(value, *i));
2009 else if(compare(value, *i))
2011 EASTL_VALIDATE_COMPARE(!compare(*i, value));
2017 ForwardIterator j(i);
2023 return ResultType(first, first);
2037 template <
typename ForwardIterator,
typename T>
2039 replace(ForwardIterator first, ForwardIterator last,
const T& old_value,
const T& new_value)
2041 for(; first != last; ++first)
2043 if(*first == old_value)
2059 template <
typename ForwardIterator,
typename Predicate,
typename T>
2061 replace_if(ForwardIterator first, ForwardIterator last, Predicate predicate,
const T& new_value)
2063 for(; first != last; ++first)
2065 if(predicate(*first))
2083 template <
typename InputIterator,
typename OutputIterator,
typename T>
2084 inline OutputIterator
2085 remove_copy(InputIterator first, InputIterator last, OutputIterator result,
const T& value)
2087 for(; first != last; ++first)
2089 if(!(*first == value))
2111 template <
typename InputIterator,
typename OutputIterator,
typename Predicate>
2112 inline OutputIterator
2113 remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate predicate)
2115 for(; first != last; ++first)
2117 if(!predicate(*first))
2150 template <
typename ForwardIterator,
typename T>
2151 inline ForwardIterator
2152 remove(ForwardIterator first, ForwardIterator last,
const T& value)
2157 ForwardIterator i(first);
2187 template <
typename ForwardIterator,
typename Predicate>
2188 inline ForwardIterator
2189 remove_if(ForwardIterator first, ForwardIterator last, Predicate predicate)
2194 ForwardIterator i(first);
2195 return eastl::remove_copy_if<ForwardIterator, ForwardIterator, Predicate>(++i, last, first, predicate);
2216 template <
typename InputIterator,
typename OutputIterator,
typename T>
2217 inline OutputIterator
2218 replace_copy(InputIterator first, InputIterator last, OutputIterator result,
const T& old_value,
const T& new_value)
2220 for(; first != last; ++first, ++result)
2221 *result = (*first == old_value) ? new_value : *first;
2241 template <
typename InputIterator,
typename OutputIterator,
typename Predicate,
typename T>
2242 inline OutputIterator
2243 replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate predicate,
const T& new_value)
2245 for(; first != last; ++first, ++result)
2246 *result = predicate(*first) ? new_value : *first;
2258 template <
typename B
idirectionalIterator>
2259 inline void reverse_impl(BidirectionalIterator first, BidirectionalIterator last, EASTL_ITC_NS::bidirectional_iterator_tag)
2261 for(; (first != last) && (first != --last); ++first)
2265 template <
typename RandomAccessIterator>
2266 inline void reverse_impl(RandomAccessIterator first, RandomAccessIterator last, EASTL_ITC_NS::random_access_iterator_tag)
2268 for(; first < --last; ++first)
2281 template <
typename B
idirectionalIterator>
2282 inline void reverse(BidirectionalIterator first, BidirectionalIterator last)
2284 typedef typename eastl::iterator_traits<BidirectionalIterator>::iterator_category IC;
2285 eastl::reverse_impl(first, last, IC());
2306 template <
typename B
idirectionalIterator,
typename OutputIterator>
2307 inline OutputIterator
2308 reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result)
2310 for(; first != last; ++result)
2331 template <
typename ForwardIterator1,
typename ForwardIterator2>
2333 search(ForwardIterator1 first1, ForwardIterator1 last1,
2334 ForwardIterator2 first2, ForwardIterator2 last2)
2340 ForwardIterator2 temp2(first2);
2345 ForwardIterator1 cur1(first1);
2346 ForwardIterator2 p2;
2348 while(first1 != last1)
2351 while((first1 != last1) && !(*first1 == *first2))
2426 template <
typename ForwardIterator1,
typename ForwardIterator2,
typename BinaryPredicate>
2428 search(ForwardIterator1 first1, ForwardIterator1 last1,
2429 ForwardIterator2 first2, ForwardIterator2 last2,
2430 BinaryPredicate predicate)
2432 typedef typename eastl::iterator_traits<ForwardIterator1>::difference_type difference_type_1;
2433 typedef typename eastl::iterator_traits<ForwardIterator2>::difference_type difference_type_2;
2435 difference_type_2 d2 = eastl::distance(first2, last2);
2439 ForwardIterator1 i(first1);
2440 eastl::advance(i, d2);
2442 for(difference_type_1 d1 = eastl::distance(first1, last1); d1 >= d2; --d1)
2444 if(eastl::equal<ForwardIterator1, ForwardIterator2, BinaryPredicate>(first1, i, first2, predicate))
2461 template <
typename ForwardIterator,
typename Size,
typename T>
2463 search_n_impl(ForwardIterator first, ForwardIterator last, Size
count,
const T& value, EASTL_ITC_NS::forward_iterator_tag)
2468 Size d1 = (Size)eastl::distance(first, last);
2473 for(; d1 >=
count; ++first, --d1)
2475 ForwardIterator i(first);
2477 for(Size n = 0; n <
count; ++n, ++i, --d1)
2490 template <
typename RandomAccessIterator,
typename Size,
typename T>
inline 2491 RandomAccessIterator
2492 search_n_impl(RandomAccessIterator first, RandomAccessIterator last, Size
count,
const T& value, EASTL_ITC_NS::random_access_iterator_tag)
2497 return find(first, last, value);
2498 else if(last > first)
2500 RandomAccessIterator lookAhead;
2501 RandomAccessIterator backTrack;
2503 Size skipOffset = (
count - 1);
2504 Size tailSize = (Size)(last - first);
2508 for(lookAhead = first + skipOffset; tailSize >=
count; lookAhead +=
count)
2512 if(*lookAhead == value)
2514 remainder = skipOffset;
2516 for(backTrack = lookAhead - 1; *backTrack == value; --backTrack)
2518 if(--remainder == 0)
2519 return (lookAhead - skipOffset);
2522 if(remainder <= tailSize)
2524 prevRemainder = remainder;
2526 while(*(++lookAhead) == value)
2528 if(--remainder == 0)
2529 return (backTrack + 1);
2531 tailSize -= (prevRemainder - remainder);
2554 template <
typename ForwardIterator,
typename Size,
typename T>
2556 search_n(ForwardIterator first, ForwardIterator last, Size
count,
const T& value)
2558 typedef typename eastl::iterator_traits<ForwardIterator>::iterator_category IC;
2559 return eastl::search_n_impl(first, last,
count, value, IC());
2584 template <
typename ForwardIterator,
typename T>
2589 ForwardIterator i(eastl::lower_bound<ForwardIterator, T>(first, last, value));
2590 return ((i != last) && !(value < *i));
2604 template <
typename ForwardIterator,
typename T,
typename Compare>
2606 binary_search(ForwardIterator first, ForwardIterator last,
const T& value, Compare compare)
2609 ForwardIterator i(eastl::lower_bound<ForwardIterator, T, Compare>(first, last, value, compare));
2610 return ((i != last) && !compare(value, *i));
2622 template <
typename ForwardIterator,
typename T>
2623 inline ForwardIterator
2627 ForwardIterator i(eastl::lower_bound<ForwardIterator, T>(first, last, value));
2628 if((i != last) && !(value < *i))
2642 template <
typename ForwardIterator,
typename T,
typename Compare>
2643 inline ForwardIterator
2644 binary_search_i(ForwardIterator first, ForwardIterator last,
const T& value, Compare compare)
2647 ForwardIterator i(eastl::lower_bound<ForwardIterator, T, Compare>(first, last, value, compare));
2648 if((i != last) && !compare(value, *i))
2676 template <
typename ForwardIterator>
2677 ForwardIterator
unique(ForwardIterator first, ForwardIterator last)
2679 first = eastl::adjacent_find<ForwardIterator>(first, last);
2683 ForwardIterator dest(first);
2685 for(++first; first != last; ++first)
2687 if(!(*dest == *first))
2713 template <
typename ForwardIterator,
typename BinaryPredicate>
2714 ForwardIterator
unique(ForwardIterator first, ForwardIterator last, BinaryPredicate predicate)
2716 first = eastl::adjacent_find<ForwardIterator, BinaryPredicate>(first, last, predicate);
2720 ForwardIterator dest(first);
2722 for(++first; first != last; ++first)
2724 if(!predicate(*dest, *first))
2741 template <
typename ForwardIterator1,
typename ForwardIterator2>
2743 find_end_impl(ForwardIterator1 first1, ForwardIterator1 last1,
2744 ForwardIterator2 first2, ForwardIterator2 last2,
2745 EASTL_ITC_NS::forward_iterator_tag, EASTL_ITC_NS::forward_iterator_tag)
2749 for(ForwardIterator1 result(last1); ; )
2751 const ForwardIterator1 resultNext(
eastl::search(first1, last1, first2, last2));
2753 if(resultNext != last1)
2755 first1 = result = resultNext;
2765 template <
typename B
idirectionalIterator1,
typename B
idirectionalIterator2>
2766 BidirectionalIterator1
2767 find_end_impl(BidirectionalIterator1 first1, BidirectionalIterator1 last1,
2768 BidirectionalIterator2 first2, BidirectionalIterator2 last2,
2769 EASTL_ITC_NS::bidirectional_iterator_tag, EASTL_ITC_NS::bidirectional_iterator_tag)
2774 reverse_iterator1 rresult(
eastl::search(reverse_iterator1(last1), reverse_iterator1(first1),
2775 reverse_iterator2(last2), reverse_iterator2(first2)));
2776 if(rresult.base() != first1)
2778 BidirectionalIterator1 result(rresult.base());
2780 eastl::advance(result, -eastl::distance(first2, last2));
2797 template <
typename ForwardIterator1,
typename ForwardIterator2>
2798 inline ForwardIterator1
2799 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
2800 ForwardIterator2 first2, ForwardIterator2 last2)
2802 typedef typename eastl::iterator_traits<ForwardIterator1>::iterator_category IC1;
2803 typedef typename eastl::iterator_traits<ForwardIterator2>::iterator_category IC2;
2805 return eastl::find_end_impl(first1, last1, first2, last2, IC1(), IC2());
2813 template <
typename ForwardIterator1,
typename ForwardIterator2,
typename BinaryPredicate>
2815 find_end_impl(ForwardIterator1 first1, ForwardIterator1 last1,
2816 ForwardIterator2 first2, ForwardIterator2 last2,
2817 BinaryPredicate predicate,
2818 EASTL_ITC_NS::forward_iterator_tag, EASTL_ITC_NS::forward_iterator_tag)
2822 for(ForwardIterator1 result = last1; ; )
2824 const ForwardIterator1 resultNext(eastl::search<ForwardIterator1, ForwardIterator2, BinaryPredicate>(first1, last1, first2, last2, predicate));
2826 if(resultNext != last1)
2828 first1 = result = resultNext;
2838 template <
typename B
idirectionalIterator1,
typename B
idirectionalIterator2,
typename BinaryPredicate>
2839 BidirectionalIterator1
2840 find_end_impl(BidirectionalIterator1 first1, BidirectionalIterator1 last1,
2841 BidirectionalIterator2 first2, BidirectionalIterator2 last2,
2842 BinaryPredicate predicate,
2843 EASTL_ITC_NS::bidirectional_iterator_tag, EASTL_ITC_NS::bidirectional_iterator_tag)
2848 reverse_iterator1 rresult(eastl::search<reverse_iterator1, reverse_iterator2, BinaryPredicate>
2849 (reverse_iterator1(last1), reverse_iterator1(first1),
2850 reverse_iterator2(last2), reverse_iterator2(first2),
2852 if(rresult.base() != first1)
2854 BidirectionalIterator1 result(rresult.base());
2855 eastl::advance(result, -eastl::distance(first2, last2));
2874 template <
typename ForwardIterator1,
typename ForwardIterator2,
typename BinaryPredicate>
2875 inline ForwardIterator1
2876 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
2877 ForwardIterator2 first2, ForwardIterator2 last2,
2878 BinaryPredicate predicate)
2880 typedef typename eastl::iterator_traits<ForwardIterator1>::iterator_category IC1;
2881 typedef typename eastl::iterator_traits<ForwardIterator2>::iterator_category IC2;
2883 return eastl::find_end_impl<ForwardIterator1, ForwardIterator2, BinaryPredicate>
2884 (first1, last1, first2, last2, predicate, IC1(), IC2());
2905 template <
typename InputIterator1,
typename InputIterator2,
typename OutputIterator>
2907 InputIterator2 first2, InputIterator2 last2,
2908 OutputIterator result)
2910 while((first1 != last1) && (first2 != last2))
2912 if(*first1 < *first2)
2918 else if(*first2 < *first1)
2931 template <
typename InputIterator1,
typename InputIterator2,
typename OutputIterator,
typename Compare>
2932 OutputIterator
set_difference(InputIterator1 first1, InputIterator1 last1,
2933 InputIterator2 first2, InputIterator2 last2,
2934 OutputIterator result, Compare compare)
2936 while((first1 != last1) && (first2 != last2))
2938 if(compare(*first1, *first2))
2940 EASTL_VALIDATE_COMPARE(!compare(*first2, *first1));
2945 else if(compare(*first2, *first1))
2947 EASTL_VALIDATE_COMPARE(!compare(*first1, *first2));
2964 #endif // Header include guard InputIterator find_if(InputIterator first, InputIterator last, Predicate predicate)
OutputIterator transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation unaryOperation)
OutputIterator fill_n(OutputIterator first, Size n, const T &value)
ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2)
OutputIterator replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate predicate, const T &new_value)
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T &value)
ForwardIterator unique(ForwardIterator first, ForwardIterator last)
ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2)
OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result)
void replace(ForwardIterator first, ForwardIterator last, const T &old_value, const T &new_value)
ForwardIterator max_element(ForwardIterator first, ForwardIterator last)
void reverse(BidirectionalIterator first, BidirectionalIterator last)
ForwardIterator1 find_first_not_of(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2)
ForwardIterator remove_if(ForwardIterator first, ForwardIterator last, Predicate predicate)
pair< ForwardIterator, ForwardIterator > equal_range(ForwardIterator first, ForwardIterator last, const T &value)
OutputIterator remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T &value)
const T & median(const T &a, const T &b, const T &c)
const T & min_alt(const T &a, const T &b)
bool identical(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2)
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last)
OutputIterator generate_n(OutputIterator first, Size n, Generator generator)
void generate(ForwardIterator first, ForwardIterator last, Generator generator)
void iter_swap(ForwardIterator1 a, ForwardIterator2 b)
OutputIterator reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result)
OutputIterator remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate predicate)
const T & max_alt(const T &a, const T &b)
void replace_if(ForwardIterator first, ForwardIterator last, Predicate predicate, const T &new_value)
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T &value)
InputIterator find(InputIterator first, InputIterator last, const T &value)
eastl::iterator_traits< InputIterator >::difference_type count_if(InputIterator first, InputIterator last, Predicate predicate)
OutputIterator replace_copy(InputIterator first, InputIterator last, OutputIterator result, const T &old_value, const T &new_value)
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2)
Function for_each(InputIterator first, InputIterator last, Function function)
BidirectionalIterator2 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 result)
ForwardIterator binary_search_i(ForwardIterator first, ForwardIterator last, const T &value)
void fill(ForwardIterator first, ForwardIterator last, const T &value)
ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2)
EA Standard Template Library.
bool binary_search(ForwardIterator first, ForwardIterator last, const T &value)
ForwardIterator1 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2)
ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Size count, const T &value)
ForwardIterator min_element(ForwardIterator first, ForwardIterator last)
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result)
eastl::iterator_traits< InputIterator >::difference_type count(InputIterator first, InputIterator last, const T &value)
bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2)