What is the fastest way to get all the keys between 2 keys in a SortedList?

Question

Given a populated SortedList<DateTime, double>. I would like to get all the keys (or their index range, what should be a closed int interval (missed I something?)) for a given low and high DateTime interval.

Note: The low and high values are not necessary are actually in the SortedList.

---

If anyone has better idea how to do this without a SortedList, here is a bit wider scope what I would like to do, and I found SortedList may be suitable:

• I would like to cache doubles with a DateTime key.
• Access performance to the double having the given key is preferable over the performance of adding keys an removing keys
• Here is the thing: I must "invalidate" the cache for a given key range (delete the keys) Again there is no guarantee that the range min and max is exactly found in the cache.

Answer 1

I wondered why SortedList<TKey, TValue> doesn't provide a BinarySearch when it's already sorted by the keys. It also uses the method itself(f.e. in IndexOf), but the array used is a private field. So i've tried to create an extension method for this. Have a look:

public static class SortedListExtensions
{
    public static int BinarySearch<TKey, TValue>(this SortedList<TKey, TValue> sortedList, TKey keyToFind, IComparer<TKey> comparer = null)
    {
        TKey[] keyArray = sortedList.GetKeyArray();
        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;
        }

        IList<TKey> keys = sortedList.Keys;
        for (int i = lowIndex; i < highIndex; i++)
        {
            yield return keys[i];
        }
    }
    
    private static TKey[] GetKeyArray<TKey, TValue>(this SortedList<TKey, TValue> sortedList)
    {
        // trying to resolve array with reflection because SortedList.keys is a private array
        Type type = typeof(SortedList<TKey, TValue>);
        FieldInfo keyField = type.GetField("keys", BindingFlags.NonPublic | BindingFlags.Instance);
        if(keyField != null && keyField.GetValue(sortedList) is TKey[] keyArrayFromReflection)
        {
            return keyArrayFromReflection;      
        }
        
        // fallback: fill a new array from the public Keys property, you might want to log this since you should change the reflection implementation
        IList<TKey> keyList = sortedList.Keys;
        TKey[] keyArray = new TKey[keyList.Count];
        for (int i = 0; i < keyArray.Length; i++)
            keyArray[i] = keyList[i];
        return keyArray;
    }
}

Create a sample 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);

Now you can use the extension method to get the range of keys between a low- and high-key:

IEnumerable<DateTime> dateRange = sortedList.GetKeyRangeBetween(low, high).ToList();

Result:

04/04/2014
04/06/2014
04/08/2014
04/10/2014

Note that this is built from scratch and not really tested.

Answer 2

As the list is sorted you can use binary search to locate the endpoints of your interval. Worst case performance will be O(log n).