キーレンジルックアップに適したデータ構造を提案する

Question

SCG.Dictionaryに似ているが数字の範囲をキーとして持つデータ構造を探している。

パフォーマンスが最も必要とされる主な操作は、指定された範囲と重複するキーをルックアップすることです。

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

理想的探索方法がIEnumerableを返すべきである：[10、30]は、それが次のエントリで応答しなければならないアルゴリズムを検索するために渡された場合は、次のマップを

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

を想定例えば

、結果を中間コンテナにコピーするのではなく、同様に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上の実際の例を見ることができます。