Skip to content

Instantly share code, notes, and snippets.

@podrezo
Created August 24, 2020 23:05
Show Gist options
  • Save podrezo/dbd1e940d117981f33527012af0fa412 to your computer and use it in GitHub Desktop.
Save podrezo/dbd1e940d117981f33527012af0fa412 to your computer and use it in GitHub Desktop.
An interval tree written in JS to find the number of intersecting intervals at a given point
// 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);
}
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);
});
});
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment