source: branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolicDataAnalysisExpressionTreeMatching.cs @ 8423

using System.Collections.Generic;
using System.Linq;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;

namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
  public class SymbolicExpressionTreeNodeSimilarityComparer : IEqualityComparer<ISymbolicExpressionTreeNode> {

    public SymbolicExpressionTreeNodeSimilarityComparer(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;
  }

  public class SymbolicExpressionTreeNodeOrderingComparer : IComparer<ISymbolicExpressionTreeNode> {
    public int Compare(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
      if (a is ConstantTreeNode) {
        if (b is ConstantTreeNode)
          return a.Symbol.ToString().Equals(b.Symbol.ToString()) ?
            (a as ConstantTreeNode).Value.CompareTo((b as ConstantTreeNode).Value) : System.String.Compare(a.Symbol.ToString(), b.Symbol.ToString());
        return -1; // if b is not constant then we consider a < b because by convention Constant < Variable < Function
      }
      if (a is VariableTreeNode) {
        if (b is ConstantTreeNode)
          return 1;
        if (b is VariableTreeNode)
          return a.Symbol.ToString().Equals(b.Symbol.ToString()) ?
            (a as VariableTreeNode).Weight.CompareTo((b as VariableTreeNode).Weight) : System.String.Compare(a.Symbol.ToString(), b.Symbol.ToString());
        return -1;
      }
      if (b is ConstantTreeNode || b is VariableTreeNode)
        return 1; // a is a Function node and is greater than Constants or Variables

      return a.Symbol.ToString().Equals(b.Symbol.ToString()) ? a.SubtreeCount.CompareTo(b.SubtreeCount) : System.String.Compare(a.Symbol.ToString(), b.Symbol.ToString());
    }
  }

  // tree equality
  public class SymbolicExpressionTreeEqualityComparer : 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.IterateNodesPostfix() as List<ISymbolicExpressionTreeNode>;
      var fragments = fragment.IterateNodesPostfix() as List<ISymbolicExpressionTreeNode>;
      return FindMatch(nodes, fragments, mode) != -1;
    }

    public static void SortSubtrees(this ISymbolicExpressionTree tree) {
      SortSubtrees(tree.Root);
    }

    public static void SortSubtrees(this ISymbolicExpressionTreeNode node) {
      if (node.SubtreeCount > 0) {
        var subtrees = node.Subtrees as List<ISymbolicExpressionTreeNode>;
        if (subtrees == null) return;
        subtrees.Sort(new SymbolicExpressionTreeNodeOrderingComparer());
        foreach (var subtree in subtrees)
          subtree.SortSubtrees();
      }
    }

    public static int FindMatch(ISymbolicExpressionTree a, ISymbolicExpressionTree b, int mode) {
      var nodesA = a.IterateNodesPostfix() as List<ISymbolicExpressionTreeNode>;
      var nodesB = b.IterateNodesPostfix() as List<ISymbolicExpressionTreeNode>;
      return FindMatch(nodesA, nodesB, mode);
    }
    public static int FindMatch(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, int mode) {
      var nodesA = a.IterateNodesPostfix() as List<ISymbolicExpressionTreeNode>;
      var nodesB = b.IterateNodesPostfix() 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 SymbolicExpressionTreeNodeSimilarityComparer(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;
    }
  }
}