Use LINQ to find gaps in a sorted list of objects?

Question

Problem: I have a wpf DataGrid, which is bound to a list of objects from my custom model class. I need to fullfil following requirements:

There is ony a set amount of models in this list (think of an online computer game with 8 players for example)
Each Model has its own unique ID
Models can be added to and removed from the list in runtime
On initialization each model should get the lowest free ID from the list
I don't want to iterate through the list each time a new model is added
All of this needs to happen back-end, so I can't use any xaml code (which is also why I didn't set the wpf tag)

I am looking for something simular to this question, but I struggle to convert my list to something that would be compatible with the Enumerable.Except method.

Here is a little example:

Model:

public class MyModel
{
    public MyModel(int mID, string mName, string mScore)
    {
      ID = mID;
      Name = mName;
      Score = mScore;
    }
    public int ID;
    public string Name;
    public string Score;
  }

Trying to add a new model with the lowest free ID to my list

  List<MyModel> list = new List<MyModel>();
  list.Add(new MyModel(0, "Rodney", "189"));
  list.Add(new MyModel(1, "Janet", "169"));
  list.Add(new MyModel(2, "John", "110"));
  list.Add(new MyModel(3, "Samantha", "160"));
  list.Add(new MyModel(4, "Daniel", "156"));
  list.Add(new MyModel(5, "Jack", "89"));

  list.RemoveAll(x => x.ID == 1);
  var result = Enumerable.Range(list.Min(m => m.ID), list.Count).Except(list).First();
  list.Add(new MyModel(result, "Carolyn", "159")); //Should be 1

I probably have to use some kind of lambda expressions, as I had to for the list.Min() Method, but it already took me ages to get this right.

You might want to have a look into [SortedList](https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.sortedlist-2?view=netframework-4.7.2) collection — Fabjan, Feb 26 '19 at 15:59
A general answer to your question may be interesting, but there are some hints that you may be overthinking this. Why don't you want to iterate over a small list every time it changes? How often does it change? Iterating over small collections (<100 elements) is often faster than more clever approaches. And even when it's not, you have to ask yourself whether being clever is worth the trouble. — StackOverthrow, Feb 26 '19 at 16:18
@TKK the small list is just an example. I don't know how big the lists are going to get (in fact the current one already has more than a few hundret entries), but I am tasked to create a general method to be used to fill any lists in our application. — Azzarrel, Mar 04 '19 at 08:46

score 2 · Accepted Answer · answered Feb 26 '19 at 16:06

2

The issue is that you compare two different kinds of objects. Enumerable.Range(list.Min(m => m.ID), list.Count) is an enumeration of integers between 0 and 5, and when you use Except(list), the list consists of MyModel objects.

You probably want to extract the ids:

var result = Enumerable.Range(list.Min(m => m.ID), list.Count).Except(list.Select(m => m.ID)).First();

answered Feb 26 '19 at 16:06

Tomer

1,606
12
18

1

Probably better to use `.FirstOrDefault()` to avoid Exception when item with `x.ID==0` happens to be the one that was removed. Also handling is needed in case there is no gap (result will be 0). – Peter B Feb 26 '19 at 16:36

score 2 · Answer 2 · answered Feb 26 '19 at 16:42

Why make complicated code? You want the number greater than the lowest item that does not exist in the list

 var result = list.Min(m => m.ID);
 while (list.Any(m => m.ID == result))
   result++;

This may not be the fastest code, but at least it is clear.

score 1 · Answer 3 · answered Feb 26 '19 at 20:31

I don't want to iterate through the list each time a new model is added

Actually this means that you can't use Linq methods like Min, Max and Except because they iterate through your collection under hood.

Another thing you should keep in mind is that RemoveAll also iterate through all items in the list. So you need to change two things: first (already mentioned in Fabjan comment and in Kit answer) is to track all removed identifiers in SortedList and second is to use a Dictionary<int, MyModel> to remove your model by key, which is O(1) complexity instead of O(N) in case with List.

You can encapsulate this logic with following Container class:

public class Container
{
    private readonly Dictionary<int, MyModel> items = new Dictionary<int, MyModel>();
    private readonly SortedList removedIds = new SortedList();
    private int maxId = 0;

    public int Add(MyModel model)
    {
        int id;
        if (removedIds.Count > 0)
        {
            id = (int) removedIds.GetByIndex(0);
            removedIds.RemoveAt(0);
        }
        else
        {
            id = maxId++;
        }

        model.ID = id;
        items.Add(id, model);
        return id;
    }

    public void RemoveById(int id)
    {
        if (!items.ContainsKey(id))
            throw new ArgumentException(); // or just return

        items.Remove(id);
        removedIds.Add(id, id);
    }
}

score 0 · Answer 4 · answered Feb 26 '19 at 17:29

To expand on what a commenter posted, use a SortedList, which you can use to track the free IDs. That way you don't have to look for gaps. When you add something to the main list, remove the first integer from the free list and use that value as the ID of your model. When you remove the model from the main list, add it's ID to the free list.

Use LINQ to find gaps in a sorted list of objects?

4 Answers4