Suggest Datenstruktur geeignet für Key Range Lookup

Question

Ich bin auf der Suche nach Datenstruktur ähnlich wie SCG.Dictionary aber mit Nummernbereichen als Schlüssel.

Hauptoperation, bei der die meiste Leistung erforderlich ist, wäre die Suche nach Schlüsseln, die sich mit dem angegebenen Bereich überschneiden.

Zum Beispiel unter der Annahme, die folgende Karte

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

, wenn [10, 30] übergeben wird Algorithmus zur Suche mit den folgenden Einträgen antworten müssen:

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

Idealersuchmethode sollte IEnumerable anstatt Ergebnisse in Zwischenbehälter zu kopieren. Ähnlich SortedSet.GetViewBetween

Nutzungsmuster wäre etwas entlang der Linien von

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

Gibt es fertige Lösungen?

Answer 1

Hier ist eine mögliche Implementierung:

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

Sie können ein anschauliches Beispiel auf this link sehen.