33#ifndef ETL_ALGORITHM_INCLUDED
34#define ETL_ALGORITHM_INCLUDED
63 template <
typename TIterator>
64#if ETL_USING_STD_NAMESPACE
69 void shell_sort(TIterator first, TIterator last);
71 template <
typename TIterator,
typename TCompare>
72#if ETL_USING_STD_NAMESPACE
77 void shell_sort(TIterator first, TIterator last, TCompare compare);
79 template <
typename TIterator>
80 ETL_CONSTEXPR14
void insertion_sort(TIterator first, TIterator last);
82 template <
typename TIterator,
typename TCompare>
83 ETL_CONSTEXPR14
void insertion_sort(TIterator first, TIterator last, TCompare compare);
94 template <
typename TIterator1,
typename TIterator2>
95#if ETL_USING_STD_NAMESPACE
100 void iter_swap(TIterator1 a, TIterator2 b)
109 template <
typename TIterator1,
typename TIterator2>
110#if ETL_USING_STD_NAMESPACE
115 TIterator2 swap_ranges(TIterator1 first1,
119 while (first1 != last1)
121 iter_swap(first1, first2);
131#if ETL_USING_STL && ETL_USING_CPP20
133 template <
typename TIterator1,
typename TIterator2>
134 constexpr TIterator2 copy(TIterator1 sb, TIterator1 se, TIterator2 db)
136 return std::copy(sb, se, db);
140 template <
typename TIterator1,
typename TIterator2>
141 ETL_CONSTEXPR14 TIterator2 copy(TIterator1 sb, TIterator1 se, TIterator2 db)
156#if ETL_USING_STL && ETL_USING_CPP20
157 template <
typename TIterator1,
typename TIterator2>
158 constexpr TIterator2 reverse_copy(TIterator1 sb, TIterator1 se, TIterator2 db)
160 return std::reverse_copy(sb, se, db);
163 template <
typename TIterator1,
typename TIterator2>
165 TIterator2 reverse_copy(TIterator1 sb, TIterator1 se, TIterator2 db)
179#if ETL_USING_STL && ETL_USING_CPP20
181 template <
typename TIterator1,
typename TSize,
typename TIterator2>
182 constexpr TIterator2 copy_n(TIterator1 sb, TSize count, TIterator2 db)
184 return std::copy_n(sb, count, db);
188 template <
typename TIterator1,
typename TSize,
typename TIterator2>
189 ETL_CONSTEXPR14 TIterator2 copy_n(TIterator1 sb, TSize count, TIterator2 db)
205#if ETL_USING_STL && ETL_USING_CPP20
206 template <
typename TIterator1,
typename TIterator2>
207 constexpr TIterator2 copy_backward(TIterator1 sb, TIterator1 se, TIterator2 de)
209 return std::copy_backward(sb, se, de);
212 template <
typename TIterator1,
typename TIterator2>
213 ETL_CONSTEXPR14 TIterator2 copy_backward(TIterator1 sb, TIterator1 se, TIterator2 de)
226#if ETL_USING_STL && ETL_USING_CPP20
227 template <
typename TIterator1,
typename TIterator2>
228 constexpr TIterator2 move(TIterator1 sb, TIterator1 se, TIterator2 db)
230 return std::move(sb, se, db);
234 template <
typename TIterator1,
typename TIterator2>
235 ETL_CONSTEXPR14 TIterator2 move(TIterator1 sb, TIterator1 se, TIterator2 db)
239 *db = etl::move(*sb);
250#if ETL_USING_STL && ETL_USING_CPP20
251 template <
typename TIterator1,
typename TIterator2>
253 TIterator2 move_backward(TIterator1 sb, TIterator1 se, TIterator2 de)
255 return std::move_backward(sb, se, de);
259 template <
typename TIterator1,
typename TIterator2>
260 ETL_CONSTEXPR14 TIterator2 move_backward(TIterator1 sb, TIterator1 se, TIterator2 de)
264 *(--de) = etl::move(*(--se));
275 template <
typename TIterator>
277 reverse(TIterator b, TIterator e)
283 etl::iter_swap(b, e);
290 template <
typename TIterator>
292 reverse(TIterator b, TIterator e)
294 while ((b != e) && (b != --e))
296 etl::iter_swap(b++, e);
303 template<
typename TIterator,
typename TValue,
typename TCompare>
306 TIterator lower_bound(TIterator first, TIterator last,
const TValue& value, TCompare compare)
308 typedef typename etl::iterator_traits<TIterator>::difference_type difference_t;
310 difference_t count = etl::distance(first, last);
314 TIterator itr = first;
315 difference_t step = count / 2;
317 etl::advance(itr, step);
319 if (compare(*itr, value))
333 template<
typename TIterator,
typename TValue>
336 TIterator lower_bound(TIterator first, TIterator last,
const TValue& value)
340 return etl::lower_bound(first, last, value, compare());
346 template<
typename TIterator,
typename TValue,
typename TCompare>
349 TIterator upper_bound(TIterator first, TIterator last,
const TValue& value, TCompare compare)
351 typedef typename etl::iterator_traits<TIterator>::difference_type difference_t;
353 difference_t count = etl::distance(first, last);
357 TIterator itr = first;
358 difference_t step = count / 2;
360 etl::advance(itr, step);
362 if (!compare(value, *itr))
376 template<
typename TIterator,
typename TValue>
379 TIterator upper_bound(TIterator first, TIterator last,
const TValue& value)
383 return etl::upper_bound(first, last, value, compare());
389 template<
typename TIterator,
typename TValue,
typename TCompare>
392 ETL_OR_STD::pair<TIterator, TIterator> equal_range(TIterator first, TIterator last,
const TValue& value, TCompare compare)
395 etl::upper_bound(first, last, value, compare));
398 template<
typename TIterator,
typename TValue>
400 ETL_OR_STD::pair<TIterator, TIterator> equal_range(TIterator first, TIterator last,
const TValue& value)
405 etl::upper_bound(first, last, value, compare()));
411 template <
typename TIterator,
typename T,
typename Compare>
413 bool binary_search(TIterator first, TIterator last,
const T& value, Compare compare)
415 first = etl::lower_bound(first, last, value, compare);
417 return (!(first == last) && !(compare(value, *first)));
420 template <
typename TIterator,
typename T>
422 bool binary_search(TIterator first, TIterator last,
const T& value)
426 return binary_search(first, last, value, compare());
432 template <
typename TIterator,
typename TUnaryPredicate>
435 TIterator find_if(TIterator first, TIterator last, TUnaryPredicate predicate)
437 while (first != last)
439 if (predicate(*first))
453 template <
typename TIterator,
typename T>
456 TIterator find(TIterator first, TIterator last,
const T& value)
458 while (first != last)
473#if ETL_USING_STL && ETL_USING_CPP20
474 template<
typename TIterator,
typename TValue>
475 constexpr void fill(TIterator first, TIterator last,
const TValue& value)
477 std::fill(first, last, value);
480 template<
typename TIterator,
typename TValue>
481 ETL_CONSTEXPR14
void fill(TIterator first, TIterator last,
const TValue& value)
483 while (first != last)
493#if ETL_USING_STL && ETL_USING_CPP20
494 template<
typename TIterator,
typename TSize,
typename TValue>
495 constexpr TIterator fill_n(TIterator first, TSize count,
const TValue& value)
497 return std::fill_n(first, count, value);
500 template<
typename TIterator,
typename TSize,
typename TValue>
501 ETL_CONSTEXPR14 TIterator fill_n(TIterator first, TSize count,
const TValue& value)
516 template <
typename TIterator,
typename T>
519 typename etl::iterator_traits<TIterator>::difference_type count(TIterator first, TIterator last,
const T& value)
521 typename iterator_traits<TIterator>::difference_type n = 0;
523 while (first != last)
539 template <
typename TIterator,
typename TUnaryPredicate>
542 typename etl::iterator_traits<TIterator>::difference_type
543 count_if(TIterator first, TIterator last, TUnaryPredicate predicate)
545 typename iterator_traits<TIterator>::difference_type n = 0;
547 while (first != last)
549 if (predicate(*first))
562#if ETL_USING_STL && ETL_USING_CPP20
563 template <
typename TIterator1,
typename TIterator2>
566 bool equal(TIterator1 first1, TIterator1 last1, TIterator2 first2)
568 return std::equal(first1, last1, first2);
571 template <
typename TIterator1,
typename TIterator2,
typename TPredicate>
574 bool equal(TIterator1 first1, TIterator1 last1, TIterator2 first2, TPredicate predicate)
576 return std::equal(first1, last1, first2, predicate);
580 template <
typename TIterator1,
typename TIterator2>
583 bool equal(TIterator1 first1, TIterator1 last1, TIterator2 first2)
585 while (first1 != last1)
587 if (*first1 != *first2)
600 template <
typename TIterator1,
typename TIterator2,
typename TPredicate>
603 bool equal(TIterator1 first1, TIterator1 last1, TIterator2 first2, TPredicate predicate)
605 while (first1 != last1)
607 if (!predicate(*first1, *first2))
620 template <
typename TIterator1,
typename TIterator2>
623 bool equal(TIterator1 first1, TIterator1 last1, TIterator2 first2, TIterator2 last2)
625 while ((first1 != last1) && (first2 != last2))
627 if (*first1 != *first2)
636 return (first1 == last1) && (first2 == last2);
640 template <
typename TIterator1,
typename TIterator2,
typename TPredicate>
643 bool equal(TIterator1 first1, TIterator1 last1, TIterator2 first2, TIterator2 last2, TPredicate predicate)
645 while ((first1 != last1) && (first2 != last2))
647 if (!predicate(*first1 , *first2))
656 return (first1 == last1) && (first2 == last2);
663 template <
typename TIterator1,
typename TIterator2,
typename TCompare>
666 bool lexicographical_compare(TIterator1 first1, TIterator1 last1,
667 TIterator2 first2, TIterator2 last2,
670 while ((first1 != last1) && (first2 != last2))
672 if (compare(*first1, *first2))
677 if (compare(*first2, *first1))
686 return (first1 == last1) && (first2 != last2);
690 template <
typename TIterator1,
typename TIterator2>
693 bool lexicographical_compare(TIterator1 first1, TIterator1 last1,
694 TIterator2 first2, TIterator2 last2)
698 return etl::lexicographical_compare(first1, last1, first2, last2, compare());
704 template <
typename T,
typename TCompare>
707 const T& min(
const T& a,
const T& b, TCompare compare)
709 return (compare(a, b)) ? a : b;
712 template <
typename T>
715 const T& min(
const T& a,
const T& b)
719 return etl::min(a, b, compare());
725 template <
typename T,
typename TCompare>
728 const T& max(
const T& a,
const T& b, TCompare compare)
730 return (compare(a, b)) ? b : a;
733 template <
typename T>
736 const T& max(
const T& a,
const T& b)
740 return etl::max(a, b, compare());
746 template <
typename TIterator,
typename TUnaryOperation>
748 TUnaryOperation for_each(TIterator first, TIterator last, TUnaryOperation unary_operation)
750 while (first != last)
752 unary_operation(*first);
756 return unary_operation;
762 template <
typename TIteratorIn,
typename TIteratorOut,
typename TUnaryOperation>
764 TIteratorOut transform(TIteratorIn first1, TIteratorIn last1, TIteratorOut d_first, TUnaryOperation unary_operation)
766 while (first1 != last1)
768 *d_first = unary_operation(*first1);
777 template <
typename TIteratorIn1,
typename TIteratorIn2,
typename TIteratorOut,
typename TBinaryOperation>
779 TIteratorOut transform(TIteratorIn1 first1, TIteratorIn1 last1, TIteratorIn2 first2, TIteratorOut d_first, TBinaryOperation binary_operation)
781 while (first1 != last1)
783 *d_first = binary_operation(*first1, *first2);
796 template <
typename TIterator,
typename T>
797 ETL_CONSTEXPR14
void replace(TIterator first, TIterator last,
const T& old_value,
const T& new_value)
799 while (first != last)
801 if (*first == old_value)
813 template <
typename TIterator,
typename TPredicate,
typename T>
814 ETL_CONSTEXPR14
void replace_if(TIterator first, TIterator last, TPredicate predicate,
const T& new_value)
816 while (first != last)
818 if (predicate(*first))
830 namespace private_heap
833 template <
typename TIterator,
typename TDistance,
typename TValue,
typename TCompare>
834 void push_heap(TIterator first, TDistance value_index, TDistance top_index, TValue value, TCompare compare)
836 TDistance parent = (value_index - 1) / 2;
838 while ((value_index > top_index) && compare(first[parent], value))
840 first[value_index] = etl::move(first[parent]);
841 value_index = parent;
842 parent = (value_index - 1) / 2;
845 first[value_index] = etl::move(value);
849 template <
typename TIterator,
typename TDistance,
typename TValue,
typename TCompare>
850 void adjust_heap(TIterator first, TDistance value_index, TDistance length, TValue value, TCompare compare)
852 TDistance top_index = value_index;
853 TDistance child2nd = (2 * value_index) + 2;
855 while (child2nd < length)
857 if (compare(first[child2nd], first[child2nd - 1]))
862 first[value_index] = etl::move(first[child2nd]);
863 value_index = child2nd;
864 child2nd = 2 * (child2nd + 1);
867 if (child2nd == length)
869 first[value_index] = etl::move(first[child2nd - 1]);
870 value_index = child2nd - 1;
873 push_heap(first, value_index, top_index, etl::move(value), compare);
877 template <
typename TIterator,
typename TDistance,
typename TCompare>
878 bool is_heap(
const TIterator first,
const TDistance n, TCompare compare)
880 TDistance parent = 0;
882 for (TDistance child = 1; child < n; ++child)
884 if (compare(first[parent], first[child]))
889 if ((child & 1) == 0)
900 template <
typename TIterator,
typename TCompare>
901 void pop_heap(TIterator first, TIterator last, TCompare compare)
903 typedef typename etl::iterator_traits<TIterator>::value_type value_t;
904 typedef typename etl::iterator_traits<TIterator>::difference_type distance_t;
906 value_t value = etl::move(last[-1]);
907 last[-1] = etl::move(first[0]);
909 private_heap::adjust_heap(first, distance_t(0), distance_t(last - first - 1), etl::move(value), compare);
913 template <
typename TIterator>
914 void pop_heap(TIterator first, TIterator last)
918 etl::pop_heap(first, last, compare());
922 template <
typename TIterator,
typename TCompare>
923 void push_heap(TIterator first, TIterator last, TCompare compare)
925 typedef typename etl::iterator_traits<TIterator>::difference_type difference_t;
926 typedef typename etl::iterator_traits<TIterator>::value_type value_t;
928 private_heap::push_heap(first, difference_t(last - first - 1), difference_t(0), value_t(etl::move(*(last - 1))), compare);
932 template <
typename TIterator>
933 void push_heap(TIterator first, TIterator last)
937 etl::push_heap(first, last, compare());
941 template <
typename TIterator,
typename TCompare>
942 void make_heap(TIterator first, TIterator last, TCompare compare)
944 typedef typename etl::iterator_traits<TIterator>::difference_type difference_t;
946 if ((last - first) < 2)
951 difference_t length = last - first;
952 difference_t parent = (length - 2) / 2;
956 private_heap::adjust_heap(first, parent, length, etl::move(*(first + parent)), compare);
968 template <
typename TIterator>
969 void make_heap(TIterator first, TIterator last)
973 etl::make_heap(first, last, compare());
977 template <
typename TIterator>
979 bool is_heap(TIterator first, TIterator last)
983 return private_heap::is_heap(first, last - first, compare());
987 template <
typename TIterator,
typename TCompare>
989 bool is_heap(TIterator first, TIterator last, TCompare compare)
991 return private_heap::is_heap(first, last - first, compare);
995 template <
typename TIterator>
996 void sort_heap(TIterator first, TIterator last)
998 while (first != last)
1000 etl::pop_heap(first, last);
1006 template <
typename TIterator,
typename TCompare>
1007 void sort_heap(TIterator first, TIterator last, TCompare compare)
1009 while (first != last)
1011 etl::pop_heap(first, last, compare);
1019 template<
typename TIterator1,
typename TIterator2,
typename TCompare>
1022 TIterator1 search(TIterator1 first, TIterator1 last, TIterator2 search_first, TIterator2 search_last, TCompare compare)
1026 TIterator1 itr = first;
1027 TIterator2 search_itr = search_first;
1031 if (search_itr == search_last)
1041 if (!compare(*itr, *search_itr))
1055 template<
typename TIterator1,
typename TIterator2>
1058 TIterator1 search(TIterator1 first, TIterator1 last, TIterator2 search_first, TIterator2 search_last)
1062 return etl::search(first, last, search_first, search_last, compare());
1068 namespace private_algorithm
1071 template <
typename TIterator>
1073 TIterator rotate_general(TIterator first, TIterator middle, TIterator last)
1075 TIterator next = middle;
1077 while (first != next)
1081 swap(*first, *next);
1090 else if (first == middle)
1100 template <
typename TIterator>
1102 TIterator rotate_left_by_one(TIterator first, TIterator last)
1104 typedef typename etl::iterator_traits<TIterator>::value_type value_type;
1107 value_type temp(etl::move(*first));
1110 TIterator result = etl::move(etl::next(first), last, first);
1113 *result = etl::move(temp);
1120 template <
typename TIterator>
1122 TIterator rotate_right_by_one(TIterator first, TIterator last)
1124 typedef typename etl::iterator_traits<TIterator>::value_type value_type;
1127 TIterator previous = etl::prev(last);
1128 value_type temp(etl::move(*previous));
1131 TIterator result = etl::move_backward(first, previous, last);
1134 *first = etl::move(temp);
1142 template<
typename TIterator>
1144 TIterator rotate(TIterator first, TIterator middle, TIterator last)
1146 if (etl::next(first) == middle)
1148 return private_algorithm::rotate_left_by_one(first, last);
1151 if (etl::next(middle) == last)
1153 return private_algorithm::rotate_right_by_one(first, last);
1156 return private_algorithm::rotate_general(first, middle, last);
1163 template <
typename TIterator1,
typename TIterator2,
typename TPredicate>
1166 TIterator1 find_end(TIterator1 b, TIterator1 e,
1167 TIterator2 sb, TIterator2 se,
1168 TPredicate predicate)
1175 TIterator1 result = e;
1179 TIterator1 new_result = etl::search(b, e, sb, se, predicate);
1181 if (new_result == e)
1187 result = new_result;
1196 template <
typename TIterator1,
typename TIterator2>
1199 TIterator1 find_end(TIterator1 b, TIterator1 e,
1200 TIterator2 sb, TIterator2 se)
1204 return find_end(b, e, sb, se, predicate());
1212 template <
typename TIterator,
typename TCompare>
1219 TIterator minimum =
begin;
1240 template <
typename TIterator>
1246 typedef typename etl::iterator_traits<TIterator>::value_type value_t;
1256 template <
typename TIterator,
typename TCompare>
1263 TIterator maximum =
begin;
1284 template <
typename TIterator>
1290 typedef typename etl::iterator_traits<TIterator>::value_type value_t;
1300 template <
typename TIterator,
typename TCompare>
1307 TIterator minimum =
begin;
1308 TIterator maximum =
begin;
1326 return ETL_OR_STD::pair<TIterator, TIterator>(minimum, maximum);
1334 template <
typename TIterator>
1340 typedef typename etl::iterator_traits<TIterator>::value_type value_t;
1350 template <
typename T>
1353 ETL_OR_STD::pair<const T&, const T&>
minmax(
const T& a,
1356 return (b < a) ? ETL_OR_STD::pair<const T&, const T&>(b, a) : ETL_OR_STD::pair<const T&, const T&>(a, b);
1364 template <
typename T,
typename TCompare>
1367 ETL_OR_STD::pair<const T&, const T&>
minmax(
const T& a,
1371 return compare(b, a) ? ETL_OR_STD::pair<const T&, const T&>(b, a) : ETL_OR_STD::pair<const T&, const T&>(a, b);
1379 template <
typename TIterator>
1387 TIterator next =
begin;
1389 while (++next !=
end)
1408 template <
typename TIterator,
typename TCompare>
1417 TIterator next =
begin;
1419 while (++next !=
end)
1438 template<
typename TIterator>
1452 template<
typename TIterator,
typename TCompare>
1467 template <
typename TIterator,
typename TUnaryPredicate>
1472 TUnaryPredicate predicate)
1476 if (!predicate(*
begin))
1492 template <
typename TIterator1,
typename TIterator2>
1501 TIterator2 end2 = begin2;
1503 etl::advance(end2, etl::distance(begin1, end1));
1505 for (TIterator1 i = begin1; i != end1; ++i)
1507 if (i == etl::find(begin1, i, *i))
1509 size_t n = etl::count(begin2, end2, *i);
1511 if (n == 0 ||
size_t(etl::count(i, end1, *i)) != n)
1527 template <
typename TIterator1,
typename TIterator2,
typename TBinaryPredicate>
1533 TBinaryPredicate predicate)
1537 TIterator2 end2 = begin2;
1539 etl::advance(end2, etl::distance(begin1, end1));
1541 for (TIterator1 i = begin1; i != end1; ++i)
1543 if (i == etl::find_if(begin1, i, etl::bind1st(predicate, *i)))
1545 size_t n = etl::count(begin2, end2, *i);
1547 if (n == 0 ||
size_t(etl::count(i, end1, *i)) != n)
1563 template <
typename TIterator1,
typename TIterator2>
1573 for (TIterator1 i = begin1; i != end1; ++i)
1575 if (i == etl::find(begin1, i, *i))
1577 size_t n = etl::count(begin2, end2, *i);
1579 if (n == 0 ||
size_t(etl::count(i, end1, *i)) != n)
1595 template <
typename TIterator1,
typename TIterator2,
typename TBinaryPredicate>
1601 TBinaryPredicate predicate)
1605 for (TIterator1 i = begin1; i != end1; ++i)
1607 if (i == etl::find_if(begin1, i, etl::bind1st(predicate, *i)))
1609 size_t n = etl::count(begin2, end2, *i);
1611 if (n == 0 ||
size_t(etl::count(i, end1, *i)) != n)
1627 template <
typename TIterator,
typename TUnaryPredicate>
1632 TUnaryPredicate predicate)
1636 if (!predicate(*
begin))
1646 if (predicate(*
begin))
1662 template <
typename TIterator,
typename TUnaryPredicate>
1667 TUnaryPredicate predicate)
1671 if (!predicate(*
begin))
1688 template <
typename TSource,
typename TDestinationTrue,
typename TDestinationFalse,
typename TUnaryPredicate>
1692 TDestinationTrue destination_true,
1693 TDestinationFalse destination_false,
1694 TUnaryPredicate predicate)
1698 if (predicate(*
begin))
1700 *destination_true = *
begin;
1705 *destination_false = *
begin;
1706 ++destination_false;
1712 return ETL_OR_STD::pair<TDestinationTrue, TDestinationFalse>(destination_true, destination_false);
1720 template <
typename TIterator,
typename TOutputIterator,
typename TUnaryPredicate>
1724 TOutputIterator out,
1725 TUnaryPredicate predicate)
1729 if (predicate(*
begin))
1746 template <
typename TIterator,
typename TUnaryPredicate>
1751 TUnaryPredicate predicate)
1761 template <
typename TIterator,
typename TUnaryPredicate>
1766 TUnaryPredicate predicate)
1768 return etl::find_if(
begin,
end, predicate) !=
end;
1776 template <
typename TIterator,
typename TUnaryPredicate>
1781 TUnaryPredicate predicate)
1783 return etl::find_if(
begin,
end, predicate) ==
end;
1786#if ETL_NOT_USING_STL
1792 template <
typename TIterator,
typename TCompare>
1793 void sort(TIterator first, TIterator last, TCompare compare)
1802 template <
typename TIterator>
1803 void sort(TIterator first, TIterator last)
1814 template <
typename TIterator,
typename TCompare>
1815 void stable_sort(TIterator first, TIterator last, TCompare compare)
1825 template <
typename TIterator>
1836 template <
typename TIterator,
typename TCompare>
1846 template <
typename TIterator>
1847 void sort(TIterator first, TIterator last)
1858 template <
typename TIterator,
typename TCompare>
1869 template <
typename TIterator>
1880 template <
typename TIterator,
typename T>
1884 while (first != last)
1886 sum = etl::move(sum) + *first;
1897 template <
typename TIterator,
typename T,
typename TBinaryOperation>
1899 T
accumulate(TIterator first, TIterator last, T sum, TBinaryOperation operation)
1901 while (first != last)
1903 sum = operation(etl::move(sum), *first);
1914 template<
typename T,
typename TCompare>
1916 const T&
clamp(
const T& value,
const T& low,
const T& high, TCompare
compare)
1918 return compare(value, low) ? low :
compare(high, value) ? high : value;
1921 template <
typename T>
1923 const T&
clamp(
const T& value,
const T& low,
const T& high )
1932 template <
typename TIterator,
typename T>
1934 TIterator
remove(TIterator first, TIterator last,
const T& value)
1936 first = etl::find(first, last, value);
1940 TIterator itr = first;
1944 if (!(*itr == value))
1946 *first = etl::move(*itr);
1961 template <
typename TIterator,
typename TUnaryPredicate>
1963 TIterator
remove_if(TIterator first, TIterator last, TUnaryPredicate predicate)
1965 first = etl::find_if(first, last, predicate);
1969 TIterator itr = first;
1973 if (!predicate(*itr))
1975 *first = etl::move(*itr);
2003 template <
typename TInputIterator,
2004 typename TOutputIterator>
2009 TInputIterator i_end,
2010 TOutputIterator o_begin,
2011 TOutputIterator o_end)
2013 size_t s_size = etl::distance(i_begin, i_end);
2014 size_t d_size = etl::distance(o_begin, o_end);
2015 size_t size = (s_size < d_size) ? s_size : d_size;
2017 return etl::copy(i_begin, i_begin + size, o_begin);
2031 template <
typename TInputIterator,
2032 typename TOutputIterator>
2037 TInputIterator i_end,
2038 TOutputIterator o_begin,
2039 TOutputIterator o_end)
2041 while ((i_begin != i_end) && (o_begin != o_end))
2043 *o_begin = *i_begin;
2056 template <
typename TInputIterator,
2058 typename TOutputIterator>
2062 TOutputIterator o_begin,
2063 TOutputIterator o_end)
2065 while ((n-- > 0) && (o_begin != o_end))
2067 *o_begin = *i_begin;
2080 template <
typename TInputIterator,
2082 typename TOutputIterator,
2087 TOutputIterator o_begin,
2090 while ((n1-- > 0) && (n2-- > 0))
2092 *o_begin = *i_begin;
2106 template <
typename TInputIterator,
2107 typename TOutputIterator,
2108 typename TUnaryPredicate>
2111 TInputIterator i_end,
2112 TOutputIterator o_begin,
2113 TOutputIterator o_end,
2114 TUnaryPredicate predicate)
2116 while ((i_begin != i_end) && (o_begin != o_end))
2118 if (predicate(*i_begin))
2120 *o_begin = *i_begin;
2135 template <
typename TInputIterator,
2137 typename TOutputIterator,
2138 typename TUnaryPredicate>
2142 TOutputIterator o_begin,
2143 TUnaryPredicate predicate)
2147 if (predicate(*i_begin))
2149 *o_begin = *i_begin;
2171 template <
typename TInputIterator,
typename TOutputIterator>
2175 move_s(TInputIterator i_begin,
2176 TInputIterator i_end,
2177 TOutputIterator o_begin,
2178 TOutputIterator o_end)
2180 size_t s_size = etl::distance(i_begin, i_end);
2181 size_t d_size = etl::distance(o_begin, o_end);
2182 size_t size = (s_size < d_size) ? s_size : d_size;
2184 return etl::move(i_begin, i_begin + size, o_begin);
2198 template <
typename TInputIterator,
typename TOutputIterator>
2202 move_s(TInputIterator i_begin,
2203 TInputIterator i_end,
2204 TOutputIterator o_begin,
2205 TOutputIterator o_end)
2207 while ((i_begin != i_end) && (o_begin != o_end))
2209 *o_begin = etl::move(*i_begin);
2229 template <
typename TInputIterator,
typename TOutputIterator>
2230 TOutputIterator
move_s(TInputIterator i_begin,
2231 TInputIterator i_end,
2232 TOutputIterator o_begin,
2233 TOutputIterator o_end)
2236 return etl::copy_s(i_begin, i_end, o_begin, o_end);
2245 template <
typename TIterator,
typename TValue>
2250 const TValue& value)
2252 TIterator it = etl::lower_bound(
begin,
end, value);
2254 if ((it ==
end) || (*it != value))
2267 template <
typename TIterator,
2269 typename TBinaryPredicate,
2270 typename TBinaryEquality>
2275 const TValue& value,
2276 TBinaryPredicate predicate,
2277 TBinaryEquality equality)
2279 TIterator it = etl::lower_bound(
begin,
end, value, predicate);
2281 if ((it ==
end) || !equality(*it, value))
2293 template <
typename TIterator,
2294 typename TUnaryFunction,
2295 typename TUnaryPredicate>
2298 const TIterator
end,
2300 TUnaryPredicate predicate)
2304 if (predicate(*
begin))
2319 template <
typename TIterator,
2321 typename TUnaryFunction>
2340 template <
typename TIterator,
2342 typename TUnaryFunction,
2343 typename TUnaryPredicate>
2348 TUnaryPredicate predicate)
2352 if (predicate(*
begin))
2369 template <
typename TInputIterator,
typename TOutputIterator,
typename TUnaryFunction>
2372 TInputIterator i_end,
2373 TOutputIterator o_begin,
2374 TOutputIterator o_end,
2377 while ((i_begin != i_end) && (o_begin != o_end))
2393 template <
typename TInputIterator,
2395 typename TOutputIterator,
2396 typename TUnaryFunction>
2400 TOutputIterator o_begin,
2403 TInputIterator i_end(i_begin);
2404 etl::advance(i_end, n);
2406 etl::transform(i_begin, i_end, o_begin,
function);
2415 template <
typename TInputIterator1,
2416 typename TInputIterator2,
2418 typename TOutputIterator,
2419 typename TBinaryFunction>
2422 TInputIterator2 i_begin2,
2424 TOutputIterator o_begin,
2427 TInputIterator1 i_end1(i_begin1);
2428 etl::advance(i_end1, n);
2430 etl::transform(i_begin1, i_end1, i_begin2, o_begin,
function);
2437 template <
typename TInputIterator,
2438 typename TOutputIterator,
2439 typename TUnaryFunction,
2440 typename TUnaryPredicate>
2443 const TInputIterator i_end,
2444 TOutputIterator o_begin,
2446 TUnaryPredicate predicate)
2448 while (i_begin != i_end)
2450 if (predicate(*i_begin))
2466 template <
typename TInputIterator1,
2467 typename TInputIterator2,
2468 typename TOutputIterator,
2469 typename TBinaryFunction,
2470 typename TBinaryPredicate>
2473 const TInputIterator1 i_end1,
2474 TInputIterator2 i_begin2,
2475 TOutputIterator o_begin,
2477 TBinaryPredicate predicate)
2479 while (i_begin1 != i_end1)
2481 if (predicate(*i_begin1, *i_begin2))
2483 *o_begin =
function(*i_begin1, *i_begin2);
2498 template <
typename TInputIterator,
2500 typename TOutputIterator,
2501 typename TUnaryFunction,
2502 typename TUnaryPredicate>
2506 TOutputIterator o_begin,
2508 TUnaryPredicate predicate)
2512 if (predicate(*i_begin))
2528 template <
typename TInputIterator1,
2529 typename TInputIterator2,
2531 typename TOutputIterator,
2532 typename TBinaryFunction,
2533 typename TBinaryPredicate>
2536 TInputIterator2 i_begin2,
2538 TOutputIterator o_begin,
2540 TBinaryPredicate predicate)
2544 if (predicate(*i_begin1, *i_begin2))
2546 *o_begin++ =
function(*i_begin1, *i_begin2);
2561 template <
typename TSource,
typename TDestinationTrue,
typename TDestinationFalse,
2562 typename TUnaryFunctionTrue,
typename TUnaryFunctionFalse,
2563 typename TUnaryPredicate>
2567 TDestinationTrue destination_true,
2568 TDestinationFalse destination_false,
2569 TUnaryFunctionTrue function_true,
2570 TUnaryFunctionFalse function_false,
2571 TUnaryPredicate predicate)
2575 if (predicate(*
begin))
2577 *destination_true = function_true(*
begin);
2582 *destination_false = function_false(*
begin);
2583 ++destination_false;
2589 return ETL_OR_STD::pair<TDestinationTrue, TDestinationFalse>(destination_true, destination_false);
2597 template <
typename TSource1,
2599 typename TDestinationTrue,
2600 typename TDestinationFalse,
2601 typename TBinaryFunctionTrue,
2602 typename TBinaryFunctionFalse,
2603 typename TBinaryPredicate>
2608 TDestinationTrue destination_true,
2609 TDestinationFalse destination_false,
2610 TBinaryFunctionTrue function_true,
2611 TBinaryFunctionFalse function_false,
2612 TBinaryPredicate predicate)
2614 while (begin1 != end1)
2616 if (predicate(*begin1, *begin2))
2618 *destination_true = function_true(*begin1, *begin2);
2623 *destination_false = function_false(*begin1, *begin2);
2624 ++destination_false;
2631 return ETL_OR_STD::pair<TDestinationTrue, TDestinationFalse>(destination_true, destination_false);
2639 template <
typename TIterator,
typename TCompare>
2640#if ETL_USING_STD_NAMESPACE
2652 typedef typename etl::iterator_traits<TIterator>::difference_type difference_t;
2654 difference_t n = etl::distance(first, last);
2656 for (difference_t i = n / 2; i > 0; i /= 2)
2658 for (difference_t j = i; j < n; ++j)
2660 for (difference_t k = j - i; k >= 0; k -= i)
2662 TIterator itr1 = first;
2663 TIterator itr2 = first;
2665 etl::advance(itr1, k);
2666 etl::advance(itr2, k + i);
2670 etl::iter_swap(itr1, itr2);
2681 template <
typename TIterator>
2682#if ETL_USING_STD_NAMESPACE
2697 template <
typename TIterator,
typename TCompare>
2701 for (TIterator itr = first; itr != last; ++itr)
2703 etl::rotate(etl::upper_bound(first, itr, *itr,
compare), itr, etl::next(itr));
2711 template <
typename TIterator>
2719 namespace private_algorithm
2721 template <
typename TIterator>
2724 get_before_last(TIterator first_, TIterator last_)
2726 TIterator last = first_;
2727 TIterator lastplus1 = first_;
2730 while (lastplus1 != last_)
2739 template <
typename TIterator>
2742 get_before_last(TIterator , TIterator last_)
2744 TIterator last = last_;
2750 template <
typename TIterator>
2753 get_before_last(TIterator , TIterator last_)
2764 template <
typename TIterator,
typename TCompare>
2769 const TIterator ilast = private_algorithm::get_before_last(first, last);
2770 const TIterator jlast = last;
2772 for (TIterator i = first; i != ilast; ++i)
2779 for (; j != jlast; ++j)
2796 template <
typename TIterator>
2808 template <
typename TIterator,
typename TCompare>
2812 if (!etl::is_heap(first, last,
compare))
2814 etl::make_heap(first, last,
compare);
2817 etl::sort_heap(first, last,
compare);
2824 template <
typename TIterator>
2828 if (!etl::is_heap(first, last))
2830 etl::make_heap(first, last);
2833 etl::sort_heap(first, last);
2840 template <
typename T>
2842 constexpr const T& multimax(
const T& a,
const T& b)
2844 return a < b ? b : a;
2847 template <
typename T,
typename... Tx>
2849 constexpr const T& multimax(
const T& t,
const Tx&... tx)
2851 return multimax(t, multimax(tx...));
2860 template <
typename TCompare,
typename T>
2862 constexpr const T& multimax_compare(TCompare compare,
const T& a,
const T& b)
2864 return compare(a, b) ? b : a;
2867 template <
typename TCompare,
typename T,
typename... Tx>
2869 constexpr const T& multimax_compare(TCompare compare,
const T& t,
const Tx&... tx)
2871 return multimax_compare(compare, t, multimax_compare(compare, tx...));
2879 template <
typename T>
2881 constexpr const T& multimin(
const T& a,
const T& b)
2883 return a < b ? a : b;
2886 template <
typename T,
typename... Tx>
2888 constexpr const T& multimin(
const T& t,
const Tx&... tx)
2890 return multimin(t, multimin(tx...));
2899 template <
typename TCompare,
typename T>
2901 constexpr const T& multimin_compare(TCompare compare,
const T& a,
const T& b)
2903 return compare(a, b) ? a : b;
2906 template <
typename TCompare,
typename T,
typename... Tx>
2908 constexpr const T& multimin_compare(TCompare compare,
const T& t,
const Tx&... tx)
2910 return multimin_compare(compare, t, multimin_compare(compare, tx...));
2918 template <
typename TIterator>
2920 constexpr const TIterator& multimax_iter(
const TIterator& a,
const TIterator& b)
2922 return *a < *b ? b : a;
2925 template <
typename TIterator,
typename... TIteratorx>
2927 constexpr const TIterator& multimax_iter(
const TIterator& t,
const TIteratorx&... tx)
2929 return multimax_iter(t, multimax_iter(tx...));
2938 template <
typename TCompare,
typename TIterator>
2940 constexpr const TIterator& multimax_iter_compare(TCompare compare,
const TIterator& a,
const TIterator& b)
2942 return compare(*a, *b) ? b : a;
2945 template <
typename TCompare,
typename TIterator,
typename... TIteratorx>
2947 constexpr const TIterator& multimax_iter_compare(TCompare compare,
const TIterator& t,
const TIteratorx&... tx)
2949 return multimax_iter_compare(compare, t, multimax_iter_compare(compare, tx...));
2957 template <
typename TIterator>
2959 constexpr const TIterator& multimin_iter(
const TIterator& a,
const TIterator& b)
2961 return *a < *b ? a : b;
2964 template <
typename TIterator,
typename... Tx>
2966 constexpr const TIterator& multimin_iter(
const TIterator& t,
const Tx&... tx)
2968 return multimin_iter(t, multimin_iter(tx...));
2977 template <
typename TCompare,
typename TIterator>
2979 constexpr const TIterator& multimin_iter_compare(TCompare compare,
const TIterator& a,
const TIterator& b)
2981 return compare(*a, *b) ? a : b;
2984 template <
typename TCompare,
typename TIterator,
typename... Tx>
2986 constexpr const TIterator& multimin_iter_compare(TCompare compare,
const TIterator& t,
const Tx&... tx)
2988 return multimin_iter_compare(compare, t, multimin_iter_compare(compare, tx...));
ETL_CONSTEXPR20 void shell_sort(TIterator first, TIterator last)
Definition: algorithm.h:2687
ETL_CONSTEXPR14 TOutputIterator copy_if(TIterator begin, TIterator end, TOutputIterator out, TUnaryPredicate predicate)
Definition: algorithm.h:1722
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:2565
ETL_NODISCARD ETL_CONSTEXPR14 bool any_of(TIterator begin, TIterator end, TUnaryPredicate predicate)
Definition: algorithm.h:1764
ETL_NODISCARD ETL_CONSTEXPR14 TIterator min_element(TIterator begin, TIterator end, TCompare compare)
Definition: algorithm.h:1215
ETL_CONSTEXPR14 TOutputIterator transform_n_if(TInputIterator i_begin, TSize n, TOutputIterator o_begin, TUnaryFunction function, TUnaryPredicate predicate)
Definition: algorithm.h:2504
ETL_CONSTEXPR14 T accumulate(TIterator first, TIterator last, T sum)
Definition: algorithm.h:1882
ETL_NODISCARD ETL_CONSTEXPR14 bool all_of(TIterator begin, TIterator end, TUnaryPredicate predicate)
Definition: algorithm.h:1749
ETL_NODISCARD ETL_CONSTEXPR14 ETL_OR_STD::pair< TIterator, TIterator > minmax_element(TIterator begin, TIterator end, TCompare compare)
Definition: algorithm.h:1303
void sort(TIterator first, TIterator last)
Definition: algorithm.h:1847
ETL_CONSTEXPR14 TOutputIterator transform_if(TInputIterator i_begin, const TInputIterator i_end, TOutputIterator o_begin, TUnaryFunction function, TUnaryPredicate predicate)
Definition: algorithm.h:2442
ETL_CONSTEXPR14 TUnaryFunction for_each_if(TIterator begin, const TIterator end, TUnaryFunction function, TUnaryPredicate predicate)
Definition: algorithm.h:2297
ETL_NODISCARD ETL_CONSTEXPR14 TIterator find_if_not(TIterator begin, TIterator end, TUnaryPredicate predicate)
Definition: algorithm.h:1470
ETL_NODISCARD ETL_CONSTEXPR14 bool is_sorted(TIterator begin, TIterator end)
Definition: algorithm.h:1441
ETL_CONSTEXPR14 TOutputIterator transform_s(TInputIterator i_begin, TInputIterator i_end, TOutputIterator o_begin, TOutputIterator o_end, TUnaryFunction function)
Definition: algorithm.h:2371
ETL_CONSTEXPR14 TIterator remove(TIterator first, TIterator last, const T &value)
Definition: algorithm.h:1934
ETL_CONSTEXPR14 void transform_n(TInputIterator i_begin, TSize n, TOutputIterator o_begin, TUnaryFunction function)
Definition: algorithm.h:2398
ETL_CONSTEXPR14 TOutputIterator copy_n_if(TInputIterator i_begin, TSize n, TOutputIterator o_begin, TUnaryPredicate predicate)
Definition: algorithm.h:2140
ETL_NODISCARD ETL_CONSTEXPR14 TIterator is_sorted_until(TIterator begin, TIterator end)
Definition: algorithm.h:1382
ETL_CONSTEXPR14 void insertion_sort(TIterator first, TIterator last)
Definition: algorithm.h:2713
void sort(TIterator first, TIterator last, TCompare compare)
Definition: algorithm.h:1837
ETL_NODISCARD ETL_CONSTEXPR14 ETL_OR_STD::pair< const T &, const T & > minmax(const T &a, const T &b)
Definition: algorithm.h:1353
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:2008
ETL_CONSTEXPR const T & clamp(const T &value, const T &low, const T &high, TCompare compare)
Definition: algorithm.h:1916
ETL_CONSTEXPR14 TIterator remove_if(TIterator first, TIterator last, TUnaryPredicate predicate)
Definition: algorithm.h:1963
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:1690
ETL_CONSTEXPR14 TIterator for_each_n(TIterator begin, TSize n, TUnaryFunction function)
Definition: algorithm.h:2323
ETL_NODISCARD ETL_CONSTEXPR14 TIterator binary_find(TIterator begin, TIterator end, const TValue &value)
Definition: algorithm.h:2248
ETL_CONSTEXPR14 void heap_sort(TIterator first, TIterator last, TCompare compare)
Definition: algorithm.h:2810
ETL_NODISCARD ETL_CONSTEXPR14 bool none_of(TIterator begin, TIterator end, TUnaryPredicate predicate)
Definition: algorithm.h:1779
ETL_CONSTEXPR20 void selection_sort(TIterator first, TIterator last, TCompare compare)
Definition: algorithm.h:2766
ETL_CONSTEXPR14 TOutputIterator copy_n_s(TInputIterator i_begin, TSize n, TOutputIterator o_begin, TOutputIterator o_end)
Definition: algorithm.h:2060
TOutputIterator move_s(TInputIterator i_begin, TInputIterator i_end, TOutputIterator o_begin, TOutputIterator o_end)
Definition: algorithm.h:2230
ETL_CONSTEXPR14 TOutputIterator copy_if_s(TInputIterator i_begin, TInputIterator i_end, TOutputIterator o_begin, TOutputIterator o_end, TUnaryPredicate predicate)
Definition: algorithm.h:2110
ETL_CONSTEXPR14 TIterator for_each_n_if(TIterator begin, TSize n, TUnaryFunction function, TUnaryPredicate predicate)
Definition: algorithm.h:2345
void stable_sort(TIterator first, TIterator last, TCompare compare)
Definition: algorithm.h:1859
ETL_NODISCARD ETL_CONSTEXPR14 bool is_partitioned(TIterator begin, TIterator end, TUnaryPredicate predicate)
Definition: algorithm.h:1630
ETL_NODISCARD ETL_CONSTEXPR14 TIterator max_element(TIterator begin, TIterator end, TCompare compare)
Definition: algorithm.h:1259
ETL_NODISCARD ETL_CONSTEXPR14 TIterator partition_point(TIterator begin, TIterator end, TUnaryPredicate predicate)
Definition: algorithm.h:1665
ETL_NODISCARD ETL_CONSTEXPR14 bool is_permutation(TIterator1 begin1, TIterator1 end1, TIterator2 begin2)
Definition: algorithm.h:1495
void stable_sort(TIterator first, TIterator last)
Definition: algorithm.h:1870
Definition: function.h:94
enable_if
Definition: type_traits_generator.h:1191
bitset_ext
Definition: absolute.h:38
pair< T1, T2 > make_pair(T1 a, T2 b)
A convenience wrapper for creating a pair from two objects.
Definition: utility.h:322
void swap(etl::array< T, SIZE > &lhs, etl::array< T, SIZE > &rhs)
Template deduction guides.
Definition: array.h:621
ETL_CONSTEXPR TContainer::iterator begin(TContainer &container)
Definition: iterator.h:931
ETL_CONSTEXPR TContainer::iterator end(TContainer &container)
Definition: iterator.h:961
Definition: functional.h:238
Definition: iterator.h:842
Definition: functional.h:134