Coverage Report - com.puppycrawl.tools.checkstyle.checks.duplicates.ChecksumInfo
 
Classes in this File Line Coverage Branch Coverage Complexity
ChecksumInfo
100%
58/58
100%
30/30
5.25
 
 1   
 ////////////////////////////////////////////////////////////////////////////////
 2   
 // checkstyle: Checks Java source code for adherence to a set of rules.
 3   
 // Copyright (C) 2001-2014  Oliver Burn
 4   
 //
 5   
 // This library is free software; you can redistribute it and/or
 6   
 // modify it under the terms of the GNU Lesser General Public
 7   
 // License as published by the Free Software Foundation; either
 8   
 // version 2.1 of the License, or (at your option) any later version.
 9   
 //
 10   
 // This library is distributed in the hope that it will be useful,
 11   
 // but WITHOUT ANY WARRANTY; without even the implied warranty of
 12   
 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 13   
 // Lesser General Public License for more details.
 14   
 //
 15   
 // You should have received a copy of the GNU Lesser General Public
 16   
 // License along with this library; if not, write to the Free Software
 17   
 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 18   
 ////////////////////////////////////////////////////////////////////////////////
 19   
 package com.puppycrawl.tools.checkstyle.checks.duplicates;
 20   
 
 21   
 import java.util.Arrays;
 22   
 
 23   
 /**
 24   
  * Helper class for {@link StrictDuplicateCodeCheck},
 25   
  * provides block checksum information for a single file.
 26   
  *
 27   
  * @author lkuehne
 28   
  */
 29   
 final class ChecksumInfo
 30   
 {
 31   
     /**
 32   
      * Helper value to avoid object allocations in
 33   
      * {@link #hasChecksumOverlapsWith(ChecksumInfo)}.
 34   
      */
 35  1 
     private static final int[] NO_LINES = new int[0];
 36   
 
 37   
     /**
 38   
      * Holds the checksums from the constructor call,
 39   
      * except {@link StrictDuplicateCodeCheck#IGNORE}, sorted.
 40   
      */
 41   
     private int[] mSortedChecksums;
 42   
 
 43   
     /**
 44   
      * Reverse mapping from {@link #mSortedChecksums} to the checksums
 45   
      * from the constructor call.
 46   
      *
 47   
      * <code>mSortedRelevantChecksums[i] == checksums[mOrigIdx[i]]</code>
 48   
      */
 49   
     private int[] mOrigIdx;
 50   
 
 51   
     /**
 52   
      * Creates a new ChecksumInfo.
 53   
      *
 54   
      * @param aBlockChecksums the block checksums as caculated by
 55   
      * the {@link StrictDuplicateCodeCheck}.ChecksumGenerator
 56   
      */
 57   
     ChecksumInfo(int[] aBlockChecksums)
 58  6 
     {
 59  6 
         final int csLen = aBlockChecksums.length;
 60  6 
         final int[] relevant = new int[csLen];
 61  6 
         final int[] reverse = new int[csLen];
 62  6 
         int count = 0;
 63  117 
         for (int j = 0; j < csLen; j++) {
 64  111 
             final int checksum = aBlockChecksums[j];
 65  111 
             if (checksum != StrictDuplicateCodeCheck.IGNORE) {
 66  98 
                 reverse[count] = j;
 67  98 
                 relevant[count++] = checksum;
 68   
             }
 69   
         }
 70  6 
         mSortedChecksums = new int[count];
 71  6 
         mOrigIdx = new int[count];
 72  6 
         System.arraycopy(relevant, 0, mSortedChecksums, 0, count);
 73  6 
         System.arraycopy(reverse, 0, mOrigIdx, 0, count);
 74  6 
         sort();
 75  6 
     }
 76   
 
 77   
     /**
 78   
      * Sorts the {@link #mSortedChecksums} field and simultaneously
 79   
      * maintains the {@link mOrigIdx} mapping. The maintenance of the
 80   
      * reverse mapping is the reason why we don't simply use Arrays.sort() here.
 81   
      */
 82   
     private void sort()
 83   
     {
 84   
         // abbreviation for longish field name
 85  6 
         final int[] arr = mSortedChecksums;
 86  6 
         final int len = arr.length;
 87   
 
 88   
         // bubblesort will do for now. It's important that the algorithm
 89   
         // is stable, i.e. it doesn't swap equal values
 90  104 
         for (int i = 0; i < len; i++) {
 91  734 
             for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
 92  636 
                 final int k = j - 1;
 93   
                 // swap j and k and maintain mOrigIdx
 94  636 
                 final int v = arr[j];
 95  636 
                 arr[j] = arr[k];
 96  636 
                 arr[k] = v;
 97  636 
                 final int z = mOrigIdx[j];
 98  636 
                 mOrigIdx[j] = mOrigIdx[k];
 99  636 
                 mOrigIdx[k] = z;
 100   
             }
 101   
         }
 102  6 
     }
 103   
 
 104   
     /**
 105   
      * Returns whether the same checksum occurs both in this ChecksumInfo and
 106   
      * another one,
 107   
      *
 108   
      * @param aChecksumInfo the other ChecksumInfo
 109   
      * @return true iff the same checksum occurs in both ChecksumInfos
 110   
      */
 111   
     boolean hasChecksumOverlapsWith(final ChecksumInfo aChecksumInfo)
 112   
     {
 113  8 
         final int[] jSortedrelevantChecksums =
 114   
             aChecksumInfo.mSortedChecksums;
 115  8 
         final int iLen = mSortedChecksums.length;
 116  8 
         final int jLen = jSortedrelevantChecksums.length;
 117   
 
 118   
         // Both arrays are sorted, so we walk them in parallel,
 119   
         // increasing the index that points to the smaller value.
 120   
         // If the values ever become the same we have found an overlap.
 121  8 
         int jdx = 0;
 122  8 
         int idx = 0;
 123  17 
         while (jdx < jLen && idx < iLen) {
 124  14 
             final long iSum = mSortedChecksums[idx];
 125  14 
             final long jSum = jSortedrelevantChecksums[jdx];
 126  14 
             if (iSum < jSum) {
 127  4 
                 idx += 1;
 128   
             }
 129  10 
             else if (iSum > jSum) {
 130  5 
                 jdx += 1;
 131   
             }
 132   
             else {
 133   
                 // files i and j contain a block with the same checksum
 134  5 
                 return true;
 135   
             }
 136  9 
         }
 137  3 
         return false;
 138   
     }
 139   
 
 140   
     /**
 141   
      * Returns the lines that start a block with a given checksum.
 142   
      *
 143   
      * @param aSum the checksum
 144   
      * @return sorted line indices
 145   
      */
 146   
     int[] findLinesWithChecksum(final int aSum)
 147   
     {
 148  111 
         int idx = Arrays.binarySearch(mSortedChecksums, aSum);
 149  111 
         if (idx < 0) {
 150  13 
             return NO_LINES;
 151   
         }
 152   
 
 153   
         // binary search might have left us in the
 154   
         // middle of a sequence of identical checksums
 155   
 
 156   
         // rewind
 157  111 
         while (idx > 0 && mSortedChecksums[idx - 1] == aSum) {
 158  13 
             idx -= 1;
 159   
         }
 160  98 
         final int start = idx;
 161   
 
 162   
         // forward
 163  98 
         int end = start + 1;
 164   
         while (end < mSortedChecksums.length
 165  122 
                 && mSortedChecksums[end] == mSortedChecksums[end - 1])
 166   
         {
 167  24 
             end += 1;
 168   
         }
 169   
 
 170   
         // find original lines through reverse mapping
 171  98 
         final int[] ret = new int[end - start];
 172  220 
         for (int i = 0; i < ret.length; i++) {
 173  122 
             ret[i] = mOrigIdx[start + i];
 174   
         }
 175  98 
         Arrays.sort(ret);
 176  98 
         return ret;
 177   
     }
 178   
 }
Report generated by Cobertura 1.9.4.1 on 2/3/14 10:27 PM.