Comparing ranges


Ryan Farley talks about comparing date ranges.  In his post is this phrase “First range represented by r1start to r1end and second range represented by r2start to r2end”.  Aha, a code smell!  2 things that are related should have that relationship represented in code.

 

It’s the Range pattern, which Fowler has discussed before.  Here I get to present my attempt at it, using the latest in C# generics technology.

 

    class Range<T>

    {

        public readonly T Start;

        public readonly T End;

 

        public Range(T start, T end)

        {

            this.Start = start;

            this.End = end;

        }

    }

 

Wow, that’s exciting!

 

Now we need some comparison:

 

    static class Range

    {

        public static bool Overlap<T>(Range<T> left, Range<T> right)

            where T : IComparable<T>

        {

            if (left.Start.CompareTo(left.Start) == 0)

            {

                return true;

            }

            else if (left.Start.CompareTo(right.Start) > 0)

            {

                return left.Start.CompareTo(right.End) <= 0;

            }

            else

            {

                return right.Start.CompareTo(left.End) <= 0;

            }

        }

    }

 

The comparison algorithm is identical to Ryan’s, but written differently.  First, because I can’t constrain type parameters to have comparison operators, I have to use IComparable<T>.  Second, I broke out the expression to use if/else.  I find that much easier to read & debug.

 

Note that I put the Overlap method in a new static class, instead of in Range<T>.  That’s so I can write “Range.Overlap(x, y)” instead of “Range<int>.Overlap (x, y)” – the method will infer the type parameter all by itself.

 

 Here are the tests I used.  

 

            Debug.Assert(Range.Overlap(

                new Range<DateTime>(new DateTime(1), new DateTime(2)),

                new Range<DateTime>(new DateTime(1), new DateTime(2))

                ));

 

            Debug.Assert(Range.Overlap(

                new Range<DateTime>(new DateTime(1), new DateTime(3)),

                new Range<DateTime>(new DateTime(2), new DateTime(4))

                ));

 

            Debug.Assert(Range.Overlap(

                new Range<DateTime>(new DateTime(2), new DateTime(4)),

                new Range<DateTime>(new DateTime(1), new DateTime(3))

                ));

 

 

            Debug.Assert(Range.Overlap(

                new Range<DateTime>(new DateTime(3), new DateTime(4)),

                new Range<DateTime>(new DateTime(1), new DateTime(2))

                ));

            Debug.Assert(Range.Overlap(

                new Range<DateTime>(new DateTime(1), new DateTime(2)),

                new Range<DateTime>(new DateTime(3), new DateTime(4))

                ));

Comments (10)
  1. Ryan Farley says:

    Awesome Jay. I agree that my way was riddled with "code smell", but it was more the algorithm I was after, not focused on the implementation (that was up to my friend who called me about this).

    I love how you did this as a range class using generics. Very cool stuff!

  2. Dithermaster says:

    Indeed. A friend approached me years ago about finding if a time range overlaps. There are just so many cases. However, (and the "ah ha!" moment), it’s *much* easier to find out of they DON’T overlap, and negate that.

    In other words (in C):

    overlap = ! ( (end2 < start1) || (start2 > end1) );

    Easy.

    ///d@

  3. Ryan Farley says:

    Dithermaster, very nice.

  4. if (left.Start.CompareTo(left.Start) == 0)

    {

    return true;

    }

    Maybe it’s just a typo in reproduction, but maybe we should add some negative tests and not just 5 positive ones? 🙂

  5. A friend of mine called me yesterday about a scheduling application he is working on. His question was so simple, or so it seemed, but it really drove me nuts. Basically he just wanted to find out if two date ranges intersected at all. Simple enough. It was one of those kinds of answers that you immediately start rattling off the solution, but every thing that started to come out of my mouth was failing my mental unit testing. I’ll admit it threw me for a loop for a short bit.

  6. mikeb says:

    In addition to the typo

    if (left.Start.CompareTo(left.Start) == 0)

    another problem happens if the start and end of a range are out of order.

    Range<int>( 4, 1) and Range<int>( 2, 1) overlap, but I believe the presented code would not detect this.

    Either the Range<T> constructor need to enforce left <= right, or the overlap check needs to handle this situation.

  7. Matthew W. Jackson says:

    I’d vote for the constructor enforcing the order. This would let you create ranges out of variable-data, which may or may not be in the right order (imagine dragging the mouse to select a range on a timeline), and have the Range automatically be in the correct order.

    Besides I’m a little biased, because that’s how MY Range (recently upgraded to Range<T>) struct works. But it also does a LOT of other nifty things.

  8. Thomas Eyde says:

    Isn’t this as easy as to verify if one value is inside the range?

    Overlap(a, b){

    return IsInside(a) || IsInside(b);

    }

    IsInside(a) {

    return IsBetween(a, this.a, this.b) || IsBetween(a, this.b, this.a);

    }

    IsBetween(c, a, b) {

    return a <= c && c <= b;

    }

  9. Quite a long article where I discuss the creation of a generic Range class, and go into the decisions and thinking about many of the design aspects. Touches on lambdas, iterators, generics, and the usual rambling grab-bag of stuff I go on about when I

Comments are closed.

Skip to main content