Как пересекаются интервалы в Javascript?

Question

В качестве входных данных у меня есть строка и массив интервалов с цветами:

//           0123456789.123456789.123456789.123456789.123
const str = 'The quick brown fox jumps over the lazy dog.';

const colors = [ 
  {from:  0, to:  8, color: 'red'},
  {from: 10, to: 14, color: 'brown'},
  {from: 16, to: 24, color: 'blue'},
  {from: 20, to: 29, color: 'yellow'}
];

Обратите внимание, что входные интервалы могут пересекаться!

В качестве выходных данных я хочу вычислитьмассив непересекающихся интервалов с цветами и подстроками из заданной строки.Вызов должен выглядеть следующим образом:

result = colorizedStrings (str, colors, 'defaultColor');

Результат должен выглядеть следующим образом:

[
  { from:  0, to:  8, sub: 'The quick',      colors: ['red'           ] },
  { from:  9, to:  9, sub: ' ',              colors: ['defaultColor'  ] },
  { from: 10, to: 14, sub: 'brown',          colors: ['brown'         ] },
  { from: 15, to: 15, sub: ' ',              colors: ['defaultColor'  ] },
  { from: 16, to: 19, sub: 'fox ',           colors: ['blue'          ] },
  { from: 20, to: 24, sub: 'jumps',          colors: ['blue', 'yellow'] },
  { from: 25, to: 29, sub: ' over',          colors: ['yellow'        ] },
  { from: 30, to: 43, sub: ' the lazy dog.', colors: ['defaultColor'  ] },
]

При необходимости выходные интервалы содержат более одного цвета.

Я попытался найти библиотеку Javascript с открытым исходным кодом, которая вычисляет пересечения интервалов.Однако я не смог найти простой и небольшой - библиотеки всегда включали в себя интересные вещи (например, графику, диаграммы и т. Д.).Я ищу здесь "чистую математику".

Можете ли вы помочь мне найти подходящее решение, пожалуйста?

Answer 1

Вы можете отобразить символы и получить цвета для каждого из них, а затем уменьшить этот массив для получения кластеров одинаковых цветов.

function colorizedStrings(string, colors, defaultColor) {
    return Array
        .from(string, (sub, i) => {
            var t = colors.filter(({ from, to }) => from <= i && i <= to).map(({ color }) => color);
            return { sub, colors: t.length ? t : [defaultColor] };
        })
        .reduce((r, { sub, colors }, i) => {
            var last = r[r.length - 1];
            if (last && last.colors.join() === colors.join()) {
                ++last.to;
                last.sub += sub;
            } else {
                r.push({ from: i, to: i, sub, colors });
            }
            return r;
        }, []);
}

//         0123456789.123456789.123456789.123456789.123
var str = 'The quick brown fox jumps over the lazy dog.',
    //     ---------
    //               -----
    //                     ---------
    //                         ----------
    colors = [{ from: 0, to: 8, color: 'red' }, { from: 10, to: 14, color: 'brown' }, { from: 16, to: 24, color: 'blue' }, { from: 20, to: 29, color: 'yellow' }],
    result = colorizedStrings(str, colors, 'defaultColor');

console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Может быть немного быстрее с сохранением цветов по заданному индексу.

function colorizedStrings(string, colors, defaultColor) {
    var colorsAtIndex = [];
    colors.forEach(({ from, to, color }) => {
        do {
            (colorsAtIndex[from] = colorsAtIndex[from] || []).push(color);
        } while (from++ < to)
    });
    return Array
        .from(string, (sub, i) => ({ sub, colors: colorsAtIndex[i] || [defaultColor] }))
        .reduce((r, { sub, colors }, i) => {
            var last = r[r.length - 1];
            if (last && last.colors.join() === colors.join()) {
                ++last.to;
                last.sub += sub;
            } else {
                r.push({ from: i, to: i, sub, colors });
            }
            return r;
        }, []);
}

var str = 'The quick brown fox jumps over the lazy dog.',
    colors = [{ from: 0, to: 8, color: 'red' }, { from: 10, to: 14, color: 'brown' }, { from: 16, to: 24, color: 'blue' }, { from: 20, to: 29, color: 'yellow' }],
    result = colorizedStrings(str, colors, 'defaultColor');

console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Наконец (более сложная версия без использования отдельных букв и более коротких циклов)

function colorizedStrings(string, colors, defaultColor) {
    const addColor = (array, color) => array.filter(v => v !== 'defaultColor').concat(color);
    return colors.reduce((r, { from, to, color }) =>
        r.reduce((s, o) => {
            if (to < o.from || from > o.to) { // no appearance
                s.push(o);
            } else if (from <= o.from && to >= o.to) { // same part
                o.colors = addColor(o.colors, color);
                s.push(o);
            } else if (from <= o.from && to <= o.to) { // split in two parts
                s.push(
                    { from: o.from, to: to, sub: string.slice(o.from, to + 1), colors: addColor(o.colors, color) },
                    { from: to + 1, to: o.to, sub: string.slice(to + 1, o.to + 1), colors: o.colors }
                );
            } else if (o.from <= from && o.to <= to) { // split in two parts
                s.push(
                    { from: o.from, to: from, sub: string.slice(o.from, from), colors: o.colors },
                    { from: from, to: o.to, sub: string.slice(from, o.to + 1), colors: addColor(o.colors, color) }
                );
            } else if (from > o.from && to < o.to) { // split in three parts
                s.push(
                    { from: o.from, to: from - 1, sub: string.slice(o.from, from), colors: o.colors },
                    { from: from, to: to, sub: string.slice(from, to + 1), colors: addColor(o.colors, color) },
                    { from: to + 1, to: o.to, sub: string.slice(to + 1, o.to + 1), colors: o.colors }
                );
            } else {
                s.push(o);
            }
            return s;
        }, []),
        [{ from: 0, to: string.length - 1, sub: string, colors: ['defaultColor'] }]);
}

var str = 'The quick brown fox jumps over the lazy dog.',
    colors = [{ from: 0, to: 8, color: 'red' }, { from: 10, to: 14, color: 'brown' }, { from: 16, to: 24, color: 'blue' }, { from: 20, to: 29, color: 'yellow' }],
    result = colorizedStrings(str, colors, 'defaultColor');

console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }