#include <chrono>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <thread>
#include <random>
#include <cstddef>
#include <algorithm>
#include <concepts>
#include <future>
#include <ranges>
#include <execution>

class Measure
{
public:
	Measure()
		: start(std::chrono::high_resolution_clock::now())
	{
	}

	~Measure()
	{
		auto end = std::chrono::high_resolution_clock::now();
		std::chrono::duration<double> delta = end - start;
		std::cout << " " << delta.count() * 1000 << " ms passed" << std::endl;
	}

	std::chrono::time_point<std::chrono::high_resolution_clock> start{};
};

template<typename Callable>
void measure(const std::string& text, Callable c)
{
	std::cout << text << ":\n";

	for(int i = 0; i < 3; ++i)
	{ // RAII timed scoped
		Measure m;
		c();
	}
}

template<typename T>
std::vector<T> get_random_vector(std::size_t size,
                                 T min = std::numeric_limits<T>::min(),
                                 T max = std::numeric_limits<T>::max())
{
	std::default_random_engine generator;
	// Randomly generate T-values from the range [min; max]
	std::uniform_int_distribution<T> distrib(min, max);

	std::vector<T> v;
	v.resize(size);
	for(auto& item : v)
	{
		item = distrib(generator);
	}

	return v;
}

std::vector<std::string> get_random_strings(std::size_t size,
                                            std::size_t length,
                                            char min, char max)
{
	std::default_random_engine generator;
	// Randomly generate T-values from the range [min; max]
	std::uniform_int_distribution<char> distrib(min, max);

	std::vector<std::string> v;
	v.resize(size);
	for(auto& str : v)
	{
		str.reserve(length);
		for(auto i = 0u; i < str.capacity(); ++i)
		{
			str += distrib(generator);
		}
	}

	return v;
}

template<typename C, typename T>
//	requires std::forward_iterator<Iter>
	requires std:: ranges::input_range<C>
//std::vector<const T*> find_all(Iter begin, Iter end, const T& key)
std::vector<const T*> find_all(const C& c, const T& key)
{
	std::vector<const T*> res{};
	std::for_each(std::execution::seq,
	              c.begin(), c.end(),
	              [&key, &res](const T& value)
	              {
		              if(value == key)
		              {
			              res.push_back(&value);
		              }
	              });
	return res;
}

template<typename C, typename T>
//requires /*std::is_container<C> &&*/ std::is_same<C::value_type, T>::value
	requires std:: ranges::input_range<C>
std::vector<const T*> find_all(const C& v, const T& key, std::size_t n)
{
	std::condition_variable cv;
	bool run{false};

	std::vector<const T*> res{};

	// Calculate the chunk size needed for splitting the values into
	// (at most) n portions and at least 1 big portion.
	std::ptrdiff_t chunk_size =
		static_cast<std::ptrdiff_t>(std::ceil(static_cast<float>(v.size()) / static_cast<float>(n)));

	std::vector<std::future<std::vector<const T*>>> futures;

	auto begin = v.begin();
	auto end = v.end();
	while(begin < v.end())
	{
		end = begin + chunk_size;
		if(end > v.end())
		{
			end = v.end();
		}
		// create suspended thread for searching on [begin, end[ range
		futures.emplace_back(std::async(std::launch::async,
		                                [&key, &cv, &run, begin, end]()
		                                {
			                                std::mutex m;
			                                std::unique_lock lk(m);
			                                cv.wait(lk, [&run](){ return run; });
			                                return find_all(std::ranges::subrange(begin, end), key);
		                                }));
		begin = end;
	}

	{
		Measure meas;

		// Signal all threads to run
		run = true;
		cv.notify_all();

		// Get and append the result from each thread into accumulated results
		// vector
		for(auto& future : futures)
		{
			auto v = future.get();
			res.insert(res.end(), v.begin(), v.end());
		}
	}

	return res;
}

int main()
{
	{
		auto v = get_random_vector<int>(10'000'000, 0, 100);
//	std::array<int, 10> v{1,2,42,4,5,6,7,8,42,10}; // - this also works
//	int v[] = {1,2,42,4,5,6,7,8,42,10}; // - doesn't seem to work :-(

		// 42 is expected to be in the vector in ~1/100th of the indices
		int needle{42};
		std::size_t found_items{};
		{ // non-threaded
			measure("Single threaded search for int",
			        [&]()
			        {
				        auto res = find_all(v, needle);
				        found_items = res.size(); // consider this the 'truth"
			        });
		}

		for(auto num_threads = 1u; num_threads < 17u; ++num_threads)
		{
			std::cout << "Multi threaded (" << num_threads << ") search for int:\n";
			for(int i = 0; i < 3; ++i)
			{
				auto res = find_all(v, needle, num_threads);
				if(res.size() != found_items)
				{
					std::cout << "That was unexpected!\n";
				}
			}
		}
	}

	{
		auto v = get_random_strings(10'000'000, 20, 'a', 'z');

		// Pick middle string as needle so we get one match:
		std::string needle{v[v.size() / 2]};

		{ // non-threaded
			measure("Single threaded search for string",
			        [&]()
			        {
				        auto res = find_all(v, needle);
				        if(res.size() != 1)
				        {
					        std::cout << "That was unexpected!\n";
				        }
			        });
		}

		for(auto num_threads = 1u; num_threads < 17u; ++num_threads)
		{
			std::cout << "Multi threaded (" << num_threads << ") search for string:\n";
			for(int i = 0; i < 3; ++i)
			{
				auto res = find_all(v, needle, num_threads);
				if(res.size() != 1)
				{
					std::cout << "That was unexpected!\n";
				}
			}
		}
	}
}