建议适用于键范围查找的数据结构

Question

我正在寻找类似于SCG.Dictionary的数据结构,但将数字范围作为键.

需要大部分性能的主要操作是查找与指定范围重叠的键.

例如,假设以下地图

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

当[10,30]传递给搜索算法时,它必须回复以下条目:

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

理想情况下,搜索方法应该返回IEnumerable而不是将结果复制到中间容器中.与SortedSet.GetViewBetween类似

使用模式将是符合的

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 );

有没有现成的解决方案？

Answer 1

这是一个可能的实现:

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;
    }
}

您可以在此链接上看到实际示例.