.NET 2.0+

A Generic Searchable Range Collection (2)

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.

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".

Class Definition

The RangeCollection will hold two values for each item in the collection. The key value will hold the start point for a range and the value element will contain the related value. The data type of each item will be variable according to a specific instance's use. This means that the class will be very similar to the generic SortedList collection. In fact, the only difference between RangeCollection and SortedList is the additional binary search method. For this reason, the RangeCollection class will inherit its base functionality from SortedList.

The generic SortedList class is in the System.Collections.Generic namespace. To keep the code neat, ensure that the following using directive appears at the top of the RangeCollection class file.

using System.Collections.Generic;

With the using directive in place, the class can be declared. A declaration will automatically have been added to the code but this must be modified to indicate that the new class is a subclass of SortedList. Change the declaration as follows:

public class RangeCollection<key, value> : SortedList<key, value> where key : IComparable
{
}

There are several items of note in the updated declaration. The class is derived from the generic SortedList class. The "key" and "value" items specify the names of the two generic types that will be used for the key and value elements in each collection entry. As we will be performing comparison operations on the key's data type, the key must implement the IComparable interface. This rule is enforced by the where element.

Constructors

The generic SortedList class provides six constructors. These constructors allow the initial capacity to be set, permit selection of the IComparer that will be used to sort the list and initialise the collection using the contents of another dictionary.

The RangeCollection currently includes only the default constructor, as constructors are not automatically inherited from the parent class. Three constructors will be defined for the new class. These will be the default constructor, a constructor that permits the capacity to be set and a constructor that provides an initialising dictionary. To declare the three constructors and have each simply call the matching underlying SortedList function, add the following code to the class:

public RangeCollection() : base() { }
public RangeCollection(int capacity) : base(capacity) { }
public RangeCollection(IDictionary<key, value> dictionary) : base(dictionary) { }