Perform Binary Searching on Range of Generic Types

• Download source - 78.44 KB

Introduction

This article will demonstrate how to perform binary searching on a range of values.

Background

My cohort (dmprantz) and I work for a startup company (shameless plug http://www.clearent.com) that is building a state-of-the-art Credit Card Processing Engine, for performing back-end processing for the various Credit Card Associations. We have repeatedly come across the need to be able to have large collections of ranges in memory, and to be able to search those collections extremely fast. The best we could tell, this functionality is not built into the .NET Framework.

To better illustrate our need, consider the following:

Assumed you had thousands of ranges of numeric data.

• 10 - 50
• 55 - 75
• 79 - 150

etc. etc., X THOUSANDS

Now, I have a simple value, let's say 68, and I need to know if that value is contained within one of my ranges. If it is contained there, I need to return a custom class associated with that range.

This may sound simple enough, but we need to be able to check thousands of these per second. We decided we needed the ability to perform a binary search on a generic range.

Before I proceed, I want to point out that we have a process in place to ensure that we will never add overlapping ranges. For example, we would not have one range of 1-100, and another range of 80-150. There is definitely some refactoring that could be done on our SortedRangeList to support this.

The Range<T> Class

We started by creating a class called Range. This class is fairly simple. It contains a LowerBound, and UpperBound, and a RangeComparisonStrategy Enum that is used to tell the class how to sort its' object.

This class requires that T is IComparable.

public enum RangeComparisonStrategy
{
    UpperBound,
    LowerBound
}

public class Range<T> : IComparable<Range<T>> where T : IComparable<T>
{
    private readonly RangeComparisonStrategy strategy;
    private readonly T upperBound;
    private readonly T lowerBound;

    public Range(RangeComparisonStrategy strategy, T lowerBound, T upperBound)
    {
        this.strategy = strategy;
        this.lowerBound = lowerBound;
        this.upperBound = upperBound;
    }

    public RangeComparisonStrategy RangeComparisonStrategy
    {
        get { return strategy; }
    }

    public T LowerBound
    {
        get { return lowerBound; }
    }

    public T UpperBound
    {
        get { return upperBound; }
    }

    public int Contains(T value)
    {
        int ret = 0;
            
        if (lowerBound.CompareTo(value) > 0)
        {
            ret = -1;
        }
        else if (upperBound.CompareTo(value) < 0)
        {
            ret = 1;
        }
        return ret;
    }

    public int CompareTo(Range other)
    {
        int ret;

        if (strategy == RangeComparisonStrategy.LowerBound)
        {
            ret = lowerBound.CompareTo(other.LowerBound);
        }
        else
        {
            ret = upperBound.CompareTo(other.UpperBound);
        }

        return ret;
    }
}

For this article, I'm using Ints and Strings, but it is important to remember that T can be anything that implements IComparable.

The SortedRangeList<T, TKey, TValue> Class

Now that we have the ability to have a range of something, we need to be able to put a list of those ranges in some kind of container, be able to query those ranges with a single value, and return an object associated with a range.

To illustrate this need, let's go back to the ranges we had above:

• 10 - 50
• 55 - 75
• 79 - 150

In this case, we would have 3 Range<T> classes that would be defined as follows:

Range<int> range1 = 
new Range<int>(RangeComparisonStrategy.LowerBound, 10, 50);

Range<int> range2 = 
new Range<int>(RangeComparisonStrategy.LowerBound, 55, 75);

Range<int> range3 = 
new Range<int>(RangeComparisonStrategy.LowerBound, 79, 150);

Using the ContainsT method of the Range class, we would be able to determine if any value (T) is contained within a range. Range1 would contain anything between 10 and 50, Range2 would contain anything between 55 and 75, and so forth.

Remember, the Range<T>; class is going to be our Key in a class that inherits from SortedList. The Value can be anything you want it to be: a simple value type, a custom class, etc. For the purpose of this article, our value will simply be an object.

public class SortedRangeList<T, TKey, TValue> : 
    SortedList<TKey, TValue> where TKey : Range<T> where T: IComparable<T> 
{
    public TValue GetT(T t)
    {
        int index = IndexOfT(t, 0, Count - 1);

        if (index < 0)
        {
            throw new ArgumentNullException();
        }
            
        return Values[index];
    }

    public bool ContainsT(T t)
    {
        return IndexOfT(t, 0, Count - 1) >= 0;
    }

    public int IndexOfT(T t)
    {
        return IndexOfT(t, 0, Count - 1);
    }

    protected int IndexOfT(T t, int startIndex, int endIndex)
    {
        int BinaryIndex = startIndex + ((endIndex - startIndex) / 2);
        int ret = -1;

        if (Count > 0)
        {
            switch (Keys[BinaryIndex].Contains(t))
            {
                case -1:
                    if (startIndex != BinaryIndex)
                    {
                        ret = IndexOfT(t, startIndex, BinaryIndex - 1);
                    }

                    break;
                case 0:
                    ret = BinaryIndex;

                    break;
                case 1:
                    if (BinaryIndex != endIndex)
                    {
                        ret = IndexOfT(t, BinaryIndex + 1, endIndex);
                    }
                    break;
            }
        }

        return ret;
    }
}

Having this SortedRangeList class gives us the ability to use a Range<T> as the key, query the list and identify the Key by passing in a value within the range of the key, and return the corresponding Value from the list.

Using the Code

Here is some code to provide an example of how this class might be used:

private class Person 
{
    public string FirstName;    
    public string LastName;

    public Person(string firstName, string lastName)
    {
        FirstName = firstName;
        LastName = lastName;
    }
}

    [Test]
    public void testForCodeProject()
    {
        SortedRangeList<int,Range<int>, Person> rangeList = 
	new SortedRangeList<int,Range<int>, Person>();

        Range range1 = new Range(RangeComparisonStrategy.LowerBound,5,20);
        Person person1 = new Person("Paul", "Brower");

        Range range2 = new Range(RangeComparisonStrategy.LowerBound,30,50);
        Person person2 = new Person("John", "Doe");

        Range range3 = new Range(RangeComparisonStrategy.LowerBound,55,100);
        Person person3 = new Person("Sarah", "Jones");

        rangeList.Add(range1,person1);
        rangeList.Add(range2,person2);
        rangeList.Add(range3,person3);

        Assert.AreEqual("Paul", rangeList.GetT(7).FirstName);
        Assert.AreEqual("Brower", rangeList.GetT(20).LastName);
    } 

I have included a sample project, that contains the Range<T> and SortedRangeList<T, TKey, TValue> classes.  As you can see from the screenshot above, the class is very fast when working with ranges as a key to a List.

If someone else doesn't do it first, Daniel or myself will probably soon add the ability to have overlapping ranges.

Let us know what you think!

- Paul Brower & Daniel Pomerantz 

History

• 23^rd September, 2008: Initial post