当一些数字在列表之间洗牌时如何重新计算范围

Question

我有一个很大的范围列表：

list A = [{lower:0,upper:10}, {lower:11,upper:20}, {lower:31, upper:33}]
list B = [{lower:21,upper:30}, {lower:34,upper:9999}]

此列表可以接受在彼此之间移动数字方面的修改。例如：

Move numbers 13, 14 and 15 from list A to list B

列表现在更改为：

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}]

目前我正在通过接受以下输入来做到这一点：

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]

然后重新计算这些数字的范围：

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;
}

这种方法的问题是，存在范围很大的列表

list C = [{lower:5000001, upper:6999900},{lower:9000000, upper:9999999}]

并且输入意图是将一小组数字（不一定是范围）从这个移动到一个新列表。例如：

Move numbers 5000010 to 5000020 from list C to list B

列表现在看起来像

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}]

将这些数字扩展为用户输入并重新计算它们会占用大量内存。另外 - 输入只是数字列表（而不是范围）

有没有比期望完整列表更好的方法来重新计算数字列表的范围？

Answer 1

如果您的范围比数字少，重新计算范围会更有效。这是更新范围时代码的样子的简短示例。

jsfiddle

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);

如果范围也非常多，您可以保持范围列表排序并使用二进制搜索来查找受移动影响的范围。也许甚至可以改变列表而不是重新创建它们，这取决于您的用例和您需要处理的数据量。

Answer 2

完全没有必要展开号码列表and/or一一检查。检查两个范围是否重叠并计算重叠部分相当简单。下面是一个函数：

接受 ranges 的数组，格式为 [{lower: x, upper: y}, ...]
和 range 删除 {lower: x, upper: y}

和returns：

result数组
和 removed 包含已成功删除的范围的数组（可以直接插入到“移动到”数组中）。

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>

当一些数字在列表之间洗牌时如何重新计算范围

How to recompute ranges when some numbers are shuffled between lists

javascript

arrays

range