#pragma once
#include "prelude.hpp"
#include <iostream>
#include <functional>

template <std::bidirectional_iterator I, std::sentinel_for<I> S,
	class Proj = std::identity,
	std::indirect_unary_predicate<std::projected<I, Proj>> Pred>
	requires std::permutable<I>
constexpr
func gather(I f, S l, I p, Pred s, Proj proj = {}) -> ra::subrange<I>
{
	auto not1 = [](auto&& pred){
		return [pred](auto const& x) { return not pred(x); };
	};

	auto r1 = ra::stable_partition(f, p, not1(s), proj);
	auto r2 = ra::stable_partition(p, l, s, proj);
	return { r1.begin(), r2.end() };
}

template <std::permutable I, std::sentinel_for<I> S>
constexpr
func slide(I f, S l, I p) -> ra::subrange<I>
{
	if (p > l) return ra::rotate(f, l, p);
	if (p < f) return ra::rotate(p, f, l);
	return { f, l };
}

template <std::permutable I, std::sentinel_for<I> S>
[[nodiscard]] constexpr
func intercalate(I f1, S l1, I f2, S l2) -> std::vector<typename std::iterator_traits<I>::value_type>
{
	using T = typename std::iterator_traits<I>::value_type;
	auto make_pair = [](T x, T y) { return std::make_pair(x, y); };
	auto concat = [](std::vector<T> vec, std::pair<T, T> e) { vec.push_back(e.first), vec.push_back(e.second); return vec; };

	std::vector<T> out;
	auto const s1 = std::distance(f1, l1);
	auto const s2 = std::distance(f2, l2);

	if (s1 > s2) return std::inner_product(f1, f1 + s2, f2, out, concat, make_pair);
	return std::inner_product(f1, l1, f2, out, concat, make_pair);
}

template <std::permutable I, std::sentinel_for<I> S>
func minimum_subsequence(I f, S l, )

void print(auto const& x, std::string sep)
{
	std::cout << x << sep;
}

void print_range(auto const& r)
{
	for (let& e : r) print(e, " ");
}