Ranges with Linq and dictionaries.

Question

I've created a Range type:

public class Range<T> where T : IComparable<T>
{
    public Range(T min, T max) : this(min, max, false) { }
    public Range(T min, T max, bool upperbound)
    {
    }
    public bool Upperbound { get; private set; }
    public T Min { get; private set; }
    public T Max { get; private set; }
    public bool Between(T Value)
    {
        return Upperbound ? (Min.CompareTo(Value) < 0) && (Value.CompareTo(Max) <= 0) : (Min.CompareTo(Value) <= 0) && (Value.CompareTo(Max) < 0);
    }
}

I want to use this as key in a dictionary, to allow me to do a search based upon a range. And yes, ranges can overlap or there might be gaps, which is part of the design. It looks simple but I want the search to be even a bit easier! I want to compare a range with it's value of type T, so I can use: myRange == 10 instead of myRange.Between(10).

How? :-) (Not wanting to break my head over this. I'll probably find the answer but maybe I'm re-inventing the wheel or whatever.)

---

The things I want to do with this dictionary? Well, in general I will use the range itself as a key. A range will be used for more than just a dictionary. I'm dealing with lots of data that have a min/max range and I need to group these together based on the same min/max values. The value in the dictionary is a list of these products that all have the same range. And by using a range, I can quickly find the proper list where I need to add a product. (Or create a new entry if no list is found.)

Once I have a list of products grouped by ranges, I can start searching for values that fir within specific ranges. Basically, this could be a Linq query on the dictionary of all values where the provides value is between the Min and Max value.

I am actually dealing with two such lists. In one, the range is upper-bound and the other lower-bound. There could be more of these kinds of lists, where I first need to collect data based on their range and then find specific items within them.

Could I use a List instead? Probably, but then I would not have the distinct grouping of my data based on the range itself. A List of Lists then? Possible, but then I'm considering the Dictionary again. :-)

---

Range examples: I have multiple items where the range is 0 to 100. Other items where range is 0 to 1, 1 to 2, 2 to 3, etc. More items where range is 0 to 4, 4 to 6, 6 to 8, etc. I even have items with ranges from 0 to 0.5, 0.5 to 1, 1 to 1.5, etc. So, first I will group all items based on their ranges, so all items with range 1 to 2 would be together in one list, while all items with range 0 to 100 would be in a different list. I've calculated that I'll be dealing with about 50 different ranges which can overlap each other. However, I have over 25000 items which need to be grouped like this.

Next, I get a value from another source. For example the value 1.12 which I need to find. So this time I use Linq to search through the dictionary to find all lists of items where 1.12 would be in the range of the keys. Thus I'd find the range 1 to 2, 1 to 1.5 and even 0 to 100. Behind these ranges there would be lists of items which I need to process for this value. And then I can move onwards to the next value, for about 4000 different values. And preferably everything should finish with 5 seconds.

Answer 1

Using a key in a dictionary is a matter of overriding GetHashCode and Equals. Basically you'd create a hash based on the minimum and maximum values and Upperbound. Typically you call GetHashCode on each component and combine them, e.g.:

public override int GetHashCode()
{
    int result = 17;
    result = result * 31 + Min.GetHashCode();
    result = result * 31 + Max.GetHashCode();
    result = result * 31 + Upperbound ? 1 : 0;
}

You'd also need the equality test.

I'm not sure what you mean by "to allow me to do a search based upon a range" though. Could you give some sample code showing how you'd like to use this ability? I'm not entirely sure it'll fit within the normal dictionary approach...

I suggest you don't overload the == operator to allow you to do a containment test with it though. A range isn't equal to a value in the range, so code using that wouldn't be very intuitive.

(I'd personally rename Between to Contains as well.)