javascript - 如何在 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; }