range.js

ranges.js

// Task: Implement a 'Range Collection' class.
// A pair of integers define a range, for example: [1, 5). This range includes integers: 1, 2, 3, and 4.
// A range collection is an aggregate of these ranges: [1, 5), [10, 11), [100, 201)
// 
/**
 * RangeCollection class
 * NOTE: Feel free to add any extra member variables/functions you like.
 */

/**
 * A class that encapsules two integers that specify 
 * beginning and end of range.
 */
class Range {
  constructor(a, b) {
    this.a = a;
    this.b = b;
  }

  /**
   * Returns the intersection of this range and the supplied range.
   * @param  {Range} other The range to intersect with
   * @return {Range}       The intersecting range
   */
  intersection(other) {
    // Return null if no intersection
    if (other.b <= this.a || other.a >= this.b) {
      return null;
    }

    const minA = Math.max(this.a, other.a);
    const minB = Math.min(this.b, other.b);
    return new Range(minA, minB);
  }

  /**
   * Check if this range contains the supplied range
   * @param  {Range} other The range to check for contains
   * @return {Boolean}        True if supplied range is contained in this range
   */
  contains(other) {
    return this.a <= other.a && other.b <= this.b;
  }

  /**
   * Check if this range equals to the supplied range
   * @param  {Range} other The range to check for equality
   * @return {Bool}        True if other range equals to this range
   */
  equals(other) {
    return this.a == other.a && this.b == other.b;
  }

  /**
   * Check if other range can be merged with this range.
   * @param  {Range}  other  The range to check for
   * @return {Boolean}       True if they can be merged.
   */
  canMergeWithRange(other) {
    if (this.intersection(other) != null || 
        (this.a == other.b || this.b == other.a)) {
      return true;
    }
    return false;
  }

  /**
   * Return a new range that is merged using this range and the supplied range.
   * Null is returned if the ranges cannot be merged.
   * @param  {Range}  other  The range to merge with
   * @return {Range}         The merged range
   */
  mergeWithRange(other) {
    if (!this.canMergeWithRange(other)) {
      return null;
    }
    return new Range(Math.min(this.a, other.a), Math.max(this.b, other.b));
  }
  
  isValid() {
    return Number.isInteger(this.a) && Number.isInteger(this.b) && this.b > this.a;
  }

  toString() {
    return '[' + this.a + ', ' + this.b + ')';
  }

  /**
   * Returns a range array into a Range instance.
   * @param {Array<number>} range - Array of two integers that specify beginning and end of range.
   */
  static fromArray(range) {
    if (range instanceof Array && range.length == 2) {
      return new Range(range[0], range[1]);
    }
    return null;
  }
}

class RangeCollection {

  constructor() {
    this.ranges = [];
  }

  /**
   * Adds a range to the collection
   * @param {Array<number>} range - Array of two integers that specify beginning and end of range.
   */
  add(input) {
    let range = Range.fromArray(input);

    // Do nothing on invalid range
    if (!range.isValid()) {
      return;
    }

    // Loop through all ranges to try to add the new range
    let isRangeAdded = false;
    const newRanges = [];
    for (let i = 0; i < this.ranges.length; i++) {
      const current = this.ranges[i];

      // Just add current range if new range is already added
      if (isRangeAdded) {
        newRanges.push(current);
        continue;
      }

      // Merge current range with target range if able to
      if (current.canMergeWithRange(range)) {
        range = current.mergeWithRange(range);

        // If merged range does not go beyond current range then we
        // can just add it.
        if (range.b <= current.b) {
          newRanges.push(range);
          isRangeAdded = true;
        }

      // Add new and current range if new range is before current range
      } else if (range.b < current.a) {
        newRanges.push(range);
        newRanges.push(current);
        isRangeAdded = true;

      } else {
        newRanges.push(current);
      }
    }

    // Last, if range has not been added then add it
    if (!isRangeAdded) {
      newRanges.push(range);
    }
    
    this.ranges = newRanges;
  }

  /**
   * Removes a range from the collection
   * @param {Array<number>} range - Array of two integers that specify beginning and end of range.
   */
  remove(input) {
    const range = Range.fromArray(input);

    // Do nothing if range is not valid or nothing to remove
    if (this.ranges.length == 0 || !range.isValid()) {
      return;
    }

    const newRanges = [];
    for (let i = 0; i < this.ranges.length; i++) {
      const current = this.ranges[i];
      const intersection = current.intersection(range);

      // No changes to current range if target range does not intersect
      if (intersection == null) {
        newRanges.push(current);

      // Split the current range only if the intersection is not
      // the entire current range.
      } else if (!current.equals(intersection)) {
        if (current.a != intersection.a) {
          newRanges.push(new Range(current.a, intersection.a));
        }
        if (current.b != intersection.b) {
          newRanges.push(new Range(intersection.b, current.b))
        }
      }
    }
    this.ranges = newRanges;
  }

  /**
   * Prints out the list of ranges in the range collection
   */
  print() {
    const results = this.ranges.map(x => x.toString());
    console.log(results.join(" "));
  }
}


// Example run
const rc = new RangeCollection();

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

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

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

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

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

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

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

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

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

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