import * as array from "@heydovetail/array";

export interface Range {
  from: number;
  to: number;
}

/**
 * Walk a set of ranges, and callback for each contiguous overlapping chunk of ranges.
 *
 * @param ranges Array of ranges, sorted by `from`
 * @param callback
 */
export function walk<T extends Range>(
  ranges: ReadonlyArray<T>,
  callback: (range: Readonly<Range>, active: ReadonlyArray<T>) => void
): void {
  const rangesCount = ranges.length;

  // Active, sorted by `to`
  let active: ReadonlyArray<T> = [];
  let remainingIndex = 0;
  let from = 0;

  function injestRanges() {
    // No active, so take from remaining that have the same `.from` and put them
    // in active.
    const sliceStart = remainingIndex;
    let sliceEnd = sliceStart + 1;
    from = ranges[sliceStart].from;
    while (sliceEnd < rangesCount && ranges[sliceEnd].from === from) {
      sliceEnd++;
    }
    for (const range of ranges.slice(sliceStart, sliceEnd)) {
      active = array.sortedInsert(active, range, array.sortComparatorAsc(range => range.to));
    }
    remainingIndex = sliceEnd;
  }

  function emitActiveChunk() {
    let count = 1;
    const to = active[0].to;
    while (count < active.length && active[count].to === to) {
      count++;
    }
    callback({ from, to }, array.sorted(active, range => range.from, array.sortComparatorAsc));
    active = active.slice(count);
    from = to;
  }

  while (true) {
    // Find the chunk boundary, either the first terminating active range `to`,
    // or a starting range `from`.

    if (remainingIndex === rangesCount) {
      if (active.length === 0) {
        // All ranges have been consumed
        return;
      }

      // Only active ranges remain, emit all that have the same `.to`.
      // Find the index of the last range with identical `.to`
      emitActiveChunk();
    } else if (active.length === 0) {
      // No active, so take from remaining that have the same `.from` and put them
      // in active.
      injestRanges();
    } else if (ranges[remainingIndex].from < active[0].to) {
      // A range starts comes first, so we need to emit all actives first, and
      // then add remaining ranges with same `.from`.
      callback({ from, to: ranges[remainingIndex].from }, active);
      injestRanges();
    } else {
      emitActiveChunk();
    }
  }
}