Swapping values in a sorted object map

Question

Lets say I have an sorted dictionary whose keys are objected

public class ExecutionMap 
{
    protected SortedDictionary<object, object> ExecutionMap { get; set; }
}

Lets say I lets say I have an object in that map and I want to swap its position with the the next :

public void SwapUp(object key) 
{
    
    value = ExecutionMap.Get(key);
    //How do I do I swap with the one that comes before it 
}

Whats an efficient way to swap this with the one before it? I would prefer not to have to enumerate the dictionary to find the key before it

Answer 1

Instead of a SortedDictionary<K,V> you could use a C5.TreeDictionary<K,V> from the third-party C5 library. This type offers rich functionality regarding finding previous and next entries, finding ranges of entries, supports backward enumeration etc. All these operations are implemented efficiently on top of a red-black tree set. Comparatively the functionality offered by the native SortedDictionary<K,V> is rather poor, and it's not sufficient for implementing what you are trying to achieve.

public class ExecutionMap
{
    protected C5.TreeDictionary<object, object> ExecutionMap { get; set; }

    public void SwapUp(object key)
    {
        // Find the entry with this key
        if (ExecutionMap.Find(ref key, out var value))
        {
            // Find the entry that comes before it
            if (ExecutionMap.TryPredecessor(key, out var predecessor))
            {
                // Create a key that is smaller than the key of the predecessor
                // Creating a suitable key may be tricky
                var newKey = CreateSmallerKey(predecessor.Key);

                // Swap the key of the stored value
                // An exception will be thrown if the newKey already exists
                ExecutionMap.Add(newKey, value);
                bool removed = ExecutionMap.Remove(key);
                Debug.Assert(removed);
            }
        }
    }
}