Merging an overlapping collection of intervals

Question

I'm getting myself acquainted with Rust and decided to implement the classical overlapping intervals problem.

Here is a statement of the problem:

Given a collection of intervals, write a function that merges all overlapping intervals and prints them out.

For example, given [1, 3], [2, 6], [8, 10], and [7, 11], the function should print [1, 6], [7, 11]. Or given [5, 12], and [8, 10] the function should print [5, 12].

You can assume that the first element of each interval is always less or equal than the second element of the interval.

This is my implementation:

use std::cmp;
use std::fmt::Write;

//--------------- Range ---------------//

#[derive(Copy, Clone)]
struct Range{
    start: i32,
    end: i32,
}

fn new_range(start: i32, end: i32)->Range{
    Range{
        start: start,
        end: end,
    }
}

impl Range{
    fn overlaps(&self,other: &Range) -> bool{
        (other.start >= self.start && other.start <= self.end)
        || (other.end >= self.start && other.end <= self.end)
    }

    fn merge(&mut self, other: &Range){
        self.start = cmp::min(self.start, other.start);
        self.end = cmp::max(self.end, other.end);
    }

    fn to_string(&self)->String{
        format!("[{},{}]",self.start,self.end)
    }
}

//--------------- RangeStack ----------------//

struct RangeStack{
    ranges: Vec<Range>,
}

fn range_stack_with_ranges(ranges : &Vec<Range>)->RangeStack{
    let mut raw_ranges = ranges.to_vec();
    raw_ranges.sort_by(|a,b| a.start.cmp(&b.start));

    let mut range_stack = RangeStack{
        ranges: Vec::new(),
    };

    for range in raw_ranges.iter(){
        range_stack.add(range);
    }

    range_stack
}

impl RangeStack{

    //private
    fn add(&mut self,range :&Range){
        if self.ranges.len() == 0 {
            self.ranges.push(range.clone());
        }else if self.ranges.last_mut().unwrap().overlaps(range){
                self.ranges.last_mut().unwrap().merge(range);
        }else{
                self.ranges.push(range.clone());
        }
    }

    fn to_string(&self) -> String {

        let mut res = String::new();
        for range in self.ranges.iter() {
            write!(&mut res, "{}", range.to_string()).unwrap();
        }

        res
    }
}

//--------------- Main ---------------//

fn main() {
    let v = vec![
        new_range(3,6),
        new_range(1,5),
        new_range(7,11),
        new_range(9,12),
        new_range(4,8),
    ];

    let rs = range_stack_with_ranges(&v);
    print!("Result: {}\n",rs.to_string());
}

I would appreciate it if someone could review the Rust code and let me know if there is anything that is not idiomatic. In particular, I'm not sure if my usage of mut would be considered ideal.

Answer 1

Some style issues:

• Space before {
• Spaces around ->
• Space after ,
• No space before :
• Space before else
• Indent else blocks 4 characters

Make constructor functions part of the impl:

impl Range {
    fn new(start: i32, end: i32) -> Range {
        Range {
            start: start,
            end: end,
        }
    }
}

Instead of creating a to_string method, implement Display instead. This allows you to automatically get .to_string(), but even better, means you can format the object without extraneous allocation:

impl fmt::Display for Range {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "[{},{}]", self.start, self.end)
    }
}

No need to use iter() when using a for loop on a slice or Vec, just take a reference:

for range in &self.ranges { ... }

Use pattern matching to avoid all the unwrap calls in RangeStack::add:

fn add(&mut self, range: &Range) {
    if let Some(last) = self.ranges.last_mut() {
        if last.overlaps(range) {
            last.merge(range);
            return;
        }
    }

    self.ranges.push(range.clone());
}

Never take a &Vec<T> as an argument. It needlessly limits what types you can accept. In your case, it also allows you to avoid the allocation of the vector in your main. Use a slice instead:

fn with_ranges(ranges: &[Range]) -> RangeStack { ... }

You probably always want to implement Debug, usually done via derive:

#[derive(Debug, Copy, Clone)]
struct Range { ... }

Consider making your with_ranges constructor more generic by implementing FromIterator:

impl FromIterator<Range> for RangeStack {
    fn from_iter<I>(iterator: I) -> Self
        where I: IntoIterator<Item=Range>
    {
        let mut raw_ranges: Vec<_> = iterator.into_iter().collect();
        // ...
    }
}

All together, this now looks like

use std::{cmp, fmt};
use std::iter::FromIterator;

#[derive(Debug, Copy, Clone)]
struct Range {
    start: i32,
    end: i32,
}

impl Range {
    fn new(start: i32, end: i32) -> Range {
        Range {
            start: start,
            end: end,
        }
    }

    fn overlaps(&self, other: &Range) -> bool {
        (other.start >= self.start && other.start <= self.end)
        || (other.end >= self.start && other.end <= self.end)
    }

    fn merge(&mut self, other: &Range) {
        self.start = cmp::min(self.start, other.start);
        self.end = cmp::max(self.end, other.end);
    }
}

impl fmt::Display for Range {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "[{},{}]", self.start, self.end)
    }
}

#[derive(Debug, Clone)]
struct RangeStack {
    ranges: Vec<Range>,
}

impl RangeStack {
    fn add(&mut self, range: &Range) {
        if let Some(last) = self.ranges.last_mut() {
            if last.overlaps(range) {
                last.merge(range);
                return;
            }
        }

        self.ranges.push(*range);
    }
}

impl fmt::Display for RangeStack {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        for range in &self.ranges {
            try!(write!(f, " {}", range));
        }
        Ok(())
    }
}

impl FromIterator<Range> for RangeStack {
    fn from_iter<I>(iterator: I) -> Self
        where I: IntoIterator<Item=Range>
    {
        let mut raw_ranges: Vec<_> = iterator.into_iter().collect();
        raw_ranges.sort_by(|a,b| a.start.cmp(&b.start));

        let mut range_stack = RangeStack {
            ranges: Vec::new(),
        };

        for range in &raw_ranges {
            range_stack.add(range);
        }

        range_stack
    }
}

impl<'a> FromIterator<&'a Range> for RangeStack {
    fn from_iter<I>(iterator: I) -> Self
        where I: IntoIterator<Item=&'a Range>
    {
        iterator.into_iter().cloned().collect()
    }
}

fn main() {
    let v = [
        Range::new(3, 6),
        Range::new(1, 5),
        Range::new(7, 11),
        Range::new(9, 12),
        Range::new(4, 8),
    ];

    let rs: RangeStack = v.iter().collect();
    print!("Result: {}\n", rs);
}

Answer 2

All of Shepmaster's suggestions are good, so I'm going to assume them in my review.

---

All of your methods are extremely generic. The sort_by you do over your values, for one, prevents any case where the start values are out of order.

This means much of your code can never run.

More local and private implementations are likely to be simpler and better covered by testing. (On the other hand, your Ranges would even be better off parametrized over a type.)

For example,

fn overlaps(&self, other: &Range) -> bool {
    (other.start >= self.start && other.start <= self.end)
    || (other.end >= self.start && other.end <= self.end)
}

fn add(&mut self, range: &Range) {
    ... last.overlaps(range) ...
}

assumes but does not require last.start <= range.start, and then does even not use that fact! For if you used that fact, you could have just done

fn add(&mut self, range: &Range) {
    ... last.end >= range.start ...
}

and avoided the function.

Let's consider the function again, though. I always suggest writing &&-chained comparisons such that all operations are in the same direction:

fn overlaps(&self, other: &Range) -> bool {
       (self.start <= other.start && other.start <= self.end)
    || (self.start <= other.end   && other.end   <= self.end)
}

This way it is easy to read as "other.start is between self.start and self.end OR other.end is between self.start and self.end".

Even better would be to write contains:

fn overlaps(&self, other: &Range) -> bool {
    self.contains(other.start) || self.contains(other.end)
}

But in the general case, this isn't correct. Consider:

     other
|--------------|
   |------|
     self

Of course, this doesn't matter because your code assumes self.start < other.start. However, this is never made explicit. Thus you end up with code that is broken for the untested general case and inefficient for the specific case.

You can also trivially remove merge by moving its functionality inline.

Another think I don't get is why RangeStack deserves to be a type. Generally, it seems that your code works along the lines of

1. Get input

2. Put input into an iterator

3. Call function, which

   a. Puts input back into new collection

   b. Sorts collection

   c. Creates newer collection, a RangeStack

   d. Merges new collection into newer collection

This might seem neat for the user, but it's a whole lot of work that seems to have absolutely no benefit. Here's something simpler:

1. Get input

2. Sort input

3. Call function, which

   a. Iterates input

   b. Yields output from a new iterator

Thus no allocations are needed, and the user has no difficulty allocating their new merged result or just looping over it if no intermediate is needed.

To back this idea up in prior art, we already have APIs for sorted slices. This would just be another, so to speak.

We'd really like to write this in terms of a generator. Eg. the Python

def merge_ranges(ranges):
    last = ranges.next()

    for new in ranges:
        if last.end >= new.start:
            last.end = max(last.end, new.end)
        else:
            yield last
            last = new

    yield last

However, since we have to save and restore state manually that turns into something more like

fn next(&mut self) -> Option<Range> {
    // Are we still in the loop?
    if let Some(_) = self.last {
        // Collect 
        for new in &mut self.values {
            if ret.end < new.start {
                self.last = Some(new);
                return Some(ret);
            }

            ret.end = cmp::max(ret.end, new.end);
        }

        self.last = None;
        return Some(ret);
    }

    None
} 

At this point, Range provides no real benefit (semantic or otherwise) over a plain old std::ops::Range, so for simplicity I'd use that instead. I suppose the fact std::ops::Range is an iterator is a little unfitting, but it's not really worrisome.

So here's my suggestion:

use std::cmp;
use std::ops::Range;

struct MergedRanges<I> {
    values: I,
    last: Option<Range<i32>>
}

fn merge_ranges<I>(iterator: I) -> MergedRanges<I::IntoIter>
    where I: IntoIterator<Item=Range<i32>>
{
    let mut iterator = iterator.into_iter();
    let last = iterator.next();

    MergedRanges {
        values: iterator,
        last: last,
    }
}

impl<I> Iterator for MergedRanges<I>
    where I: Iterator<Item=Range<i32>>
{
    type Item = Range<i32>;

    fn next(&mut self) -> Option<Range<i32>> {
        // Are we still in the loop?
        if let Some(mut last) = self.last.clone() {
            for new in &mut self.values {
                if last.end < new.start {
                    self.last = Some(new);
                    return Some(last);
                }

                last.end = cmp::max(last.end, new.end);
            }

            self.last = None;
            return Some(last);
        }

        None
    } 
}

fn main() {
    let mut v = vec![3..6, 1..5, 7..11, 9..12, 4..8];

    v.sort_by(|left, right| left.start.cmp(&right.start));
    let merged: Vec<_> = merge_ranges(v).collect();

    for range in &merged {
        print!(" {:?}", range);
    }
    println!("");
}

The last thing to do would be move from Range<i32> to Range<T: One + Step + Ord> or such, if you want.