How do intersect intervals in Javascript?

Question

As an input, I have a string and an array of intervals with colors:

//           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'}
];

Note that the input intervals can intersect!

As output, I want to calculate an array of non-intersecting intervals, with colors and substrings from the given string. The call should look like this:

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

The result should look like this:

[
  { 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'  ] },
]

The output intervals contain more than one color when necessary.

I have tried to find an open source Javascript library that calculates the interval intersections. However, I could not find one that is simple and small – the libraries always included fancy stuff (e.g. graphics, charts, etc.). I am looking for "pure math", here.

Can you help me find a suitable solution, please?

please add what you have tried and what does not work. please have a look here, too: minimal reproducible example — Nina Scholz
– Nina Scholz, Commented Sep 28, 2018 at 12:25
not clear what you're aiming for, some further explanations would help. — ThS
– ThS, Commented Sep 28, 2018 at 12:30
Hi @NinaScholz, I have added a paragraph with "I have tried..." at the end of the question. — Matthias Bohlen
– Matthias Bohlen, Commented Sep 28, 2018 at 12:32
@kiranvj The criteria is that the resulting intervals must not overlap any more. The numbers are always integers. — Matthias Bohlen
– Matthias Bohlen, Commented Sep 28, 2018 at 12:33

Nina Scholz · Accepted Answer · 2018-09-28 18:35:55Z

You could map the characters and get the colors for each of it and then reduce this array for getting clusters of same colors.

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

Maybe a bit faster with storing of the colors at a given index.

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

Finally (a more complicated version without using single letters and shorter looping)

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

Wow, this works as expected, thank you very much! I studied it a little and found out what happens in the code. The complexity depends on string.length and on colors.length. Intuitively, I had expected a solution where the complexity does not depend on string.length, only on colors.length. However, for my purposes, this does not matter because my strings are small.
I knew the answer will be from Nina if the topic is related to arrays. I added the label so that you will notice the question. +1
@MatthiasBohlen, maybe the third approach is waht you want. but it is a bit more complicated, because of the range checks and the splitting into two or three parts.

Collectives™ on Stack Overflow

How do intersect intervals in Javascript?

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related