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

• Anonymous
  August 20, 2004
  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
  
  
• Anonymous
  August 20, 2004
  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?
• Anonymous
  August 20, 2004
  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?
• Anonymous
  August 20, 2004
  The comment has been removed
• Anonymous
  August 20, 2004
  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).
• Anonymous
  August 21, 2004
  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);
  }
  
• Anonymous
  August 21, 2004
  I hope I didn't just flood the comments with posts. None of my responses seem to be going through.
• Anonymous
  August 21, 2004
  The comment has been removed
• Anonymous
  August 21, 2004
  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.
• Anonymous
  August 21, 2004
  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.
• Anonymous
  August 21, 2004
  It seems like the kind of thing FxCop would be useful for.
• Anonymous
  August 24, 2004
  I just stumbled upon an earlier blog of yours where you talk about using FxCop for this.
  
  Touché.
• Anonymous
  August 24, 2004
  Matthew: While it could be done in FxCop, I actually think that immutability of structs should be a first-class feature of the language.
• Anonymous
  August 24, 2004
  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.
• 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