jcbp jcbp - 3 months ago 15
Javascript Question

Filter redundant objects from array with lodash

Data

var ranges = [
{ start: 2, end: 5 },
{ start: 8, end: 12 },
{ start: 15, end: 20 },
{ start: 9, end: 11 },
{ start: 2, end: 6 }
];


Each object represents a range. I need to remove the ranges that are contained into another.
That is, between two redundant objects I need to keep the longer range.

I wrote this code, but I wonder if there is a better way to achieve this using lodash.

var Range = {
contains: function(r1, r2) {
return r2.start >= r1.start && r2.end <= r1.end;
}
};

var result = _.chain(ranges)
.filter(function(r2) {
return !_.some(ranges, function(r1) {
return r1 != r2 && Range.contains(r1, r2);
});
})
.value();

console.log(result);


Output

[
{ start: 8, end: 12 },
{ start: 15, end: 20 },
{ start: 2, end: 6 }
]

Answer

If you want to avoid redundant comparisons for large datasets you could have the ranges sorted before comparing them:

var sorted = _.orderBy(ranges, ['start', 'end'], ['desc', 'asc']);

var result = _.chain(sorted)
    .filter(function(r2, i) {
        //Only the items after r2 may contain r2 so we slice the array.
        return !_.some(_.slice(sorted,i+1), function(r1) {
            // You could just test if r2.end <= r1.end here
            // We already know that r2.start >= r1.start
            return Range.contains(r1, r2);
        });
    })
    .value();

All the items before r2 start after r2 and can't contain it, so we don't compare them.

I don't think lodash offers any way to do this out of the box.

Comments