Inserting interval into a collection

The task is fairly simple. I want to create a collection of intervals and implement an Add method which would insert new intervals to the collection and merge overlapping ones. I would also like this method to somehow tell me which parts of the added interval were not in the collection before adding.

Here is an interval implementation, which is pretty straightforward:

public class Interval
{
    public Interval(int start, int end)
    {
        Start = start;
        End = end;
    }

    public Interval ()
    {
    }

    public int Start { get; set; }
    public int End { get; set; }

    public bool Contains(int value)
    {
        return value = Start;
    }

    public bool Contains(Interval other)
    {
        return Contains(other.Start) && Contains(other.End);
    }

    public override string ToString()
    {
        return String.Format("[{0}, {1}]", Start, End);
    }

    public Interval Clone()
    {
        return new Interval(Start, End);
    }
}

Implementing the collection proved to be a much trickier task.

```
public class IntervalCollection
{
private readonly List _intervals = new List();

public IEnumerable Intervals { get { return _intervals; } }

public bool TryAdd(Interval interval, out List addedSections)
{
addedSections = null;
int indexToDelete = -1;
int countToDelete = 0;
Interval mergedInterval = null;
var i = 0;
//in this loop i am trying to locate intersections with existing intervals
for (; i interval.Start)
{
//start of added interval does not intersects with anything
mergedInterval = new Interval(interval.Start, -1);
addedSections = new List { mergedInterval.Clone() };
indexToDelete = i;
}
else if (current.Contains(interval.Start))
{
//start of added interval intersects with one of the

Unless necessary you should consider making your Interval immutable by making the sets private. It's easier to deal with such "value containers" if they're immutable (see Point, DateTime, etc.).

Also at the moment you can break your collection by doing the following (also it's non obvious what happens, to be honest):

List intervals = new List();
IntervalCollection intervalsCollection = new IntervalCollection();
intervalsCollection.TryAdd(new Interval(1, 5), out intervals);
intervalsCollection.TryAdd(new Interval(20, 25), out intervals);
intervalsCollection.TryAdd(new Interval(7, 10), out intervals);

Interval intervalA = new Interval(100, 120);
intervalsCollection.TryAdd(intervalA, out intervals)
intervalA.Start = 7;
intervalA.End = 50;

Prints:

[1, 5]
[7, 10]
[20, 25]
[7, 50]

This class would benefit a lot from documentation. F.e. it is not obvious if the start or end is inclusive or exclusive. Make sure to cover this in the docs.

Adding an Intersects function would also help in the long run, especially when checking in the list.

foreach (Interval interval : theIntervalsYouHave)
{
    if (interval.Intersects(intervalToInsert))
    {
        // ...

An Extend function might also be interesting for later use, something like this:

function Interval Extend(Interval extendWith)
{
    return new Interval(
        Math.Min(Start, extendWith.Start),
        Math.Max(End, extendWith.End));
}

There's no checking if Start is greater then End, is this a valid Interval?

new Interval(10, 5);

var i = 0;
//in this loop i am trying to locate intersections with existing intervals
for (; i < _intervals.Count; i++)
{

You did not reuse i for something different then the loop counter, did you? That's bad, either rename it accordingly or use a different variable for whatever you need to do outside of the loop.

The name IntervalsCollection suggests that it implements ICollection or Icollection (or inherits from one of the implementing classes), yet this is not the case. Either rename the class or actually implement ICollection...or clearly document why this is not the case.

If I see this correct, IntervalsCollection.TryAdd() does not really try to add an interval, it will add it, merge it with another or not add it.

Without knowing your exact usage, maybe a better approach would be to provide a immutable collection which needs to be recreated every time.

• You make Interval immutable.

• You write an implementation of ICollection (called Intervals, there might be a better name) which is readonly.

• You create a static constructor/factory function Merge which accepts the original collection and a new value to add to it and returns a new collection. You can add overloads as you see fit (f.e. one that only accepts Intervals without a prior collection).

That twill leave you with a very slick interface (and much less glue), which looks like this:

Intervals intervals = Intervals.Merge(intervalA, intervalB, intervalC);
Intervals extended = Intervals.Merge(intervals, intervalD);

And no way to break the list.

StackExchange Code Review Q#37729, answer score: 5