Clover coverage report - PMD - 3.7
Coverage timestamp: Wed May 31 2006 09:25:59 EDT
file stats: LOC: 165   Methods: 7
NCLOC: 143   Classes: 1
 
 Source file Conditionals Statements Methods TOTAL
MatchCollector.java 67.3% 81.6% 100% 77.4%
coverage coverage
 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.HashMap;
 9    import java.util.HashSet;
 10    import java.util.Iterator;
 11    import java.util.List;
 12    import java.util.Map;
 13    import java.util.Set;
 14   
 15    public class MatchCollector {
 16   
 17    private MatchAlgorithm ma;
 18    private Map startMap = new HashMap();
 19    private Map fileMap = new HashMap();
 20   
 21  2 public MatchCollector(MatchAlgorithm ma) {
 22  2 this.ma = ma;
 23    }
 24   
 25  8 public void collect(List marks) {
 26    //first get a pairwise collection of all maximal matches
 27  8 for (int i = 0; i < marks.size() - 1; i++) {
 28  12 TokenEntry mark1 = (TokenEntry) marks.get(i);
 29  12 for (int j = i + 1; j < marks.size(); j++) {
 30  16 TokenEntry mark2 = (TokenEntry) marks.get(j);
 31  16 int diff = mark1.getIndex() - mark2.getIndex();
 32  16 if (-diff < ma.getMinimumTileSize()) {
 33  0 continue;
 34    }
 35  16 if (hasPreviousDupe(mark1, mark2)) {
 36  12 continue;
 37    }
 38   
 39    // "match too small" check
 40  4 int dupes = countDuplicateTokens(mark1, mark2);
 41  4 if (dupes < ma.getMinimumTileSize()) {
 42  0 continue;
 43    }
 44    // is it still too close together
 45  4 if (diff + dupes >= 1) {
 46  0 continue;
 47    }
 48  4 determineMatch(mark1, mark2, dupes);
 49    }
 50    }
 51    }
 52   
 53  2 public List getMatches() {
 54  2 List matchList = new ArrayList(startMap.values());
 55  2 Collections.sort(matchList);
 56  2 Set matchSet = new HashSet();
 57  2 Match.MatchCode matchCode = new Match.MatchCode();
 58  2 for (int i = matchList.size(); i > 1; i--) {
 59  1 Match match1 = (Match) matchList.get(i - 1);
 60  1 TokenEntry mark1 = (TokenEntry) match1.getMarkSet().iterator().next();
 61  1 matchSet.clear();
 62  1 matchSet.add(match1.getMatchCode());
 63  1 for (int j = i - 1; j > 0; j--) {
 64  2 Match match2 = (Match) matchList.get(j - 1);
 65  2 if (match1.getTokenCount() != match2.getTokenCount()) {
 66  0 break;
 67    }
 68  2 TokenEntry mark2 = null;
 69  3 for (Iterator iter = match2.getMarkSet().iterator(); iter.hasNext();) {
 70  3 mark2 = (TokenEntry) iter.next();
 71  3 if (mark2 != mark1) {
 72  2 break;
 73    }
 74    }
 75  2 int dupes = countDuplicateTokens(mark1, mark2);
 76  2 if (dupes < match1.getTokenCount()) {
 77  0 break;
 78    }
 79  2 matchSet.add(match2.getMatchCode());
 80  2 match1.getMarkSet().addAll(match2.getMarkSet());
 81  2 matchList.remove(i - 2);
 82  2 i--;
 83    }
 84  1 if (matchSet.size() == 1) {
 85  0 continue;
 86    }
 87    //prune the mark set
 88  1 Set pruned = match1.getMarkSet();
 89  1 boolean done = false;
 90  1 ArrayList a1 = new ArrayList(match1.getMarkSet());
 91  1 Collections.sort(a1);
 92  1 for (int outer = 0; outer < a1.size() - 1 && !done; outer++) {
 93  2 TokenEntry cmark1 = (TokenEntry) a1.get(outer);
 94  2 for (int inner = outer + 1; inner < a1.size() && !done; inner++) {
 95  3 TokenEntry cmark2 = (TokenEntry) a1.get(inner);
 96  3 matchCode.setFirst(cmark1.getIndex());
 97  3 matchCode.setSecond(cmark2.getIndex());
 98  3 if (!matchSet.contains(matchCode)) {
 99  0 if (pruned.size() > 2) {
 100  0 pruned.remove(cmark2);
 101    }
 102  0 if (pruned.size() == 2) {
 103  0 done = true;
 104    }
 105    }
 106    }
 107    }
 108    }
 109  2 return matchList;
 110    }
 111   
 112    /**
 113    * A greedy algorithm for determining non-overlapping matches
 114    */
 115  4 private void determineMatch(TokenEntry mark1, TokenEntry mark2, int dupes) {
 116  4 Match match = new Match(dupes, mark1, mark2);
 117  4 String fileKey = mark1.getTokenSrcID() + mark2.getTokenSrcID();
 118  4 List pairMatches = (ArrayList) fileMap.get(fileKey);
 119  4 if (pairMatches == null) {
 120  2 pairMatches = new ArrayList();
 121  2 fileMap.put(fileKey, pairMatches);
 122    }
 123  4 boolean add = true;
 124  4 for (int i = 0; i < pairMatches.size(); i++) {
 125  3 Match other = (Match) pairMatches.get(i);
 126  3 if (other.getFirstMark().getIndex() + other.getTokenCount() - mark1.getIndex()
 127    > 0) {
 128  1 boolean ordered = other.getSecondMark().getIndex() - mark2.getIndex() < 0;
 129  1 if ((ordered && (other.getEndIndex() - mark2.getIndex() > 0))
 130    || (!ordered && (match.getEndIndex() - other.getSecondMark().getIndex()) > 0)) {
 131  0 if (other.getTokenCount() >= match.getTokenCount()) {
 132  0 add = false;
 133  0 break;
 134    } else {
 135  0 pairMatches.remove(i);
 136  0 startMap.remove(other.getMatchCode());
 137    }
 138    }
 139    }
 140    }
 141  4 if (add) {
 142  4 pairMatches.add(match);
 143  4 startMap.put(match.getMatchCode(), match);
 144    }
 145    }
 146   
 147  16 private boolean hasPreviousDupe(TokenEntry mark1, TokenEntry mark2) {
 148  16 if (mark1.getIndex() == 0) {
 149  0 return false;
 150    }
 151  16 return !matchEnded(ma.tokenAt(-1, mark1), ma.tokenAt(-1, mark2));
 152    }
 153   
 154  6 private int countDuplicateTokens(TokenEntry mark1, TokenEntry mark2) {
 155  6 int index = 0;
 156  6 while (!matchEnded(ma.tokenAt(index, mark1), ma.tokenAt(index, mark2))) {
 157  48 index++;
 158    }
 159  6 return index;
 160    }
 161   
 162  70 private boolean matchEnded(TokenEntry token1, TokenEntry token2) {
 163  70 return token1.getIdentifier() != token2.getIdentifier() || token1 == TokenEntry.EOF || token2 == TokenEntry.EOF;
 164    }
 165    }