#ifndef TIMELINE_HH

#define TIMELINE_HH

#include <algorithm>

#include <cmath>

#include <concepts>

#include <optional>

#include <span>

namespace openmsx {

// concept for types that have a "time" member of type Time

template<typename T, typename Time>

concept HasTime = requires(T t) {

	{ t.time } -> std::convertible_to<Time>;

};

// concept for timeline coordinate mapper (time <-> screen space)

template<typename T, typename Time>

concept TimelineMapper = requires(T c, Time time, float x) {

	{ c.timeToX(time) } -> std::convertible_to<float>;

	{ c.xToTime(x) } -> std::convertible_to<Time>;

};

/**

 * Classifies and processes timeline events as either DETAILED or COARSE regions.

 *

 * Motivation: When drawing millions of events on a limited screen (e.g., 1000 pixels wide),

 * many events will be smaller than a single pixel. This algorithm efficiently handles this by:

 * - Drawing individual events where there's space (DETAILED regions)

 * - Grouping dense clusters into coarse representations (COARSE regions)

 * This allows rendering large datasets (e.g., 10M events) efficiently on any zoom level.

 *

 * This function uses a streaming algorithm to efficiently process events on a zoomable timeline,

 * deciding for each event whether it should be processed individually (DETAILED) or grouped into

 * a coarse region (COARSE) based on available screen space.

 *

 * Algorithm:

 * - Iterates through events in a single pass (streaming)

 * - For each event, calculates its screen-space width (spacing to next event)

 * - If spacing > threshold: process event as DETAILED

 * - If spacing <= threshold: accumulates into a COARSE region and uses binary search

 *   to jump to the next pixel boundary, skipping dense clusters efficiently

 * - Merges adjacent coarse regions into single callback invocations

 *

 * Time Complexity: O(R log E)

 * - R = number of output regions (detailed + coarse)

 * - E = number of events

 * - R is bounded by: min(E, X) where X = number of screen pixels covered

 * - Best case: R = E (all events well-spaced, all detailed)

 * - Worst case: R = X (dense events, one coarse region per pixel)

 * - The binary search allows efficient skipping of dense event clusters

 *

 * @tparam Time       Time type (e.g., int, std::chrono::duration, EmuTime)

 * @tparam Event      Event type (must satisfy HasTime<Event, Time> concept)

 * @tparam Mapper     Mapper type (must satisfy TimelineMapper<Mapper, Time> concept)

 * @param events      Sorted list of events (must be sorted by time, ascending)

 * @param endTime     End time of the visible timeline (must be >= last event time)

 * @param mapper      Coordinate mapper (time <-> screen space)

 * @param onDetailed  Callable invoked for detailed events: (float fromX, float toX, const Event&)

 *                    - Called when an event has > threshold pixels of space

 *                    - [fromX, toX) defines the half-open interval in screen space

 * @param onCoarse    Callable invoked for coarse regions: (float fromX, float toX)

 *                    - Called when multiple events are densely packed (spacing <= threshold)

 *                    - Adjacent coarse pixels are automatically merged into single calls

 *                    - [fromX, toX) defines the half-open interval in screen space

 * @param threshold   Minimum spacing (in pixels) to process event as detailed (default: 1.0)

 *                    - spacing > threshold → DETAILED

 *                    - spacing <= threshold → COARSE

 *

 * Preconditions:

 * - events must be sorted by time (ascending order)

 * - endTime >= events.back().time (if events not empty)

 */

template<typename Time, HasTime<Time> Event, TimelineMapper<Time> Mapper>

void processTimeline(

	std::span<const Event> events,

	Time endTime,

	const Mapper& mapper,

	std::invocable<float, float, const Event&> auto onDetailed,

	std::invocable<float, float, typename std::span<const Event>::iterator, typename std::span<const Event>::iterator> auto onCoarse,

	float threshold = 1.0)

{

	if (events.empty()) return;

	std::optional<float> coarseStart; // start of current coarse region

	decltype(events.begin()) coarseBeginIt;

	auto flushCoarse = [&](float endPixel, auto endIt) {

		if (coarseStart) {

			onCoarse(*coarseStart, endPixel, coarseBeginIt, endIt);

			coarseStart = {};

			coarseBeginIt = {};

		}

	};

	auto currentIt = events.begin();

	auto currentPixel = mapper.timeToX(currentIt->time);

	while (currentIt != events.end()) {

		// get next time (either next event or endTime)

		const auto nextIt = std::next(currentIt);

		const auto nextTimestamp = (nextIt != events.end())

		                         ? nextIt->time

		                         : endTime;

		const auto nextPixel = mapper.timeToX(nextTimestamp);

		const auto spacing = nextPixel - currentPixel; // event spans [currentPixel, nextPixel)

		if (spacing > threshold) {

			// DETAILED: flush pending coarse region first

			flushCoarse(currentPixel, nextIt);

			onDetailed(currentPixel, nextPixel, *currentIt);

			currentIt = nextIt; // reuse for next iteration

			currentPixel = nextPixel;

		} else {

			// COARSE: start/continue coarse region

			if (!coarseStart) {

				coarseStart = currentPixel;

				coarseBeginIt = currentIt;

			}

			// binary search: jump to next integer pixel boundary

			const auto targetPixel = std::floor(currentPixel) + 1.0f;

			const auto targetTime = mapper.xToTime(targetPixel);

			// Find last event at or before the next pixel boundary.

			// upper_bound gives first event > targetTime, then back up one.

			// Important: Start from next event to ensure we make progress.

			if (auto it = std::ranges::upper_bound(nextIt, events.end(), targetTime, {}, &Event::time);

			    it != nextIt) {

				currentIt = std::prev(it);

				currentPixel = mapper.timeToX(currentIt->time);

			} else {

				// no more events in this pixel, jump to next event

				currentIt = nextIt;

				currentPixel = nextPixel;

			}

		}

	}

	// flush final coarse region if any

	flushCoarse(currentPixel, currentIt); // at this point: currentPixel == mapper.timeToX(endTime)

}

} // namespace openmsx

#endif