Classes in this File | Line Coverage | Branch Coverage | Complexity | ||||
ChecksumInfo |
|
| 5.25;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 | } |