1 files changed, 470 insertions, 0 deletions
diff --git a/apps/web/src/timeline/group-move/resolve-move.ts b/apps/web/src/timeline/group-move/resolve-move.ts
new file mode 100644
index 00000000..60940315
--- /dev/null
+++ b/apps/web/src/timeline/group-move/resolve-move.ts
@@ -0,0 +1,470 @@
+import type { SceneTracks } from "@/timeline";
+import { getTrackTypeForElementType } from "@/timeline/placement/compatibility";
+import { canPlaceTimeSpansOnTrack } from "@/timeline/placement/overlap";
+import type {
+	GroupMoveResult,
+	MoveGroup,
+	PlannedElementMove,
+	PlannedTrackCreation,
+} from "./types";
+import {
+	getDisplayTracks,
+	getTrackPlacementByDisplayIndex,
+	getTrackPlacementById,
+} from "./track-placement";
+
+type GroupMoveTarget =
+	| {
+			kind: "existingTrack";
+			anchorTargetTrackId: string;
+	  }
+	| {
+			kind: "newTracks";
+			anchorInsertIndex: number;
+			newTrackIds: string[];
+	  };
+
+export function resolveGroupMove({
+	group,
+	tracks,
+	anchorStartTime,
+	target,
+}: {
+	group: MoveGroup;
+	tracks: SceneTracks;
+	anchorStartTime: number;
+	target: GroupMoveTarget;
+}): GroupMoveResult | null {
+	if (target.kind === "newTracks") {
+		return resolveNewTrackMove({
+			group,
+			tracks,
+			anchorStartTime,
+			anchorInsertIndex: target.anchorInsertIndex,
+			newTrackIds: target.newTrackIds,
+		});
+	}
+
+	return resolveExistingTrackMove({
+		group,
+		tracks,
+		anchorStartTime,
+		anchorTargetTrackId: target.anchorTargetTrackId,
+	});
+}
+
+function resolveExistingTrackMove({
+	group,
+	tracks,
+	anchorStartTime,
+	anchorTargetTrackId,
+}: {
+	group: MoveGroup;
+	tracks: SceneTracks;
+	anchorStartTime: number;
+	anchorTargetTrackId: string;
+}): GroupMoveResult | null {
+	const anchorTargetPlacement = getTrackPlacementById({
+		tracks,
+		trackId: anchorTargetTrackId,
+	});
+	if (!anchorTargetPlacement) {
+		return null;
+	}
+
+	const targetTrackIdsByElementId = resolveExistingTrackIdsByElementId({
+		group,
+		tracks,
+		anchorTargetDisplayIndex: anchorTargetPlacement.displayIndex,
+	});
+	if (!targetTrackIdsByElementId) {
+		return null;
+	}
+
+	const clampedAnchorStartTime = clampAnchorStartTime({
+		group,
+		tracks,
+		anchorStartTime,
+		targetTrackIdsByElementId,
+	});
+
+	const moves = group.members.map((member) => ({
+		sourceTrackId: member.trackId,
+		targetTrackId:
+			targetTrackIdsByElementId.get(member.elementId) ?? member.trackId,
+		elementId: member.elementId,
+		newStartTime: clampedAnchorStartTime + member.timeOffset,
+	}));
+
+	if (!canApplyMovesToExistingTracks({ tracks, moves })) {
+		return null;
+	}
+
+	return {
+		moves,
+		createTracks: [],
+		targetSelection: moves.map(({ elementId, targetTrackId }) => ({
+			trackId: targetTrackId,
+			elementId,
+		})),
+	};
+}
+
+function resolveNewTrackMove({
+	group,
+	tracks,
+	anchorStartTime,
+	anchorInsertIndex,
+	newTrackIds,
+}: {
+	group: MoveGroup;
+	tracks: SceneTracks;
+	anchorStartTime: number;
+	anchorInsertIndex: number;
+	newTrackIds: string[];
+}): GroupMoveResult | null {
+	const sortedMembers = [...group.members].sort(
+		(leftMember, rightMember) =>
+			leftMember.displayIndex - rightMember.displayIndex,
+	);
+	const anchorMemberIndex = sortedMembers.findIndex(
+		(member) => member.elementId === group.anchor.elementId,
+	);
+	if (anchorMemberIndex < 0 || newTrackIds.length < sortedMembers.length) {
+		return null;
+	}
+
+	const hasAudioMember = sortedMembers.some(
+		(member) => member.trackSection === "audio",
+	);
+	const hasNonAudioMember = sortedMembers.some(
+		(member) => member.trackSection !== "audio",
+	);
+	if (hasAudioMember && hasNonAudioMember) {
+		return null;
+	}
+
+	const clampedAnchorStartTime = clampAnchorStartTime({
+		group,
+		tracks,
+		anchorStartTime,
+		targetTrackIdsByElementId: new Map(),
+	});
+	const blockStartIndex = hasAudioMember
+		? clampAudioInsertIndex({
+				tracks,
+				insertIndex: anchorInsertIndex - anchorMemberIndex,
+			})
+		: Math.max(
+				0,
+				Math.min(anchorInsertIndex - anchorMemberIndex, tracks.overlay.length),
+			);
+
+	const createTracks: PlannedTrackCreation[] = sortedMembers.map(
+		(member, memberIndex) => ({
+			id: newTrackIds[memberIndex],
+			type: getTrackTypeForElementType({
+				elementType: member.elementType,
+			}),
+			index: blockStartIndex + memberIndex,
+		}),
+	);
+	const moves = sortedMembers.map((member, memberIndex) => ({
+		sourceTrackId: member.trackId,
+		targetTrackId: newTrackIds[memberIndex],
+		elementId: member.elementId,
+		newStartTime: clampedAnchorStartTime + member.timeOffset,
+	}));
+
+	return {
+		moves,
+		createTracks,
+		targetSelection: moves.map(({ elementId, targetTrackId }) => ({
+			trackId: targetTrackId,
+			elementId,
+		})),
+	};
+}
+
+function clampAudioInsertIndex({
+	tracks,
+	insertIndex,
+}: {
+	tracks: SceneTracks;
+	insertIndex: number;
+}): number {
+	const minimumAudioInsertIndex = tracks.overlay.length + 1;
+	return Math.max(
+		minimumAudioInsertIndex,
+		Math.min(insertIndex, minimumAudioInsertIndex + tracks.audio.length),
+	);
+}
+
+function resolveExistingTrackIdsByElementId({
+	group,
+	tracks,
+	anchorTargetDisplayIndex,
+}: {
+	group: MoveGroup;
+	tracks: SceneTracks;
+	anchorTargetDisplayIndex: number;
+}): Map<string, string> | null {
+	const sortedMembers = [...group.members].sort(
+		(leftMember, rightMember) =>
+			leftMember.displayIndex - rightMember.displayIndex,
+	);
+	const anchorMemberIndex = sortedMembers.findIndex(
+		(member) => member.elementId === group.anchor.elementId,
+	);
+	if (anchorMemberIndex < 0) {
+		return null;
+	}
+
+	const targetTrackIdsByElementId = new Map<string, string>();
+	const usedTrackIds = new Set<string>();
+	const anchorPlacement = getTrackPlacementByDisplayIndex({
+		tracks,
+		displayIndex: anchorTargetDisplayIndex,
+	});
+	if (!anchorPlacement) {
+		return null;
+	}
+
+	targetTrackIdsByElementId.set(
+		group.anchor.elementId,
+		anchorPlacement.trackId,
+	);
+	usedTrackIds.add(anchorPlacement.trackId);
+
+	let upperBoundaryIndex = anchorTargetDisplayIndex;
+	for (
+		let memberIndex = anchorMemberIndex - 1;
+		memberIndex >= 0;
+		memberIndex -= 1
+	) {
+		const member = sortedMembers[memberIndex];
+		const targetPlacement = findCompatibleTrackPlacement({
+			tracks,
+			requiredTrackType: getTrackTypeForElementType({
+				elementType: member.elementType,
+			}),
+			startDisplayIndex: upperBoundaryIndex - 1,
+			step: -1,
+			usedTrackIds,
+		});
+		if (!targetPlacement) {
+			return null;
+		}
+
+		targetTrackIdsByElementId.set(member.elementId, targetPlacement.trackId);
+		usedTrackIds.add(targetPlacement.trackId);
+		upperBoundaryIndex = targetPlacement.displayIndex;
+	}
+
+	let lowerBoundaryIndex = anchorTargetDisplayIndex;
+	for (
+		let memberIndex = anchorMemberIndex + 1;
+		memberIndex < sortedMembers.length;
+		memberIndex += 1
+	) {
+		const member = sortedMembers[memberIndex];
+		const targetPlacement = findCompatibleTrackPlacement({
+			tracks,
+			requiredTrackType: getTrackTypeForElementType({
+				elementType: member.elementType,
+			}),
+			startDisplayIndex: lowerBoundaryIndex + 1,
+			step: 1,
+			usedTrackIds,
+		});
+		if (!targetPlacement) {
+			return null;
+		}
+
+		targetTrackIdsByElementId.set(member.elementId, targetPlacement.trackId);
+		usedTrackIds.add(targetPlacement.trackId);
+		lowerBoundaryIndex = targetPlacement.displayIndex;
+	}
+
+	return targetTrackIdsByElementId;
+}
+
+function findCompatibleTrackPlacement({
+	tracks,
+	requiredTrackType,
+	startDisplayIndex,
+	step,
+	usedTrackIds,
+}: {
+	tracks: SceneTracks;
+	requiredTrackType: ReturnType<typeof getTrackTypeForElementType>;
+	startDisplayIndex: number;
+	step: -1 | 1;
+	usedTrackIds: Set<string>;
+}) {
+	for (
+		let displayIndex = startDisplayIndex;
+		displayIndex >= 0 &&
+		displayIndex < tracks.overlay.length + 1 + tracks.audio.length;
+		displayIndex += step
+	) {
+		const placement = getTrackPlacementByDisplayIndex({
+			tracks,
+			displayIndex,
+		});
+		if (!placement) {
+			continue;
+		}
+
+		if (
+			placement.trackType === requiredTrackType &&
+			!usedTrackIds.has(placement.trackId)
+		) {
+			return placement;
+		}
+	}
+
+	return null;
+}
+
+function clampAnchorStartTime({
+	group,
+	tracks,
+	anchorStartTime,
+	targetTrackIdsByElementId,
+}: {
+	group: MoveGroup;
+	tracks: SceneTracks;
+	anchorStartTime: number;
+	targetTrackIdsByElementId: Map<string, string>;
+}): number {
+	const minimumAnchorStartTime = Math.max(
+		0,
+		...group.members.map((member) => -member.timeOffset),
+	);
+	let clampedAnchorStartTime = Math.max(
+		minimumAnchorStartTime,
+		anchorStartTime,
+	);
+
+	const memberOnMainTrack = group.members.find(
+		(member) =>
+			targetTrackIdsByElementId.get(member.elementId) === tracks.main.id,
+	);
+	if (!memberOnMainTrack) {
+		return clampedAnchorStartTime;
+	}
+
+	const movingElementIds = new Set(
+		group.members.map((member) => member.elementId),
+	);
+	const requestedMainStartTime =
+		clampedAnchorStartTime + memberOnMainTrack.timeOffset;
+	const earliestStationaryMainStartTime = tracks.main.elements
+		.filter((element) => !movingElementIds.has(element.id))
+		.reduce<number | null>((earliestStartTime, element) => {
+			if (earliestStartTime == null || element.startTime < earliestStartTime) {
+				return element.startTime;
+			}
+
+			return earliestStartTime;
+		}, null);
+	if (
+		earliestStationaryMainStartTime == null ||
+		requestedMainStartTime <= earliestStationaryMainStartTime
+	) {
+		clampedAnchorStartTime = Math.max(
+			minimumAnchorStartTime,
+			-memberOnMainTrack.timeOffset,
+		);
+	}
+
+	return clampedAnchorStartTime;
+}
+
+function canApplyMovesToExistingTracks({
+	tracks,
+	moves,
+}: {
+	tracks: SceneTracks;
+	moves: PlannedElementMove[];
+}): boolean {
+	const movingElementIds = new Set(moves.map((move) => move.elementId));
+	const sourceElements = new Map(
+		getDisplayTracks({ tracks }).flatMap((track) =>
+			track.elements.map((element) => [element.id, element] as const),
+		),
+	);
+	const movesByTargetTrackId = new Map<string, PlannedElementMove[]>();
+	for (const move of moves) {
+		const targetMoves = movesByTargetTrackId.get(move.targetTrackId) ?? [];
+		targetMoves.push(move);
+		movesByTargetTrackId.set(move.targetTrackId, targetMoves);
+	}
+
+	for (const [targetTrackId, targetMoves] of movesByTargetTrackId) {
+		const targetPlacement = getTrackPlacementById({
+			tracks,
+			trackId: targetTrackId,
+		});
+		if (!targetPlacement) {
+			return false;
+		}
+
+		const targetTrack = getDisplayTracks({ tracks })[
+			targetPlacement.displayIndex
+		];
+		if (!targetTrack) {
+			return false;
+		}
+
+		const timeSpans = targetMoves.map((move) => {
+			const sourceElement = sourceElements.get(move.elementId);
+			return {
+				startTime: move.newStartTime,
+				duration: sourceElement?.duration ?? 0,
+			};
+		});
+		if (hasOverlappingTimeSpans({ timeSpans })) {
+			return false;
+		}
+
+		if (
+			!canPlaceTimeSpansOnTrack({
+				track: {
+					elements: targetTrack.elements.filter(
+						(element) => !movingElementIds.has(element.id),
+					),
+				},
+				timeSpans,
+			})
+		) {
+			return false;
+		}
+	}
+
+	return true;
+}
+
+function hasOverlappingTimeSpans({
+	timeSpans,
+}: {
+	timeSpans: Array<{ startTime: number; duration: number }>;
+}): boolean {
+	const sortedSpans = [...timeSpans].sort(
+		(leftSpan, rightSpan) => leftSpan.startTime - rightSpan.startTime,
+	);
+
+	for (let spanIndex = 1; spanIndex < sortedSpans.length; spanIndex += 1) {
+		const previousSpan = sortedSpans[spanIndex - 1];
+		const currentSpan = sortedSpans[spanIndex];
+		if (
+			previousSpan.startTime + previousSpan.duration >
+			currentSpan.startTime
+		) {
+			return true;
+		}
+	}
+
+	return false;
+}