#include <limits>
#include <random>
#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <chrono>
#include <type_traits>

#include "generator.h"
#include "octave.h"

template<typename T>
Generator<T> get_random(int seed,
                        T min = std::numeric_limits<T>::min(),
                        T max = std::numeric_limits<T>::max())
{
	std::default_random_engine generator(seed);
	// Randomly generate T-values from the range [min; max]
	std::uniform_int_distribution<T> distrib(min, max);

	while(true)
	{
		co_yield distrib(generator);
	}
}

class Timer
{
public:
	void start()
	{
		_start = std::chrono::high_resolution_clock::now();
	}

	void stop()
	{
		_elapsed = std::chrono::high_resolution_clock::now() - _start;
		std::cout << " took " << _elapsed.count() * 1000 << "ms\n";
	}

	double elapsed() const
	{
		return _elapsed.count() * 1000; // return number of milliseconds passed
	}

private:
	std::chrono::time_point<std::chrono::high_resolution_clock> _start{};
	std::chrono::duration<double> _elapsed{};
};

class Measure
{
public:
	Measure(Timer& timer)
		: timer(timer)
	{
		timer.start();
	}

	~Measure()
	{
		timer.stop();
	}

private:
	Timer& timer;
};

template<typename C, typename T>
void sorted_insert(C& container, T element)
{
	auto it = std::begin(container);
	while(it != std::end(container) && *it < element)
	{
		++it;
	}

	container.insert(it, element);
}

template<typename C>
void remove_index(C& container, int index)
{
	auto it = std::begin(container);
	for(int i = 0; i < index; ++i)
	{
		++it;
	}

	container.erase(it);
}

struct PaddedInt
{
	PaddedInt(int i) : i(i) {}
	int operator=(int other)
	{
		i = other;
		return i;
	}

	bool operator<(int other) const
	{
		return i < other;
	}

	bool operator<(const PaddedInt& other) const
	{
		return i < other.i;
	}

	int i;
	char padding[1024 - sizeof(int)]{}; // pad up to 1k
};

std::ostream& operator<<(std::ostream& s, const PaddedInt& i)
{
	s << i.i;
	return s;
}

template<typename C>
	requires std::is_same<C, std::vector<PaddedInt>>::value ||
	         std::is_same<C, std::list<PaddedInt>>::value ||
	         std::is_same<C, std::set<PaddedInt>>::value ||
	         std::is_same<C, std::vector<int>>::value ||
	         std::is_same<C, std::list<int>>::value ||
	         std::is_same<C, std::set<int>>::value
std::ostream& operator<<(std::ostream& s, const C& container)
{
	for(const auto& item : container)
	{
		s << item << " ";
	}
	return s;
}

int main()
{
	//using experiment_type_t = int;
	using experiment_type_t = PaddedInt;

	Timer timer;
	Octave ins_oct("insert-padded");
	ins_oct.setAxis("N", "time (ms)");

	auto& ins_plot_v = ins_oct.add("std::vector");
	auto& ins_plot_l = ins_oct.add("std::list");
	auto& ins_plot_s = ins_oct.add("std::set");

	Octave rem_oct("remove-padded");
	rem_oct.setAxis("N", "time (ms)");

	auto& rem_plot_v = rem_oct.add("std::vector");
	auto& rem_plot_l = rem_oct.add("std::list");
	auto& rem_plot_s = rem_oct.add("std::set");

	constexpr std::size_t Ns[]{10, 50, 100, 200, 500, 1000, 2000, 3000, 4000, 5000, 8000, 10'000, 12'000, 14'000, 16'000, 18'000, 20'000};

	for(auto N : Ns)
	{
		ins_plot_v.setX(double(N));
		ins_plot_l.setX(double(N));
		ins_plot_s.setX(double(N));

		rem_plot_v.setX(double(N));
		rem_plot_l.setX(double(N));
		rem_plot_s.setX(double(N));

		for(int i = 0; i < 3; ++i)
		{
			std::cout << "--- Iteration " << i << " of 3\n";
			// Create N unique values in rnd vector:
			std::vector<int> rnd;
			auto gen = get_random<int>(i, 0, int(N) * 10);
			while(rnd.size() < N)
			{
				auto r = gen();
				if(std::find(rnd.begin(), rnd.end(), r) == std::end(rnd))
				{
					rnd.push_back(r);
				}
			}

			if(N < 64)
			{
				std::cout << "rnd: " << rnd << '\n';
			}

			// Create vector of removal indices
			std::vector<int> rem;
			{
				std::default_random_engine generator(i);
				for(int end = int(N) - 1; end >= 0; --end)
				{
					// Gradually decrease the range of valid removal indices
					std::uniform_int_distribution<int> distrib(0, end);
					rem.push_back(distrib(generator));
				}

				if(N < 64)
				{
					std::cout << "rem: " << rem << '\n';
				}
			}

			// std::vector experiment
			{
				std::vector<experiment_type_t> vec;
				std::cout << "std::vector insert (N=" + std::to_string(N) + "):\n";
				{
					Measure _(timer);
					for(auto r : rnd)
					{
						sorted_insert(vec, r);
					}
				}
				ins_plot_v.add(timer.elapsed());

				if(N < 64)
				{
					std::cout << "vec: " << vec << '\n';
				}

				std::cout << "std::vector remove (N=" + std::to_string(N) + "):\n";
				{
					Measure _(timer);
					for(auto r : rem)
					{
						remove_index(vec, r);
					}
				}
				rem_plot_v.add(timer.elapsed());
			}

			// std::list experiment
			{
				std::list<experiment_type_t> lst;
				std::cout << "std::list insert (N=" + std::to_string(N) + "):\n";
				{
					Measure _(timer);
					for(auto r : rnd)
					{
						sorted_insert(lst, r);
					}
				}
				ins_plot_l.add(timer.elapsed());

				if(N < 64)
				{
					std::cout << "lst: " << lst  << '\n';
				}

				std::cout << "std::list remove (N=" + std::to_string(N) + "):\n";
				{
					Measure _(timer);
					for(auto r : rem)
					{
						remove_index(lst, r);
					}
				}
				rem_plot_l.add(timer.elapsed());
			}

			// std::set experiment
			{
				std::set<experiment_type_t> set;
				std::cout << "std::set insert (N=" + std::to_string(N) + "):\n";
				{
					Measure _(timer);
					for(auto r : rnd)
					{
						set.insert(r);
					}
				}
				ins_plot_s.add(timer.elapsed());

				if(N < 64)
				{
					std::cout << "set: " << set << '\n';
				}

				std::cout << "std::set remove (N=" + std::to_string(N) + "):\n";
				{
					Measure _(timer);
					for(auto r : rem)
					{
						remove_index(set, r);
					}
				}
				rem_plot_s.add(timer.elapsed());
			}
		}
	}
}