source: branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/QueryMatch.cs @ 12933

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2015 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.Linq;
using System.Text;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;

namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
  // this class implements the decision version of the tree pattern query matching algorithm 
  // by M. Götz, C. Koch and W. Martens in http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.182.5440
  public class QueryMatch {
    private List<NodeInfo> dNodes;
    private List<NodeInfo> qNodes;
    private readonly ISymbolicExpressionTreeNodeEqualityComparer comparer;

    private QueryMatch() { }

    private readonly Stack<string> stack = new Stack<string>();

    public string Trace {
      get {
        var sb = new StringBuilder();
        while (stack.Count > 0)
          sb.Append(stack.Pop());
        return sb.ToString();
      }
    }

    // whether matching nodes should also have matching parents
    // in theory, this restricts the matching so that parent-child
    // pairs in the query tree are matched by parent-child pairs in 
    // the data tree (and not ancestor-descendant pairs)
    public bool MatchParents { get; set; }

    public QueryMatch(ISymbolicExpressionTreeNodeEqualityComparer comparer) {
      this.comparer = comparer;
    }

    public bool Match(ISymbolicExpressionTreeNode data, ISymbolicExpressionTreeNode query) {
      stack.Clear();
      dNodes = InitializePostOrder(data);
      qNodes = InitializePostOrder(query);

      var dRoot = dNodes.Last();
      var qRoot = qNodes.Last();
      var result = Tmatch(dRoot, qNodes.First(), qNodes.Last());
      return result == qRoot;
    }

    private List<NodeInfo> InitializePostOrder(ISymbolicExpressionTreeNode node) {
      var list = node.IterateNodesPostfix().Select((x, i) => new NodeInfo(x, i)).ToList();
      foreach (var l in list)
        l.Nodes = list;

      return list;
    }

    private bool AreMatching(NodeInfo a, NodeInfo b) {
      bool equals = comparer.Equals(a.Node, b.Node);

      if (equals && MatchParents) {
        var pa = a.Parent();
        var pb = b.Parent();
        if (pa != null && pb != null)
          return comparer.Equals(pa.Node, pb.Node);
        if (!(pa == null && pb == null))
          return false;
      }
      return equals;
    }

    private NodeInfo Tmatch(NodeInfo d, NodeInfo qFrom, NodeInfo qUntil, int tab = 0) {
#if DEBUG
      var sb = new StringBuilder();
#endif
      NodeInfo qBest = d.IsLeaf ? qFrom.Previous() : Hmatch(d.LastChild(), qFrom, qUntil, tab + 1);

      var next = qBest.Next();
      if (next.Index <= qUntil.Index && AreMatching(d, next)) {
        qBest = next;
        next = qBest.Next();
        var lastSibling = qBest.LastSibling();
        var result = next.Index <= lastSibling.Index ? Tmatch(d, next, lastSibling, tab + 1) : qBest;
#if DEBUG
        for (int i = 0; i < tab; ++i)
          sb.Append("\t");
        sb.AppendLine(string.Format("TM(d{0}, q{1}, q{2}) => q{3}", d.Index, qFrom.Index, qUntil.Index, result.Index));
        stack.Push(sb.ToString());
#endif
        return result;
      }
#if DEBUG
      for (int i = 0; i < tab; ++i)
        sb.Append("\t");
      sb.AppendLine(string.Format("TM(d{0}, q{1}, q{2}) => q{3}", d.Index, qFrom.Index, qUntil.Index, qBest.Index));
      stack.Push(sb.ToString());
#endif
      return qBest;
    }

    private NodeInfo Hmatch(NodeInfo d, NodeInfo qFrom, NodeInfo qUntil, int tab = 0) {
#if DEBUG
      var sb = new StringBuilder();
#endif
      if (d.IsFirstSibling) {
        var result = Tmatch(d, qFrom, qUntil, tab + 1);
#if DEBUG
        for (int i = 0; i < tab; ++i)
          sb.Append("\t");
        sb.AppendLine(string.Format("HM(d{0}, q{1}, q{2}) => q{3}", d.Index, qFrom.Index, qUntil.Index, result.Index));
        stack.Push(sb.ToString());
#endif
        return result;
      }

      var qHedge = Hmatch(d.PreviousSibling(), qFrom, qUntil, tab + 1);
      var qTree = Tmatch(d, qFrom, qUntil, tab + 1);

      for (;;) {
        if (qHedge == qTree) {
#if DEBUG
          for (int i = 0; i < tab; ++i)
            sb.Append("\t");
          sb.AppendLine(string.Format("HM(d{0}, q{1}, q{2}) => q{3}", d.Index, qFrom.Index, qUntil.Index, qHedge.Index));
          stack.Push(sb.ToString());
#endif
          return qHedge;
        }
        if (qTree.Index < qHedge.Index) {
          var rtop = Rtop(qTree.Next(), qHedge, tab);
          while (rtop.Index < qHedge.Next().Index && qHedge.Index < rtop.LastSibling().Index) {
            qTree = Tmatch(d, rtop.Next(), rtop.LastSibling(), tab + 1);
            rtop = Rtop(qTree.Next(), qHedge, tab);
          }
          if (qTree.Index <= qHedge.Index) {
#if DEBUG
            for (int i = 0; i < tab; ++i)
              sb.Append("\t");
            sb.AppendLine(string.Format("HM(d{0}, q{1}, q{2}) => q{3}", d.Index, qFrom.Index, qUntil.Index, qHedge.Index));
            stack.Push(sb.ToString());
#endif
            return qHedge;
          }
        } else {
          var rtop = Rtop(qHedge.Next(), qTree, tab);
          while (rtop.Index < qTree.Next().Index && qTree.Index < rtop.LastSibling().Index) {
            qHedge = Hmatch(d.PreviousSibling(), rtop.Next(), rtop.LastSibling(), tab + 1);
            rtop = Rtop(qHedge.Next(), qTree, tab);
          }
          if (qHedge.Index <= qTree.Index) {
#if DEBUG
            for (int i = 0; i < tab; ++i)
              sb.Append("\t");
            sb.AppendLine(string.Format("HM(d{0}, q{1}, q{2}) => q{3}", d.Index, qFrom.Index, qUntil.Index, qTree.Index));
            stack.Push(sb.ToString());
#endif
            return qTree;
          }
        }
      }
    }

    // returns the rightmost node from the topmost nodes in the interval [hFrom, hUntil]
    private NodeInfo Rtop(NodeInfo hFrom, NodeInfo hUntil, int tab = 0) {
#if DEBUG
      var sb = new StringBuilder();
      for (int i = 0; i < tab; ++i)
        sb.Append("\t");
      sb.Append(string.Format("Rtop(q{0}, q{1})", hFrom.Index, hUntil.Index));
#endif

      if (hFrom == hUntil) {
#if DEBUG
        sb.AppendLine(string.Format(" => q{0}", hUntil.Index));
        stack.Push(sb.ToString());
#endif
        return hUntil;
      }

      if (hFrom.Nodes != hUntil.Nodes)
        throw new ArgumentException("hFrom and hUntil must belong to the same tree/hedge");


      NodeInfo rtop = null;
      if (hFrom.Index > hUntil.Index) {
        rtop = hFrom.Next(); // or return inf (inf is defined in the paper as the successor of the largest node in the hedge)
#if DEBUG
        sb.AppendLine(string.Format(" => q{0}", rtop.Index));
        stack.Push(sb.ToString());
#endif
        return rtop;
      }

      // let u be the highest ancestor of hUntil that has a previous sibling s such that s >= hFrom
      // if no such u exists, then Rtop(hFrom, hUntil) = hUntil. Otherwise, rtop(hFrom, hUntil) = s
      var p = hUntil.Parent();
      if (p == null)
        return hUntil;
      List<NodeInfo> ancestors = hUntil.Ancestors().ToList();
      // ancestors list is ordered in decreasing depth therefore we start from the end
      for (int i = ancestors.Count - 1; i >= 0; --i) {
        var s = ancestors[i].PreviousSibling();
        if (s.Index >= hFrom.Index) {
          rtop = s;
          break;
        }
      }
      if (rtop == null)
        rtop = hUntil;
#if DEBUG
      sb.AppendLine(string.Format(" => q{0}", rtop.Index));
      stack.Push(sb.ToString());
#endif
      return rtop;
    }

    private class NodeInfo {
      private NodeInfo() { }

      public NodeInfo(ISymbolicExpressionTreeNode n, int i) {
        Node = n;
        Index = i;
      }

      public List<NodeInfo> Nodes { get; set; }
      public ISymbolicExpressionTreeNode Node { get; }
      public int Index { get; }

      public bool IsLeaf {
        get { return Node.SubtreeCount == 0; }
      }

      public bool IsFirstSibling {
        get { return this.Node == this.Node.Parent.Subtrees.First(); }
      }

      public IEnumerable<NodeInfo> Ancestors() {
        var p = Parent();
        while (p != null) {
          yield return p;
          p = p.Parent();
        }
      }

      public NodeInfo Parent() {
        var p = Node.Parent;
        if (p == null || p.Symbol is StartSymbol)
          return null;
        var index = Index + 1;
        for (int i = p.SubtreeCount - 1; i >= 0; --i) {
          var subtree = p.GetSubtree(i);
          if (subtree == Node)
            break;
          index += subtree.GetLength();
        }
        return Nodes[index];
      }

      public NodeInfo Next() {
        if (this == Nodes.Last())
          return new NodeInfo(null, int.MaxValue) { Nodes = Nodes };
        return Nodes[Index + 1];
      }

      public NodeInfo NextSibling() {
        if (Node.Parent == null || Node == Node.Parent.Subtrees.Last())
          return new NodeInfo(null, -1);

        var s = Node.Parent.GetSubtree(Node.Parent.IndexOfSubtree(Node) + 1);
        var nextSibling = Nodes[Index + s.GetLength()];
        return nextSibling;
      }

      public NodeInfo LastSibling() {
        if (Node.Parent == null)
          return new NodeInfo(null, -1);

        var last = Node.Parent.Subtrees.Last();
        if (this.Node == last)
          return this;

        var n = this;
        while (n.Node != last)
          n = n.NextSibling();
        return n;
      }

      public NodeInfo Previous() {
        if (this == Nodes.First())
          return new NodeInfo(null, -1) { Nodes = Nodes }; // return nil

        return Nodes[Index - 1];
      }

      public NodeInfo PreviousSibling() {
        if (Node.Parent == null || Node == Node.Parent.Subtrees.First())
          return new NodeInfo(null, -1) { Nodes = Nodes };
        var previousSibling = Nodes[Index - Node.GetLength()];
        return previousSibling;
      }

      public NodeInfo LastChild() {
        var nil = new NodeInfo(null, -1);
        if (IsLeaf)
          return nil;
        return Previous();
      }
    }
  }
}