Finding 'Next Available' Key in a dictionary or related collection

Question

I want to write an linq extension (or a custom dictionary, sorted list list or whatever solution is best) that will allow me to add a value to a collection with its key being the 'next available' one.

For example:

int CreatedKey = IncrementDictionary.AddNext(myCustomer);

If the currently existing keys are as follows:

1
2
8
4
3

Then it would add the myCustomer into the dictionary with a key of 5 and it would return that key.

What do you think?

Answer 1

public static int AddNext(this Dictionary<int, string> dict)
{
    int min = dict.Keys.Min();
    int max = dict.Keys.Max();

    return Enumerable.Range(min, max-min).Except(dict.Keys).First();   
}

Use it as

int result = new Dictionary<int, string>(){ {1, "a"}, {2, "a"}, 
                                            {8, "a"}, {4, "a"}, 
                                                      {3, "a"}}.AddNext();

Here result comes to be 5.

Answer 2

You can use SortedList with Extension method for Adding to next automatically retrieved key.

Assuming Data structure be any object, with numeric key,

Following is ExtensionMethod for SortedList

public static class SortedListExtensions
{
    ///Add item to sortedList (numeric key) to next available key item, and return key
    public static int AddNext<T>(this SortedList<int, T> sortedList, T item)
    {
        int key = 1; // Make it 0 to start from Zero based index
        int count = sortedList.Count;

        int counter=0;
        do
        {
            if (count == 0) break;
            int nextKeyInList = sortedList.Keys[counter++];

            if (key != nextKeyInList) break;

            key = nextKeyInList +1;

            if (count == 1 || counter == count  ) break;


            if (key != sortedList.Keys[counter])
                break;

        } while (true);

        sortedList.Add(key, item);
        return key;
    }

}

It can be used like following

  SortedList<int, string> x = new SortedList<int, string>();

        x.Add(4, "BCD");
        x.Add(6, "BCD");

        x.AddNext("a");
        x.AddNext("b");
        x.AddNext("c");
        x.AddNext("d");
        x.AddNext("e");

        foreach (var item in x)
            Console.WriteLine(item.Key + " " + item.Value);

The output is

        1 a
        2 b
        3 c
        4 BCD
        5 d
        6 BCD
        7 e

You can use Dictionary, or any other data structure. In that case Double loop will be required. In case of SortedList, one loop is saved while searching key. This loop is internally used by SortedList.Add function using BinarySearch Algorithm.

Binary search is faster than looping all elements (for larger size data).