From ae5528042cd2f948cea3e50c32a5426eb302d3f7 Mon Sep 17 00:00:00 2001
From: Evgeny Mandrikov <mandrikov@gmail.com>
Date: Thu, 15 Dec 2011 14:02:49 +0400
Subject: SONAR-3060 Improve new CPD algorithm

* Remove recursive part of algorithm to avoid StackOverflowError
* Fix violations
---
 .../duplications/detector/original/Filter.java     |  3 +-
 .../duplications/detector/suffixtree/Search.java   | 61 ++++++++++++----------
 2 files changed, 33 insertions(+), 31 deletions(-)

(limited to 'sonar-duplications/src/main')

diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/detector/original/Filter.java b/sonar-duplications/src/main/java/org/sonar/duplications/detector/original/Filter.java
index f9e1fecdec9..5c317dbe0ce 100644
--- a/sonar-duplications/src/main/java/org/sonar/duplications/detector/original/Filter.java
+++ b/sonar-duplications/src/main/java/org/sonar/duplications/detector/original/Filter.java
@@ -25,7 +25,6 @@ import java.util.List;
 import org.sonar.duplications.detector.ContainsInComparator;
 import org.sonar.duplications.index.CloneGroup;
 import org.sonar.duplications.index.ClonePart;
-import org.sonar.duplications.utils.FastStringComparator;
 import org.sonar.duplications.utils.SortedListsUtils;
 
 import com.google.common.collect.Lists;
@@ -103,7 +102,7 @@ final class Filter {
    * </p>
    * <p>
    * <strong>Important: this method relies on fact that all parts were already sorted by resourceId and unitStart by using
-   * {@link BlocksGroup.BlockComparator}, which uses {@link FastStringComparator} for comparison by resourceId.</strong>
+   * {@link BlocksGroup.BlockComparator}, which uses {@link org.sonar.duplications.utils.FastStringComparator} for comparison by resourceId.</strong>
    * </p>
    * <p>
    * Running time - O(|A|+|B|).
diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/detector/suffixtree/Search.java b/sonar-duplications/src/main/java/org/sonar/duplications/detector/suffixtree/Search.java
index d0c32f74765..8e5b4e665d1 100644
--- a/sonar-duplications/src/main/java/org/sonar/duplications/detector/suffixtree/Search.java
+++ b/sonar-duplications/src/main/java/org/sonar/duplications/detector/suffixtree/Search.java
@@ -21,14 +21,16 @@ package org.sonar.duplications.detector.suffixtree;
 
 import java.util.*;
 
+import com.google.common.collect.Lists;
+
 public final class Search {
 
   private final SuffixTree tree;
   private final TextSet text;
   private final Collector reporter;
 
-  private final List<Integer> list = new ArrayList<Integer>();
-  private final List<Node> innerNodes = new ArrayList<Node>();
+  private final List<Integer> list = Lists.newArrayList();
+  private final List<Node> innerNodes = Lists.newArrayList();
 
   public static void perform(TextSet text, Collector reporter) {
     new Search(SuffixTree.create(text), text, reporter).compute();
@@ -42,52 +44,53 @@ public final class Search {
 
   private void compute() {
     // O(N)
-    computeDepth();
+    dfs();
 
     // O(N * log(N))
     Collections.sort(innerNodes, DEPTH_COMPARATOR);
 
-    // O(N), recursive
-    createListOfLeafs(tree.getRootNode());
-
     // O(N)
     visitInnerNodes();
   }
 
-  private void computeDepth() {
-    Queue<Node> queue = new LinkedList<Node>();
-    queue.add(tree.getRootNode());
-    tree.getRootNode().depth = 0;
-    while (!queue.isEmpty()) {
-      Node node = queue.remove();
-      if (!node.getEdges().isEmpty()) {
+  private static final Comparator<Node> DEPTH_COMPARATOR = new Comparator<Node>() {
+    public int compare(Node o1, Node o2) {
+      return o2.depth - o1.depth;
+    }
+  };
+
+  /**
+   * Depth-first search (DFS).
+   */
+  private void dfs() {
+    LinkedList<Node> stack = Lists.newLinkedList();
+    stack.add(tree.getRootNode());
+    while (!stack.isEmpty()) {
+      Node node = stack.removeLast();
+      node.startSize = list.size();
+      if (node.getEdges().isEmpty()) { // leaf
+        list.add(node.depth);
+        node.endSize = list.size();
+      } else {
         if (node != tree.getRootNode()) { // inner node = not leaf and not root
           innerNodes.add(node);
         }
         for (Edge edge : node.getEdges()) {
           Node endNode = edge.getEndNode();
           endNode.depth = node.depth + edge.getSpan() + 1;
-          queue.add(endNode);
+          stack.addLast(endNode);
         }
       }
     }
-  }
-
-  private static final Comparator<Node> DEPTH_COMPARATOR = new Comparator<Node>() {
-    public int compare(Node o1, Node o2) {
-      return o2.depth - o1.depth;
-    }
-  };
-
-  private void createListOfLeafs(Node node) {
-    node.startSize = list.size();
-    if (node.getEdges().isEmpty()) { // leaf
-      list.add(node.depth);
-    } else {
+    // At this point all inner nodes are ordered by the time of entering, so we visit them from last to first
+    ListIterator<Node> iterator = innerNodes.listIterator(innerNodes.size());
+    while (iterator.hasPrevious()) {
+      Node node = iterator.previous();
+      int max = -1;
       for (Edge edge : node.getEdges()) {
-        createListOfLeafs(edge.getEndNode());
+        max = Math.max(edge.getEndNode().endSize, max);
       }
-      node.endSize = list.size();
+      node.endSize = max;
     }
   }
 
-- 
cgit v1.2.3