What happens when ==, CompareTo(), and Equals() do not agree?

1.5k views Asked by At

I have a program I wrote some years back to find "good" binary operators for bytes; byte A is left multiplied by byte B to yield byte C. The operator is defined as 256x256 byte matrix. A stripped down version of the class implementation is below.

Equals() is true IFF all 65536 bytes in the array are the same.

CompareTo() compares the Linearity of the operator into a continuum of more linear (bad for cryto) to less linear (good for crypto).

So it is possible for two instances, A and B, that both of the following are true:

A.Equals(B) = false
(A.ComparesTo(B) == 0) = true

My question is less: Is this a good idea? I know the answer is No, but given the large computational cost of measuring linearity and the narrow nature of my problem this design works. Also code similar to:

if (localMinimumOperator < globalMinimumOperator)
{
  localMinimumOperator = globalMinimumOperator;
}

is easier for me to read.

My question is: What are the consequences of this divergence among: ==, CompareTo()== 0, and Equals()? or alternately: Is there list of which LINQ extensions methods describing which extension use which interface (IEquatable or IComparable)?

Something more concise than this MSDN article on Enumerable?

For example:

IEnumerable<BinaryOperation> distinct = orgList.Distinct();

calls Equals(BinaryOperator) as per: Enumerable.Distinct<TSource> Method as does Contains(). I understand that Sort() and OrderBy() use calls to CompareTo().

But what about FindFirst() and BinarySearch()?

My example class:

using System;
using System.Collections.Generic;
using System.Linq;


namespace Jww05
{
  public class BinaryOperation : IEquatable<BinaryOperation>, IComparable<BinaryOperation>
  {
    #region ClassMembers

    public List<List<byte>> TruthTable
    {
      get
      {
        // I don't like giving out the underlying list if I help it
        var retVal = new List<List<byte>>(OperatorDefintion);
        return retVal;
      }
    }

    // private data store for TruthTable
    private List<List<byte>> OperatorDefintion { get; set; }

    public BinaryOperation()
    {
      // initial state is the Identity operator
      OperatorDefintion = new List<List<byte>>();
      for (int i = 0; i < 256; i++)
      {
        var curRow = new List<byte>();
        for (int j = 0; j < 256; j++)
        {
          curRow.Add((byte)(i + j));
        }
        OperatorDefintion.Add(curRow);
      }
    }

    private long MeasureOperatorLinearity()
    {
      var diagonalOffsets = new byte[] { 255, 0, 1 };

      /*
       * Code that measures linearity in the original code used the Fast Walsh Hadamard Transform.
       * That should go here, but it is removed because the FWHT is clutter for the purposes of this question.
       *
       * Since I needed a stub for this, I decided to exacerbate the differnece
       * between CompareTo() == 0 and Equals()
       * by returning an arbitrary int in lieu of the long CPU intensive Fast Walsh Hadamard Transform.
       *
       * If the matrices are identical on an element-by-element basis, then the Faux Linearity will be the the same.
       * If the faux linearity (sum of terms on the main diagonal and corners) are the same, the underlying matrices could be different on an element-by-element basis.
       */
      long fauxLinearityMeasure = 0;
      for (var currRow = 0; currRow < OperatorDefintion.Count(); ++currRow)
      {
        fauxLinearityMeasure *= 5;
        fauxLinearityMeasure = diagonalOffsets.Select(diagonalOffset => (byte)(currRow + diagonalOffset))
                                              .Aggregate(fauxLinearityMeasure, (current, offestedIndex) => current + (OperatorDefintion[offestedIndex][currRow]));
      }

      return (int)fauxLinearityMeasure;
    }

    #endregion ClassMembers

    #region ComparisonOperations

    public int CompareTo(BinaryOperation other)
    {
      long otherLinearity = other.MeasureOperatorLinearity();
      long thisLinearity = MeasureOperatorLinearity();
      long linearityDiff = thisLinearity - otherLinearity;

      // case the differnece of the linarity measures into {-1, 0, 1}
      return (0 < linearityDiff) ? 1
           : (0 > linearityDiff) ? -1
           : 0;
    }

    public static bool operator >(BinaryOperation lhs, BinaryOperation rhs)
    {
      if (ReferenceEquals(null, lhs) ||
          ReferenceEquals(null, rhs))
      {
        return false;
      }
      return (0 < lhs.CompareTo(rhs));
    }

    public static bool operator <(BinaryOperation lhs, BinaryOperation rhs)
    {
      if (ReferenceEquals(null, lhs) ||
          ReferenceEquals(null, rhs))
      {
        return false;
      }
      return (0 > lhs.CompareTo(rhs));
    }

    public static bool operator <=(BinaryOperation lhs, BinaryOperation rhs)
    {
      if (ReferenceEquals(null, lhs) ||
          ReferenceEquals(null, rhs))
      {
        return false;
      }

      // equals is cheap
      if (lhs.Equals(rhs))
      {
        return true;
      }

      return (0 > lhs.CompareTo(rhs));
    }

    public static bool operator >=(BinaryOperation lhs, BinaryOperation rhs)
    {
      if (ReferenceEquals(null, lhs) ||
          ReferenceEquals(null, rhs))
      {
        return false;
      }

      // equals is cheap
      if (lhs.Equals(rhs))
      {
        return true;
      }

      return (0 < lhs.CompareTo(rhs));
    }

    #endregion ComparisonOperations

    #region EqualityOperators

    public bool Equals(BinaryOperation other)
    {
      if (ReferenceEquals(null, other))
      {
        return false;
      }

      var otherTruthTable = other.TruthTable;
      var thisTruthTable = TruthTable;
      var isEquals = true;
      for (int currRow = 0; currRow < thisTruthTable.Count(); ++currRow)
      {
        isEquals = isEquals && thisTruthTable[currRow].SequenceEqual(otherTruthTable[currRow]);
      }

      return isEquals;
    }

    public override bool Equals(object obj)
    {
      return Equals(obj as BinaryOperation);
    }

    public override int GetHashCode()
    {
      return OperatorDefintion.SelectMany(currRow => currRow)
                              .Aggregate(1, (current, currByte) => current * 5 + currByte);
    }

    public static bool operator ==(BinaryOperation lhs, BinaryOperation rhs)
    {
      if (ReferenceEquals(null, lhs) ||
          ReferenceEquals(null, rhs))
      {
        return false;
      }

      return (0 == lhs.CompareTo(rhs));
    }

    public static bool operator !=(BinaryOperation lhs, BinaryOperation rhs)
    {
      if (ReferenceEquals(null, lhs) ||
          ReferenceEquals(null, rhs))
      {
        return false;
      }

      return (0 != lhs.CompareTo(rhs));
    }

    #endregion EqualityOperators
  }
}
1

There are 1 answers

3
BartoszKP On BEST ANSWER

What are the consequences of this divergence among: ==, CompareTo()== 0, and Equals()?

Someone looking at your code in the future will truly hate you.

or alternately: Is there list of which linq extensions methods describing which extension use which interface (IEquitable or IComparable)?

I think that you've found most of it by yourself. A good rule of thumb is that usually there is nothing surprising in what interface is used by which LINQ function (no surprises is one of features of good design - unlike yours). For example: it's quite obvious that to sort elements it is necessary to know in which particular order should elements go, equality/inequality alone are not sufficient for this. BinarySearch also needs to know "which way to go" during search - if element is larger than current it re-curses into upper part of sorted array, if smaller it goes into lower. Again: obviously it needs IComparable. For Distinct Equals and GetHashCode suffice - sorting is not needed to determine a set of unique elements. And so on.