/*
	This file is part of Fennix Kernel.

	Fennix Kernel 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.

	Fennix Kernel 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 Fennix Kernel. If not, see <https://www.gnu.org/licenses/>.
*/

#pragma once
#include <utility>
#include <cstddef>

namespace std
{
	template <typename T>
	typename std::remove_reference<T>::type &&__algo_move(T &&arg)
	{
		return static_cast<typename std::remove_reference<T>::type &&>(arg);
	}

	template <typename InputIt, typename OutputIt>
	OutputIt copy(InputIt first, InputIt last, OutputIt result)
	{
		while (first != last)
		{
			*result = *first;
			++result;
			++first;
		}
		return result;
	}

	template <class BidirIt1, class BidirIt2>
	BidirIt2 copy_backward(BidirIt1 first, BidirIt1 last, BidirIt2 d_last)
	{
		while (first != last)
		{
			*(--d_last) = *(--last);
		}
		return d_last;
	}

	template <typename InputIt, typename OutputIt, typename UnaryOperation>
	OutputIt transform(InputIt first, InputIt last, OutputIt result, UnaryOperation op)
	{
		while (first != last)
		{
			*result = op(*first);
			++first;
			++result;
		}
		return result;
	};

	template <class T>
	void swap(T &a, T &b) noexcept(std::is_nothrow_move_constructible<T>::value && std::is_nothrow_move_assignable<T>::value)
	{
		T temp = __algo_move(a);
		a = __algo_move(b);
		b = __algo_move(temp);
	}

	template <class T2, std::size_t N>
	void swap(T2 (&a)[N], T2 (&b)[N]) noexcept(std::is_nothrow_swappable_v<T2>)
	{
		for (std::size_t i = 0; i < N; ++i)
			std::swap(a[i], b[i]);
	}

	template <typename T>
	constexpr const T &min(const T &a, const T &b)
	{
		return (a < b) ? a : b;
	}

	template <typename T>
	constexpr const T &max(const T &a, const T &b)
	{
		return (a > b) ? a : b;
	}

	template <typename T>
	constexpr const T &clamp(const T &v, const T &lo, const T &hi)
	{
		return std::max(lo, std::min(v, hi));
	}

	template <class T, class Compare>
	constexpr const T &clamp(const T &v, const T &lo, const T &hi, Compare comp)
	{
		return comp(v, lo) ? lo : comp(hi, v) ? hi
											  : v;
	}

	template <class ForwardIt1, class ForwardIt2>
	ForwardIt1 search(ForwardIt1 first, ForwardIt1 last,
					  ForwardIt2 s_first, ForwardIt2 s_last)
	{
		for (; first != last; ++first)
		{
			ForwardIt1 it = first;
			for (ForwardIt2 s_it = s_first;; ++it, ++s_it)
			{
				if (s_it == s_last)
					return first;
				if (it == last)
					return last;
				if (!(*it == *s_it))
					break;
			}
		}
		return last;
	}

	template <class InputIt, class T>
	constexpr InputIt find(InputIt first, InputIt last, const T &value)
	{
		for (; first != last; ++first)
			if (*first == value)
				return first;

		return last;
	}

	template <class InputIt, class UnaryPred>
	constexpr InputIt find_if(InputIt first, InputIt last, UnaryPred p)
	{
		for (; first != last; ++first)
			if (p(*first))
				return first;

		return last;
	}

	template <class InputIt, class UnaryPred>
	constexpr InputIt find_if_not(InputIt first, InputIt last, UnaryPred q)
	{
		for (; first != last; ++first)
			if (!q(*first))
				return first;

		return last;
	}

	template <class ForwardIt1, class ForwardIt2>
	ForwardIt1 find_end(ForwardIt1 first, ForwardIt1 last,
						ForwardIt2 s_first, ForwardIt2 s_last)
	{
		if (s_first == s_last)
			return last;
		ForwardIt1 result = last;
		while (true)
		{
			ForwardIt1 new_result = std::search(first, last, s_first, s_last);
			if (new_result == last)
				return result;
			result = new_result;
			first = new_result;
			++first;
		}
	}

	template <class InputIt, class ForwardIt>
	InputIt find_first_of(InputIt first, InputIt last,
						  ForwardIt s_first, ForwardIt s_last)
	{
		for (; first != last; ++first)
			for (ForwardIt it = s_first; it != s_last; ++it)
				if (*first == *it)
					return first;
		return last;
	}

	template <class ForwardIt, class T>
	ForwardIt remove(ForwardIt first, ForwardIt last, const T &value)
	{
		first = std::find(first, last, value);
		if (first != last)
			for (ForwardIt i = first; ++i != last;)
				if (!(*i == value))
					*first++ = __algo_move(*i);
		return first;
	}

	template <class ForwardIt, class UnaryPred>
	ForwardIt remove_if(ForwardIt first, ForwardIt last, UnaryPred p)
	{
		first = std::find_if(first, last, p);
		if (first != last)
			for (ForwardIt i = first; ++i != last;)
				if (!p(*i))
					*first++ = __algo_move(*i);
		return first;
	}

	template <class ForwardIt, class T>
	void fill(ForwardIt first, ForwardIt last, const T &value)
	{
		for (; first != last; ++first)
			*first = value;
	}

	template <class OutputIt, class Size, class T>
	OutputIt fill_n(OutputIt first, Size count, const T &value)
	{
		for (Size i = 0; i < count; ++i)
		{
			*first = value;
			++first;
		}
		return first;
	}

	template <class InputIt1, class InputIt2>
	constexpr bool equal(InputIt1 first1, InputIt1 last1, InputIt2 first2)
	{
		while (first1 != last1)
		{
			if (!(*first1 == *first2))
				return false;

			++first1;
			++first2;
		}
		return true;
	}

	template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2>
	bool equal(ExecutionPolicy &&policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2)
	{
		while (first1 != last1)
		{
			if (!(*first1 == *first2))
				return false;

			++first1;
			++first2;
		}
		return true;
	}

	template <class InputIt1, class InputIt2, class BinaryPred>
	constexpr bool equal(InputIt1 first1, InputIt1 last1, InputIt2 first2, BinaryPred p)
	{
		while (first1 != last1)
		{
			if (!p(*first1, *first2))
				return false;

			++first1;
			++first2;
		}
		return true;
	}

	template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryPred>
	bool equal(ExecutionPolicy &&policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, BinaryPred p)
	{
		while (first1 != last1)
		{
			if (!p(*first1, *first2))
				return false;

			++first1;
			++first2;
		}
		return true;
	}

	template <class InputIt1, class InputIt2>
	constexpr bool equal(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2)
	{
		while (first1 != last1)
		{
			if (!(*first1 == *first2))
				return false;

			++first1;
			++first2;
		}
		return true;
	}

	template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2>
	bool equal(ExecutionPolicy &&policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2)
	{
		while (first1 != last1)
		{
			if (!(*first1 == *first2))
				return false;

			++first1;
			++first2;
		}
		return true;
	}

	template <class InputIt1, class InputIt2, class BinaryPred>
	constexpr bool equal(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, BinaryPred p)
	{
		while (first1 != last1)
		{
			if (!p(*first1, *first2))
				return false;

			++first1;
			++first2;
		}
		return true;
	}

	template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryPred>
	bool equal(ExecutionPolicy &&policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, BinaryPred p)
	{
		while (first1 != last1)
		{
			if (!p(*first1, *first2))
				return false;

			++first1;
			++first2;
		}
		return true;
	}

	template <class RandomIt>
	constexpr void sort(RandomIt first, RandomIt last)
	{
		if (first == last)
			return;

		for (RandomIt i = first; i != last; ++i)
		{
			for (RandomIt j = i + 1; j != last; ++j)
			{
				if (*j < *i)
					std::swap(*i, *j);
			}
		}
	}

	template <class ExecutionPolicy, class RandomIt>
	void sort(ExecutionPolicy &&policy, RandomIt first, RandomIt last);

	template <class RandomIt, class Compare>
	constexpr void sort(RandomIt first, RandomIt last, Compare comp)
	{
		if (first == last)
			return;

		for (RandomIt i = first; i != last; ++i)
		{
			for (RandomIt j = i + 1; j != last; ++j)
			{
				if (comp(*j, *i))
					std::swap(*i, *j);
			}
		}
	}

	template <class ExecutionPolicy, class RandomIt, class Compare>
	void sort(ExecutionPolicy &&policy, RandomIt first, RandomIt last, Compare comp);

	template <class InputIt1, class InputIt2>
	constexpr bool lexicographical_compare(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2)
	{
		for (; (first1 != last1) && (first2 != last2); ++first1, (void)++first2)
		{
			if (*first1 < *first2)
				return true;
			if (*first2 < *first1)
				return false;
		}

		return (first1 == last1) && (first2 != last2);
	}

	template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2>
	bool lexicographical_compare(ExecutionPolicy &&policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2);

	template <class InputIt1, class InputIt2, class Compare>
	constexpr bool lexicographical_compare(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, Compare comp)
	{
		for (; (first1 != last1) && (first2 != last2); ++first1, (void)++first2)
		{
			if (comp(*first1, *first2))
				return true;
			if (comp(*first2, *first1))
				return false;
		}

		return (first1 == last1) && (first2 != last2);
	}

	template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class Compare>
	bool lexicographical_compare(ExecutionPolicy &&policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, Compare comp);

	template <class InputIt1, class InputIt2, class Cmp>
	constexpr auto lexicographical_compare_three_way(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, Cmp comp) -> decltype(comp(*first1, *first2));

	template <class InputIt1, class InputIt2>
	constexpr auto lexicographical_compare_three_way(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2);
}