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>
1476 template <
typename TIterator>
1482 typedef typename etl::iterator_traits<TIterator>::value_type
value_t;
1492 template <
typename TIterator,
typename TCompare>
1524 template <
typename TIterator>
1530 typedef typename etl::iterator_traits<TIterator>::value_type
value_t;
1540 template <
typename TIterator,
typename TCompare>
1570 return ETL_OR_STD::pair<TIterator, TIterator>(
minimum, maximum);
1578 template <
typename TIterator>
1584 typedef typename etl::iterator_traits<TIterator>::value_type
value_t;
1594 template <
typename T>
1597 ETL_OR_STD::pair<const T&, const T&>
minmax(
const T& a,
1600 return (
b < a) ? ETL_OR_STD::pair<const T&, const T&>(
b, a) : ETL_OR_STD::pair<const T&, const T&>(a,
b);
1608 template <
typename T,
typename TCompare>
1611 ETL_OR_STD::pair<const T&, const T&>
minmax(
const T& a,
1615 return compare(
b, a) ? ETL_OR_STD::pair<const T&, const T&>(
b, a) : ETL_OR_STD::pair<const T&, const T&>(a,
b);
1623 template <
typename TIterator>
1633 while (++next !=
end)
1652 template <
typename TIterator,
typename TCompare>
1663 while (++next !=
end)
1682 template<
typename TIterator>
1696 template<
typename TIterator,
typename TCompare>
1711 template <
typename TIterator,
typename TUnaryPredicate>
1736 template <
typename TIterator1,
typename TIterator2>
1755 if (
n == 0 ||
size_t(etl::count(
i,
end1, *
i)) !=
n)
1771 template <
typename TIterator1,
typename TIterator2,
typename TBinaryPredicate>
1791 if (
n == 0 ||
size_t(etl::count(
i,
end1, *
i)) !=
n)
1807 template <
typename TIterator1,
typename TIterator2>
1823 if (
n == 0 ||
size_t(etl::count(
i,
end1, *
i)) !=
n)
1839 template <
typename TIterator1,
typename TIterator2,
typename TBinaryPredicate>
1855 if (
n == 0 ||
size_t(etl::count(
i,
end1, *
i)) !=
n)
1871 template <
typename TIterator,
typename TUnaryPredicate>
1906 template <
typename TIterator,
typename TUnaryPredicate>
1932 template <
typename TSource,
typename TDestinationTrue,
typename TDestinationFalse,
typename TUnaryPredicate>
1964 template <
typename TIterator,
typename TOutputIterator,
typename TUnaryPredicate>
1990 template <
typename TIterator,
typename TUnaryPredicate>
2005 template <
typename TIterator,
typename TUnaryPredicate>
2020 template <
typename TIterator,
typename TUnaryPredicate>
2030#if ETL_NOT_USING_STL
2036 template <
typename TIterator,
typename TCompare>
2037 void sort(TIterator first, TIterator last, TCompare compare)
2046 template <
typename TIterator>
2047 void sort(TIterator first, TIterator last)
2058 template <
typename TIterator,
typename TCompare>
2059 void stable_sort(TIterator first, TIterator last, TCompare compare)
2069 template <
typename TIterator>
2080 template <
typename TIterator,
typename TCompare>
2083 std::sort(first, last,
compare);
2090 template <
typename TIterator>
2093 std::sort(first, last);
2102 template <
typename TIterator,
typename TCompare>
2105 std::stable_sort(first, last,
compare);
2113 template <
typename TIterator>
2116 std::stable_sort(first, last);
2124 template <
typename TIterator,
typename T>
2128 while (first != last)
2130 sum = etl::move(sum) + *first;
2141 template <
typename TIterator,
typename T,
typename TBinaryOperation>
2145 while (first != last)
2147 sum = operation(etl::move(sum), *first);
2158 template<
typename T,
typename TCompare>
2165 template <
typename T>
2167 T
clamp(
const T& value,
const T& low,
const T& high)
2172 template<
typename T, T Low, T High,
typename TCompare>
2174 T
clamp(
const T& value, TCompare compare)
2176 return compare(value, Low) ? Low : compare(High, value) ? High : value;
2179 template <
typename T, T Low, T High>
2181 T
clamp(
const T& value)
2190 template <
typename TIterator,
typename T>
2194 first = etl::find(first, last, value);
2200 while (++itr != last)
2202 if (!(*itr == value))
2204 *first++ = etl::move(*itr);
2216 template <
typename TIterator,
typename TUnaryPredicate>
2220 first = etl::find_if(first, last,
predicate);
2226 while (++itr != last)
2230 *first++ = etl::move(*itr);
2255 template <
typename TInputIterator,
2256 typename TOutputIterator>
2283 template <
typename TInputIterator,
2284 typename TOutputIterator>
2308 template <
typename TInputIterator,
2310 typename TOutputIterator>
2332 template <
typename TInputIterator,
2334 typename TOutputIterator,
2342 while ((
n1-- > 0) && (
n2-- > 0))
2358 template <
typename TInputIterator,
2359 typename TOutputIterator,
2360 typename TUnaryPredicate>
2387 template <
typename TInputIterator,
2389 typename TOutputIterator,
2390 typename TUnaryPredicate>
2423 template <
typename TInputIterator,
typename TOutputIterator>
2427 move_s(TInputIterator i_begin,
2428 TInputIterator i_end,
2429 TOutputIterator o_begin,
2430 TOutputIterator o_end)
2432 size_t s_size = etl::distance(i_begin, i_end);
2433 size_t d_size = etl::distance(o_begin, o_end);
2434 size_t size = (s_size < d_size) ? s_size : d_size;
2436 return etl::move(i_begin, i_begin +
size, o_begin);
2450 template <
typename TInputIterator,
typename TOutputIterator>
2454 move_s(TInputIterator i_begin,
2455 TInputIterator i_end,
2456 TOutputIterator o_begin,
2457 TOutputIterator o_end)
2459 while ((i_begin != i_end) && (o_begin != o_end))
2461 *o_begin = etl::move(*i_begin);
2481 template <
typename TInputIterator,
typename TOutputIterator>
2497 template <
typename TIterator,
typename TValue>
2506 if ((it ==
end) || (*it != value))
2519 template <
typename TIterator,
2521 typename TBinaryPredicate,
2522 typename TBinaryEquality>
2545 template <
typename TIterator,
2546 typename TUnaryFunction,
2547 typename TUnaryPredicate>
2571 template <
typename TIterator,
2573 typename TUnaryFunction>
2592 template <
typename TIterator,
2594 typename TUnaryFunction,
2595 typename TUnaryPredicate>
2621 template <
typename TInputIterator,
typename TOutputIterator,
typename TUnaryFunction>
2645 template <
typename TInputIterator,
2647 typename TOutputIterator,
2648 typename TUnaryFunction>
2667 template <
typename TInputIterator1,
2668 typename TInputIterator2,
2670 typename TOutputIterator,
2671 typename TBinaryFunction>
2689 template <
typename TInputIterator,
2690 typename TOutputIterator,
2691 typename TUnaryFunction,
2692 typename TUnaryPredicate>
2718 template <
typename TInputIterator1,
2719 typename TInputIterator2,
2720 typename TOutputIterator,
2721 typename TBinaryFunction,
2722 typename TBinaryPredicate>
2750 template <
typename TInputIterator,
2752 typename TOutputIterator,
2753 typename TUnaryFunction,
2754 typename TUnaryPredicate>
2780 template <
typename TInputIterator1,
2781 typename TInputIterator2,
2783 typename TOutputIterator,
2784 typename TBinaryFunction,
2785 typename TBinaryPredicate>
2813 template <
typename TSource,
typename TDestinationTrue,
typename TDestinationFalse,
2814 typename TUnaryFunctionTrue,
typename TUnaryFunctionFalse,
2815 typename TUnaryPredicate>
2849 template <
typename TSource1,
2851 typename TDestinationTrue,
2852 typename TDestinationFalse,
2853 typename TBinaryFunctionTrue,
2854 typename TBinaryFunctionFalse,
2855 typename TBinaryPredicate>
2891 template <
typename TIterator,
typename TCompare>
2892#if ETL_USING_STD_NAMESPACE
2904 typedef typename etl::iterator_traits<TIterator>::difference_type
difference_t;
2917 etl::advance(
itr1,
k);
2918 etl::advance(
itr2,
k +
i);
2933 template <
typename TIterator>
2934#if ETL_USING_STD_NAMESPACE
2949 template <
typename TIterator,
typename TCompare>
2953 for (
TIterator itr = first; itr != last; ++itr)
2955 etl::rotate(etl::upper_bound(first, itr, *itr,
compare), itr, etl::next(itr));
2963 template <
typename TIterator>
2971 namespace private_algorithm
2973 template <
typename TIterator>
2976 get_before_last(TIterator first_, TIterator last_)
2978 TIterator last = first_;
2979 TIterator lastplus1 = first_;
2982 while (lastplus1 != last_)
2991 template <
typename TIterator>
2994 get_before_last(TIterator , TIterator last_)
2996 TIterator last = last_;
3002 template <
typename TIterator>
3005 get_before_last(TIterator , TIterator last_)
3016 template <
typename TIterator,
typename TCompare>
3021 const TIterator ilast = private_algorithm::get_before_last(first, last);
3039 using ETL_OR_STD::swap;
3048 template <
typename TIterator>
3060 template <
typename TIterator,
typename TCompare>
3064 if (!etl::is_heap(first, last,
compare))
3066 etl::make_heap(first, last,
compare);
3069 etl::sort_heap(first, last,
compare);
3076 template <
typename TIterator>
3080 if (!etl::is_heap(first, last))
3082 etl::make_heap(first, last);
3085 etl::sort_heap(first, last);
3092 template <
typename T>
3094 constexpr const T& multimax(
const T& a,
const T& b)
3096 return a < b ? b : a;
3099 template <
typename T,
typename... Tx>
3101 constexpr const T& multimax(
const T& t,
const Tx&... tx)
3103 return multimax(t, multimax(tx...));
3112 template <
typename TCompare,
typename T>
3114 constexpr const T& multimax_compare(TCompare compare,
const T& a,
const T& b)
3116 return compare(a, b) ? b : a;
3119 template <
typename TCompare,
typename T,
typename... Tx>
3121 constexpr const T& multimax_compare(TCompare compare,
const T& t,
const Tx&... tx)
3123 return multimax_compare(compare, t, multimax_compare(compare, tx...));
3131 template <
typename T>
3133 constexpr const T& multimin(
const T& a,
const T& b)
3135 return a < b ? a : b;
3138 template <
typename T,
typename... Tx>
3140 constexpr const T& multimin(
const T& t,
const Tx&... tx)
3142 return multimin(t, multimin(tx...));
3151 template <
typename TCompare,
typename T>
3153 constexpr const T& multimin_compare(TCompare compare,
const T& a,
const T& b)
3155 return compare(a, b) ? a : b;
3158 template <
typename TCompare,
typename T,
typename... Tx>
3160 constexpr const T& multimin_compare(TCompare compare,
const T& t,
const Tx&... tx)
3162 return multimin_compare(compare, t, multimin_compare(compare, tx...));
3170 template <
typename TIterator>
3172 constexpr const TIterator& multimax_iter(
const TIterator& a,
const TIterator& b)
3174 return *a < *b ? b : a;
3177 template <
typename TIterator,
typename... TIteratorx>
3179 constexpr const TIterator& multimax_iter(
const TIterator& t,
const TIteratorx&... tx)
3181 return multimax_iter(t, multimax_iter(tx...));
3190 template <
typename TCompare,
typename TIterator>
3192 constexpr const TIterator& multimax_iter_compare(TCompare compare,
const TIterator& a,
const TIterator& b)
3194 return compare(*a, *b) ? b : a;
3197 template <
typename TCompare,
typename TIterator,
typename... TIteratorx>
3199 constexpr const TIterator& multimax_iter_compare(TCompare compare,
const TIterator& t,
const TIteratorx&... tx)
3201 return multimax_iter_compare(compare, t, multimax_iter_compare(compare, tx...));
3209 template <
typename TIterator>
3211 constexpr const TIterator& multimin_iter(
const TIterator& a,
const TIterator& b)
3213 return *a < *b ? a : b;
3216 template <
typename TIterator,
typename... Tx>
3218 constexpr const TIterator& multimin_iter(
const TIterator& t,
const Tx&... tx)
3220 return multimin_iter(t, multimin_iter(tx...));
3229 template <
typename TCompare,
typename TIterator>
3231 constexpr const TIterator& multimin_iter_compare(TCompare compare,
const TIterator& a,
const TIterator& b)
3233 return compare(*a, *b) ? a : b;
3236 template <
typename TCompare,
typename TIterator,
typename... Tx>
3238 constexpr const TIterator& multimin_iter_compare(TCompare compare,
const TIterator& t,
const Tx&... tx)
3240 return multimin_iter_compare(compare, t, multimin_iter_compare(compare, tx...));
3249 template <
typename TIterator,
typename TPredicate>
3265 using ETL_OR_STD::swap;
3279 template <
typename TIterator,
typename TPredicate>
3284 while (first != last)
3303 using ETL_OR_STD::swap;
3304 swap(*first, *last);
3312 namespace private_algorithm
3314 using ETL_OR_STD::swap;
3316 template <
typename TIterator,
typename TCompare>
3317#if (ETL_USING_CPP20 && ETL_USING_STL) || (ETL_USING_CPP14 && ETL_NOT_USING_STL && !defined(ETL_IN_UNIT_TEST))
3320 TIterator nth_partition(TIterator first, TIterator last, TCompare compare)
3322 typedef typename etl::iterator_traits<TIterator>::value_type value_type;
3324 TIterator pivot = last;
3325 value_type pivot_value = *pivot;
3330 swap(*pivot, *last);
3333 TIterator i = first;
3335 for (TIterator j = first; j < last; ++j)
3337 if (!compare(pivot_value, *j))
3355 template <typename TIterator, typename TCompare = etl::less<typename etl::iterator_traits<TIterator>::value_type>>
3356#if (ETL_USING_CPP20 && ETL_USING_STL) || (ETL_USING_CPP14 && ETL_NOT_USING_STL && !defined(ETL_IN_UNIT_TEST))
3360 nth_element(TIterator first, TIterator nth, TIterator last, TCompare compare = TCompare())
3370 while (first <= last)
3372 TIterator p = private_algorithm::nth_partition(first, last, compare);
3392 template <
typename TIterator,
typename TCompare>
3404 while (first <= last)
3424 template <
typename TIterator>
3426 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:2160
ETL_CONSTEXPR20 void shell_sort(TIterator first, TIterator last)
Definition algorithm.h:2939
ETL_CONSTEXPR14 TOutputIterator copy_if(TIterator begin, TIterator end, TOutputIterator out, TUnaryPredicate predicate)
Definition algorithm.h:1966
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:2817
ETL_NODISCARD ETL_CONSTEXPR14 bool any_of(TIterator begin, TIterator end, TUnaryPredicate predicate)
Definition algorithm.h:2008
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:2756
ETL_CONSTEXPR14 T accumulate(TIterator first, TIterator last, T sum)
Definition algorithm.h:2126
ETL_NODISCARD ETL_CONSTEXPR14 bool all_of(TIterator begin, TIterator end, TUnaryPredicate predicate)
Definition algorithm.h:1993
ETL_NODISCARD ETL_CONSTEXPR14 ETL_OR_STD::pair< TIterator, TIterator > minmax_element(TIterator begin, TIterator end, TCompare compare)
Definition algorithm.h:1543
ETL_CONSTEXPR14 TOutputIterator transform_if(TInputIterator i_begin, const TInputIterator i_end, TOutputIterator o_begin, TUnaryFunction function, TUnaryPredicate predicate)
Definition algorithm.h:2694
ETL_CONSTEXPR14 TUnaryFunction for_each_if(TIterator begin, const TIterator end, TUnaryFunction function, TUnaryPredicate predicate)
Definition algorithm.h:2549
ETL_NODISCARD ETL_CONSTEXPR14 TIterator find_if_not(TIterator begin, TIterator end, TUnaryPredicate predicate)
Definition algorithm.h:1714
ETL_NODISCARD ETL_CONSTEXPR14 bool is_sorted(TIterator begin, TIterator end)
Definition algorithm.h:1685
ETL_CONSTEXPR14 TOutputIterator transform_s(TInputIterator i_begin, TInputIterator i_end, TOutputIterator o_begin, TOutputIterator o_end, TUnaryFunction function)
Definition algorithm.h:2623
ETL_CONSTEXPR14 TIterator remove(TIterator first, TIterator last, const T &value)
Definition algorithm.h:2192
ETL_CONSTEXPR14 void transform_n(TInputIterator i_begin, TSize n, TOutputIterator o_begin, TUnaryFunction function)
Definition algorithm.h:2650
ETL_CONSTEXPR14 TOutputIterator copy_n_if(TInputIterator i_begin, TSize n, TOutputIterator o_begin, TUnaryPredicate predicate)
Definition algorithm.h:2392
ETL_NODISCARD ETL_CONSTEXPR14 TIterator is_sorted_until(TIterator begin, TIterator end)
Definition algorithm.h:1626
ETL_CONSTEXPR14 void insertion_sort(TIterator first, TIterator last)
Definition algorithm.h:2965
void sort(TIterator first, TIterator last, TCompare compare)
Definition algorithm.h:2081
ETL_NODISCARD ETL_CONSTEXPR14 ETL_OR_STD::pair< const T &, const T & > minmax(const T &a, const T &b)
Definition algorithm.h:1597
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:2260
ETL_CONSTEXPR14 TIterator remove_if(TIterator first, TIterator last, TUnaryPredicate predicate)
Definition algorithm.h:2218
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:1934
ETL_CONSTEXPR14 TIterator for_each_n(TIterator begin, TSize n, TUnaryFunction function)
Definition algorithm.h:2575
ETL_NODISCARD ETL_CONSTEXPR14 TIterator binary_find(TIterator begin, TIterator end, const TValue &value)
Definition algorithm.h:2500
ETL_CONSTEXPR14 void heap_sort(TIterator first, TIterator last, TCompare compare)
Definition algorithm.h:3062
ETL_NODISCARD ETL_CONSTEXPR14 bool none_of(TIterator begin, TIterator end, TUnaryPredicate predicate)
Definition algorithm.h:2023
ETL_CONSTEXPR20 void selection_sort(TIterator first, TIterator last, TCompare compare)
Definition algorithm.h:3018
ETL_CONSTEXPR14 TOutputIterator copy_n_s(TInputIterator i_begin, TSize n, TOutputIterator o_begin, TOutputIterator o_end)
Definition algorithm.h:2312
TOutputIterator move_s(TInputIterator i_begin, TInputIterator i_end, TOutputIterator o_begin, TOutputIterator o_end)
Definition algorithm.h:2482
ETL_CONSTEXPR14 TOutputIterator copy_if_s(TInputIterator i_begin, TInputIterator i_end, TOutputIterator o_begin, TOutputIterator o_end, TUnaryPredicate predicate)
Definition algorithm.h:2362
ETL_CONSTEXPR14 TIterator for_each_n_if(TIterator begin, TSize n, TUnaryFunction function, TUnaryPredicate predicate)
Definition algorithm.h:2597
void stable_sort(TIterator first, TIterator last, TCompare compare)
Definition algorithm.h:2103
ETL_NODISCARD ETL_CONSTEXPR14 bool is_partitioned(TIterator begin, TIterator end, TUnaryPredicate predicate)
Definition algorithm.h:1874
ETL_NODISCARD ETL_CONSTEXPR14 TIterator max_element(TIterator begin, TIterator end, TCompare compare)
Definition algorithm.h:1495
ETL_NODISCARD ETL_CONSTEXPR14 TIterator partition_point(TIterator begin, TIterator end, TUnaryPredicate predicate)
Definition algorithm.h:1909
ETL_NODISCARD ETL_CONSTEXPR14 bool is_permutation(TIterator1 begin1, TIterator1 end1, TIterator2 begin2)
Definition algorithm.h:1739
enable_if
Definition type_traits_generator.h:1186
is_reference
Definition type_traits_generator.h:1106
is_same
Definition type_traits_generator.h:1036
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:3394
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:3252
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