Один из способов определить, перекрывается ли createdRange с одним из ranges, - дать каждому range начальному и конечному индексам, а затем проверить, перекрываются ли индексы createdRange с индексами любого другой диапазон или нет.
Во-первых, давайте изменим форму объекта range с лучшей читаемостью:
{
start: { row: 2, col: 9 },
end: { row: 4, col: 7 }
}
Отображение этого range объекта с тем, который вы определили, просто:
rangeStartLineIndex => start.row
rangeStartColIndex => start.col
rangeEndLineIndex => end.row
rangeEndColIndex => end.col
После всего этого я бы сначала указал на одну маленькую ошибку в логике.
В цикле for вы проверяете, перекрывается ли createdRange с текущим range или нет. Если нет, то вы добавляете , что createdRange в массив диапазонов.
Однако вам нужно только добавить createdRange в ranges , ЕСЛИ ни один из диапазонов не перекрывается с createdRange
Таким образом, правильный цикл for будет выглядеть так:
var hasOverlap = false; // this will tell if any of the ranges overlap
for(var i = 0; i < ranges; i++) {
var overlap = doesThisOverlap(createdRange, ranges[i]);
if(overlap) {
// overlaps, which means we extend the existing range.
// some logic to update the overlapped ranges
hasOverlap = true; // a range has overlapped, set the flag to true
break;
}
}
// Did we see any overlap?
if(!hasOverlap) {
// no we did not, let us add this range to ranges array
// means the new range does not extend an existing range, so add it.
ranges.push(createdRange);
}
Хорошо, теперь давайте посмотрим, как рассчитать индексы для данного диапазона.
Если мы начнем присваивать индексы (начиная с 0) слева направо в сетке,
простая математика говорит, что индекс поля в строке r и в столбце c будет:
index = r * (COL + 1) + c [COL is the total number of columns in the grid]
Вот вспомогательные функции, которые помогут рассчитать индексы в заданном диапазоне:
function getIndex(row, col, COL) {
return row * (COL + 1) + col;
}
function getIndices(range) {
var start = range.start;
var end = range.end;
var startIndex = getIndex(start.row, start.col, COLS);
var endIndex = getIndex(end.row, end.col, COLS);
return { start: startIndex, end: endIndex };
}
Обратите внимание, что getIndices принимает range и выводит объект с индексами start и end. Теперь мы можем рассчитать индексы для createdRange и текущего range. И основываясь на индексах, мы будем знать, перекрываются ли диапазоны или нет.
Теперь проблема сводится к следующему:
У нас есть линия AB, и, учитывая новую строку PQ, выясним, перекрывает ли новая строка PQ AB или нет. (где A, B, P, Q - точки на числовой линии, A
Возьмите ручку и бумагу и нарисуйте несколько линий. Вы узнаете, что существует только два условия, когда линии не будут перекрываться:
Либо Q
Сопоставляя эти наблюдения с нашим range объектом, мы можем сказать, что:
P => createdRange.startIndex
Q => createdRange.endIndex
A => currentRange.startIndex
B => currentRange.endIndex
Вот как это будет выглядеть в коде:
var createdRangeIndices = getIndices(createdRange);
var hasOverlap = false;
for (var i = 0; i < ranges.length; i++) {
var currentRangeIndices = getIndices(ranges[i]);
var overlap = (createdRangeIndices.end < currentRangeIndices.start)
|| (currentRangeIndices.end < createdRangeIndices.start);
if (!overlap) {
// overlaps, which means we extend the existing range.
// some logic to update the overlapped ranges
hasOverlap = true;
break;
}
}
if (!hasOverlap) {
// means the new range does not extend an existing range, so add it.
ranges.push(createdRange);
}
Обратите внимание, что мы избавились от функции doesThisOverlap. Подойдет простой флаг.
Все, что остается сейчас, - это логика для обновления range, если есть перекрытие.
Часть, которую вы уже выяснили в своем вопросе. Мы берем минимум начального индекса и максимум конечного индекса. Вот код для этого:
for (var i = 0; i < ranges.length; i++) {
var currentRangeIndices = getIndices(ranges[i]);
var overlap = (createdRangeIndices.end < currentRangeIndices.start)
|| (currentRangeIndices.end < createdRangeIndices.start);
if (!overlap) {
// overlaps, which means we extend the existing range.
// some logic to update the overlapped ranges
var start, end;
if (currentRangeIndices.start < createdRangeIndices.start) {
start = ranges[i].start;
} else {
start = createdRange.start;
}
if (currentRangeIndices.end > createdRangeIndices.end) {
end = ranges[i].end;
} else {
end = createdRange.end;
}
ranges[i] = { start: start, end: end };
hasOverlap = true;
break;
}
}
И готово!
Вот полный код, который объединяет все биты и кусочки вместе:
var ROWS = 7;
var COLS = 3;
function getIndex(row, col, COL) {
return row * (COL + 1) + col;
}
function getIndices(range) {
var start = range.start;
var end = range.end;
var startIndex = getIndex(start.row, start.col, COLS);
var endIndex = getIndex(end.row, end.col, COLS);
return { start: startIndex, end: endIndex };
}
function addRange(ranges, createdRange) {
var createdRangeIndices = getIndices(createdRange);
var hasOverlap = false;
for (var i = 0; i < ranges.length; i++) {
var currentRangeIndices = getIndices(ranges[i]);
var overlap =
createdRangeIndices.end < currentRangeIndices.start ||
currentRangeIndices.end < createdRangeIndices.start;
if (!overlap) {
var start, end;
if (currentRangeIndices.start < createdRangeIndices.start) {
start = ranges[i].start;
} else {
start = createdRange.start;
}
if (currentRangeIndices.end > createdRangeIndices.end) {
end = ranges[i].end;
} else {
end = createdRange.end;
}
ranges[i] = { start: start, end: end };
hasOverlap = true;
break;
}
}
if (!hasOverlap) {
// means the new range does not extend an existing range, so add it.
ranges.push(createdRange);
}
}
var ranges = []; // stores the range objects that are created earlier.
var rangesToAdd = [
{
start: { row: 2, col: 1 },
end: { row: 6, col: 0 }
},
{
start: { row: 6, col: 2 },
end: { row: 7, col: 2 }
},
{
start: { row: 3, col: 1 },
end: { row: 6, col: 1 }
},
{
start: { row: 6, col: 1 },
end: { row: 6, col: 2 }
}
];
rangesToAdd.forEach(aRange => addRange(ranges, aRange));
console.log(ranges);