I have a list of values like this
1000, 20400
22200, 24444
The ranges don't overlap.
What I want to do is have a c# function that can store (loaded values from db then cache it locally) a relatively large list of these values then have a method for finding if a supplied value is in any of the ranges?
Does this make sense?
Need the quickest solution
You've specified values, but then talked about ranges.
For just values, I'd use a HashSet<int>. For ranges it gets more complicated... Let us know if that's actually what you're after and I'll think about it more. If they are ranges, do you have any extra information about them? Do you know if they'll overlap or not? Are you just interested in the existence of a range, or do you need to find all the ranges that a value belongs to?
EDIT: With the edits to the question, Barry's answer is exactly right. Just sort (by lower bound is good enough) at initialization time and then do a binary search to find the range containing the value, or the lack thereof.
EDIT: I've found the code below in my answer to a similar question recently.
The ranges will need to be sorted beforehand - List<Range>.Sort will work fine assuming you have no overlap.
public class Range : IComparable<Range>
{
private readonly int bottom; // Add properties for these if you want
private readonly int top;
public Range(int bottom, int top)
{
this.bottom = bottom;
this.top = top;
}
public int CompareTo(Range other)
{
if (bottom < other.bottom && top < other.top)
{
return -1;
}
if (bottom > other.bottom && top > other.top)
{
return 1;
}
if (bottom == other.bottom && top == other.top)
{
return 0;
}
throw new ArgumentException("Incomparable values (overlapping)");
}
/// <summary>
/// Returns 0 if value is in the specified range;
/// less than 0 if value is above the range;
/// greater than 0 if value is below the range.
/// </summary>
public int CompareTo(int value)
{
if (value < bottom)
{
return 1;
}
if (value > top)
{
return -1;
}
return 0;
}
}
// Just an existence search
public static bool BinarySearch(IList<Range> ranges, int value)
{
int min = 0;
int max = ranges.Count-1;
while (min <= max)
{
int mid = (min + max) / 2;
int comparison = ranges[mid].CompareTo(value);
if (comparison == 0)
{
return true;
}
if (comparison < 0)
{
min = mid+1;
}
else if (comparison > 0)
{
max = mid-1;
}
}
return false;
}
A binary search will do just fine. Keep the list of ranges in sorted order, making sure that none of them intersect (if they do, merge them). Then write a binary search which, rather than testing against a single value, tests against either end of the range when looking to choose above or below.
I'd try the simplest option first, and optimize if that doesn't meet your needs.
class Range {
int Lower { get; set; }
int Upper { get; set; }
}
List<Range>.FirstOrDefault(r => i >= r.Lower && i <= r.Upper);
As previously mentioned, if the set of ranges are big and non-overlapping, it is best to do a binary search. One way to do this is to use SortedDictionary, which implements a red-black tree to give a O(log(n)) search time. We can use the ranges as keys, and do a dictionary lookup by converting the single value we want to match into a range of a single point. If we implement the CompareTo method so that ranges that are overlapping are considered equal/matching, the dictionary lookup will find the matching range for use.
public struct Range : IComparable<Range>
{
public int From;
public int To;
public Range(int point)
{
From = point;
To = point;
}
public Range(int from, int to)
{
From = from;
To = to;
}
public int CompareTo(Range other)
{
// If the ranges are overlapping, they are considered equal/matching
if (From <= other.To && To >= other.From)
{
return 0;
}
// Since the ranges are not overlapping, we can compare either end
return From.CompareTo(other.From);
}
}
public class RangeDictionary
{
private static SortedDictionary<Range, string> _ranges = new SortedDictionary<Range, string>();
public RangeDictionary()
{
_ranges.Add(new Range(1, 1000), "Alice");
_ranges.Add(new Range(1001, 2000), "Bob");
_ranges.Add(new Range(2001, 3000), "Carol");
}
public string Lookup(int key)
{
/* We convert the value we want to lookup into a range,
* so it can be compared with the other ranges */
var keyAsRange = new Range(key);
string value;
if (_ranges.TryGetValue(keyAsRange, out value))
{
return value;
}
return null;
}
}
As an example, running the following code
var ranges = new RangeDictionary();
var value = ranges.Lookup(1356);
value will in this case contain the string "Bob", since 1356 matches the range 1001-2000.
In your case, if you are interested in fetching the range itself, you can use the range as both key and value in the dictionary. The example code can be easily extended to holding generic values instead.
As a sidenote, this trick can also be done using a SortedList with virtually the same code, which uses less memory (array instead of tree) but have slower insertion/deletion time for unsorted data. They both use the default comparator for the key type (or a specified one) to compare values. The normal C# Dictionary on the other hand uses GetHashCode and Equals to compare values.
class Ranges
{
int[] starts = new[] { 1000, 22200 };
int[] ends = new[] { 20400, 24444 };
public int RangeIndex(int test)
{
int index = -1;
if (test >= starts[0] && test <= ends[ends.Length - 1])
{
index = Array.BinarySearch(ends, test);
if (index <= 0)
{
index = ~index;
if (starts[index] > test) index = -1;
}
}
return index;
}
}
Obviously, how you instantiate the class is up to you. Maybe pass in a DataTable and construct the arrays from that.
index <= 0? shouldn't it be index < 0 instead?
Assuming your ranges don't overlap:
-> Put all your range numbers in an array.
-> Sort your array.
-> Also keep a HashSet for your startvalues.
-> Now do a binary search on your number. Two possiblities:
--> Array range left of (smaller then) your number is a start value: your number is in range.
--> Array range left of (smaller then) your number is not a start value: your number is not in range.
Is this functionally what you're after? If so, and you just want it to be more performant, than change the foreach in the ValueRangeCollection to a binary search..
public struct ValueRange
{
public int LowVal;
public int HiVal;
public bool Contains (int CandidateValue)
{ return CandidateValue >= LowVal && CandidateValue <= HiVal; }
public ValueRange(int loVal, int hiVal)
{
LowVal = loVal;
HiVal = hiVal;
}
}
public class ValueRangeCollection: SortedList<int, ValueRange>
{
public bool Contains(int candValue)
{
foreach ( ValueRange valRng in Values)
if (valRng.Contains(candValue)) return true;
return false;
}
public void Add(int loValue, int hiValue)
{
Add(loValue, new ValueRange(loValue, hiValue));
}
}
class Range
{
public int Start { get; set; }
public int End { get; set; }
static Dictionary<int, Range> values;
static int[] arrToBinarySearchIn;
public static void BuildRanges(IEnumerable<Range> ranges) {
values = new Dictionary<int, Range>();
foreach (var item in ranges)
values[item.Start] = item;
arrToBinarySearchIn = values.Keys.ToArray();
Array.Sort(arrToBinarySearchIn);
}
public static Range GetRange(int value)
{
int searchIndex = Array.BinarySearch(arrToBinarySearchIn, value);
if (searchIndex < 0)
searchIndex = ~searchIndex - 1;
if (searchIndex < 0)
return null;
Range proposedRange = values[arrToBinarySearchIn[searchIndex]];
if (proposedRange.End >= value)
return proposedRange;
return null;
}
}