Merging an overlapping collection of intervals

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.start && other.end String{
format!("[{},{}]",self.start,self.end)
}
}

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

struct RangeStack{
ranges: Vec,
}

fn range_stack_with_ranges(ranges : &Vec)->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();

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 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 for RangeStack {
    fn from_iter(iterator: I) -> Self
        where I: IntoIterator
    {
        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.start && other.end  fmt::Result {
        write!(f, "[{},{}]", self.start, self.end)
    }
}

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

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 for RangeStack {
    fn from_iter(iterator: I) -> Self
        where I: IntoIterator
    {
        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 FromIterator for RangeStack {
    fn from_iter(iterator: I) -> Self
        where I: IntoIterator
    {
        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);
}

StackExchange Code Review Q#103864, answer score: 8