Doing a range lookup in C# - how to implement

Question

I'm trying to understand how to implement the code found in thread by Jon Skeet: Doing a range lookup in C#?

Can someone provide an setup example using something like: 1-10000, 10001-40000, 40000+

where is the first group returns a value of 1, 2, 3 respectively?

I don't quite have a grasp of how that is done in this code. tx.

public interface IRangeComparer<TRange, TValue>
{
    /// <summary>
    /// Returns 0 if value is in the specified range;
    /// less than 0 if value is above the range;
    /// greater than 0 if value is below the range.
    /// </summary>
    int Compare(TRange range, TValue value);
}


/// <summary>
/// See contract for Array.BinarySearch
/// </summary>
public static int BinarySearch<TRange, TValue>(IList<TRange> ranges,
                                               TValue value,
                                               IRangeComparer<TRange, TValue> comparer)
{
    int min = 0;
    int max = ranges.Count-1;

    while (min <= max)
    {
        int mid = (min + max) / 2;
        int comparison = comparer.Compare(ranges[mid], value);
        if (comparison == 0)
        {
            return mid;
        }
        if (comparison < 0)
        {
            min = mid+1;
        }
        else if (comparison > 0)
        {
            max = mid-1;
        }
    }
    return ~min;
}

Answer 1

You need to have a good grasp of generics to understand this code. Here’s a functional implementation:

public class Range<TValue> 
    where TValue : IComparable<TValue>
{
    public TValue Min { get; set; }
    public TValue Max { get; set; }

    public Range(TValue min, TValue max)
    {
        this.Min = min;
        this.Max = max;
    }
}

public class RangeComparer<TValue> : IRangeComparer<Range<TValue>, TValue> 
    where TValue : IComparable<TValue>
{
    /// <summary>
    /// Returns 0 if value is in the specified range;
    /// less than 0 if value is above the range;
    /// greater than 0 if value is below the range.
    /// </summary>
    public int Compare(Range<TValue> range, TValue value)
    {
        // Check if value is below range (less than min).
        if (range.Min.CompareTo(value) > 0)
            return 1;

        // Check if value is above range (greater than max)
        if (range.Max.CompareTo(value) < 0)
            return -1;

        // Value is within range.
        return 0;
    }
}

static void Main(string[] args)
{
    var ranges = new Range<int>[]
    {
        new Range<int>(1, 10000),
        new Range<int>(10001, 40000),
        new Range<int>(40001, int.MaxValue),
    };

    var rangeComparer = new RangeComparer<int>();

    Console.WriteLine(BinarySearch(ranges, 7, rangeComparer));       // gives 0
    Console.WriteLine(BinarySearch(ranges, 10007, rangeComparer));   // gives 1
    Console.WriteLine(BinarySearch(ranges, 40007, rangeComparer));   // gives 2
    Console.WriteLine(BinarySearch(ranges, 1, rangeComparer));       // gives 0
    Console.WriteLine(BinarySearch(ranges, 10000, rangeComparer));   // gives 0
    Console.WriteLine(BinarySearch(ranges, 40000, rangeComparer));   // gives 1
    Console.WriteLine(BinarySearch(ranges, 40001, rangeComparer));   // gives 2
}

Don’t forget that:

• the ranges must be in ascending order
• the ranges must not overlap
• the indexes returned by BinarySearch are zero-based