Я задавался вопросом, почему SortedList<TKey, TValue>
не предоставляет BinarySearch
, когда он уже отсортирован ключами. Он также использует сам метод (f.e. In IndexOf
), но используемый массив является частным полем.
Итак, я попытался создать для этого метод расширения, посмотрите:
public static class SortedListExtensions
{
public static int BinarySearch<TKey, TValue>(this SortedList<TKey, TValue> sortedList, TKey keyToFind, IComparer<TKey> comparer = null)
{
// need to create an array because SortedList.keys is a private array
var keys = sortedList.Keys;
TKey[] keyArray = new TKey[keys.Count];
for (int i = 0; i < keyArray.Length; i++)
keyArray[i] = keys[i];
if(comparer == null) comparer = Comparer<TKey>.Default;
int index = Array.BinarySearch<TKey>(keyArray, keyToFind, comparer);
return index;
}
public static IEnumerable<TKey> GetKeyRangeBetween<TKey, TValue>(this SortedList<TKey, TValue> sortedList, TKey low, TKey high, IComparer<TKey> comparer = null)
{
int lowIndex = sortedList.BinarySearch(low, comparer);
if (lowIndex < 0)
{
// list doesn't contain the key, find nearest behind
// If not found, BinarySearch returns the complement of the index
lowIndex = ~lowIndex;
}
int highIndex = sortedList.BinarySearch(high, comparer);
if (highIndex < 0)
{
// list doesn't contain the key, find nearest before
// If not found, BinarySearch returns the complement of the index
highIndex = ~highIndex - 1;
}
var keys = sortedList.Keys;
for (int i = lowIndex; i < highIndex; i++)
{
yield return keys[i];
}
}
}
Создайте образец SortedList
:
DateTime start = DateTime.Today.AddDays(-50);
var sortedList = new SortedList<DateTime, string>();
for(int i = 0; i < 50; i+=2)
{
var dt = start.AddDays(i);
sortedList.Add(dt, string.Format("Date #{0}: {1}", i, dt.ToShortDateString()));
}
DateTime low = start.AddDays(1); // is not in the SortedList which contains only every second day
DateTime high = start.AddDays(10);
Теперь вы можете использовать метод расширения выше, чтобы получить диапазон ключей между низким и высоким ключом:
IEnumerable<DateTime> dateRange = sortedList.GetKeyRangeBetween(low, high).ToList();
Результат:
04/04/2014
04/06/2014
04/08/2014
04/10/2014
Обратите внимание, что это построенный с нуля и не протестированный, но он может дать вам идею.