Menu
I have need of a sort of specialized dictionary. My use case is this: The user wants to specify ranges of values (the range could be a single point as well) and assign a value to a particular range. We then want to perform a lookup using a single value as a key. If this single value occurs within one of the ranges then we will return the value associated to the range.
For example:
// 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(); This is obviously just some code to illustrate what I'm looking for. Does anyone know of an algorithm to implement such a thing? If so could they point me towards it, please?
I have already tried implementing a custom IEqualityComparer object and overloading Equals() and GetHashCode() on Interval but to no avail so far. It may be that I'm doing something wrong though.
288
Yes, you can, only if you convert your range lists as immutable tuple , so they are hashable and accepted as keys of your dictionary: stealth_check = { tuple(range(1, 6)) : 'You are about as stealthy as thunderstorm.
For example, you can use an integer, float, string, or Boolean as a dictionary key. However, neither a list nor another dictionary can serve as a dictionary key, because lists and dictionaries are mutable. Values, on the other hand, can be any type and can be used more than once.
We can use integer, string, tuples as dictionary keys but cannot use list as a key of it .
A dictionary is not the appropriate data structure for the operations you are describing.
If the intervals are required to never overlap then you can just build a sorted list of intervals and binary search it.
If the intervals can overlap then you have a more difficult problem to solve. To solve that problem efficiently you'll want to build an interval tree:
http://en.wikipedia.org/wiki/Interval_tree
This is a well-known data structure. See "Introduction To Algorithms" or any other decent undergraduate text on data structures.
190
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
