字典对象,使用键值的范围

我需要一种专门的字典。 我的用例是这样的:用户想要指定值的范围(该范围也可以是一个单一的点),并为特定的范围分配一个值。 然后,我们希望使用单个值作为关键字执行查找。 如果这个单一值出现在一个范围内,那么我们将返回与范围相关的值。

例如:

// represents the keyed value struct Interval { public int Min; public int Max; } // some code elsewhere in the program var dictionary = new Dictionary<Interval, double>(); dictionary.Add(new Interval { Min = 0, Max = 10 }, 9.0); var result = dictionary[1]; if (result == 9.0) JumpForJoy(); 

这显然只是一些代码来说明我在找什么。 有谁知道一个algorithm来实现这样的事情? 如果是的话,他们可以指点我吗?

我已经尝试实现一个自定义的IEqualityComparer对象,并在Interval上重载Equals()和GetHashCode(),但迄今为止无济于事。 这可能是我做错了。

字典不是您正在描述的操作的适当数据结构。

如果要求间隔从不重叠,那么你可以build立一个sorting的间隔列表和二进制search它。

如果时间间隔可以重叠,那么你有一个更难解决的问题。 为了有效地解决这个问题,你需要build立一个间隔树:

http://en.wikipedia.org/wiki/Interval_tree

这是一个众所周知的数据结构。 请参阅“algorithm导论”或任何其他体面的本科数据结构文本。

这只在间隔不重叠时才起作用。 而你的主要问题似乎是从一个(关键)值转换为一个区间。

我会写一个SortedList的包装。 SortedList.Keys.IndexOf()会find一个索引,可以用来validation间隔是否有效,然后使用它。

这不完全是你想要的,但我认为这可能是你可以预期的最接近的。

你当然可以做得比这更好(我以前喝酒?)。 但是你必须承认这很好,很简单。

 var map = new Dictionary<Func<double, bool>, double>() { { d => d >= 0.0 && d <= 10.0, 9.0 } }; var key = map.Keys.Single(test => test(1.0)) var value = map[key]; 

我已经解决了类似的问题,确保收集是连续的时间间隔从不重叠,从来没有差距。 每个区间被定义为一个下边界,如果它等于或大于该边界并小于下一个区间的下边界,那么任何值都位于该区间内。 低于最低边界的是一个特例箱。

这有点简化了这个问题。 然后我们通过实现一个二元印章来优化关键search。 不幸的是,我无法分享代码。

我会做一个小的Interval类,这将是这样的:

 public class Interval { public int Start {get; set;} public int End {get; set;} public int Step {get; set;} public double Value {get; set;} public WriteToDictionary(Dictionary<int, double> dict) { for(int i = Start; i < End; i += Step) { dict.Add(i, Value); } } } 

所以你仍然可以在你的字典中正常查找。 也许你还应该在调用Add()之前执行一些检查,或者如果任何值已经在字典中,则实现某种回滚。

您可以在Open Geospatial Library中findJava风格的 C#间隔树实现。 它需要一些小的调整来解决你的问题,它也可以真正使用一些C#化。

这是开源的,但我不知道在什么牌照下。

你可以看看在这里find的集成,可以做你正在寻找的codeplex的powercollections。

希望这有助于,最好的问候,汤姆。