union_span.ts

interface Span {
  start: number;
  end: number;
}

const removeRangeAndInsert = <T extends unknown>(
  arr: T[],
  from: number,
  until: number,
  newElem: T
): T[] => {
  return [
    ...(from <= 0 ? [] : arr.slice(0, from + 1)),
    newElem,
    ...(arr.length - 1 <= until ? [] : arr.slice(until + 1)),
  ];
};

const foldLeft = <A, B>(arr: A[], init: B, combine: (acc: B, elem: A) => B): B => {
  let acc = init;
  arr.forEach(a => {
    acc = combine(acc, a);
  })
  return acc;
}

const insertAndMergeSpan = (
  spanSeries: Span[],
  newSpan: Span
): Span[] => {
  if (spanSeries.length === 0) {
    return [newSpan];
  }
  if (newSpan.end < spanSeries[0].start) {
    return [newSpan, ...spanSeries];
  }
  if (spanSeries[spanSeries.length - 1].end < newSpan.start) {
    return [...spanSeries, newSpan];
  }

  let overlapStart = -1;
  let isStartOverlap = false;
  if (spanSeries[0].start <= newSpan.start) {
    const i = spanSeries.findIndex((si) => si.start <= newSpan.start);
    if (i !== -1) {
      overlapStart = i;
      isStartOverlap = newSpan.start <= spanSeries[i].end;
    } else {
      // 起こり得ない
      throw new Error("unreachable");
    }
  }

  let overlapEnd = spanSeries.length;
  let isEndOverlap = false;
  if (newSpan.end <= spanSeries[spanSeries.length - 1].end) {
    const searchEndFrom = isStartOverlap ? overlapStart : overlapStart + 1;
    for (let j = searchEndFrom; j < spanSeries.length; j += 1) {
      if (newSpan.end <= spanSeries[j].end) {
        overlapEnd = j;
        isEndOverlap = spanSeries[j].start <= newSpan.end;
        break;
      }
    }
  }

  const removeFrom = isStartOverlap ? overlapStart : overlapStart + 1;
  const removeUntil = isEndOverlap ? overlapEnd : overlapEnd - 1;
  const insertSpan = {
    start: isStartOverlap ? spanSeries[overlapStart].start : newSpan.start,
    end: isEndOverlap ? spanSeries[overlapEnd].end : newSpan.end,
  };

  return removeRangeAndInsert(spanSeries, removeFrom, removeUntil, insertSpan);
};

const unionedSpans = (spans: Span[]): Span[] => foldLeft(spans, [], insertAndMergeSpan);