refactor: unify element updates into pipeline and centralize ripple

4 files changed, 358 insertions, 0 deletions

diff --git a/apps/web/src/lib/ripple/apply.ts b/apps/web/src/lib/ripple/apply.ts
new file mode 100644
index 00000000..098a0247
--- /dev/null
+++ b/apps/web/src/lib/ripple/apply.ts
@@ -0,0 +1,65 @@
+import type { TimelineTrack } from "@/lib/timeline/types";
+import { rippleShiftElements } from "./shift";
+
+export interface RippleAdjustment {
+	trackId: string;
+	afterTime: number;
+	shiftAmount: number;
+}
+
+export function applyRippleAdjustments({
+	tracks,
+	adjustments,
+}: {
+	tracks: TimelineTrack[];
+	adjustments: RippleAdjustment[];
+}): TimelineTrack[] {
+	if (adjustments.length === 0) {
+		return tracks;
+	}
+
+	const adjustmentsByTrack = new Map<string, RippleAdjustment[]>();
+	for (const adjustment of adjustments) {
+		const trackAdjustments = adjustmentsByTrack.get(adjustment.trackId) ?? [];
+		trackAdjustments.push(adjustment);
+		adjustmentsByTrack.set(adjustment.trackId, trackAdjustments);
+	}
+
+	return tracks.map((track) =>
+		applyTrackRippleAdjustments({
+			track,
+			adjustments: adjustmentsByTrack.get(track.id) ?? [],
+		}),
+	);
+}
+
+function applyTrackRippleAdjustments<
+	TElement extends TimelineTrack["elements"][number],
+	TTrack extends TimelineTrack & { elements: TElement[] },
+>({
+	track,
+	adjustments,
+}: {
+	track: TTrack;
+	adjustments: RippleAdjustment[];
+}): TTrack {
+	if (adjustments.length === 0) {
+		return track;
+	}
+
+	const sortedAdjustments = [...adjustments].sort(
+		(firstAdjustment, secondAdjustment) =>
+			secondAdjustment.afterTime - firstAdjustment.afterTime,
+	);
+
+	let elements: TElement[] = track.elements;
+	for (const adjustment of sortedAdjustments) {
+		elements = rippleShiftElements({
+			elements,
+			afterTime: adjustment.afterTime,
+			shiftAmount: adjustment.shiftAmount,
+		});
+	}
+
+	return { ...track, elements };
+}
diff --git a/apps/web/src/lib/ripple/diff.ts b/apps/web/src/lib/ripple/diff.ts
new file mode 100644
index 00000000..8a9730e1
--- /dev/null
+++ b/apps/web/src/lib/ripple/diff.ts
@@ -0,0 +1,272 @@
+import { TIME_EPSILON_SECONDS } from "@/constants/animation-constants";
+import type { TimelineElement, TimelineTrack } from "@/lib/timeline/types";
+import type { RippleAdjustment } from "./apply";
+
+interface Interval {
+	startTime: number;
+	endTime: number;
+}
+
+interface ElementSpan extends Interval {
+	id: string;
+}
+
+export function computeRippleAdjustments({
+	beforeTracks,
+	afterTracks,
+}: {
+	beforeTracks: TimelineTrack[];
+	afterTracks: TimelineTrack[];
+}): RippleAdjustment[] {
+	const afterTracksById = new Map(afterTracks.map((track) => [track.id, track]));
+	const allAfterElementIds = new Set(
+		afterTracks.flatMap((track) => track.elements.map((element) => element.id)),
+	);
+
+	return beforeTracks.flatMap((beforeTrack): RippleAdjustment[] =>
+		computeTrackRippleAdjustments({
+			trackId: beforeTrack.id,
+			beforeElements: beforeTrack.elements,
+			afterElements: afterTracksById.get(beforeTrack.id)?.elements ?? [],
+			allAfterElementIds,
+		}),
+	);
+}
+
+function computeTrackRippleAdjustments({
+	trackId,
+	beforeElements,
+	afterElements,
+	allAfterElementIds,
+}: {
+	trackId: string;
+	beforeElements: TimelineElement[];
+	afterElements: TimelineElement[];
+	allAfterElementIds: Set<string>;
+}): RippleAdjustment[] {
+	const beforeElementsById = buildElementSpanMap({ elements: beforeElements });
+	const afterElementsById = buildElementSpanMap({ elements: afterElements });
+	const { vacatedIntervals, joinedIntervals } = collectTrackIntervals({
+		beforeElementsById,
+		afterElementsById,
+		allAfterElementIds,
+	});
+	const freedIntervals = subtractIntervalSets({
+		sourceIntervals: vacatedIntervals,
+		overlappingIntervals: joinedIntervals,
+	});
+
+	return buildAdjustments({ trackId, intervals: freedIntervals });
+}
+
+function buildElementSpanMap({
+	elements,
+}: {
+	elements: TimelineElement[];
+}): Map<string, ElementSpan> {
+	return new Map(
+		elements.map((element) => [
+			element.id,
+			{
+				id: element.id,
+				startTime: element.startTime,
+				endTime: element.startTime + element.duration,
+			},
+		]),
+	);
+}
+
+function collectTrackIntervals({
+	beforeElementsById,
+	afterElementsById,
+	allAfterElementIds,
+}: {
+	beforeElementsById: Map<string, ElementSpan>;
+	afterElementsById: Map<string, ElementSpan>;
+	allAfterElementIds: Set<string>;
+}): {
+	vacatedIntervals: Interval[];
+	joinedIntervals: Interval[];
+} {
+	const vacatedIntervals: Interval[] = [];
+	const joinedIntervals: Interval[] = [];
+
+	for (const beforeElement of beforeElementsById.values()) {
+		const afterElement = afterElementsById.get(beforeElement.id);
+		if (!afterElement) {
+			const wasMovedToAnotherTrack = allAfterElementIds.has(beforeElement.id);
+			if (!wasMovedToAnotherTrack) {
+				pushInterval({
+					intervals: vacatedIntervals,
+					startTime: beforeElement.startTime,
+					endTime: beforeElement.endTime,
+				});
+			}
+			continue;
+		}
+
+		if (beforeElement.endTime > afterElement.endTime + TIME_EPSILON_SECONDS) {
+			pushInterval({
+				intervals: vacatedIntervals,
+				startTime: afterElement.endTime,
+				endTime: beforeElement.endTime,
+			});
+		}
+	}
+
+	for (const afterElement of afterElementsById.values()) {
+		if (beforeElementsById.has(afterElement.id)) {
+			continue;
+		}
+
+		pushInterval({
+			intervals: joinedIntervals,
+			startTime: afterElement.startTime,
+			endTime: afterElement.endTime,
+		});
+	}
+
+	return {
+		vacatedIntervals: normalizeIntervals({ intervals: vacatedIntervals }),
+		joinedIntervals: normalizeIntervals({ intervals: joinedIntervals }),
+	};
+}
+
+function buildAdjustments({
+	trackId,
+	intervals,
+}: {
+	trackId: string;
+	intervals: Interval[];
+}): RippleAdjustment[] {
+	return intervals.flatMap((interval): RippleAdjustment[] => {
+		const shiftAmount = interval.endTime - interval.startTime;
+		if (shiftAmount <= TIME_EPSILON_SECONDS) {
+			return [];
+		}
+
+		return [
+			{
+				trackId,
+				afterTime: interval.endTime,
+				shiftAmount,
+			},
+		];
+	});
+}
+
+function subtractIntervalSets({
+	sourceIntervals,
+	overlappingIntervals,
+}: {
+	sourceIntervals: Interval[];
+	overlappingIntervals: Interval[];
+}): Interval[] {
+	const normalizedSourceIntervals = normalizeIntervals({
+		intervals: sourceIntervals,
+	});
+	const normalizedOverlappingIntervals = normalizeIntervals({
+		intervals: overlappingIntervals,
+	});
+
+	return normalizedSourceIntervals.flatMap((sourceInterval) =>
+		subtractSingleInterval({
+			sourceInterval,
+			overlappingIntervals: normalizedOverlappingIntervals,
+		}),
+	);
+}
+
+function normalizeIntervals({
+	intervals,
+}: {
+	intervals: Interval[];
+}): Interval[] {
+	const validIntervals: Interval[] = [];
+	for (const interval of intervals) {
+		pushInterval({
+			intervals: validIntervals,
+			startTime: interval.startTime,
+			endTime: interval.endTime,
+		});
+	}
+
+	const sortedIntervals = validIntervals.sort(
+		(leftInterval, rightInterval) =>
+			leftInterval.startTime - rightInterval.startTime,
+	);
+
+	if (sortedIntervals.length === 0) {
+		return [];
+	}
+
+	const mergedIntervals: Interval[] = [{ ...sortedIntervals[0] }];
+	for (const interval of sortedIntervals.slice(1)) {
+		const previousInterval = mergedIntervals[mergedIntervals.length - 1];
+		if (interval.startTime <= previousInterval.endTime + TIME_EPSILON_SECONDS) {
+			previousInterval.endTime = Math.max(
+				previousInterval.endTime,
+				interval.endTime,
+			);
+			continue;
+		}
+
+		mergedIntervals.push({ ...interval });
+	}
+
+	return mergedIntervals;
+}
+
+function subtractSingleInterval({
+	sourceInterval,
+	overlappingIntervals,
+}: {
+	sourceInterval: Interval;
+	overlappingIntervals: Interval[];
+}): Interval[] {
+	let remainingIntervals: Interval[] = [{ ...sourceInterval }];
+
+	for (const overlappingInterval of overlappingIntervals) {
+		remainingIntervals = remainingIntervals.flatMap((remainingInterval) => {
+			if (
+				overlappingInterval.endTime <=
+					remainingInterval.startTime + TIME_EPSILON_SECONDS ||
+				overlappingInterval.startTime >=
+					remainingInterval.endTime - TIME_EPSILON_SECONDS
+			) {
+				return [remainingInterval];
+			}
+
+			const nextIntervals: Interval[] = [];
+			pushInterval({
+				intervals: nextIntervals,
+				startTime: remainingInterval.startTime,
+				endTime: overlappingInterval.startTime,
+			});
+			pushInterval({
+				intervals: nextIntervals,
+				startTime: overlappingInterval.endTime,
+				endTime: remainingInterval.endTime,
+			});
+			return nextIntervals;
+		});
+
+		if (remainingIntervals.length === 0) {
+			return [];
+		}
+	}
+
+	return remainingIntervals;
+}
+
+function pushInterval({
+	intervals,
+	startTime,
+	endTime,
+}: { intervals: Interval[]; startTime: number; endTime: number }): void {
+	if (endTime - startTime <= TIME_EPSILON_SECONDS) {
+		return;
+	}
+
+	intervals.push({ startTime, endTime });
+}
diff --git a/apps/web/src/lib/ripple/index.ts b/apps/web/src/lib/ripple/index.ts
new file mode 100644
index 00000000..5a14de64
--- /dev/null
+++ b/apps/web/src/lib/ripple/index.ts
@@ -0,0 +1,4 @@
+export type { RippleAdjustment } from "./apply";
+export { applyRippleAdjustments } from "./apply";
+export { computeRippleAdjustments } from "./diff";
+export { rippleShiftElements } from "./shift";
diff --git a/apps/web/src/lib/ripple/shift.ts b/apps/web/src/lib/ripple/shift.ts
new file mode 100644
index 00000000..03ab4a67
--- /dev/null
+++ b/apps/web/src/lib/ripple/shift.ts
@@ -0,0 +1,17 @@
+import type { TimelineElement } from "@/lib/timeline/types";
+
+export function rippleShiftElements<TElement extends TimelineElement>({
+	elements,
+	afterTime,
+	shiftAmount,
+}: {
+	elements: TElement[];
+	afterTime: number;
+	shiftAmount: number;
+}): TElement[] {
+	return elements.map((element) =>
+		element.startTime >= afterTime
+			? ({ ...element, startTime: element.startTime - shiftAmount } as TElement)
+			: element,
+	);
+}