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) { }FindValueInRange Method
To complete the RangeCollection class the search functionality needs to be added. This will be provided by a new method named "FindValueInRange" that performs a binary search of the dictionary keys and returns the corresponding value. As it will be possible to pass a value that does not appear within any range, a default value will be supplied as a second parameter to the method. Where the search value is not found the default value will be returned instead.
The search value must be of the same generic type as the keys in the collection and the default value must match the type of the related values. Therefore, the declaration for the new method to be added to the class is as follows:
public value FindValueInRange(key lookup, value defaultValue)
{
}Initial Checks
The first task in the search method is to test for unusual conditions. An if statement checks that the RangeCollection has been populated with at least one range. A second condition ensures that the value to search for is greater than or equal to the lowest range key. If either condition is not met, the default value will be returned immediately.
To add the conditions, add the following code to the FindValueInRange method:
if (this.Count == 0) return defaultValue;
if (lookup.CompareTo(this.Keys[0]) < 0) return defaultValue;
NB: The lowest range will be the item at index zero as the collection is sorted into ascending order by the underlying SortedList class.
Preparing the Binary Search
The search will be performed within a while loop that continues until a matching range is found. The matching range will be the range that starts at a value equal to or less than the search value and is either the last range in the collection or is directly before another range that has a key higher than the search value.
To maximise the performance of the process for large collections, a binary search algorithm will be used. Initially the boundaries of the search will be the first and last items. Each time a check is made, at least half of the range will be discarded before the loop is restarted.
To initialise the search range and declare the loop, add the following to the method:
int searchStart = 0;
int searchEnd = this.Count - 1;
while (searchStart <= searchEnd)
{
}8 March 2008