Tengo una gran lista de rangos:
list A = [{lower:0,upper:10}, {lower:11,upper:20}, {lower:31, upper:33}] list B = [{lower:21,upper:30}, {lower:34,upper:9999}]Esta lista puede aceptar modificaciones en cuanto a mover números entre sí. Por ejemplo:
Mover los números 13, 14 y 15 de la lista A a la lista B
Las listas ahora cambian a:
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}]Actualmente estoy haciendo esto aceptando lo siguiente como entrada:
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]Y luego vuelva a calcular los rangos de estos números:
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; }El problema con este enfoque es que hay listas con rangos enormes
list C = [{lower:5000001, upper:6999900},{lower:9000000, upper:9999999}]Y la intención de entrada es mover un pequeño conjunto de números (no necesariamente un rango) de esto a una nueva lista. Por ejemplo:
Mover los números 5000010 a 5000020 de la lista C a la lista B
Las listas ahora se verán como
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}]Expandir estos números como entradas de usuario y volver a calcularlos consume mucha memoria. Además, las entradas son solo una lista de números (y no rangos)
¿Hay una mejor manera de volver a calcular los rangos de la lista de números que esperar la lista completa?
No hay absolutamente ninguna necesidad de expandir la lista de números y/o revisarlos uno por uno. Verificar si dos rangos se superponen y calcular la porción superpuesta es bastante simple. A continuación se muestra una función que:
ranges en la forma [{lower: x, upper: y}, ...]range a eliminar {lower: x, upper: y}Y devuelve:
resultremoved la matriz que contenía rangos que se eliminaron con éxito (podría insertarse directamente en la matriz "mover a"). 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>Si el caso es que tiene una cantidad pequeña de rangos en comparación con los números, será más efectivo volver a calcular los rangos. Aquí hay un breve ejemplo de cómo podría verse el código al actualizar un rango.
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);Si también hay muchos rangos, puede mantener ordenadas las listas de rangos y usar la búsqueda binaria para encontrar los rangos que se ven afectados por un movimiento. Tal vez incluso esté bien mutar las listas en lugar de volver a crearlas, eso depende de su caso de uso y la cantidad de datos que necesita manejar.