#include <chrono>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <thread>
#include <random>

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


int main()
{
	using namespace std::chrono_literals;

	// Sanity check measurement mechanism
	measure("Sanity check (sleep 100ms)",
	        []()
	        {
		        std::this_thread::sleep_for(100ms);
	        });

	// std::find() on a vector<int>:
	// Use a vector large enough to get meaningful values on your machine
	// (1,000,000 elements are likely not enough). Measure the time needed to
	//  * Find the 7 in the middle of a vector<int> where all other elements are
	//    not 7.
	{
		std::vector<int> v(10'000'000, 42); // one million items with the int 42
		v[v.size() / 2] = 7; // set middle item to 7
		measure("std::find 7 in the middle",
		        [&v]()
		        {
			        if(std::find(v.begin(), v.end(), 7) == std::end(v))
			        {
				        std::cout << "That was unexpected!\n";
			        }
		        });
	}

	//  * Try to find a 7 in a vector<int> where no element is 7
	{
		std::vector<int> v(10'000'000, 42); // one million items with the int 42
		measure("std::find 7 not there",
		        [&v]()
		        {
			        if(std::find(v.begin(), v.end(), 7) != std::end(v))
			        {
				        std::cout << "That was unexpected!\n";
			        }
		        });
	}

	// std::find_if() on a vector<int>:
	// Use a vector large enough to get meaningful values on your machine.
	// Measure the time needed to
	//  * Find the x < 7 in the middle of a vector<int> where all other elements
	//    are >= 7.
	{
		std::vector<int> v(10'000'000, 42); // one million items with the int 42
		v[v.size() / 2] = 5; // set middle item to 5
		measure("std::find_if x < 7 in the middle",
		        [&v]()
		        {
			        if(std::find_if(v.begin(), v.end(), [](int x){ return x < 7;}) == std::end(v))
			        {
				        std::cout << "That was unexpected!\n";
			        }
		        });
	}

	//  * Try to find an x < 7 in a vector<int> where all elements are >= 7.
	{
		std::vector<int> v(10'000'000, 42); // one million items with the int 42
		measure("std::find_if x < 7 not there",
		        [&v]()
		        {
			        if(std::find_if(v.begin(), v.end(), [](int x){ return x < 7;}) != std::end(v))
			        {
				        std::cout << "That was unexpected!\n";
			        }
		        });
	}

	// std::find() on a vector<std::string>:
	// Generate a vector<string> containing 1,000,000 random 20-letter strings
	// (don't bother timing this).
	{
		std::default_random_engine generator;
		// Randomly generate characters from the range  [A;Z]
		std::uniform_int_distribution<char> distrib('A', 'Z');

		std::vector<std::string> vs;
		vs.resize(10'000'000);
		for(auto &str: vs)
		{
			str.reserve(20);
			for(auto i = 0u; i < str.capacity(); ++i)
			{
				str += distrib(generator);
			}
		}

		std::string needle(20, 'X');

		// Measure the time needed to
		//  * Try to find XXXXXXXXXXXXXXXXXXXX (20 Xs) in that vector using
		//    std::find().
		measure("Find " + needle + " (not there)",
		        [&]()
		        {
			        if(std::find(vs.begin(), vs.end(), needle) != std::end(vs))
			        {
				        std::cout << "That was unexpected!\n";
			        }
		        });

		//  * Was it there? Unlikely, but if so, try with another value.
		//    Alternatively (optional), ensure you never generate
		//    XXXXXXXXXXXXXXXXXXXX in the first place.
		//
		//  * Place XXXXXXXXXXXXXXXXXXXX (or whatever value is not present) in the
		//    middle and find it using std::find().
		vs[vs.size() / 2] = needle;
		measure("Find " + needle + " (in the middle)",
		        [&]()
		        {
			        if(std::find(vs.begin(), vs.end(), needle) == std::end(vs))
			        {
				        std::cout << "That was unexpected!\n";
			        }
		        });
	}
}