建議適用於鍵範圍查找的數據結構

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

你可以看到一個this link活生生的例子。