Skip to content

Instantly share code, notes, and snippets.

@qingant
Last active October 10, 2022 12:35
Show Gist options
  • Save qingant/d34a2663e597e01710991edfd696143b to your computer and use it in GitHub Desktop.
Save qingant/d34a2663e597e01710991edfd696143b to your computer and use it in GitHub Desktop.
// 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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment