View Javadoc
1   /**
2    * BSD-style license; for more info see http://pmd.sourceforge.net/license.html
3    */
4   package net.sourceforge.pmd.cpd;
5   
6   import java.util.ArrayList;
7   import java.util.Collections;
8   import java.util.List;
9   import java.util.Map;
10  import java.util.TreeMap;
11  
12  public class MatchCollector {
13      private List<Match> matchList = new ArrayList<Match>();
14      private Map<Integer, Map<Integer, Match>> matchTree = new TreeMap<Integer, Map<Integer, Match>>();
15      private MatchAlgorithm ma;
16  
17      public MatchCollector(MatchAlgorithm ma) {
18          this.ma = ma;
19      }
20  
21      public void collect(List<TokenEntry> marks) {
22          //first get a pairwise collection of all maximal matches
23          for (int i = 0; i < marks.size() - 1; i++) {
24              TokenEntry mark1 = marks.get(i);
25              for (int j = i + 1; j < marks.size(); j++) {
26                  TokenEntry mark2 = marks.get(j);
27                  int diff = mark1.getIndex() - mark2.getIndex();
28                  if (-diff < ma.getMinimumTileSize()) {
29                      continue;
30                  }
31                  if (hasPreviousDupe(mark1, mark2)) {
32                      continue;
33                  }
34  
35                  // "match too small" check
36                  int dupes = countDuplicateTokens(mark1, mark2);
37                  if (dupes < ma.getMinimumTileSize()) {
38                      continue;
39                  }
40                  // is it still too close together
41                  if (diff + dupes >= 1) {
42                      continue;
43                  }
44                  reportMatch(mark1, mark2, dupes);
45              }
46          }
47      }
48  
49      private void reportMatch(TokenEntry mark1, TokenEntry mark2, int dupes) {
50          Map<Integer, Match> matches = matchTree.get(dupes);
51          if (matches == null) {            
52              matches = new TreeMap<Integer, Match>();
53              matchTree.put(dupes, matches);
54              addNewMatch(mark1, mark2, dupes, matches);
55          } else {
56              Match matchA = matchTree.get(dupes).get(mark1.getIndex());
57              Match matchB = matchTree.get(dupes).get(mark2.getIndex());
58  
59              if (matchA == null && matchB == null) {
60                  addNewMatch(mark1, mark2, dupes, matches);
61              } else if(matchA == null) {
62                  matchB.addTokenEntry(mark1);
63                  matches.put(mark1.getIndex(), matchB);
64              } else if(matchB == null) {
65                  matchA.addTokenEntry(mark2);
66                  matches.put(mark2.getIndex(), matchA);
67              }
68          }
69      }
70      
71      private void addNewMatch(TokenEntry mark1, TokenEntry mark2, int dupes, Map<Integer, Match> matches){
72          Match match = new Match(dupes, mark1, mark2);
73          matches.put(mark1.getIndex(), match);
74          matches.put(mark2.getIndex(), match);
75          matchList.add(match);        
76      }
77  
78      @SuppressWarnings("PMD.CompareObjectsWithEquals")
79      public List<Match> getMatches() {
80          Collections.sort(matchList);
81          return matchList;
82      }    
83  
84      private boolean hasPreviousDupe(TokenEntry mark1, TokenEntry mark2) {
85          if (mark1.getIndex() == 0) {
86              return false;
87          }
88          return !matchEnded(ma.tokenAt(-1, mark1), ma.tokenAt(-1, mark2));
89      }
90  
91      private int countDuplicateTokens(TokenEntry mark1, TokenEntry mark2) {
92          int index = 0;
93          while (!matchEnded(ma.tokenAt(index, mark1), ma.tokenAt(index, mark2))) {
94              index++;
95          }
96          return index;
97      }
98  
99      private boolean matchEnded(TokenEntry token1, TokenEntry token2) {
100         return token1.getIdentifier() != token2.getIdentifier() || token1 == TokenEntry.EOF || token2 == TokenEntry.EOF;
101     }
102 }