Multidimensional array replace with close range Javascript-CodePudding

Let's say we have a List of ranges expressed in arrays with two elements [from, to].

When we add a new array range like [5,8], it should check in List if there is a closest range and then replace it with the new range value. An example is provided below:

Example 1

var List = [[1,2], [3,4], [6,7], [9,10]]

var newData = [5,8]

Expected Output:

[[1,2], [3,4], [5,8], [9,10]]

The [6,7] range is already included in [5,8]

Example 2

var List = [[1,3], [4,6], [8,10]]
var newData = [5,9]

Expected Output:

[[1,3], [4,10]]

CodePudding user response：

Assuming the initial list is well-formed, with its pairs sorted and non-overlapping, you could use binary search to find the end points of a new pair in the array and so determine any overlap. If overlap, splice the array accordingly:

function addSegments(segments, ...pairs) {
    for (let pair of pairs) {
        let [start, end] = pair.map(function (x, i) { // Binary search
            let low = 0, 
                high = segments.length;
                side = 1 - i;
            while (low < high) {
                let mid = (low   high) >> 1;
                if (x < segments[mid][side]) high = mid;
                else low = mid   1;
            }
            return low - (side && segments[low-1]?.[side] === x);
        });
        if (start < end) {
            pair = [
                Math.min(segments[start][0], pair[0]),
                Math.max(segments[end-1][1], pair[1])
            ];
        }
        segments.splice(start, end - start, pair);
    }
}

// Demo
let list = [[1, 2], [3, 4], [6, 7], [9, 10]];
addSegments(list, [5, 8]);
console.log(JSON.stringify(list));

list = [[1, 3], [4, 6], [8, 10]];
addSegments(list, [5, 9]);
console.log(JSON.stringify(list));

CodePudding user response：

If we have two arrays containing all the integers included in the ranges, then we can intersect and see if they overlap. If they do, we create a new range from the union of the two ranges, and use that in the output instead.

So to that end, we define three helper functions, range(), intersect() and union(), and then we use those to generate the output array. If the intersection exists, we overwrite any overlapped range with the new union of the two. I assumed that if two ranges just touched they weren't meant to be combined, so the overwrite is only triggered if the intersection contains more than one element. Also, I added an initial sort.

function add(list, data) {
  
  let buffer = [], idx;
  const range=(a,b)=>Array.from({length:b-a 1}, (_, i)=>(a i));
  const intersect=(a,b)=>a.filter(x=>b.includes(x));
  const union=(a,b)=>[...new Set([...a, ...b])].sort((a,b)=>a-b);
  list.sort((a,b)=>a[0]-b[0]);
  
  list.forEach(el=>{
    
    let x = range(el[0], el[1]);
    let y = range(data[0], data[1]);
    let i = intersect(x, y);
    
    if(i.length>1) {
      let d = union(x,y);
      data = [d[0], d[d.length-1]];
      if(idx) { buffer[idx] = data; }
      else { idx = buffer.push(data)-1; }
    } 
    else { buffer.push(el); };
    
  });
  
  return buffer;
  
}


// DEMO
let List = [[1,2], [3,4], [6,7], [9,10]];
let newData = [5,8];
console.log(JSON.stringify(List));
console.log(JSON.stringify(newData));
console.log(JSON.stringify(add(List, newData)));
console.log('');

List = [[1,3], [4,6], [8,10]];
newData = [5,9];
console.log(JSON.stringify(List));
console.log(JSON.stringify(newData));
console.log(JSON.stringify(add(List, newData)));
console.log('');

// DEMO WITH UNORDERED ELEMENTS
List = [[3,4], [9,10], [6,7], [1,2]];
newData = [5,8];
console.log(JSON.stringify(List));
console.log(JSON.stringify(newData));
console.log(JSON.stringify(add(List, newData)));
console.log('');