#include <psemek/test/test.hpp>

#include <psemek/util/flat_list.hpp>

#include <algorithm>
#include <vector>
#include <random>
#include <list>

using namespace psemek::util;

test_case(util_flat__list_empty)
{
	flat_list<int> l;
	expect(l.empty());
	expect_equal(l.size(), 0);
	expect_equal(l.capacity(), 0);
}

test_case(util_flat__list_sequential)
{
	auto p = std::make_shared<int>(42);
	flat_list<std::shared_ptr<int>> l;

	std::vector<decltype(l)::handle_type> h;

	for (std::size_t i = 0; i < 1024*1024; ++i)
	{
		h.push_back(l.insert(p));
		expect_equal(*l[h.back()], *p);
		expect_equal(l.size(), i + 1);
		expect_gequal(l.capacity(), l.size());
		expect_equal(p.use_count(), i + 2);
	}

	for (std::size_t i = 0; i < h.size(); ++i)
	{
		l.erase(h[i]);
		expect_equal(l.size(), h.size() - i - 1);
		expect_gequal(l.capacity(), l.size());
		expect_equal(p.use_count(), h.size() - i);
	}

	expect(l.empty());

	l.clear();
	expect(l.empty());
}

test_case(util_flat__list_shuffle)
{
	auto p = std::make_shared<int>(42);
	flat_list<std::shared_ptr<int>> l;

	std::vector<decltype(l)::handle_type> h;

	for (std::size_t i = 0; i < 1024*1024; ++i)
	{
		h.push_back(l.insert(p));
		expect_equal(l[h.back()], p);
		expect_equal(l.size(), i + 1);
		expect_gequal(l.capacity(), l.size());
		expect_equal(p.use_count(), i + 2);
	}

	std::default_random_engine rng{42};
	std::shuffle(h.begin(), h.end(), rng);

	for (std::size_t i = 0; i < h.size(); ++i)
	{
		l.erase(h[i]);
		expect_equal(l.size(), h.size() - i - 1);
		expect_gequal(l.capacity(), l.size());
		expect_equal(p.use_count(), h.size() - i);
	}

	expect(l.empty());

	l.clear();
	expect(l.empty());
}

test_case(util_flat__list_random)
{
	auto p = std::make_shared<int>(42);
	flat_list<std::shared_ptr<int>> l;

	std::vector<decltype(l)::handle_type> h;

	std::default_random_engine rng{42};
	std::uniform_int_distribution<int> action{0, 1};

	for (std::size_t i = 0; i < 1024*1024; ++i)
	{
		if (h.empty() || action(rng) == 0)
		{
			h.push_back(l.insert(p));
			expect_equal(l[h.back()], p);
		}
		else
		{
			auto index = std::uniform_int_distribution<std::size_t>{0, h.size() - 1}(rng);
			expect_equal(l[h[index]], p);
			l.erase(h[index]);
			h.erase(h.begin() + index);
		}

		expect_equal(l.size(), h.size());
		expect_gequal(l.capacity(), l.size());
		expect_equal(p.use_count(), h.size() + 1);
	}

	l.clear();
	expect(l.empty());
}