source: branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/SymbolicExpressionTreeMatching.cs @ 7792

using System.Collections.Generic;
using System.Linq;
using HeuristicLab.Problems.DataAnalysis.Symbolic;

namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
  public class SymbolicExpressionTreeNodeComparer : IEqualityComparer<ISymbolicExpressionTreeNode> {

    public SymbolicExpressionTreeNodeComparer(int similarityLevel) {
      _similarityLevel = similarityLevel;
    }

    public int GetHashCode(ISymbolicExpressionTreeNode n) {
      return n.ToString().ToLower().GetHashCode();
    }

    public bool Equals(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
      if (a.SubtreeCount != b.SubtreeCount) { return false; }
      if (a.SubtreeCount > 0) { return a.Symbol.ToString().Equals(b.Symbol.ToString()); }
      // compare leaf nodes according to desired similarity level
      switch (_similarityLevel) {
        case ((int)SymbolicExpressionTreeMatching.SimilarityLevel.Exact):
          if (a is ConstantTreeNode && b is ConstantTreeNode) {
            return ((ConstantTreeNode)a).Value.Equals(((ConstantTreeNode)b).Value);
          }
          if (a is VariableTreeNode && b is VariableTreeNode) {
            return (a as VariableTreeNode).Weight.Equals((b as VariableTreeNode).Weight);
          }
          return false;
        case ((int)SymbolicExpressionTreeMatching.SimilarityLevel.High):
          return (a is ConstantTreeNode && b is ConstantTreeNode) || (a is VariableTreeNode && b is VariableTreeNode);
        case ((int)SymbolicExpressionTreeMatching.SimilarityLevel.Relaxed):
          return true;
        default:
          return false;
      }
    }

    private readonly int _similarityLevel;
  }

  // tree equality
  public class SymbolicExpressionTreeComparer : IEqualityComparer<ISymbolicExpressionTree> {
    public bool Equals(ISymbolicExpressionTree a, ISymbolicExpressionTree b) {
      return SymbolicExpressionTreeMatching.FindMatch(a, b, _mode) == 0;
    }

    public int GetHashCode(ISymbolicExpressionTree tree) {
      return tree.Length;
    }

    private int _mode;
    public void SetComparisonMode(int mode) {
      _mode = mode;
    }
  }

  public static class SymbolicExpressionTreeMatching {
    public enum SimilarityLevel {
      Exact,   // everything is matched bit by bit (functions and terminals)
      High,    // symbols are matched. leaf node types are matched
      Relaxed  // only symbols are matched, leafs count as wildcards
    }

    public static bool IsSimilarTo(this ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, int mode) {
      return FindMatch(t1, t2, mode) == 0;
    }
    public static bool IsSimilarTo(this ISymbolicExpressionTreeNode t1, ISymbolicExpressionTreeNode t2, int mode) {
      return FindMatch(t1, t2, mode) == 0;
    }

    public static bool ContainsFragment(this ISymbolicExpressionTree tree, ISymbolicExpressionTreeNode fragment, int mode) {
      var nodes = tree.IterateNodesBreadth() as List<ISymbolicExpressionTreeNode>;
      var fragments = fragment.IterateNodesBreadth() as List<ISymbolicExpressionTreeNode>;
      return FindMatch(nodes, fragments, mode) != -1;
    }

    // convenience methods for less typing :)
    private static IEnumerator<ISymbolicExpressionTreeNode> Enumerator(this ISymbolicExpressionTree tree) {
      return tree.IterateNodesBreadth().GetEnumerator();
    }
    private static IEnumerator<ISymbolicExpressionTreeNode> Enumerator(this ISymbolicExpressionTreeNode tree) {
      return tree.IterateNodesBreadth().GetEnumerator();
    }
    public static int FindMatch(ISymbolicExpressionTree a, ISymbolicExpressionTree b, int mode) {
      var nodesA = a.IterateNodesBreadth() as List<ISymbolicExpressionTreeNode>;
      var nodesB = b.IterateNodesBreadth() as List<ISymbolicExpressionTreeNode>;
      return FindMatch(nodesA, nodesB, mode);
    }
    public static int FindMatch(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, int mode) {
      var nodesA = a.IterateNodesBreadth() as List<ISymbolicExpressionTreeNode>;
      var nodesB = b.IterateNodesBreadth() as List<ISymbolicExpressionTreeNode>;
      return FindMatch(nodesA, nodesB, mode);
    }
    // returns the index in the sequence 'seq', where pattern 'pat' is matched, or -1 for no match
    // -1 means no match, 0 means perfect match (the sequences overlap, hence the match index is 0)
    public static int FindMatch(List<ISymbolicExpressionTreeNode> seq, List<ISymbolicExpressionTreeNode> pat, int mode) {
      int patlen = pat.Count;
      int seqlen = seq.Count;
      if (patlen == 0 || seqlen == 0) return -1;
      var comparer = new SymbolicExpressionTreeNodeComparer(mode);
      if (patlen == seqlen) return seq.SequenceEqual(pat, comparer) ? 0 : -1;
      for (int i = patlen; i <= seqlen; ++i) {
        if (comparer.Equals(seq[i - 1], pat.Last())) // first check if last element is a match
          if (seq.Skip(i - patlen).Take(patlen).SequenceEqual(pat, comparer)) // then check the whole sequence
            return i - patlen;
      }
      return -1;
    }
  }
}