LINQ: Use .Except() on collections of different types by making them convertible/comparable?

Question

Given two lists of different types, is it possible to make those types convertible between or comparable to each other (eg with a TypeConverter or similar) so that a LINQ query can compare them? I've seen other similar questions on SO but nothing that points to making the types convertible between each other to solve the problem.

Collection Types:

public class Data
{
    public int ID { get; set; }
}

public class ViewModel
{
    private Data _data;

    public ViewModel(Data data)
    {
        _data = data;
    }
}

Desired usage:

    public void DoMerge(ObservableCollection<ViewModel> destination, IEnumerable<Data> data)
    {
        // 1. Find items in data that don't already exist in destination
        var newData = destination.Except(data);

        // ...
    }

It would seem logical that since I know how to compare an instance of ViewModel to an instance of Data I should be able to provide some comparison logic that LINQ would then use for queries like .Except(). Is this possible?

Farleigh

Poor old for loop, he was once so useful but, alas, he never makes the one-liner people happy. – Karole

@Marc: I don't agree with the sentiment you are expressing. We have ways of writing code now that more clearly expresses the intent without worrying about the mechanism. for expresses mechanisms and obscures intent. The LINQ-based one-liners that you are decrying often (yes, not always) better express intent and hide mechanisms. This leads to code that is easier to understand and maintain. – Ramses

@Jason, while I was being flippant, any functions you throw into a projection like you are only provides an assumption of intent. – Karole

@Jason, simply that I agree when the LINQ hides simple control-structure based logic. A projection from one type to another is not one of those cases, imo. It's no more clear what is happening than in var newData = MeaningfulFunctionNameHere(destination, data); In both cases, we make an assumption about what is really happening. In reality, I was really just poking fun at the LINQ is cool and applies everywhere crowd. – Karole

What's wrong with you? LINQ is cool and does apply everywhere. ;-) – Ramses

Answer 1

Your best bet is to provide a projection from Data to ViewModel so that you can say

var newData = destination.Except(data.Select(x => f(x)));

where f maps Data to ViewModel. You will need a IEqualityComparer<Data> too.

Ramses

Answer 2

I know this is late but there is a simpler syntax using Func that eliminates the need for a comparer.

public static class LinqExtensions
{
   public static IEnumerable<TSource> Except<TSource, VSource>(this IEnumerable<TSource> first, IEnumerable<VSource> second, Func<TSource, VSource, bool> comparer)
   {
       return first.Where(x => second.Count(y => comparer(x, y)) == 0);
   }

   public static IEnumerable<TSource> Contains<TSource, VSource>(this IEnumerable<TSource> first, IEnumerable<VSource> second, Func<TSource, VSource, bool> comparer)
   {
       return first.Where(x => second.FirstOrDefault(y => comparer(x, y)) != null);
   }

   public static IEnumerable<TSource> Intersect<TSource, VSource>(this IEnumerable<TSource> first, IEnumerable<VSource> second, Func<TSource, VSource, bool> comparer)
   {
       return first.Where(x => second.Count(y => comparer(x, y)) == 1);
   }
}

so with lists of class Foo and Bar

public class Bar
{
   public int Id { get; set; }
   public string OtherBar { get; set; }
}

public class Foo
{
   public int Id { get; set; }
   public string OtherFoo { get; set; }
}

one can run Linq statements like

var fooExceptBar = fooList.Except(barList, (f, b) => f.Id == b.Id);
var barExceptFoo = barList.Except(fooList, (b, f) => b.OtherBar == f.OtherFoo);

it's basically a slight variation on above but seems cleaner to me.

Askja

i like this solution – Purnell

Nice solution. As an optimisation I'd recommend replacing .Count() with .Any() to avoid unnecessary iteration over the collection. – Molotov

Nice! Another suggestion: replace null by default(VSource) – Skaggs

Answer 3

I assume that providing a projection from Data to ViewModel is problematic, so I'm offering another solution in addition to Jason's.

Except uses a hash set (if I recall correctly), so you can get similar performance by creating your own hashset. I'm also assuming that you are identifying Data objects as equal when their IDs are equal.

var oldIDs = new HashSet<int>(data.Select(d => d.ID));
var newData = destination.Where(vm => !oldIDs.Contains(vm.Data.ID));

You might have another use for a collection of "oldData" elsewhere in the method, in which case, you would want to do this instead. Either implement IEquatable<Data> on your data class, or create a custom IEqualityComparer<Data> for the hash set:

var oldData = new HashSet<Data>(data);
//or: var oldData = new HashSet<Data>(data, new DataEqualityComparer());
var newData = destination.Where(vm => !oldData.Contains(vm.Data));

Lyrism

Why would it be problematic? ViewModel has a constructor that takes Data! – Ramses

I mean "problematic" for performance, or philosophically, not in terms of figuring out how to write the code. Performance-wise, the ViewModel class might require a lot of other overhead in its construction. Philosophically, it seems odd to create a bunch of objects just so we can use Except to select some objects that don't meet certain criteria. – Lyrism

Answer 4

If you use this :

var newData = destination.Except(data.Select(x => f(x)));

You have to project 'data' to same type contained in 'destination', but using the code below you could get rid of this limitation :

//Here is how you can compare two different sets.
class A { public string Bar { get; set; } }
class B { public string Foo { get; set; } }

IEnumerable<A> setOfA = new A[] { /*...*/ };
IEnumerable<B> setOfB = new B[] { /*...*/ };
var subSetOfA1 = setOfA.Except(setOfB, a => a.Bar, b => b.Foo);

//alternatively you can do it with a custom EqualityComparer, if your not case sensitive for instance.
var subSetOfA2 = setOfA.Except(setOfB, a => a.Bar, b => b.Foo, StringComparer.OrdinalIgnoreCase);

//Here is the extension class definition allowing you to use the code above
public static class IEnumerableExtension
{
    public static IEnumerable<TFirst> Except<TFirst, TSecond, TCompared>(
        this IEnumerable<TFirst> first,
        IEnumerable<TSecond> second,
        Func<TFirst, TCompared> firstSelect,
        Func<TSecond, TCompared> secondSelect)
    {
        return Except(first, second, firstSelect, secondSelect, EqualityComparer<TCompared>.Default);
    }

    public static IEnumerable<TFirst> Except<TFirst, TSecond, TCompared>(
        this IEnumerable<TFirst> first,
        IEnumerable<TSecond> second,
        Func<TFirst, TCompared> firstSelect,
        Func<TSecond, TCompared> secondSelect,
        IEqualityComparer<TCompared> comparer)
    {
        if (first == null)
            throw new ArgumentNullException("first");
        if (second == null)
            throw new ArgumentNullException("second");
        return ExceptIterator<TFirst, TSecond, TCompared>(first, second, firstSelect, secondSelect, comparer);
    }

    private static IEnumerable<TFirst> ExceptIterator<TFirst, TSecond, TCompared>(
        IEnumerable<TFirst> first,
        IEnumerable<TSecond> second,
        Func<TFirst, TCompared> firstSelect,
        Func<TSecond, TCompared> secondSelect,
        IEqualityComparer<TCompared> comparer)
    {
        HashSet<TCompared> set = new HashSet<TCompared>(second.Select(secondSelect), comparer);
        foreach (TFirst tSource1 in first)
            if (set.Add(firstSelect(tSource1)))
                yield return tSource1;
    }
}

Some may argue that's memory inefficient due to the use of an HashSet. But actually the Enumerable.Except method of the framework is doing the same with a similar internal class called 'Set' (I took a look by decompiling).

Clean

Answer 5

Dirty trick: project the two lists to just their shared IDs, do the Except, and then project the resulting list again to the original type using a Join with the original list to add the rest of the properties you removed with the first Select. Probably the performance is not great, but for small lists it will be okay.

listOfType1.Select(x => x.Id)
    .Except(listOfType2.Select(x => x.Id))
    .Join(listOfType1,
        onlyIds => onlyIds,
        fullData => fullData.Id,
        (onlyIds, fullData)
        => new Type1
        {
            Id = fullData.Id,
            OtherPropertyOfType1 = fullData.OtherPropertyOfType1
        });

Skaggs