#ifndef ETL_STL_ALTERNATE_ALGORITHM_INCLUDED
#define ETL_STL_ALTERNATE_ALGORITHM_INCLUDED
#include "../../platform.h"
#include <string.h>
#include "../../type_traits.h"
#include "iterator.h"
#include "functional.h"
#include "utility.h"
#if defined(ETL_IN_UNIT_TEST)
#if !defined(ETLSTD)
#define ETLSTD etlstd
#endif
namespace etlstd
#else
#if !defined(ETLSTD)
#define ETLSTD std
#endif
namespace std
#endif
{
template <typename TIterator, typename TDistance>
typename etl::enable_if<!etl::is_same<typename ETLSTD::iterator_traits<TIterator>::iterator_tag, ETLSTD::random_access_iterator_tag>::value, void>::type
advance(TIterator itr, TDistance distance)
{
while (distance-- != 0)
{
++itr;
}
}
template <typename TIterator, typename TDistance>
typename etl::enable_if<etl::is_same<typename ETLSTD::iterator_traits<TIterator>::iterator_tag, ETLSTD::random_access_iterator_tag>::value, void>::type
advance(TIterator itr, TDistance distance)
{
return itr += distance;
}
template <typename TIterator1, typename TIterator2>
typename etl::enable_if<etl::is_pointer<TIterator1>::value &&
etl::is_pointer<TIterator2>::value &&
etl::is_pod<typename ETLSTD::iterator_traits<TIterator1>::value_type>::value, TIterator2>::type
copy(TIterator1 sb, TIterator1 se, TIterator2 db)
{
typedef typename ETLSTD::iterator_traits<TIterator1>::value_type value_t;
return TIterator2(memcpy(db, sb, sizeof(value_t) * (se - sb)));
}
template <typename TIterator1, typename TIterator2>
typename etl::enable_if<!etl::is_pointer<TIterator1>::value ||
!etl::is_pointer<TIterator2>::value ||
!etl::is_pod<typename ETLSTD::iterator_traits<TIterator1>::value_type>::value, TIterator2>::type
copy(TIterator1 sb, TIterator1 se, TIterator2 db)
{
while (sb != se)
{
*db++ = *sb++;
}
return db;
}
template <typename TIterator1, typename TSize, typename TIterator2>
typename etl::enable_if<etl::is_pointer<TIterator1>::value &&
etl::is_pointer<TIterator2>::value &&
etl::is_pod<typename ETLSTD::iterator_traits<TIterator1>::value_type>::value, TIterator2>::type
copy_n(TIterator1 sb, TSize count, TIterator2 db)
{
typedef typename ETLSTD::iterator_traits<TIterator1>::value_type value_t;
return TIterator2(memcpy(db, sb, sizeof(value_t) * count));
}
template <typename TIterator1, typename TSize, typename TIterator2>
typename etl::enable_if<!etl::is_pointer<TIterator1>::value ||
!etl::is_pointer<TIterator2>::value ||
!etl::is_pod<typename ETLSTD::iterator_traits<TIterator1>::value_type>::value, TIterator2>::type
copy_n(TIterator1 sb, TSize count, TIterator2 db)
{
while (count != 0)
{
*db++ = *sb++;
--count;
}
return db;
}
template <typename TIterator1, typename TIterator2>
typename etl::enable_if<etl::is_pointer<TIterator1>::value &&
etl::is_pointer<TIterator2>::value &&
etl::is_pod<typename ETLSTD::iterator_traits<TIterator1>::value_type>::value, TIterator2>::type
copy_backward(TIterator1 sb, TIterator1 se, TIterator2 de)
{
typedef typename ETLSTD::iterator_traits<TIterator1>::value_type value_t;
const size_t length = (se - sb);
return TIterator2(memmove(de - length, sb, sizeof(value_t) * length));
}
template <typename TIterator1, typename TIterator2>
typename etl::enable_if<!etl::is_pointer<TIterator1>::value ||
!etl::is_pointer<TIterator2>::value ||
!etl::is_pod<typename ETLSTD::iterator_traits<TIterator1>::value_type>::value, TIterator2>::type
copy_backward(TIterator1 sb, TIterator1 se, TIterator2 de)
{
while (se != sb)
{
*(--de) = *(--se);
}
return de;
}
template <typename TIterator1, typename TIterator2>
TIterator2 move(TIterator1 sb, TIterator1 se, TIterator2 db)
{
while (sb != se)
{
*db++ = std::move(*sb++);
}
return db;
}
template <typename TIterator1, typename TIterator2>
TIterator2 move_backward(TIterator1 sb, TIterator1 se, TIterator2 de)
{
while (sb != se)
{
*(--de) = std::move(*(--se));
}
return de;
}
template<typename TIterator, typename TValue, typename TCompare>
TIterator lower_bound(TIterator first, TIterator last, const TValue& value, TCompare compare)
{
typedef typename ETLSTD::iterator_traits<TIterator>::difference_type difference_t;
difference_t count = ETLSTD::distance(first, last);
while (count > 0)
{
TIterator itr = first;
difference_t step = count / 2;
ETLSTD::advance(itr, step);
if (compare(*itr, value))
{
first = ++itr;
count -= step + 1;
}
else
{
count = step;
}
}
return first;
}
template<typename TIterator, typename TValue>
TIterator lower_bound(TIterator first, TIterator last, const TValue& value)
{
typedef ETLSTD::less<typename ETLSTD::iterator_traits<TIterator>::value_type> compare;
return ETLSTD::lower_bound(first, last, value, compare());
}
template<typename TIterator, typename TValue, typename TCompare>
TIterator upper_bound(TIterator first, TIterator last, const TValue& value, TCompare compare)
{
typedef typename ETLSTD::iterator_traits<TIterator>::difference_type difference_t;
difference_t count = ETLSTD::distance(first, last);
while (count > 0)
{
TIterator itr = first;
difference_t step = count / 2;
ETLSTD::advance(itr, step);
if (!compare(value, *itr))
{
first = ++itr;
count -= step + 1;
}
else
{
count = step;
}
}
return first;
}
template<typename TIterator, typename TValue>
TIterator upper_bound(TIterator first, TIterator last, const TValue& value)
{
typedef ETLSTD::less<typename ETLSTD::iterator_traits<TIterator>::value_type> compare;
return ETLSTD::upper_bound(first, last, value, compare());
}
template<typename TIterator, typename TValue, typename TCompare>
ETLSTD::pair <TIterator, TIterator> equal_range(TIterator first, TIterator last, const TValue& value, TCompare compare)
{
return ETLSTD::make_pair(ETLSTD::lower_bound(first, last, value, compare),
ETLSTD::upper_bound(first, last, value, compare));
}
template<typename TIterator, typename TValue>
ETLSTD::pair<TIterator, TIterator> equal_range(TIterator first, TIterator last, const TValue& value)
{
typedef ETLSTD::less<typename ETLSTD::iterator_traits<TIterator>::value_type> compare;
return ETLSTD::make_pair(ETLSTD::lower_bound(first, last, value, compare()),
ETLSTD::upper_bound(first, last, value, compare()));
}
template <typename TIterator, typename TUnaryPredicate>
TIterator find_if(TIterator first, TIterator last, TUnaryPredicate predicate)
{
while (first != last)
{
if (predicate(*first))
{
return first;
}
++first;
}
return last;
}
template <typename TIterator, typename T>
TIterator find(TIterator first, TIterator last, const T& value)
{
while (first != last)
{
if (*first == value)
{
return first;
}
++first;
}
return last;
}
template<typename TIterator, typename TValue>
typename etl::enable_if<!(etl::is_same<char, TValue>::value || etl::is_same<unsigned char, TValue>::value) || !etl::is_pointer<TIterator>::value, void>::type
fill(TIterator first, TIterator last, const TValue& value)
{
while (first != last)
{
*first++ = value;
}
}
template<typename TIterator, typename TValue>
typename etl::enable_if<(etl::is_same<char, TValue>::value || etl::is_same<unsigned char, TValue>::value) && etl::is_pointer<TIterator>::value, void>::type
fill(TIterator first, TIterator last, const TValue& value)
{
memset(first, value, last - first);
}
template<typename TIterator, typename TSize, typename TValue>
typename etl::enable_if<!(etl::is_same<char, TValue>::value || etl::is_same<unsigned char, TValue>::value) || !etl::is_pointer<TIterator>::value, TIterator>::type
fill_n(TIterator first, TSize count, const TValue& value)
{
for (TSize i = 0; i < count; ++i)
{
*first++ = value;
}
return first;
}
template<typename TIterator, typename TSize, typename TValue>
typename etl::enable_if<(etl::is_same<char, TValue>::value || etl::is_same<unsigned char, TValue>::value) && etl::is_pointer<TIterator>::value, void>::type
fill_n(TIterator first, TSize count, const TValue& value)
{
memset(first, value, count);
}
template <typename TIterator, typename T>
typename iterator_traits<TIterator>::difference_type count(TIterator first, TIterator last, const T& value)
{
typename iterator_traits<TIterator>::difference_type n = 0;
while (first != last)
{
if (*first == value)
{
++n;
}
++first;
}
return n;
}
template <typename TIterator, typename TUnaryPredicate>
typename iterator_traits<TIterator>::difference_type count_if(TIterator first, TIterator last, TUnaryPredicate predicate)
{
typename iterator_traits<TIterator>::difference_type n = 0;
while (first != last)
{
if (predicate(*first))
{
++n;
}
++first;
}
return n;
}
template <typename T>
void swap(T& a, T& b)
{
T c = a;
a = b;
b = c;
}
template <typename TIterator1, typename TIterator2>
void iter_swap(TIterator1 a, TIterator2 b)
{
typename ETLSTD::iterator_traits<TIterator1>::value_type c = *a;
*a = *b;
*b = c;
}
template <typename TIterator1, typename TIterator2>
typename etl::enable_if<!etl::is_pointer<TIterator1>::value || !etl::is_pointer<TIterator2>::value || !etl::is_pod<typename ETLSTD::iterator_traits<TIterator1>::value_type>::value, bool>::type
equal(TIterator1 first1, TIterator1 last1, TIterator2 first2)
{
while (first1 != last1)
{
if (*first1++ != *first2++)
{
return false;
}
}
return true;
}
template <typename TIterator1, typename TIterator2>
typename etl::enable_if<etl::is_pointer<TIterator1>::value && etl::is_pointer<TIterator2>::value && etl::is_pod<typename ETLSTD::iterator_traits<TIterator1>::value_type>::value, bool>::type
equal(TIterator1 first1, TIterator1 last1, TIterator2 first2)
{
typedef typename ETLSTD::iterator_traits<TIterator1>::value_type value_t;
return (memcmp(first1, first2, sizeof(value_t) * (last1 - last1)) == 0);
}
template <typename TIterator1, typename TIterator2, typename TCompare>
bool lexicographical_compare(TIterator1 first1, TIterator1 last1,
TIterator2 first2, TIterator2 last2,
TCompare compare)
{
while ((first1 != last1) && (first2 != last2))
{
if (compare(*first1, *first2))
{
return true;
}
if (compare(*first2, *first1))
{
return false;
}
++first1;
++first2;
}
return (first1 == last1) && (first2 != last2);
}
template <typename TIterator1, typename TIterator2>
bool lexicographical_compare(TIterator1 first1, TIterator1 last1,
TIterator2 first2, TIterator2 last2)
{
typedef ETLSTD::less<typename ETLSTD::iterator_traits<TIterator1>::value_type> compare;
return ETLSTD::lexicographical_compare(first1, last1, first2, last2, compare());
}
template <typename T, typename TCompare>
const T& min(const T& a, const T& b, TCompare compare)
{
return (compare(a, b)) ? a : b;
}
template <typename T>
const T& min(const T& a, const T& b)
{
typedef ETLSTD::less<T> compare;
return ETLSTD::min(a, b, compare());
}
template <typename T, typename TCompare>
const T& max(const T& a, const T& b, TCompare compare)
{
return (compare(a, b)) ? b : a;
}
template <typename T>
const T& max(const T& a, const T& b)
{
typedef ETLSTD::less<T> compare;
return ETLSTD::max(a, b, compare());
}
template <typename TIteratorIn, typename TIteratorOut, typename TUnaryOperation>
TIteratorOut transform(TIteratorIn first1, TIteratorIn last1, TIteratorOut d_first, TUnaryOperation unary_operation)
{
while (first1 != last1)
{
*d_first++ = unary_operation(*first1++);
}
return d_first;
}
template <typename TIteratorIn1, typename TIteratorIn2, typename TIteratorOut, typename TBinaryOperation>
TIteratorOut transform(TIteratorIn1 first1, TIteratorIn1 last1, TIteratorIn2 first2, TIteratorOut d_first, TBinaryOperation binary_operation)
{
while (first1 != last1)
{
*d_first++ = binary_operation(*first1++, *first2++);
}
return d_first;
}
namespace private_heap
{
template <typename TIterator, typename TDistance, typename TValue, typename TCompare>
void push_heap(TIterator first, TDistance value_index, TDistance top_index, TValue value, TCompare compare)
{
TDistance parent = (value_index - 1) / 2;
while ((value_index > top_index) && compare(first[parent], value))
{
first[value_index] = first[parent];
value_index = parent;
parent = (value_index - 1) / 2;
}
first[value_index] = value;
}
template <typename TIterator, typename TDistance, typename TValue, typename TCompare>
void adjust_heap(TIterator first, TDistance value_index, TDistance length, TValue value, TCompare compare)
{
TDistance top_index = value_index;
TDistance child2nd = (2 * value_index) + 2;
while (child2nd < length)
{
if (compare(first[child2nd], first[child2nd - 1]))
{
child2nd--;
}
first[value_index] = first[child2nd];
value_index = child2nd;
child2nd = 2 * (child2nd + 1);
}
if (child2nd == length)
{
first[value_index] = first[child2nd - 1];
value_index = child2nd - 1;
}
push_heap(first, value_index, top_index, value, compare);
}
template <typename TIterator, typename TDistance, typename TCompare>
bool is_heap(const TIterator first, const TDistance n, TCompare compare)
{
TDistance parent = 0;
for (TDistance child = 1; child < n; ++child)
{
if (compare(first[parent], first[child]))
{
return false;
}
if ((child & 1) == 0)
{
++parent;
}
}
return true;
}
}
template <typename TIterator, typename TCompare>
void pop_heap(TIterator first, TIterator last, TCompare compare)
{
typedef typename ETLSTD::iterator_traits<TIterator>::value_type value_t;
typedef typename ETLSTD::iterator_traits<TIterator>::difference_type distance_t;
value_t value = last[-1];
last[-1] = first[0];
private_heap::adjust_heap(first, distance_t(0), distance_t(last - first - 1), value, compare);
}
template <typename TIterator>
void pop_heap(TIterator first, TIterator last)
{
typedef ETLSTD::less<typename ETLSTD::iterator_traits<TIterator>::value_type> compare;
ETLSTD::pop_heap(first, last, compare());
}
template <typename TIterator, typename TCompare>
void push_heap(TIterator first, TIterator last, TCompare compare)
{
typedef typename ETLSTD::iterator_traits<TIterator>::difference_type difference_t;
typedef typename ETLSTD::iterator_traits<TIterator>::value_type value_t;
private_heap::push_heap(first, difference_t(last - first - 1), difference_t(0), value_t(*(last - 1)), compare);
}
template <typename TIterator>
void push_heap(TIterator first, TIterator last)
{
typedef ETLSTD::less<typename ETLSTD::iterator_traits<TIterator>::value_type> compare;
ETLSTD::push_heap(first, last, compare());
}
template <typename TIterator, typename TCompare>
void make_heap(TIterator first, TIterator last, TCompare compare)
{
typedef typename ETLSTD::iterator_traits<TIterator>::difference_type difference_t;
if ((last - first) < 2)
{
return;
}
difference_t length = last - first;
difference_t parent = (length - 2) / 2;
while (true)
{
private_heap::adjust_heap(first, parent, length, *(first + parent), compare);
if (parent == 0)
{
return;
}
--parent;
}
}
template <typename TIterator>
void make_heap(TIterator first, TIterator last)
{
typedef ETLSTD::less<typename ETLSTD::iterator_traits<TIterator>::value_type> compare;
ETLSTD::make_heap(first, last, compare());
}
template <typename TIterator>
bool is_heap(TIterator first, TIterator last)
{
typedef ETLSTD::less<typename ETLSTD::iterator_traits<TIterator>::value_type> compare;
return private_heap::is_heap(first, last - first, compare());
}
template <typename TIterator, typename TCompare>
bool is_heap(TIterator first, TIterator last, TCompare compare)
{
return private_heap::is_heap(first, last - first, compare);
}
template<typename TIterator1, typename TIterator2, typename TCompare>
TIterator1 search(TIterator1 first, TIterator1 last, TIterator2 search_first, TIterator2 search_last, TCompare compare)
{
if (search_first == search_last)
{
return first;
}
while (first != last)
{
TIterator1 itr1 = first;
TIterator2 itr2 = search_first;
while (compare(*itr1,*itr2))
{
if (itr2 == search_last)
{
return first;
}
if (itr1 == last)
{
return last;
}
++itr1;
++itr2;
}
++first;
}
return last;
}
template<typename TIterator1, class TIterator2>
TIterator1 search(TIterator1 first, TIterator1 last, TIterator2 search_first, TIterator2 search_last)
{
typedef ETLSTD::equal_to<typename ETLSTD::iterator_traits<TIterator1>::value_type> compare;
return ETLSTD::search(first, last, search_first, search_last, compare());
}
}
#endif