Split Overlap Ranges

Question

I have implemented an algorithm for dividing overlapping existing ranges into a list of date / number ranges.

The algorithm is working but I was wondering if you can avoid the last loop of the algorithm.

It's possible?

0-100(red) 90-150(green) 90-150(blue) 140-300(yellow) 170-240(black) 350-530(orange) 50-500(silver) 50-60(pink)

0-49(red) 50-60(red,silver,pink) 61-89(red,silver) 90-100(red,green,blue,silver) 101-139(green,blue,silver) 140-150(green,blue,yellow,silver) 151-169(yellow,silver) 170-240(yellow,black,silver) 241-300(yellow,silver) 301-349(silver) 350-500(orange,silver) 501-530(orange)

Javascript Code:

    function splitRanges(original_intervals) {
    
        for (var to = [], from = [], n, i = original_intervals.length; i--;) {
            if (to.indexOf(n = original_intervals[i].to) < 0)
                to.push(n);
            if (from.indexOf(n = original_intervals[i].from) < 0)
                from.push(n);
        }
    
    
        to.sort(function(a, b) {
            return a - b;
        });
        from.sort(function(a, b) {
            return a - b;
        });
    
    
    
    
        var intervals = [];
        while (to.length) {
            var sFrom = from.shift();
            var sTo = 0;
            if (from.length == 0) {
                sTo = (from.push((n = to.shift()) + 1), n);
    
            } else {
                if (from[0] > to[0]) {
                    while (to[0] < from[0]) {
    
                        from.unshift(to[0] + 1);
                        to.shift();
    
                    }
    
                    sTo = from[0] - 1;
                } else {
                    sTo = from[0] - 1;
    
                }
            }
            intervals.push({
                from: sFrom,
                to: sTo,
                colors: []
            });
        }
    
        /***********************Loop that i want remove*/
    
        intervals.forEach(function(item, index) {
            original_intervals.forEach(function(item1, index1) {
                if ((item.from >= item1.from && item.from <= item1.to) || (item.to >= item1.from && item.to <= item1.to))
                    item.colors.push(item1.color);
            });
    
        });
    
        return intervals;
    }
    
    
    
    
    var r1 = [{
    id: 1,
    from: 0,
    to: 100,
	color:'red'
}, {
    id: 2,
    from: 90,
    to: 150,
	color:'green'
}, {
    id: 3,
    from: 90,
    to: 150,
	color:'blue'
}, {
    id: 4,
    from: 140,
    to: 300,
	color:'yellow'
}, {
    id: 5,
    from: 170,
    to: 240,
	color:'black'
}, {
    id: 6,
    from: 350,
    to: 530,
	color:'orange'
}, {
    id: 7,
    from: 50,
    to: 500,
	color:'silver'
}
, {
    id: 8,
    from: 50,
    to: 60,
	color:'pink'
}

];


console.log(splitRanges(r1));

Nina Scholz Nina Scholz · Accepted Answer · 2017-09-26T17:08:33

You need some iterations, at least the one with getting all range points, and then generate an array out of it and take the subset of colors for each small interval.

var data = [{ from: 0, to: 100, color: 'red' }, { from: 90, to: 150, color: 'green' }, { from: 90, to: 150, color: 'blue' }, { from: 140, to: 300, color: 'yellow' }, { from: 170, to: 240, color: 'black' }, { from: 350, to: 530, color: 'orange' }, { from: 50, to: 500, color: 'silver' }, { from: 50, to: 60, color: 'pink' }],
    ranges = new Set,
    parts,
    result;

data.forEach(({ from, to }) => (ranges.add(from), ranges.add(to)));
parts = [...ranges].sort((a, b) => a - b);
result = parts.slice(1).map(function (a, i, aa) {
    var from = i ? aa[i - 1] : parts[0],
        to = a,
        colors = data.filter(d => d.from <= from && to <= d.to).map(({ color }) => color);
    return { from, to, colors };
});
    
console.log(result);

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

Split Overlap Ranges

1 Answers