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

 

 

Comments (15)
  1. Operator constraints (and method constraints in general) would be nice to have. It reminds me of the IArithmetic proposal that was on OSNews a couple weeks back.

    http://www.osnews.com/story.php?news_id=7930

  2. Matthew W. Jackson says:

    For compairison operations, I’m thinking abuot writing a Comparable<T> struct which wraps an IComparable<T> value and implements all of the needed operators (<, >, <=, >=, !=, ==). Since it’s a struct, it won’t add any memory overhead, and all of the methods should be short, and being non-virtual, they should be inlined by the JIT.

    Any time I would need to store a Comparable value, I could use this instead of the actual value.

    This might make code cleaner, but it also might make it more confusing by adding another layer. I’ll have to try it out next chance I get.

    I’m trying to decide if it should have an implict conversion operator to its underlying type. That way, I could store a Comparable<T> and return it in a function that just returns T.

    Anyone have some thoughts on the pros and cons of this approach?

  3. jaybaz [MS] says:

    Mattew, I’m curious where you’re going with this. I tried playing with some stuff, but didn’t get anywhere. Can you put together an example that demonstrates the idea?

  4. Matthew W. Jackson says:

    // Comparable<T> is a semi-transparent struct for adding comparison operators

    // to the IComparable<T> interface. It can be implicitly converted to and from

    // T, and therefore can be compared to T with any of the comparison operators.

    [CLSCompliant(false)]

    public struct Comparable<T> : IComparable<Comparable<T>>, IComparable

    where T : IComparable<T> {

    private T value;

    public Comparable(T value) {

    this.value = value;

    }

    public T Value {

    get { return this.value; }

    }

    public bool Equals(Comparable<T> other) {

    return this.value.Equals(other.value);

    }

    public int CompareTo(Comparable<T> other) {

    return this.value.CompareTo(other.value);

    }

    public int CompareTo(object obj) {

    if(obj is Comparable<T>)

    return this.CompareTo((Comparable<T>)obj);

    throw new ArgumentException("Invalid argument type", "obj");

    }

    public override int GetHashCode() {

    return this.value.GetHashCode();

    }

    public override bool Equals(object obj) {

    if(obj is Comparable<T>)

    return this.Equals((Comparable<T>)obj);

    return false;

    }

    public override string ToString() {

    return this.value.ToString();

    }

    public static bool operator ==(Comparable<T> comparableValue1, Comparable<T> comparableValue2) {

    return comparableValue1.Equals(comparableValue2);

    }

    public static bool operator !=(Comparable<T> comparableValue1, Comparable<T> comparableValue2) {

    return !comparableValue1.Equals(comparableValue2);

    }

    public static bool operator >(Comparable<T> comparableValue1, Comparable<T> comparableValue2) {

    return (comparableValue1.CompareTo(comparableValue2) > 0);

    }

    public static bool operator <(Comparable<T> comparableValue1, Comparable<T> comparableValue2) {

    return (comparableValue1.CompareTo(comparableValue2) < 0);

    }

    public static bool operator >=(Comparable<T> comparableValue1, Comparable<T> comparableValue2) {

    return (comparableValue1.CompareTo(comparableValue2) >= 0);

    }

    public static bool operator <=(Comparable<T> comparableValue1, Comparable<T> comparableValue2) {

    return comparableValue1.CompareTo(comparableValue2) <= 0;

    }

    public static implicit operator T(Comparable<T> comparableValue) {

    return comparableValue.value;

    }

    public static implicit operator Comparable<T>(T value) {

    return new Comparable<T>(value);

    }

    }

    // Subset of a Range struct (could also be a class) that utilizes the Comparable<T>

    // struct. Notice the contains method, which uses normal comparison operators instead

    // of complicated CompareTo(T) calls.

    [CLSCompliant(false)]

    public struct Range<T> where T : IComparable<T> {

    private Comparable<T> start;

    private Comparable<T> end;

    public Range(T start, T end) {

    this.start = start;

    this.end = end;

    }

    public T Start {

    get { return this.start; }

    }

    public T End {

    get { return this.end; }

    }

    public bool Contains(T other) {

    return (start <= other) && (end >= other);

    }

    }

  5. Matthew W. Jackson says:

    By the way, if the Framework designers decide to include some form of IArithmetic<T> (and I really really really really really really really really hope they do, as it can solve a bunch of generic problems without changing the current languages–ie no immediate need for operator constaints), then I would probably design a similar pattern around that interface as well.

    I’d probably call it struct Number<T> where T : IArithmetic<T>.

    I’d implement all of the operators that make sense for numbers, and then any time I write a generic class that needs to work with numbers, I work with Number<T> instead of T itself, since "value1 + value2" reads much much better than "value1.AddTo(value2)".

    But this whole concept is moot if IArithmetic<T> (or equivalent) is left out of the BCL.

    By the way, I’m really liking the implementation of Comparable<T>. I’m still not sure if the extra layer makes what’s happening in the code less clear, but I really enjoy not having to call CompareTo(T).

  6. jaybaz [MS] says:

    The Comparable<T> is interesting because it’s something the consumer applies, instead of being a feature of the comparable class. It does seem to work quite nicely.

    You used a struct. That’s probably just fine, but I think it’s important that you make fields of a struct ‘readonly’, as mutable structs often have surprising semantics.

    I’d also choose to write 3 of the operators via their complements. At least for me, that means I’m more likely to get it right.

    public static bool operator !=(Comparable<T> comparableValue1, Comparable<T> comparableValue2)

    {

    return !(comparableValue1 == comparableValue2);

    }

  7. Matthew W. Jackson says:

    I hope I didn’t just flood the comments with posts. None of my responses seem to be going through.

  8. Matthew W. Jackson says:

    You are right about mutable structs. I detest them. I do not like System.Drawing.Rectangle for that reason. There are a few exceptions, such as caching a hash code or something, but that does not really change the value. And yeah, I forgot to mark my fields as readonly, but the struct is still (publicly, at least) immutable. Thanks for pointing that out…it is now fixed in my code. Anyway, I am a big fan of structs when it comes to values that need value semmantics. In this case I used a struct to keep from allocating another heap object just because I wanted to add operators to an interface. Not to mention the performance gains when using structs in generics.

  9. Matthew W. Jackson says:

    As for the operators, that is all a matter of taste. I try to minimize the amount of layers in the logic because I tend to like my structs to be performant, but I still do not want to implement the core logic in more than one place, so I am happy with making the operators call the named static methods. Also, it keeps the methods somewhat balanced: == calls Equals and != calls !Equals, instead of == calls Equals and != calls == calls Equals. The other solution is to make the named static methods call the operators, but that always confuses me. I do not really like having a type use its own operators. That is also why I would not implement != to call ==. But as long as the code is correct, I could not care less how other people do it.

  10. jaybaz [MS] says:

    Matthew: No spam that I see.

    If C# were my language, I would add the partially-reserved word ‘mutable’ as a modifier on structs:

    mutable struct S { readonly int x; } // warning: no mutable members

    struct S { int x; } // error: mutable struct not marked as such

    mutable struct S { int x; } // OK

    struct S { readonly int x; } // OK

    then I would go through the .Net FX and fix up all the structs to work correctly; ideally make them all immutable.

  11. Matthew W. Jackson says:

    It seems like the kind of thing FxCop would be useful for.

  12. Matthew W. Jackson says:

    I just stumbled upon an earlier blog of yours where you talk about using FxCop for this.

    Touché.

  13. jaybaz [MS] says:

    Matthew: While it could be done in FxCop, I actually think that immutability of structs should be a first-class feature of the language.

  14. Matthew W. Jackson says:

    Seems like there are new "mistakes" in Whidbey regarding structs. I think that the mutable design of KeyValuePair<K, V> is an incorrect design, but since there are no mutating methods, it shouldn’t cause any direct problems. Still, I consider a Pair to be a value, not a collection of values, and therefore changing one of the members seems wrong. I personally think they should have made Key and Value readonly. The nicest thing about keeping structs immutable is that they follow almost the same semantics of immutable classes, except for the existance of null values.

    I don’t know if it would be worth submitting a suggestion on MSDN about this. It seems that there seems to be a big split on the issue.

  15. 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