I have a large list of ranges:
list A = [{lower:0,upper:10}, {lower:11,upper:20}, {lower:31, upper:33}]
list B = [{lower:21,upper:30}, {lower:34,upper:9999}]
This list can accept modifications in terms of moving numbers between one another. For example:
Move numbers 13, 14 and 15 from list A to list B
The lists now change to:
list A = [{lower:0,upper:10}, {lower:11,upper:12}, {lower:14, upper:20},{lower:31, upper:33}]
list B = [{lower:13, upper:15},{lower:21,upper:30}, {lower:34,upper:9999}]
Currently I am doing this by accepting the following as input:
numbers for list A: [0,1,2,3,4,5,6,7,8,9,10,11,12,...20,31...33]
numbers for list B: [13,14,15,21,22...30,34...9999]
And then recompute the ranges from these numbers:
getRanges(numbers) {
numbers.sort();
let length = 1;
let ranges = [];
for (let i = 1; i <= numbers.length; i++) {
if (i == numbers.length || numbers[i] - numbers[i - 1] != 1) {
if (length == 1) {
let upper = lower = numbers[i - length];
ranges.push({lower, upper});
}
else {
let lower = numbers[i - length];
let upper = numbers[i - 1];
ranges.push({lower, upper});
}
length = 1;
}
else {
length++;
}
}
return ranges;
}
The problem with this approach is, there are lists with huge ranges
list C = [{lower:5000001, upper:6999900},{lower:9000000, upper:9999999}]
And the input intent is to move a small set of numbers (Not necessarily a range) from this to a new list. For example:
Move numbers 5000010 to 5000020 from list C to list B
The lists will now look like
list A = [{lower:0,upper:10}, {lower:11,upper:12}, {lower:14, upper:20},{lower:31, upper:33}]
list B = [{lower:13, upper:15},{lower:21,upper:30}, {lower:34,upper:9999},{lower:5000010, upper:5000020},]
list C = [{lower:5000000, upper:5000009},{lower:5000021, upper:6999900},{lower:9000000, upper:9999999}]
Expanding these numbers as user inputs and recomputing them is memory intensive. Also - inputs are only a list of numbers (And not ranges)
Is there a better way to recompute ranges from list of numbers than to expect the complete list?
There is absolutely no need to expand the list of numbers and/or check them one by one. Checking if two ranges overlap and calculating the overlapping portion is fairly simple. Below is a function that:
ranges in the form [{lower: x, upper: y}, ...]range to remove {lower: x, upper: y}And returns:
result arrayremoved array containing ranges that were successfully removed (could be inserted directly into the "move to" array).function removeRange(ranges, remove) {
let result = [];
let removed = [];
ranges.forEach(function(range) {
// if this range overlaps the remove range
if (remove.upper >= range.lower && range.upper >= remove.lower) {
// calculate the overlapping portion
let overlap = { lower: Math.max(range.lower, remove.lower), upper: Math.min(range.upper, remove.upper) };
// this range needs to be split into:
// 0 parts when fully covered by remove range
// 1 part when remove range starts or ends inside
// 2 parts whem remove range is fully inside
if (overlap.lower > range.lower) {
result.push({ lower: range.lower, upper: overlap.lower - 1 });
}
if (overlap.upper < range.upper) {
result.push({ lower: overlap.upper + 1, upper: range.upper });
}
// the overlap has been dealt with
removed.push(overlap);
} else {
result.push(range);
}
});
return { result: result, removed: removed };
}
/*
* Tests
*/
const ranges = [{ lower: 0, upper: 10 }, { lower: 11, upper: 20 }, { lower: 31, upper: 33 }];
console.log("fully inside test");
console.log(removeRange(ranges, { lower: 13, upper: 15 }));
console.log("ends inside test");
console.log(removeRange(ranges, { lower: 30, upper: 32 }));
console.log("starts inside test");
console.log(removeRange(ranges, { lower: 32, upper: 34 }));
console.log("fully covered test");
console.log(removeRange(ranges, { lower: 30, upper: 34 }));
console.log("no-op test");
console.log(removeRange(ranges, { lower: 50, upper: 60 }));
console.log("multi removal test");
console.log(removeRange(ranges, { lower: 19, upper: 32 }));<p>Check logs in Developer Console</p>If the case is that you have a small amount of ranges compared to numbers, it will be more effective to recalculate the ranges. Here's a short example of how the code could look like when updating a range.
let listA = [{lower:0,upper:10}, {lower:11,upper:20}, {lower:31, upper:33}]
let listB = [{lower:21,upper:30}, {lower:34,upper:9999}]
const removeNumberFromList = (number, currentList) => {
return currentList.reduce((acc, range) => {
if (number < range.lower ||number > range.upper) {
acc.push(range)
return acc
}
if (number === range.lower) {
acc.push([{lower: range.lower + 1, upper: range.upper}])
return acc
}
if (number === range.upper) {
acc.push([{lower: range.lower, upper: range.upper - 1}])
return acc
}
if (number > range.lower && number < range.upper) {
acc.push({lower: range.lower,upper:number - 1})
acc.push({lower: number + 1,upper:range.upper})
return acc
}
return acc
}, [])
}
// When moving a number, remove it from the old list
// and add it to the new list. If you want to move
// multiple numbers, do this for every number to be
// moved.
const updatedFromList = removeNumberFromList(13, listA)
// const updatedToList = addNumberToist(13, listB)
console.log("updatedFromList", updatedFromList);
If there are very many ranges as well, you can keep the range lists sorted and use binary search to find the ranges that is affected by a move. Maybe it is even okay to mutate the lists instead of recreating them, that depends on your use case and the amount of data you need to handle.