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 removedAnonymous
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 IAnonymous
June 16, 2009
PingBack from http://topalternativedating.info/story.php?id=10942