boat+hill

·舟山詩詞·淘海洗玉集 – My Poems, and etc.

EqualityComparer

leave a comment »

In C#, for a list of string (or some primitive type), IEnumerable.Distinct() method can help reduce the duplicates.

var distinctList = strList.Distinct();
 

However, for a list of complex type, this may not work as expected, since Distinct() will produce a new list based on the hash code of each item. For any Foo type class, in order to use Distinct() method, Equals() and GetHashCode() need to be override.

public override bool Equals(object obj)
{
  Foo other = obj as Foo;
  return 
    other != null && 
    other.Name.Equals(this.Name) && 
    other.Prop.Equals(this.Prop);
}

public override int GetHashCode()
{
  var tuple = new Tuple<string, PropType>(this.Name, this.Prop);
  int hashCode = tuple.GetHashCode();
  return hashCode;
}

For hash code, see algorithms, here, and here. Do remember the rule: “If two objects compare as equal, the GetHashCode method for each object must return the same value. However, if two objects do not compare as equal, the GetHashCode methods for the two object do not have to return different values.” (See more rules and guidelines on this blog)

In many cases, the developer may not own the code of class Foo to override Equals() and GetHashCode(), or the Distinct may vary in run time. One solution is to use GroupBy method in System.Linq.Enumerable extension applying on item’s property (e.g. using Name as a key to distinguish each item):

var distinctList = myList
    .GroupBy(i => i.Name)
    .Select(g => g.First())
    .ToList();

And for more than 1 key property (e.g. Prop1 and Prop2) in a group:

var distinctList = myList
    .GroupBy(i => new { i.Prop1, i.Prop2 })
    .Select(g => g.First())
    .ToList();

Same can be done with group operator using System.Linq:

var distinctList = (
    from i in recipients
    group i by new { i.Prop1, i.Prop2 } into grp
    select grp.First()).ToList();

Alternatively IEnumerable.Distinct() method can take an IEqualityComparer in the following style

var distinctList = myList.Distinct(
    EqualityFactory.Create<FooType>(
    (x, y) => x.Prop1 == y.Prop1 && x.Prop2 == y.Prop2)
    ).ToList();

Here is the source code of the factory:

// -------------------------------------
// <copyright file="EqualityFactory.cs" company="OpenSource">
//  Copyleft (c) All rights released.
// </copyright>
// -------------------------------------

namespace Common.Helpers
{
  using System;
  using System.Collections.Generic;

  /// <summary>
  /// Factory to produce instances of the <see cref="EqualityComparer{T}" /> class.
  /// <typeparam name="T">the type of an object.</typeparam>
  /// </summary>
  public class EqualityFactory
  {
    /// <summary>
    /// Creates a new instance of the <see cref="IEqualtyComparer{T}" /> class.
    /// </summary>
    /// <typeparam name="T">the type of an object.</typeparam>
    /// <returns>returns an instance of equality comparer.</returns>
    public static IEqualityComparer<T> Create<T>(Func<T, T, bool> funcComparer)
    {
      return new ImpEqualityComparer<T>(funcComparer);
    }

    #region internal equality comparer class

    /// <summary>
    /// Implements <see cref="IEqualityComparer" /> interface.
    /// </summary>
    /// <typeparam name="T">the type of an object.</typeparam>
    private class ImpEqualityComparer<T> : IEqualityComparer<T>
    {
      /// <summary>the comparison function.</summary>
      private Func<T, T, bool> comparer;

      /// <summary>the default comparison function.</summary>
      private IEqualityComparer<T> defaultComparer;

      /// <summary>
      /// Initializes a new instance of the <see cref="ImpEqualityComparer{T}" /> class.
      /// </summary>
      public ImpEqualityComparer(Func<T, T, bool> delegateComparer)
      {
        this.comparer = delegateComparer;
        this.defaultComparer = EqualityComparer<T>.Default;
      }

      /// <summary>
      /// Compares objects by using equality comparer.
      /// </summary> 
      /// <returns>returns True if objects are equal; otherwise False.</returns> 
      bool IEqualityComparer<T>.Equals(T x, T y)
      {
        if (x == null && y == null) return true;
        if (x == null || y == null) return false;

        return this.comparer(x, y);
      }

      /// <summary>
      /// Get hash code by the equality comparer.
      /// </summary>
      /// <returns>returns the hash code.</returns>
      int IEqualityComparer<T>.GetHashCode(T obj)
      {
        // In order to use the comparer, the hash code has to be the same.
        return 0;
      }
    }

    #endregion
  }
}
// class EqualityFactory

If hash code comparison is required, use an LambdaEqualityComparer class instead. In the following example, the distinct result will be based on objects’ Name, and other properties (Prop1 and Prop2).

var distinctList = myList.Distinct(
    new LambdaEqualityComparer<FooType>(
    (x, y) => x.Prop1 == y.Prop1 && x.Prop2 == y.Prop2,
    (t) => t.Name.GetHashCode()) // assume t.Name is a string
    ).ToList();

See LambdaEqualityComparer class source code:

// -------------------------------------
// LambdaEqualityComparer.cs
// -------------------------------------

namespace Common.Helpers
{
  using System;
  using System.Collections.Generic;

  /// <summary>
  /// Implements <see cref="IEqualityComparer" /> interface.
  /// </summary>
  /// <typeparam name="T">the type of an object.</typeparam>
  public class LambdaEqualityComparer<T> : IEqualityComparer<T>
  {
    /// <summary>
    /// Initializes a new instance of the <see cref="LambdaEqualityComparer{T}" /> class.
    /// </summary>
    public LambdaEqualityComparer(
      Func<T, T, bool> funcEquals, 
      Func<T, int> funcGetHashCode = null)
    {
      if (funcEquals == null)
      {
        throw new ArgumentNullException("funcEquals", "An equals function is required.");
      }
      this.GetHashCodeMethod = funcGetHashCode;
      this.EqualsMethod = funcEquals;
    }

    /// <summary>Gets and sets the method used to compute equals.</summary>
    public Func<T, T, bool> EqualsMethod { get; private set; }

    /// <summary>Gets and sets the method used to compute a hash code.</summary>
    public Func<T, int> GetHashCodeMethod { get; private set; }

    /// <summary>
    /// Implements Equals from <see cref="IEqualityComparer{T}" /> interface.
    /// </summary>
    /// <returns>returns result of the comparison.</returns>
    bool IEqualityComparer<T>.Equals(T x, T y)
    {
      return this.EqualsMethod(x, y);
    }

    /// <summary>
    /// Implements GetHashCode from <see cref="IEqualityComparer{T}" /> interface.
    /// </summary>
    /// <returns>returns hash code.</returns>
    int IEqualityComparer<T>.GetHashCode(T obj)
    {
      if (this.GetHashCodeMethod == null) return 0;

      return this.GetHashCodeMethod(obj);
    }
  }  
}// class LambdaEqualityComparer

More advanced, to wrap GetHashCode into a projection (MiscUtil):

// -------------------------------------
// ProjectionEqualityComparer.cs
// -------------------------------------

namespace Common.Helpers
{
  using System;
  using System.Collections.Generic;

  /// <summary>
  /// Comparer uses projected keys from source element.
  /// </summary>
  /// <typeparam name="TSource">Type of elements the comparer to project.</typeparam>
  /// <typeparam name="TKey">Type of the key projected from the element.</typeparam>
  public class ProjectionEqualityComparer<TSource, TKey> : IEqualityComparer<TSource>
  {
    /// <summary>the comparison function.</summary>
    private readonly Func<TSource, TKey> projection;

    /// <summary>the equality comparer.</summary>
    private readonly IEqualityComparer<TKey> comparer;

    /// <summary>
    /// Initializes a new instance of the <see cref="ProjectionEqualityComparer{TSource, TKey}" />.
    /// Using default comparer for the projected type.
    /// </summary>
    public ProjectionEqualityComparer(
      Func<TSource, TKey> projection) : this(projection, null)
    {
    }

    /// <summary>
    /// Initializes a new instance of the <see cref="ProjectionEqualityComparer{TSource, TKey}" />.
    /// The default comparer for the projected type is used if a comparer not specified.
    /// </summary>
    public ProjectionEqualityComparer(
      Func<TSource, TKey> projection, IEqualityComparer<TKey> comparer)
    {
      if (projection == null)
      {
        throw new ArgumentNullException("projection");
      }
      this.comparer = comparer ?? EqualityComparer<TKey>.Default;
      this.projection = projection;
    }

    /// <summary>
    /// Compares the two specified values for equality by applying the projection to
    /// each value and then using the equality comparer on the resulting keys.
    /// Null references are never passed to the projection.
    /// </summary>
    /// <returns>returns True if objects are equal; otherwise False.</returns>
    public bool Equals(TSource x, TSource y)
    {
      if (x == null && y == null) return true;
      if (x == null || y == null) return false;

      return this.comparer.Equals(this.projection(x), this.projection(y));
    }

    /// <summary>
    /// Produces a hash code for the given value by projecting it and then
    /// asking the equality comparer to find the hash code of the resulting key.
    /// </summary>
    /// <returns>returns the hash code.</returns>
    public int GetHashCode(TSource obj)
    {
      if (obj == null)
      {
        throw new ArgumentNullException("obj");
      }
      return this.comparer.GetHashCode(this.projection(obj));
    }
  }
}// class ProjectionEqualityComparer

Or using string value of a property name (see Cuemon.Reflection):

// -------------------------------------
// PropertyEqualityComparer.cs
// -------------------------------------

namespace Common.Helpers
{
  using System;
  using System.Collections.Generic;
  using System.Linq;
  using System.Reflection;

  /// <summary>
  /// Implements <see cref="IEqualityComparer{T}" /> interface.
  /// </summary>
  /// <typeparam name="T">the type of an object.</typeparam>
  public class PropertyEqualityComparer<T> : IEqualityComparer<T>
  {
    /// <summary>the <see cref="PropertyInfo"/> object.</summary>
    private PropertyInfo propertyInfo;

    /// <summary>
    /// Initializes a new instance of the <see cref="PropertyEqualityComparer{T}" /> class.
    /// </summary>
    public PropertyEqualityComparer(string propertyName)
    {
      // store a reference to the <see cref="PropertyInfo"/> for use in comparison
      this.propertyInfo = typeof(T).GetProperty(
        propertyName, 
        BindingFlags.GetProperty | BindingFlags.Instance | BindingFlags.Public
        );
      if (this.propertyInfo == null)
      {
        var message = string.Format(
          "The name '{0}' is not a property of type {1}.", 
          propertyName, typeof(T));
        throw new ArgumentException(message);
      }
    }

    #region Methods :: Implments IEqualityComparer

    /// <summary>
    /// Implements Equals from <see cref="IEqualityComparer{T}" /> interface.
    /// </summary>
    /// <returns>returns result of the comparison.</returns>
    public bool Equals(T x, T y)
    {
      // get the current value of the comparison property of x and of y
      var valueX = this.propertyInfo.GetValue(x, null);
      var valueY = this.propertyInfo.GetValue(y, null);
    
      // consider equal only if both xValue and yValue are null
      if (valueX == null)
      {
        return valueY == null;
      }
      // use default comparer
      return valueX.Equals(valueY);
    }

    /// <summary>
    /// Implements GetHashCode from <see cref="IEqualityComparer{T}" /> interface.
    /// </summary>
    /// <returns>returns hash code.</returns>
    public int GetHashCode(T obj)
    {
      var propertyValue = this.propertyInfo.GetValue(obj, null);

      if (propertyValue != null)
      {
        return propertyValue.GetHashCode();
      }
      return 0;
    }
  
    #endregion
  }  
}

Happy coding!

Written by Boathill

2014-01-02 at 22:00

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: