Как написать Equatable или Comparable тип

Не редко возникает необходимость добавить к типу данных, созданных вами, возможности для сравнения экземпляров друг с другом или с другими объектами. В C#, так уж повелось, это не самая простая операция, чреватая и ошибками и избыточным кодом. Связано это с тем, как мне кажется, что в различных источниках приведены самые разные "паттерны" реализации сравнения и люди, начитавшись (кто-то больше, кто-то меньше) иногда смешивают подходы в одном примере с подходами в другом да добавляют ещё и что-то от себя лично :) Таким образом "паттерны" размножаются, служа пищей для размышления и источником вдохновения для следующего поколения программистов, которые читают доставшийся им код, другие публикации и придумывают свои "паттерны".

Компараторы для HashSet<>

Как я попробовал показать в предыдущем сообщении, стандартная реализация компаратора для HashSet<> содержит ошибку, которая состоит в том, что при сравнении элементов хешсета может использоваться внутренний компаратор хешсета, а при расчёте хешкода всегда используется стандартный (EqualityComparer<>.Default).

Настало время эту ошибку исправить. Вдаваясь в долгие и скучные объяснения с различными примерами можно показать, что одним методом без параметров для получения компаратора, как HashSet<>::CreateSetComparer(), нельзя вернуть универсальный компаратор на все случаи жизни. Поэтому придётся использовать два метода:

• Один (без параметров) возвращает компаратор, который для сравнения элементов и расчёта хешкода всегда использует внутренний компаратор хешсета. При этом, при сравнении двух хешсетов компаратор вернёт false в том случае, если компараторы в хешсетах не эквивалентны.
• Второй позволяет задать извне компаратор, который будет использоваться для сравнения элементов хешсета и расчёта хешкода.

Первый метод следует использовать тогда, когда вы заранее знаете, что будете сравнивать хешсеты, которые одинаково (одним и тем же компаратором) сравнивают свои собственные элементы. Второй метод позволит сравнивать произвольные хешсеты, но вы должны сами задать (с помощью компаратора) - как именно следует сравнивать элементы в этих хешсетах.

Вот эти методы (класс Comparers у меня содержит всякое безобразие для всевозможных компараторов, например, ещё это и это):

public static partial class Comparers
{
 public static EqualityComparer<HashSet<T>> HashSetComparer<T>() {
   return HashSetEqualityComparer<T>.Default;
 }

 public static EqualityComparer<HashSet<T>> HashSetCustomComparer<T>(IEqualityComparer<T> comparer = null) {
   return new HashSetCustomEqualityComparer<T>(comparer);
 }
}

Первый метод всегда возвращает один и тот же объект, так логика работы этого компаратора не зависит от каких либо внешних факторов. Второй метод возвращает компаратор, параметризованный другим компаратором, который будет использоваться для сравнения элементов хешсета, поэтому каждый раз создаётся новый объект. Рассмотрим устройство и особенности этих объектов.

Первый компаратор:

public static partial class Comparers
{
 [Serializable]
 private sealed class HashSetEqualityComparer<T> : EqualityComparer<HashSet<T>>
 {
   private const int MagicNumber = 13;

   static HashSetEqualityComparer() {
     Default = new HashSetEqualityComparer<T>();
   }

   public static new HashSetEqualityComparer<T> Default { get; private set; }

   public override bool Equals(HashSet<T> x, HashSet<T> y) {
     if(x == null) {
       return y == null;
     } else if(y == null) {
       return false;
     } else if(!Equals(x.Comparer, y.Comparer)) {
       return false;
     }//if

     return x.SetEquals(y);
   }

   public override int GetHashCode(HashSet<T> obj) {
     if(obj == null) {
       return 0;
     }//if

     return obj.Aggregate(0, (hash, item) =>
       hash ^ (obj.Comparer.GetHashCode(item) & 0x7FFFFFFF));
   }

   public override bool Equals(object obj) {
     return obj is HashSetEqualityComparer<T>;
   }

   public override int GetHashCode() {
     return MagicNumber;
   }
 }
}

Особенности:

• Данный компаратор умеет сравнивать только хешсеты с одинаковыми компараторами, зато достаточно оптимально.
• При вычислении хешкода для получения хешкода элемента хешсета используется внутренний компаратор хешсета.
• Любые два экземпляра этого компаратора всегда равны между собой (а экземпляров может быть несколько, так как конструктор открытый). Вообще, реализация сравнения в компараторах - отдельная тема. Обратите внимание, что для сравнения компараторов здесь используется метод Object::Equals(object, object), а не оператор сравнения (как, например, в родной реализации компаратора).
• MaficNumber, не равный нулю, используется из-за того, что равный нулю хешкод обычно возвращается для объектов, имеющих значение null.

Второй компаратор:

public static partial class Comparers
{
 [Serializable]
 private sealed class HashSetCustomEqualityComparer<T> : EqualityComparer<HashSet<T>>
 {
   public HashSetCustomEqualityComparer(IEqualityComparer<T> comparer = null) {
     Comparer = comparer ?? EqualityComparer<T>.Default;
   }

   private IEqualityComparer<T> Comparer { get; set; }

   public override bool Equals(HashSet<T> x, HashSet<T> y) {
     if(x == null) {
       return y == null;
     } else if(y == null) {
       return false;
     } else if(Equals(x.Comparer, y.Comparer) && Equals(x.Comparer, Comparer)) {
       return x.SetEquals(y);
     }//if

     var set = new HashSet<T>(x, Comparer);
     return set.SetEquals(y);
   }

   public override int GetHashCode(HashSet<T> obj) {
     if(obj == null) {
       return 0;
     }//if

     return obj.Aggregate(0, (hash, item) =>
       hash ^ (Comparer.GetHashCode(item) & 0x7FFFFFFF));
   }

   public override bool Equals(object obj) {
     var other = obj as HashSetCustomEqualityComparer<T>;
     return other != null && Equals(other.Comparer, Comparer);
   }

   public override int GetHashCode() {
     return Comparer.GetHashCode();
   }
 }
}

Особенности:

• Если компараторы сравниваемых хешсетов эквивалентны как между собой, так и с внутренним компаратором, будет использован более оптимальный способ сравнения.
• При вычислении хешкода для получения хешкода элемента хешсета используется собственный компаратор.

Конечно, можно было бы обойтись и одним методом и одним классом компаратора, но было бы больше проверок и ветвлений, поэтому я выбрал небольшое дублирование кода (реализация GetHashCode() у компараторов отличается только используемым внутри компаратором), но более простые классы.

В заключении надо сказать, что похожие проблемы есть и у компаратора, который стандартная библиотека предоставляет для SortedSet<>. Я, как мог, постарался описать их на форуме BCL (здесь) и узнал, что, оказывается, это всё by design, то есть "так и задумано". Хотя это может быть и ошибочным мнением. Отдельно на коннект сообщать об этой, второй, похожей проблеме нет желания - много писанины с заранее известным результатом. Буду надеяться, что справившись с опубликованной багой они просмотрят аналогичный код и приведут его в соответствие.

Баг в реализации HashSet<>::CreateSetComparer()

Не правильно работает компаратор, возвращаемый методом CreateSetComparer класса HashSet<>. Пример кода, демонстрирующий ошибку:

using System;
using System.Collections.Generic;
using System.Diagnostics;

internal sealed class MyItem
{
  public MyItem(int number, string text) {
    Number = number;
    Text = text ?? String.Empty;
  }

  public int Number { get; private set; }
  public string Text { get; private set; }
}

internal sealed class MyItemComparer : EqualityComparer<MyItem>
{
  public override bool Equals(MyItem x, MyItem y) {
    if(x == null) {
      return y == null;
    } else if(y == null) {
      return false;
    } else {
      return EqualityComparer<int>.Default.Equals(x.Number, y.Number);
    }//if
  }

  public override int GetHashCode(MyItem obj) {
    if(obj == null) {
      return 0;
    }//if

    return EqualityComparer<int>.Default.GetHashCode(obj.Number);
  }
}

internal static class Program
{
  private static void Main() {
    var itemComparer = new MyItemComparer();

    var set1 = new HashSet<MyItem>(itemComparer) { new MyItem(1, "One"), };
    var set2 = new HashSet<MyItem>(itemComparer) { new MyItem(1, "1"), };

    var test = set1.SetEquals(set2);
    Debug.Assert(test); // OK

    var setComparer = HashSet<MyItem>.CreateSetComparer();
    var equals = setComparer.Equals(set1, set2);
    Debug.Assert(equals); // OK

    var hash1 = setComparer.GetHashCode(set1);
    var hash2 = setComparer.GetHashCode(set2);
    Debug.Assert(hash1 == hash2, "hash1 == hash2"); // Failed
  }
}

Ошибка заключается в том, что для двух объектов, которые компаратор считает равными, он возвращает различные хеш-коды. Происходит это в рассмотренном случае из-за того, что при рассчёте равенства используется внутренний компаратор хеш-сета (потому что компараторы оказываются равными), а вот при подсчёте хеш-кода всегда используется дефолтовый компаратор.

Для решения моей проблемы будет достаточным написать свой аналог компаратора, в который можно будет передать кастомный компаратор элементов.

Update: Желающие могут проголосовать за этот баг на коннекте.

О реализации сравнений /* CompareTo() */

Почему-то не редко встречаюсь с мнением, что реализация сравнения двух знаковых целых (Int32) делается (или [наиболее] эффективно может быть сделана) с помощью обычной операции вычитания, например:

static int CompareTo(int x, int y) {
  return x - y;
}

Это не правда. Во-первых, как поведёт себя такая функция сравнения с аргументами:

var compare = CompareTo(Int32.MaxValue, Int32.MinValue);

и, во-вторых (если это не убедительно), посмотрите, наконец, реализацию:

public int CompareTo(int value) {
  // Need to use compare because subtraction will wrap
  // to positive for very large neg numbers, etc.
  if (m_value < value) return -1;
  if (m_value > value) return 1;
  return 0;
}