Changeset 14326

Timestamp:

10/07/16 00:04:21 (8 years ago)

Author:

bburlacu

Message:

#1772: Refactor QueryMatch class to make the code more readable and easier to understand.

File:

• branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/QueryMatch.cs (modified) (9 diffs)

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/QueryMatch.cs

@@ -20 +20 @@
 #endregion
 
+using System;
 using System.Collections.Generic;
 using System.Linq;
@@ -28 +29 @@
   // 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 {
-    public ISymbolicExpressionTreeNodeEqualityComparer Comparer { get; }
+    public ISymbolicExpressionTreeNodeEqualityComparer Comparer { get; private set; }
+    private readonly NodeInfo Inf = new NodeInfo { Index = int.MaxValue };
+    private readonly NodeInfo Nil = new NodeInfo { Index = -1 };
 
     private QueryMatch() { }
@@ -39 +42 @@
 
     public QueryMatch(ISymbolicExpressionTreeNodeEqualityComparer comparer) {
-      this.Comparer = comparer;
+      Comparer = comparer;
     }
 
@@ -93 +96 @@
 
     private NodeInfo Tmatch(NodeInfo d, NodeInfo qFrom, NodeInfo qUntil) {
-      NodeInfo qBest = d.IsLeaf ? qFrom.Previous : Hmatch(d.LastChild, qFrom, qUntil);
+      var qBest = d.IsLeaf ? qFrom.Previous : Hmatch(d.LastChild, qFrom, qUntil);
       var next = qBest.Next;
-      if (next.Index <= qUntil.Index && AreMatching(d, next)) {
+      if (next <= qUntil && AreMatching(d, next)) {
         qBest = next;
         next = qBest.Next;
         var lastSibling = qBest.LastSibling;
-        return next.Index <= lastSibling.Index ? Tmatch(d, next, lastSibling) : qBest;
+        return next <= lastSibling ? Tmatch(d, next, lastSibling) : qBest;
       }
       return qBest;
@@ -114 +117 @@
         if (qHedge == qTree)
           return qHedge;
-        if (qTree.Index < qHedge.Index) {
+        if (qTree < qHedge) {
           var rtop = Rtop(qTree.Next, qHedge);
-          while (rtop.Index < int.MaxValue && qHedge.Index < rtop.LastSibling.Index) {
+          while (rtop < Inf && qHedge < rtop.LastSibling) {
             qTree = Tmatch(d, rtop.Next, rtop.LastSibling);
             rtop = Rtop(qTree.Next, qHedge);
           }
-          if (qTree.Index <= qHedge.Index)
+          if (qTree <= qHedge)
             return qHedge;
         } else {
           var rtop = Rtop(qHedge.Next, qTree);
-          while (rtop.Index < int.MaxValue && qTree.Index < rtop.LastSibling.Index) {
+          while (rtop < Inf && qTree < rtop.LastSibling) {
             qHedge = Hmatch(d.PreviousSibling, rtop.Next, rtop.LastSibling);
             rtop = Rtop(qHedge.Next, qTree);
           }
-          if (qHedge.Index <= qTree.Index)
+          if (qHedge <= qTree)
             return qTree;
         }
@@ -134 +137 @@
     }
 
-    // returns the rightmost node from the topmost nodes in the interval [hFrom, hUntil]
+    /// <summary>
+    /// Description from Götz et al. - Efficient Algorithms for Descendant-only Tree Pattern Queries, 2009:
+    /// Given two nodes hFrom and hUntil, returns the rightmost node among the topmost nodes in the interval [hFrom, hUntil]
+    /// More formally, Rtop(hFrom,hUntil) is the node u such that depth(u) is minimal and u is larger than every other node v 
+    /// in [hFrom, hUntil] with depth(u)==depth(v).
+    /// </summary>
+    /// <param name="hFrom">The interval start</param>
+    /// <param name="hUntil">The interval end</param>
+    /// <returns>The rightmost node from the topmost nodes in the interval [hFrom, hUntil]</returns>
     private NodeInfo Rtop(NodeInfo hFrom, NodeInfo hUntil) {
       if (hFrom == hUntil)
         return hUntil;
       if (hFrom.Index > hUntil.Index)
-        return new NodeInfo { Node = null, Index = int.MaxValue };
+        return Inf;
       // 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
-      NodeInfo rtop = null;
-      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) {
-        if (ancestors[i].Parent == null || ancestors[i].IsFirstSibling)
-          continue;
-        var s = ancestors[i].PreviousSibling;
-        if (s != null && s.Index >= hFrom.Index) {
-          rtop = s;
-          break;
-        }
-      }
+      var rtop = hUntil.Ancestors.OrderBy(x => x.Level).Select(x => x.PreviousSibling).FirstOrDefault(x => x != null && x >= hFrom);
       return rtop ?? hUntil;
     }
 
     internal static List<NodeInfo> InitializePostOrder(ISymbolicExpressionTreeNode node) {
+      // levels will be computed below
       var nodes = node.IterateNodesPostfix().Select((x, i) => new NodeInfo { Node = x, Index = i, Level = 0 }).ToList();
       var map = nodes.ToDictionary(x => x.Node, x => x);
-
-      var inf = new NodeInfo { Node = null, Index = int.MaxValue, Previous = nodes.Last() };
-      var nil = new NodeInfo { Node = null, Index = -1, Next = nodes.First() };
-
+      nodes.First().Previous = new NodeInfo { Node = null, Index = -1, Next = nodes.First() };
+      nodes.Last().Next = new NodeInfo { Node = null, Index = int.MaxValue, Previous = nodes.Last() };
       for (int i = nodes.Count - 1; i >= 0; --i) {
         var n = nodes[i];
-        n.Parent = n.Node.Parent != null && map.ContainsKey(n.Node.Parent) ? map[n.Node.Parent] : null;
-        n.Level = n.Parent?.Level + 1 ?? -1;
-        n.Next = n == nodes.Last() ? inf : nodes[n.Index + 1];
-        n.Previous = n == nodes.First() ? nil : nodes[n.Index - 1];
+        if (n != nodes.Last()) n.Next = nodes[n.Index + 1];
+        if (n != nodes.First()) n.Previous = nodes[n.Index - 1];
+        NodeInfo parentInfo;
+        map.TryGetValue(n.Node.Parent, out parentInfo);
+        n.Parent = parentInfo;
         if (n.Parent == null) {
-          n.PreviousSibling = n.NextSibling = null;
-          n.LastSibling = nil;
+          n.PreviousSibling = n.NextSibling = n.LastSibling = null;
         } else {
           var parent = n.Parent.Node;
@@ -179 +178 @@
           n.NextSibling = n.IsLastSibling ? null : map[parent.GetSubtree(si + 1)];
           n.LastSibling = map[parent.Subtrees.Last()];
+          n.Level = n.Parent.Level + 1;
         }
         n.LastChild = n.IsLeaf ? null : n.Previous;
@@ -186 +186 @@
   }
 
-  internal class NodeInfo {
+  /// <summary>
+  /// NodeInfo objects are useful for keeping sibling, parent, index and depth information for tree nodes
+  /// </summary>
+  internal class NodeInfo : IComparable<NodeInfo> {
     public ISymbolicExpressionTreeNode Node { get; set; }
     public int Index { get; set; }
@@ -219 +222 @@
       }
     }
+
+    public int CompareTo(NodeInfo other) {
+      return other == null ? 1 : Index.CompareTo(other.Index);
+    }
+
+    public static bool operator <(NodeInfo lsh, NodeInfo rhs) {
+      return lsh.CompareTo(rhs) == -1;
+    }
+
+    public static bool operator >(NodeInfo lhs, NodeInfo rhs) {
+      return lhs.CompareTo(rhs) == 1;
+    }
+
+    public static bool operator <=(NodeInfo lhs, NodeInfo rhs) {
+      return lhs.CompareTo(rhs) <= 0;
+    }
+
+    public static bool operator >=(NodeInfo lhs, NodeInfo rhs) {
+      return lhs.CompareTo(rhs) >= 0;
+    }
   }
 }