BlackWaspTM

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.

Tabular Lookup

There are many programming situations where a one value is linked to another and, given the first value, you need to determine the second. In some cases the link is a simple calculation within the code. For example, the relationship between a value and its square can be determined with a simple multiplication.

In more complicated situations, or where the link between two values is arbitrary, a tabular lookup may be used. Here you may decide to store the information in a dictionary collection such as a SortedList or Hashtable. The collection's key element can hold the lookup value and the value element can contain the related item. This is ideal for relationships where calculations would be inefficient or impossible such as those in the table of customer codes below:

Customer Code (Key)Customer Name (Value)
ABC001ABC Technology Limited
ABC002ABC Construction Plc
JOH001John Smith
......

As the table uses discrete values for the customer codes, finding a related name is easy. When stored using a Hashtable, the items can be added as key / value pairs and found using the unique key as an indexer.

Hashtable customers = new Hashtable();

customers.Add("ABC001", "ABC Technology Limited");
customers.Add("ABC002", "ABC Construction Plc");
customers.Add("JOH001", "John Smith");

Console.WriteLine(customers["ABC002"]);     // Outputs "ABC Construction Plc"

The tabular lookup method becomes problematic when the key values are divided into ranges. As an example, the following table shows the available rankings for the 1980's computer game "Elite" and the number of enemies that must be destroyed to achieve each rating.

Kills (Key)Rating (Value)
0 - 3Harmless
4 - 7Mostly Harmless
8 - 15Poor
16 - 31Below Average
32 - 63Average
64 - 127Above Average
128 - 999Competent
1,000 - 2,999Dangerous
3,000 - 5,999Deadly
6,000 +Elite

This information could be held in a simple dictionary but to permit a lookup using the standard indexer, each item would need to be repeated multiple times. As an example, the "Harmless" option would require four entries so that a lookup could be performed for zero, one, two or three battles won. To support all of the possible searches the collection would include 6,001 items and a rule would be added to the code to check for the special case of over six thousands kills.

The problem of duplicating entries becomes even more serious when the lookup values are not integers. If strings or floating-point values are included in the key column of the table, the table size is limited only by the length of string or accuracy of the fractional values. In either case, a simple lookup is unusable except for very small tables.

The resolution to this problem is to have a collection class that represents value ranges. Unfortunately no such class exists in the .NET framework. The remainder of this article will describe the process and the code required for creating one.

RangeCollection Requirements

The RangeCollection class will hold ranges of keys with each range linked to a value. The new dictionary will meet the following requirements:

  • The collection's keys will be of any type that implements IEnumerable. The use of this interface will permit the range keys to be compared with a search value to determine which of two is the larger.
  • The collection's related values will be of any type.
  • Each key in the collection will indicate the lower boundary of a range. The upper boundary will be determined by the next highest key in the collection or, if there is no higher key, the largest value that can be held in the key's data type.
  • The class will include a method that performs a binary search on the ranges to quickly find the range in which a specific value falls, even when there are many thousands, or even millions, of ranges in the collection.

Creating the RangeCollection Project

For simplicity in this article, the RangeCollection class will be created in a console application project. You may wish to create the collection in a class library instead for use within your own projects. To begin, create a new console application named "RangeCollectionDemo". Add a new class file to the project named "RangeCollection".

8 March 2008