#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);
}

int main()
{
	Timer timer;
	Octave ins_oct("insert");
	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");
	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, 5000, 10'000, 15'000, 20'000, 25'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)
		{
			// 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);
				}
			}

			// 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:";
					for(auto i : rem)
					{
						std::cout << " " << i;
					}
					std::cout << '\n';
				}
			}

			// std::vector experiment
			{
				std::vector<int> 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:";
					for(auto i : vec)
					{
						std::cout << " " << i;
					}
					std::cout << '\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<int> 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:";
					for(auto i : lst)
					{
						std::cout << " " << i;
					}
					std::cout << '\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<int> 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:";
					for(auto i : set)
					{
						std::cout << " " << i;
					}
					std::cout << '\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());
			}
		}
	}
}