sdgfsdh sdgfsdh - 3 months ago 12
C# Question

How do I generate a new id which is not in an IEnumerable?

I have an

IEnumerable<int>
which contains all existing ids. I would like to generate a new id, which is any
int
that is not in existing ids. I have a hacked together a solution, but I would like to the know the best way to do this.

// Inefficient solution
public static int GetFreshId(this IEnumerable<int> existingIds)
{
int i = Int32.MinValue;
while (existingIds.Contains(i)) // There is a case where all ids are taken!
{
i += 1;
}
return i;
}





Update: here best is defined as:


  • Meeting the requirements

  • Predictable performance

  • Smallest big-oh possible

  • Should work for any
    IEnumerable
    implementation, albiet faster for some than others

  • Should be stateless


Answer

If you don't care to use the lowest free ID you can simply take the successor of the currently biggest ID:

public static int GetFreshId(this IEnumerable<int> existingIds)
{
    return existingIds.Max() + 1;
}

Of course there will be a problem if Int32.MaxValue and Int32.MinValue are already contained, so you'll need some special treatment for this case.

But seeing how many ID's there are in an Int32 range, this should rarely happen so it would be ok to implement a more expensive algorithm for that corner case.


If you're afraid of an overflow, you can improve your first approach by sorting the sequence at first and then scanning for a gap (instead of testing for each possible int-value):

public static int GetFreshId(this IEnumerable<int> existingIds)
{
    int i = Int32.MinValue;
    foreach(int id in existingIds.OrderBy(id => id))
    {
        if (id != i) return i;
        if (i == Int32.MaxValue)
            throw new Exception("We ran out of IDs!");
        i += 1;
    }

    return i; // this now one more than the last/biggest existing ID
}

EDIT: Thanks Ivan to beat me to my big mistake, improved the second approach accordingly