Range set

/**
 * A set of integers held as ranges: `[0, 1_000_000)` is two numbers, and
 * "everything but these three rows" is four ranges. It is what a selection over
 * a million rows needs, where a set of row numbers would be a million entries.
 *
 * A range set is a flat array of half-open ranges — `[start0, end0, start1, …]`
 * — kept sorted, disjoint and merged, so two equal sets are equal arrays. Every
 * operation returns a new array and leaves its argument alone, which is what
 * React state wants; membership is O(log r) in the number of ranges, a change or
 * an inversion O(r).
 *
 * Bounds are safe integers, to ±2^53; nothing here is narrowed to 32 bits, so
 * the number of ranges is limited only by the length of an array.
 */

export type RangeSet = readonly number[];

export const EMPTY_RANGE_SET: RangeSet = Object.freeze([]);

/** The index of the first range that ends after `value`, by binary search. */
function firstEndingAfter(set: RangeSet, value: number): number {
  let low = 0;
  let high = set.length / 2;
  while (low < high) {
    const middle = (low + high) >>> 1;
    if (set[middle * 2 + 1]! > value) high = middle;
    else low = middle + 1;
  }
  return low;
}

export function rangeSetHas(set: RangeSet, value: number): boolean {
  const index = firstEndingAfter(set, value) * 2;
  return index < set.length && set[index]! <= value;
}

/** The set with every integer in `[start, end)` added. */
export function rangeSetAdd(set: RangeSet, start: number, end: number): RangeSet {
  // Written this way round so that a bound that is not a number is no range either.
  if (!(start < end)) return set;
  // Ranges that touch the new one merge with it: the first ending at or after
  // `start`, through the last starting at or before `end`.
  const first = firstEndingAfter(set, start - 1);
  let last = first;
  while (last * 2 < set.length && set[last * 2]! <= end) last += 1;
  if (last === first) return [...set.slice(0, first * 2), start, end, ...set.slice(first * 2)];
  const mergedStart = Math.min(start, set[first * 2]!);
  const mergedEnd = Math.max(end, set[last * 2 - 1]!);
  if (last - first === 1 && mergedStart === set[first * 2] && mergedEnd === set[first * 2 + 1]) return set;
  return [...set.slice(0, first * 2), mergedStart, mergedEnd, ...set.slice(last * 2)];
}

/** The set with every integer in `[start, end)` removed. */
export function rangeSetRemove(set: RangeSet, start: number, end: number): RangeSet {
  if (!(start < end)) return set;
  const first = firstEndingAfter(set, start);
  let last = first;
  while (last * 2 < set.length && set[last * 2]! < end) last += 1;
  if (last === first) return set;
  const kept: number[] = [];
  // What the first and last overlapped ranges have outside the removed span.
  if (set[first * 2]! < start) kept.push(set[first * 2]!, start);
  if (set[last * 2 - 1]! > end) kept.push(end, set[last * 2 - 1]!);
  return [...set.slice(0, first * 2), ...kept, ...set.slice(last * 2)];
}

/** How many integers the set holds. */
export function rangeSetSize(set: RangeSet): number {
  let size = 0;
  for (let i = 0; i < set.length; i += 2) size += set[i + 1]! - set[i]!;
  return size;
}

/**
 * Every integer of `[start, end)` that the set does not hold: one search for
 * where `start` falls, then one pass over the ranges up to `end`.
 */
export function rangeSetInvert(set: RangeSet, start: number, end: number): RangeSet {
  if (!(start < end)) return EMPTY_RANGE_SET;
  const inverted: number[] = [];
  // Where the gap being measured began.
  let gap = start;
  for (let i = firstEndingAfter(set, start) * 2; i < set.length && gap < end; i += 2) {
    const rangeStart = set[i]!;
    if (rangeStart >= end) break;
    if (rangeStart > gap) inverted.push(gap, rangeStart);
    gap = set[i + 1]!;
  }
  if (gap < end) inverted.push(gap, end);
  return inverted;
}

/** The integers of the set, in order. */
export function* rangeSetValues(set: RangeSet): Generator<number, void, void> {
  for (let i = 0; i < set.length; i += 2) {
    for (let value = set[i]!; value < set[i + 1]!; value += 1) yield value;
  }
}