Checking if all items in one generic collection exist in another using custom comparison delegate

Question

I have a situation where I need a generic method to which I can pass two collections of type T along with a delegate that compares the two collections and returns true if every element in collection 1 has an equal element in collection 2, even if they are not in the same index of the collection. What I mean by "equal" is handled by the delegate. My initial thought was to return false if the collections were different lengths and otherwise sort them and then compare them like parallel arrays. Then it occurred to me that I can't sort a collection of a generic type without the types sharing an interface. So now I am thinking a LINQ expression might do the trick, but I can't think of how to write it. Consider my current code:

private static bool HasSameCollectionItems<T>(ICollection<T> left, ICollection<T> right, Func<T, T, bool> func)
{
    if (left.Count != right.Count)
    {
        return false;
    }

    foreach (var item in left)
    {
        bool leftItemIsInRightCollection = ??? MAGIC ???

        if (!leftItemIsInRightCollection)
        {
            return false;
        }
    }

    return true;
}

I would like to replace ??? MAGIC ??? with a LINQ expression to see if item is "equal" to an element in right using the passed in delegate func. Is this even possible?

Note: For reasons I don't want to bother getting into here, impelemnting IEquatable or overriding the Equals method is not an option here.

And why are you looking for LINQ and MAGIC when `for` & `foreach` are right there waiting for you? — Amit, Oct 06 '15 at 20:03
@Amit - I'm not sure exactly what you mean, but my original plan was to order the collections and then use a for loop to check the parallel elements against each other. When I got to that point I realize "Oops, I can't order a collection of type T." — bubbleking, Oct 06 '15 at 20:36
You can iterate it from the start each and every time. All you have is an equality checking function that you *have* to apply to each item, so do exactly that. (And us, it will be O(n^2)) — Amit, Oct 06 '15 at 21:32

Fabjan · Accepted Answer · 2015-10-07T06:26:20.200

0

It looks like you want .All() and .Any() methods (first method checks that all elements satisfy condition second only check if such an element exist) :

bool leftItemIsInRightCollection = right.Any(rItem => func(item, rItem));

Also i'd refactor your code to something like :

    private static bool HasSameCollectionItems<T>(ICollection<T> left, ICollection<T> right, Func<T, T, bool> func)
    {
        return left.Count == right.Count && left.All(LI => right.Any(RI => func(LI, RI)));
    }

edited Oct 07 '15 at 06:26

answered Oct 06 '15 at 20:09

Fabjan

13,506
4
25
52

1

This works but is slow for large collections because: [O(n^2)](http://stackoverflow.com/a/487278/141397) – 3dGrabber Oct 06 '15 at 20:28
Yes, I believe this is perfect. I actually have my code more like what you refactored it into but broke it out too illustrate where that magic had to happen. I was getting lost in the weeds trying to do everything against the left object, chaining Any and Where and all kinds of stuff. I knew a second set of eyes would help me cut through the garbage. Thanks. – bubbleking Oct 06 '15 at 20:29
@3dGrabber Can you think of a faster way without messing with hash codes? – bubbleking Oct 06 '15 at 20:33
No. Unless you can sort the collections, in which case you need `IComparer` or an equivalent delegate – 3dGrabber Oct 06 '15 at 20:39
@Fabjan - The last bit of the refactored code has the ! on func(). Isn't this backwards? func() returns true if the objects match. Am I getting twisted? – bubbleking Oct 06 '15 at 20:47
@bubbleking thank you, it's just a typo, corrected it – Fabjan Oct 06 '15 at 20:48

score 0 · Answer 2 · edited May 23 '17 at 10:26

The following works by checking whether there are element in left which are not in right.

If you insist on a delegate to determine equality, you can use the FuncEqualityComparer from here. (Note that you must also provide an implementation for Object.GetHashCode)

private static bool HasSameCollectionItems<T>(ICollection<T> left, ICollection<T> right,  IEqualityComparer<T> comparer)
{
    if (left.Count != right.Count) return false;

    return !left.Except(right, comparer).Any();
}

Checking if all items in one generic collection exist in another using custom comparison delegate

2 Answers2