Looking up values based on range data

Question

What data structure or datatype would be good for holding data ranges, and return a value based on data that lies in that range?

For example suppose I have the following ranges

1-10 -> 1  
11-35 -> 2.5  
36-49-> 3.8  
50-60 -> 1.2  
61-80 -> 0.9 

In this case given the number 41 I would want the number 3.8 returned (as 41 is between the ranges of 36 and 49).

Is there a clever way of representing such data in a datastructure in order to perform this lookup?

Answer 1

A comparatively convenient and very performant implementation would be to use a SortedList<int, Tuple<int, double>>. Use the lower bound for each segment as the key and a tuple of upper bound + mapped value for the value:

var list = new SortedList<int, Tuple<int, double>>
{
    { 1, Tuple.Create(10, 1.0) },
    { 11, Tuple.Create(35, 2.5) },
};

(Of course you could decide to use a better-looking data structure to declare your parameters in order to enhance code maintainability and internally convert to this before getting down to business).

Since list.Keys is guaranteed to be sorted, when looking up a value you can use binary search on it to find the index that is equal to or greater than your input value:

var index = list.Keys.BinarySearch(value);
if (index < 0 && ~index == 0) {
    // no match, stop processing
}
else if (index < 0) {
    // key not found as is, look at the previous interval
    index = ~index - 1;
}

At this point index points at the only range that might include value, so all that remains is to test for that:

if(x >= list.Keys[index] && x <= list.Values[index].Item1) {
    var result = list.Values[index].Item2;
}
else {
    // no match
}

You wouldn't call this "clean", but it's very short and very fast.

Answer 2

You can use this code

Key :

public class Interval<T> where T : IComparable
{
    public Nullable<T> Start { get; set; }
    public Nullable<T> End { get; set; }

    public Interval(T start, T end)
    {
        Start = start;
        End = end;
    }

    public bool InRange(T value)
    {
        return ((!Start.HasValue || value.CompareTo(Start.Value) > 0) &&
                (!End.HasValue || End.Value.CompareTo(value) > 0));
    }
}

value : decimal

And you can use this Type : Dictionary<Interval, decimal>

Nota : you can define access methods

Answer 3

It took me a while but I have a QuickAndDirty method which assumes all given values are valid and ranges are adjacent, without using any data structures. And a very specific data structure which will only return something if the given index is exactly in the specified range and which can be expanded at run-time.

public abstract class TreeNode
{
    public static double QuickAndDirty(int index)
    {
        double result = 1.0;

        if (index > 10)
            result = 2.5;

        if (index > 35)
            result = 3.8;

        if (index > 49)
            result = 1.2;

        if (index > 60)
            result = 0.9;

        return result;
    }

    public abstract double GetValue(int index);

    public abstract TreeNode AddRange(int begin, int end, double value);

    public static TreeNode MakeTreePart(Tuple<int, int, double>[] ranges)
    {
        return TreeNode.MakeTreePart(ranges, 0, ranges.Length >> 1, ranges.Length - 1);
    }

    private static TreeNode MakeTreePart(Tuple<int, int, double>[] ranges, int min, int index, int max)
    {
        if (index == min || index == max)
            return new Leaf(ranges[index].Item1, ranges[index].Item2, ranges[index].Item3);

        return new SegmentTree(
            ranges[index].Item2 + .5,
            TreeNode.MakeTreePart(ranges, min, index >> 1, index - 1),
            TreeNode.MakeTreePart(ranges, index + 1, index << 1, max));
    }
}

public class SegmentTree : TreeNode
{
    private double pivot;
    private TreeNode left, right;

    public SegmentTree(double pivot, TreeNode left, TreeNode right)
    {
        this.pivot = pivot;
        this.left = left;
        this.right = right;
    }

    public override double GetValue(int index)
    {
        if (index < pivot)
            return left.GetValue(index);
        return right.GetValue(index);
    }

    public override TreeNode AddRange(int begin, int end, double value)
    {
        if (end < pivot)
            this.left = this.left.AddRange(begin, end, value);
        else
            this.right = this.right.AddRange(begin, end, value);
        // Do this to confirm to the interface.
        return this;
    }
}

public class Leaf : TreeNode
{
    private int begin, end;
    private double value;

    public Leaf(int begin, int end, double value)
    {
        this.begin = begin;
        this.end = end;
        this.value = value;
    }

    public override double GetValue(int index)
    {
        if (index >= begin && index <= end)
            return value;
        throw new Exception("index out of range");
    }

    public override TreeNode AddRange(int begin, int end, double value)
    {
        if (this.end < begin)
            return new SegmentTree(((double)this.end + begin) * .5, this, new Leaf(begin, end, value));
        else if (end < this.begin)
            return new SegmentTree(((double)end + this.begin) * .5, new Leaf(begin, end, value), this);
        else throw new Exception("Indexes overlap.");
    }
}
    static void Main()
    {
        TreeNode start = new Leaf(36, 49, 3.8);
        start = start.AddRange(11, 35, 2.5);
        start = start.AddRange(1, 10, 1.0);
        start = start.AddRange(50, 60, 1.2);
        start = start.AddRange(61, 80, 0.9);
        double[] values = new double[70];
        for (int i = 1; i < values.Length; i++)
            values[i] = start.GetValue(i);

        TreeNode array = TreeNode.MakeTreePart(
            new Tuple<int, int, double>[]
            {
                Tuple.Create(1, 10, 1.0),
                Tuple.Create(11, 35, 2.5),
                Tuple.Create(36, 49, 3.8),
                Tuple.Create(50, 60, 1.2),
                Tuple.Create(61, 80, 0.9)
            });

        for (int i = 1; i < values.Length; i++)
            values[i] = start.GetValue(i);
    }