Creating a custom equality comparer for IEnumerables when T is IEnumerable

Question

I want to have a custom equality comparer IEnumerables. using @PaulZahra's code, I created the following class:

class CustomEqualityComparer<T> : IEqualityComparer<IEnumerable<T>>
{
    public bool Equals(IEnumerable<T> x, IEnumerable<T> y)
    {
        var enumerables = new Dictionary<T, uint>();

        foreach (T item in x)
        {
            enumerables.Add(item, 1);
        }

        foreach (T item in y)
        {
            if (enumerables.ContainsKey(item))
            {
                enumerables[item]--;
            }
            else
            {
                return false;
            }
        }

        return enumerables.Values.All(v => v == 0);
    }

    public int GetHashCode(IEnumerable<T> obj) => obj.GetHashCode();
}

The problem is that if T itself is an IEnumerable, then ContainsKey will check for reference equality, while the point of this equality comparer is to check for value equality at any given depth.

I thought to use .Keys.Contains() instead, since it can accept an IEqualityComparer as an argument:

if (enumerables.Keys.Contains(item, this)) // not sure if "this" or a new object

but I get the following error (CS1929):

'Dictionary.KeyCollection' does not contain a definition for 'Contains' and the best extension method overload 'Queryable.Contains(IQueryable, T, IEqualityComparer)' requires a receiver of type 'IQueryable'

I am not sure how to approach this. How to fix it? Thanks.

Edit: Note that this comparer doesn't care about order.

Side note: cost of iterating an `IEnumerable` multiple times could be enormous (i.e. read all lines in a huge file every time) - make sure you understand limitations and really need that. — Alexei Levenkov, Feb 18 '18 at 19:03
@InBetween - no, the order is not relevant. I Will edit the question to add this information. — Michael Haddad, Feb 18 '18 at 19:09
Your `GetHashcode` is wrong, it won’t return the same hash for equal enumerables — InBetween, Feb 18 '18 at 19:09
@Sipo you approach is plausible (when done correctly) as long as you understand limitations. There is no way to express "this enumerable is safe to enumerate multiple times" in C#/.Net code... Also remember that not everything can be compared - even simple `{ int i=0; while(true){ yield return i++;} }` will cause you a lot of pain :) — Alexei Levenkov, Feb 18 '18 at 19:11
What is the purpose of this comparer? Are you looking for equal elements in the same order? Does order not matter? Does set equality suffice? — MgSam, Feb 18 '18 at 19:13

score 3 · Answer 1 · answered Feb 19 '18 at 00:15

As others have mentioned, IEnumerable<T> can enumerate forever, so it's dangerous to do this on that interface. I'd recommend using ICollection<T> instead- it has a fixed size. And you'll find it will work for most any type you'd want to use anyway.
Furthermore, I'd recommend using TryGetValue to reduce the number of times you need to look up into the dictionary.
Your code is not correctly keeping the count of each item in the first enumerable.
GetHashCode needs to take into account every member of the enumerable.

All that being said, here is an adjustment of your implementation:

class CustomEqualityComparer<T> : IEqualityComparer<ICollection<T>>
{
    public bool Equals(ICollection<T> x, ICollection<T> y)
    {
        if (x.Count != y.Count) return false;
        var enumerables = new Dictionary<T, uint>(x.Count);

        foreach (T item in x)
        {
            enumerables.TryGetValue(item, out var value);
            enumerables[item] = value + 1;
        }

        foreach (T item in y)
        {
            var success = enumerables.TryGetValue(item, out var value);
            if (success)
            {
                enumerables[item] = value - 1;
            }
            else
            {
                return false;
            }
        }

        return enumerables.Values.All(v => v == 0);
    }

    public int GetHashCode(ICollection<T> obj)
    {
         unchecked
         {
             var hashCode = 0;

             foreach(var item in obj)
             {
                 hashCode += (item != null ? item.GetHashCode() : 0);                
             }
             return hashCode;
         }

     }
}

Thanks for the comment! The problem is that `success` is false even when the values do have value equality. — Michael Haddad, Feb 19 '18 at 19:40
@Sipo Ok, I didn't realize that your `T` is also `IEnumerable`, you'll need to add specific handling for that case. Though I think the more important question is what kind of data is it that you're using in this format? — MgSam, Feb 20 '18 at 15:00
Thanks. This case is the core of my question, I will be gratful if you could explain to me how to handle it. I have a class called `WorkSession` with `Entrance` and `Exit` properties. This time represent a period of time an employee is at work. An employee can have multiple `WorkSession` in a day, so I have a dictionary where the key is the day of the week and the value is a list of `WorkSession`. This dictionary represents when the employee should be at work every week. Hope I am clear. — Michael Haddad, Feb 20 '18 at 15:15

Alexei Levenkov · Answer 2 · 2018-02-18T20:44:30.780

To have such recursive comparer you simply need pass proper comparer to Dictionary if T is enumerable. I think getting type T from IEnumerable<T> and then equivalent of new Dictionary<U, uint>(new CustomEqualityComparer<U>) (using Create instance of generic type?) should achieve what you want.

Notes:

you must provide correct implementation of GetHashCode that matches Equals if you use comparer for any dictionary/HashSet. Default Equals for sequences is reference compare that does not align with your Equals. Note that most implementation of GetHashCode depend on order of the items in the collection - so you need to find one that works for sets. I.e. sum of hash codes of each item would do, probably making distribution slightly worse.
you may want to LINQ set operations instead of doing them by hand. All operations like Distinct already take comparers. In case of "sets are the same" you can use Distinct - x.Distinct(y, comparerBuiltViaReflection)
Beware of limitations of such code: not every enumerable can be enumerated more than once (user input, network streams,..) or may produce different result on re-iteration (while(count < 10){ count ++; yield return random.Next(); }), cost of re-iteartion many be significant (re-read all lines in huge file on each iteration) or enumerable can represent infinite sequence (while(true){ yield return count++; }).

Thanks! Could you please give a code example of how to accomplish that with LINQ? — Michael Haddad, Feb 18 '18 at 20:01
@Sipo I've added all links to questions that you need to construct inner comparer and link to `Distinct`. — Alexei Levenkov, Feb 18 '18 at 20:45
Thanks. I have tried to implement your suggestions but I failed. Could you please show me some actual code? I am not sure how to approach this. — Michael Haddad, Feb 20 '18 at 07:58

Creating a custom equality comparer for IEnumerables when T is IEnumerable

2 Answers2