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

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
 *
 * This file is part of HeuristicLab.
 *
 * HeuristicLab is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * HeuristicLab is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
 */
#endregion

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using HeuristicLab.Common;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;

namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration {

  [StorableClass]
  public abstract class Hasher<THashType> : DeepCloneable {
    protected struct HashItem : IComparable<HashItem>, IEquatable<HashItem> {
      public THashType Value { get; private set; }
      public Symbol Symbol { get; private set; }

      public int CompareTo(HashItem other) {
        var res = Symbol.CompareTo(other.Symbol);
        return res == 0 ? Comparer<THashType>.Default.Compare(Value, other.Value) : res;
      }

      private HashItem(THashType h, Symbol s) {
        Value = h;
        Symbol = s;
      }

      public static HashItem Create(THashType h, Symbol s) {
        return new HashItem(h, s);
      }

      public bool Equals(HashItem other) {
        return Symbol.Equals(other.Symbol) && Value.Equals(other.Value);
      }
    }
    protected Hasher(Grammar grammar) {
      Grammar = grammar;
    }

    protected Hasher(Hasher<THashType> original, Cloner cloner) : base(original, cloner) {
      Grammar = cloner.Clone(original.Grammar);
    }

    [Storable]
    protected Grammar Grammar { get; private set; }

    protected abstract HashItem AggregateHashes(Symbol operatorSym, IList<HashItem> hashes);

    public int CalcHashCode(SymbolList 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)).Value.GetHashCode();
    }

    [StorableConstructor]
    protected Hasher(bool deserializing) { }

    private IList<HashItem> 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.Inv) {
        // Directly aggregate the single subtree
        return new[] { AggregateHashes(currentSymbol, GetSubtreeHashes(parseStack)) };
      }

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

    private void AddAdditionChildHashes(HashSet<HashItem> hashSet, Stack<Symbol> symbolStack) {
      var peek = symbolStack.Peek();
      var hashes = GetSubtreeHashes(symbolStack); // will pop the stack

      if (peek == Grammar.Addition)
        hashSet.UnionWith(hashes);
      else
        hashSet.Add(AggregateHashes(peek, hashes));
    }

    private IList<HashItem> GetAdditionSubtreeHashes(Stack<Symbol> parseStack) {
      var uniqueChildHashes = new HashSet<HashItem>();

      AddAdditionChildHashes(uniqueChildHashes, parseStack); // first child 
      AddAdditionChildHashes(uniqueChildHashes, parseStack); // second child 

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

    private void AddMultiplicationChildHashes(List<HashItem> hashList, Stack<Symbol> symbolStack) {
      var peek = symbolStack.Peek();
      var hashes = GetSubtreeHashes(symbolStack);
      if (peek == Grammar.Multiplication)
        hashList.AddRange(hashes);
      else
        hashList.Add(AggregateHashes(peek, hashes));
    }

    private IList<HashItem> GetMultiplicationSubtreeHashes(Stack<Symbol> parseStack) {
      var childHashes = new List<HashItem>();

      AddMultiplicationChildHashes(childHashes, parseStack); // first child
      AddMultiplicationChildHashes(childHashes, parseStack); // second child

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

      if (childHashes.Count <= 2)
        return childHashes;

      // Cancel out inverse factors.
      var isInvFactor = new bool[childHashes.Count];
      bool foundInvFactor = false;
      for (int i = 0; i < isInvFactor.Length; i++) {
        if (isInvFactor[i]) continue;

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

        int indexOfInv = childHashes.IndexOf(invFactor);
        if (indexOfInv >= 0 && !isInvFactor[indexOfInv]) {
          isInvFactor[i] = isInvFactor[indexOfInv] = true;
          foundInvFactor = true;
        }
      }

      if (!foundInvFactor)
        return childHashes;

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

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

    public IntHasher(IntHasher original, Cloner cloner) : base(original, cloner) { }

    public override IDeepCloneable Clone(Cloner cloner) {
      return new IntHasher(this, cloner);
    }

    [StorableConstructor]
    protected IntHasher(bool deserializing) : base(deserializing) { }

    protected override HashItem AggregateHashes(Symbol operatorSym, IList<HashItem> hashes) {
      int start;
      if ((operatorSym == Grammar.Addition || operatorSym == Grammar.Multiplication) && hashes.Count <= 1) {
        start = 0;

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

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

      for (int i = 0; i < hashes.Count; i++) {
        start = ((start << 5) + start) ^ hashes[i].Value;
      }
      return HashItem.Create(start, operatorSym);
    }
  }

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

    public StringHasher(StringHasher original, Cloner cloner) : base(original, cloner) { }

    public override IDeepCloneable Clone(Cloner cloner) {
      return new StringHasher(this, cloner);
    }

    [StorableConstructor]
    protected StringHasher(bool deserializing) : base(deserializing) { }

    protected override HashItem AggregateHashes(Symbol operatorSym, IList<HashItem> 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 HashItem.Create(operatorSym.StringRepresentation, operatorSym);
      }

      return HashItem.Create($"[{operatorSym.StringRepresentation} ° {string.Join(" ° ", hashesArray.Select(x => x.Value))}]", operatorSym);
    }
  }
}