Ranges Manager

RangesManager.test.ts

import { RangesManager } from '../RangesManager';

/*
About test cases:

There are three equivalence classes with respect to any range.
Using the range from 5 to 10 as an example (or [5; 10])
- to the left of the range: [-∞; 4]
- the range itself: [5; 10]
- to the right of the range: [11; ∞]

We take control values at the boundaries and inside the classes:
1/3, 4, 5, 7/9, 10, 11, 14/20

Let's make pairs for testing the left and right boundaries at the same time (variables "testCases..." below).
*/

const arrayToRange = (values: number[]) => ({ from: values[0], to: values[1] });

describe('RangesManager', () => {
  let rangesManager: RangesManager;

  beforeEach(() => {
    rangesManager = new RangesManager();
  });

  it(`Manager returns an empty array of ranges after creation`, () => {
    expect(rangesManager.ranges).toEqual([]);
  });

  describe('Range adding', () => {
    it(`Adding to an empty manager`, () => {
      expect(rangesManager.add({ from: 5, to: 10 }).ranges).toEqual([{ from: 5, to: 10 }]);
    });

    describe('Adding to a manager with one range', () => {
      beforeEach(() => {
        rangesManager.add({ from: 5, to: 10 });
      });

      // prettier-ignore
      const testCasesResultsByTerm = new Map([
        [[1, 3], [[1, 3], [5, 10]]],
        [[1, 4], [[1, 10]]],
        [[1, 5], [[1, 10]]],
        [[1, 7], [[1, 10]]],
        [[1, 10], [[1, 10]]],
        [[1, 11], [[1, 11]]],
        [[1, 14], [[1, 14]]],
        [[4, 5], [[4, 10]]],
        [[4, 7], [[4, 10]]],
        [[4, 10], [[4, 10]]],
        [[4, 11], [[4, 11]]],
        [[4, 14], [[4, 14]]],
        [[5, 7], [[5, 10]]],
        [[5, 10], [[5, 10]]],
        [[5, 11], [[5, 11]]],
        [[5, 14], [[5, 14]]],
        [[7, 9], [[5, 10]]],
        [[7, 10], [[5, 10]]],
        [[7, 11], [[5, 11]]],
        [[7, 14], [[5, 14]]],
        [[10, 11], [[5, 11]]],
        [[10, 14], [[5, 14]]],
        [[11, 14], [[5, 14]]],
        [[14, 20], [[5, 10], [14, 20]]],
      ]);

      testCasesResultsByTerm.forEach((resultRaw, termRaw) => {
        const term = arrayToRange(termRaw);
        const result = resultRaw.map(arrayToRange);
        it(`Adding to a manager with one range: ${JSON.stringify(term)}`, () => {
          expect(rangesManager.add(term).ranges).toEqual(result);
        });
      });
    });

    describe('Adding to a manager with multiple ranges', () => {
      beforeEach(() => {
        rangesManager.add({ from: 1, to: 5 }).add({ from: 8, to: 10 }).add({ from: 21, to: 34 });
      });

      it(`Expand one of the ranges`, () => {
        expect(rangesManager.add({ from: 10, to: 14 }).ranges).toEqual([
          { from: 1, to: 5 },
          { from: 8, to: 14 },
          { from: 21, to: 34 },
        ]);
      });

      it(`Add range`, () => {
        expect(rangesManager.add({ from: 12, to: 14 }).ranges).toEqual([
          { from: 1, to: 5 },
          { from: 8, to: 10 },
          { from: 12, to: 14 },
          { from: 21, to: 34 },
        ]);
      });

      it(`Merge two ranges`, () => {
        expect(rangesManager.add({ from: 9, to: 30 }).ranges).toEqual([
          { from: 1, to: 5 },
          { from: 8, to: 34 },
        ]);
      });

      it(`Merge all ranges and expand on the right`, () => {
        expect(rangesManager.add({ from: 6, to: 40 }).ranges).toEqual([{ from: 1, to: 40 }]);
      });
    });

    it('Adding another range manager', () => {
      rangesManager.add({ from: 1, to: 5 }).add({ from: 8, to: 10 }).add({ from: 21, to: 34 });
      const anotherManager = new RangesManager().add({ from: 9, to: 15 }).add({ from: 18, to: 19 });
      expect(rangesManager.add(anotherManager).ranges).toEqual([
        { from: 1, to: 5 },
        { from: 8, to: 15 },
        { from: 18, to: 19 },
        { from: 21, to: 34 },
      ]);
    });

    describe('Addition Validation', () => {
      it(`"from" cannot be greater than "to"`, () => {
        expect(() => rangesManager.add({ from: 5, to: 3 })).toThrow();
      });
      it(`"from" and "to" cannot be NaN`, () => {
        expect(() => rangesManager.add({ from: NaN, to: 5 })).toThrow();
        expect(() => rangesManager.add({ from: 5, to: NaN })).toThrow();
      });
    });
  });

  describe('Range subtraction', () => {
    it(`Subtraction from empty manager`, () => {
      rangesManager.sub({ from: 5, to: 8 });
      expect(rangesManager.ranges).toEqual([]);
    });

    describe('Subtraction from a manager with one range', () => {
      beforeEach(() => {
        rangesManager.add({ from: 5, to: 10 });
      });

      // prettier-ignore
      const testCasesResultsBySubtrahend = new Map([
        [[1, 3], [[5, 10]]],
        [[1, 4], [[5, 10]]],
        [[1, 5], [[6, 10]]],
        [[1, 7], [[8, 10]]],
        [[1, 10], []],
        [[1, 11], []],
        [[1, 14], []],
        [[4, 5], [[6, 10]]],
        [[4, 7], [[8, 10]]],
        [[4, 10], []],
        [[4, 11], []],
        [[4, 14], []],
        [[5, 7], [[8, 10]]],
        [[5, 10], []],
        [[5, 11], []],
        [[5, 14], []],
        [[7, 9], [[5, 6], [10, 10]]],
        [[7, 10], [[5, 6]]],
        [[7, 11], [[5, 6]]],
        [[7, 14], [[5, 6]]],
        [[10, 11], [[5, 9]]],
        [[10, 14], [[5, 9]]],
        [[11, 14], [[5, 10]]],
        [[14, 20], [[5, 10]]],
      ]);

      testCasesResultsBySubtrahend.forEach((resultRaw, subtrahendRaw) => {
        const subtrahend = arrayToRange(subtrahendRaw);
        const result = resultRaw.map(arrayToRange);
        it(`Subtraction from a manager with one range: ${JSON.stringify(subtrahend)}`, () => {
          expect(rangesManager.sub(subtrahend).ranges).toEqual(result);
        });
      });
    });

    describe('Subtraction from a manager with multiple ranges', () => {
      beforeEach(() => {
        rangesManager.add({ from: 1, to: 5 }).add({ from: 8, to: 10 }).add({ from: 21, to: 34 });
      });

      it(`Cut part of one of the ranges`, () => {
        expect(rangesManager.sub({ from: 15, to: 25 }).ranges).toEqual([
          { from: 1, to: 5 },
          { from: 8, to: 10 },
          { from: 26, to: 34 },
        ]);
      });

      it(`Cut one range completely and part of the second range`, () => {
        expect(rangesManager.sub({ from: 8, to: 25 }).ranges).toEqual([
          { from: 1, to: 5 },
          { from: 26, to: 34 },
        ]);
      });

      it(`Cut part of one range the second range completely`, () => {
        expect(rangesManager.sub({ from: 9, to: 35 }).ranges).toEqual([
          { from: 1, to: 5 },
          { from: 8, to: 8 },
        ]);
      });

      it(`Cut all ranges`, () => {
        expect(rangesManager.sub({ from: 0, to: 34 }).ranges).toEqual([]);
      });
    });

    it('Subtraction another range manager', () => {
      rangesManager.add({ from: 1, to: 5 }).add({ from: 8, to: 10 }).add({ from: 21, to: 34 });
      const anotherManager = new RangesManager().add({ from: 9, to: 15 }).add({ from: 18, to: 19 });
      expect(rangesManager.sub(anotherManager).ranges).toEqual([
        { from: 1, to: 5 },
        { from: 8, to: 8 },
        { from: 21, to: 34 },
      ]);
    });

    describe('Subtraction Validation', () => {
      it(`"from" cannot be greater than "to"`, () => {
        expect(() => rangesManager.add({ from: 0, to: 0 }).sub({ from: 5, to: 3 })).toThrow();
      });
      it(`"from" and "to" cannot be NaN`, () => {
        expect(() => rangesManager.add({ from: 0, to: 0 }).sub({ from: NaN, to: 5 })).toThrow();
        expect(() => rangesManager.add({ from: 0, to: 0 }).sub({ from: 5, to: NaN })).toThrow();
      });
    });
  });

  it(`Get ranges`, () => {
    rangesManager.add({ from: 5, to: 10 });
    expect(rangesManager.ranges).toEqual([{ from: 5, to: 10 }]);
  });

  it(`Clear ranges`, () => {
    rangesManager.add({ from: 5, to: 10 }).clear();
    expect(rangesManager.ranges).toEqual([]);
  });
});

RangesManager.ts

type Range = { from: number; to: number; }

type StepAdding = 'before' | 'now' | 'after';

class RangesManager {
  private _ranges: Range[] = [];

  public add(termRange: Range | RangesManager): this {
    if (termRange instanceof RangesManager) {
      termRange.ranges.forEach(range => this.add(range));
      return this;
    }

    validateRange(termRange);

    if (this.isEmpty()) {
      this._ranges.push(termRange);
      return this;
    }

    const ranges: Range[] = [];

    let stepAdding: StepAdding = 'before';
    let from: number = 0;
    this._ranges.forEach(range => {
      switch (stepAdding) {
        case 'before': {
          switch (rangesRelationship(range, termRange)) {
            case 'left-out':
              ranges.push(termRange);
              ranges.push(range);
              stepAdding = 'after';
              break;
            case 'left-intersection':
              ranges.push({
                from: termRange.from,
                to: range.to,
              });
              stepAdding = 'after';
              break;
            case 'in':
              ranges.push(range);
              stepAdding = 'after';
              break;
            case 'contain':
              from = termRange.from;
              stepAdding = 'now';
              break;
            case 'right-intersection':
              from = range.from;
              stepAdding = 'now';
              break;
            case 'right-out':
              ranges.push(range);
              break;
            // no default
          }
          break;
        }

        case 'now': {
          switch (rangesRelationship(range, termRange)) {
            case 'left-out':
              ranges.push({
                from,
                to: termRange.to,
              });
              ranges.push(range);
              stepAdding = 'after';
              break;
            case 'left-intersection':
              ranges.push({
                from,
                to: range.to,
              });
              stepAdding = 'after';
              break;
            // no default
          }
          break;
        }

        case 'after': {
          ranges.push(range);
          break;
        }
        // no default
      }
    });

    switch (stepAdding as StepAdding) {
      case 'before': {
        ranges.push(termRange);
        break;
      }
      case 'now': {
        ranges.push({
          from,
          to: termRange.to,
        });
        break;
      }
      // no default
    }

    this._ranges = ranges;

    this.normalizeRanges();

    return this;
  }

  public sub(subtrahendRange: Range | RangesManager): this {
    if (subtrahendRange instanceof RangesManager) {
      subtrahendRange.ranges.forEach(range => this.sub(range));
      return this;
    }

    if (this.isEmpty()) {
      return this;
    }

    this._ranges = rangesSubtraction(this._ranges, subtrahendRange);

    return this;
  }

  public clear(): void {
    this._ranges = [];
  }

  public get ranges(): Range[] {
    return this._ranges;
  }

  private isEmpty() {
    return this._ranges.length === 0;
  }

  private normalizeRanges() {
    if (this.isEmpty()) {
      return;
    }
    const ranges = [];
    let { from } = this._ranges[0];
    this._ranges.forEach((range, index) => {
      if (index === 0) {
        return;
      }
      const prevRange = this._ranges[index - 1];
      if (range.from !== prevRange.to + 1) {
        // стоп слияния
        ranges.push({
          from,
          to: prevRange.to,
        });
        from = range.from;
      }
    });
    ranges.push({
      from,
      to: this._ranges[this._ranges.length - 1].to,
    });
    this._ranges = ranges;
  }
}

function rangesRelationship(rangeExisting: Range, rangeChecking: Range) {
  if (rangeChecking.to < rangeExisting.from) {
    return 'left-out';
  }
  if (rangeChecking.from > rangeExisting.to) {
    return 'right-out';
  }
  if (rangeChecking.from < rangeExisting.from && rangeChecking.to > rangeExisting.to) {
    return 'contain';
  }
  if (rangeChecking.from >= rangeExisting.from && rangeChecking.to <= rangeExisting.to) {
    return 'in';
  }
  return rangeChecking.from < rangeExisting.from ? 'left-intersection' : 'right-intersection';
}

function validateRange(range: Range): void {
  if (Number.isNaN(range.from)) {
    throw new Error('range.from is NaN');
  }
  if (Number.isNaN(range.to)) {
    throw new Error('range.to is NaN');
  }
  if (!isValidRangeOrder(range)) {
    throw new Error('range.from is larger than range.to');
  }
}

function isValidRangeOrder(range: Range) {
  return range.from <= range.to;
}

function rangesSubtraction(minuendRanges: Range[], subtrahendRange: Range): Range[] {
  validateRange(subtrahendRange);

  const ranges: Range[] = [];

  let isSubtractionFinished = false;
  minuendRanges.forEach(range => {
    if (isSubtractionFinished) {
      ranges.push(range);
    } else {
      switch (rangesRelationship(range, subtrahendRange)) {
        case 'left-out':
          ranges.push(range);
          isSubtractionFinished = true;
          break;
        case 'left-intersection': {
          const maybeRange = {
            from: subtrahendRange.to + 1,
            to: range.to,
          };
          if (isValidRangeOrder(maybeRange)) {
            ranges.push(maybeRange);
          }
          isSubtractionFinished = true;
          break;
        }
        case 'in': {
          const maybeRangeLeft = {
            from: range.from,
            to: subtrahendRange.from - 1,
          };
          if (isValidRangeOrder(maybeRangeLeft)) {
            ranges.push(maybeRangeLeft);
          }
          const maybeRangeRight = {
            from: subtrahendRange.to + 1,
            to: range.to,
          };
          if (isValidRangeOrder(maybeRangeRight)) {
            ranges.push(maybeRangeRight);
          }
          isSubtractionFinished = true;
          break;
        }
        case 'contain':
          break;
        case 'right-intersection': {
          const maybeRange = {
            from: range.from,
            to: subtrahendRange.from - 1,
          };
          if (isValidRangeOrder(maybeRange)) {
            ranges.push(maybeRange);
          }
          break;
        }
        case 'right-out':
          ranges.push(range);
          break;
        // no default
      }
    }
  });

  return ranges;
}

export { RangesManager, rangesSubtraction };