Embedded Template Library 1.0
Loading...
Searching...
No Matches
algorithm.h
Go to the documentation of this file.
1
2
3/******************************************************************************
4The MIT License(MIT)
5
6Embedded Template Library.
7https://github.com/ETLCPP/etl
8https://www.etlcpp.com
9
10Documentation: https://www.etlcpp.com/algorithm.html
11
12Copyright(c) 2014 John Wellbelove
13
14Permission is hereby granted, free of charge, to any person obtaining a copy
15of this software and associated documentation files(the "Software"), to deal
16in the Software without restriction, including without limitation the rights
17to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
18copies of the Software, and to permit persons to whom the Software is
19furnished to do so, subject to the following conditions :
20
21The above copyright notice and this permission notice shall be included in all
22copies or substantial portions of the Software.
23
24THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
25IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
26FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
27AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
28LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
29OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
30SOFTWARE.
31******************************************************************************/
32
33#ifndef ETL_ALGORITHM_INCLUDED
34#define ETL_ALGORITHM_INCLUDED
35
40
41#include "platform.h"
42#include "type_traits.h"
43#include "iterator.h"
44#include "functional.h"
45#include "utility.h"
46#include "gcd.h"
47
48#include <stdint.h>
49#include <string.h>
50
51#include "private/minmax_push.h"
52
53#if ETL_USING_STL
54 #include <algorithm>
55 #include <utility>
56 #include <iterator>
57 #include <functional>
58 #include <numeric>
59#endif
60
61namespace etl
62{
63 // Declare prototypes of the ETL's sort functions
64 template <typename TIterator>
65#if ETL_USING_STD_NAMESPACE
66 ETL_CONSTEXPR20
67#else
68 ETL_CONSTEXPR14
69#endif
70 void shell_sort(TIterator first, TIterator last);
71
72 template <typename TIterator, typename TCompare>
73#if ETL_USING_STD_NAMESPACE
74 ETL_CONSTEXPR20
75#else
76 ETL_CONSTEXPR14
77#endif
78 void shell_sort(TIterator first, TIterator last, TCompare compare);
79
80 template <typename TIterator>
81 ETL_CONSTEXPR14 void insertion_sort(TIterator first, TIterator last);
82
83 template <typename TIterator, typename TCompare>
84 ETL_CONSTEXPR14 void insertion_sort(TIterator first, TIterator last, TCompare compare);
85}
86
87//*****************************************************************************
88// Algorithms defined by the ETL
89//*****************************************************************************
90namespace etl
91{
92 namespace private_algorithm
93 {
94 template <bool use_swap>
95 struct swap_impl;
96
97 // Generic swap
98 template <>
99 struct swap_impl<false>
100 {
101 template <typename TIterator1, typename TIterator2>
102 static void do_swap(TIterator1 a, TIterator2 b)
103 {
104 typename etl::iterator_traits<TIterator1>::value_type tmp = *a;
105 *a = *b;
106 *b = tmp;
107 }
108 };
109
110 // Specialised swap
111 template <>
112 struct swap_impl<true>
113 {
114 template <typename TIterator1, typename TIterator2>
115 static void do_swap(TIterator1 a, TIterator2 b)
116 {
117 using ETL_OR_STD::swap; // Allow ADL
118 swap(*a, *b);
119 }
120 };
121 }
122
123 //***************************************************************************
124 // iter_swap
125 //***************************************************************************
126 template <typename TIterator1, typename TIterator2>
127#if ETL_USING_STD_NAMESPACE
128 ETL_CONSTEXPR20
129#else
130 ETL_CONSTEXPR14
131#endif
132 void iter_swap(TIterator1 a, TIterator2 b)
133 {
134 typedef etl::iterator_traits<TIterator1> traits1;
135 typedef etl::iterator_traits<TIterator2> traits2;
136
137 typedef typename traits1::value_type v1;
138 typedef typename traits2::value_type v2;
139
140 typedef typename traits1::reference r1;
141 typedef typename traits2::reference r2;
142
143 const bool use_swap = etl::is_same<v1, v2>::value &&
146
148 }
149
150 //***************************************************************************
151 // swap_ranges
152 //***************************************************************************
153 template <typename TIterator1, typename TIterator2>
154#if ETL_USING_STD_NAMESPACE
155 ETL_CONSTEXPR20
156#else
157 ETL_CONSTEXPR14
158#endif
159 TIterator2 swap_ranges(TIterator1 first1,
160 TIterator1 last1,
161 TIterator2 first2)
162 {
163 while (first1 != last1)
164 {
165 iter_swap(first1, first2);
166 ++first1;
167 ++first2;
168 }
169
170 return first2;
171 }
172
173 //***************************************************************************
174 // generate
175 template <typename TIterator, typename TFunction>
176 ETL_CONSTEXPR14
177 void generate(TIterator db, TIterator de, TFunction funct)
178 {
179 while (db != de)
180 {
181 *db++ = funct();
182 }
183 }
184
185 //***************************************************************************
186 // copy
187#if ETL_USING_STL && ETL_USING_CPP20
188 // Use the STL constexpr implementation.
189 template <typename TIterator1, typename TIterator2>
190 constexpr TIterator2 copy(TIterator1 sb, TIterator1 se, TIterator2 db)
191 {
192 return std::copy(sb, se, db);
193 }
194#else
195 // Non-pointer or not trivially copyable or not using builtin memcpy.
196 template <typename TIterator1, typename TIterator2>
197 ETL_CONSTEXPR14 TIterator2 copy(TIterator1 sb, TIterator1 se, TIterator2 db)
198 {
199 while (sb != se)
200 {
201 *db = *sb;
202 ++db;
203 ++sb;
204 }
205
206 return db;
207 }
208#endif
209
210 //***************************************************************************
211 // reverse_copy
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)
215 {
216 return std::reverse_copy(sb, se, db);
217 }
218#else
219 template <typename TIterator1, typename TIterator2>
220 ETL_CONSTEXPR14
221 TIterator2 reverse_copy(TIterator1 sb, TIterator1 se, TIterator2 db)
222 {
223 while (sb != se)
224 {
225 *db = *--se;
226 ++db;
227 }
228
229 return db;
230 }
231#endif
232
233 //***************************************************************************
234 // copy_n
235#if ETL_USING_STL && ETL_USING_CPP20
236 // Use the STL implementation
237 template <typename TIterator1, typename TSize, typename TIterator2>
238 constexpr TIterator2 copy_n(TIterator1 sb, TSize count, TIterator2 db)
239 {
240 return std::copy_n(sb, count, db);
241 }
242#else
243 // Non-pointer or not trivially copyable or not using builtin memcpy.
244 template <typename TIterator1, typename TSize, typename TIterator2>
245 ETL_CONSTEXPR14 TIterator2 copy_n(TIterator1 sb, TSize count, TIterator2 db)
246 {
247 while (count != 0)
248 {
249 *db = *sb;
250 ++db;
251 ++sb;
252 --count;
253 }
254
255 return db;
256 }
257#endif
258
259 //***************************************************************************
260 // copy_backward
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)
264 {
265 return std::copy_backward(sb, se, de);
266 }
267#else
268 template <typename TIterator1, typename TIterator2>
269 ETL_CONSTEXPR14 TIterator2 copy_backward(TIterator1 sb, TIterator1 se, TIterator2 de)
270 {
271 while (se != sb)
272 {
273 *(--de) = *(--se);
274 }
275
276 return de;
277 }
278#endif
279
280 //***************************************************************************
281 // move
282#if ETL_USING_STL && ETL_USING_CPP20
283 template <typename TIterator1, typename TIterator2>
284 constexpr TIterator2 move(TIterator1 sb, TIterator1 se, TIterator2 db)
285 {
286 return std::move(sb, se, db);
287 }
288#elif ETL_USING_CPP11
289 // For C++11
290 template <typename TIterator1, typename TIterator2>
291 ETL_CONSTEXPR14 TIterator2 move(TIterator1 sb, TIterator1 se, TIterator2 db)
292 {
293 while (sb != se)
294 {
295 *db = etl::move(*sb);
296 ++db;
297 ++sb;
298 }
299
300 return db;
301 }
302#else
303 // For C++03
304 template <typename TIterator1, typename TIterator2>
305 ETL_CONSTEXPR14 TIterator2 move(TIterator1 sb, TIterator1 se, TIterator2 db)
306 {
307 return copy(sb, se, db);
308 }
309#endif
310
311 //***************************************************************************
312 // move_backward
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)
316 {
317 return std::move_backward(sb, se, de);
318 }
319#elif ETL_USING_CPP11
320 // For C++11
321 template <typename TIterator1, typename TIterator2>
322 ETL_CONSTEXPR14 TIterator2 move_backward(TIterator1 sb, TIterator1 se, TIterator2 de)
323 {
324 while (sb != se)
325 {
326 *(--de) = etl::move(*(--se));
327 }
328
329 return de;
330 }
331#else
332 // For C++03
333 template <typename TIterator1, typename TIterator2>
334 ETL_CONSTEXPR14 TIterator2 move_backward(TIterator1 sb, TIterator1 se, TIterator2 de)
335 {
336 return etl::copy_backward(sb, se, de);
337 }
338#endif
339
340 //***************************************************************************
341 // reverse
342 //***************************************************************************
343 // Pointers
344 template <typename TIterator>
345 ETL_CONSTEXPR14
347 reverse(TIterator b, TIterator e)
348 {
349 if (b != e)
350 {
351 while (b < --e)
352 {
353 etl::iter_swap(b, e);
354 ++b;
355 }
356 }
357 }
358
359 // Non-pointers
360 template <typename TIterator>
361 ETL_CONSTEXPR14
363 reverse(TIterator b, TIterator e)
364 {
365 while ((b != e) && (b != --e))
366 {
367 etl::iter_swap(b++, e);
368 }
369 }
370
371 //***************************************************************************
372 // lower_bound
373 //***************************************************************************
374 template<typename TIterator, typename TValue, typename TCompare>
375 ETL_NODISCARD
376 ETL_CONSTEXPR14
377 TIterator lower_bound(TIterator first, TIterator last, const TValue& value, TCompare compare)
378 {
379 typedef typename etl::iterator_traits<TIterator>::difference_type difference_t;
380
381 difference_t count = etl::distance(first, last);
382
383 while (count > 0)
384 {
385 TIterator itr = first;
386 difference_t step = count / 2;
387
388 etl::advance(itr, step);
389
390 if (compare(*itr, value))
391 {
392 first = ++itr;
393 count -= step + 1;
394 }
395 else
396 {
397 count = step;
398 }
399 }
400
401 return first;
402 }
403
404 template<typename TIterator, typename TValue>
405 ETL_NODISCARD
406 ETL_CONSTEXPR14
407 TIterator lower_bound(TIterator first, TIterator last, const TValue& value)
408 {
410
411 return etl::lower_bound(first, last, value, compare());
412 }
413
414 //***************************************************************************
415 // upper_bound
416 //***************************************************************************
417 template<typename TIterator, typename TValue, typename TCompare>
418 ETL_NODISCARD
419 ETL_CONSTEXPR14
420 TIterator upper_bound(TIterator first, TIterator last, const TValue& value, TCompare compare)
421 {
422 typedef typename etl::iterator_traits<TIterator>::difference_type difference_t;
423
424 difference_t count = etl::distance(first, last);
425
426 while (count > 0)
427 {
428 TIterator itr = first;
429 difference_t step = count / 2;
430
431 etl::advance(itr, step);
432
433 if (!compare(value, *itr))
434 {
435 first = ++itr;
436 count -= step + 1;
437 }
438 else
439 {
440 count = step;
441 }
442 }
443
444 return first;
445 }
446
447 template<typename TIterator, typename TValue>
448 ETL_NODISCARD
449 ETL_CONSTEXPR14
450 TIterator upper_bound(TIterator first, TIterator last, const TValue& value)
451 {
453
454 return etl::upper_bound(first, last, value, compare());
455 }
456
457 //***************************************************************************
458 // equal_range
459 //***************************************************************************
460 template<typename TIterator, typename TValue, typename TCompare>
461 ETL_NODISCARD
462 ETL_CONSTEXPR14
463 ETL_OR_STD::pair<TIterator, TIterator> equal_range(TIterator first, TIterator last, const TValue& value, TCompare compare)
464 {
465 return ETL_OR_STD::make_pair(etl::lower_bound(first, last, value, compare),
466 etl::upper_bound(first, last, value, compare));
467 }
468
469 template<typename TIterator, typename TValue>
470 ETL_NODISCARD
471 ETL_OR_STD::pair<TIterator, TIterator> equal_range(TIterator first, TIterator last, const TValue& value)
472 {
474
475 return ETL_OR_STD::make_pair(etl::lower_bound(first, last, value, compare()),
476 etl::upper_bound(first, last, value, compare()));
477 }
478
479 //***************************************************************************
480 // binary_search
481 //***************************************************************************
482 template <typename TIterator, typename T, typename Compare>
483 ETL_NODISCARD
484 bool binary_search(TIterator first, TIterator last, const T& value, Compare compare)
485 {
486 first = etl::lower_bound(first, last, value, compare);
487
488 return (!(first == last) && !(compare(value, *first)));
489 }
490
491 template <typename TIterator, typename T>
492 ETL_NODISCARD
493 bool binary_search(TIterator first, TIterator last, const T& value)
494 {
496
497 return binary_search(first, last, value, compare());
498 }
499
500 //***************************************************************************
501 // find_if
502 //***************************************************************************
503 template <typename TIterator, typename TUnaryPredicate>
504 ETL_NODISCARD
505 ETL_CONSTEXPR14
506 TIterator find_if(TIterator first, TIterator last, TUnaryPredicate predicate)
507 {
508 while (first != last)
509 {
510 if (predicate(*first))
511 {
512 return first;
513 }
514
515 ++first;
516 }
517
518 return last;
519 }
520
521 //***************************************************************************
522 // find
523 //***************************************************************************
524 template <typename TIterator, typename T>
525 ETL_NODISCARD
526 ETL_CONSTEXPR14
527 TIterator find(TIterator first, TIterator last, const T& value)
528 {
529 while (first != last)
530 {
531 if (*first == value)
532 {
533 return first;
534 }
535
536 ++first;
537 }
538
539 return last;
540 }
541
542 //***************************************************************************
543 // fill
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)
547 {
548 std::fill(first, last, value);
549 }
550#else
551 template<typename TIterator, typename TValue>
552 ETL_CONSTEXPR14 void fill(TIterator first, TIterator last, const TValue& value)
553 {
554 while (first != last)
555 {
556 *first = value;
557 ++first;
558 }
559 }
560#endif
561
562 //***************************************************************************
563 // fill_n
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)
567 {
568 return std::fill_n(first, count, value);
569 }
570#else
571 template<typename TIterator, typename TSize, typename TValue>
572 ETL_CONSTEXPR14 TIterator fill_n(TIterator first, TSize count, const TValue& value)
573 {
574 while (count != 0)
575 {
576 *first++ = value;
577 --count;
578 }
579
580 return first;
581 }
582#endif
583
584 //***************************************************************************
585 // count
586 //***************************************************************************
587 template <typename TIterator, typename T>
588 ETL_NODISCARD
589 ETL_CONSTEXPR14
590 typename etl::iterator_traits<TIterator>::difference_type count(TIterator first, TIterator last, const T& value)
591 {
592 typename iterator_traits<TIterator>::difference_type n = 0;
593
594 while (first != last)
595 {
596 if (*first == value)
597 {
598 ++n;
599 }
600
601 ++first;
602 }
603
604 return n;
605 }
606
607 //***************************************************************************
608 // count_if
609 //***************************************************************************
610 template <typename TIterator, typename TUnaryPredicate>
611 ETL_NODISCARD
612 ETL_CONSTEXPR14
613 typename etl::iterator_traits<TIterator>::difference_type
614 count_if(TIterator first, TIterator last, TUnaryPredicate predicate)
615 {
616 typename iterator_traits<TIterator>::difference_type n = 0;
617
618 while (first != last)
619 {
620 if (predicate(*first))
621 {
622 ++n;
623 }
624
625 ++first;
626 }
627
628 return n;
629 }
630
631 //***************************************************************************
632 // equal
633#if ETL_USING_STL && ETL_USING_CPP20
634 // Three parameter
635 template <typename TIterator1, typename TIterator2>
636 [[nodiscard]]
637 constexpr
638 bool equal(TIterator1 first1, TIterator1 last1, TIterator2 first2)
639 {
640 return std::equal(first1, last1, first2);
641 }
642
643 // Three parameter + predicate
644 template <typename TIterator1, typename TIterator2, typename TPredicate>
645 [[nodiscard]]
646 constexpr
647 bool equal(TIterator1 first1, TIterator1 last1, TIterator2 first2, TPredicate predicate)
648 {
649 return std::equal(first1, last1, first2, predicate);
650 }
651
652 // Four parameter
653 template <typename TIterator1, typename TIterator2>
654 [[nodiscard]]
655 constexpr
656 bool equal(TIterator1 first1, TIterator1 last1, TIterator2 first2, TIterator2 last2)
657 {
658 return std::equal(first1, last1, first2, last2);
659 }
660
661 // Four parameter + Predicate
662 template <typename TIterator1, typename TIterator2, typename TPredicate>
663 [[nodiscard]]
664 constexpr
665 bool equal(TIterator1 first1, TIterator1 last1, TIterator2 first2, TIterator2 last2, TPredicate predicate)
666 {
667 return std::equal(first1, last1, first2, last2, predicate);
668 }
669
670#else
671
672 template <typename TIterator1, typename TIterator2>
673 ETL_NODISCARD
674 ETL_CONSTEXPR14
675 bool equal(TIterator1 first1, TIterator1 last1, TIterator2 first2)
676 {
677 while (first1 != last1)
678 {
679 if (*first1 != *first2)
680 {
681 return false;
682 }
683
684 ++first1;
685 ++first2;
686 }
687
688 return true;
689 }
690
691 // Predicate
692 template <typename TIterator1, typename TIterator2, typename TPredicate>
693 ETL_NODISCARD
694 ETL_CONSTEXPR14
695 bool equal(TIterator1 first1, TIterator1 last1, TIterator2 first2, TPredicate predicate)
696 {
697 while (first1 != last1)
698 {
699 if (!predicate(*first1, *first2))
700 {
701 return false;
702 }
703
704 ++first1;
705 ++first2;
706 }
707
708 return true;
709 }
710
711 // Four parameter
712 template <typename TIterator1, typename TIterator2>
713 ETL_NODISCARD
714 ETL_CONSTEXPR14
715 bool equal(TIterator1 first1, TIterator1 last1, TIterator2 first2, TIterator2 last2)
716 {
717 while ((first1 != last1) && (first2 != last2))
718 {
719 if (*first1 != *first2)
720 {
721 return false;
722 }
723
724 ++first1;
725 ++first2;
726 }
727
728 return (first1 == last1) && (first2 == last2);
729 }
730
731 // Four parameter, Predicate
732 template <typename TIterator1, typename TIterator2, typename TPredicate>
733 ETL_NODISCARD
734 ETL_CONSTEXPR14
735 bool equal(TIterator1 first1, TIterator1 last1, TIterator2 first2, TIterator2 last2, TPredicate predicate)
736 {
737 while ((first1 != last1) && (first2 != last2))
738 {
739 if (!predicate(*first1 , *first2))
740 {
741 return false;
742 }
743
744 ++first1;
745 ++first2;
746 }
747
748 return (first1 == last1) && (first2 == last2);
749 }
750#endif
751
752 //***************************************************************************
753 // lexicographical_compare
754 //***************************************************************************
755 template <typename TIterator1, typename TIterator2, typename TCompare>
756 ETL_NODISCARD
757 ETL_CONSTEXPR14
758 bool lexicographical_compare(TIterator1 first1, TIterator1 last1,
759 TIterator2 first2, TIterator2 last2,
760 TCompare compare)
761 {
762 while ((first1 != last1) && (first2 != last2))
763 {
764 if (compare(*first1, *first2))
765 {
766 return true;
767 }
768
769 if (compare(*first2, *first1))
770 {
771 return false;
772 }
773
774 ++first1;
775 ++first2;
776 }
777
778 return (first1 == last1) && (first2 != last2);
779 }
780
781 // lexicographical_compare
782 template <typename TIterator1, typename TIterator2>
783 ETL_NODISCARD
784 ETL_CONSTEXPR14
785 bool lexicographical_compare(TIterator1 first1, TIterator1 last1,
786 TIterator2 first2, TIterator2 last2)
787 {
789
790 return etl::lexicographical_compare(first1, last1, first2, last2, compare());
791 }
792
793 //***************************************************************************
794 // min
795 //***************************************************************************
796 template <typename T, typename TCompare>
797 ETL_NODISCARD
798 ETL_CONSTEXPR
799 const T& min(const T& a, const T& b, TCompare compare)
800 {
801 return (compare(a, b)) ? a : b;
802 }
803
804 template <typename T>
805 ETL_NODISCARD
806 ETL_CONSTEXPR
807 const T& min(const T& a, const T& b)
808 {
809 typedef etl::less<T> compare;
810
811 return etl::min(a, b, compare());
812 }
813
814 //***************************************************************************
815 // max
816 //***************************************************************************
817 template <typename T, typename TCompare>
818 ETL_NODISCARD
819 ETL_CONSTEXPR
820 const T& max(const T& a, const T& b, TCompare compare)
821 {
822 return (compare(a, b)) ? b : a;
823 }
824
825 template <typename T>
826 ETL_NODISCARD
827 ETL_CONSTEXPR
828 const T& max(const T& a, const T& b)
829 {
830 typedef etl::less<T> compare;
831
832 return etl::max(a, b, compare());
833 }
834
835 //***************************************************************************
836 // for_each
837 //***************************************************************************
838 template <typename TIterator, typename TUnaryOperation>
839 ETL_CONSTEXPR14
840 TUnaryOperation for_each(TIterator first, TIterator last, TUnaryOperation unary_operation)
841 {
842 while (first != last)
843 {
844 unary_operation(*first);
845 ++first;
846 }
847
848 return unary_operation;
849 }
850
851 //***************************************************************************
852 // transform
853 //***************************************************************************
854 template <typename TIteratorIn, typename TIteratorOut, typename TUnaryOperation>
855 ETL_CONSTEXPR14
856 TIteratorOut transform(TIteratorIn first1, TIteratorIn last1, TIteratorOut d_first, TUnaryOperation unary_operation)
857 {
858 while (first1 != last1)
859 {
860 *d_first = unary_operation(*first1);
861
862 ++d_first;
863 ++first1;
864 }
865
866 return d_first;
867 }
868
869 template <typename TIteratorIn1, typename TIteratorIn2, typename TIteratorOut, typename TBinaryOperation>
870 ETL_CONSTEXPR14
871 TIteratorOut transform(TIteratorIn1 first1, TIteratorIn1 last1, TIteratorIn2 first2, TIteratorOut d_first, TBinaryOperation binary_operation)
872 {
873 while (first1 != last1)
874 {
875 *d_first = binary_operation(*first1, *first2);
876
877 ++d_first;
878 ++first1;
879 ++first2;
880 }
881
882 return d_first;
883 }
884
885 //***************************************************************************
886 // replace
887 //***************************************************************************
888 template <typename TIterator, typename T>
889 ETL_CONSTEXPR14 void replace(TIterator first, TIterator last, const T& old_value, const T& new_value)
890 {
891 while (first != last)
892 {
893 if (*first == old_value)
894 {
895 *first = new_value;
896 }
897
898 ++first;
899 }
900 }
901
902 //***************************************************************************
903 // replace_if
904 //***************************************************************************
905 template <typename TIterator, typename TPredicate, typename T>
906 ETL_CONSTEXPR14 void replace_if(TIterator first, TIterator last, TPredicate predicate, const T& new_value)
907 {
908 while (first != last)
909 {
910 if (predicate(*first))
911 {
912 *first = new_value;
913 }
914
915 ++first;
916 }
917 }
918
919 //***************************************************************************
920 // Heap
921 //***************************************************************************
922 namespace private_heap
923 {
924 // Push Heap Helper
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)
927 {
928 TDistance parent = (value_index - 1) / 2;
929
930 while ((value_index > top_index) && compare(first[parent], value))
931 {
932 first[value_index] = etl::move(first[parent]);
933 value_index = parent;
934 parent = (value_index - 1) / 2;
935 }
936
937 first[value_index] = etl::move(value);
938 }
939
940 // Adjust Heap Helper
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)
943 {
944 TDistance top_index = value_index;
945 TDistance child2nd = (2 * value_index) + 2;
946
947 while (child2nd < length)
948 {
949 if (compare(first[child2nd], first[child2nd - 1]))
950 {
951 --child2nd;
952 }
953
954 first[value_index] = etl::move(first[child2nd]);
955 value_index = child2nd;
956 child2nd = 2 * (child2nd + 1);
957 }
958
959 if (child2nd == length)
960 {
961 first[value_index] = etl::move(first[child2nd - 1]);
962 value_index = child2nd - 1;
963 }
964
965 push_heap(first, value_index, top_index, etl::move(value), compare);
966 }
967
968 // Is Heap Helper
969 template <typename TIterator, typename TDistance, typename TCompare>
970 bool is_heap(const TIterator first, const TDistance n, TCompare compare)
971 {
972 TDistance parent = 0;
973
974 for (TDistance child = 1; child < n; ++child)
975 {
976 if (compare(first[parent], first[child]))
977 {
978 return false;
979 }
980
981 if ((child & 1) == 0)
982 {
983 ++parent;
984 }
985 }
986
987 return true;
988 }
989 }
990
991 // Pop Heap
992 template <typename TIterator, typename TCompare>
993 void pop_heap(TIterator first, TIterator last, TCompare compare)
994 {
995 typedef typename etl::iterator_traits<TIterator>::value_type value_t;
996 typedef typename etl::iterator_traits<TIterator>::difference_type distance_t;
997
998 value_t value = etl::move(last[-1]);
999 last[-1] = etl::move(first[0]);
1000
1001 private_heap::adjust_heap(first, distance_t(0), distance_t(last - first - 1), etl::move(value), compare);
1002 }
1003
1004 // Pop Heap
1005 template <typename TIterator>
1006 void pop_heap(TIterator first, TIterator last)
1007 {
1009
1010 etl::pop_heap(first, last, compare());
1011 }
1012
1013 // Push Heap
1014 template <typename TIterator, typename TCompare>
1015 void push_heap(TIterator first, TIterator last, TCompare compare)
1016 {
1017 typedef typename etl::iterator_traits<TIterator>::difference_type difference_t;
1018 typedef typename etl::iterator_traits<TIterator>::value_type value_t;
1019
1020 private_heap::push_heap(first, difference_t(last - first - 1), difference_t(0), value_t(etl::move(*(last - 1))), compare);
1021 }
1022
1023 // Push Heap
1024 template <typename TIterator>
1025 void push_heap(TIterator first, TIterator last)
1026 {
1028
1029 etl::push_heap(first, last, compare());
1030 }
1031
1032 // Make Heap
1033 template <typename TIterator, typename TCompare>
1034 void make_heap(TIterator first, TIterator last, TCompare compare)
1035 {
1036 typedef typename etl::iterator_traits<TIterator>::difference_type difference_t;
1037
1038 if ((last - first) < 2)
1039 {
1040 return;
1041 }
1042
1043 difference_t length = last - first;
1044 difference_t parent = (length - 2) / 2;
1045
1046 while (true)
1047 {
1048 private_heap::adjust_heap(first, parent, length, etl::move(*(first + parent)), compare);
1049
1050 if (parent == 0)
1051 {
1052 return;
1053 }
1054
1055 --parent;
1056 }
1057 }
1058
1059 // Make Heap
1060 template <typename TIterator>
1061 void make_heap(TIterator first, TIterator last)
1062 {
1064
1065 etl::make_heap(first, last, compare());
1066 }
1067
1068 // Is Heap
1069 template <typename TIterator>
1070 ETL_NODISCARD
1071 bool is_heap(TIterator first, TIterator last)
1072 {
1074
1075 return private_heap::is_heap(first, last - first, compare());
1076 }
1077
1078 // Is Heap
1079 template <typename TIterator, typename TCompare>
1080 ETL_NODISCARD
1081 bool is_heap(TIterator first, TIterator last, TCompare compare)
1082 {
1083 return private_heap::is_heap(first, last - first, compare);
1084 }
1085
1086 // Sort Heap
1087 template <typename TIterator>
1088 void sort_heap(TIterator first, TIterator last)
1089 {
1090 while (first != last)
1091 {
1092 etl::pop_heap(first, last);
1093 --last;
1094 }
1095 }
1096
1097 // Sort Heap
1098 template <typename TIterator, typename TCompare>
1099 void sort_heap(TIterator first, TIterator last, TCompare compare)
1100 {
1101 while (first != last)
1102 {
1103 etl::pop_heap(first, last, compare);
1104 --last;
1105 }
1106 }
1107
1108 //***************************************************************************
1109 // Search
1110 //***************************************************************************
1111 template<typename TIterator1, typename TIterator2, typename TCompare>
1112 ETL_NODISCARD
1113 ETL_CONSTEXPR14
1114 TIterator1 search(TIterator1 first, TIterator1 last, TIterator2 search_first, TIterator2 search_last, TCompare compare)
1115 {
1116 while (true)
1117 {
1118 TIterator1 itr = first;
1119 TIterator2 search_itr = search_first;
1120
1121 while (true)
1122 {
1123 if (search_itr == search_last)
1124 {
1125 return first;
1126 }
1127
1128 if (itr == last)
1129 {
1130 return last;
1131 }
1132
1133 if (!compare(*itr, *search_itr))
1134 {
1135 break;
1136 }
1137
1138 ++itr;
1139 ++search_itr;
1140 }
1141
1142 ++first;
1143 }
1144 }
1145
1146 // Search
1147 template<typename TIterator1, typename TIterator2>
1148 ETL_NODISCARD
1149 ETL_CONSTEXPR14
1150 TIterator1 search(TIterator1 first, TIterator1 last, TIterator2 search_first, TIterator2 search_last)
1151 {
1153
1154 return etl::search(first, last, search_first, search_last, compare());
1155 }
1156
1157 //***************************************************************************
1158 // Rotate
1159 //***************************************************************************
1160 namespace private_algorithm
1161 {
1162#if ETL_USING_CPP11
1163 //*********************************
1164 // For random access iterators
1165 template <typename TIterator>
1166 ETL_CONSTEXPR14
1168 rotate_general(TIterator first, TIterator middle, TIterator last)
1169 {
1170 if (first == middle || middle == last)
1171 {
1172 return first;
1173 }
1174
1175 typedef typename etl::iterator_traits<TIterator>::value_type value_type;
1176
1177 int n = last - first;
1178 int m = middle - first;
1179 int gcd_nm = (n == 0 || m == 0) ? n + m : etl::gcd(n, m);
1180
1181 TIterator result = first + (last - middle);
1182
1183 for (int i = 0; i < gcd_nm; i++)
1184 {
1185 value_type temp = etl::move(*(first + i));
1186 int j = i;
1187
1188 while (true)
1189 {
1190 int k = j + m;
1191
1192 if (k >= n)
1193 {
1194 k = k - n;
1195 }
1196
1197 if (k == i)
1198 {
1199 break;
1200 }
1201
1202 *(first + j) = etl::move(*(first + k));
1203 j = k;
1204 }
1205
1206 *(first + j) = etl::move(temp);
1207 }
1208
1209 return result;
1210 }
1211#else
1212 //*********************************
1213 // For random access iterators
1214 template <typename TIterator>
1215 ETL_CONSTEXPR14
1217 rotate_general(TIterator first, TIterator middle, TIterator last)
1218 {
1219 if (first == middle || middle == last)
1220 {
1221 return first;
1222 }
1223
1224 typedef typename etl::iterator_traits<TIterator>::value_type value_type;
1225
1226 int n = last - first;
1227 int m = middle - first;
1228 int gcd_nm = (n == 0 || m == 0) ? n + m : etl::gcd(n, m);
1229
1230 TIterator result = first + (last - middle);
1231
1232 for (int i = 0; i < gcd_nm; i++)
1233 {
1234 value_type temp = *(first + i);
1235 int j = i;
1236
1237 while (true)
1238 {
1239 int k = j + m;
1240
1241 if (k >= n)
1242 {
1243 k = k - n;
1244 }
1245
1246 if (k == i)
1247 {
1248 break;
1249 }
1250
1251 *(first + j) = *(first + k);
1252 j = k;
1253 }
1254
1255 *(first + j) = temp;
1256 }
1257
1258 return result;
1259 }
1260#endif
1261
1262 //*********************************
1263 // For bidirectional iterators
1264 template <typename TIterator>
1265 ETL_CONSTEXPR14
1267 rotate_general(TIterator first, TIterator middle, TIterator last)
1268 {
1269 if (first == middle || middle == last)
1270 {
1271 return first;
1272 }
1273
1274 TIterator result = first;
1275 etl::advance(result, etl::distance(middle, last));
1276
1277 reverse(first, middle);
1278 reverse(middle, last);
1279 reverse(first, last);
1280
1281 return result;
1282 }
1283
1284 //*********************************
1285 // For forward iterators
1286 template <typename TIterator>
1287 ETL_CONSTEXPR14
1289 rotate_general(TIterator first, TIterator middle, TIterator last)
1290 {
1291 if (first == middle || middle == last)
1292 {
1293 return first;
1294 }
1295
1296 TIterator next = middle;
1297 TIterator result = first;
1298 etl::advance(result, etl::distance(middle, last));
1299
1300 while (first != next)
1301 {
1302 using ETL_OR_STD::swap;
1303 swap(*first++, *next++);
1304
1305 if (next == last)
1306 {
1307 next = middle;
1308 }
1309 else if (first == middle)
1310 {
1311 middle = next;
1312 }
1313 }
1314
1315 return result;
1316 }
1317
1318 //*********************************
1319 // Simplified algorithm for rotate left by one
1320 template <typename TIterator>
1321 ETL_CONSTEXPR14
1322 TIterator rotate_left_by_one(TIterator first, TIterator last)
1323 {
1324 typedef typename etl::iterator_traits<TIterator>::value_type value_type;
1325
1326 // Save the first item.
1327 value_type temp(etl::move(*first));
1328
1329 // Move the rest.
1330 TIterator result = etl::move(etl::next(first), last, first);
1331
1332 // Restore the first item in its rotated position.
1333 *result = etl::move(temp);
1334
1335 // The new position of the first item.
1336 return result;
1337 }
1338
1339 //*********************************
1340 // Simplified for algorithm rotate right by one
1341 template <typename TIterator>
1342 ETL_CONSTEXPR14
1343 TIterator rotate_right_by_one(TIterator first, TIterator last)
1344 {
1345 typedef typename etl::iterator_traits<TIterator>::value_type value_type;
1346
1347 // Save the last item.
1348 TIterator previous = etl::prev(last);
1349 value_type temp(etl::move(*previous));
1350
1351 // Move the rest.
1352 TIterator result = etl::move_backward(first, previous, last);
1353
1354 // Restore the last item in its rotated position.
1355 *first = etl::move(temp);
1356
1357 // The new position of the first item.
1358 return result;
1359 }
1360 }
1361
1362 //*********************************
1363 template<typename TIterator>
1364 ETL_CONSTEXPR14
1365 TIterator rotate(TIterator first, TIterator middle, TIterator last)
1366 {
1367 if (etl::next(first) == middle)
1368 {
1369 return private_algorithm::rotate_left_by_one(first, last);
1370 }
1371
1372 if (etl::next(middle) == last)
1373 {
1374#if ETL_USING_CPP20
1376 {
1377 return private_algorithm::rotate_general(first, middle, last);
1378 }
1379 else
1380 {
1381 return private_algorithm::rotate_right_by_one(first, last);
1382 }
1383#else
1384 return private_algorithm::rotate_general(first, middle, last);
1385#endif
1386 }
1387
1388 return private_algorithm::rotate_general(first, middle, last);
1389 }
1390
1391 //***************************************************************************
1392 // find_end
1393 //***************************************************************************
1394 // Predicate
1395 template <typename TIterator1, typename TIterator2, typename TPredicate>
1396 ETL_NODISCARD
1397 ETL_CONSTEXPR14
1398 TIterator1 find_end(TIterator1 b, TIterator1 e,
1399 TIterator2 sb, TIterator2 se,
1400 TPredicate predicate)
1401 {
1402 if (sb == se)
1403 {
1404 return e;
1405 }
1406
1407 TIterator1 result = e;
1408
1409 while (true)
1410 {
1411 TIterator1 new_result = etl::search(b, e, sb, se, predicate);
1412
1413 if (new_result == e)
1414 {
1415 break;
1416 }
1417 else
1418 {
1419 result = new_result;
1420 b = result;
1421 ++b;
1422 }
1423 }
1424 return result;
1425 }
1426
1427 // Default
1428 template <typename TIterator1, typename TIterator2>
1429 ETL_NODISCARD
1430 ETL_CONSTEXPR14
1431 TIterator1 find_end(TIterator1 b, TIterator1 e,
1432 TIterator2 sb, TIterator2 se)
1433 {
1435
1436 return find_end(b, e, sb, se, predicate());
1437 }
1438
1439 //***************************************************************************
1443 //***************************************************************************
1444 template <typename TIterator, typename TCompare>
1445 ETL_NODISCARD
1446 ETL_CONSTEXPR14
1448 TIterator end,
1450 {
1452
1453 if (begin != end)
1454 {
1455 ++begin;
1456
1457 while (begin != end)
1458 {
1459 if (compare(*begin, *minimum))
1460 {
1461 minimum = begin;
1462 }
1463
1464 ++begin;
1465 }
1466 }
1467
1468 return minimum;
1469 }
1470
1471 //***************************************************************************
1475 //***************************************************************************
1476 template <typename TIterator>
1477 ETL_NODISCARD
1478 ETL_CONSTEXPR14
1480 TIterator end)
1481 {
1482 typedef typename etl::iterator_traits<TIterator>::value_type value_t;
1483
1485 }
1486
1487 //***************************************************************************
1491 //***************************************************************************
1492 template <typename TIterator, typename TCompare>
1493 ETL_NODISCARD
1494 ETL_CONSTEXPR14
1496 TIterator end,
1498 {
1499 TIterator maximum = begin;
1500
1501 if (begin != end)
1502 {
1503 ++begin;
1504
1505 while (begin != end)
1506 {
1507 if (!compare(*begin, *maximum))
1508 {
1509 maximum = begin;
1510 }
1511
1512 ++begin;
1513 }
1514 }
1515
1516 return maximum;
1517 }
1518
1519 //***************************************************************************
1523 //***************************************************************************
1524 template <typename TIterator>
1525 ETL_NODISCARD
1526 ETL_CONSTEXPR14
1528 TIterator end)
1529 {
1530 typedef typename etl::iterator_traits<TIterator>::value_type value_t;
1531
1533 }
1534
1535 //***************************************************************************
1539 //***************************************************************************
1540 template <typename TIterator, typename TCompare>
1541 ETL_NODISCARD
1542 ETL_CONSTEXPR14
1543 ETL_OR_STD::pair<TIterator, TIterator> minmax_element(TIterator begin,
1544 TIterator end,
1546 {
1548 TIterator maximum = begin;
1549
1550 if (begin != end)
1551 {
1552 ++begin;
1553
1554 while (begin != end)
1555 {
1556 if (compare(*begin, *minimum))
1557 {
1558 minimum = begin;
1559 }
1560
1561 if (compare(*maximum, *begin))
1562 {
1563 maximum = begin;
1564 }
1565
1566 ++begin;
1567 }
1568 }
1569
1570 return ETL_OR_STD::pair<TIterator, TIterator>(minimum, maximum);
1571 }
1572
1573 //***************************************************************************
1577 //***************************************************************************
1578 template <typename TIterator>
1579 ETL_NODISCARD
1580 ETL_CONSTEXPR14
1581 ETL_OR_STD::pair<TIterator, TIterator> minmax_element(TIterator begin,
1582 TIterator end)
1583 {
1584 typedef typename etl::iterator_traits<TIterator>::value_type value_t;
1585
1587 }
1588
1589 //***************************************************************************
1593 //***************************************************************************
1594 template <typename T>
1595 ETL_NODISCARD
1596 ETL_CONSTEXPR14
1597 ETL_OR_STD::pair<const T&, const T&> minmax(const T& a,
1598 const T& b)
1599 {
1600 return (b < a) ? ETL_OR_STD::pair<const T&, const T&>(b, a) : ETL_OR_STD::pair<const T&, const T&>(a, b);
1601 }
1602
1603 //***************************************************************************
1607 //***************************************************************************
1608 template <typename T, typename TCompare>
1609 ETL_NODISCARD
1610 ETL_CONSTEXPR14
1611 ETL_OR_STD::pair<const T&, const T&> minmax(const T& a,
1612 const T& b,
1614 {
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);
1616 }
1617
1618 //***************************************************************************
1622 //***************************************************************************
1623 template <typename TIterator>
1624 ETL_NODISCARD
1625 ETL_CONSTEXPR14
1627 TIterator end)
1628 {
1629 if (begin != end)
1630 {
1631 TIterator next = begin;
1632
1633 while (++next != end)
1634 {
1635 if (*next < *begin)
1636 {
1637 return next;
1638 }
1639
1640 ++begin;
1641 }
1642 }
1643
1644 return end;
1645 }
1646
1647 //***************************************************************************
1651 //***************************************************************************
1652 template <typename TIterator, typename TCompare>
1653 ETL_NODISCARD
1654 ETL_CONSTEXPR14
1656 TIterator end,
1658 {
1659 if (begin != end)
1660 {
1661 TIterator next = begin;
1662
1663 while (++next != end)
1664 {
1665 if (compare(*next, *begin))
1666 {
1667 return next;
1668 }
1669
1670 ++begin;
1671 }
1672 }
1673
1674 return end;
1675 }
1676
1677 //***************************************************************************
1681 //***************************************************************************
1682 template<typename TIterator>
1683 ETL_NODISCARD
1684 ETL_CONSTEXPR14
1686 TIterator end)
1687 {
1688 return etl::is_sorted_until(begin, end) == end;
1689 }
1690
1691 //***************************************************************************
1695 //***************************************************************************
1696 template<typename TIterator, typename TCompare>
1697 ETL_NODISCARD
1698 ETL_CONSTEXPR14
1700 TIterator end,
1702 {
1704 }
1705
1706 //***************************************************************************
1710 //***************************************************************************
1711 template <typename TIterator, typename TUnaryPredicate>
1712 ETL_NODISCARD
1713 ETL_CONSTEXPR14
1715 TIterator end,
1717 {
1718 while (begin != end)
1719 {
1720 if (!predicate(*begin))
1721 {
1722 return begin;
1723 }
1724
1725 ++begin;
1726 }
1727
1728 return end;
1729 }
1730
1731 //***************************************************************************
1735 //***************************************************************************
1736 template <typename TIterator1, typename TIterator2>
1737 ETL_NODISCARD
1738 ETL_CONSTEXPR14
1742 {
1743 if (begin1 != end1)
1744 {
1746
1747 etl::advance(end2, etl::distance(begin1, end1));
1748
1749 for (TIterator1 i = begin1; i != end1; ++i)
1750 {
1751 if (i == etl::find(begin1, i, *i))
1752 {
1753 size_t n = etl::count(begin2, end2, *i);
1754
1755 if (n == 0 || size_t(etl::count(i, end1, *i)) != n)
1756 {
1757 return false;
1758 }
1759 }
1760 }
1761 }
1762
1763 return true;
1764 }
1765
1766 //***************************************************************************
1770 //***************************************************************************
1771 template <typename TIterator1, typename TIterator2, typename TBinaryPredicate>
1772 ETL_NODISCARD
1773 ETL_CONSTEXPR14
1778 {
1779 if (begin1 != end1)
1780 {
1782
1783 etl::advance(end2, etl::distance(begin1, end1));
1784
1785 for (TIterator1 i = begin1; i != end1; ++i)
1786 {
1787 if (i == etl::find_if(begin1, i, etl::bind1st(predicate, *i)))
1788 {
1789 size_t n = etl::count(begin2, end2, *i);
1790
1791 if (n == 0 || size_t(etl::count(i, end1, *i)) != n)
1792 {
1793 return false;
1794 }
1795 }
1796 }
1797 }
1798
1799 return true;
1800 }
1801
1802 //***************************************************************************
1806 //***************************************************************************
1807 template <typename TIterator1, typename TIterator2>
1808 ETL_NODISCARD
1809 ETL_CONSTEXPR14
1814 {
1815 if (begin1 != end1)
1816 {
1817 for (TIterator1 i = begin1; i != end1; ++i)
1818 {
1819 if (i == etl::find(begin1, i, *i))
1820 {
1821 size_t n = etl::count(begin2, end2, *i);
1822
1823 if (n == 0 || size_t(etl::count(i, end1, *i)) != n)
1824 {
1825 return false;
1826 }
1827 }
1828 }
1829 }
1830
1831 return true;
1832 }
1833
1834 //***************************************************************************
1838 //***************************************************************************
1839 template <typename TIterator1, typename TIterator2, typename TBinaryPredicate>
1840 ETL_NODISCARD
1846 {
1847 if (begin1 != end1)
1848 {
1849 for (TIterator1 i = begin1; i != end1; ++i)
1850 {
1851 if (i == etl::find_if(begin1, i, etl::bind1st(predicate, *i)))
1852 {
1853 size_t n = etl::count(begin2, end2, *i);
1854
1855 if (n == 0 || size_t(etl::count(i, end1, *i)) != n)
1856 {
1857 return false;
1858 }
1859 }
1860 }
1861 }
1862
1863 return true;
1864 }
1865
1866 //***************************************************************************
1870 //***************************************************************************
1871 template <typename TIterator, typename TUnaryPredicate>
1872 ETL_NODISCARD
1873 ETL_CONSTEXPR14
1875 TIterator end,
1877 {
1878 while (begin != end)
1879 {
1880 if (!predicate(*begin))
1881 {
1882 break;
1883 }
1884
1885 ++begin;
1886 }
1887
1888 while (begin != end)
1889 {
1890 if (predicate(*begin))
1891 {
1892 return false;
1893 }
1894
1895 ++begin;
1896 }
1897
1898 return true;
1899 }
1900
1901 //***************************************************************************
1905 //***************************************************************************
1906 template <typename TIterator, typename TUnaryPredicate>
1907 ETL_NODISCARD
1908 ETL_CONSTEXPR14
1910 TIterator end,
1912 {
1913 while (begin != end)
1914 {
1915 if (!predicate(*begin))
1916 {
1917 return begin;
1918 }
1919
1920 ++begin;
1921 }
1922
1923 return begin;
1924 }
1925
1926 //***************************************************************************
1931 //***************************************************************************
1932 template <typename TSource, typename TDestinationTrue, typename TDestinationFalse, typename TUnaryPredicate>
1933 ETL_CONSTEXPR14
1934 ETL_OR_STD::pair<TDestinationTrue, TDestinationFalse> partition_copy(TSource begin,
1935 TSource end,
1939 {
1940 while (begin != end)
1941 {
1942 if (predicate(*begin))
1943 {
1946 }
1947 else
1948 {
1951 }
1952
1953 ++begin;
1954 }
1955
1956 return ETL_OR_STD::pair<TDestinationTrue, TDestinationFalse>(destination_true, destination_false);
1957 }
1958
1959 //***************************************************************************
1963 //***************************************************************************
1964 template <typename TIterator, typename TOutputIterator, typename TUnaryPredicate>
1965 ETL_CONSTEXPR14
1967 TIterator end,
1968 TOutputIterator out,
1970 {
1971 while (begin != end)
1972 {
1973 if (predicate(*begin))
1974 {
1975 *out = *begin;
1976 ++out;
1977 }
1978
1979 ++begin;
1980 }
1981
1982 return out;
1983 }
1984
1985 //***************************************************************************
1989 //***************************************************************************
1990 template <typename TIterator, typename TUnaryPredicate>
1991 ETL_NODISCARD
1992 ETL_CONSTEXPR14
1999
2000 //***************************************************************************
2004 //***************************************************************************
2005 template <typename TIterator, typename TUnaryPredicate>
2006 ETL_NODISCARD
2007 ETL_CONSTEXPR14
2009 TIterator end,
2011 {
2012 return etl::find_if(begin, end, predicate) != end;
2013 }
2014
2015 //***************************************************************************
2019 //***************************************************************************
2020 template <typename TIterator, typename TUnaryPredicate>
2021 ETL_NODISCARD
2022 ETL_CONSTEXPR14
2024 TIterator end,
2026 {
2027 return etl::find_if(begin, end, predicate) == end;
2028 }
2029
2030#if ETL_NOT_USING_STL
2031 //***************************************************************************
2035 //***************************************************************************
2036 template <typename TIterator, typename TCompare>
2037 void sort(TIterator first, TIterator last, TCompare compare)
2038 {
2039 etl::shell_sort(first, last, compare);
2040 }
2041
2042 //***************************************************************************
2045 //***************************************************************************
2046 template <typename TIterator>
2047 void sort(TIterator first, TIterator last)
2048 {
2049 etl::shell_sort(first, last, etl::less<typename etl::iterator_traits<TIterator>::value_type>());
2050 }
2051
2052 //***************************************************************************
2057 //***************************************************************************
2058 template <typename TIterator, typename TCompare>
2059 void stable_sort(TIterator first, TIterator last, TCompare compare)
2060 {
2061 etl::insertion_sort(first, last, compare);
2062 }
2063
2064 //***************************************************************************
2068 //***************************************************************************
2069 template <typename TIterator>
2070 void stable_sort(TIterator first, TIterator last)
2071 {
2072 etl::insertion_sort(first, last, etl::less<typename etl::iterator_traits<TIterator>::value_type>());
2073 }
2074#else
2075 //***************************************************************************
2079 //***************************************************************************
2080 template <typename TIterator, typename TCompare>
2082 {
2083 std::sort(first, last, compare);
2084 }
2085
2086 //***************************************************************************
2089 //***************************************************************************
2090 template <typename TIterator>
2091 void sort(TIterator first, TIterator last)
2092 {
2093 std::sort(first, last);
2094 }
2095
2096 //***************************************************************************
2101 //***************************************************************************
2102 template <typename TIterator, typename TCompare>
2104 {
2105 std::stable_sort(first, last, compare);
2106 }
2107
2108 //***************************************************************************
2112 //***************************************************************************
2113 template <typename TIterator>
2115 {
2116 std::stable_sort(first, last);
2117 }
2118#endif
2119
2120 //***************************************************************************
2123 //***************************************************************************
2124 template <typename TIterator, typename T>
2125 ETL_CONSTEXPR14
2127 {
2128 while (first != last)
2129 {
2130 sum = etl::move(sum) + *first;
2131 ++first;
2132 }
2133
2134 return sum;
2135 }
2136
2137 //***************************************************************************
2140 //***************************************************************************
2141 template <typename TIterator, typename T, typename TBinaryOperation>
2142 ETL_CONSTEXPR14
2143 T accumulate(TIterator first, TIterator last, T sum, TBinaryOperation operation)
2144 {
2145 while (first != last)
2146 {
2147 sum = operation(etl::move(sum), *first);
2148 ++first;
2149 }
2150
2151 return sum;
2152 }
2153
2154 //***************************************************************************
2157 //***************************************************************************
2158 template<typename T, typename TCompare>
2159 ETL_CONSTEXPR
2160 T clamp(const T& value, const T& low, const T& high, TCompare compare)
2161 {
2162 return compare(value, low) ? low : compare(high, value) ? high : value;
2163 }
2164
2165 template <typename T>
2166 ETL_CONSTEXPR
2167 T clamp(const T& value, const T& low, const T& high)
2168 {
2169 return clamp(value, low, high, etl::less<T>());
2170 }
2171
2172 template<typename T, T Low, T High, typename TCompare>
2173 ETL_CONSTEXPR
2174 T clamp(const T& value, TCompare compare)
2175 {
2176 return compare(value, Low) ? Low : compare(High, value) ? High : value;
2177 }
2178
2179 template <typename T, T Low, T High>
2180 ETL_CONSTEXPR
2181 T clamp(const T& value)
2182 {
2183 return clamp<T, Low, High>(value, etl::less<T>());
2184 }
2185
2186 //***************************************************************************
2189 //***************************************************************************
2190 template <typename TIterator, typename T>
2191 ETL_CONSTEXPR14
2192 TIterator remove(TIterator first, TIterator last, const T& value)
2193 {
2194 first = etl::find(first, last, value);
2195
2196 if (first != last)
2197 {
2198 TIterator itr = first;
2199
2200 while (++itr != last)
2201 {
2202 if (!(*itr == value))
2203 {
2204 *first++ = etl::move(*itr);
2205 }
2206 }
2207 }
2208
2209 return first;
2210 }
2211
2212 //***************************************************************************
2215 //***************************************************************************
2216 template <typename TIterator, typename TUnaryPredicate>
2217 ETL_CONSTEXPR14
2219 {
2220 first = etl::find_if(first, last, predicate);
2221
2222 if (first != last)
2223 {
2224 TIterator itr = first;
2225
2226 while (++itr != last)
2227 {
2228 if (!predicate(*itr))
2229 {
2230 *first++ = etl::move(*itr);
2231 }
2232 }
2233 }
2234
2235 return first;
2236 }
2237}
2238
2239//*****************************************************************************
2240// ETL extensions to the STL algorithms.
2241//*****************************************************************************
2242namespace etl
2243{
2244 //***************************************************************************
2254 //***************************************************************************
2255 template <typename TInputIterator,
2256 typename TOutputIterator>
2257 ETL_CONSTEXPR14
2264 {
2265 size_t s_size = etl::distance(i_begin, i_end);
2266 size_t d_size = etl::distance(o_begin, o_end);
2267 size_t size = (s_size < d_size) ? s_size : d_size;
2268
2269 return etl::copy(i_begin, i_begin + size, o_begin);
2270 }
2271
2272 //***************************************************************************
2282 //***************************************************************************
2283 template <typename TInputIterator,
2284 typename TOutputIterator>
2285 ETL_CONSTEXPR14
2292 {
2293 while ((i_begin != i_end) && (o_begin != o_end))
2294 {
2295 *o_begin = *i_begin;
2296 ++o_begin;
2297 ++i_begin;
2298 }
2299
2300 return o_begin;
2301 }
2302
2303 //***************************************************************************
2307 //***************************************************************************
2308 template <typename TInputIterator,
2309 typename TSize,
2310 typename TOutputIterator>
2311 ETL_CONSTEXPR14
2313 TSize n,
2316 {
2317 while ((n-- > 0) && (o_begin != o_end))
2318 {
2319 *o_begin = *i_begin;
2320 ++o_begin;
2321 ++i_begin;
2322 }
2323
2324 return o_begin;
2325 }
2326
2327 //***************************************************************************
2331 //***************************************************************************
2332 template <typename TInputIterator,
2333 typename TSize1,
2334 typename TOutputIterator,
2335 typename TSize2>
2336 ETL_CONSTEXPR14
2338 TSize1 n1,
2340 TSize2 n2)
2341 {
2342 while ((n1-- > 0) && (n2-- > 0))
2343 {
2344 *o_begin = *i_begin;
2345 ++o_begin;
2346 ++i_begin;
2347 }
2348
2349 return o_begin;
2350 }
2351
2352 //***************************************************************************
2357 //***************************************************************************
2358 template <typename TInputIterator,
2359 typename TOutputIterator,
2360 typename TUnaryPredicate>
2361 ETL_CONSTEXPR14
2367 {
2368 while ((i_begin != i_end) && (o_begin != o_end))
2369 {
2370 if (predicate(*i_begin))
2371 {
2372 *o_begin = *i_begin;
2373 ++o_begin;
2374 }
2375
2376 ++i_begin;
2377 }
2378
2379 return o_begin;
2380 }
2381
2382 //***************************************************************************
2386 //***************************************************************************
2387 template <typename TInputIterator,
2388 typename TSize,
2389 typename TOutputIterator,
2390 typename TUnaryPredicate>
2391 ETL_CONSTEXPR14
2393 TSize n,
2396 {
2397 while (n-- > 0)
2398 {
2399 if (predicate(*i_begin))
2400 {
2401 *o_begin = *i_begin;
2402 ++o_begin;
2403 }
2404
2405 ++i_begin;
2406 }
2407
2408 return o_begin;
2409 }
2410
2411#if ETL_USING_CPP11
2412 //***************************************************************************
2422 //***************************************************************************
2423 template <typename TInputIterator, typename TOutputIterator>
2424 ETL_CONSTEXPR14
2427 move_s(TInputIterator i_begin,
2428 TInputIterator i_end,
2429 TOutputIterator o_begin,
2430 TOutputIterator o_end)
2431 {
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;
2435
2436 return etl::move(i_begin, i_begin + size, o_begin);
2437 }
2438
2439 //***************************************************************************
2449 //***************************************************************************
2450 template <typename TInputIterator, typename TOutputIterator>
2451 ETL_CONSTEXPR14
2454 move_s(TInputIterator i_begin,
2455 TInputIterator i_end,
2456 TOutputIterator o_begin,
2457 TOutputIterator o_end)
2458 {
2459 while ((i_begin != i_end) && (o_begin != o_end))
2460 {
2461 *o_begin = etl::move(*i_begin);
2462 ++i_begin;
2463 ++o_begin;
2464 }
2465
2466 return o_begin;
2467 }
2468#else
2469 //***************************************************************************
2480 //***************************************************************************
2481 template <typename TInputIterator, typename TOutputIterator>
2486 {
2487 // Move not supported. Defer to copy.
2489 }
2490#endif
2491
2492 //***************************************************************************
2496 //***************************************************************************
2497 template <typename TIterator, typename TValue>
2498 ETL_NODISCARD
2499 ETL_CONSTEXPR14
2501 TIterator end,
2502 const TValue& value)
2503 {
2504 TIterator it = etl::lower_bound(begin, end, value);
2505
2506 if ((it == end) || (*it != value))
2507 {
2508 it = end;
2509 }
2510
2511 return it;
2512 }
2513
2514 //***************************************************************************
2518 //***************************************************************************
2519 template <typename TIterator,
2520 typename TValue,
2521 typename TBinaryPredicate,
2522 typename TBinaryEquality>
2523 ETL_NODISCARD
2524 ETL_CONSTEXPR14
2526 TIterator end,
2527 const TValue& value,
2530 {
2531 TIterator it = etl::lower_bound(begin, end, value, predicate);
2532
2533 if ((it == end) || !equality(*it, value))
2534 {
2535 it = end;
2536 }
2537
2538 return it;
2539 }
2540
2541 //***************************************************************************
2544 //***************************************************************************
2545 template <typename TIterator,
2546 typename TUnaryFunction,
2547 typename TUnaryPredicate>
2548 ETL_CONSTEXPR14
2550 const TIterator end,
2553 {
2554 while (begin != end)
2555 {
2556 if (predicate(*begin))
2557 {
2558 function(*begin);
2559 }
2560
2561 ++begin;
2562 }
2563
2564 return function;
2565 }
2566
2567 //***************************************************************************
2570 //***************************************************************************
2571 template <typename TIterator,
2572 typename TSize,
2573 typename TUnaryFunction>
2574 ETL_CONSTEXPR14
2576 TSize n,
2578 {
2579 while (n-- > 0)
2580 {
2581 function(*begin);
2582 ++begin;
2583 }
2584
2585 return begin;
2586 }
2587
2588 //***************************************************************************
2591 //***************************************************************************
2592 template <typename TIterator,
2593 typename TSize,
2594 typename TUnaryFunction,
2595 typename TUnaryPredicate>
2596 ETL_CONSTEXPR14
2598 TSize n,
2601 {
2602 while (n-- > 0)
2603 {
2604 if (predicate(*begin))
2605 {
2606 function(*begin);
2607 }
2608
2609 ++begin;
2610 }
2611
2612 return begin;
2613 }
2614
2615 //***************************************************************************
2620 //***************************************************************************
2621 template <typename TInputIterator, typename TOutputIterator, typename TUnaryFunction>
2622 ETL_CONSTEXPR14
2628 {
2629 while ((i_begin != i_end) && (o_begin != o_end))
2630 {
2632 ++i_begin;
2633 ++o_begin;
2634 }
2635
2636 return o_begin;
2637 }
2638
2639 //***************************************************************************
2644 //***************************************************************************
2645 template <typename TInputIterator,
2646 typename TSize,
2647 typename TOutputIterator,
2648 typename TUnaryFunction>
2649 ETL_CONSTEXPR14
2651 TSize n,
2654 {
2656 etl::advance(i_end, n);
2657
2658 etl::transform(i_begin, i_end, o_begin, function);
2659 }
2660
2661 //***************************************************************************
2666 //***************************************************************************
2667 template <typename TInputIterator1,
2668 typename TInputIterator2,
2669 typename TSize,
2670 typename TOutputIterator,
2671 typename TBinaryFunction>
2672 ETL_CONSTEXPR14
2675 TSize n,
2678 {
2680 etl::advance(i_end1, n);
2681
2682 etl::transform(i_begin1, i_end1, i_begin2, o_begin, function);
2683 }
2684
2685 //***************************************************************************
2688 //***************************************************************************
2689 template <typename TInputIterator,
2690 typename TOutputIterator,
2691 typename TUnaryFunction,
2692 typename TUnaryPredicate>
2693 ETL_CONSTEXPR14
2695 const TInputIterator i_end,
2699 {
2700 while (i_begin != i_end)
2701 {
2702 if (predicate(*i_begin))
2703 {
2705 ++o_begin;
2706 }
2707
2708 ++i_begin;
2709 }
2710
2711 return o_begin;
2712 }
2713
2714 //***************************************************************************
2717 //***************************************************************************
2718 template <typename TInputIterator1,
2719 typename TInputIterator2,
2720 typename TOutputIterator,
2721 typename TBinaryFunction,
2722 typename TBinaryPredicate>
2723 ETL_CONSTEXPR14
2725 const TInputIterator1 i_end1,
2730 {
2731 while (i_begin1 != i_end1)
2732 {
2733 if (predicate(*i_begin1, *i_begin2))
2734 {
2736 ++o_begin;
2737 }
2738
2739 ++i_begin1;
2740 ++i_begin2;
2741 }
2742
2743 return o_begin;
2744 }
2745
2746 //***************************************************************************
2749 //***************************************************************************
2750 template <typename TInputIterator,
2751 typename TSize,
2752 typename TOutputIterator,
2753 typename TUnaryFunction,
2754 typename TUnaryPredicate>
2755 ETL_CONSTEXPR14
2757 TSize n,
2761 {
2762 while (n-- > 0)
2763 {
2764 if (predicate(*i_begin))
2765 {
2767 ++o_begin;
2768 }
2769
2770 ++i_begin;
2771 }
2772
2773 return o_begin;
2774 }
2775
2776 //***************************************************************************
2779 //***************************************************************************
2780 template <typename TInputIterator1,
2781 typename TInputIterator2,
2782 typename TSize,
2783 typename TOutputIterator,
2784 typename TBinaryFunction,
2785 typename TBinaryPredicate>
2786 ETL_CONSTEXPR14
2789 TSize n,
2793 {
2794 while (n-- > 0)
2795 {
2796 if (predicate(*i_begin1, *i_begin2))
2797 {
2799 }
2800
2801 ++i_begin1;
2802 ++i_begin2;
2803 }
2804
2805 return o_begin;
2806 }
2807
2808 //***************************************************************************
2812 //***************************************************************************
2813 template <typename TSource, typename TDestinationTrue, typename TDestinationFalse,
2814 typename TUnaryFunctionTrue, typename TUnaryFunctionFalse,
2815 typename TUnaryPredicate>
2816 ETL_CONSTEXPR14
2817 ETL_OR_STD::pair<TDestinationTrue, TDestinationFalse> partition_transform(TSource begin,
2818 TSource end,
2824 {
2825 while (begin != end)
2826 {
2827 if (predicate(*begin))
2828 {
2831 }
2832 else
2833 {
2836 }
2837
2838 ++begin;
2839 }
2840
2841 return ETL_OR_STD::pair<TDestinationTrue, TDestinationFalse>(destination_true, destination_false);
2842 }
2843
2844 //***************************************************************************
2848 //***************************************************************************
2849 template <typename TSource1,
2850 typename TSource2,
2851 typename TDestinationTrue,
2852 typename TDestinationFalse,
2853 typename TBinaryFunctionTrue,
2854 typename TBinaryFunctionFalse,
2855 typename TBinaryPredicate>
2856 ETL_CONSTEXPR14
2857 ETL_OR_STD::pair<TDestinationTrue, TDestinationFalse> partition_transform(TSource1 begin1,
2858 TSource1 end1,
2865 {
2866 while (begin1 != end1)
2867 {
2868 if (predicate(*begin1, *begin2))
2869 {
2872 }
2873 else
2874 {
2877 }
2878
2879 ++begin1;
2880 ++begin2;
2881 }
2882
2883 return ETL_OR_STD::pair<TDestinationTrue, TDestinationFalse>(destination_true, destination_false);
2884 }
2885
2886 //***************************************************************************
2890 //***************************************************************************
2891 template <typename TIterator, typename TCompare>
2892#if ETL_USING_STD_NAMESPACE
2893 ETL_CONSTEXPR20
2894#else
2895 ETL_CONSTEXPR14
2896#endif
2898 {
2899 if (first == last)
2900 {
2901 return;
2902 }
2903
2904 typedef typename etl::iterator_traits<TIterator>::difference_type difference_t;
2905
2906 difference_t n = etl::distance(first, last);
2907
2908 for (difference_t i = n / 2; i > 0; i /= 2)
2909 {
2910 for (difference_t j = i; j < n; ++j)
2911 {
2912 for (difference_t k = j - i; k >= 0; k -= i)
2913 {
2914 TIterator itr1 = first;
2915 TIterator itr2 = first;
2916
2917 etl::advance(itr1, k);
2918 etl::advance(itr2, k + i);
2919
2920 if (compare(*itr2, *itr1))
2921 {
2922 etl::iter_swap(itr1, itr2);
2923 }
2924 }
2925 }
2926 }
2927 }
2928
2929 //***************************************************************************
2932 //***************************************************************************
2933 template <typename TIterator>
2934#if ETL_USING_STD_NAMESPACE
2935 ETL_CONSTEXPR20
2936#else
2937 ETL_CONSTEXPR14
2938#endif
2940 {
2941 etl::shell_sort(first, last, etl::less<typename etl::iterator_traits<TIterator>::value_type>());
2942 }
2943
2944 //***************************************************************************
2948 //***************************************************************************
2949 template <typename TIterator, typename TCompare>
2950 ETL_CONSTEXPR14
2952 {
2953 for (TIterator itr = first; itr != last; ++itr)
2954 {
2955 etl::rotate(etl::upper_bound(first, itr, *itr, compare), itr, etl::next(itr));
2956 }
2957 }
2958
2959 //***************************************************************************
2962 //***************************************************************************
2963 template <typename TIterator>
2964 ETL_CONSTEXPR14
2966 {
2967 etl::insertion_sort(first, last, etl::less<typename etl::iterator_traits<TIterator>::value_type>());
2968 }
2969
2970 //***************************************************************************
2971 namespace private_algorithm
2972 {
2973 template <typename TIterator>
2974 ETL_CONSTEXPR14
2976 get_before_last(TIterator first_, TIterator last_)
2977 {
2978 TIterator last = first_;
2979 TIterator lastplus1 = first_;
2980 ++lastplus1;
2981
2982 while (lastplus1 != last_)
2983 {
2984 ++last;
2985 ++lastplus1;
2986 }
2987
2988 return last;
2989 }
2990
2991 template <typename TIterator>
2992 ETL_CONSTEXPR14
2994 get_before_last(TIterator /*first_*/, TIterator last_)
2995 {
2996 TIterator last = last_;
2997 --last;
2998
2999 return last;
3000 }
3001
3002 template <typename TIterator>
3003 ETL_CONSTEXPR14
3005 get_before_last(TIterator /*first_*/, TIterator last_)
3006 {
3007 return last_ - 1;
3008 }
3009 }
3010
3011 //***************************************************************************
3015 //***************************************************************************
3016 template <typename TIterator, typename TCompare>
3017 ETL_CONSTEXPR20
3019 {
3020 TIterator min;
3021 const TIterator ilast = private_algorithm::get_before_last(first, last);
3022 const TIterator jlast = last;
3023
3024 for (TIterator i = first; i != ilast; ++i)
3025 {
3026 min = i;
3027
3028 TIterator j = i;
3029 ++j;
3030
3031 for (; j != jlast; ++j)
3032 {
3033 if (compare(*j, *min))
3034 {
3035 min = j;
3036 }
3037 }
3038
3039 using ETL_OR_STD::swap; // Allow ADL
3040 swap(*i, *min);
3041 }
3042 }
3043
3044 //***************************************************************************
3047 //***************************************************************************
3048 template <typename TIterator>
3049 ETL_CONSTEXPR20
3051 {
3052 selection_sort(first, last, etl::less<typename etl::iterator_traits<TIterator>::value_type>());
3053 }
3054
3055 //***************************************************************************
3059 //***************************************************************************
3060 template <typename TIterator, typename TCompare>
3061 ETL_CONSTEXPR14
3063 {
3064 if (!etl::is_heap(first, last, compare))
3065 {
3066 etl::make_heap(first, last, compare);
3067 }
3068
3069 etl::sort_heap(first, last, compare);
3070 }
3071
3072 //***************************************************************************
3075 //***************************************************************************
3076 template <typename TIterator>
3077 ETL_CONSTEXPR14
3079 {
3080 if (!etl::is_heap(first, last))
3081 {
3082 etl::make_heap(first, last);
3083 }
3084
3085 etl::sort_heap(first, last);
3086 }
3087
3088 //***************************************************************************
3090 //***************************************************************************
3091#if ETL_USING_CPP11
3092 template <typename T>
3093 ETL_NODISCARD
3094 constexpr const T& multimax(const T& a, const T& b)
3095 {
3096 return a < b ? b : a;
3097 }
3098
3099 template <typename T, typename... Tx>
3100 ETL_NODISCARD
3101 constexpr const T& multimax(const T& t, const Tx&... tx)
3102 {
3103 return multimax(t, multimax(tx...));
3104 }
3105#endif
3106
3107 //***************************************************************************
3110 //***************************************************************************
3111#if ETL_USING_CPP11
3112 template <typename TCompare, typename T>
3113 ETL_NODISCARD
3114 constexpr const T& multimax_compare(TCompare compare, const T& a, const T& b)
3115 {
3116 return compare(a, b) ? b : a;
3117 }
3118
3119 template <typename TCompare, typename T, typename... Tx>
3120 ETL_NODISCARD
3121 constexpr const T& multimax_compare(TCompare compare, const T& t, const Tx&... tx)
3122 {
3123 return multimax_compare(compare, t, multimax_compare(compare, tx...));
3124 }
3125#endif
3126
3127 //***************************************************************************
3129 //***************************************************************************
3130#if ETL_USING_CPP11
3131 template <typename T>
3132 ETL_NODISCARD
3133 constexpr const T& multimin(const T& a, const T& b)
3134 {
3135 return a < b ? a : b;
3136 }
3137
3138 template <typename T, typename... Tx>
3139 ETL_NODISCARD
3140 constexpr const T& multimin(const T& t, const Tx&... tx)
3141 {
3142 return multimin(t, multimin(tx...));
3143 }
3144#endif
3145
3146 //***************************************************************************
3149 //***************************************************************************
3150#if ETL_USING_CPP11
3151 template <typename TCompare, typename T>
3152 ETL_NODISCARD
3153 constexpr const T& multimin_compare(TCompare compare, const T& a, const T& b)
3154 {
3155 return compare(a, b) ? a : b;
3156 }
3157
3158 template <typename TCompare, typename T, typename... Tx>
3159 ETL_NODISCARD
3160 constexpr const T& multimin_compare(TCompare compare, const T& t, const Tx&... tx)
3161 {
3162 return multimin_compare(compare, t, multimin_compare(compare, tx...));
3163 }
3164#endif
3165
3166 //***************************************************************************
3168 //***************************************************************************
3169#if ETL_USING_CPP11
3170 template <typename TIterator>
3171 ETL_NODISCARD
3172 constexpr const TIterator& multimax_iter(const TIterator& a, const TIterator& b)
3173 {
3174 return *a < *b ? b : a;
3175 }
3176
3177 template <typename TIterator, typename... TIteratorx>
3178 ETL_NODISCARD
3179 constexpr const TIterator& multimax_iter(const TIterator& t, const TIteratorx&... tx)
3180 {
3181 return multimax_iter(t, multimax_iter(tx...));
3182 }
3183#endif
3184
3185 //***************************************************************************
3188 //***************************************************************************
3189#if ETL_USING_CPP11
3190 template <typename TCompare, typename TIterator>
3191 ETL_NODISCARD
3192 constexpr const TIterator& multimax_iter_compare(TCompare compare, const TIterator& a, const TIterator& b)
3193 {
3194 return compare(*a, *b) ? b : a;
3195 }
3196
3197 template <typename TCompare, typename TIterator, typename... TIteratorx>
3198 ETL_NODISCARD
3199 constexpr const TIterator& multimax_iter_compare(TCompare compare, const TIterator& t, const TIteratorx&... tx)
3200 {
3201 return multimax_iter_compare(compare, t, multimax_iter_compare(compare, tx...));
3202 }
3203#endif
3204
3205 //***************************************************************************
3207 //***************************************************************************
3208#if ETL_USING_CPP11
3209 template <typename TIterator>
3210 ETL_NODISCARD
3211 constexpr const TIterator& multimin_iter(const TIterator& a, const TIterator& b)
3212 {
3213 return *a < *b ? a : b;
3214 }
3215
3216 template <typename TIterator, typename... Tx>
3217 ETL_NODISCARD
3218 constexpr const TIterator& multimin_iter(const TIterator& t, const Tx&... tx)
3219 {
3220 return multimin_iter(t, multimin_iter(tx...));
3221 }
3222#endif
3223
3224 //***************************************************************************
3227 //***************************************************************************
3228#if ETL_USING_CPP11
3229 template <typename TCompare, typename TIterator>
3230 ETL_NODISCARD
3231 constexpr const TIterator& multimin_iter_compare(TCompare compare, const TIterator& a, const TIterator& b)
3232 {
3233 return compare(*a, *b) ? a : b;
3234 }
3235
3236 template <typename TCompare, typename TIterator, typename... Tx>
3237 ETL_NODISCARD
3238 constexpr const TIterator& multimin_iter_compare(TCompare compare, const TIterator& t, const Tx&... tx)
3239 {
3240 return multimin_iter_compare(compare, t, multimin_iter_compare(compare, tx...));
3241 }
3242#endif
3243
3244 //***************************************************************************
3248 //***************************************************************************
3249 template <typename TIterator, typename TPredicate>
3250 ETL_CONSTEXPR14
3253 {
3254 first = etl::find_if_not(first, last, predicate);
3255
3256 if (first == last)
3257 {
3258 return first;
3259 }
3260
3261 for (TIterator i = etl::next(first); i != last; ++i)
3262 {
3263 if (predicate(*i))
3264 {
3265 using ETL_OR_STD::swap;
3266 swap(*i, *first);
3267 ++first;
3268 }
3269 }
3270
3271 return first;
3272 }
3273
3274 //***************************************************************************
3278 //***************************************************************************
3279 template <typename TIterator, typename TPredicate>
3280 ETL_CONSTEXPR14
3283 {
3284 while (first != last)
3285 {
3286 first = etl::find_if_not(first, last, predicate);
3287
3288 if (first == last)
3289 {
3290 break;
3291 }
3292
3293 last = etl::find_if(etl::reverse_iterator<TIterator>(last),
3295 predicate).base();
3296
3297 if (first == last)
3298 {
3299 break;
3300 }
3301
3302 --last;
3303 using ETL_OR_STD::swap;
3304 swap(*first, *last);
3305 ++first;
3306 }
3307
3308 return first;
3309 }
3310
3311 //*********************************************************
3312 namespace private_algorithm
3313 {
3314 using ETL_OR_STD::swap;
3315
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))
3318 constexpr
3319#endif
3320 TIterator nth_partition(TIterator first, TIterator last, TCompare compare)
3321 {
3322 typedef typename etl::iterator_traits<TIterator>::value_type value_type;
3323
3324 TIterator pivot = last; // Maybe find a better pivot choice?
3325 value_type pivot_value = *pivot;
3326
3327 // Swap the pivot with the last, if necessary.
3328 if (pivot != last)
3329 {
3330 swap(*pivot, *last);
3331 }
3332
3333 TIterator i = first;
3334
3335 for (TIterator j = first; j < last; ++j)
3336 {
3337 if (!compare(pivot_value, *j)) // Hack to get '*j <= pivot_value' in terms of 'pivot_value < *j'
3338 {
3339 swap(*i, *j);
3340 ++i;
3341 }
3342 }
3343
3344 swap(*i, *last);
3345
3346 return i;
3347 }
3348 }
3349
3350 //*********************************************************
3353 //*********************************************************
3354#if ETL_USING_CPP11
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))
3357 constexpr
3358#endif
3360 nth_element(TIterator first, TIterator nth, TIterator last, TCompare compare = TCompare())
3361 {
3362 if (first == last)
3363 {
3364 return;
3365 }
3366
3367 // 'last' must point to the actual last value.
3368 --last;
3369
3370 while (first <= last)
3371 {
3372 TIterator p = private_algorithm::nth_partition(first, last, compare);
3373
3374 if (p == nth)
3375 {
3376 return;
3377 }
3378 else if (p > nth)
3379 {
3380 last = p - 1;
3381 }
3382 else
3383 {
3384 first = p + 1;
3385 }
3386 }
3387 }
3388
3389#else
3390
3391 //*********************************************************
3392 template <typename TIterator, typename TCompare>
3395 {
3396 if (first == last)
3397 {
3398 return;
3399 }
3400
3401 // 'last' must point to the actual last value.
3402 --last;
3403
3404 while (first <= last)
3405 {
3406 TIterator p = private_algorithm::nth_partition(first, last, compare);
3407
3408 if (p == nth)
3409 {
3410 return;
3411 }
3412 else if (p > nth)
3413 {
3414 last = p - 1;
3415 }
3416 else
3417 {
3418 first = p + 1;
3419 }
3420 }
3421 }
3422
3423 //*********************************************************
3424 template <typename TIterator>
3426 nth_element(TIterator first, TIterator nth, TIterator last)
3427 {
3429
3430 nth_element(first, last, compare_t());
3431 }
3432#endif
3433}
3434
3435#include "private/minmax_pop.h"
3436
3437#endif
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
Definition function.h:94
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 compare.h:51
Definition iterator.h:854
Definition iterator.h:873
Definition iterator.h:63
Definition functional.h:135
pair holds two objects of arbitrary type
Definition utility.h:164
Definition algorithm.h:95