/*
 * algorithm.hpp
 *
 * This file is part of Algorithms library toolkit.
 * Copyright (C) 2017 Jan Travnicek (jan.travnicek@fit.cvut.cz)

 * Algorithms library toolkit is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.

 * Algorithms library toolkit is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.

 * You should have received a copy of the GNU General Public License
 * along with Algorithms library toolkit.  If not, see <http://www.gnu.org/licenses/>.
 *
 * Created on: May 28, 2015
 * Author: Jan Travnicek
 */

#ifndef __ALGORITHM_HPP_
#define __ALGORITHM_HPP_

#include <algorithm>
#include <functional>

namespace ext {

/**
 * \brief
 * Tests two sorted ranges wheter all elements from the second are not present in the first.
 *
 * Complexity linear in minimum of sizes of the two ranges.
 *
 * \param first1 the begining of the first range
 * \param first2 the end of the first range
 * \param second1 the begining of the second range
 * \param second2 the end of the second range
 * \param comp the comparator of range elements
 *
 * \return true if all elements from second range are not in the first, false othervise
 */
template<class InputIt1, class InputIt2, class Compare>
bool excludes(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, Compare comp) {
	while (first2 != last2 && first1 != last1) {
		if (comp(*first2, *first1)) {
			++first2;
		} else if (comp(*first1, *first2)) {
			++first1;
		} else {
			return false;
		}
	}
	return true;
}

/**
 * \brief
 * Tests two sorted ranges wheter all elements from the second are not present in the first.
 *
 * Complexity linear in minimum of sizes of the two ranges.
 *
 * The elements of the ranges are compared by the default less operator
 *
 * \param first1 the begining of the first range
 * \param first2 the end of the first range
 * \param second1 the begining of the second range
 * \param second2 the end of the second range
 *
 * \tparam ImputIt1 type of the first iterator
 * \tparam ImputIt2 type of the second iterator
 *
 * \return true if all elements from second range are not in the first, false othervise
 */
template<class InputIt1, class InputIt2>
bool excludes(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2) {
	return excludes(first1, last1, first2, last2, std::less<decltype(*first1)>());
}

/**
 * \brief
 * Constructs sorted ranges beginning in the location pointed by result1 and result2 with the set differences of the two sorted ranges [first1,last1) and [first2,last2).
 *
 * The symmetric difference of two sets is formed by the elements that are present in one of the sets, but not in the other. The result1 and result2 are each representing half of the symmetric difference, i.e. each being a set difference of the first range to the second and of the second range to the first. Among the equivalent elements in each range, those discarded are those that appear before in the existent order before the call. The existing order is also preserved for the copied elements.
 *
 * The elements are compared using comp callback. Two elements, a and b are considered equivalent if (!comp(a,b) && !comp(b,a)).
 *
 * The elements in the ranges shall already be ordered according to this same criterion (operator< or comp). The resulting range is also sorted according to this.
 */
template < class InputIterator1, class InputIterator2, class OutputIterator1, class OutputIterator2, class Compare >
void set_symmetric_difference ( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator1 result1, OutputIterator2 result2, Compare comp ) {
	while ( first1 != last1 && first2 != last2 ) {
		if ( comp ( * first1, * first2 ) ) {
			* result1 = * first1;
			++ result1;
			++ first1;
		} else if ( comp ( * first2, * first1 ) ) {
			* result2 = * first2;
			++ result2;
			++ first2;
		} else {
			++first1;
			++first2;
		}
	}

	if ( first1 == last1 ) {
		std::copy ( first2, last2, result2 );
	}
	if ( first2 == last2 ) {
		std::copy ( first1, last1, result1 );
	}
}

/**
 * \brief
 * Constructs sorted ranges beginning in the location pointed by result1 and result2 with the set differences of the two sorted ranges [first1,last1) and [first2,last2).
 *
 * The symmetric difference of two sets is formed by the elements that are present in one of the sets, but not in the other. The result1 and result2 are each representing half of the symmetric difference, i.e. each being a set difference of the first range to the second and of the second range to the first. Among the equivalent elements in each range, those discarded are those that appear before in the existent order before the call. The existing order is also preserved for the copied elements.
 *
 * The elements are compared using operator <. Two elements, a and b are considered equivalent if (!(a<b) && !(b<a)).
 *
 * The elements in the ranges shall already be ordered according to this same criterion (operator< or comp). The resulting range is also sorted according to this.
 */
template < class InputIterator1, class InputIterator2, class OutputIterator1, class OutputIterator2 >
void set_symmetric_difference ( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator1 result1, OutputIterator2 result2 ) {
	set_symmetric_difference ( first1, last1, first2, last2, result1, result2, std::less < decltype ( * first1 ) > ( ) );
}

/**
 * \brief
 * In container tranformation of all elements according to the \p tranform.
 *
 * \param in the input container
 * \param transform the callback
 *
 * \tparam ResType the result of the transformation
 * \tparam InType the type of original element
 * \tparam Ts ... additional types of the in container
 * \tparam ContainerType the template parameter of the container
 * \tparam Callback the type of the transformation callback
 *
 * The function needs redesign. Ranges and output iterator should be used instead of container construction.
 *
 * \return a new container with transformed elements
 */
template < class ResType, class InType, typename ... Ts, template < typename ... > class ContainerType, class Callback >
ContainerType < ResType > transform(const ContainerType < InType, Ts ... > & in, Callback transform ) {
	ContainerType<ResType> res;
	std::transform ( in.begin ( ), in.end ( ), std::inserter ( res, res.begin ( ) ), transform );
	return res;
}

/**
 * \brief
 * Linear version of search in a range of values.
 *
 * \param first the beginning of the range
 * \param second the end of the range
 * \param elem the searched element
 *
 * \tparam InputIt the type of the iterator
 * \tparam Element the type of the searched element
 *
 * \return true if the elem is inside the range (first, second], false othervise
 */
template<class InputIt, class Element>
bool contains(InputIt first, InputIt last, const Element& elem) {
	return find(first, last, elem) != last;
}

/**
 * \brief
 * Logaritmic version of search in a range of sorted values.
 *
 * \param first the beginning of the range
 * \param second the end of the range
 * \param elem the searched element
 *
 * \tparam InputIt the type of the iterator
 * \tparam Element the type of the searched element
 *
 * \return true if the elem is inside the range (first, second], false othervise
 */
template<class InputIt, class Element>
bool binary_contains(InputIt first, InputIt last, const Element& elem) {
	return binary_search(first, last, elem) != last;
}

// TODO repace in c++17 with fold expressions
template < class ... Ts >
inline bool andAll ( Ts ... );

template < >
inline bool andAll ( ) {
	return true;
}

template < class T, class ... Ts >
inline bool andAll ( T value, Ts ... other ) {
	return value && andAll ( other ... );
}

// TODO repace in c++17 with fold expressions
template < class ... Ts >
inline bool orAll ( Ts ... );

template < >
inline bool orAll ( ) {
	return false;
}

template < class T, class ... Ts >
inline bool orAll ( T value, Ts ... other ) {
	return value || orAll ( other ... );
}

/**
 * \brief
 * Function to locate pair of iterators (openPos, closePos), i.e. both openPos and closePos are included in the range, where * openPos == \p open and closePos == \p closePos, or openPos = closePos = begin if no range can be found.
 *
 * The found range either does not contain nested range or the range it contains is recursively satisfying this definition.
 *
 * In order for the function to find all ranges satisfying the above condition, the range (begin, end] must contain corretly nested ranges delimited by \p open and \p close.
 *
 * \param begin the begining of the examined range
 * \param end the end of the examined range
 * \param open the opening parenthesis
 * \param end the value of closing parenthesis
 *
 * \tparam Iterator the type of range denoting iterator
 * \tparam Value the type of open and close delimiters
 */
template < class Iterator, class Value >
std::pair < Iterator, Iterator > __find_range ( Iterator begin, Iterator end, const Value & open, const Value & close ) {
	for ( ; begin != end && * begin != open && * begin != close ; ++ begin );

	if ( begin == end || * begin == close )
		return std::make_pair ( begin, begin );

	Iterator openPos = begin;

	for ( ; ; ) {
		std::pair < Iterator, Iterator > subRange = __find_range ( begin + 1, end, open, close );
		if ( subRange.first == subRange.second )
			break;
		begin = subRange.second;
	}

	if ( begin == end )
		return std::make_pair ( begin, begin );

	++ begin;

	for ( ; begin != end && * begin != close ; ++ begin );

	if ( begin == end )
		return std::make_pair ( begin, begin );

	Iterator closePos = begin;

	return std::make_pair ( openPos, closePos );
}

/**
 * \brief
 * Function to locate pair of iterators (openPos, closePos] where * openPos == \p open and closePos == \p closePos, or openPos = closePos = begin if no range can be found.
 *
 * The found range either does not contain nested range or the range it contains is recursively satisfying this definition.
 *
 * In order for the function to find all ranges satisfying the above condition, the range (begin, end] must contain corretly nested ranges delimited by \p open and \p close.
 *
 * \param begin the begining of the examined range
 * \param end the end of the examined range
 * \param open the opening parenthesis
 * \param end the value of closing parenthesis
 *
 * \tparam Iterator the type of range denoting iterator
 * \tparam Value the type of open and close delimiters
 */
template < class Iterator, class Value >
std::pair < Iterator, Iterator > find_range ( Iterator begin, Iterator end, const Value & open, const Value & close ) {
	std::pair < Iterator, Iterator > res = __find_range ( begin, end, open, close );

	if ( res.first == res.second )
		return res;

	++ res.second;

	return res;
}

/**
 * \brief
 * Root case of maximum computation. The maximum from one value is the value itself.
 *
 * \param a the value to compute maximum from
 *
 * \tparam T the type of the value to compute maximum from
 *
 * \return the value a
 */
template < typename T >
constexpr const T & max ( const T & a ) {
	return a;
}

/**
 * \brief
 * Root case of maximum computation. The maximum from one value is the value itself.
 *
 * \param a the first value to compute maximum from
 * \param b the second value to compute maximum from
 * \param args ... the other values to compute maximum from
 *
 * \tparam T the type of the values to compute maximum from
 * \tparam Args ... type of other values not yet processed here. Technically these types should be same as T
 *
 * \return the maximum from all values a, b, args ...
 */
template < typename T, typename ... Args >
constexpr const T & max ( const T & a, const T & b, const Args & ... args ) {
	return max ( b < a ? a : b, args ... );
}

/**
 * Root case of minimum computation. The minimum from one value is the value itself.
 *
 * \param a the value to compute minimum from
 *
 * \tparam T the type of the value to compute minimum from
 *
 * \return the value a
 */
template < typename T >
constexpr const T & min ( const T & a) {
	return a;
}

/**
 * \brief
 * Root case of minimum computation. The minimum from one value is the value itself.
 *
 * \param a the first value to compute minimum from
 * \param b the second value to compute minimum from
 * \param args ... the other values to compute minimum from
 *
 * \tparam T the type of the values to compute minimum from
 * \tparam Args ... type of other values not yet processed here. Technically these types should be same as T
 *
 * \return the minimum from all values a, b, args ...
 */
template < typename T, typename ... Args >
constexpr const T & min ( const T & a, const T & b, const Args & ... args) {
	return min ( b > a ? a : b, args ... );
}

/**
 * \brief
 * Internal function of standard library.
 */
template < typename _ForwardIterator, typename _BinaryPredicate >
_ForwardIterator __adjacent_find ( _ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __binary_pred ) {
	if (__first == __last)
		return __last;
	_ForwardIterator __next = __first;
	while (++__next != __last) {
		if ( __binary_pred( * __first, * __next ) )
			return __first;
		__first = __next;
	}
	return __last;
}

/**
 * \brief
 * Internal function of standard library tuned to handle swapping of pointers.
 */
template < typename _ForwardIterator, typename _BinaryPredicate >
_ForwardIterator __unique ( _ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __binary_pred ) {
	// Skip the beginning, if already unique.
	__first = ext::__adjacent_find ( __first, __last, __binary_pred );
	if ( __first == __last )
		return __last;

	// Do the real copy work.
	_ForwardIterator __dest = __first;
	++ __first;
	while ( ++__first != __last )
		if ( ! __binary_pred ( * __dest, * __first ) )
			std::swap ( * ++__dest, * __first );
	return ++ __dest;
}

/**
 *  @brief Shuffles values in a sequece so that consecutive duplicate values are pushed to the front and others to the back.
 *  @ingroup mutating_algorithms
 *  @param  __first  A forward iterator.
 *  @param  __last   A forward iterator.
 *  @return  An iterator designating the end of the resulting sequence.
 *
 *  All but the first element from each group of consecutive
 *  values that compare equal are pushed to the end of the sequence.
 *  unique() is stable, so the relative order of elements that are
 *  not pushed to the end is unchanged.
 *  Elements between the end of the resulting sequence and @p __last
 *  are still present, but their order is unspecified.
*/
template < typename _ForwardIterator >
inline _ForwardIterator unique ( _ForwardIterator __first, _ForwardIterator __last ) {
	return ext::__unique(__first, __last, [] ( const auto & a, const auto & b ) { return a == b; } );
}

/**
 *  @brief Shuffles values in a sequece so that consecutive duplicate values are pushed to the front and others to the back.
 *  @ingroup mutating_algorithms
 *  @param  __first  A forward iterator.
 *  @param  __last   A forward iterator.
 *  @param  __binary_pred  A binary predicate.
 *  @return  An iterator designating the end of the resulting sequence.
 *
 *  All but the first element from each group of consecutive
 *  values for which @p __binary_pred returns true are pushed to the end of the sequence.
 *  unique() is stable, so the relative order of elements that are
 *  not pushed to the end is unchanged.
 *  Elements between the end of the resulting sequence and @p __last
 *  are still present, but their order is unspecified.
*/
template < typename _ForwardIterator, typename _BinaryPredicate >
inline _ForwardIterator unique ( _ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __binary_pred ) {
	return ext::__unique(__first, __last, __binary_pred );
}

} /* namespace ext */

#endif /* __ALGORITHM_HPP_ */