src/unittest/timeline_test.cc at main · doomsdayone/openmsx

◆ main openmsx / src / unittest / timeline_test.cc

12.7 KiB · C++ · last changed chore(): initial commit 1 month ago source blame history raw

#include "catch.hpp"
#include "timeline.hh"

#include "strCat.hh"

#include <vector>

struct Event {
	double time;
	int value;  // for testing/display purposes
};

struct SimpleMapper {
	double scale; // zoom factor: pixels per time unit

	explicit SimpleMapper(double s = 1.0) : scale(s) {}

	[[nodiscard]] float timeToX(double time) const {
		return static_cast<float>(time * scale);
	}

	[[nodiscard]] double xToTime(float x) const {
		return x / scale;
	}
};

// helper to capture draw calls
struct DrawCall {
	enum Type { DETAILED, COARSE } type;
	float fromX;
	float toX;
	int value1;
	int value2 = -1; // only for COARSE

	bool operator==(const DrawCall& other) const {
		if (type != other.type) return false;
		// use epsilon comparison for floating point
		constexpr float eps = 0.01f;
		if (std::abs(fromX - other.fromX) > eps) return false;
		if (std::abs(toX - other.toX) > eps) return false;
		if (value1 != other.value1) return false;
		if (value2 != other.value2) return false;
		return true;
	}
};
namespace Catch {
template<> struct StringMaker<DrawCall> {
	static std::string convert(const DrawCall& c)
	{
		return strCat(
			"DrawCall{"
			" type=", (c.type == DrawCall::DETAILED ? "detailed" : "coarse"),
			" fromX=", c.fromX,
			" toX=", c.toX,
			" value1=", c.value1,
			" value2=", c.value2,
			" }");
	}
};
}

// helper to run algorithm and capture calls
static std::vector<DrawCall> runAlgorithm(
	const std::vector<Event>& events,
	double endTime,
	const SimpleMapper& mapper = SimpleMapper(1.0),
	float threshold = 1.0f)
{
	std::vector<DrawCall> calls;
	auto span = std::span<const Event>(events);

	auto onDetailed = [&](float fromX, float toX, const Event& event) {
		calls.push_back({DrawCall::DETAILED, fromX, toX, event.value});
	};
	auto onCoarse = [&](float fromX, float toX, auto first, auto last) {
		calls.push_back({DrawCall::COARSE, fromX, toX, first->value, (last != span.end() ? last->value : -1)});
	};

	openmsx::processTimeline(span, endTime, mapper, onDetailed, onCoarse, threshold);
	return calls;
}

TEST_CASE("Timeline processing algorithm - basic scenarios", "[timeline]") {

	SECTION("empty events list") {
		auto calls = runAlgorithm({}, 20.0);
		REQUIRE(calls.empty());
	}

	SECTION("single event") {
		auto calls = runAlgorithm({{10.0, 42}}, 20.0);
		REQUIRE(calls.size() == 1);
		CHECK(calls[0] == DrawCall{DrawCall::DETAILED, 10.0f, 20.0f, 42});
	}

	SECTION("all detailed - well-spaced events") {
		auto calls = runAlgorithm({{10.0, 1}, {15.0, 2}, {22.0, 3}, {30.0, 4}}, 40.0);
		REQUIRE(calls.size() == 4);
		CHECK(calls[0] == DrawCall{DrawCall::DETAILED, 10.0f, 15.0f, 1});
		CHECK(calls[1] == DrawCall{DrawCall::DETAILED, 15.0f, 22.0f, 2});
		CHECK(calls[2] == DrawCall{DrawCall::DETAILED, 22.0f, 30.0f, 3});
		CHECK(calls[3] == DrawCall{DrawCall::DETAILED, 30.0f, 40.0f, 4});
	}

	SECTION("all coarse - dense cluster") {
		auto calls = runAlgorithm({{10.1, 1}, {10.3, 2}, {10.5, 3}, {10.7, 4}, {10.9, 5}, {20.0, 6}}, 25.0);
		REQUIRE(calls.size() == 3);
		CHECK(calls[0] == DrawCall{DrawCall::COARSE, 10.1f, 10.9f, 1, 6});
		CHECK(calls[1] == DrawCall{DrawCall::DETAILED, 10.9f, 20.0f, 5});
		CHECK(calls[2] == DrawCall{DrawCall::DETAILED, 20.0f, 25.0f, 6});
	}

	SECTION("mixed pattern") {
		auto calls = runAlgorithm({{5.1, 1}, {5.3, 2}, {5.5, 3}, {10.0, 4}, {20.1, 5}, {20.3, 6}, {20.6, 7}, {30.0, 8}}, 35.0);
		REQUIRE(calls.size() == 6);
		CHECK(calls[0] == DrawCall{DrawCall::COARSE, 5.1f, 5.5f, 1, 4});
		CHECK(calls[1] == DrawCall{DrawCall::DETAILED, 5.5f, 10.0f, 3});
		CHECK(calls[2] == DrawCall{DrawCall::DETAILED, 10.0f, 20.1f, 4});
		CHECK(calls[3] == DrawCall{DrawCall::COARSE, 20.1f, 20.6f, 5, 8});
		CHECK(calls[4] == DrawCall{DrawCall::DETAILED, 20.6f, 30.0f, 7});
		CHECK(calls[5] == DrawCall{DrawCall::DETAILED, 30.0f, 35.0f, 8});
	}
}

TEST_CASE("Timeline - threshold boundary behavior", "[timeline][threshold]") {

	SECTION("spacing exactly = 1.0 (aligned) -> coarse") {
		auto calls = runAlgorithm({{10.0, 1}, {11.0, 2}, {12.0, 3}, {13.0, 4}}, 20.0);
		REQUIRE(calls.size() == 2);
		CHECK(calls[0] == DrawCall{DrawCall::COARSE, 10.0f, 13.0f, 1, -1});
		CHECK(calls[1] == DrawCall{DrawCall::DETAILED, 13.0f, 20.0f, 4});
	}

	SECTION("spacing exactly = 1.0 (non-aligned) -> coarse") {
		auto calls = runAlgorithm({{10.3, 1}, {11.3, 2}, {12.3, 3}, {13.3, 4}}, 20.0);
		REQUIRE(calls.size() == 2);
		CHECK(calls[0] == DrawCall{DrawCall::COARSE, 10.3f, 13.3f, 1, -1});
		CHECK(calls[1] == DrawCall{DrawCall::DETAILED, 13.3f, 20.0f, 4});
	}

	SECTION("spacing = 1.1 (just above threshold) -> detailed") {
		auto calls = runAlgorithm({{10.0, 1}, {11.1, 2}, {12.2, 3}, {13.3, 4}}, 20.0);
		REQUIRE(calls.size() == 4);
		CHECK(calls[0] == DrawCall{DrawCall::DETAILED, 10.0f, 11.1f, 1});
		CHECK(calls[1] == DrawCall{DrawCall::DETAILED, 11.1f, 12.2f, 2});
		CHECK(calls[2] == DrawCall{DrawCall::DETAILED, 12.2f, 13.3f, 3});
		CHECK(calls[3] == DrawCall{DrawCall::DETAILED, 13.3f, 20.0f, 4});
	}

	SECTION("custom threshold = 2.0") {
		auto calls = runAlgorithm({{10.0, 1}, {11.5, 2}, {13.0, 3}, {16.0, 4}}, 20.0, SimpleMapper(1.0), 2.0f);
		REQUIRE(calls.size() == 3);
		CHECK(calls[0] == DrawCall{DrawCall::COARSE, 10.0f, 13.0f, 1, 4});
		CHECK(calls[1] == DrawCall{DrawCall::DETAILED, 13.0f, 16.0f, 3});
		CHECK(calls[2] == DrawCall{DrawCall::DETAILED, 16.0f, 20.0f, 4});
	}

	SECTION("two very close events (spacing = 0.01)") {
		auto calls = runAlgorithm({{7.51, 1}, {7.52, 2}, {15.0, 3}}, 20.0);
		REQUIRE(calls.size() == 3);
		CHECK(calls[0] == DrawCall{DrawCall::COARSE, 7.51f, 7.52f, 1, 3});
		CHECK(calls[1] == DrawCall{DrawCall::DETAILED, 7.52f, 15.0f, 2});
		CHECK(calls[2] == DrawCall{DrawCall::DETAILED, 15.0f, 20.0f, 3});
	}

	SECTION("multiple events at exact same time (spacing = 0)") {
		auto calls = runAlgorithm({{10.0, 1}, {10.0, 2}, {10.0, 3}, {15.0, 4}}, 20.0);
		REQUIRE(calls.size() == 3);
		CHECK(calls[0] == DrawCall{DrawCall::COARSE, 10.0f, 10.0f, 1, 4});  // zero-width
		CHECK(calls[1] == DrawCall{DrawCall::DETAILED, 10.0f, 15.0f, 3});
		CHECK(calls[2] == DrawCall{DrawCall::DETAILED, 15.0f, 20.0f, 4});
	}
}

TEST_CASE("Timeline - dense clusters (binary search)", "[timeline][performance]") {

	SECTION("many events tightly clustered (15 events in 0.15 units)") {
		std::vector<Event> events;
		for (int i = 0; i < 15; ++i) {
			events.push_back({5.01 + i * 0.01, i + 1});
		}
		events.push_back({10.0, 16});

		auto calls = runAlgorithm(events, 15.0);
		REQUIRE(calls.size() == 3);
		CHECK(calls[0] == DrawCall{DrawCall::COARSE, 5.01f, 5.15f, 1, 16});
		CHECK(calls[1] == DrawCall{DrawCall::DETAILED, 5.15f, 10.0f, 15});
		CHECK(calls[2] == DrawCall{DrawCall::DETAILED, 10.0f, 15.0f, 16});
	}

	SECTION("dense events spanning multiple pixels (100 events in 2 units)") {
		std::vector<Event> events;
		for (int i = 0; i < 100; ++i) {
			events.push_back({10.0 + i * 0.02, 100 + i});
		}
		events.push_back({20.0, 200});

		auto calls = runAlgorithm(events, 25.0);
		REQUIRE(calls.size() == 3);
		CHECK(calls[0] == DrawCall{DrawCall::COARSE, 10.0f, 11.98f, 100, 200});
		CHECK(calls[1] == DrawCall{DrawCall::DETAILED, 11.98f, 20.0f, 199});
		CHECK(calls[2] == DrawCall{DrawCall::DETAILED, 20.0f, 25.0f, 200});
	}

	SECTION("cluster right before pixel boundary") {
		auto calls = runAlgorithm(
			{{9.91, 1}, {9.92, 2}, {9.93, 3}, {9.94, 4}, {9.95, 5},
			 {9.96, 6}, {9.97, 7}, {9.98, 8}, {9.99, 9}, {15.0, 10}},
			20.0);
		REQUIRE(calls.size() == 3);
		CHECK(calls[0] == DrawCall{DrawCall::COARSE, 9.91f, 9.99f, 1, 10});
		CHECK(calls[1] == DrawCall{DrawCall::DETAILED, 9.99f, 15.0f, 9});
		CHECK(calls[2] == DrawCall{DrawCall::DETAILED, 15.0f, 20.0f, 10});
	}
}

TEST_CASE("Timeline - edge cases", "[timeline][edge]") {

	SECTION("last events are coarse") {
		auto calls = runAlgorithm({{5.0, 1}, {10.1, 2}, {10.2, 3}, {10.3, 4}, {10.4, 5}}, 10.5);
		REQUIRE(calls.size() == 2);
		CHECK(calls[0] == DrawCall{DrawCall::DETAILED, 5.0f, 10.1f, 1});
		CHECK(calls[1] == DrawCall{DrawCall::COARSE, 10.1f, 10.5f, 2, -1});
	}

	SECTION("dense cluster at very end of timeline") {
		auto calls = runAlgorithm({{5.0, 1}, {99.1, 2}, {99.2, 3}, {99.3, 4}, {99.4, 5}, {99.5, 6}}, 99.6);
		REQUIRE(calls.size() == 2);
		CHECK(calls[0] == DrawCall{DrawCall::DETAILED, 5.0f, 99.1f, 1});
		CHECK(calls[1] == DrawCall{DrawCall::COARSE, 99.1f, 99.6f, 2, -1});
	}

	SECTION("endTimeequals last event time") {
		auto calls = runAlgorithm({{10.0, 1}, {15.5, 2}, {23.7, 3}}, 23.7);
		REQUIRE(calls.size() == 3);
		CHECK(calls[0] == DrawCall{DrawCall::DETAILED, 10.0f, 15.5f, 1});
		CHECK(calls[1] == DrawCall{DrawCall::DETAILED, 15.5f, 23.7f, 2});
		CHECK(calls[2] == DrawCall{DrawCall::COARSE, 23.7f, 23.7f, 3, -1});  // zero-width
	}

	SECTION("fractional endTime") {
		auto calls = runAlgorithm({{14.1, 1}, {14.9, 2}, {23.6, 3}}, 30.27);
		REQUIRE(calls.size() == 3);
		CHECK(calls[0] == DrawCall{DrawCall::COARSE, 14.1f, 14.9f, 1, 3});
		CHECK(calls[1] == DrawCall{DrawCall::DETAILED, 14.9f, 23.6f, 2});
		CHECK(calls[2] == DrawCall{DrawCall::DETAILED, 23.6f, 30.27f, 3});
	}
}

TEST_CASE("Timeline - zoom behavior", "[timeline][zoom]") {
	// same events at different zoom levels
	std::vector<Event> events = {{10.0, 1}, {10.1, 2}, {10.2, 3}, {10.3, 4}, {10.4, 5}};
	double endTime = 15.0;

	SECTION("zoom 1x (identity) - events 0.1 apart -> coarse") {
		auto calls = runAlgorithm(events, endTime, SimpleMapper(1.0));
		REQUIRE(calls.size() == 2);
		CHECK(calls[0] == DrawCall{DrawCall::COARSE, 10.0f, 10.4f, 1, -1});
		CHECK(calls[1] == DrawCall{DrawCall::DETAILED, 10.4f, 15.0f, 5});
	}

	SECTION("zoom 2x - spacing becomes 0.2 pixels -> still coarse") {
		auto calls = runAlgorithm(events, endTime, SimpleMapper(2.0));
		REQUIRE(calls.size() == 2);
		CHECK(calls[0] == DrawCall{DrawCall::COARSE, 20.0f, 20.8f, 1, -1});
		CHECK(calls[1] == DrawCall{DrawCall::DETAILED, 20.8f, 30.0f, 5});
	}

	SECTION("zoom 15x - spacing becomes 1.5 pixels -> all detailed") {
		auto calls = runAlgorithm(events, endTime, SimpleMapper(15.0));
		REQUIRE(calls.size() == 5);
		CHECK(calls[0] == DrawCall{DrawCall::DETAILED, 150.0f, 151.5f, 1});
		CHECK(calls[1] == DrawCall{DrawCall::DETAILED, 151.5f, 153.0f, 2});
		CHECK(calls[2] == DrawCall{DrawCall::DETAILED, 153.0f, 154.5f, 3});
		CHECK(calls[3] == DrawCall{DrawCall::DETAILED, 154.5f, 156.0f, 4});
		CHECK(calls[4] == DrawCall{DrawCall::DETAILED, 156.0f, 225.0f, 5});
	}

	SECTION("zoom 0.01x (zoom out) - everything in same pixel -> single coarse") {
		auto calls = runAlgorithm(events, endTime, SimpleMapper(0.01));
		REQUIRE(calls.size() == 1);
		CHECK(calls[0] == DrawCall{DrawCall::COARSE, 0.1f, 0.15f, 1, -1});
	}
}

TEST_CASE("Timeline - complex realistic scenarios", "[timeline][integration]") {

	SECTION("alternating dense and sparse regions") {
		auto calls = runAlgorithm(
			{{10.1, 1}, {10.2, 2}, {10.3, 3}, {20.0, 4},
			 {30.1, 5}, {30.2, 6}, {30.3, 7}, {40.0, 8},
			 {50.1, 9}, {50.2, 10}, {60.0, 11}},
			70.0);
		REQUIRE(calls.size() == 9);
		CHECK(calls[0] == DrawCall{DrawCall::COARSE, 10.1f, 10.3f, 1, 4});
		CHECK(calls[1] == DrawCall{DrawCall::DETAILED, 10.3f, 20.0f, 3});
		CHECK(calls[2] == DrawCall{DrawCall::DETAILED, 20.0f, 30.1f, 4});
		CHECK(calls[3] == DrawCall{DrawCall::COARSE, 30.1f, 30.3f, 5, 8});
		CHECK(calls[4] == DrawCall{DrawCall::DETAILED, 30.3f, 40.0f, 7});
		CHECK(calls[5] == DrawCall{DrawCall::DETAILED, 40.0f, 50.1f, 8});
		CHECK(calls[6] == DrawCall{DrawCall::COARSE, 50.1f, 50.2f, 9, 11});
		CHECK(calls[7] == DrawCall{DrawCall::DETAILED, 50.2f, 60.0f, 10});
		CHECK(calls[8] == DrawCall{DrawCall::DETAILED, 60.0f, 70.0f, 11});
	}

	SECTION("large dataset with mixed regions") {
		std::vector<Event> events;
		// dense cluster at start (50 events, 0.1 apart)
		for (int i = 0; i < 50; ++i) {
			events.push_back({0.0 + i * 0.1, 1000 + i});
		}
		// well-spaced events
		events.push_back({10.0, 2000});
		events.push_back({15.5, 2001});
		events.push_back({23.7, 2002});
		events.push_back({35.2, 2003});
		events.push_back({48.9, 2004});
		// another dense cluster (30 events, 0.066 apart)
		for (int i = 0; i < 30; ++i) {
			events.push_back({50.0 + i * 0.066, 3000 + i});
		}
		// final well-spaced events
		events.push_back({60.0, 4000});
		events.push_back({75.5, 4001});
		events.push_back({90.0, 4002});

		auto calls = runAlgorithm(events, 100.0);
		REQUIRE(calls.size() == 12);
		CHECK(calls[0].type == DrawCall::COARSE);  // first dense cluster
		CHECK(calls[1].type == DrawCall::DETAILED);
		// well-spaced section
		CHECK(calls[2].type == DrawCall::DETAILED);
		CHECK(calls[3].type == DrawCall::DETAILED);
		CHECK(calls[4].type == DrawCall::DETAILED);
		CHECK(calls[5].type == DrawCall::DETAILED);
		CHECK(calls[6].type == DrawCall::DETAILED);
		// second dense cluster
		CHECK(calls[7].type == DrawCall::COARSE);
		// final well-spaced section
		CHECK(calls[8].type == DrawCall::DETAILED);
		CHECK(calls[9].type == DrawCall::DETAILED);
		CHECK(calls[10].type == DrawCall::DETAILED);
		CHECK(calls[11].type == DrawCall::DETAILED);
	}
}

`/`	Search
`g` `c`	Code
`g` `h`	History
`g` `b`	Bookmarks
`g` `t`	Trust
`y`	Permalink to this state (files and trees)
`?`	This sheet

1	#include "catch.hpp"
2	#include "timeline.hh"
3
4	#include "strCat.hh"
5
6	#include <vector>
7
8	struct Event {
9	double time;
10	int value; // for testing/display purposes
11	};
12
13	struct SimpleMapper {
14	double scale; // zoom factor: pixels per time unit
15
16	explicit SimpleMapper(double s = 1.0) : scale(s) {}
17
18	[[nodiscard]] float timeToX(double time) const {
19	return static_cast<float>(time * scale);
20	}
21
22	[[nodiscard]] double xToTime(float x) const {
23	return x / scale;
24	}
25	};
26
27	// helper to capture draw calls
28	struct DrawCall {
29	enum Type { DETAILED, COARSE } type;
30	float fromX;
31	float toX;
32	int value1;
33	int value2 = -1; // only for COARSE
34
35	bool operator==(const DrawCall& other) const {
36	if (type != other.type) return false;
37	// use epsilon comparison for floating point
38	constexpr float eps = 0.01f;
39	if (std::abs(fromX - other.fromX) > eps) return false;
40	if (std::abs(toX - other.toX) > eps) return false;
41	if (value1 != other.value1) return false;
42	if (value2 != other.value2) return false;
43	return true;
44	}
45	};
46	namespace Catch {
47	template<> struct StringMaker<DrawCall> {
48	static std::string convert(const DrawCall& c)
49	{
50	return strCat(
51	"DrawCall{"
52	" type=", (c.type == DrawCall::DETAILED ? "detailed" : "coarse"),
53	" fromX=", c.fromX,
54	" toX=", c.toX,
55	" value1=", c.value1,
56	" value2=", c.value2,
57	" }");
58	}
59	};
60	}
61
62	// helper to run algorithm and capture calls
63	static std::vector<DrawCall> runAlgorithm(
64	const std::vector<Event>& events,
65	double endTime,
66	const SimpleMapper& mapper = SimpleMapper(1.0),
67	float threshold = 1.0f)
68	{
69	std::vector<DrawCall> calls;
70	auto span = std::span<const Event>(events);
71
72	auto onDetailed = [&](float fromX, float toX, const Event& event) {
73	calls.push_back({DrawCall::DETAILED, fromX, toX, event.value});
74	};
75	auto onCoarse = [&](float fromX, float toX, auto first, auto last) {
76	calls.push_back({DrawCall::COARSE, fromX, toX, first->value, (last != span.end() ? last->value : -1)});
77	};
78
79	openmsx::processTimeline(span, endTime, mapper, onDetailed, onCoarse, threshold);
80	return calls;
81	}
82
83	TEST_CASE("Timeline processing algorithm - basic scenarios", "[timeline]") {
84
85	SECTION("empty events list") {
86	auto calls = runAlgorithm({}, 20.0);
87	REQUIRE(calls.empty());
88	}
89
90	SECTION("single event") {
91	auto calls = runAlgorithm({{10.0, 42}}, 20.0);
92	REQUIRE(calls.size() == 1);
93	CHECK(calls[0] == DrawCall{DrawCall::DETAILED, 10.0f, 20.0f, 42});
94	}
95
96	SECTION("all detailed - well-spaced events") {
97	auto calls = runAlgorithm({{10.0, 1}, {15.0, 2}, {22.0, 3}, {30.0, 4}}, 40.0);
98	REQUIRE(calls.size() == 4);
99	CHECK(calls[0] == DrawCall{DrawCall::DETAILED, 10.0f, 15.0f, 1});
100	CHECK(calls[1] == DrawCall{DrawCall::DETAILED, 15.0f, 22.0f, 2});
101	CHECK(calls[2] == DrawCall{DrawCall::DETAILED, 22.0f, 30.0f, 3});
102	CHECK(calls[3] == DrawCall{DrawCall::DETAILED, 30.0f, 40.0f, 4});
103	}
104
105	SECTION("all coarse - dense cluster") {
106	auto calls = runAlgorithm({{10.1, 1}, {10.3, 2}, {10.5, 3}, {10.7, 4}, {10.9, 5}, {20.0, 6}}, 25.0);
107	REQUIRE(calls.size() == 3);
108	CHECK(calls[0] == DrawCall{DrawCall::COARSE, 10.1f, 10.9f, 1, 6});
109	CHECK(calls[1] == DrawCall{DrawCall::DETAILED, 10.9f, 20.0f, 5});
110	CHECK(calls[2] == DrawCall{DrawCall::DETAILED, 20.0f, 25.0f, 6});
111	}
112
113	SECTION("mixed pattern") {
114	auto calls = runAlgorithm({{5.1, 1}, {5.3, 2}, {5.5, 3}, {10.0, 4}, {20.1, 5}, {20.3, 6}, {20.6, 7}, {30.0, 8}}, 35.0);
115	REQUIRE(calls.size() == 6);
116	CHECK(calls[0] == DrawCall{DrawCall::COARSE, 5.1f, 5.5f, 1, 4});
117	CHECK(calls[1] == DrawCall{DrawCall::DETAILED, 5.5f, 10.0f, 3});
118	CHECK(calls[2] == DrawCall{DrawCall::DETAILED, 10.0f, 20.1f, 4});
119	CHECK(calls[3] == DrawCall{DrawCall::COARSE, 20.1f, 20.6f, 5, 8});
120	CHECK(calls[4] == DrawCall{DrawCall::DETAILED, 20.6f, 30.0f, 7});
121	CHECK(calls[5] == DrawCall{DrawCall::DETAILED, 30.0f, 35.0f, 8});
122	}
123	}
124
125	TEST_CASE("Timeline - threshold boundary behavior", "[timeline][threshold]") {
126
127	SECTION("spacing exactly = 1.0 (aligned) -> coarse") {
128	auto calls = runAlgorithm({{10.0, 1}, {11.0, 2}, {12.0, 3}, {13.0, 4}}, 20.0);
129	REQUIRE(calls.size() == 2);
130	CHECK(calls[0] == DrawCall{DrawCall::COARSE, 10.0f, 13.0f, 1, -1});
131	CHECK(calls[1] == DrawCall{DrawCall::DETAILED, 13.0f, 20.0f, 4});
132	}
133
134	SECTION("spacing exactly = 1.0 (non-aligned) -> coarse") {
135	auto calls = runAlgorithm({{10.3, 1}, {11.3, 2}, {12.3, 3}, {13.3, 4}}, 20.0);
136	REQUIRE(calls.size() == 2);
137	CHECK(calls[0] == DrawCall{DrawCall::COARSE, 10.3f, 13.3f, 1, -1});
138	CHECK(calls[1] == DrawCall{DrawCall::DETAILED, 13.3f, 20.0f, 4});
139	}
140
141	SECTION("spacing = 1.1 (just above threshold) -> detailed") {
142	auto calls = runAlgorithm({{10.0, 1}, {11.1, 2}, {12.2, 3}, {13.3, 4}}, 20.0);
143	REQUIRE(calls.size() == 4);
144	CHECK(calls[0] == DrawCall{DrawCall::DETAILED, 10.0f, 11.1f, 1});
145	CHECK(calls[1] == DrawCall{DrawCall::DETAILED, 11.1f, 12.2f, 2});
146	CHECK(calls[2] == DrawCall{DrawCall::DETAILED, 12.2f, 13.3f, 3});
147	CHECK(calls[3] == DrawCall{DrawCall::DETAILED, 13.3f, 20.0f, 4});
148	}
149
150	SECTION("custom threshold = 2.0") {
151	auto calls = runAlgorithm({{10.0, 1}, {11.5, 2}, {13.0, 3}, {16.0, 4}}, 20.0, SimpleMapper(1.0), 2.0f);
152	REQUIRE(calls.size() == 3);
153	CHECK(calls[0] == DrawCall{DrawCall::COARSE, 10.0f, 13.0f, 1, 4});
154	CHECK(calls[1] == DrawCall{DrawCall::DETAILED, 13.0f, 16.0f, 3});
155	CHECK(calls[2] == DrawCall{DrawCall::DETAILED, 16.0f, 20.0f, 4});
156	}
157
158	SECTION("two very close events (spacing = 0.01)") {
159	auto calls = runAlgorithm({{7.51, 1}, {7.52, 2}, {15.0, 3}}, 20.0);
160	REQUIRE(calls.size() == 3);
161	CHECK(calls[0] == DrawCall{DrawCall::COARSE, 7.51f, 7.52f, 1, 3});
162	CHECK(calls[1] == DrawCall{DrawCall::DETAILED, 7.52f, 15.0f, 2});
163	CHECK(calls[2] == DrawCall{DrawCall::DETAILED, 15.0f, 20.0f, 3});
164	}
165
166	SECTION("multiple events at exact same time (spacing = 0)") {
167	auto calls = runAlgorithm({{10.0, 1}, {10.0, 2}, {10.0, 3}, {15.0, 4}}, 20.0);
168	REQUIRE(calls.size() == 3);
169	CHECK(calls[0] == DrawCall{DrawCall::COARSE, 10.0f, 10.0f, 1, 4}); // zero-width
170	CHECK(calls[1] == DrawCall{DrawCall::DETAILED, 10.0f, 15.0f, 3});
171	CHECK(calls[2] == DrawCall{DrawCall::DETAILED, 15.0f, 20.0f, 4});
172	}
173	}
174
175	TEST_CASE("Timeline - dense clusters (binary search)", "[timeline][performance]") {
176
177	SECTION("many events tightly clustered (15 events in 0.15 units)") {
178	std::vector<Event> events;
179	for (int i = 0; i < 15; ++i) {
180	events.push_back({5.01 + i * 0.01, i + 1});
181	}
182	events.push_back({10.0, 16});
183
184	auto calls = runAlgorithm(events, 15.0);
185	REQUIRE(calls.size() == 3);
186	CHECK(calls[0] == DrawCall{DrawCall::COARSE, 5.01f, 5.15f, 1, 16});
187	CHECK(calls[1] == DrawCall{DrawCall::DETAILED, 5.15f, 10.0f, 15});
188	CHECK(calls[2] == DrawCall{DrawCall::DETAILED, 10.0f, 15.0f, 16});
189	}
190
191	SECTION("dense events spanning multiple pixels (100 events in 2 units)") {
192	std::vector<Event> events;
193	for (int i = 0; i < 100; ++i) {
194	events.push_back({10.0 + i * 0.02, 100 + i});
195	}
196	events.push_back({20.0, 200});
197
198	auto calls = runAlgorithm(events, 25.0);
199	REQUIRE(calls.size() == 3);
200	CHECK(calls[0] == DrawCall{DrawCall::COARSE, 10.0f, 11.98f, 100, 200});
201	CHECK(calls[1] == DrawCall{DrawCall::DETAILED, 11.98f, 20.0f, 199});
202	CHECK(calls[2] == DrawCall{DrawCall::DETAILED, 20.0f, 25.0f, 200});
203	}
204
205	SECTION("cluster right before pixel boundary") {
206	auto calls = runAlgorithm(
207	{{9.91, 1}, {9.92, 2}, {9.93, 3}, {9.94, 4}, {9.95, 5},
208	{9.96, 6}, {9.97, 7}, {9.98, 8}, {9.99, 9}, {15.0, 10}},
209	20.0);
210	REQUIRE(calls.size() == 3);
211	CHECK(calls[0] == DrawCall{DrawCall::COARSE, 9.91f, 9.99f, 1, 10});
212	CHECK(calls[1] == DrawCall{DrawCall::DETAILED, 9.99f, 15.0f, 9});
213	CHECK(calls[2] == DrawCall{DrawCall::DETAILED, 15.0f, 20.0f, 10});
214	}
215	}
216
217	TEST_CASE("Timeline - edge cases", "[timeline][edge]") {
218
219	SECTION("last events are coarse") {
220	auto calls = runAlgorithm({{5.0, 1}, {10.1, 2}, {10.2, 3}, {10.3, 4}, {10.4, 5}}, 10.5);
221	REQUIRE(calls.size() == 2);
222	CHECK(calls[0] == DrawCall{DrawCall::DETAILED, 5.0f, 10.1f, 1});
223	CHECK(calls[1] == DrawCall{DrawCall::COARSE, 10.1f, 10.5f, 2, -1});
224	}
225
226	SECTION("dense cluster at very end of timeline") {
227	auto calls = runAlgorithm({{5.0, 1}, {99.1, 2}, {99.2, 3}, {99.3, 4}, {99.4, 5}, {99.5, 6}}, 99.6);
228	REQUIRE(calls.size() == 2);
229	CHECK(calls[0] == DrawCall{DrawCall::DETAILED, 5.0f, 99.1f, 1});
230	CHECK(calls[1] == DrawCall{DrawCall::COARSE, 99.1f, 99.6f, 2, -1});
231	}
232
233	SECTION("endTimeequals last event time") {
234	auto calls = runAlgorithm({{10.0, 1}, {15.5, 2}, {23.7, 3}}, 23.7);
235	REQUIRE(calls.size() == 3);
236	CHECK(calls[0] == DrawCall{DrawCall::DETAILED, 10.0f, 15.5f, 1});
237	CHECK(calls[1] == DrawCall{DrawCall::DETAILED, 15.5f, 23.7f, 2});
238	CHECK(calls[2] == DrawCall{DrawCall::COARSE, 23.7f, 23.7f, 3, -1}); // zero-width
239	}
240
241	SECTION("fractional endTime") {
242	auto calls = runAlgorithm({{14.1, 1}, {14.9, 2}, {23.6, 3}}, 30.27);
243	REQUIRE(calls.size() == 3);
244	CHECK(calls[0] == DrawCall{DrawCall::COARSE, 14.1f, 14.9f, 1, 3});
245	CHECK(calls[1] == DrawCall{DrawCall::DETAILED, 14.9f, 23.6f, 2});
246	CHECK(calls[2] == DrawCall{DrawCall::DETAILED, 23.6f, 30.27f, 3});
247	}
248	}
249
250	TEST_CASE("Timeline - zoom behavior", "[timeline][zoom]") {
251	// same events at different zoom levels
252	std::vector<Event> events = {{10.0, 1}, {10.1, 2}, {10.2, 3}, {10.3, 4}, {10.4, 5}};
253	double endTime = 15.0;
254
255	SECTION("zoom 1x (identity) - events 0.1 apart -> coarse") {
256	auto calls = runAlgorithm(events, endTime, SimpleMapper(1.0));
257	REQUIRE(calls.size() == 2);
258	CHECK(calls[0] == DrawCall{DrawCall::COARSE, 10.0f, 10.4f, 1, -1});
259	CHECK(calls[1] == DrawCall{DrawCall::DETAILED, 10.4f, 15.0f, 5});
260	}
261
262	SECTION("zoom 2x - spacing becomes 0.2 pixels -> still coarse") {
263	auto calls = runAlgorithm(events, endTime, SimpleMapper(2.0));
264	REQUIRE(calls.size() == 2);
265	CHECK(calls[0] == DrawCall{DrawCall::COARSE, 20.0f, 20.8f, 1, -1});
266	CHECK(calls[1] == DrawCall{DrawCall::DETAILED, 20.8f, 30.0f, 5});
267	}
268
269	SECTION("zoom 15x - spacing becomes 1.5 pixels -> all detailed") {
270	auto calls = runAlgorithm(events, endTime, SimpleMapper(15.0));
271	REQUIRE(calls.size() == 5);
272	CHECK(calls[0] == DrawCall{DrawCall::DETAILED, 150.0f, 151.5f, 1});
273	CHECK(calls[1] == DrawCall{DrawCall::DETAILED, 151.5f, 153.0f, 2});
274	CHECK(calls[2] == DrawCall{DrawCall::DETAILED, 153.0f, 154.5f, 3});
275	CHECK(calls[3] == DrawCall{DrawCall::DETAILED, 154.5f, 156.0f, 4});
276	CHECK(calls[4] == DrawCall{DrawCall::DETAILED, 156.0f, 225.0f, 5});
277	}
278
279	SECTION("zoom 0.01x (zoom out) - everything in same pixel -> single coarse") {
280	auto calls = runAlgorithm(events, endTime, SimpleMapper(0.01));
281	REQUIRE(calls.size() == 1);
282	CHECK(calls[0] == DrawCall{DrawCall::COARSE, 0.1f, 0.15f, 1, -1});
283	}
284	}
285
286	TEST_CASE("Timeline - complex realistic scenarios", "[timeline][integration]") {
287
288	SECTION("alternating dense and sparse regions") {
289	auto calls = runAlgorithm(
290	{{10.1, 1}, {10.2, 2}, {10.3, 3}, {20.0, 4},
291	{30.1, 5}, {30.2, 6}, {30.3, 7}, {40.0, 8},
292	{50.1, 9}, {50.2, 10}, {60.0, 11}},
293	70.0);
294	REQUIRE(calls.size() == 9);
295	CHECK(calls[0] == DrawCall{DrawCall::COARSE, 10.1f, 10.3f, 1, 4});
296	CHECK(calls[1] == DrawCall{DrawCall::DETAILED, 10.3f, 20.0f, 3});
297	CHECK(calls[2] == DrawCall{DrawCall::DETAILED, 20.0f, 30.1f, 4});
298	CHECK(calls[3] == DrawCall{DrawCall::COARSE, 30.1f, 30.3f, 5, 8});
299	CHECK(calls[4] == DrawCall{DrawCall::DETAILED, 30.3f, 40.0f, 7});
300	CHECK(calls[5] == DrawCall{DrawCall::DETAILED, 40.0f, 50.1f, 8});
301	CHECK(calls[6] == DrawCall{DrawCall::COARSE, 50.1f, 50.2f, 9, 11});
302	CHECK(calls[7] == DrawCall{DrawCall::DETAILED, 50.2f, 60.0f, 10});
303	CHECK(calls[8] == DrawCall{DrawCall::DETAILED, 60.0f, 70.0f, 11});
304	}
305
306	SECTION("large dataset with mixed regions") {
307	std::vector<Event> events;
308	// dense cluster at start (50 events, 0.1 apart)
309	for (int i = 0; i < 50; ++i) {
310	events.push_back({0.0 + i * 0.1, 1000 + i});
311	}
312	// well-spaced events
313	events.push_back({10.0, 2000});
314	events.push_back({15.5, 2001});
315	events.push_back({23.7, 2002});
316	events.push_back({35.2, 2003});
317	events.push_back({48.9, 2004});
318	// another dense cluster (30 events, 0.066 apart)
319	for (int i = 0; i < 30; ++i) {
320	events.push_back({50.0 + i * 0.066, 3000 + i});
321	}
322	// final well-spaced events
323	events.push_back({60.0, 4000});
324	events.push_back({75.5, 4001});
325	events.push_back({90.0, 4002});
326
327	auto calls = runAlgorithm(events, 100.0);
328	REQUIRE(calls.size() == 12);
329	CHECK(calls[0].type == DrawCall::COARSE); // first dense cluster
330	CHECK(calls[1].type == DrawCall::DETAILED);
331	// well-spaced section
332	CHECK(calls[2].type == DrawCall::DETAILED);
333	CHECK(calls[3].type == DrawCall::DETAILED);
334	CHECK(calls[4].type == DrawCall::DETAILED);
335	CHECK(calls[5].type == DrawCall::DETAILED);
336	CHECK(calls[6].type == DrawCall::DETAILED);
337	// second dense cluster
338	CHECK(calls[7].type == DrawCall::COARSE);
339	// final well-spaced section
340	CHECK(calls[8].type == DrawCall::DETAILED);
341	CHECK(calls[9].type == DrawCall::DETAILED);
342	CHECK(calls[10].type == DrawCall::DETAILED);
343	CHECK(calls[11].type == DrawCall::DETAILED);
344	}
345	}

Keyboard