// 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. | |
*/ | |
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(range) { | |
let isStartAvailable = false, | |
isEndAvailable = false; | |
// get the start and end from the array by destructuring | |
const [start, end] = range; | |
// if start and end are the same, no range is between them, return | |
if (start == end) { | |
return; | |
} | |
// If this is the first array to be added, just push to the ranges array | |
if (this.ranges.length == 0) { | |
return this.ranges.push(range); | |
} | |
// loop through all current ranges to find out if the start and end are contained herein | |
for (let element of this.ranges) { | |
for (let num of this.range(element)){ | |
if (num == start) isStartAvailable = true; | |
if (num == end) isEndAvailable = true; | |
} | |
} | |
if (isStartAvailable && isEndAvailable) { | |
return; | |
} | |
// if the start and stop happens not to be in any of the ranges array, push the new ranges to the array. | |
if (!isStartAvailable && !isEndAvailable) { | |
return this.ranges.push(range); | |
} | |
if (isStartAvailable && !isEndAvailable) { | |
// get all the ranges, whose last value is lesser than this end. | |
let availableRangesWithLesserEnd = this.ranges.filter(r => { | |
return r[1] < end; | |
}); | |
// sort by the greater end of them both, so the greater one is the first array | |
let sortedAvailableRangeByValue = availableRangesWithLesserEnd.sort((a, b) => { | |
return a[1] < b[1]; | |
}); | |
// find the position of the array in the ranges index | |
let indexOfRange = this.ranges.indexOf(sortedAvailableRangeByValue[0]); | |
// alter the end of the range to the new end we need | |
return (this.ranges[indexOfRange][1] = end); | |
} | |
} | |
/** | |
* Returns all the numbers in a range | |
* @param {Array<number>} range - Array of two integers that specify beginning and end of range. | |
*/ | |
*range(range) { | |
// destructure start and end from the range array | |
let [start, end] = range; | |
while (start <= end) { | |
yield start; | |
start++; | |
} | |
} | |
/** | |
* Removes a range from the collection | |
* @param {Array<number>} range - Array of two integers that specify beginning and end of range. | |
*/ | |
remove(range) { | |
const [start, end] = range; | |
// if start and end are the same, no range is between them, return | |
if (start == end) { | |
return; | |
} | |
// check for the array that has its start sequence and end sequence | |
let startIndex, endIndex; | |
// loop through all the ranges, to see which of them has the range we are looking for | |
for (let element of this.ranges) { | |
// if our range is equal to the current element, delete and exit from loop | |
if(range == element){ | |
let ind = this.ranges.indexOf(element); | |
return this.ranges.splice(ind, 1); | |
} | |
for (let num of this.range(element)){ | |
if (num == start) startIndex = element; | |
if (num == end) endIndex = element; | |
} | |
} | |
startIndex = this.ranges.indexOf(startIndex); | |
endIndex = this.ranges.indexOf(endIndex); | |
// if the range given for start and end are both in the same array, check if the range given | |
// is the exact same thing with the one in our ranges array, then delete the entry | |
if (startIndex == endIndex) { | |
if (range == this.ranges[endIndex]) { | |
return this.ranges.splice(endIndex, 1); | |
} | |
// check if the end of the range we want to remove is not the same as the end of the range in the ranges array | |
// also check if the start is not the first one | |
if (this.ranges[endIndex][1] - end > 0 && start - this.ranges[endIndex][0] > 0) { | |
// save the current value for the end of the zrange | |
let formerEnd = this.ranges[endIndex][1]; | |
// update the end of the range to the start of where we want to remove | |
this.ranges[endIndex][1] = start; | |
// create a new range leaving the ranges we want to remove out | |
let newRange = [end, formerEnd]; | |
// add the new range just after the one we have edited. | |
return this.ranges.splice(endIndex + 1, 0, newRange); | |
} | |
return (this.ranges[endIndex][0] = end); | |
} | |
// Not the same index, find a way to remove the ranges | |
// delete all ranges between the start and end. | |
this.ranges[startIndex][1] = start; | |
this.ranges[endIndex][0] = end; | |
for (let i = startIndex + 1; i < endIndex; i++) { | |
this.ranges.splice(i, 1); | |
} | |
return; | |
} | |
/** | |
* Prints out the list of ranges in the range collection | |
*/ | |
print() { | |
// loop through all the arrays and print one after the other, so the results do not come out | |
// as [[1,5]], but instead as [1. 5] | |
for (let el of this.ranges) { | |
console.log(el); | |
} | |
} | |
} | |
// 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) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment