duckhandy/test/unit/scapegoat_tree_test.cpp

/* Copyright 2016-2018 Michele Santullo
 * This file is part of "duckhandy".
 *
 * "duckhandy" is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * "duckhandy" is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with "duckhandy".  If not, see <http://www.gnu.org/licenses/>.
 */

#include "catch2/catch.hpp"
#include "duckhandy/scapegoat_tree.hpp"
#include <set>

TEST_CASE ("Insert values in a ScapegoatTree", "[Scapegoat][ScapegoatTree][containers]") {
	using duckmem::ScapegoatTree;

	ScapegoatTree<int> tree;
	{
		auto it = tree.insert(25);
		CHECK(it.second == true);
		CHECK(it.first != tree.end());
		CHECK(*it.first == 25);
		CHECK(tree.size() == 1);
	}

	{
		auto it = tree.insert(25);
		CHECK(tree.size() == 1);
		CHECK(it.second == false);
		CHECK(it.first != tree.end());
		CHECK(*it.first == 25);
	}

	{
		auto it = tree.insert(26);
		CHECK(it.second == true);
		CHECK(it.first != tree.end());
		CHECK(*it.first == 26);
		CHECK(tree.size() == 2);
	}

	{
		for (std::size_t z = 0; z < 100; ++z) {
			const int val = static_cast<int>(z);

			auto it = tree.insert(val);
			if (z < 25) {
				CHECK(tree.size() == z + 2 + 1);
				CHECK(it.second == true);
			}
			else if (z < 26) {
				CHECK(tree.size() == z + 1 + 1);
				CHECK(it.second == false);
			}
			else if (z < 27) {
				CHECK(tree.size() == z + 1);
				CHECK(it.second == false);
			}
			else {
				CHECK(tree.size() == z + 1);
				CHECK(it.second == true);
			}
			CHECK(*it.first == val);
		}
	}

	{
		auto end = tree.end();
		int val = 0;
		for (auto it = tree.begin(); it != end; ++it, ++val) {
			CHECK(val == *it);
		}
		CHECK(static_cast<int>(tree.size()) == val);

		val = 75;
		for (auto it = tree.insert(val).first; it != end; ++it, ++val) {
			CHECK(val == *it);
		}
		CHECK(static_cast<int>(tree.size()) == val);
	}
}

TEST_CASE ("Erase values from a ScapegoatTree", "[Scapegoat][ScapegoatTree][containers]") {
	using duckmem::ScapegoatTree;

	//auto rand_num = std::bind(std::uniform_int_distribution<int>(1, 1000), std::mt19937(std::time(0)));

	ScapegoatTree<int> tree;
	for (int z = 0; z < 5000; ++z) {
		tree.insert(z + 1);
	}
	CHECK(tree.size() == 5000);

	std::set<int> cpy(tree.begin(), tree.end());
	CHECK(cpy.size() == 5000);

	{
		auto it_num = tree.find(0);
		CHECK(it_num == tree.end());
	}
	{
		auto it_num = tree.find(1);
		REQUIRE(it_num != tree.end());
		CHECK(*it_num == 1);
		CHECK(it_num == tree.begin());
		tree.erase(it_num);
		cpy.erase(1);
		CHECK(tree.size() == 4999);
		it_num = tree.find(1);
		CHECK(it_num == tree.end());
		CHECK(not tree.include(1));
	}
	{
		auto it_num = tree.find(2345);
		REQUIRE(it_num != tree.end());
		CHECK(*it_num == 2345);
		tree.erase(it_num);
		cpy.erase(2345);
		CHECK(tree.size() == 4998);
		it_num = tree.find(2345);
		CHECK(it_num == tree.end());
		CHECK(not tree.include(2345));
	}
	{
		auto it_num = tree.find(3000);
		REQUIRE(it_num != tree.end());
		int test_num = 3000;
		for (; it_num != tree.end(); ++it_num) {
			CHECK(*it_num == test_num);
			test_num++;
		}
		CHECK(test_num == 5001);
	}
	{
		const ScapegoatTree<int>& ref = tree;
		auto it_num = ref.find(18);
		REQUIRE(it_num != ref.end());
		CHECK(*it_num == 18);
		CHECK(ref.include(18));
	}

	REQUIRE(tree.size() == cpy.size());
	CHECK(std::equal(tree.begin(), tree.end(), cpy.begin()));
}