SortedDictionary should have GetViewBetween method

[acerbusace]

Even though SortedDictionary currently stores KeyValuePair's inside a SortedSet, it does not provide access to GetViewBetween.

Rational and Usage

SortedDictionary doesn't have a efficient way to enumerate through batches of elements. Currently you would either have to enumerate through the entire collection and then filter out the key range needed or convert the KeyCollection into a SortedSet and then use GetViewBetween. Both the described ways are performance intensive, the first way iterates through unnecessary keys and in the latter method, the conversion to SortedSet is extremely costly.

foreach (var key in sDict.Keys) 
{
    if (key >= lowerbound && key <= upperbound) 
    {
        // do something...    
    }
}

Or

SortedSet<int> sKeys = new SortedSet<int>(sDict.Keys);
SortedSet<int> sView = sKeys.GetViewBetween(lowerbound, upperbound);
foreach (var key in sView) 
{
    // do something...
}

With the proposed changes, we can leverage SortedSet's already implemented method GetViewBetween to efficiently enumerate through a range of keys:

SortedSet<KeyValuePair<int, int>> sView = sDict.GetViewBetween(lowerbound, upperbound);
foreach (var pair in sView) 
{
    // do something...
}

If you have a large dictionary and only need to iterate through a certain range of keys, this allows you to do that efficiently.

Proposed API

public class SortedDictionary<TKey, TValue> : IDictionary<TKey, TValue>, IDictionary, IReadOnlyDictionary<TKey, TValue>
{
    ...
    public SortedSet<KeyValuePair<Tkey, TValue>> GetViewBetween(TKey lowerValue, TKey upperValue); 
    ...
}

Details and Open Questions

• A possible concern is that the SortedSet returned by GetViewBetween is mutable, so any changes may be in conflict with the global dictionary. For example if there is a SortedDictionary that contains:

{
    1:"1",
    2:"2",
    3:"3"
}

Now we try to add 1:"11" to the SortedSet returned by GetViewBetween, how do we go about blocking these type of operations?

• We could try converting the mutable SortedSet into a immutable one before being returned, however this would be an expensive operation
• Additionally, we can add a wrapper to the returned SortedSet which restricts the allowed operations

[safern]

I think this would be very simple to implement as we could just call the underlying set in Dictionary to get the view between the requested bounds. It also makes sense to have it to make it in a more efficient way.

Marking this as API ready to review and as 3.0 so that it gets attention, from the open questions I think it is fair to be concerned about blocking those type of operations due to the SortedSet being mutable, we can discuss it in the API review meeting.

[terrajobst]

Adding GetViewBetween() to SortedDictionary<K,V> makes sense. However, the proposed shape seems problematic:

1. Returning SortedSet<KeyValuePair<TKey, TValue>> seems odd. Why not SortedDictionary<TKey, TValue>?
2. A more natural return type would be IEnumerable<KeyValuePair<TKey, TValue>> if the primary goal is enumeration. Is it important to have random access for the view? If so, what scenarios is this used for?

There is also some behavior questions, which we should answer by how SortedSet<T> works today. Is the behavior sound?

• What happens if someone adds an item to the view? SortedSet<T> allows this and adds to the parent. Subsequent enumeration will return it.
• What happens if someone adds an entry that is outside the bounds of the view? SortedSet<T> throws.
• What happnens to the view if someone removes from the original collection? SortedSet<T> reflects that in both view as well as parent.

To answer (1) and (2) we'd need more scenarios.

[danmoseley]

Moving to Future .Not a must have for 3.0

[acerbusace]

Haven't had any time to work on this and I don't need this implementation anymore. Thanks.