11

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?

Mooh
  • 744
  • 5
  • 25
  • Is your example correct? Whats the result for `[10,35]`? should it be `King, Bear` or `King, Doll` or `King, Bear, Doll`? – Jehof Jan 02 '17 at 09:14
  • 2
    Seems easy enough to write your own, any reason why you are searching for a ready made solution for this? – Zohar Peled Jan 02 '17 at 09:53
  • 1
    I think that you are looking for an interval tree, see http://stackoverflow.com/questions/303591/a-range-intersection-algorithm-better-than-on – PartlyCloudy Jan 02 '17 at 12:52

1 Answers1

5

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.

Zohar Peled
  • 79,642
  • 10
  • 69
  • 121
  • 1
    Suggested structure implies full scan while I am after something faster than O(n) – Mooh Jan 03 '17 at 20:29
  • Not only it's O(n), deriving from base collection classes is a really bad practice – George Polevoy Sep 19 '17 at 16:27
  • @George I don't see any other suggestions... Why do you think it's so bad to derive from a collection, given that the .net framework already contains a class derived from a dictionary... – Zohar Peled Sep 19 '17 at 19:01
  • @ZohadPeled because there is nothing you can't do with an extension method in your implementation. https://stackoverflow.com/questions/3748931/inheriting-listt-to-implement-collections-a-bad-idea there are few other good arguments for you to consider in the answers. – George Polevoy Sep 20 '17 at 13:14
  • I don't even need a method, It's only wrapping a linq... But it provides better readability, as does all the class... – Zohar Peled Sep 20 '17 at 14:37