Suggest data structure suitable for key range lookup

Question

I am looking for data structure similar to SCG.Dictionary but having number ranges as keys.

Main operation where the most of performance is required would be lookup for keys overlapping with the specified range.

For example, assuming the following map

[ 5, 15] -> King
[35, 50] -> Bear
[25, 40] -> Doll

when [10, 30] is passed to search algorithm it must reply with the following entries:

[ 5, 15] -> King
[25, 40] -> Doll

Ideally search method should return IEnumerable rather than copying results into intermediate container. Similarly to SortedSet.GetViewBetween

Usage pattern would be something along the lines of

var lookup = new RangeDictionary<int>();
lookup.Add( 5, 15, 'King' );
lookup.Add( 35, 50, 'Bear' );
lookup.Add( 25, 40, 'Doll' );

var results = lookup.FindIntersection( 10, 30 );
foreach( var pair in results )
  Console.WriteLine( "[{0}, {1}] -> {2}", pair.Key.From, pair.Key.To, pair.Value );

Are there any ready made solutions?

Answer 1

Here is one possible implementation:

public class RangeDictionary<T> : Dictionary<Range, T>
{
    public void Add(int from, int to, T value)
    {
        Add(new Range(from, to), value);
    }

    public IEnumerable<KeyValuePair<Range, T>> FindIntersection(int from, int to)
    {
        return this.Where(x => x.Key.IntersectWith(from, to));
    }
}

public struct Range
{
    public Range(int from, int to)
        : this()
    {
        From = from;
        To = to;
    }
    public int From { get; }
    public int To { get; }

    public bool IntersectWith(int from, int to)
    {
        return this.From <= to && this.To >= from;
    }
}

You can see a live example on this link.