Some good feedback on the Range post.
Dithermaster says “it's *much* easier to find out of they DON'T overlap” and proposes:
! ( (end2 < start1) || (start2 > end1) );
If we apply DeMorgan’s Law, we get:
(! (end2 < start1) && !(start2 > end1) );
And
(end2 >= start1) && (start2 <= end1);
Right? Even simpler. However, this idea disappears in my new code, as I do comparisons on the whole ranges, as suggested by Thomas Eyde:
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;
}
They bring different kinds of simplicity to the problem.
James Manning is the first to notice the bugs in my unit tests which allow bugs in my code to get by. Those are now fixed.
Mikeb notices that out-of-order parameters to the range can get you into trouble. I’m not sure which way to go on this. I decided that you’d be surprised that:
new Range(s, e).Start != s
so I went with the exception.
I thought pretty hard about whether Ranges should be constrained to IComparable types. I can’t think of any cases of ranges of non-ordered items, but I don’t want to make the constraint if I don’t have to. However, adding the constraint makes my code a bit simpler. In the end, I decided to take the constraint, solving the 99% case.
I also thought hard about whether ‘Overlaps’ should be a method on Range. It’s clear that ‘Contains’ should be, but I’m not sure where to put a method that acts on two peers. In the end, I decided to put the logic on an instance, and leave the static class for convenience of callers.
One thing I find myself desparately wishing for is operator constraints on generics. Then I could use ‘<’ and friends, instead of:
return this.Start.CompareTo(other) <= 0 && this.End.CompareTo(other) >= 0;
Luckily I only have to compare in 3 places.
The logic does seem to be much simpler now & easier to read. I’m happy about that.
Here’s the code:
class Range<T> where T : IComparable<T>
{
public readonly T Start;
public readonly T End;
// static void Swap<U>(ref U left, ref U right)
// {
// U u = left;
// left = right;
// right = u;
// }
public Range(T start, T end)
{
if (start.CompareTo(end) > 0)
{
throw new ArgumentException("Arguments are out of order");
// you may decide to just allow this & reorder, but I'm
// not sure that's a good idea.
//Swap(ref start, ref end);
}
this.Start = start;
this.End = end;
}
public bool Contains(T other)
{
return this.Start.CompareTo(other) <= 0 && this.End.CompareTo(other) >= 0;
}
public bool Overlaps(Range<T> that)
{
return this.Contains(that.Start) || this.Contains(that.End);
}
}
static class Range
{
public static bool Overlap<T>(Range<T> left, Range<T> right)
where T : IComparable<T>
{
return left.Overlaps(right);
}
}
And the revised tests:
Range<int> r = new Range<int>(1, 3);
Debug.Assert(r.Contains(2));
Debug.Assert(!r.Contains(5));
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))
));
}
Thanks for all your ideas. J