#ifndef ETL_ALGORITHM_INCLUDED
#define ETL_ALGORITHM_INCLUDED
#include "stl/algorithm.h"
#include "stl/utility.h"
#include "stl/iterator.h"
#include "stl/functional.h"
#include <stdint.h>
#include "platform.h"
#include "iterator.h"
#include "type_traits.h"
namespace etl
{
template <typename TIterator,
typename TCompare>
std::pair<TIterator, TIterator> minmax_element(TIterator begin,
TIterator end,
TCompare compare)
{
TIterator minimum = begin;
TIterator maximum = begin;
while (begin != end)
{
if (compare(*begin, *minimum))
{
minimum = begin;
}
if (compare(*maximum, *begin))
{
maximum = begin;
}
++begin;
}
return std::pair<TIterator, TIterator>(minimum, maximum);
}
template <typename TIterator>
std::pair<TIterator, TIterator> minmax_element(TIterator begin,
TIterator end)
{
typedef typename std::iterator_traits<TIterator>::value_type value_t;
return etl::minmax_element(begin, end, std::less<value_t>());
}
template <typename T>
std::pair<const T&, const T&> minmax(const T& a,
const T& b)
{
return (b < a) ? std::pair<const T&, const T&>(b, a) : std::pair<const T&, const T&>(a, b);
}
template <typename T,
typename TCompare>
std::pair<const T&, const T&> minmax(const T& a,
const T& b,
TCompare compare)
{
return compare(b, a) ? std::pair<const T&, const T&>(b, a) : std::pair<const T&, const T&>(a, b);
}
template <typename TIterator>
TIterator is_sorted_until(TIterator begin,
TIterator end)
{
if (begin != end)
{
TIterator next = begin;
while (++next != end)
{
if (*next < *begin)
{
return next;
}
++begin;
}
}
return end;
}
template <typename TIterator,
typename TCompare>
TIterator is_sorted_until(TIterator begin,
TIterator end,
TCompare compare)
{
if (begin != end)
{
TIterator next = begin;
while (++next != end)
{
if (compare(*next, *begin))
{
return next;
}
++begin;
}
}
return end;
}
template<typename TIterator>
bool is_sorted(TIterator begin,
TIterator end)
{
return etl::is_sorted_until(begin, end) == end;
}
template<typename TIterator,
typename TCompare>
bool is_sorted(TIterator begin,
TIterator end,
TCompare compare)
{
return etl::is_sorted_until(begin, end, compare) == end;
}
template <typename TInputIterator,
typename TOutputIterator>
typename etl::enable_if<etl::is_random_iterator<TInputIterator>::value &&
etl::is_random_iterator<TOutputIterator>::value, TOutputIterator>::type
copy(TInputIterator i_begin,
TInputIterator i_end,
TOutputIterator o_begin,
TOutputIterator o_end)
{
size_t s_size = std::distance(i_begin, i_end);
size_t d_size = std::distance(o_begin, o_end);
size_t size = (s_size < d_size) ? s_size : d_size;
return std::copy(i_begin, i_begin + size, o_begin);
}
template <typename TInputIterator,
typename TOutputIterator>
typename etl::enable_if<!etl::is_random_iterator<TInputIterator>::value ||
!etl::is_random_iterator<TOutputIterator>::value, TOutputIterator>::type
copy(TInputIterator i_begin,
TInputIterator i_end,
TOutputIterator o_begin,
TOutputIterator o_end)
{
while ((i_begin != i_end) && (o_begin != o_end))
{
*o_begin++ = *i_begin++;
}
return o_begin;
}
template <typename TInputIterator,
typename TSize,
typename TOutputIterator>
typename etl::enable_if<etl::is_random_iterator<TInputIterator>::value, TOutputIterator>::type
copy_n(TInputIterator i_begin,
TSize n,
TOutputIterator o_begin)
{
return std::copy(i_begin, i_begin + n, o_begin);
}
template <typename TInputIterator,
typename TSize,
typename TOutputIterator>
typename etl::enable_if<!etl::is_random_iterator<TInputIterator>::value, TOutputIterator>::type
copy_n(TInputIterator i_begin,
TSize n,
TOutputIterator o_begin)
{
while (n-- > 0)
{
*o_begin++ = *i_begin++;
}
return o_begin;
}
template <typename TInputIterator,
typename TSize,
typename TOutputIterator>
TOutputIterator copy_n(TInputIterator i_begin,
TSize n,
TOutputIterator o_begin,
TOutputIterator o_end)
{
while ((n-- > 0) && (o_begin != o_end))
{
*o_begin++ = *i_begin++;
}
return o_begin;
}
template <typename TInputIterator,
typename TSize1,
typename TOutputIterator,
typename TSize2>
TOutputIterator copy_n(TInputIterator i_begin,
TSize1 n1,
TOutputIterator o_begin,
TSize2 n2)
{
while ((n1-- > 0) && (n2-- > 0))
{
*o_begin++ = *i_begin++;
}
return o_begin;
}
template <typename TIterator,
typename TOutputIterator,
typename TUnaryPredicate>
TOutputIterator copy_if(TIterator begin,
TIterator end,
TOutputIterator out,
TUnaryPredicate predicate)
{
while (begin != end)
{
if (predicate(*begin))
{
*out++ = *begin;
}
++begin;
}
return out;
}
template <typename TInputIterator,
typename TOutputIterator,
typename TUnaryPredicate>
TOutputIterator copy_if(TInputIterator i_begin,
TInputIterator i_end,
TOutputIterator o_begin,
TOutputIterator o_end,
TUnaryPredicate predicate)
{
while ((i_begin != i_end) && (o_begin != o_end))
{
if (predicate(*i_begin))
{
*o_begin++ = *i_begin;
}
++i_begin;
}
return o_begin;
}
template <typename TInputIterator,
typename TSize,
typename TOutputIterator,
typename TUnaryPredicate>
TOutputIterator copy_n_if(TInputIterator i_begin,
TSize n,
TOutputIterator o_begin,
TUnaryPredicate predicate)
{
while (n-- > 0)
{
if (predicate(*i_begin))
{
*o_begin++ = *i_begin;
}
++i_begin;
}
return o_begin;
}
template <typename TIterator,
typename TValue>
TIterator binary_find(TIterator begin,
TIterator end,
const TValue& value)
{
TIterator it = std::lower_bound(begin, end, value);
if ((it == end) || (*it != value))
{
it = end;
}
return it;
}
template <typename TIterator,
typename TValue,
typename TBinaryPredicate,
typename TBinaryEquality>
TIterator binary_find(TIterator begin,
TIterator end,
const TValue& value,
TBinaryPredicate predicate,
TBinaryEquality equality)
{
TIterator it = std::lower_bound(begin, end, value, predicate);
if ((it == end) || !equality(*it, value))
{
it = end;
}
return it;
}
template <typename TIterator,
typename TUnaryPredicate>
TIterator find_if_not(TIterator begin,
TIterator end,
TUnaryPredicate predicate)
{
while (begin != end)
{
if (!predicate(*begin))
{
return begin;
}
++begin;
}
return end;
}
template <typename TIterator,
typename TUnaryPredicate>
bool all_of(TIterator begin,
TIterator end,
TUnaryPredicate predicate)
{
return etl::find_if_not(begin, end, predicate) == end;
}
template <typename TIterator,
typename TUnaryPredicate>
bool any_of(TIterator begin,
TIterator end,
TUnaryPredicate predicate)
{
return std::find_if(begin, end, predicate) != end;
}
template <typename TIterator,
typename TUnaryPredicate>
bool none_of(TIterator begin,
TIterator end,
TUnaryPredicate predicate)
{
return std::find_if(begin, end, predicate) == end;
}
template <typename TIterator1,
typename TIterator2>
bool is_permutation(TIterator1 begin1,
TIterator1 end1,
TIterator2 begin2)
{
if (begin1 != end1)
{
TIterator2 end2 = begin2;
std::advance(end2, std::distance(begin1, end1));
for (TIterator1 i = begin1; i != end1; ++i)
{
if (i == std::find(begin1, i, *i))
{
size_t n = std::count(begin2, end2, *i);
if (n == 0 || size_t(std::count(i, end1, *i)) != n)
{
return false;
}
}
}
}
return true;
}
template <typename TIterator1,
typename TIterator2>
bool is_permutation(TIterator1 begin1,
TIterator1 end1,
TIterator2 begin2,
TIterator2 end2)
{
if (begin1 != end1)
{
for (TIterator1 i = begin1; i != end1; ++i)
{
if (i == std::find(begin1, i, *i))
{
size_t n = std::count(begin2, end2, *i);
if (n == 0 || size_t(std::count(i, end1, *i)) != n)
{
return false;
}
}
}
}
return true;
}
template <typename TIterator1,
typename TIterator2,
typename TBinaryPredicate>
bool is_permutation(TIterator1 begin1,
TIterator1 end1,
TIterator2 begin2,
TBinaryPredicate predicate)
{
if (begin1 != end1)
{
TIterator2 end2 = begin2;
std::advance(end2, std::distance(begin1, end1));
for (TIterator1 i = begin1; i != end1; ++i)
{
#if ETL_CPP11_SUPPORTED && !defined(ETL_NO_STL)
if (i == std::find_if(begin1, i, std::bind(predicate, *i, std::placeholders::_1)))
#else
if (i == std::find_if(begin1, i, std::bind1st(predicate, *i)))
#endif
{
size_t n = std::count(begin2, end2, *i);
if (n == 0 || size_t(std::count(i, end1, *i)) != n)
{
return false;
}
}
}
}
return true;
}
template <typename TIterator1,
typename TIterator2,
typename TBinaryPredicate>
bool is_permutation(TIterator1 begin1,
TIterator1 end1,
TIterator2 begin2,
TIterator2 end2,
TBinaryPredicate predicate)
{
if (begin1 != end1)
{
for (TIterator1 i = begin1; i != end1; ++i)
{
#if ETL_CPP11_SUPPORTED && !defined(ETL_NO_STL)
if (i == std::find_if(begin1, i, std::bind(predicate, *i, std::placeholders::_1)))
#else
if (i == std::find_if(begin1, i, std::bind1st(predicate, *i)))
#endif
{
size_t n = std::count(begin2, end2, *i);
if (n == 0 || size_t(std::count(i, end1, *i)) != n)
{
return false;
}
}
}
}
return true;
}
template <typename TIterator,
typename TUnaryPredicate>
bool is_partitioned(TIterator begin,
TIterator end,
TUnaryPredicate predicate)
{
while (begin != end)
{
if (!predicate(*begin++))
{
break;
}
}
while (begin != end)
{
if (predicate(*begin++))
{
return false;
}
}
return true;
}
template <typename TIterator,
typename TUnaryPredicate>
TIterator partition_point(TIterator begin,
TIterator end,
TUnaryPredicate predicate)
{
while (begin != end)
{
if (!predicate(*begin))
{
return begin;
}
++begin;
}
return begin;
}
template <typename TSource,
typename TDestinationTrue,
typename TDestinationFalse,
typename TUnaryPredicate>
std::pair<TDestinationTrue, TDestinationFalse> partition_copy(TSource begin,
TSource end,
TDestinationTrue destination_true,
TDestinationFalse destination_false,
TUnaryPredicate predicate)
{
while (begin != end)
{
if (predicate(*begin))
{
*destination_true++ = *begin++;
}
else
{
*destination_false++ = *begin++;
}
}
return std::pair<TDestinationTrue, TDestinationFalse>(destination_true, destination_false);
}
template <typename TIterator,
typename TUnaryFunction,
typename TUnaryPredicate>
TUnaryFunction for_each_if(TIterator begin,
const TIterator end,
TUnaryFunction function,
TUnaryPredicate predicate)
{
while (begin != end)
{
if (predicate(*begin))
{
function(*begin);
}
++begin;
}
return function;
}
template <typename TIterator,
typename TSize,
typename TUnaryFunction>
TIterator for_each_n(TIterator begin,
TSize n,
TUnaryFunction function)
{
while (n-- > 0)
{
function(*begin++);
}
return begin;
}
template <typename TIterator,
typename TSize,
typename TUnaryFunction,
typename TUnaryPredicate>
TIterator for_each_n_if(TIterator begin,
TSize n,
TUnaryFunction function,
TUnaryPredicate predicate)
{
while (n-- > 0)
{
if (predicate(*begin))
{
function(*begin);
}
++begin;
}
return begin;
}
template <typename TInputIterator,
typename TOutputIterator,
typename TUnaryFunction>
void transform(TInputIterator i_begin,
TInputIterator i_end,
TOutputIterator o_begin,
TOutputIterator o_end,
TUnaryFunction function)
{
while ((i_begin != i_end) && (o_begin != o_end))
{
*o_begin++ = function(*i_begin++);
}
}
template <typename TInputIterator,
typename TSize,
typename TOutputIterator,
typename TUnaryFunction>
typename etl::enable_if<etl::is_random_iterator<TInputIterator>::value, void>::type
transform_n(TInputIterator i_begin,
TSize n,
TOutputIterator o_begin,
TUnaryFunction function)
{
std::transform(i_begin, i_begin + n, o_begin, function);
}
template <typename TInputIterator1,
typename TInputIterator2,
typename TSize,
typename TOutputIterator,
typename TBinaryFunction>
typename etl::enable_if<etl::is_random_iterator<TInputIterator1>::value &&
etl::is_random_iterator<TInputIterator2>::value, void>::type
transform_n(TInputIterator1 i_begin1,
TInputIterator2 i_begin2,
TSize n,
TOutputIterator o_begin,
TBinaryFunction function)
{
std::transform(i_begin1, i_begin1 + n, i_begin2, o_begin, function);
}
template <typename TInputIterator,
typename TSize,
typename TOutputIterator,
typename TUnaryFunction>
typename etl::enable_if<!etl::is_random_iterator<TInputIterator>::value, void>::type
transform_n(TInputIterator i_begin,
TSize n,
TOutputIterator o_begin,
TUnaryFunction function)
{
while (n > 0)
{
*o_begin++ = function(*i_begin++);
--n;
}
}
template <typename TInputIterator1,
typename TInputIterator2,
typename TSize,
typename TOutputIterator,
typename TBinaryFunction>
typename etl::enable_if<!etl::is_random_iterator<TInputIterator1>::value ||
!etl::is_random_iterator<TInputIterator2>::value, void>::type
transform_n(TInputIterator1 i_begin1,
TInputIterator2 i_begin2,
TSize n,
TOutputIterator o_begin,
TBinaryFunction function)
{
while (n > 0)
{
*o_begin++ = function(*i_begin1++, *i_begin2++);
--n;
}
}
template <typename TInputIterator,
typename TOutputIterator,
typename TUnaryFunction,
typename TUnaryPredicate>
TOutputIterator transform_if(TInputIterator i_begin,
const TInputIterator i_end,
TOutputIterator o_begin,
TUnaryFunction function,
TUnaryPredicate predicate)
{
while (i_begin != i_end)
{
if (predicate(*i_begin))
{
*o_begin++ = function(*i_begin);
}
++i_begin;
}
return o_begin;
}
template <typename TInputIterator1,
typename TInputIterator2,
typename TOutputIterator,
typename TBinaryFunction,
typename TBinaryPredicate>
TOutputIterator transform_if(TInputIterator1 i_begin1,
const TInputIterator1 i_end1,
TInputIterator2 i_begin2,
TOutputIterator o_begin,
TBinaryFunction function,
TBinaryPredicate predicate)
{
while (i_begin1 != i_end1)
{
if (predicate(*i_begin1, *i_begin2))
{
*o_begin++ = function(*i_begin1, *i_begin2);
}
++i_begin1;
++i_begin2;
}
return o_begin;
}
template <typename TInputIterator,
typename TSize,
typename TOutputIterator,
typename TUnaryFunction,
typename TUnaryPredicate>
TOutputIterator transform_n_if(TInputIterator i_begin,
TSize n,
TOutputIterator o_begin,
TUnaryFunction function,
TUnaryPredicate predicate)
{
while (n-- > 0)
{
if (predicate(*i_begin))
{
*o_begin++ = function(*i_begin);
}
++i_begin;
}
return o_begin;
}
template <typename TInputIterator1,
typename TInputIterator2,
typename TSize,
typename TOutputIterator,
typename TBinaryFunction,
typename TBinaryPredicate>
TOutputIterator transform_n_if(TInputIterator1 i_begin1,
TInputIterator2 i_begin2,
TSize n,
TOutputIterator o_begin,
TBinaryFunction function,
TBinaryPredicate predicate)
{
while (n-- > 0)
{
if (predicate(*i_begin1, *i_begin2))
{
*o_begin++ = function(*i_begin1, *i_begin2);
}
++i_begin1;
++i_begin2;
}
return o_begin;
}
template <typename TSource, typename TDestinationTrue, typename TDestinationFalse,
typename TUnaryFunctionTrue, typename TUnaryFunctionFalse,
typename TUnaryPredicate>
std::pair<TDestinationTrue, TDestinationFalse> partition_transform(TSource begin,
TSource end,
TDestinationTrue destination_true,
TDestinationFalse destination_false,
TUnaryFunctionTrue function_true,
TUnaryFunctionFalse function_false,
TUnaryPredicate predicate)
{
while (begin != end)
{
if (predicate(*begin))
{
*destination_true++ = function_true(*begin++);
}
else
{
*destination_false++ = function_false(*begin++);
}
}
return std::pair<TDestinationTrue, TDestinationFalse>(destination_true, destination_false);
}
template <typename TSource1,
typename TSource2,
typename TDestinationTrue,
typename TDestinationFalse,
typename TBinaryFunctionTrue,
typename TBinaryFunctionFalse,
typename TBinaryPredicate>
std::pair<TDestinationTrue, TDestinationFalse> partition_transform(TSource1 begin1,
TSource1 end1,
TSource2 begin2,
TDestinationTrue destination_true,
TDestinationFalse destination_false,
TBinaryFunctionTrue function_true,
TBinaryFunctionFalse function_false,
TBinaryPredicate predicate)
{
while (begin1 != end1)
{
if (predicate(*begin1, *begin2))
{
*destination_true++ = function_true(*begin1++, *begin2++);
}
else
{
*destination_false++ = function_false(*begin1++, *begin2++);
}
}
return std::pair<TDestinationTrue, TDestinationFalse>(destination_true, destination_false);
}
template <typename TIterator, typename TCompare>
void sort(TIterator first, TIterator last, TCompare compare)
{
typedef typename std::iterator_traits<TIterator>::difference_type difference_t;
difference_t n = std::distance(first, last);
for (difference_t i = n / 2; i > 0; i /= 2)
{
for (difference_t j = i; j < n; ++j)
{
for (difference_t k = j - i; k >= 0; k -= i)
{
TIterator itr1 = first;
TIterator itr2 = first;
std::advance(itr1, k);
std::advance(itr2, k + i);
if (compare(*itr2, *itr1))
{
std::iter_swap(itr1, itr2);
}
}
}
}
}
template <typename TIterator>
void sort(TIterator first, TIterator last)
{
etl::sort(first, last, std::less<typename std::iterator_traits<TIterator>::value_type>());
}
}
#endif