interval.spec.ts

import * as fc from "fast-check";
import { pipe } from "fp-ts/lib/function";
import {
  fromArray,
  groupSort,
  map,
  NonEmptyArray,
} from "fp-ts/lib/NonEmptyArray";
import { Ord, ordDate, ordNumber } from "fp-ts/lib/Ord";
import {
  chunksOf,
  comprehension,
  dropLeft,
  head,
  last,
  snoc,
  sort,
} from "fp-ts/lib/Array";
import { Interval, mergeIntervals } from "../../src/lib/interval";
import { typeIs } from "../../src/lib/ts-utils";
import { isNone, isSome } from "fp-ts/lib/Option";
import { assert, notNull } from "../../src/lib/assert";

type TestCase<T> = {
  input: NonEmptyArray<Interval<T>>;
  output: NonEmptyArray<Interval<T>>;
};

// Generate test case with many subsequent intervals
//
// Example input and output
// xs: [1,2,3,4]
// input: [[1,2], [2,3], [3,4]]
// output: [[1,4]]
const mkArbitrarySubsequentIntervals = <T>(
  genMin: fc.Arbitrary<T>,
  genMiddle: fc.Arbitrary<T>,
  genMax: fc.Arbitrary<T>,
  ord: Ord<T>
): fc.Arbitrary<TestCase<T>> => {
  return fc.tuple(genMin, fc.array(genMiddle), genMax).map(
    ([a, xs, b]): TestCase<T> => {
      const { start, intervals } = sort(ord)(xs).reduce(
        (acc, x) => ({
          start: x,
          intervals: [...acc.intervals, { start: acc.start, end: x }],
        }),
        { start: a, intervals: typeIs<Interval<T>[]>([]) }
      );

      const input = snoc(intervals, { start, end: b });
      const output: NonEmptyArray<Interval<T>> = [{ start: a, end: b }];
      return {
        input,
        output,
      };
    }
  );
};

// Generate test case where there are no overlaps
//
// Example input and output
// xs: [1,2,3,4,5]
// input: [[1,2], [3,4]]
// output: [[1,2], [3,4]]
const mkArbitraryNonOverlappingIntervals = <T>(
  genVal: fc.Arbitrary<T>,
  ord: Ord<T>
): fc.Arbitrary<TestCase<T>> => {
  return fc
    .array(genVal)
    .map((xs): null | TestCase<T> => {
      const sortedUniqueValues = groupSort(ord)(xs).map((_) => _[0]);
      const intervals = chunksOf(2)(sortedUniqueValues)
        .map((chunk) =>
          chunk[0] != null && chunk[1] != null
            ? { start: chunk[0], end: chunk[1] }
            : null
        )
        .filter(notNull);
      const intervalsNEA = fromArray(intervals);
      if (isNone(intervalsNEA)) {
        return null;
      }
      return {
        input: intervalsNEA.value,
        output: intervalsNEA.value,
      };
    })
    .filter(notNull);
};

// Generate test case where there are overlaps
//
// Example input and output
// xs: [3, 4, 2, 1]
// input: [[1,3], [2,4]]
// output: [1,4]
const mkArbitraryOverlappingIntervals = <T>(
  genVal: fc.Arbitrary<T>,
  ord: Ord<T>
): fc.Arbitrary<TestCase<T>> => {
  return fc
    .array(genVal, { minLength: 4 })
    .map((xs): null | TestCase<T> => {
      const sortedValues = sort(ord)(xs);
      const intervals = comprehension(
        [sortedValues, dropLeft(2)(sortedValues)],
        (n, nPlus2) => ({
          start: n,
          end: nPlus2,
        })
      );
      const headElem = head(sortedValues);
      const lastElem = last(sortedValues);
      const intervalsNEA = fromArray(intervals);

      assert(
        isSome(headElem) && isSome(lastElem) && isSome(intervalsNEA),
        "isSome(headElem) && isSome(lastElem) && isSome(intervalsNEA)"
      );

      const output: NonEmptyArray<Interval<T>> = [
        { start: headElem.value, end: lastElem.value },
      ];

      return {
        input: intervalsNEA.value,
        output,
      };
    })
    .filter(notNull);
};

const minNum = 0;
const maxNum = 100;
const genNum = fc.integer({ min: minNum, max: maxNum });
const minDate = new Date(1995, 11, 17, 3, 24, 0);
const maxDate = new Date(2030, 11, 17, 3, 24, 0);
const genDate = fc.date({ min: minDate, max: maxDate });

const test = <T>(name: string, gen: fc.Arbitrary<TestCase<T>>, ord: Ord<T>) => {
  it(name, () => {
    fc.assert(
      fc.property(gen, (_) => {
        expect(mergeIntervals(ord, _.output)).toEqual(_.output);
      })
    );
  });
};

describe("Interval", () => {
  describe("mergeIntervals", () => {
    it("example 1", () => {
      expect(
        mergeIntervals(ordNumber, [
          { start: 1, end: 3 },
          { start: 2, end: 6 },
          { start: 8, end: 10 },
          { start: 15, end: 18 },
        ])
      ).toEqual([
        { start: 1, end: 6 },
        { start: 8, end: 10 },
        { start: 15, end: 18 },
      ]);
      // Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
    });

    it("example 2", () => {
      expect(
        mergeIntervals(ordNumber, [
          { start: 1, end: 4 },
          { start: 4, end: 5 },
        ])
      ).toEqual([{ start: 1, end: 5 }]);
      // Explanation: Intervals [1,4] and [4,5] are considered overlapping.
    });

    test(
      "Subsequent Intervals: Num",
      mkArbitrarySubsequentIntervals(
        fc.constant(minNum),
        genNum,
        fc.constant(maxNum),
        ordNumber
      ),
      ordNumber
    );

    test(
      "Subsequent Intervals: Date",
      mkArbitrarySubsequentIntervals(
        fc.constant(minDate),
        genDate,
        fc.constant(maxDate),
        ordDate
      ),
      ordDate
    );

    test(
      "Non Overlapping Intervals: Num",
      mkArbitraryNonOverlappingIntervals(genNum, ordNumber),
      ordNumber
    );

    test(
      "Non Overlapping Intervals: Date",
      mkArbitraryNonOverlappingIntervals(genDate, ordDate),
      ordDate
    );

    test(
      "Overlapping Intervals: Num",
      mkArbitraryOverlappingIntervals(genNum, ordNumber),
      ordNumber
    );

    test(
      "Overlapping Intervals: Date",
      mkArbitraryOverlappingIntervals(genDate, ordDate),
      ordDate
    );
  });
});

interval.ts

import { snoc } from "fp-ts/lib/Array";
import { NonEmptyArray, sort, uncons } from "fp-ts/lib/NonEmptyArray";
import * as Ord from "fp-ts/lib/Ord";
import { reduceNEA } from "./non-empty-array";

/**
 * Interval is generic representation of anything that has start and end
 * It could be date/time/datetime interval or it could be range between numbers etc.
 */
export type Interval<T> = {
  start: T;
  end: T;
};

/**
 * Merge intervals of any type `T` together.
 * If the Interval overlap then combine them into a single `Interval`
 * otherwise add them separately to the returned array
 */
export const mergeIntervals = <T>(
  ord: Ord.Ord<T>,
  intervals: NonEmptyArray<Interval<T>>
): NonEmptyArray<Interval<T>> => {
  const lessThenOrEqual = Ord.leq(ord);
  const maximum = Ord.max(ord);
  const equals = ord.equals;

  const ordByStart = Ord.contramap((a: Interval<T>) => a.start)(ord);
  const sortedByStart = sort(ordByStart)(intervals);
  const x = reduceNEA(
    sortedByStart,
    (val) => {
      // NOTE: Linked List could be used here to make this super efficient
      const init: Interval<T>[] = [];
      return {
        current: val,
        init,
      };
    },
    (acc, val) => {
      if (
        equals(acc.current.start, val.start) ||
        lessThenOrEqual(val.start, acc.current.end)
      ) {
        const current: Interval<T> = {
          start: acc.current.start,
          end: maximum(acc.current.end, val.end),
        };

        return {
          current,
          init: acc.init,
        };
      }

      const last: Interval<T> = {
        start: acc.current.start,
        end: acc.current.end,
      };

      return {
        current: val,
        init: [...acc.init, last],
      };
    }
  );
  return snoc(x.init, x.current);
};