Prompt for Four Kitchens JavaScript Practice Group 2020.05.20

removeOverlap.js

/* @flow */

export type Range<P> = {
  payload: P,
  start: number,
  end: number,
  priority: number,
};

/**
 * Given a set of ranges, remove any overlapping ranges giving preference to
 * those with a higher priority value.
 *
 * NOTE: ranges with invalid start/end values (start > end) are filtered out.
 *
 * @param ranges An array of ranges with the following properties:
 * @param ranges[].start The lower bound of the range.
 * @param ranges[].end The upper bound of the range.
 * @param ranges[].payload The value associated with the range. This prevents
 *   the payload from requiring the properties start, end, and priority.
 * @param ranges[].priority The numeric value which determines which overlapping
 *   range will be given preference. Ranges with higher priority values are
 *   preferred over those with lower priority values.
 */
module.exports = function removeOverlap<P>(
  ranges: Array<Range<P>>
): Array<Range<P>> {
  return ranges;
};

removeOverlap.test.js

const removeOverlap = require('./removeOverlap');

describe('removeOverlap', () => {
  it('removes exactly overlapping ranges', () => {
    expect(
      removeOverlap([
        { payload: 'one', start: 1, end: 3, priority: 1 },
        { payload: 'two', start: 1, end: 3, priority: 2 },
      ])
    ).toEqual([{ payload: 'two', start: 1, end: 3, priority: 2 }]);
  });
  it('removes a range extending the lower bound of another range', () => {
    expect(
      removeOverlap([
        { payload: 'one', start: 0, end: 3, priority: 1 },
        { payload: 'two', start: 1, end: 4, priority: 2 },
      ])
    ).toEqual([{ payload: 'two', start: 1, end: 4, priority: 2 }]);
  });
  it('removes a range extending the upper bound of another range', () => {
    expect(
      removeOverlap([
        { payload: 'two', start: 0, end: 3, priority: 2 },
        { payload: 'one', start: 1, end: 4, priority: 1 },
      ])
    ).toEqual([{ payload: 'two', start: 0, end: 3, priority: 2 }]);
  });
  it('removes more than two overlapping ranges', () => {
    expect(
      removeOverlap([
        { payload: 'one', start: 1, end: 3, priority: 1 },
        { payload: 'three', start: 1, end: 3, priority: 3 },
        { payload: 'two', start: 1, end: 3, priority: 2 },
      ])
    ).toEqual([{ payload: 'three', start: 1, end: 3, priority: 3 }]);
  });
  it('removes a range containing another range', () => {
    expect(
      removeOverlap([
        { payload: 'two', start: 1, end: 3, priority: 2 },
        { payload: 'one', start: 0, end: 4, priority: 1 },
      ])
    ).toEqual([{ payload: 'two', start: 1, end: 3, priority: 2 }]);
  });
  it('removes a range contained in another range', () => {
    expect(
      removeOverlap([
        { payload: 'one', start: 1, end: 3, priority: 1 },
        { payload: 'two', start: 0, end: 4, priority: 2 },
      ])
    ).toEqual([{ payload: 'two', start: 0, end: 4, priority: 2 }]);
  });
  it('removes multiple groups of overlapping ranges', () => {
    expect(
      removeOverlap([
        { payload: 'one', start: 0, end: 3, priority: 1 },

        // overlapping
        { payload: 'eight', start: 3, end: 6, priority: 8 },
        { payload: 'two', start: 3, end: 7, priority: 2 },

        { payload: 'three', start: 7, end: 8, priority: 3 },

        // overlapping
        { payload: 'seven', start: 9, end: 11, priority: 7 },
        { payload: 'six', start: 10, end: 14, priority: 6 },
        { payload: 'five', start: 11, end: 13, priority: 5 },

        { payload: 'nine', start: 15, end: 16, priority: 9 },

        // overlapping
        { payload: 'four', start: 17, end: 18, priority: 4 },
        { payload: 'ten', start: 17, end: 20, priority: 10 },
      ])
    ).toEqual([
      { payload: 'one', start: 0, end: 3, priority: 1 },
      { payload: 'eight', start: 3, end: 6, priority: 8 },
      { payload: 'three', start: 7, end: 8, priority: 3 },
      { payload: 'seven', start: 9, end: 11, priority: 7 },
      { payload: 'five', start: 11, end: 13, priority: 5 },
      { payload: 'nine', start: 15, end: 16, priority: 9 },
      { payload: 'ten', start: 17, end: 20, priority: 10 },
    ]);
  });
  it('removes all the different kinds of overlapping ranges all at once', () => {
    expect(
      removeOverlap([
        { payload: 'in', start: 0, end: 1, priority: 1 },
        { payload: 'out', start: 0, end: 9, priority: 4 },
        { payload: 'in', start: 1, end: 2, priority: 1 },
        { payload: 'in', start: 2, end: 3, priority: 1 },
        { payload: 'out', start: 2, end: 5, priority: 6 },
        { payload: 'out', start: 2, end: 6, priority: 7 },
        { payload: 'priority', start: 3, end: 6, priority: 10 },
        { payload: 'out', start: 3, end: 6, priority: 3 },
        { payload: 'out', start: 3, end: 7, priority: 9 },
        { payload: 'out', start: 4, end: 7, priority: 8 },
        { payload: 'out', start: 4, end: 5, priority: 5 },
        { payload: 'in', start: 6, end: 7, priority: 2 },
        { payload: 'in', start: 7, end: 9, priority: 0 },
      ])
    ).toEqual([
      { payload: 'priority', start: 3, end: 6, priority: 10 },
      { payload: 'in', start: 6, end: 7, priority: 2 },
      { payload: 'in', start: 0, end: 1, priority: 1 },
      { payload: 'in', start: 1, end: 2, priority: 1 },
      { payload: 'in', start: 2, end: 3, priority: 1 },
      { payload: 'in', start: 7, end: 9, priority: 0 },
    ]);
  });
  it('When there are collisions in priority, return the range with the lowest start', () => {
    expect(
      removeOverlap([
        { payload: 'out', start: 5, end: 7, priority: 2 },
        { payload: 'out', start: 6, end: 8, priority: 2 },
        { payload: 'in', start: 4, end: 9, priority: 2 },
      ])
    ).toEqual([{ payload: 'in', start: 4, end: 9, priority: 2 }]);
  });
  it('filters out a range overlapping two other ranges in both lower/upper bounds', () => {
    expect(
      removeOverlap([
        { payload: 'in', start: 5, end: 7, priority: 4 },
        { payload: 'out', start: 6, end: 9, priority: 1 },
        { payload: 'in', start: 8, end: 9, priority: 2 },
      ])
    ).toEqual([
      { payload: 'in', start: 5, end: 7, priority: 4 },
      { payload: 'in', start: 8, end: 9, priority: 2 },
    ]);
  });
  it('filters out ranges with invalid start/end values', () => {
    expect(
      removeOverlap([
        { payload: 'in', start: 0, end: 5, priority: 1 },
        { payload: 'out', start: 2, end: 1, priority: 2 },
      ])
    ).toEqual([{ payload: 'in', start: 0, end: 5, priority: 1 }]);
  });
});