source: branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/Hashing/Hasher.cs @ 15849

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

namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.GrammarEnumeration {
  public abstract class Hasher<THashType> {
    protected Hasher(Grammar grammar) {
      Grammar = grammar;
    }

    protected Grammar Grammar { get; }

    protected abstract THashType AggregateHashes(Symbol operatorSym, THashType[] hashes);

    public int CalcHashCode(SymbolString sentence) {
      Debug.Assert(sentence.Any(), "Trying to evaluate empty sentence!");

      Stack<Symbol> parseStack = new Stack<Symbol>(sentence);

      Symbol peek = parseStack.Peek();
      return AggregateHashes(peek, GetSubtreeHashes(parseStack)).GetHashCode();
    }

    private THashType[] GetSubtreeHashes(Stack<Symbol> parseStack) {
      Symbol currentSymbol = parseStack.Pop();

      // ADDITION
      if (currentSymbol == Grammar.Addition) {
        return GetAdditionSubtreeHashes(parseStack);
      }

      // MULTIPLICATION
      if (currentSymbol == Grammar.Multiplication) {
        return GetMultiplicationSubtreeHashes(parseStack);
      }

      // LOG, EXP, SIN, INV
      if (currentSymbol == Grammar.Log || currentSymbol == Grammar.Exp ||
          currentSymbol == Grammar.Sin || currentSymbol == Grammar.Cos ||
          currentSymbol == Grammar.Inv) {
        // Directly aggregate the single subtree
        return new[] { AggregateHashes(parseStack.Peek(), GetSubtreeHashes(parseStack)) };
      }

      // var, const or nonterminal symbol
      return new[] { AggregateHashes(currentSymbol, new THashType[0]) };
    }

    private THashType[] GetAdditionSubtreeHashes(Stack<Symbol> parseStack) {
      var uniqueChildHashes = new HashSet<THashType>();

      // First subtree
      if (parseStack.Peek() == Grammar.Addition) {
        uniqueChildHashes.UnionWith(GetSubtreeHashes(parseStack));
      } else {
        var peek = parseStack.Peek();
        uniqueChildHashes.Add(AggregateHashes(peek, GetSubtreeHashes(parseStack)));
      }
      // Second subtree
      if (parseStack.Peek() == Grammar.Addition) {
        uniqueChildHashes.UnionWith(GetSubtreeHashes(parseStack));
      } else {
        var peek = parseStack.Peek();
        uniqueChildHashes.Add(AggregateHashes(peek, GetSubtreeHashes(parseStack)));
      }

      var result = uniqueChildHashes.ToArray();
      Array.Sort(result);
      return result;
    }

    public THashType[] GetMultiplicationSubtreeHashes(Stack<Symbol> parseStack) {
      var childHashes = new List<THashType>();

      // First subtree
      if (parseStack.Peek() == Grammar.Multiplication) {
        childHashes.AddRange(GetSubtreeHashes(parseStack));
      } else {
        childHashes.Add(AggregateHashes(parseStack.Peek(), GetSubtreeHashes(parseStack)));
      }
      // Second subtree
      if (parseStack.Peek() == Grammar.Multiplication) {
        childHashes.AddRange(GetSubtreeHashes(parseStack));
      } else {
        childHashes.Add(AggregateHashes(parseStack.Peek(), GetSubtreeHashes(parseStack)));
      }

      // Sort due to commutativity
      childHashes.Sort();

      // Cancel out inverse factors.
      bool[] isFactorRemaining = Enumerable.Repeat(true, childHashes.Count).ToArray();

      for (int i = 0; i < isFactorRemaining.Length; i++) {
        if (!isFactorRemaining[i]) continue;
        if (isFactorRemaining.Length <= 2) break; // Until we have constants, we can't cancel out all terms.

        var currFactor = childHashes[i];
        var invFactor = AggregateHashes(Grammar.Inv, new[] { currFactor });

        int indexOfInv = childHashes.IndexOf(invFactor);
        if (indexOfInv >= 0 && isFactorRemaining[indexOfInv]) {
          isFactorRemaining[i] = isFactorRemaining[indexOfInv] = false;
        }
      }

      return childHashes
        .Where((c, i) => isFactorRemaining[i])
        .ToArray();
    }


  }

  public class IntHasher : Hasher<int> {
    public IntHasher(Grammar grammar) : base(grammar) { }

    protected override int AggregateHashes(Symbol operatorSym, int[] hashes) {
      int start;
      if ((operatorSym == Grammar.Addition || operatorSym == Grammar.Multiplication) && hashes.Length <= 1) {
        start = 0;

      } else if (operatorSym is NonterminalSymbol || operatorSym is VariableTerminalSymbol) {
        return operatorSym.StringRepresentation.GetHashCode();

      } else {
        start = operatorSym.StringRepresentation.GetHashCode();
      }

      for (int i = 0; i < hashes.Length; i++) {
        start = ((start << 5) + start) ^ hashes[i];
      }
      return start;
    }
  }

  public class StringHasher : Hasher<string> {
    public StringHasher(Grammar grammar) : base(grammar) { }

    protected override string AggregateHashes(Symbol operatorSym, string[] hashes) {
      var hashesArray = hashes.ToArray();

      if ((operatorSym == Grammar.Addition || operatorSym == Grammar.Multiplication) && hashesArray.Length <= 1) {
        return hashesArray[0];
      }
      if (operatorSym is NonterminalSymbol || operatorSym is VariableTerminalSymbol) {
        return operatorSym.StringRepresentation;
      }

      return $"[{operatorSym.StringRepresentation} ° {string.Join(" ° ", hashesArray)}]";
    }
  }
}