C# collection of two points doesn't return any results

Question

Class:

public class Point : IEqualityComparer<Point>
{               
    public char HorizontalPosition { get; set; }
    public int VerticalPosition { get; set; }

    public Point(char horizontalPosition, int verticalPosition)
    {
        HorizontalPosition = char.ToUpper(horizontalPosition);
        VerticalPosition = verticalPosition;           
    }   

    public bool Equals(Point x, Point y)
    {
        return (x.VerticalPosition == y.VerticalPosition && x.HorizontalPosition == y.HorizontalPosition);
    }

    public int GetHashCode(Point obj)
    {
        return (obj.HorizontalPosition.GetHashCode() + obj.VerticalPosition.GetHashCode());
    }
}

I am trying to find common Points (intersection) in two collections, but the result is empty collection - two elements should be in it. Why? I've implemented IEqualityComparer. Did I did something wrong?

Example collections:

  List<Point> first = new List<Point> { new Point('a', 1), new Point('b', 2) };
  List<Point> second = new List<Point> { new Point('a', 1), new Point('b', 2) };
  List<Point> intersection = first.Intersect(second).ToList();

Intersection is empty list, but two elements should be in it.

Wow, the documentation looks wrong. Your type should implement `IEquatable`, not `IEqualityComparer` — Dennis_E, Oct 05 '16 at 13:40
@Dennis_E Except that it won't work as you expect. Here's why: http://stackoverflow.com/questions/1645891/why-isnt-except-linq-comparing-things-properly-using-iequatable — decPL, Oct 05 '16 at 13:48
@decPL That link talks about it not working if you don't implement `GetHashCode()`. But he has, so I don't see why it won't work as expected. — Dennis_E, Oct 05 '16 at 14:11
That links talks about it not working if you don't **override** `public int GetHashCode()`. What he did is he provided an implementation for `IComparable.GetHashCode(T)` which will never get called for reasons others specified in their answers. And if you don't trust me - check for yourself. — decPL, Oct 05 '16 at 14:15
@decPL I didn't notice it was `IEqualityComparer.GetHashCode()` and not `object.GetHashCode()`. Anyway, that's going into detail of actually implementing `IEquatable`. I was only making a remark on the documentation saying `IEqualityComparer` instead of `IEquatable`. The sentence looks wrong: "The default equality comparer, Default, is used to compare values of the types that implement the IEqualityComparer generic interface." — Dennis_E, Oct 05 '16 at 14:59

score 5 · Answer 1 · answered Oct 05 '16 at 13:38

IEqualityComparer is an interface you can give to the Intersect method to compare items. It is not used by default to compare anything. So your code is just using the built-in Equals in Object which will return false unless the objects are the same object.

You have to either override the default Equal and GetHashCode methods in the class or tell the intersection to use your implementation of the comparer. But you shouldn't implement the comparer in a data storage class.

Nico · Answer 2 · 2016-10-05T13:46:51.820

You should override Equals and GetHashCode from object:

public class Point
{
    public char HorizontalPosition { get; set; }
    public int VerticalPosition { get; set; }

    public Point(char horizontalPosition, int verticalPosition)
    {
        HorizontalPosition = char.ToUpper(horizontalPosition);
        VerticalPosition = verticalPosition;
    }

    public override int GetHashCode()
    {
        unchecked
        { 
            return (HorizontalPosition * 397) ^ VerticalPosition;
        }
    }

    protected bool Equals(Point other)
    {
        return Equals(HorizontalPosition, other.HorizontalPosition) && Equals(VerticalPosition, other.VerticalPosition);
    }

    public override bool Equals(object obj)
    {
        if (ReferenceEquals(null, obj)) return false;
        if (ReferenceEquals(this, obj)) return true;
        if (obj.GetType() != this.GetType()) return false;
        return Equals((Point)obj);
    }
}

You could also implement a custom IEqualityComparer and pass it to intersect:

public class PointComparer : IEqualityComparer<Point>
{
    public bool Equals(Point a, Point b)
    {
        return a.HorizontalPosition == b.HorizontalPosition && a.VerticalPosition == b.VerticalPosition;
    }

    public int GetHashCode(Point p)
    {
        unchecked
        { 
            return (p.HorizontalPosition * 397) ^ p.VerticalPosition;
        }
    }
}

// ...

List<Point> intersection = first.Intersect(second, new PointComparer()).ToList();

As mentioned in the comments by @decPL, you should also reconsider your hash code implementation.

One additional point - OP's GetHashCode implementation is not perfect, as it will create a lot of collisions (hash code for (x,y) == hashcode for (y,x) for any x and y). It's better to use something like `unchecked { return (this.HorizontalPosition * 397) ^ this.VerticalPosition; }` — decPL, Oct 05 '16 at 13:44
Thanks @decPL! That is true and should be implemented that way. I update my answer. — Nico, Oct 05 '16 at 13:45

Stefano d'Antonio · Answer 3 · 2016-10-05T13:49:06.710

Unless specified, Intersect uses EqualityComparer<Point>.Default which will use the object.Equals and object.GetHashCode methods for comparison (they will just check if the reference is the same);

to make it work, pass the comparer to the method:

  List<Point> first = new List<Point> { new Point('a', 1), new Point('b', 2) };
  List<Point> second = new List<Point> { new Point('a', 1), new Point('b', 2) };
  List<Point> intersection = first.Intersect(second, new Point('a', 0)).ToList();

Although, ideally for the SRP you shouldn't have the comparer on the Point class itself as it would look hacky as it looks above creating a Point just as logic class for comparison.

From MSDN:

EqualityComparer

Intersect

score 2 · Accepted Answer · answered Oct 05 '16 at 13:47

List<Point> first = new List<Point> { new Point('a', 1), new Point('b', 2) };
            List<Point> second = new List<Point> { new Point('a', 1), new Point('b', 2) };
            List<Point> intersection = first.Intersect(second, new PointComparer()).ToList();


public class Point 
{
    public char HorizontalPosition { get; set; }
    public int VerticalPosition { get; set; }

    public Point(char horizontalPosition, int verticalPosition)
    {
        HorizontalPosition = char.ToUpper(horizontalPosition);
        VerticalPosition = verticalPosition;
    }
}

public class PointComparer : IEqualityComparer<Point>
{
    public bool Equals(Point x, Point y)
    {
        return (x.VerticalPosition == y.VerticalPosition && x.HorizontalPosition == y.HorizontalPosition);
    }

    public int GetHashCode(Point obj)
    {
        return (obj.HorizontalPosition.GetHashCode() + obj.VerticalPosition.GetHashCode());
    }
}

Try above example

score 1 · Answer 5 · answered Oct 05 '16 at 13:46

You should separate your Point and PointComparer classes.

The manual has good example:

public class ProductA
{ 
    public string Name { get; set; }
    public int Code { get; set; }
}

public class ProductComparer : IEqualityComparer<ProductA>
{

    public bool Equals(ProductA x, ProductA y)
    {
        //Check whether the objects are the same object. 
        if (Object.ReferenceEquals(x, y)) return true;

        //Check whether the products' properties are equal. 
        return x != null && y != null && x.Code.Equals(y.Code) && x.Name.Equals(y.Name);
    }

    public int GetHashCode(ProductA obj)
    {
        //Get hash code for the Name field if it is not null. 
        int hashProductName = obj.Name == null ? 0 : obj.Name.GetHashCode();

        //Get hash code for the Code field. 
        int hashProductCode = obj.Code.GetHashCode();

        //Calculate the hash code for the product. 
        return hashProductName ^ hashProductCode;
    }
}

https://msdn.microsoft.com/en-us/library/bb460136(v=vs.110).aspx

score 0 · Answer 6 · answered Oct 05 '16 at 13:49

As you can find on reference https://referencesource.microsoft.com/

System\Linq\Enumerable.cs

    public static IEnumerable<TSource> Intersect<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second) {
                if (first == null) throw Error.ArgumentNull("first");
                if (second == null) throw Error.ArgumentNull("second");
                return IntersectIterator<TSource>(first, second, null);
            }

...
    static IEnumerable<TSource> IntersectIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
        {
            Set<TSource> set = new Set<TSource>(comparer);
            foreach (TSource element in second) set.Add(element);
            foreach (TSource element in first)
                if (set.Remove(element)) yield return element;
        }
...
// If value is in set, remove it and return true; otherwise return false
        public bool Remove(TElement value) {
            int hashCode = InternalGetHashCode(value);
            int bucket = hashCode % buckets.Length;
            int last = -1;
            for (int i = buckets[bucket] - 1; i >= 0; last = i, i = slots[i].next) {
                if (slots[i].hashCode == hashCode && comparer.Equals(slots[i].value, value)) {
                    if (last < 0) {
                        buckets[bucket] = slots[i].next + 1;
                    }
                    else {
                        slots[last].next = slots[i].next;
                    }
                    slots[i].hashCode = -1;
                    slots[i].value = default(TElement);
                    slots[i].next = freeList;
                    freeList = i;
                    return true;
                }
            }
            return false;
        }

Your comparer actually doesn't used

C# collection of two points doesn't return any results

6 Answers6