An interval tree written in JS to find the number of intersecting intervals at a given point

interval_tree.js

// https://en.wikipedia.org/wiki/Interval_tree

export default class IntervalTree {
  // intervals is a two dimensional array of "from" and "to" values
  // the values can be of any type. If they can directly be compared
  // using greater/lesser than operators then a compare function does
  // not need to be supplied
  constructor(intervals) {
    this.allIntervals = intervals.map(interval => new Interval(interval[0], interval[1]));
    this.root = new IntervalTreeNode(this.allIntervals);
  }
  intersectionsAtPoint(point) {
    return this.root.intersectionsAtPoint(point);
  }
}

class Interval {
  constructor(start, end) {
    this.start = start;
    this.end = end;
  }
}

class IntervalTreeNode {
  constructor(intervals) {
    // find and set the center of this node
    const intervalAverages = intervals.map(interval => {
      return Math.round((interval.start + interval.end) / 2);
    });
    const mean = Math.round(sumArray(intervalAverages) / intervalAverages.length);
    this.center = mean;
    const left = [];
    const right = [];
    const intersect = [];
    intervals.forEach(interval => {
      if(interval.end < this.center) {
        left.push(interval);
      }
      else if (interval.start > this.center) {
        right.push(interval);
      } else { // start < center < end
        intersect.push(interval);
      }
    });
    this.left = left.length > 0 ? new IntervalTreeNode(left) : null;
    this.right = right.length > 0 ? new IntervalTreeNode(right) : null;
    this.intersect = intersect;
  }

  intersectionsAtPoint(point) {
    if(point < this.center && this.left) {
      return this.left.intersectionsAtPoint(point);
    }
    else if(point > this.center && this.right) {
      return this.right.intersectionsAtPoint(point);
    }
    else {
      const pointIsInIntersection = intersection => {
        if(intersection.start <= point && point <= intersection.end) {
          return 1;
        } else {
          return 0;
        }
      }
      return sumArray(this.intersect.map(pointIsInIntersection));
    }
  }
}

function sumArray(arr) {
  return arr.reduce((accumulator, currentValue) => {
    return accumulator + currentValue;
  }, 0);
}

interval_tree_spec.js

import IntervalTree from 'interval_tree.js';

describe('IntervalTree', () => {
  it('should have nothing before or after one interval', () => {
    const it = new IntervalTree([[5,10]]);
    expect(it.intersectionsAtPoint(4)).toStrictEqual(0);
    expect(it.intersectionsAtPoint(11)).toStrictEqual(0);
  });
  it('should be able to count a lone interval', () => {
    const it = new IntervalTree([[5,10]]);
    expect(it.intersectionsAtPoint(7)).toStrictEqual(1);
  });
  it('should be able to count two overlapping intervals of the same size', () => {
    // -------------XXXXXXXXXX---------
    // -------------XXXXXXXXXX---------
    const it = new IntervalTree([[5,10], [5,10]]);
    expect(it.intersectionsAtPoint(7)).toStrictEqual(2);
    expect(it.intersectionsAtPoint(5)).toStrictEqual(2); // boundary condition
    expect(it.intersectionsAtPoint(10)).toStrictEqual(2); // boundary condition
  });
  it('should be able to count two overlapping intervals of the same size but different times', () => {
    // -------------XXXXXXXXXX---------
    // ---------XXXXXXXXXX-------------
    const it = new IntervalTree([[2,7], [5,10]]);
    expect(it.intersectionsAtPoint(6)).toStrictEqual(2);
  });
  it('should be able to count two overlapping intervals where one envelops the other', () => {
    // -------------XXXXXXXXXX---------
    // ---------XXXXXXXXXXXXXXXXXX-----
    const it = new IntervalTree([[4,6], [4,9]]);
    expect(it.intersectionsAtPoint(5)).toStrictEqual(2);
  });
  it('should be able to handle a handful of intervals', () => {
    // -------------XXXXXXXXXX---------
    // ---------XXXXXXXXXXXXXXXXXX-----
    const it = new IntervalTree([
      [0,5],
      [1,9],
      [3,10],
      [4,6]
    ]);
    expect(it.intersectionsAtPoint(0.5)).toStrictEqual(1);
    expect(it.intersectionsAtPoint(2)).toStrictEqual(2);
    expect(it.intersectionsAtPoint(5)).toStrictEqual(4);
    expect(it.intersectionsAtPoint(9)).toStrictEqual(2);
  });
});