CODEWITHSUNDEEP
c#linq
Azzarrel
Azzarrel

Reputation: 573

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

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:

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.

Upvotes: 2

Views: 848

Answers (4)

Aleks Andreev
Aleks Andreev

Reputation: 7054

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);
    }
}

Upvotes: 1

Kit
Kit

Reputation: 21719

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.

Upvotes: 0

Hogan
Hogan

Reputation: 70529

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.

Upvotes: 2

Tomer
Tomer

Reputation: 1704

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();

Upvotes: 2

Related Questions