CODEWITHSUNDEEP
c#linq
D C
D C

Reputation: 21

Find next incremental value not in existing list using linq

I have two methods in an IntExtensions class to help generate the next available incremental value (which is not in a list of existing integers which need to be excluded). I dont think I'm addressing the NextIncrementalValueNotInList method in the best way and am wondering if I can better use linq to return the next available int?

public static bool IsInList(this int value, List<int> ListOfIntegers) {
    if (ListOfIntegers.Contains(value))
        return true;

    return false;
}

public static int NextIncrementalValueNotInList(this int value, 
                                                List<int> ListOfIntegers) {

        int maxResult;
        maxResult = ListOfIntegers.Max() + 1;

        for (int i = value; i <= maxResult; i++)
        {
            if (!(i.IsInList(ListOfIntegers)))
            {
                return i;
            }
        }
        return maxResult;
    }

Upvotes: 2

Views: 329

Answers (3)

Nikita B
Nikita B

Reputation: 3333

Using linq your method will look like:

return IEnumerable.Range(1, ListOfIntegers.Count + 1)
                  .Except(ListOfIntegers)
                  .First();

Upvotes: 5

Andras Zoltan
Andras Zoltan

Reputation: 42333

You don't actually need to calculate the Max value - just keep incrementing i until you find a value that doesn't exist in the list, e.g:

public static int NextIncrementalValueNotInList(this int value, 
  List<int> ListOfIntegers)
{
    int i = value;

    while(true)
    {
        if (!(i.IsInList(ListOfIntegers)))
        {
            return i;
        }
        i++;
    }
    return maxResult;
}

. Besides that, I'm not sure if there's much more you can do about this unless:

  • ListOfIntegers is guaranteed to be, or needs to be, sorted, or
  • ListOfIntegers doesn't actually need to be a List<int>

If the answer to the first is no, and to the second is yes, then you might instead use a HashSet<int>, which might provide a faster implementation by allowing you to simply use HashSet<T>'s own bool Contains(T) method:

public static int NextIncrementalValueNotInList(this int value, 
  HashSet<int> ListOfIntegers) 
{
    int i = value;
    while(true)
    {
        if (!(ListOfIntegers.Contains(i))
        {
            return value;
        }
        i++;
    }
}

Note that this version shows how to do away with the Max check also.

Although be careful of premature optimisation - if your current implementation is fast enough, then I wouldn't worry. You should properly benchmark any alternative solution with extreme cases as well as real-world cases to see if there's actually any difference.

Also what you don't want to do is use my suggestion above by turning your list into a HashSet for every call. I'm suggesting changing entirely your use of List to HashSet - any piecemeal conversion per-call will negate any potential performance benefits due to the overhead of creating the HashSet.

Finally, if you're not actually expecting much fragmentation in your integer list, then it's possible that a HashSet might not be much different from the current Linq version, because it's possibly going to end up doing similar amounts of work anyway.

Upvotes: 2

Serge
Serge

Reputation: 6692

I guess it starting at 1.

You could also proceed like this:

IEnumerable.Range(1, ListOfIntegers.Count)
           .Where(i => !ListOfIntegers.Contains(i))
           .Union(new []{ ListOfIntegers.Count + 1 })
           .First();

Upvotes: 2

Related Questions