/*
 * Copyright (C) 2022 StApps
 * This program is free software: you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the Free
 * Software Foundation, version 3.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
 * more details.
 *
 * You should have received a copy of the GNU General Public License along with
 * this program. If not, see <https://www.gnu.org/licenses/>.
 */
import {partition} from '@openstapps/collection-utils';

export interface RangeInfo<T> {
  elements: T[];
  start: number;
  end: number;
}

/**
 * Takes a list of ranges and groups by overlaps.
 */
export function groupRangeOverlaps<T>(
  ranges: T[],
  start: (range: T) => number,
  end: (range: T) => number,
): RangeInfo<T>[] {
  return internalGroupRangeOverlaps(
    ranges
      .sort((a, b) => start(a) - start(b))
      .map(range => ({
        elements: [range],
        start: start(range),
        end: end(range),
      })),
  )
    .map(range => ({
      ...range,
      elements: range.elements.sort((a, b) => start(a) - start(b)),
    }))
    .sort((a, b) => a.start - b.start);
}

/**
 *
 */
function within(a: number, b: number, c: number): boolean {
  return a > b && a < c;
}

/**
 *
 */
function equals(start1: number, end1: number, start2: number, end2: number) {
  return start1 === start2 && end1 === end2;
}

/**
 *
 */
function hasOverlap(a1: number, b1: number, a2: number, b2: number): boolean {
  return within(a1, a2, b2) || within(b1, a2, b2) || equals(a1, b1, a2, b2);
}

/**
 * Takes a list of ranges and groups by overlaps.
 */
function internalGroupRangeOverlaps<T>(input: RangeInfo<T>[]): RangeInfo<T>[] {
  const result: RangeInfo<T>[] = [];
  let ranges = [...input];
  let cumulativeReorders = 0;
  while (ranges.length > 0) {
    // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
    const range = ranges.pop()!;
    const [overlaps, rest] = partition(ranges, r => hasOverlap(range.start, range.end, r.start, r.end));
    cumulativeReorders += overlaps.length;
    ranges = rest;
    const elements = [range, ...overlaps];
    result.push({
      elements: elements.flatMap(it => it.elements),
      start: Math.min(...elements.map(it => it.start)),
      end: Math.max(...elements.map(it => it.end)),
    });
  }
  return cumulativeReorders === 0 ? result : internalGroupRangeOverlaps(result);
}
