Equality Comparison with Multiple Instances/IEqualityComparer problems in LINQ

Question

This is similar to my last question; but from a different angle. http://stackoverflow.com/questions/2792393/see-if-item-exists-once-in-enumerable-linq

Given the following set of items, and lists containing them...

Item 1
Item 2
Item 3
Item 4
Item 5

class Item
{
 string Name { get; set; }
}

List<Item> available = new List<Item>()
{
 Item 1
 Item 1
 Item 2
 Item 3
 Item 5
}

List<Item> selected = new List<Item>()
{
 Item 1
 Item 2
 Item 3
}

I need to make a third List that has everything from "available", except what is in "selected". However 'Item 1' is in 'available' twice, but only in 'selected' once. Since they are instances of the same item, I am having trouble figuring out the appropriate logic to accomodate this.

The final array should look like...

List<Item> selectable = new List<Item>()
{
 Item 1
 Item5
}

Answer 1

There may be a LINQ method to accomplish this task. You could certainly get the 5 item since it is unique, but the second item 1 could prove difficult. However, you could always do this the old fashioned way and create the new list yourself. Consider this example:

class Item
{
    public Item(string name) { Name = name; }
    public string Name { get; set; }
}

...

List<Item> available = new List<Item>()
{
    new Item("1"), new Item("1"), new Item("2"), new Item("3"), new Item("5")
};

List<Item> selected = new List<Item>()
{
    new Item("1"),new Item("2"), new Item("3")
};

List<Item> stillAvailable = new List<Item>();
List<Item> stillSelected = new List<Item>(selected);

foreach (Item item in available)
{
    Item temp = stillSelected.Find(i => i.Name == item.Name);
    if (temp == null)
        stillAvailable.Add(item);
    else 
        stillSelected.Remove(temp);
}

You create a list for the items still available, which is initially empty. You create a list for the items still selected, which contains all of the selected items. You then simply iterate over the available items and search the stillSelected list. If the item is found, you remove it from the stillSelected list. If not, you add it to the stillAvailable list. By the end of the loop, stillAvailable will contain a single item 1 and item 5.

Answer 2

This is a kinda tricky approach, but it gets the job done. I borrowed from the "Decorate-Sort-Undecorate" idiom in Python, which does sorting by associating a temporary sort key with an array, combined with the fun and useful fact that anonymous types in .NET have a default EqualityComparer that compares based on the values of their fields.

Step 1: Group the elements in each list by Name, and then associate an index with each item within each group, and flatten the groups back into a regular list:

var indexedAvailable = available.GroupBy(i => i.Name)
                                .SelectMany(g => g.Select((itm, idx) => new 
                                              { Name = itm.Name, Index = idx }));
var indexedSelected = selected.GroupBy(i => i.Name)
                              .SelectMany(g => g.Select((itm, idx) => new
                                              { Name = itm.Name, Index = idx }));

This will turn the lists into these:

indexedAvailable            indexedSelected
Name = Item 1, Index = 0    Name = Item 1, Index = 0
Name = Item 1, Index = 1    Name = Item 2, Index = 0
Name = Item 2, Index = 0    Name = Item 3, Index = 0
Name = Item 3, Index = 0
Name = Item 5, Index = 0

Now you can see that in the indexed lists, each numbered occurrence of any Name in available will match only with the equivalent-numbered occurrence of the same name in selected. So you can use a simple Except to remove anything in indexedAvailable that isn't in indexedSelected, and then "undecorate' by turning the anonymous-typed indexed objects back into Items.

var selectable = indexedAvailable.Except(indexedSelected)
                                 .Select(i => new Item() { Name = i.Name });

And the proof:

foreach (var item in selectable)
    Console.WriteLine(item.Name);
//prints out:
//Item 1
//Item 5

Note that this will work even if selected contains names that aren't in available, e.g. if the second list has an Item 4 like in your last question.

Answer 3

var comp = new MyEqualityComparer();
selectable = available.Distinct(comp).Except(selected, comp);