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

• Anonymous
  August 19, 2004
  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!

• Anonymous
  August 19, 2004
  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@
  

• Anonymous
  August 19, 2004
  Dithermaster, very nice.

• Anonymous
  August 19, 2004
  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? :)

• Anonymous
  August 19, 2004
  The comment has been removed

• Anonymous
  August 19, 2004
  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.
  
  
  

• Anonymous
  August 19, 2004
  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.

• Anonymous
  August 19, 2004
  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;
  }

• Anonymous
  May 31, 2007
  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

• Anonymous
  June 16, 2009
  PingBack from http://topalternativedating.info/story.php?id=10942