when-am-i / files / src / utils / lanes.ts

lanes.ts

1	// Pack time intervals into non-overlapping horizontal lanes — the trick the
2	// Wikipedia band-member timelines use to show concurrent roles as parallel
3	// stripes instead of overpainting. Greedy: sweep by start time, reuse the first
4	// lane whose last interval has already ended, else open a new lane.
5
6	export interface Laned<T> {
7	item: T;
8	lane: number;
9	}
10
11	export function assignLanes<T>(
12	items: T[],
13	startOf: (item: T) => number,
14	endOf: (item: T) => number,
15	): { lanes: Laned<T>[]; count: number } {
16	const ordered = items
17	.map((item, i) => ({ item, i }))
18	.sort((a, b) => {
19	const sa = startOf(a.item);
20	const sb = startOf(b.item);
21	if (sa < sb) return -1;
22	if (sa > sb) return 1;
23	return a.i - b.i; // stable for equal starts
24	});
25
26	const laneEnds: number[] = [];
27	const lanes: Laned<T>[] = [];
28	for (const { item } of ordered) {
29	const start = startOf(item);
30	// Half-open intervals: a lane is free if its last interval ended at or
31	// before this one starts.
32	let lane = laneEnds.findIndex((end) => end <= start);
33	if (lane === -1) {
34	lane = laneEnds.length;
35	laneEnds.push(endOf(item));
36	} else {
37	laneEnds[lane] = endOf(item);
38	}
39	lanes.push({ item, lane });
40	}
41
42	return { lanes, count: laneEnds.length };
43	}