33#ifndef ETL_ALGORITHM_INCLUDED
34#define ETL_ALGORITHM_INCLUDED
64 template <
typename TIterator>
65#if ETL_USING_STD_NAMESPACE
70 void shell_sort(TIterator first, TIterator last);
72 template <
typename TIterator,
typename TCompare>
73#if ETL_USING_STD_NAMESPACE
78 void shell_sort(TIterator first, TIterator last, TCompare compare);
80 template <
typename TIterator>
81 ETL_CONSTEXPR14
void insertion_sort(TIterator first, TIterator last);
83 template <
typename TIterator,
typename TCompare>
84 ETL_CONSTEXPR14
void insertion_sort(TIterator first, TIterator last, TCompare compare);
92 namespace private_algorithm
94 template <
bool use_swap>
101 template <
typename TIterator1,
typename TIterator2>
102 static void do_swap(TIterator1 a, TIterator2 b)
104 typename etl::iterator_traits<TIterator1>::value_type tmp = *a;
114 template <
typename TIterator1,
typename TIterator2>
115 static void do_swap(TIterator1 a, TIterator2 b)
117 using ETL_OR_STD::swap;
126 template <
typename TIterator1,
typename TIterator2>
127#if ETL_USING_STD_NAMESPACE
132 void iter_swap(TIterator1 a, TIterator2 b)
137 typedef typename traits1::value_type v1;
138 typedef typename traits2::value_type v2;
140 typedef typename traits1::reference r1;
141 typedef typename traits2::reference r2;
153 template <
typename TIterator1,
typename TIterator2>
154#if ETL_USING_STD_NAMESPACE
159 TIterator2 swap_ranges(TIterator1 first1,
163 while (first1 != last1)
165 iter_swap(first1, first2);
175 template <
typename TIterator,
typename TFunction>
177 void generate(TIterator db, TIterator de, TFunction funct)
187#if ETL_USING_STL && ETL_USING_CPP20
189 template <
typename TIterator1,
typename TIterator2>
190 constexpr TIterator2 copy(TIterator1 sb, TIterator1 se, TIterator2 db)
192 return std::copy(sb, se, db);
196 template <
typename TIterator1,
typename TIterator2>
197 ETL_CONSTEXPR14 TIterator2 copy(TIterator1 sb, TIterator1 se, TIterator2 db)
212#if ETL_USING_STL && ETL_USING_CPP20
213 template <
typename TIterator1,
typename TIterator2>
214 constexpr TIterator2 reverse_copy(TIterator1 sb, TIterator1 se, TIterator2 db)
216 return std::reverse_copy(sb, se, db);
219 template <
typename TIterator1,
typename TIterator2>
221 TIterator2 reverse_copy(TIterator1 sb, TIterator1 se, TIterator2 db)
235#if ETL_USING_STL && ETL_USING_CPP20
237 template <
typename TIterator1,
typename TSize,
typename TIterator2>
238 constexpr TIterator2 copy_n(TIterator1 sb, TSize count, TIterator2 db)
240 return std::copy_n(sb, count, db);
244 template <
typename TIterator1,
typename TSize,
typename TIterator2>
245 ETL_CONSTEXPR14 TIterator2 copy_n(TIterator1 sb, TSize count, TIterator2 db)
261#if ETL_USING_STL && ETL_USING_CPP20
262 template <
typename TIterator1,
typename TIterator2>
263 constexpr TIterator2 copy_backward(TIterator1 sb, TIterator1 se, TIterator2 de)
265 return std::copy_backward(sb, se, de);
268 template <
typename TIterator1,
typename TIterator2>
269 ETL_CONSTEXPR14 TIterator2 copy_backward(TIterator1 sb, TIterator1 se, TIterator2 de)
282#if ETL_USING_STL && ETL_USING_CPP20
283 template <
typename TIterator1,
typename TIterator2>
284 constexpr TIterator2 move(TIterator1 sb, TIterator1 se, TIterator2 db)
286 return std::move(sb, se, db);
290 template <
typename TIterator1,
typename TIterator2>
291 ETL_CONSTEXPR14 TIterator2 move(TIterator1 sb, TIterator1 se, TIterator2 db)
295 *db = etl::move(*sb);
304 template <
typename TIterator1,
typename TIterator2>
305 ETL_CONSTEXPR14 TIterator2 move(TIterator1 sb, TIterator1 se, TIterator2 db)
307 return copy(sb, se, db);
313#if ETL_USING_STL && ETL_USING_CPP20
314 template <
typename TIterator1,
typename TIterator2>
315 ETL_CONSTEXPR20 TIterator2 move_backward(TIterator1 sb, TIterator1 se, TIterator2 de)
317 return std::move_backward(sb, se, de);
321 template <
typename TIterator1,
typename TIterator2>
322 ETL_CONSTEXPR14 TIterator2 move_backward(TIterator1 sb, TIterator1 se, TIterator2 de)
326 *(--de) = etl::move(*(--se));
333 template <
typename TIterator1,
typename TIterator2>
334 ETL_CONSTEXPR14 TIterator2 move_backward(TIterator1 sb, TIterator1 se, TIterator2 de)
336 return etl::copy_backward(sb, se, de);
344 template <
typename TIterator>
347 reverse(TIterator b, TIterator e)
353 etl::iter_swap(b, e);
360 template <
typename TIterator>
363 reverse(TIterator b, TIterator e)
365 while ((b != e) && (b != --e))
367 etl::iter_swap(b++, e);
374 template<
typename TIterator,
typename TValue,
typename TCompare>
377 TIterator lower_bound(TIterator first, TIterator last,
const TValue& value, TCompare compare)
379 typedef typename etl::iterator_traits<TIterator>::difference_type difference_t;
381 difference_t count = etl::distance(first, last);
385 TIterator itr = first;
386 difference_t step = count / 2;
388 etl::advance(itr, step);
390 if (compare(*itr, value))
404 template<
typename TIterator,
typename TValue>
407 TIterator lower_bound(TIterator first, TIterator last,
const TValue& value)
411 return etl::lower_bound(first, last, value, compare());
417 template<
typename TIterator,
typename TValue,
typename TCompare>
420 TIterator upper_bound(TIterator first, TIterator last,
const TValue& value, TCompare compare)
422 typedef typename etl::iterator_traits<TIterator>::difference_type difference_t;
424 difference_t count = etl::distance(first, last);
428 TIterator itr = first;
429 difference_t step = count / 2;
431 etl::advance(itr, step);
433 if (!compare(value, *itr))
447 template<
typename TIterator,
typename TValue>
450 TIterator upper_bound(TIterator first, TIterator last,
const TValue& value)
454 return etl::upper_bound(first, last, value, compare());
460 template<
typename TIterator,
typename TValue,
typename TCompare>
463 ETL_OR_STD::pair<TIterator, TIterator> equal_range(TIterator first, TIterator last,
const TValue& value, TCompare compare)
465 return ETL_OR_STD::make_pair(etl::lower_bound(first, last, value, compare),
466 etl::upper_bound(first, last, value, compare));
469 template<
typename TIterator,
typename TValue>
471 ETL_OR_STD::pair<TIterator, TIterator> equal_range(TIterator first, TIterator last,
const TValue& value)
475 return ETL_OR_STD::make_pair(etl::lower_bound(first, last, value, compare()),
476 etl::upper_bound(first, last, value, compare()));
482 template <
typename TIterator,
typename T,
typename Compare>
484 bool binary_search(TIterator first, TIterator last,
const T& value, Compare compare)
486 first = etl::lower_bound(first, last, value, compare);
488 return (!(first == last) && !(compare(value, *first)));
491 template <
typename TIterator,
typename T>
493 bool binary_search(TIterator first, TIterator last,
const T& value)
497 return binary_search(first, last, value, compare());
503 template <
typename TIterator,
typename TUnaryPredicate>
506 TIterator find_if(TIterator first, TIterator last, TUnaryPredicate predicate)
508 while (first != last)
510 if (predicate(*first))
524 template <
typename TIterator,
typename T>
527 TIterator find(TIterator first, TIterator last,
const T& value)
529 while (first != last)
544#if ETL_USING_STL && ETL_USING_CPP20
545 template<
typename TIterator,
typename TValue>
546 constexpr void fill(TIterator first, TIterator last,
const TValue& value)
548 std::fill(first, last, value);
551 template<
typename TIterator,
typename TValue>
552 ETL_CONSTEXPR14
void fill(TIterator first, TIterator last,
const TValue& value)
554 while (first != last)
564#if ETL_USING_STL && ETL_USING_CPP20
565 template<
typename TIterator,
typename TSize,
typename TValue>
566 constexpr TIterator fill_n(TIterator first, TSize count,
const TValue& value)
568 return std::fill_n(first, count, value);
571 template<
typename TIterator,
typename TSize,
typename TValue>
572 ETL_CONSTEXPR14 TIterator fill_n(TIterator first, TSize count,
const TValue& value)
587 template <
typename TIterator,
typename T>
590 typename etl::iterator_traits<TIterator>::difference_type count(TIterator first, TIterator last,
const T& value)
592 typename iterator_traits<TIterator>::difference_type n = 0;
594 while (first != last)
610 template <
typename TIterator,
typename TUnaryPredicate>
613 typename etl::iterator_traits<TIterator>::difference_type
614 count_if(TIterator first, TIterator last, TUnaryPredicate predicate)
616 typename iterator_traits<TIterator>::difference_type n = 0;
618 while (first != last)
620 if (predicate(*first))
633#if ETL_USING_STL && ETL_USING_CPP20
635 template <
typename TIterator1,
typename TIterator2>
638 bool equal(TIterator1 first1, TIterator1 last1, TIterator2 first2)
640 return std::equal(first1, last1, first2);
644 template <
typename TIterator1,
typename TIterator2,
typename TPredicate>
647 bool equal(TIterator1 first1, TIterator1 last1, TIterator2 first2, TPredicate predicate)
649 return std::equal(first1, last1, first2, predicate);
653 template <
typename TIterator1,
typename TIterator2>
656 bool equal(TIterator1 first1, TIterator1 last1, TIterator2 first2, TIterator2 last2)
658 return std::equal(first1, last1, first2, last2);
662 template <
typename TIterator1,
typename TIterator2,
typename TPredicate>
665 bool equal(TIterator1 first1, TIterator1 last1, TIterator2 first2, TIterator2 last2, TPredicate predicate)
667 return std::equal(first1, last1, first2, last2, predicate);
672 template <
typename TIterator1,
typename TIterator2>
675 bool equal(TIterator1 first1, TIterator1 last1, TIterator2 first2)
677 while (first1 != last1)
679 if (*first1 != *first2)
692 template <
typename TIterator1,
typename TIterator2,
typename TPredicate>
695 bool equal(TIterator1 first1, TIterator1 last1, TIterator2 first2, TPredicate predicate)
697 while (first1 != last1)
699 if (!predicate(*first1, *first2))
712 template <
typename TIterator1,
typename TIterator2>
715 bool equal(TIterator1 first1, TIterator1 last1, TIterator2 first2, TIterator2 last2)
717 while ((first1 != last1) && (first2 != last2))
719 if (*first1 != *first2)
728 return (first1 == last1) && (first2 == last2);
732 template <
typename TIterator1,
typename TIterator2,
typename TPredicate>
735 bool equal(TIterator1 first1, TIterator1 last1, TIterator2 first2, TIterator2 last2, TPredicate predicate)
737 while ((first1 != last1) && (first2 != last2))
739 if (!predicate(*first1 , *first2))
748 return (first1 == last1) && (first2 == last2);
755 template <
typename TIterator1,
typename TIterator2,
typename TCompare>
758 bool lexicographical_compare(TIterator1 first1, TIterator1 last1,
759 TIterator2 first2, TIterator2 last2,
762 while ((first1 != last1) && (first2 != last2))
764 if (compare(*first1, *first2))
769 if (compare(*first2, *first1))
778 return (first1 == last1) && (first2 != last2);
782 template <
typename TIterator1,
typename TIterator2>
785 bool lexicographical_compare(TIterator1 first1, TIterator1 last1,
786 TIterator2 first2, TIterator2 last2)
790 return etl::lexicographical_compare(first1, last1, first2, last2, compare());
796 template <
typename T,
typename TCompare>
799 const T& min(
const T& a,
const T& b, TCompare compare)
801 return (compare(a, b)) ? a : b;
804 template <
typename T>
807 const T& min(
const T& a,
const T& b)
811 return etl::min(a, b, compare());
817 template <
typename T,
typename TCompare>
820 const T& max(
const T& a,
const T& b, TCompare compare)
822 return (compare(a, b)) ? b : a;
825 template <
typename T>
828 const T& max(
const T& a,
const T& b)
832 return etl::max(a, b, compare());
838 template <
typename TIterator,
typename TUnaryOperation>
840 TUnaryOperation for_each(TIterator first, TIterator last, TUnaryOperation unary_operation)
842 while (first != last)
844 unary_operation(*first);
848 return unary_operation;
854 template <
typename TIteratorIn,
typename TIteratorOut,
typename TUnaryOperation>
856 TIteratorOut transform(TIteratorIn first1, TIteratorIn last1, TIteratorOut d_first, TUnaryOperation unary_operation)
858 while (first1 != last1)
860 *d_first = unary_operation(*first1);
869 template <
typename TIteratorIn1,
typename TIteratorIn2,
typename TIteratorOut,
typename TBinaryOperation>
871 TIteratorOut transform(TIteratorIn1 first1, TIteratorIn1 last1, TIteratorIn2 first2, TIteratorOut d_first, TBinaryOperation binary_operation)
873 while (first1 != last1)
875 *d_first = binary_operation(*first1, *first2);
888 template <
typename TIterator,
typename T>
889 ETL_CONSTEXPR14
void replace(TIterator first, TIterator last,
const T& old_value,
const T& new_value)
891 while (first != last)
893 if (*first == old_value)
905 template <
typename TIterator,
typename TPredicate,
typename T>
906 ETL_CONSTEXPR14
void replace_if(TIterator first, TIterator last, TPredicate predicate,
const T& new_value)
908 while (first != last)
910 if (predicate(*first))
922 namespace private_heap
925 template <
typename TIterator,
typename TDistance,
typename TValue,
typename TCompare>
926 void push_heap(TIterator first, TDistance value_index, TDistance top_index, TValue value, TCompare compare)
928 TDistance parent = (value_index - 1) / 2;
930 while ((value_index > top_index) && compare(first[parent], value))
932 first[value_index] = etl::move(first[parent]);
933 value_index = parent;
934 parent = (value_index - 1) / 2;
937 first[value_index] = etl::move(value);
941 template <
typename TIterator,
typename TDistance,
typename TValue,
typename TCompare>
942 void adjust_heap(TIterator first, TDistance value_index, TDistance length, TValue value, TCompare compare)
944 TDistance top_index = value_index;
945 TDistance child2nd = (2 * value_index) + 2;
947 while (child2nd < length)
949 if (compare(first[child2nd], first[child2nd - 1]))
954 first[value_index] = etl::move(first[child2nd]);
955 value_index = child2nd;
956 child2nd = 2 * (child2nd + 1);
959 if (child2nd == length)
961 first[value_index] = etl::move(first[child2nd - 1]);
962 value_index = child2nd - 1;
965 push_heap(first, value_index, top_index, etl::move(value), compare);
969 template <
typename TIterator,
typename TDistance,
typename TCompare>
970 bool is_heap(
const TIterator first,
const TDistance n, TCompare compare)
972 TDistance parent = 0;
974 for (TDistance child = 1; child < n; ++child)
976 if (compare(first[parent], first[child]))
981 if ((child & 1) == 0)
992 template <
typename TIterator,
typename TCompare>
993 void pop_heap(TIterator first, TIterator last, TCompare compare)
995 typedef typename etl::iterator_traits<TIterator>::value_type value_t;
996 typedef typename etl::iterator_traits<TIterator>::difference_type distance_t;
998 value_t value = etl::move(last[-1]);
999 last[-1] = etl::move(first[0]);
1001 private_heap::adjust_heap(first, distance_t(0), distance_t(last - first - 1), etl::move(value), compare);
1005 template <
typename TIterator>
1006 void pop_heap(TIterator first, TIterator last)
1010 etl::pop_heap(first, last, compare());
1014 template <
typename TIterator,
typename TCompare>
1015 void push_heap(TIterator first, TIterator last, TCompare compare)
1017 typedef typename etl::iterator_traits<TIterator>::difference_type difference_t;
1018 typedef typename etl::iterator_traits<TIterator>::value_type value_t;
1020 private_heap::push_heap(first, difference_t(last - first - 1), difference_t(0), value_t(etl::move(*(last - 1))), compare);
1024 template <
typename TIterator>
1025 void push_heap(TIterator first, TIterator last)
1029 etl::push_heap(first, last, compare());
1033 template <
typename TIterator,
typename TCompare>
1034 void make_heap(TIterator first, TIterator last, TCompare compare)
1036 typedef typename etl::iterator_traits<TIterator>::difference_type difference_t;
1038 if ((last - first) < 2)
1043 difference_t length = last - first;
1044 difference_t parent = (length - 2) / 2;
1048 private_heap::adjust_heap(first, parent, length, etl::move(*(first + parent)), compare);
1060 template <
typename TIterator>
1061 void make_heap(TIterator first, TIterator last)
1065 etl::make_heap(first, last, compare());
1069 template <
typename TIterator>
1071 bool is_heap(TIterator first, TIterator last)
1075 return private_heap::is_heap(first, last - first, compare());
1079 template <
typename TIterator,
typename TCompare>
1081 bool is_heap(TIterator first, TIterator last, TCompare compare)
1083 return private_heap::is_heap(first, last - first, compare);
1087 template <
typename TIterator>
1088 void sort_heap(TIterator first, TIterator last)
1090 while (first != last)
1092 etl::pop_heap(first, last);
1098 template <
typename TIterator,
typename TCompare>
1099 void sort_heap(TIterator first, TIterator last, TCompare compare)
1101 while (first != last)
1103 etl::pop_heap(first, last, compare);
1111 template<
typename TIterator1,
typename TIterator2,
typename TCompare>
1114 TIterator1 search(TIterator1 first, TIterator1 last, TIterator2 search_first, TIterator2 search_last, TCompare compare)
1118 TIterator1 itr = first;
1119 TIterator2 search_itr = search_first;
1123 if (search_itr == search_last)
1133 if (!compare(*itr, *search_itr))
1147 template<
typename TIterator1,
typename TIterator2>
1150 TIterator1 search(TIterator1 first, TIterator1 last, TIterator2 search_first, TIterator2 search_last)
1154 return etl::search(first, last, search_first, search_last, compare());
1160 namespace private_algorithm
1165 template <
typename TIterator>
1168 rotate_general(TIterator first, TIterator middle, TIterator last)
1170 if (first == middle || middle == last)
1175 typedef typename etl::iterator_traits<TIterator>::value_type value_type;
1177 int n = last - first;
1178 int m = middle - first;
1179 int gcd_nm = (n == 0 || m == 0) ? n + m :
etl::gcd(n, m);
1181 TIterator result = first + (last - middle);
1183 for (
int i = 0; i < gcd_nm; i++)
1185 value_type temp = etl::move(*(first + i));
1202 *(first + j) = etl::move(*(first + k));
1206 *(first + j) = etl::move(temp);
1214 template <
typename TIterator>
1217 rotate_general(TIterator first, TIterator middle, TIterator last)
1219 if (first == middle || middle == last)
1224 typedef typename etl::iterator_traits<TIterator>::value_type value_type;
1226 int n = last - first;
1227 int m = middle - first;
1228 int gcd_nm = (n == 0 || m == 0) ? n + m :
etl::gcd(n, m);
1230 TIterator result = first + (last - middle);
1232 for (
int i = 0; i < gcd_nm; i++)
1234 value_type temp = *(first + i);
1251 *(first + j) = *(first + k);
1255 *(first + j) = temp;
1264 template <
typename TIterator>
1267 rotate_general(TIterator first, TIterator middle, TIterator last)
1269 if (first == middle || middle == last)
1274 TIterator result = first;
1275 etl::advance(result, etl::distance(middle, last));
1277 reverse(first, middle);
1278 reverse(middle, last);
1279 reverse(first, last);
1286 template <
typename TIterator>
1289 rotate_general(TIterator first, TIterator middle, TIterator last)
1291 if (first == middle || middle == last)
1296 TIterator next = middle;
1297 TIterator result = first;
1298 etl::advance(result, etl::distance(middle, last));
1300 while (first != next)
1302 using ETL_OR_STD::swap;
1303 swap(*first++, *next++);
1309 else if (first == middle)
1320 template <
typename TIterator>
1322 TIterator rotate_left_by_one(TIterator first, TIterator last)
1324 typedef typename etl::iterator_traits<TIterator>::value_type value_type;
1327 value_type temp(etl::move(*first));
1330 TIterator result = etl::move(etl::next(first), last, first);
1333 *result = etl::move(temp);
1341 template <
typename TIterator>
1343 TIterator rotate_right_by_one(TIterator first, TIterator last)
1345 typedef typename etl::iterator_traits<TIterator>::value_type value_type;
1348 TIterator previous = etl::prev(last);
1349 value_type temp(etl::move(*previous));
1352 TIterator result = etl::move_backward(first, previous, last);
1355 *first = etl::move(temp);
1363 template<
typename TIterator>
1365 TIterator rotate(TIterator first, TIterator middle, TIterator last)
1367 if (etl::next(first) == middle)
1369 return private_algorithm::rotate_left_by_one(first, last);
1372 if (etl::next(middle) == last)
1377 return private_algorithm::rotate_general(first, middle, last);
1381 return private_algorithm::rotate_right_by_one(first, last);
1384 return private_algorithm::rotate_general(first, middle, last);
1388 return private_algorithm::rotate_general(first, middle, last);
1395 template <
typename TIterator1,
typename TIterator2,
typename TPredicate>
1398 TIterator1 find_end(TIterator1 b, TIterator1 e,
1399 TIterator2 sb, TIterator2 se,
1400 TPredicate predicate)
1407 TIterator1 result = e;
1411 TIterator1 new_result = etl::search(b, e, sb, se, predicate);
1413 if (new_result == e)
1419 result = new_result;
1428 template <
typename TIterator1,
typename TIterator2>
1431 TIterator1 find_end(TIterator1 b, TIterator1 e,
1432 TIterator2 sb, TIterator2 se)
1436 return find_end(b, e, sb, se, predicate());
1444 template <
typename TIterator,
typename TCompare>
1472 template <
typename TIterator>
1478 typedef typename etl::iterator_traits<TIterator>::value_type
value_t;
1488 template <
typename TIterator,
typename TCompare>
1516 template <
typename TIterator>
1522 typedef typename etl::iterator_traits<TIterator>::value_type
value_t;
1532 template <
typename TIterator,
typename TCompare>
1558 return ETL_OR_STD::pair<TIterator, TIterator>(
minimum, maximum);
1566 template <
typename TIterator>
1572 typedef typename etl::iterator_traits<TIterator>::value_type
value_t;
1582 template <
typename T>
1585 ETL_OR_STD::pair<const T&, const T&>
minmax(
const T& a,
1588 return (
b < a) ? ETL_OR_STD::pair<const T&, const T&>(
b, a) : ETL_OR_STD::pair<const T&, const T&>(a,
b);
1596 template <
typename T,
typename TCompare>
1599 ETL_OR_STD::pair<const T&, const T&>
minmax(
const T& a,
1603 return compare(
b, a) ? ETL_OR_STD::pair<const T&, const T&>(
b, a) : ETL_OR_STD::pair<const T&, const T&>(a,
b);
1611 template <
typename TIterator>
1621 while (++next !=
end)
1640 template <
typename TIterator,
typename TCompare>
1651 while (++next !=
end)
1670 template<
typename TIterator>
1684 template<
typename TIterator,
typename TCompare>
1699 template <
typename TIterator,
typename TUnaryPredicate>
1724 template <
typename TIterator1,
typename TIterator2>
1743 if (
n == 0 ||
size_t(etl::count(
i,
end1, *
i)) !=
n)
1759 template <
typename TIterator1,
typename TIterator2,
typename TBinaryPredicate>
1779 if (
n == 0 ||
size_t(etl::count(
i,
end1, *
i)) !=
n)
1795 template <
typename TIterator1,
typename TIterator2>
1811 if (
n == 0 ||
size_t(etl::count(
i,
end1, *
i)) !=
n)
1827 template <
typename TIterator1,
typename TIterator2,
typename TBinaryPredicate>
1843 if (
n == 0 ||
size_t(etl::count(
i,
end1, *
i)) !=
n)
1859 template <
typename TIterator,
typename TUnaryPredicate>
1894 template <
typename TIterator,
typename TUnaryPredicate>
1920 template <
typename TSource,
typename TDestinationTrue,
typename TDestinationFalse,
typename TUnaryPredicate>
1952 template <
typename TIterator,
typename TOutputIterator,
typename TUnaryPredicate>
1978 template <
typename TIterator,
typename TUnaryPredicate>
1993 template <
typename TIterator,
typename TUnaryPredicate>
2008 template <
typename TIterator,
typename TUnaryPredicate>
2018#if ETL_NOT_USING_STL
2024 template <
typename TIterator,
typename TCompare>
2025 void sort(TIterator first, TIterator last, TCompare compare)
2034 template <
typename TIterator>
2035 void sort(TIterator first, TIterator last)
2046 template <
typename TIterator,
typename TCompare>
2047 void stable_sort(TIterator first, TIterator last, TCompare compare)
2057 template <
typename TIterator>
2068 template <
typename TIterator,
typename TCompare>
2071 std::sort(first, last,
compare);
2078 template <
typename TIterator>
2081 std::sort(first, last);
2090 template <
typename TIterator,
typename TCompare>
2093 std::stable_sort(first, last,
compare);
2101 template <
typename TIterator>
2104 std::stable_sort(first, last);
2112 template <
typename TIterator,
typename T>
2116 while (first != last)
2118 sum = etl::move(sum) + *first;
2129 template <
typename TIterator,
typename T,
typename TBinaryOperation>
2133 while (first != last)
2135 sum = operation(etl::move(sum), *first);
2146 template<
typename T,
typename TCompare>
2153 template <
typename T>
2155 T
clamp(
const T& value,
const T& low,
const T& high)
2160 template<
typename T, T Low, T High,
typename TCompare>
2162 T
clamp(
const T& value, TCompare compare)
2164 return compare(value, Low) ? Low : compare(High, value) ? High : value;
2167 template <
typename T, T Low, T High>
2169 T
clamp(
const T& value)
2178 template <
typename TIterator,
typename T>
2182 first = etl::find(first, last, value);
2188 while (++itr != last)
2190 if (!(*itr == value))
2192 *first++ = etl::move(*itr);
2204 template <
typename TIterator,
typename TUnaryPredicate>
2208 first = etl::find_if(first, last,
predicate);
2214 while (++itr != last)
2218 *first++ = etl::move(*itr);
2243 template <
typename TInputIterator,
2244 typename TOutputIterator>
2271 template <
typename TInputIterator,
2272 typename TOutputIterator>
2296 template <
typename TInputIterator,
2298 typename TOutputIterator>
2320 template <
typename TInputIterator,
2322 typename TOutputIterator,
2330 while ((
n1-- > 0) && (
n2-- > 0))
2346 template <
typename TInputIterator,
2347 typename TOutputIterator,
2348 typename TUnaryPredicate>
2375 template <
typename TInputIterator,
2377 typename TOutputIterator,
2378 typename TUnaryPredicate>
2411 template <
typename TInputIterator,
typename TOutputIterator>
2415 move_s(TInputIterator i_begin,
2416 TInputIterator i_end,
2417 TOutputIterator o_begin,
2418 TOutputIterator o_end)
2420 size_t s_size = etl::distance(i_begin, i_end);
2421 size_t d_size = etl::distance(o_begin, o_end);
2422 size_t size = (s_size < d_size) ? s_size : d_size;
2424 return etl::move(i_begin, i_begin +
size, o_begin);
2438 template <
typename TInputIterator,
typename TOutputIterator>
2442 move_s(TInputIterator i_begin,
2443 TInputIterator i_end,
2444 TOutputIterator o_begin,
2445 TOutputIterator o_end)
2447 while ((i_begin != i_end) && (o_begin != o_end))
2449 *o_begin = etl::move(*i_begin);
2469 template <
typename TInputIterator,
typename TOutputIterator>
2485 template <
typename TIterator,
typename TValue>
2494 if ((it ==
end) || (*it != value))
2507 template <
typename TIterator,
2509 typename TBinaryPredicate,
2510 typename TBinaryEquality>
2533 template <
typename TIterator,
2534 typename TUnaryFunction,
2535 typename TUnaryPredicate>
2559 template <
typename TIterator,
2561 typename TUnaryFunction>
2580 template <
typename TIterator,
2582 typename TUnaryFunction,
2583 typename TUnaryPredicate>
2609 template <
typename TInputIterator,
typename TOutputIterator,
typename TUnaryFunction>
2633 template <
typename TInputIterator,
2635 typename TOutputIterator,
2636 typename TUnaryFunction>
2655 template <
typename TInputIterator1,
2656 typename TInputIterator2,
2658 typename TOutputIterator,
2659 typename TBinaryFunction>
2677 template <
typename TInputIterator,
2678 typename TOutputIterator,
2679 typename TUnaryFunction,
2680 typename TUnaryPredicate>
2706 template <
typename TInputIterator1,
2707 typename TInputIterator2,
2708 typename TOutputIterator,
2709 typename TBinaryFunction,
2710 typename TBinaryPredicate>
2738 template <
typename TInputIterator,
2740 typename TOutputIterator,
2741 typename TUnaryFunction,
2742 typename TUnaryPredicate>
2768 template <
typename TInputIterator1,
2769 typename TInputIterator2,
2771 typename TOutputIterator,
2772 typename TBinaryFunction,
2773 typename TBinaryPredicate>
2801 template <
typename TSource,
typename TDestinationTrue,
typename TDestinationFalse,
2802 typename TUnaryFunctionTrue,
typename TUnaryFunctionFalse,
2803 typename TUnaryPredicate>
2837 template <
typename TSource1,
2839 typename TDestinationTrue,
2840 typename TDestinationFalse,
2841 typename TBinaryFunctionTrue,
2842 typename TBinaryFunctionFalse,
2843 typename TBinaryPredicate>
2879 template <
typename TIterator,
typename TCompare>
2880#if ETL_USING_STD_NAMESPACE
2892 typedef typename etl::iterator_traits<TIterator>::difference_type
difference_t;
2905 etl::advance(
itr1,
k);
2906 etl::advance(
itr2,
k +
i);
2921 template <
typename TIterator>
2922#if ETL_USING_STD_NAMESPACE
2937 template <
typename TIterator,
typename TCompare>
2941 for (
TIterator itr = first; itr != last; ++itr)
2943 etl::rotate(etl::upper_bound(first, itr, *itr,
compare), itr, etl::next(itr));
2951 template <
typename TIterator>
2959 namespace private_algorithm
2961 template <
typename TIterator>
2964 get_before_last(TIterator first_, TIterator last_)
2966 TIterator last = first_;
2967 TIterator lastplus1 = first_;
2970 while (lastplus1 != last_)
2979 template <
typename TIterator>
2982 get_before_last(TIterator , TIterator last_)
2984 TIterator last = last_;
2990 template <
typename TIterator>
2993 get_before_last(TIterator , TIterator last_)
3004 template <
typename TIterator,
typename TCompare>
3009 const TIterator ilast = private_algorithm::get_before_last(first, last);
3027 using ETL_OR_STD::swap;
3036 template <
typename TIterator>
3048 template <
typename TIterator,
typename TCompare>
3052 if (!etl::is_heap(first, last,
compare))
3054 etl::make_heap(first, last,
compare);
3057 etl::sort_heap(first, last,
compare);
3064 template <
typename TIterator>
3068 if (!etl::is_heap(first, last))
3070 etl::make_heap(first, last);
3073 etl::sort_heap(first, last);
3080 template <
typename T>
3082 constexpr const T& multimax(
const T& a,
const T& b)
3084 return a < b ? b : a;
3087 template <
typename T,
typename... Tx>
3089 constexpr const T& multimax(
const T& t,
const Tx&... tx)
3091 return multimax(t, multimax(tx...));
3100 template <
typename TCompare,
typename T>
3102 constexpr const T& multimax_compare(TCompare compare,
const T& a,
const T& b)
3104 return compare(a, b) ? b : a;
3107 template <
typename TCompare,
typename T,
typename... Tx>
3109 constexpr const T& multimax_compare(TCompare compare,
const T& t,
const Tx&... tx)
3111 return multimax_compare(compare, t, multimax_compare(compare, tx...));
3119 template <
typename T>
3121 constexpr const T& multimin(
const T& a,
const T& b)
3123 return a < b ? a : b;
3126 template <
typename T,
typename... Tx>
3128 constexpr const T& multimin(
const T& t,
const Tx&... tx)
3130 return multimin(t, multimin(tx...));
3139 template <
typename TCompare,
typename T>
3141 constexpr const T& multimin_compare(TCompare compare,
const T& a,
const T& b)
3143 return compare(a, b) ? a : b;
3146 template <
typename TCompare,
typename T,
typename... Tx>
3148 constexpr const T& multimin_compare(TCompare compare,
const T& t,
const Tx&... tx)
3150 return multimin_compare(compare, t, multimin_compare(compare, tx...));
3158 template <
typename TIterator>
3160 constexpr const TIterator& multimax_iter(
const TIterator& a,
const TIterator& b)
3162 return *a < *b ? b : a;
3165 template <
typename TIterator,
typename... TIteratorx>
3167 constexpr const TIterator& multimax_iter(
const TIterator& t,
const TIteratorx&... tx)
3169 return multimax_iter(t, multimax_iter(tx...));
3178 template <
typename TCompare,
typename TIterator>
3180 constexpr const TIterator& multimax_iter_compare(TCompare compare,
const TIterator& a,
const TIterator& b)
3182 return compare(*a, *b) ? b : a;
3185 template <
typename TCompare,
typename TIterator,
typename... TIteratorx>
3187 constexpr const TIterator& multimax_iter_compare(TCompare compare,
const TIterator& t,
const TIteratorx&... tx)
3189 return multimax_iter_compare(compare, t, multimax_iter_compare(compare, tx...));
3197 template <
typename TIterator>
3199 constexpr const TIterator& multimin_iter(
const TIterator& a,
const TIterator& b)
3201 return *a < *b ? a : b;
3204 template <
typename TIterator,
typename... Tx>
3206 constexpr const TIterator& multimin_iter(
const TIterator& t,
const Tx&... tx)
3208 return multimin_iter(t, multimin_iter(tx...));
3217 template <
typename TCompare,
typename TIterator>
3219 constexpr const TIterator& multimin_iter_compare(TCompare compare,
const TIterator& a,
const TIterator& b)
3221 return compare(*a, *b) ? a : b;
3224 template <
typename TCompare,
typename TIterator,
typename... Tx>
3226 constexpr const TIterator& multimin_iter_compare(TCompare compare,
const TIterator& t,
const Tx&... tx)
3228 return multimin_iter_compare(compare, t, multimin_iter_compare(compare, tx...));
3237 template <
typename TIterator,
typename TPredicate>
3253 using ETL_OR_STD::swap;
3267 template <
typename TIterator,
typename TPredicate>
3272 while (first != last)
3291 using ETL_OR_STD::swap;
3292 swap(*first, *last);
3300 namespace private_algorithm
3302 using ETL_OR_STD::swap;
3304 template <
typename TIterator,
typename TCompare>
3305#if (ETL_USING_CPP20 && ETL_USING_STL) || (ETL_USING_CPP14 && ETL_NOT_USING_STL && !defined(ETL_IN_UNIT_TEST))
3308 TIterator nth_partition(TIterator first, TIterator last, TCompare compare)
3310 typedef typename etl::iterator_traits<TIterator>::value_type value_type;
3312 TIterator pivot = last;
3313 value_type pivot_value = *pivot;
3318 swap(*pivot, *last);
3321 TIterator i = first;
3323 for (TIterator j = first; j < last; ++j)
3325 if (!compare(pivot_value, *j))
3343 template <typename TIterator, typename TCompare = etl::less<typename etl::iterator_traits<TIterator>::value_type>>
3344#if (ETL_USING_CPP20 && ETL_USING_STL) || (ETL_USING_CPP14 && ETL_NOT_USING_STL && !defined(ETL_IN_UNIT_TEST))
3348 nth_element(TIterator first, TIterator nth, TIterator last, TCompare compare = TCompare())
3358 while (first <= last)
3360 TIterator p = private_algorithm::nth_partition(first, last, compare);
3380 template <
typename TIterator,
typename TCompare>
3392 while (first <= last)
3412 template <
typename TIterator>
3414 nth_element(TIterator first, TIterator nth, TIterator last)
ETL_CONSTEXPR T clamp(const T &value, const T &low, const T &high, TCompare compare)
Definition algorithm.h:2148
ETL_CONSTEXPR20 void shell_sort(TIterator first, TIterator last)
Definition algorithm.h:2927
ETL_CONSTEXPR14 TOutputIterator copy_if(TIterator begin, TIterator end, TOutputIterator out, TUnaryPredicate predicate)
Definition algorithm.h:1954
ETL_CONSTEXPR14 ETL_OR_STD::pair< TDestinationTrue, TDestinationFalse > partition_transform(TSource begin, TSource end, TDestinationTrue destination_true, TDestinationFalse destination_false, TUnaryFunctionTrue function_true, TUnaryFunctionFalse function_false, TUnaryPredicate predicate)
Definition algorithm.h:2805
ETL_NODISCARD ETL_CONSTEXPR14 bool any_of(TIterator begin, TIterator end, TUnaryPredicate predicate)
Definition algorithm.h:1996
ETL_NODISCARD ETL_CONSTEXPR14 TIterator min_element(TIterator begin, TIterator end, TCompare compare)
Definition algorithm.h:1447
ETL_CONSTEXPR14 TOutputIterator transform_n_if(TInputIterator i_begin, TSize n, TOutputIterator o_begin, TUnaryFunction function, TUnaryPredicate predicate)
Definition algorithm.h:2744
ETL_CONSTEXPR14 T accumulate(TIterator first, TIterator last, T sum)
Definition algorithm.h:2114
ETL_NODISCARD ETL_CONSTEXPR14 bool all_of(TIterator begin, TIterator end, TUnaryPredicate predicate)
Definition algorithm.h:1981
ETL_NODISCARD ETL_CONSTEXPR14 ETL_OR_STD::pair< TIterator, TIterator > minmax_element(TIterator begin, TIterator end, TCompare compare)
Definition algorithm.h:1535
ETL_CONSTEXPR14 TOutputIterator transform_if(TInputIterator i_begin, const TInputIterator i_end, TOutputIterator o_begin, TUnaryFunction function, TUnaryPredicate predicate)
Definition algorithm.h:2682
ETL_CONSTEXPR14 TUnaryFunction for_each_if(TIterator begin, const TIterator end, TUnaryFunction function, TUnaryPredicate predicate)
Definition algorithm.h:2537
ETL_NODISCARD ETL_CONSTEXPR14 TIterator find_if_not(TIterator begin, TIterator end, TUnaryPredicate predicate)
Definition algorithm.h:1702
ETL_NODISCARD ETL_CONSTEXPR14 bool is_sorted(TIterator begin, TIterator end)
Definition algorithm.h:1673
ETL_CONSTEXPR14 TOutputIterator transform_s(TInputIterator i_begin, TInputIterator i_end, TOutputIterator o_begin, TOutputIterator o_end, TUnaryFunction function)
Definition algorithm.h:2611
ETL_CONSTEXPR14 TIterator remove(TIterator first, TIterator last, const T &value)
Definition algorithm.h:2180
ETL_CONSTEXPR14 void transform_n(TInputIterator i_begin, TSize n, TOutputIterator o_begin, TUnaryFunction function)
Definition algorithm.h:2638
ETL_CONSTEXPR14 TOutputIterator copy_n_if(TInputIterator i_begin, TSize n, TOutputIterator o_begin, TUnaryPredicate predicate)
Definition algorithm.h:2380
ETL_NODISCARD ETL_CONSTEXPR14 TIterator is_sorted_until(TIterator begin, TIterator end)
Definition algorithm.h:1614
ETL_CONSTEXPR14 void insertion_sort(TIterator first, TIterator last)
Definition algorithm.h:2953
void sort(TIterator first, TIterator last, TCompare compare)
Definition algorithm.h:2069
ETL_NODISCARD ETL_CONSTEXPR14 ETL_OR_STD::pair< const T &, const T & > minmax(const T &a, const T &b)
Definition algorithm.h:1585
ETL_CONSTEXPR14 etl::enable_if< etl::is_random_iterator< TInputIterator >::value &&etl::is_random_iterator< TOutputIterator >::value, TOutputIterator >::type copy_s(TInputIterator i_begin, TInputIterator i_end, TOutputIterator o_begin, TOutputIterator o_end)
Definition algorithm.h:2248
ETL_CONSTEXPR14 TIterator remove_if(TIterator first, TIterator last, TUnaryPredicate predicate)
Definition algorithm.h:2206
ETL_CONSTEXPR14 ETL_OR_STD::pair< TDestinationTrue, TDestinationFalse > partition_copy(TSource begin, TSource end, TDestinationTrue destination_true, TDestinationFalse destination_false, TUnaryPredicate predicate)
Definition algorithm.h:1922
ETL_CONSTEXPR14 TIterator for_each_n(TIterator begin, TSize n, TUnaryFunction function)
Definition algorithm.h:2563
ETL_NODISCARD ETL_CONSTEXPR14 TIterator binary_find(TIterator begin, TIterator end, const TValue &value)
Definition algorithm.h:2488
ETL_CONSTEXPR14 void heap_sort(TIterator first, TIterator last, TCompare compare)
Definition algorithm.h:3050
ETL_NODISCARD ETL_CONSTEXPR14 bool none_of(TIterator begin, TIterator end, TUnaryPredicate predicate)
Definition algorithm.h:2011
ETL_CONSTEXPR20 void selection_sort(TIterator first, TIterator last, TCompare compare)
Definition algorithm.h:3006
ETL_CONSTEXPR14 TOutputIterator copy_n_s(TInputIterator i_begin, TSize n, TOutputIterator o_begin, TOutputIterator o_end)
Definition algorithm.h:2300
TOutputIterator move_s(TInputIterator i_begin, TInputIterator i_end, TOutputIterator o_begin, TOutputIterator o_end)
Definition algorithm.h:2470
ETL_CONSTEXPR14 TOutputIterator copy_if_s(TInputIterator i_begin, TInputIterator i_end, TOutputIterator o_begin, TOutputIterator o_end, TUnaryPredicate predicate)
Definition algorithm.h:2350
ETL_CONSTEXPR14 TIterator for_each_n_if(TIterator begin, TSize n, TUnaryFunction function, TUnaryPredicate predicate)
Definition algorithm.h:2585
void stable_sort(TIterator first, TIterator last, TCompare compare)
Definition algorithm.h:2091
ETL_NODISCARD ETL_CONSTEXPR14 bool is_partitioned(TIterator begin, TIterator end, TUnaryPredicate predicate)
Definition algorithm.h:1862
ETL_NODISCARD ETL_CONSTEXPR14 TIterator max_element(TIterator begin, TIterator end, TCompare compare)
Definition algorithm.h:1491
ETL_NODISCARD ETL_CONSTEXPR14 TIterator partition_point(TIterator begin, TIterator end, TUnaryPredicate predicate)
Definition algorithm.h:1897
ETL_NODISCARD ETL_CONSTEXPR14 bool is_permutation(TIterator1 begin1, TIterator1 end1, TIterator2 begin2)
Definition algorithm.h:1727
enable_if
Definition type_traits_generator.h:1191
is_reference
Definition type_traits_generator.h:1111
is_same
Definition type_traits_generator.h:1041
bitset_ext
Definition absolute.h:38
etl::enable_if< etl::is_random_access_iterator_concept< TIterator >::value, void >::type nth_element(TIterator first, TIterator nth, TIterator last, TCompare compare)
Definition algorithm.h:3382
void swap(etl::array< T, SIZE > &lhs, etl::array< T, SIZE > &rhs)
Template deduction guides.
Definition array.h:630
ETL_CONSTEXPR TContainer::size_type size(const TContainer &container)
Definition iterator.h:1187
ETL_CONSTEXPR TContainer::iterator begin(TContainer &container)
Definition iterator.h:962
ETL_CONSTEXPR14 etl::enable_if< etl::is_forward_iterator< TIterator >::value, TIterator >::type partition(TIterator first, TIterator last, TPredicate predicate)
Returns the maximum value.
Definition algorithm.h:3240
ETL_CONSTEXPR TContainer::iterator end(TContainer &container)
Definition iterator.h:992
Definition iterator.h:854
Definition iterator.h:873
Definition functional.h:135
pair holds two objects of arbitrary type
Definition utility.h:164
Definition algorithm.h:95