This web site uses cookies. By using the site you accept the cookie policy.This message is for compliance with the UK ICO law.

Algorithms and Data Structures
.NET 2.0+

A Generic Searchable Range Collection

A common programming task is to match a value to a group of ranges in order to find a value associated with that range. The .NET framework does not provide a collection class to support this functionality so a new generic collection must be created.

Get the Range to Check

During each iteration of the loop, the range item half way between the two search boundaries will be checked. As the search boundaries will change each time, the middle item is calculated by adding the following line within the loop.

int checkRange = searchStart + (searchEnd - searchStart) / 2;

Comparing the Check Range

Once the range to check has been identified, several conditions are checked. Firstly, if the value being searched for is greater than or equal to the check range's key there is a possibility of a match. If this is not the case, there is no match and the end of the search range can be lowered before the loop restarts.

The second condition tests if the value being searched for is the same as the key of the range to check. If so, a match has been found and the related value for the item can be returned. If not, a match is still possible if the range being checked is that last item in the collection or if the next range has a key larger than the search value. If this check gives no match, the lower boundary of the search can be raised before the loop restarts.

To include these conditions, add the following code to the loop:

// Check the lookup value against the check range.
if (lookup.CompareTo(this.Keys[checkRange]) >= 0)
    if (checkRange == searchEnd)
        return this.Values[checkRange];
        // Is the next range above the check value, meaning
        // that the check range is the correct range.
        if (lookup.CompareTo(this.Keys[checkRange + 1]) < 0)
            return this.Values[checkRange];
            searchStart = checkRange + 1;
    // Range to find is lower than the check range
    // so move the end of the search.
    searchEnd = checkRange - 1;

Checking for Unexpected Errors

The use of ranges with no maximum value and the initial testing for a value lower than the smallest range means that there should be no situation where the loop exits because the search boundaries overlap. However, in case this does happen for an unexpected reason, the following line can be added after the end brace (}) of the loop to throw an exception.

throw new InvalidOperationException("Search unexpectedly exhausted.");

Testing the RangeCollection

The RangeCollection class can now be tested. For an example test, change the Main method in the Program class as follows and execute the program:

static void Main(string[] args)
    RangeCollection<int, string> ranges = new RangeCollection<int, string>();

    ranges.Add(0, "Harmless");
    ranges.Add(4, "Mostly Harmless");
    ranges.Add(8, "Poor");
    ranges.Add(16, "Below Average");
    ranges.Add(32, "Average");
    ranges.Add(64, "Above Average");
    ranges.Add(128, "Competent");
    ranges.Add(1000, "Dangerous");
    ranges.Add(3000, "Deadly");
    ranges.Add(6000, "Elite");

    for (int i = -1; i < 10000; i = (i + 1) * 2)
        string rating = ranges.FindValueInRange(i, "Unknown");
        Console.WriteLine("{0} kills = {1}", i, rating);


-1 kills = Unknown
0 kills = Harmless
2 kills = Harmless
6 kills = Mostly Harmless
14 kills = Poor
30 kills = Below Average
62 kills = Average
126 kills = Above Average
254 kills = Competent
510 kills = Competent
1022 kills = Dangerous
2046 kills = Dangerous
4094 kills = Deadly
8190 kills = Elite

8 March 2008