algorithm.h

#ifndef RDESTL_ALGORITHM_H
#define RDESTL_ALGORITHM_H

#include "utility.h"
#include "int_to_type.h"
#include "iterator.h"
#include "type_traits.h"

namespace rde
{

//-----------------------------------------------------------------------------
// Modern C++ version that does constructor/copy constructor/move constructor in 1
template<typename T, typename... Args> RDE_FORCEINLINE
void construct_args(T* p, Args&&... args)
{
	::new (static_cast<void*>(p)) T(std::forward<Args>(args)...);
}

//-----------------------------------------------------------------------------
template<typename T> RDE_FORCEINLINE
void copy_construct(T* mem, const T& orig)
{
	//new (mem) T(orig);
	internal::copy_construct(mem, orig, int_to_type<has_trivial_copy<T>::value>());
}

//-----------------------------------------------------------------------------
template<typename T> RDE_FORCEINLINE
void construct(T* mem)
{
	internal::construct(mem, int_to_type<has_trivial_constructor<T>::value>());
}

//-----------------------------------------------------------------------------
template<typename T> RDE_FORCEINLINE
void destruct(T* mem)
{
	internal::destruct(mem, int_to_type<has_trivial_destructor<T>::value>());
}

//-----------------------------------------------------------------------------
template<typename T>
void copy_n(const T* first, size_t n, T* result)
{
	internal::copy_n(first, n, result, int_to_type<has_trivial_copy<T>::value>());
}

//-----------------------------------------------------------------------------
template<typename T>
void copy(const T* first, const T* last, T* result)
{
	internal::copy(first, last, result, int_to_type<has_trivial_copy<T>::value>());
}

//-----------------------------------------------------------------------------
template<typename T>
void copy_construct_n(T* first, size_t n, T* result)
{
	internal::copy_construct_n(first, n, result, int_to_type<has_trivial_copy<T>::value>());
}

//-----------------------------------------------------------------------------
// Modern C++ version that does constructor / copy constructor / move constructor in 1
template <typename T>
void move_construct_n(T* first, size_t n, T* result)
{
	internal::move_construct_n(first, n, result, int_to_type<has_trivial_copy<T>::value>());
}

//-----------------------------------------------------------------------------
template<typename T>
void move_n(const T* from, size_t n, T* result)
{
	RDE_ASSERT(from != result || n == 0);
	// Overlap?
	if (result + n >= from && result < from + n)
	{
		internal::move_n(from, n, result, int_to_type<has_trivial_copy<T>::value>());
	}
	else
	{
		internal::copy_n(from, n, result, int_to_type<has_trivial_copy<T>::value>());
	}
}

//-----------------------------------------------------------------------------
template<typename T>
inline void move(const T* first, const T* last, T* result)
{
	RDE_ASSERT(first != result || first == last);
	const size_t n = reinterpret_cast<uintptr_t>(last) - reinterpret_cast<uintptr_t>(first);
	const unsigned char* resultEnd = reinterpret_cast<const unsigned char*>(result) + n;
	if (resultEnd >= reinterpret_cast<const unsigned char*>(first) && result < last)
	{
		internal::move(first, last, result, int_to_type<has_trivial_copy<T>::value>());
	}
	else
	{
		internal::copy(first, last, result, int_to_type<has_trivial_copy<T>::value>());
	}
}

//-----------------------------------------------------------------------------
template<typename T>
void construct_n(T* first, size_t n)
{
	internal::construct_n(first, n, int_to_type<has_trivial_constructor<T>::value>());
}

//-----------------------------------------------------------------------------
template<typename T>
void destruct_n(T* first, size_t n)
{
	internal::destruct_n(first, n, int_to_type<has_trivial_destructor<T>::value>());
}

//-----------------------------------------------------------------------------
template<typename T> RDE_FORCEINLINE
void fill_n(T* first, size_t n, const T& val)
{
	//for (size_t i = 0; i < n; ++i)
	//	first[i] = val;
	// Loop unrolling with Duff's Device.
	T* last = first + n;
	switch (n & 0x7)
	{
	case 0:
		while (first != last)
		{
			*first = val; ++first;
	case 7:	*first = val; ++first;
	case 6:	*first = val; ++first;
	case 5:	*first = val; ++first;
	case 4:	*first = val; ++first;
	case 3:	*first = val; ++first;
	case 2:	*first = val; ++first;
	case 1:	*first = val; ++first;
		}
	}
}

//-----------------------------------------------------------------------------
template<typename TIter, typename TDist> inline
void distance(TIter first, TIter last, TDist& dist)
{
	internal::distance(first, last, dist, typename iterator_traits<TIter>::iterator_category());
}

//-----------------------------------------------------------------------------
template<typename TIter, typename TDist> inline
void advance(TIter& iter, TDist off)
{
	internal::advance(iter, off, typename iterator_traits<TIter>::iterator_category());
}

//-----------------------------------------------------------------------------
template<class TIter, typename T, class TPred> inline
TIter lower_bound(TIter first, TIter last, const T& val, const TPred& pred)
{
	internal::test_ordering(first, last, pred);
	ptrdiff_t dist(0);
	distance(first, last, dist);
	while (dist > 0)
	{
		const ptrdiff_t halfDist = dist >> 1;
		TIter mid = first;
		rde::advance(mid, halfDist);
		if (internal::debug_pred(pred, *mid, val))
			first = ++mid, dist -= halfDist + 1;
		else
			dist = halfDist;
	}
	return first;
}

//-----------------------------------------------------------------------------
template<class TIter, typename T, class TPred> inline
TIter upper_bound(TIter first, TIter last, const T& val, const TPred& pred)
{
	internal::test_ordering(first, last, pred);
	ptrdiff_t dist(0);
	distance(first, last, dist);
	while (dist > 0)
	{
		const ptrdiff_t halfDist = dist >> 1;
		TIter mid = first;
		advance(mid, halfDist);
		if (!internal::debug_pred(pred, val, *mid))
			first = ++mid, dist -= halfDist + 1;
		else
			dist = halfDist;
	}
	return first;
}

//-----------------------------------------------------------------------------
template<class TIter, typename T>
TIter find(TIter first, TIter last, const T& val)
{
	while (first != last)
	{
		if ((*first) == val)
			return first;
		++first;
	}
	return last;
}

//-----------------------------------------------------------------------------
template<class TIter, typename T, class TPred>
TIter find_if(TIter first, TIter last, const T& val, const TPred& pred)
{
	while (first != last)
	{
		if (pred(*first, val))
			return first;
		++first;
	}
	return last;
}

//-----------------------------------------------------------------------------
template<class TIter, typename T>
void accumulate(TIter first, TIter last, T& result)
{
	while (first != last)
	{
		result += *first;
		++first;
	}
}

//-----------------------------------------------------------------------------
template<typename T>
T abs(const T& t)
{
	return t >= T(0) ? t : -t;
}
// No branches, Hacker's Delight way.
RDE_FORCEINLINE int abs(int x)
{
	const int y = x >> 31;
	return (x ^ y) - y;
}
RDE_FORCEINLINE short abs(short x)
{
	const short y = x >> 15;
	return (x ^ y) - y;
}

//-----------------------------------------------------------------------------
template<typename T> inline
T max(const T& x, const T& y)
{
	return x > y ? x : y;
}

//-----------------------------------------------------------------------------
template<typename T> inline
T min(const T& x, const T& y)
{
	return x < y ? x : y;
}
// @TODO: determine if it REALLY is quicker than version with branches.
/*RDE_FORCEINLINE float min(float x, float y)
{
	float result;
	__asm
	{
		fld		[x]
		fld		[y]
		fcomi	st(0), st(1)
		fcmovnb	st(0), st(1)
		fstp	[result]
		fcomp
	}
	return result;
}*/

//-----------------------------------------------------------------------------
template<typename TAssignable>
void swap(TAssignable& a, TAssignable& b)
{
	TAssignable tmp(a);
	a = b;
	b = tmp;
}

} // namespace rde

//-----------------------------------------------------------------------------
#endif // #ifndef RDESTL_ALGORITHM_H