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  
 }