This post will be quite long, since not only am I going to present the Range class I wrote, but I’m also going to go into some of the decisions I made and why I made them. First off, I’d like to thank Jay Bazuzi and his readers for his article and its follow-up where they created a simple Range class.
Generic or non-Generic?
Well-this question was easy enough in its way; it makes sense that we make a Range class generic. However, there was an implication on this. Obviously any kind of range will need to be able to compare its items, but which IComparable should we support? IComparable<T> has the advantage of being more strongly typed, but IComparable is probably more widely supported. It took me a while to decide, but I finally settled on IComparable<T>, largely because strong type safety is a good thing. In any case, the main Framework classes support it, and for custom classes, it’s not difficult to add.
Class or Struct?
This was a question that took a while to decide. I actually originally settled on struct, but then switched to class when I decided I wanted to return null from some methods. Then I changed my mind again and instead returned Nullable<Range<T>>. Finally, the decision was made for me due to two design decisions:
1. I wanted to have child classes that inherited from Range<T>
2. I wanted to ensure that the Range<T>’s created by a set of factory methods only.
Since you cannot inherit from structs, and anyone can create a struct using its default constructor, I had settled (by default) on a class.
Mutable or Immutable?
This was another tough call. By making the Range<T> mutable, I would certainly simplify my life, but there were some points against too. First off I was at that point considering a RangeList<T> that would keep a set of sorted ranges, trying to keep contiguous ranges together. If we could change the values of the range underneath the collection, this would become very difficult to keep in a consistent state. What finally hit the nail in the coffin though were the two child classes that I created, let’s look at the classes:
In this diagram you can see that I decided on a Range<T> base class that would contain the UpperBound and LowerBound properties, and handle all the comparisons and modifications necessary. Sometimes we would want to associate a range with something other than just the range, some extra data. To cater for this possibility, I created the Range<TKey, TValue> class, which inherited from the base Range<T>, but added a Value property. Finally, I also handled a special case, a case where the range represented an array, similar to Range<TKey, TValue>. but different in two respects. Firstly, it inherited from Range<int> specifically, and secondly the value was an array just for easier access to the elements. To be honest I’m still not sure about this one.
Anyway, these subclasses decided the mutability question for me. It’s all very well to talk about splitting a Range<T>, but what exactly does it mean to split a Range<TKey, TValue>? What should I do with the value? If I didn’t know what it was, how could I meaningfully handle joining or splitting ranges containing such values? I couldn’t, so I decided to make the ranges immutable. All the “modification” methods on Range<T> you see in that diagram return completely new ranges. More particularly a call to Range<TKey, TValue>’s Union would return a Range<TKey>, without the associated value. All of the main methods here return simple ranges, without associated extra data. They are used, in a sense to tell the developer what to do:
var start = Range.Create(0, 5, "Hello ");
var end = Range.Create(6, 10, "World");
var join = start.Union(end); // 0->10
In the example above, the last Range tells us that the union of start and end is a range from 0 to 10; it doesn’t know to concatenate the two strings though. That would be for the programmer to determine, perhaps something like:
var final = Range.Create(join.LowerBound, join.UpperBound, start.Value + end.Value);
So, as with the class vs. struct decision, in a very real way it was previous decisions that forced my hand on this one. The lesson is important I think. Quite often decisions made much earlier in the process constrain your choices later on. In a sense, this is the point of refactoring, to once again open up your available options.
Interfaces and Overloads
The one interface to implement was pretty obvious, IComparable<Range<T>>. A complete no-brainer there. I also thought it was important to provide comparison against T, so that’s why IComparable<T>. This segues nicely into quite an interesting digression. Given a range {0->10}, is it bigger or smaller than 5? The comparisons were to give me nightmares. I created all sorts of spaghetti code, made even more monstrous by a doomed decision to try and support not only infinities, but also limits, values that were not quite the given value. So we could have a range {[5]->10} which meant that the range extended from just after 5 up to and including 10. Now, ask yourself this question; forget the simple comparison I gave you earlier, which is now larger: {[5]->10} or {1->[5]}, or what about {∞->[5]} vs. {5->[7]}? I found myself in a nightmare world in which comparisons changed their meaning based on which side of the comparison and which side of the range they were on.
I had forgotten the cardinal rule of software development: Keep it Simple Stupid. For goodness sakes if I needed infinities and limits, I could bloody well implement another class that handled them, and just pass it in as the type parameter to Range! Trying to implement a range that did everything was an exercise in futility. More particularly, what if the developer using my class didn’t want to have infinities, or the hassle of figuring out obscure comparison rules?
Anyway, after a fair bit of time excising the horrific comparison code and unit tests, I settled on a simple solution, comparisons would be against the LowerBound. So {5->10} < 6. Just for jollies I decided to also support IComparable, where I just tested the type of the incoming object and passed it to the relevant CompareTo method.
I also overloaded Equals. Now, I decided that Equals would only ever return true for two ranges. I’m not fully decided on this one. It means I have the unusual situation where {5->10}.CompareTo(5) == 0, but {5->10}.Equals(5) == false. However, as I see it Equals is a much stricter comparison than CompareTo. If you disagree, let me know.
To make life a bit easier I also provided a simple little overload of ToString that gives me my nice {x->y} in the debugger.
Operators
This was fun. I normally don’t do operator overloading, simply because there isn’t much call for it. Let’s face it, what exactly does it mean to add two Customer objects? I implemented the usual comparison operators, and also implemented three modification operators:
· ^ - Which I took to mean Complement, removing a range from another.
· | - Which I took to mean Union, coalescing two ranges into one range that spans both.
· & - Which I took to mean Intersect, providing a range for the areas where both ranges overlap.
Again, I’m not 100% sure I’ve done the right thing by providing the modification operators, but I guess I just got carried away.
Iterators
This was quite interesting. I wanted to be able to iterate through a range. In other words (for integers), given {0->5}, to iterate 0, 1, 2, 3, 4, 5. However, since I’m dealing in generics, I don’t really know what the T is, and I especially don’t know what it means to iterate from one T to another. Even for types I do know about, how would I iterate them? I mean, if it was DateTime, would I iterate the seconds, minutes, years? So what I did was take a delegate in the Iterate method called incrementor. It’s a Func<TArg0, TResult>> and so can be used with a lambda expression. So you can do this for example:
Range<int> range = Range.Create(0, 5);
foreach (int i in range.Iterate(x => x + 1))
{
Debug.WriteLine(i);
}
I thought it was a nice touch. Just for completeness I provided a ReverseIterate that takes a decrementor. So, the meaning of a range is left up to the person supplying the incrementor, and a single range can mean different things at different times. Cool!Factory class
A nice touch from the original article by Jay was to have a static Range class that takes the methods that operate on multiple ranges. I decided not to completely go that route, but all the stuff that operated on lists of ranges, as well as the factory methods I put in this class:
Covariance/Contravariance
C# does not support covariance for generics. What this means is that if I have a method like this:
IEnumerable<Range<T>> Find<T>(this IEnumerable<Range<T>> ranges, Func<Range<T>, bool> predicate)
I cannot pass a List<RangeArray<object>> into the ranges parameter. Even though the list implements IEnumerable<T>, and the T in this case is inherited from Range<T>, it does not see these two types as compatible. Apparently there is good reason for this, but I don’t know what it is.
So, in order to get around this problem, I originally decided to create a RangeList<T> and a RangeList<TKey, TValue> and a RangeArrayList<T>, all of which would implement IEnumerable<Range<T>>, and thus the methods on the static class would accept them, and there would be celebrations throughout the land. Well, I did, and it worked fine, but it niggled at me. I realized that the only reason those collection classes existed was to get around the covariance problem, but that they also constrained the solution. What if someone wanted a Dictionary<Range<T>, string>, and wanted to pass the Keys enumerator to one of my methods? Well, they wouldn’t be able to, all because of bloody covariance. So, if you cast your eye up to that class diagram above, you’ll see my solution.
First I made all the constructors of my classes internal, ensuring that no-one could inherit them, just for good measure I marked Range<TKey, TValue> and RangeArray<T> as sealed. Then, I created two overloaded private methods on Range, called MakeCovariant. One took an IEnumerable<Range<TKey, TValue>> and the other an IEnumerable<RangeArray<T>>, and they both returned IEnumerable<Range<T>>. Then I created similar overloads for each of the static methods that called MakeCovariant on their arguments and passed the IEnumerable<Range<T>> to the “master” method. The upshot of all this was that the lack of covariance had now ceased to be a problem as far as my static Range was concerned. This would only work as long as my three classes were all that there was, and no-one created new subclasses, which I’ve ensured.
I guess this wouldn’t be necessary if I had just decided to stick with having the Range class as a struct, but I like having the three Range options, and now I don’t have to have three extra collection classes supporting them.
Anyway, one side-effect of all this is that the Find method is a bit interesting. Have a look at the three Find signatures:
... Find<T> (this IEnumerable<Range<T>> ranges, Predicate<Range<T>> predicate) ...
... Find<TKey, TValue>(this IEnumerable<Range<TKey, TValue>> ranges, Predicate<Range<TKey>> predicate) ...
... Find<T> (this IEnumerable<RangeArray<T>> ranges, Predicate<Range<int>> predicate)
Note that, in all three cases, the predicate takes the base Range<T> class. What this means is that it you attempt something like:
IEnumerable<RangeArray<T>> ranges = /* Create Range */
Range.Find(ranges, x => (x.Values.Count == 0));
You’ll find that the lambda won’t compile. The simple reason is that, despite the fact that the collection contains RangeArray‘s, I’ve only written the predicate to accept Range<T>. I guess I could change it, but it’d mean duplicating the Find functionality, and I’m lazy.
So, have fun with the class, which you can find here. Please note that this is an Orcas project. It doesn’t take too much effort to back-port it to Whidbey though. Let me know if you have any problems, improvements or anything. It has not been rigorously tested, but I’ve included the unit tests I’ve done so far.