range.js

// Problem Set below: 

// Task: Implement a class named 'RangeList'
// A pair of integers define a range, for example: [1, 5). This range includes integers: 1, 2, 3, and 4.
// A range list is an aggregate of these ranges: [1, 5), [10, 11), [100, 201)

/*
  RangeList is a strict ordered range list: 
  1. For any [a, b] in RangeList, a < b
  2. For any [a1, b1], [a2, b2] in RangeList with index i, j, given i < j,  a1 < b1 < a2 < b2 
  3. As a special case of 2, for any [a1, b1], [a2, b2], [a1, b2], [a2, b2] is not mergeable, I add a test case for this property
*/

const {
  max,
  min
} = Math


class RangeList {
  constructor() {
    this._ranges = []
  }

  /**
   *  Merge two range (a, b) with the assume that (a, b) is mergeable
   * @param {Array<number>} a range a
   * @param {Array<number>} b range b
   * @returns {Array<number>}
   */
  mergeRange([aStart, aStop], [bStart, bStop]) {
    return [min(aStart, bStart), max(aStop, bStop)]
  }

  _add(range) {
    let [start, stop] = range
    let i = 0
    while (i < this._ranges.length) {
      let [a, b] = this._ranges[i]
      if (stop < a) {
        this._ranges.splice(i, 0, range)
        return
      }
      if (start <= b) {
        // merge until not mergeable by recursion
        let r = this.mergeRange(range, [a, b])
        // console.log('Merged', r)
        this._ranges.splice(i, 1)
        this.add(r)
        return
      }

      i += 1
    }
    this._ranges.push(range)
  }

  /**
   * Adds a range to the list
   * @param {Array<number>} range - Array of two integers that specify beginning and end of range.
   */
  add(range) {
    let [start, stop] = range
    if (start < stop) {
      this._add(range)
    }
  }

  /**
   * Minus range a and b, return a - b whichi is a list of range, invalid range filtered
   * @param {Array<number>} a - range a
   * @param {Array<number>} b - range b
   * @returns {Array<Array<number>>}
   */
  rangeMinus([aStart, aStop], [bStart, bStop]) {
    let ret = [
      [aStart, bStart],
      [bStop, aStop]
    ]
    return ret.filter(([a, b]) => b > a)
  }

  /**
   * Check whether a and b have common parts
   * @param {Array<number>} a - range a
   * @param {Array<number>} b - range b
   * @returns {boolean}
   */
  isRangesIntersected(a, b) {
    let [aStart, aStop] = a
    let [bStart, bStop] = b
    return !(aStop <= bStart || bStop <= aStart)
  }

  /**
   * Removes a range from the list
   * @param {Array<number>} range - Array of two integers that specify beginning and end of range.
   */
  remove(range) {
    let [start, stop] = range
    if (!(stop > start)) {
      return
    }
    let i = 0
    while (i < this._ranges.length) {
      let [a, b] = this._ranges[i]
      if (stop < a) {
        return
      }
      if (this.isRangesIntersected([a, b], range)) {
        let rs = this.rangeMinus([a, b], range)
        this._ranges.splice(i, 1, ...rs)
        // those adds is  NOT mergeable so can use it's length to skip
        // rs.map((v, _) => this.add(v))
        i += (rs.length - 1)
      }
      i += 1
    }
  }

  toString() {
    let ret = this._ranges.map(([start, stop], _) => `[${start}, ${stop})`)
    return ret.join(' ')
  }

  /**
   * Prints out the list of ranges in the range list
   */
  print() {
    console.log(this.toString())
  }
}

// Example run
const rl = new RangeList();

rl.add([1, 5]);
rl.print();
// Should display: [1, 5)

rl.add([10, 20]);
rl.print();
// Should display: [1, 5) [10, 20)

rl.add([20, 20]);
rl.print();
// Should display: [1, 5) [10, 20)

rl.add([20, 21]);
rl.print();
// Should display: [1, 5) [10, 21)

rl.add([2, 4]);
rl.print();
// Should display: [1, 5) [10, 21)

rl.add([3, 8]);
rl.print();
// Should display: [1, 8) [10, 21)

rl.remove([10, 10]);
rl.print();
// Should display: [1, 8) [10, 21)

rl.remove([10, 11]);
rl.print();
// Should display: [1, 8) [11, 21)

rl.remove([15, 17]);
rl.print();
// Should display: [1, 8) [11, 15) [17, 21)

rl.remove([3, 19]);
rl.print();
// Should display: [1, 3) [19, 21)

// add test case
rl.add([3, 19])
rl.print()
// should display: [1, 21)