001: ////////////////////////////////////////////////////////////////////////////////
002: // checkstyle: Checks Java source code for adherence to a set of rules.
003: // Copyright (C) 2001-2007 Oliver Burn
004: //
005: // This library is free software; you can redistribute it and/or
006: // modify it under the terms of the GNU Lesser General Public
007: // License as published by the Free Software Foundation; either
008: // version 2.1 of the License, or (at your option) any later version.
009: //
010: // This library is distributed in the hope that it will be useful,
011: // but WITHOUT ANY WARRANTY; without even the implied warranty of
012: // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
013: // Lesser General Public License for more details.
014: //
015: // You should have received a copy of the GNU Lesser General Public
016: // License along with this library; if not, write to the Free Software
017: // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
018: ////////////////////////////////////////////////////////////////////////////////
019: package com.puppycrawl.tools.checkstyle.checks.duplicates;
020:
021: import java.util.Arrays;
022:
023: /**
024: * Helper class for {@link StrictDuplicateCodeCheck},
025: * provides block checksum information for a single file.
026: *
027: * @author lkuehne
028: */
029: final class ChecksumInfo {
030: /**
031: * Helper value to avoid object allocations in
032: * {@link #hasChecksumOverlapsWith(ChecksumInfo)}.
033: */
034: private static final int[] NO_LINES = new int[0];
035:
036: /**
037: * Holds the checksums from the constructor call,
038: * except {@link StrictDuplicateCodeCheck#IGNORE}, sorted.
039: */
040: private int[] mSortedChecksums;
041:
042: /**
043: * Reverse mapping from {@link #mSortedChecksums} to the checksums
044: * from the constructor call.
045: *
046: * <code>mSortedRelevantChecksums[i] == checksums[mOrigIdx[i]]</code>
047: */
048: private int[] mOrigIdx;
049:
050: /**
051: * Creates a new ChecksumInfo.
052: *
053: * @param aBlockChecksums the block checksums as caculated by
054: * the {@link StrictDuplicateCodeCheck}.ChecksumGenerator
055: */
056: ChecksumInfo(int[] aBlockChecksums) {
057: final int csLen = aBlockChecksums.length;
058: final int[] relevant = new int[csLen];
059: final int[] reverse = new int[csLen];
060: int count = 0;
061: for (int j = 0; j < csLen; j++) {
062: final int checksum = aBlockChecksums[j];
063: if (checksum != StrictDuplicateCodeCheck.IGNORE) {
064: reverse[count] = j;
065: relevant[count++] = checksum;
066: }
067: }
068: mSortedChecksums = new int[count];
069: mOrigIdx = new int[count];
070: System.arraycopy(relevant, 0, mSortedChecksums, 0, count);
071: System.arraycopy(reverse, 0, mOrigIdx, 0, count);
072: sort();
073: }
074:
075: /**
076: * Sorts the {@link #mSortedChecksums} field and simultaneously
077: * maintains the {@link mOrigIdx} mapping. The maintainance of the
078: * reverse mapping is the reason why we don't simply use Arrays.sort() here.
079: */
080: private void sort() {
081: // abbreviation for longish field name
082: final int[] arr = mSortedChecksums;
083: final int len = arr.length;
084:
085: // bubblesort will do for now. It's important that the algorithm
086: // is stable, i.e. it doesn't swap equal values
087: for (int i = 0; i < len; i++) {
088: for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
089: final int k = j - 1;
090: // swap j and k and maintain mOrigIdx
091: final int v = arr[j];
092: arr[j] = arr[k];
093: arr[k] = v;
094: final int z = mOrigIdx[j];
095: mOrigIdx[j] = mOrigIdx[k];
096: mOrigIdx[k] = z;
097: }
098: }
099: }
100:
101: /**
102: * Returns whether the same checksum occurs both in this ChecksumInfo and
103: * another one,
104: *
105: * @param aChecksumInfo the other ChecksumInfo
106: * @return true iff the same checksum occurs in both ChecksumInfos
107: */
108: boolean hasChecksumOverlapsWith(final ChecksumInfo aChecksumInfo) {
109: final int[] jSortedrelevantChecksums = aChecksumInfo.mSortedChecksums;
110: final int iLen = mSortedChecksums.length;
111: final int jLen = jSortedrelevantChecksums.length;
112:
113: // Both arrays are sorted, so we walk them in parallel,
114: // increasing the index that points to the smaller value.
115: // If the values ever become the same we have found an overlap.
116: int jdx = 0;
117: int idx = 0;
118: while (jdx < jLen && idx < iLen) {
119: final long iSum = mSortedChecksums[idx];
120: final long jSum = jSortedrelevantChecksums[jdx];
121: if (iSum < jSum) {
122: idx += 1;
123: } else if (iSum > jSum) {
124: jdx += 1;
125: } else {
126: // files i and j contain a block with the same checksum
127: return true;
128: }
129: }
130: return false;
131: }
132:
133: /**
134: * Returns the lines that start a block with a given checksum.
135: *
136: * @param aSum the checksum
137: * @return sorted line indices
138: */
139: int[] findLinesWithChecksum(final int aSum) {
140: int idx = Arrays.binarySearch(mSortedChecksums, aSum);
141: if (idx < 0) {
142: return NO_LINES;
143: }
144:
145: // binary search might have left us in the
146: // middle of a sequence of identical checksums
147:
148: // rewind
149: while (idx > 0 && mSortedChecksums[idx - 1] == aSum) {
150: idx -= 1;
151: }
152: final int start = idx;
153:
154: // forward
155: int end = start + 1;
156: while (end < mSortedChecksums.length
157: && mSortedChecksums[end] == mSortedChecksums[end - 1]) {
158: end += 1;
159: }
160:
161: // find original lines through reverse mapping
162: final int[] ret = new int[end - start];
163: for (int i = 0; i < ret.length; i++) {
164: ret[i] = mOrigIdx[start + i];
165: }
166: Arrays.sort(ret);
167: return ret;
168: }
169: }
|