How do I get previous key from SortedDictionary?

Question

I have dictionary containing key value pairs.

SortedDictionary<int,int> dictionary=new SortedDictionary<int,int>();
dictionary.Add(1,33);
dictionary.Add(2,20);
dictionary.Add(4,35);

I want to get previous key value pair from a known key value. In the above case, if I have key 4, then how can I get <2,20>?

Answer 1

It's hard to implement this efficiently with a SortedDictionary<TKey, TValue> since it is implemented as a binary search tree that does not expose predecessors or successors.

You could of course just enumerate each KeyValuePair until you find the "known" key. With a little bit of LINQ, this would look like (assuming the key definitely exists and isn't the first key):

SortedDictionary<int, int> dictionary = ...
int knownKey = ...

var previousKvp = dictionary.TakeWhile(kvp => kvp.Key != knownKey)
                            .Last();

If those assumptions don't hold, you could do:

var maybePreviousKvp = dictionary.TakeWhile(kvp => kvp.Key != knownKey)
                                 .Cast<KeyValuePair<int, int>?>()
                                 .LastOrDefault();

(Check that maybePreviousKvp != null to ascertain that the previous KeyValuePair was retrieved successfully.)

But this isn't going to be efficient at all.

---

If feasible, consider using a SortedList<TKey, TValue> instead (obviously, this may not be possible if you can't take its slower inserts and deletes). This collection supports efficient key and value-retrieval by ordered index since it is implemented as a growable array. Then your query becomes as simple as:

SortedList<int, int> dictionary = ...
int knownKey = ...

int indexOfPrevious = dictionary.IndexOfKey(knownKey) - 1;

// if "known" key exists and isn't the first key
if(indexOfPrevious >= 0)
{
   // Wrap these in a KeyValuePair if necessary
   int previousKey = dictionary.Keys[indexOfPrevious];
   int previousValue = dictionary.Values[indexOfPrevious];      
}

IndexOfKey runs a binary search on the keys-list, running in O(log n) time. Everything else should run in constant time, meaning the entire operation should run in logarithmic time.

---

Otherwise, you'll have to implement yourself / find a BST collection that does expose predecessors / successors.

Answer 2

I was also looking for an answer to this problem, and I thought a better solution than all of the answers here is to use the TreeDictionary<K, V> from the C5 Collections (GitHub/NuGet), which is an implementation of a red-black tree.

It has Predecessor/TryPredecessor and WeakPredessor/TryWeakPredecessor methods (as well as equivalent methods for successors) which does exactly what you want.

For example:

TreeDictionary<int,int> dictionary = new TreeDictionary<int,int>();
dictionary.Add(1,33);
dictionary.Add(2,20);
dictionary.Add(4,35);

// applied to the dictionary itself, returns KeyValuePair<int,int>
var previousValue = dictionary.Predecessor(4);
Assert.Equals(previousValue.Key, 2);
Assert.Equals(previousValue.Value, 20);

// applied to the keys of the dictionary, returns key only
var previousKey = dictionary.Keys.Predecessor(4);
Assert.Equals(previousKey, 2);

// it is also possible to specify keys not in the dictionary
previousKey = dictionary.Keys.Predecessor(3);
Assert.Equals(previousKey, 2);