/**
* class RangeList
*
* This is collection class, List with range of integer.
* like this: [ [ 5, 7 ], [ 9, 13 ], [ 17, 21 ] ] as is 5 to 7, 9 to 13 and 17 to 21.
*
* Version: 1.0.0
* Date: 2018-12-27
*/
/*
Usage:
import RangeList from "./RangeList";
const r = new RangeList();
r.add([5, 7]);
r.add([9, 13]);
r.add([17, 21]);
console.log("ranges: ", r.get());
r.remove([22, 23]);
console.log("ranges: ", r.get());
*/
// Type alias
type n2 = [number, number];
// Interface, extends and generics declaration
interface Data extends Array<n2> {
[index: number]: n2;
}
export default class RangeList {
private data: Data = [];
/**
* Return as array list what is not covered range in the list.
*
* @param r range array [a, b]
* @returns range items array list [ [a, b], [c, d], ... ], or false
*/
public notCoveredRanges(r: n2): Data | false {
// invalid arguments
if (r[0] > r[1]) {
return false;
}
const len = this.data.length;
// this.data is empty
if (!len) {
return [r];
}
// target range is not covered any range items in the array. target is less than.
let d = this.data[0];
if (r[1] < d[0]) {
return [r];
}
// target range is not covered any range items in the array. target is greater than.
d = this.data[len - 1];
if (r[0] > d[1]) {
return [r];
}
// find the uncovered range in the array at the target range.
const result: Data = [];
let a = r[0], b = r[1]; // [a, b]
for (let i = 0; i < len; i++) {
let d = this.data[i];
if (a < d[0]) {
if (b < d[0]) {
result.push([a, b]);
break;
} else if (b <= d[1]) {
result.push([a, d[0] - 1]);
break;
} else {
result.push([a, d[0] - 1]);
a = d[1] + 1;
continue;
}
} else if (a >= d[0] && a <= d[1]) {
if (b <= d[1]) {
return [];
} else {
a = d[1] + 1;
continue;
}
} else {
continue;
}
}
if (b > d[1]) {
result.push([d[1] + 1, b]);
}
return result;
}
/**
* Add range
*
* @param r range array [a, b]
* @returns range items array list [ [a, b], [c, d], ... ], or false
*/
public add(r: n2): Data | false {
// invalid arguments
if (r[0] > r[1]) {
return false;
}
const len = this.data.length;
// this.data is empty
if (!len) {
this.data.push(r);
return this.data;
}
// additional item is less than any in array
let d = this.data[0];
if (r[1] < d[0] - 1) {
this.data.unshift(r);
return this.data;
}
// additional item is greater than any in array
d = this.data[len - 1];
if (r[0] > d[1] + 1) {
this.data.push(r);
return this.data;
}
// find the items from the array what is covered all and part of range array by additional range
// and result is the found first and end item index number: firstIndex, endIndex
let firstIndex = -1, endIndex = -1;
for (let i = 0; i < len; i++) {
let d = this.data[i];
if (firstIndex < 0 && r[0] >= d[0] - 1 && r[0] <= d[1] + 1) {
firstIndex = i;
}
if (r[1] >= d[0] - 1 && r[1] <= d[1] + 1) {
endIndex = i;
}
if (r[1] < d[0] - 1) {
break;
}
}
if (firstIndex < 0) {
firstIndex = 0;
}
if (endIndex < 0) {
endIndex = len - 1;
}
// make the new range: [a, b]
let a = this.data[firstIndex][0];
if (a > r[0]) {
a = r[0];
}
let b = this.data[endIndex][1];
if (b < r[1]) {
b = r[1];
}
// remove and add range items
this.data.splice(firstIndex, endIndex - firstIndex + 1, [a, b]);
return this.data;
}
/**
* Remove range
*
* @param r range array [a, b]
* @returns range items array list [ [a, b], [c, d], ... ], or false
*/
public remove(r: n2): Data | false {
// invalid arguments
if (r[0] > r[1]) {
return false;
}
const len = this.data.length;
// this.data is empty
if (!len) {
return this.data;
}
// remove range is less than any in array
let d = this.data[0];
if (r[1] < d[0]) {
return this.data;
}
// remove range is greater than any in array
d = this.data[len - 1];
if (r[0] > d[1]) {
return this.data;
}
// find the items from the array what is covered all and part of range array by remove range
// and result is the found first and end item index number: firstIndex, endIndex
let firstIndex = -1, endIndex = -1;
for (let i = 0; i < len; i++) {
let d = this.data[i];
if (firstIndex < 0 && r[0] >= d[0] && r[0] <= d[1]) {
firstIndex = i;
}
if (r[1] >= d[0]) {
endIndex = i;
}
if (r[1] < d[0]) {
break;
}
}
if (firstIndex < 0) {
firstIndex = 0;
}
if (endIndex < 0) {
endIndex = len - 1;
}
//
d = this.data[firstIndex];
if (r[0] == d[0] && r[1] >= d[1]) {
// remove firstIndex range
} else if (r[0] < d[0]) {
if (r[1] < d[1]) {
this.data[firstIndex] = [r[1] + 1, d[1]];
firstIndex += 1;
} else { // r[1] >= d[1]
// remove firstIndex range
}
} else { // d[0] <= r[0] <= d[1]
if (r[1] < d[1]) {
this.data[firstIndex] = [d[0], r[0] - 1];
firstIndex += 1;
this.data.splice(firstIndex, 0, [r[1] + 1, d[1]]);
firstIndex += 1;
} else { // r[1] >= d[1]
this.data[firstIndex] = [d[0], r[0] - 1];
firstIndex += 1;
}
}
//
d = this.data[endIndex];
if (r[0] > d[0]) {
endIndex -= 1;
} if (r[1] < d[1]) {
this.data[endIndex] = [r[1] + 1, d[1]];
endIndex -= 1;
} else {
// nothing
}
// remove items
this.data.splice(firstIndex, endIndex - firstIndex + 1);
return this.data;
}
/**
* @returns range array, like this: [ [a, b], [c, d], ... ]
*/
public get(): Data {
return this.data;
}
public clear() {
this.data = [];
}
/**
* @returns count of ranges in array
*/
public length(): number {
return this.data.length;
}
}
