Click here to Skip to main content
Click here to Skip to main content

Perform Binary Searching on Range of Generic Types

, , 23 Sep 2008
Rate this:
Please Sign up or sign in to vote.
Perform Binary Searching on Range of Generic Types
Range_Dictionary

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><t /> : IComparable<Range<T><range<t />> where T : IComparable<T><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<t /> 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><int, />, Person> rangeList = 
	new SortedRangeList<int,Range<int><int, />, Person>();

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

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

        Range<int /> range3 = new Range<int />(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

  • 23rd September, 2008: Initial post

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

About the Authors

Paul Brower
Choice Genetics US
United States United States
Seasoned IT Professional. Currently the IT Director for Choice Genetics, and also the world-wide manager for IT Projects related to R&D for Groupe Grimaud (our parent company).
 
I've spent about half my career as a contractor. I've lived all over the place, but currently reside near St. Louis, Missouri. Moved out here from Roseville, California in Feb-2005. No regrets yet.
 
Over the recent years I've written software for:
- Disposing of radioactive and toxic waste.
- Disposing of surplus inventory during the Decommission of McClellan Air Force Base.
- Facilitating genetic improvement for Swine Breeding.
- Managing children placed in State custody.
- Dealing with commercial trucking delivery schedules.
- Tracking high resolution images from archeological digs.
- Project Management for the roofing industry.
- Processing engines for credit card transactions.
Follow on   LinkedIn

dmprantz

United States United States
No Biography provided

Comments and Discussions

 
GeneralSimilar articles [modified] PinmemberPIEBALDconsult23-Sep-08 5:17 
GeneralRe: Similar articles PinmemberPaul Brower23-Sep-08 5:24 
GeneralRe: Similar articles PinmemberPIEBALDconsult23-Sep-08 7:28 
GeneralRe: Similar articles PinmemberPaul Brower23-Sep-08 7:41 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web01 | 2.8.140721.1 | Last Updated 23 Sep 2008
Article Copyright 2008 by Paul Brower, dmprantz
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid