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];
}
else
{
// 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];
else
searchStart = checkRange + 1;
}
}
else
{
// 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);
}
}
/* OUTPUT
-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