tikhomirov@542: /* tikhomirov@542: * Copyright (c) 2013 TMate Software Ltd tikhomirov@542: * tikhomirov@542: * This program is free software; you can redistribute it and/or modify tikhomirov@542: * it under the terms of the GNU General Public License as published by tikhomirov@542: * the Free Software Foundation; version 2 of the License. tikhomirov@542: * tikhomirov@542: * This program is distributed in the hope that it will be useful, tikhomirov@542: * but WITHOUT ANY WARRANTY; without even the implied warranty of tikhomirov@542: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the tikhomirov@542: * GNU General Public License for more details. tikhomirov@542: * tikhomirov@542: * For information on how to redistribute this software under tikhomirov@542: * the terms of a license other than GNU General Public License tikhomirov@542: * contact TMate Software at support@hg4j.com tikhomirov@542: */ tikhomirov@542: package org.tmatesoft.hg.internal; tikhomirov@542: tikhomirov@542: import static org.tmatesoft.hg.repo.HgRepository.NO_REVISION; tikhomirov@548: import static org.tmatesoft.hg.repo.HgRepository.TIP; tikhomirov@542: tikhomirov@542: import org.tmatesoft.hg.core.Nodeid; tikhomirov@551: import org.tmatesoft.hg.internal.DiffHelper.LineSequence; tikhomirov@542: import org.tmatesoft.hg.repo.HgDataFile; tikhomirov@542: import org.tmatesoft.hg.repo.HgInvalidStateException; tikhomirov@542: import org.tmatesoft.hg.util.CancelledException; tikhomirov@542: tikhomirov@542: /** tikhomirov@542: * tikhomirov@542: * @author Artem Tikhomirov tikhomirov@542: * @author TMate Software Ltd. tikhomirov@542: */ tikhomirov@542: @Experimental(reason="work in progress") tikhomirov@542: public class AnnotateFacility { tikhomirov@549: tikhomirov@549: /** tikhomirov@549: * mimic 'hg diff -r csetRevIndex1 -r csetRevIndex2' tikhomirov@549: */ tikhomirov@549: public void diff(HgDataFile df, int csetRevIndex1, int csetRevIndex2, BlockInspector insp) { tikhomirov@549: int fileRevIndex1 = fileRevIndex(df, csetRevIndex1); tikhomirov@549: int fileRevIndex2 = fileRevIndex(df, csetRevIndex2); tikhomirov@549: LineSequence c1 = lines(df, fileRevIndex1); tikhomirov@549: LineSequence c2 = lines(df, fileRevIndex2); tikhomirov@551: DiffHelper pg = new DiffHelper(); tikhomirov@549: pg.init(c1, c2); tikhomirov@549: pg.findMatchingBlocks(new BlameBlockInspector(insp, csetRevIndex1, csetRevIndex2)); tikhomirov@549: } tikhomirov@548: tikhomirov@548: /** tikhomirov@548: * Annotate file revision, line by line. tikhomirov@548: */ tikhomirov@548: public void annotate(HgDataFile df, int changesetRevisionIndex, LineInspector insp) { tikhomirov@548: if (!df.exists()) { tikhomirov@548: return; tikhomirov@548: } tikhomirov@549: int fileRevIndex = fileRevIndex(df, changesetRevisionIndex); tikhomirov@548: int[] fileRevParents = new int[2]; tikhomirov@548: FileAnnotation fa = new FileAnnotation(insp); tikhomirov@548: do { tikhomirov@548: // also covers changesetRevisionIndex == TIP, #implAnnotateChange doesn't tolerate constants tikhomirov@548: changesetRevisionIndex = df.getChangesetRevisionIndex(fileRevIndex); tikhomirov@548: df.parents(fileRevIndex, fileRevParents, null, null); tikhomirov@548: implAnnotateChange(df, changesetRevisionIndex, fileRevIndex, fileRevParents, fa); tikhomirov@548: fileRevIndex = fileRevParents[0]; tikhomirov@548: } while (fileRevIndex != NO_REVISION); tikhomirov@548: } tikhomirov@548: tikhomirov@544: /** tikhomirov@544: * Annotates changes of the file against its parent(s) tikhomirov@544: */ tikhomirov@546: public void annotateChange(HgDataFile df, int changesetRevisionIndex, BlockInspector insp) { tikhomirov@545: // TODO detect if file is text/binary (e.g. looking for chars < ' ' and not \t\r\n\f tikhomirov@549: int fileRevIndex = fileRevIndex(df, changesetRevisionIndex); tikhomirov@542: int[] fileRevParents = new int[2]; tikhomirov@542: df.parents(fileRevIndex, fileRevParents, null, null); tikhomirov@548: if (changesetRevisionIndex == TIP) { tikhomirov@548: changesetRevisionIndex = df.getChangesetRevisionIndex(fileRevIndex); tikhomirov@548: } tikhomirov@548: implAnnotateChange(df, changesetRevisionIndex, fileRevIndex, fileRevParents, insp); tikhomirov@548: } tikhomirov@548: tikhomirov@548: private void implAnnotateChange(HgDataFile df, int csetRevIndex, int fileRevIndex, int[] fileParentRevs, BlockInspector insp) { tikhomirov@549: final LineSequence fileRevLines = lines(df, fileRevIndex); tikhomirov@549: if (fileParentRevs[0] != NO_REVISION && fileParentRevs[1] != NO_REVISION) { tikhomirov@549: LineSequence p1Lines = lines(df, fileParentRevs[0]); tikhomirov@549: LineSequence p2Lines = lines(df, fileParentRevs[1]); tikhomirov@549: int p1ClogIndex = df.getChangesetRevisionIndex(fileParentRevs[0]); tikhomirov@549: int p2ClogIndex = df.getChangesetRevisionIndex(fileParentRevs[1]); tikhomirov@551: DiffHelper pg = new DiffHelper(); tikhomirov@549: pg.init(p2Lines, fileRevLines); tikhomirov@549: EqualBlocksCollector p2MergeCommon = new EqualBlocksCollector(); tikhomirov@549: pg.findMatchingBlocks(p2MergeCommon); tikhomirov@549: // tikhomirov@549: pg.init(p1Lines); tikhomirov@549: BlameBlockInspector bbi = new BlameBlockInspector(insp, p1ClogIndex, csetRevIndex); tikhomirov@549: bbi.setMergeParent2(p2MergeCommon, p2ClogIndex); tikhomirov@549: pg.findMatchingBlocks(bbi); tikhomirov@549: } else if (fileParentRevs[0] == fileParentRevs[1]) { tikhomirov@549: // may be equal iff both are unset tikhomirov@549: assert fileParentRevs[0] == NO_REVISION; tikhomirov@549: // everything added tikhomirov@549: BlameBlockInspector bbi = new BlameBlockInspector(insp, NO_REVISION, csetRevIndex); tikhomirov@549: bbi.begin(LineSequence.newlines(new byte[0]), fileRevLines); tikhomirov@549: bbi.match(0, fileRevLines.chunkCount()-1, 0); tikhomirov@549: bbi.end(); tikhomirov@549: } else { tikhomirov@549: int soleParent = fileParentRevs[0] == NO_REVISION ? fileParentRevs[1] : fileParentRevs[0]; tikhomirov@549: assert soleParent != NO_REVISION; tikhomirov@549: LineSequence parentLines = lines(df, soleParent); tikhomirov@549: tikhomirov@549: int parentChangesetRevIndex = df.getChangesetRevisionIndex(soleParent); tikhomirov@551: DiffHelper pg = new DiffHelper(); tikhomirov@549: pg.init(parentLines, fileRevLines); tikhomirov@549: pg.findMatchingBlocks(new BlameBlockInspector(insp, parentChangesetRevIndex, csetRevIndex)); tikhomirov@549: } tikhomirov@549: } tikhomirov@549: tikhomirov@549: private static int fileRevIndex(HgDataFile df, int csetRevIndex) { tikhomirov@549: Nodeid fileRev = df.getRepo().getManifest().getFileRevision(csetRevIndex, df.getPath()); tikhomirov@549: return df.getRevisionIndex(fileRev); tikhomirov@549: } tikhomirov@549: tikhomirov@549: private static LineSequence lines(HgDataFile df, int fileRevIndex) { tikhomirov@545: try { tikhomirov@549: ByteArrayChannel c; tikhomirov@549: df.content(fileRevIndex, c = new ByteArrayChannel()); tikhomirov@549: return LineSequence.newlines(c.toArray()); tikhomirov@545: } catch (CancelledException ex) { tikhomirov@545: // TODO likely it was bad idea to throw cancelled exception from content() tikhomirov@545: // deprecate and provide alternative? tikhomirov@545: HgInvalidStateException ise = new HgInvalidStateException("ByteArrayChannel never throws CancelledException"); tikhomirov@545: ise.initCause(ex); tikhomirov@545: throw ise; tikhomirov@542: } tikhomirov@542: } tikhomirov@542: tikhomirov@542: @Callback tikhomirov@546: public interface BlockInspector { tikhomirov@545: void same(EqualBlock block); tikhomirov@542: void added(AddBlock block); tikhomirov@542: void changed(ChangeBlock block); tikhomirov@542: void deleted(DeleteBlock block); tikhomirov@542: } tikhomirov@542: tikhomirov@545: @Callback tikhomirov@546: public interface BlockInspectorEx extends BlockInspector { // XXX better name tikhomirov@545: // XXX perhaps, shall pass object instead of separate values for future extension? tikhomirov@545: void start(int originLineCount, int targetLineCount); tikhomirov@545: void done(); tikhomirov@545: } tikhomirov@545: tikhomirov@542: public interface Block { tikhomirov@545: int originChangesetIndex(); tikhomirov@545: int targetChangesetIndex(); tikhomirov@542: // boolean isMergeRevision(); tikhomirov@542: // int fileRevisionIndex(); tikhomirov@542: // int originFileRevisionIndex(); tikhomirov@542: // String[] lines(); tikhomirov@542: // byte[] data(); tikhomirov@542: } tikhomirov@542: tikhomirov@545: public interface EqualBlock extends Block { tikhomirov@545: int originStart(); tikhomirov@545: int targetStart(); tikhomirov@545: int length(); tikhomirov@545: } tikhomirov@545: tikhomirov@542: public interface AddBlock extends Block { tikhomirov@543: int insertedAt(); // line index in the old file tikhomirov@542: int firstAddedLine(); tikhomirov@542: int totalAddedLines(); tikhomirov@542: String[] addedLines(); tikhomirov@542: } tikhomirov@542: public interface DeleteBlock extends Block { tikhomirov@543: int removedAt(); // line index in the new file tikhomirov@542: int firstRemovedLine(); tikhomirov@542: int totalRemovedLines(); tikhomirov@542: String[] removedLines(); tikhomirov@542: } tikhomirov@542: public interface ChangeBlock extends AddBlock, DeleteBlock { tikhomirov@542: } tikhomirov@546: tikhomirov@546: @Callback tikhomirov@546: public interface LineInspector { tikhomirov@548: /** tikhomirov@548: * Not necessarily invoked sequentially by line numbers tikhomirov@548: */ tikhomirov@546: void line(int lineNumber, int changesetRevIndex, LineDescriptor ld); tikhomirov@546: } tikhomirov@546: tikhomirov@546: public interface LineDescriptor { tikhomirov@546: int totalLines(); tikhomirov@546: } tikhomirov@546: tikhomirov@546: tikhomirov@542: tikhomirov@551: static class BlameBlockInspector extends DiffHelper.DeltaInspector { tikhomirov@546: private final BlockInspector insp; tikhomirov@549: private final int csetOrigin; tikhomirov@545: private final int csetTarget; tikhomirov@549: private EqualBlocksCollector p2MergeCommon; tikhomirov@549: private int csetMergeParent; tikhomirov@549: private IntVector mergeRanges; tikhomirov@542: tikhomirov@549: public BlameBlockInspector(BlockInspector inspector, int originCset, int targetCset) { tikhomirov@542: assert inspector != null; tikhomirov@542: insp = inspector; tikhomirov@549: csetOrigin = originCset; tikhomirov@545: csetTarget = targetCset; tikhomirov@545: } tikhomirov@545: tikhomirov@549: public void setMergeParent2(EqualBlocksCollector p2Merge, int parentCset2) { tikhomirov@549: p2MergeCommon = p2Merge; tikhomirov@549: csetMergeParent = parentCset2; tikhomirov@549: mergeRanges = new IntVector(3*10, 3*10); tikhomirov@549: } tikhomirov@549: tikhomirov@545: @Override tikhomirov@545: public void begin(LineSequence s1, LineSequence s2) { tikhomirov@545: super.begin(s1, s2); tikhomirov@546: if (insp instanceof BlockInspectorEx) { tikhomirov@546: ((BlockInspectorEx) insp).start(s1.chunkCount() - 1, s2.chunkCount() - 1); tikhomirov@545: } tikhomirov@545: } tikhomirov@545: tikhomirov@545: @Override tikhomirov@545: public void end() { tikhomirov@545: super.end(); tikhomirov@546: if(insp instanceof BlockInspectorEx) { tikhomirov@546: ((BlockInspectorEx) insp).done(); tikhomirov@545: } tikhomirov@542: } tikhomirov@542: tikhomirov@542: @Override tikhomirov@542: protected void changed(int s1From, int s1To, int s2From, int s2To) { tikhomirov@549: if (p2MergeCommon != null) { tikhomirov@549: mergeRanges.clear(); tikhomirov@549: p2MergeCommon.combineAndMarkRangesWithTarget(s2From, s2To - s2From, csetOrigin, csetMergeParent, mergeRanges); tikhomirov@549: tikhomirov@549: /* tikhomirov@549: * Usecases: tikhomirov@549: * 3 lines changed to 10 lines. range of 10 lines breaks down to 2 from p2, 3 from p1, and 5 from p2. tikhomirov@549: * We report: 2 lines changed to 2(p2), then 1 line changed with 3(p1) and 5 lines added from p2. tikhomirov@549: * tikhomirov@549: * 10 lines changed to 3 lines, range of 3 lines breaks down to 2 line from p1 and 1 line from p2. tikhomirov@549: * We report: 2 lines changed to 2(p1) and 8 lines changed to 1(p2) tikhomirov@549: */ tikhomirov@549: int s1TotalLines = s1To - s1From, s1ConsumedLines = 0, s1Start = s1From; tikhomirov@549: tikhomirov@549: for (int i = 0; i < mergeRanges.size(); i += 3) { tikhomirov@549: final int rangeOrigin = mergeRanges.get(i); tikhomirov@549: final int rangeStart = mergeRanges.get(i+1); tikhomirov@549: final int rangeLen = mergeRanges.get(i+2); tikhomirov@549: final boolean lastRange = i+3 >= mergeRanges.size(); tikhomirov@549: final int s1LinesLeft = s1TotalLines - s1ConsumedLines; tikhomirov@549: // how many lines we may reported as changed (don't use more than in range unless it's the very last range) tikhomirov@549: final int s1LinesToBorrow = lastRange ? s1LinesLeft : Math.min(s1LinesLeft, rangeLen); tikhomirov@549: if (s1LinesToBorrow > 0) { tikhomirov@549: BlockImpl2 block = new BlockImpl2(seq1, seq2, s1Start, s1LinesToBorrow, rangeStart, rangeLen, s1Start, rangeStart); tikhomirov@549: block.setOriginAndTarget(rangeOrigin, csetTarget); tikhomirov@549: insp.changed(block); tikhomirov@549: s1ConsumedLines += s1LinesToBorrow; tikhomirov@549: s1Start += s1LinesToBorrow; tikhomirov@549: } else { tikhomirov@549: BlockImpl2 block = getAddBlock(rangeStart, rangeLen, s1Start); tikhomirov@549: block.setOriginAndTarget(rangeOrigin, csetTarget); tikhomirov@549: insp.added(block); tikhomirov@549: } tikhomirov@549: } tikhomirov@549: if (s1ConsumedLines != s1TotalLines) { tikhomirov@549: throw new HgInvalidStateException(String.format("Expected to process %d lines, but actually was %d", s1TotalLines, s1ConsumedLines)); tikhomirov@549: } tikhomirov@549: } else { tikhomirov@549: BlockImpl2 block = new BlockImpl2(seq1, seq2, s1From, s1To-s1From, s2From, s2To - s2From, s1From, s2From); tikhomirov@549: block.setOriginAndTarget(csetOrigin, csetTarget); tikhomirov@549: insp.changed(block); tikhomirov@549: } tikhomirov@542: } tikhomirov@542: tikhomirov@542: @Override tikhomirov@542: protected void added(int s1InsertPoint, int s2From, int s2To) { tikhomirov@549: if (p2MergeCommon != null) { tikhomirov@549: mergeRanges.clear(); tikhomirov@549: p2MergeCommon.combineAndMarkRangesWithTarget(s2From, s2To - s2From, csetOrigin, csetMergeParent, mergeRanges); tikhomirov@549: int insPoint = s1InsertPoint; // track changes to insertion point tikhomirov@549: for (int i = 0; i < mergeRanges.size(); i += 3) { tikhomirov@549: int rangeOrigin = mergeRanges.get(i); tikhomirov@549: int rangeStart = mergeRanges.get(i+1); tikhomirov@549: int rangeLen = mergeRanges.get(i+2); tikhomirov@549: BlockImpl2 block = getAddBlock(rangeStart, rangeLen, insPoint); tikhomirov@549: block.setOriginAndTarget(rangeOrigin, csetTarget); tikhomirov@549: insp.added(block); tikhomirov@549: // indicate insPoint moved down number of lines we just reported tikhomirov@549: insPoint += rangeLen; tikhomirov@549: } tikhomirov@549: } else { tikhomirov@549: BlockImpl2 block = getAddBlock(s2From, s2To - s2From, s1InsertPoint); tikhomirov@549: block.setOriginAndTarget(csetOrigin, csetTarget); tikhomirov@549: insp.added(block); tikhomirov@549: } tikhomirov@542: } tikhomirov@542: tikhomirov@542: @Override tikhomirov@543: protected void deleted(int s2DeletePoint, int s1From, int s1To) { tikhomirov@545: BlockImpl2 block = new BlockImpl2(seq1, null, s1From, s1To - s1From, -1, -1, -1, s2DeletePoint); tikhomirov@549: block.setOriginAndTarget(csetOrigin, csetTarget); tikhomirov@545: insp.deleted(block); tikhomirov@542: } tikhomirov@542: tikhomirov@542: @Override tikhomirov@542: protected void unchanged(int s1From, int s2From, int length) { tikhomirov@545: BlockImpl1 block = new BlockImpl1(s1From, s2From, length); tikhomirov@549: block.setOriginAndTarget(csetOrigin, csetTarget); tikhomirov@545: insp.same(block); tikhomirov@545: } tikhomirov@549: tikhomirov@549: private BlockImpl2 getAddBlock(int start, int len, int insPoint) { tikhomirov@549: return new BlockImpl2(null, seq2, -1, -1, start, len, insPoint, -1); tikhomirov@549: } tikhomirov@545: } tikhomirov@545: tikhomirov@545: static class BlockImpl implements Block { tikhomirov@545: tikhomirov@545: private int originCset; tikhomirov@545: private int targetCset; tikhomirov@545: tikhomirov@545: void setOriginAndTarget(int originChangesetIndex, int targetChangesetIndex) { tikhomirov@545: // XXX perhaps, shall be part of Inspector API, rather than Block's tikhomirov@545: // as they don't change between blocks (although the moment about merged revisions) tikhomirov@545: // is not yet clear to me tikhomirov@545: originCset = originChangesetIndex; tikhomirov@545: targetCset = targetChangesetIndex; tikhomirov@545: } tikhomirov@545: tikhomirov@545: public int originChangesetIndex() { tikhomirov@545: return originCset; tikhomirov@545: } tikhomirov@545: tikhomirov@545: public int targetChangesetIndex() { tikhomirov@545: return targetCset; tikhomirov@542: } tikhomirov@542: } tikhomirov@542: tikhomirov@545: static class BlockImpl1 extends BlockImpl implements EqualBlock { tikhomirov@545: private final int start1, start2; tikhomirov@542: private final int length; tikhomirov@542: tikhomirov@545: BlockImpl1(int blockStartSeq1, int blockStartSeq2, int blockLength) { tikhomirov@545: start1 = blockStartSeq1; tikhomirov@545: start2 = blockStartSeq2; tikhomirov@545: length = blockLength; tikhomirov@542: } tikhomirov@542: tikhomirov@545: public int originStart() { tikhomirov@545: return start1; tikhomirov@545: } tikhomirov@545: tikhomirov@545: public int targetStart() { tikhomirov@545: return start2; tikhomirov@545: } tikhomirov@545: tikhomirov@545: public int length() { tikhomirov@545: return length; tikhomirov@542: } tikhomirov@542: tikhomirov@545: @Override tikhomirov@545: public String toString() { tikhomirov@545: return String.format("@@ [%d..%d) == [%d..%d) @@", start1, start1+length, start2, start2+length); tikhomirov@545: } tikhomirov@542: } tikhomirov@542: tikhomirov@545: static class BlockImpl2 extends BlockImpl implements ChangeBlock { tikhomirov@542: tikhomirov@545: private final LineSequence oldSeq; tikhomirov@545: private final LineSequence newSeq; tikhomirov@542: private final int s1Start; tikhomirov@542: private final int s1Len; tikhomirov@542: private final int s2Start; tikhomirov@542: private final int s2Len; tikhomirov@543: private final int s1InsertPoint; tikhomirov@543: private final int s2DeletePoint; tikhomirov@542: tikhomirov@545: public BlockImpl2(LineSequence s1, LineSequence s2, int s1Start, int s1Len, int s2Start, int s2Len, int s1InsertPoint, int s2DeletePoint) { tikhomirov@542: oldSeq = s1; tikhomirov@542: newSeq = s2; tikhomirov@542: this.s1Start = s1Start; tikhomirov@542: this.s1Len = s1Len; tikhomirov@542: this.s2Start = s2Start; tikhomirov@542: this.s2Len = s2Len; tikhomirov@543: this.s1InsertPoint = s1InsertPoint; tikhomirov@543: this.s2DeletePoint = s2DeletePoint; tikhomirov@543: } tikhomirov@543: tikhomirov@543: public int insertedAt() { tikhomirov@543: return s1InsertPoint; tikhomirov@542: } tikhomirov@542: tikhomirov@542: public int firstAddedLine() { tikhomirov@542: return s2Start; tikhomirov@542: } tikhomirov@542: tikhomirov@542: public int totalAddedLines() { tikhomirov@542: return s2Len; tikhomirov@542: } tikhomirov@542: tikhomirov@542: public String[] addedLines() { tikhomirov@542: return generateLines(totalAddedLines(), firstAddedLine()); tikhomirov@542: } tikhomirov@543: tikhomirov@543: public int removedAt() { tikhomirov@543: return s2DeletePoint; tikhomirov@543: } tikhomirov@542: tikhomirov@542: public int firstRemovedLine() { tikhomirov@542: return s1Start; tikhomirov@542: } tikhomirov@542: tikhomirov@542: public int totalRemovedLines() { tikhomirov@542: return s1Len; tikhomirov@542: } tikhomirov@542: tikhomirov@542: public String[] removedLines() { tikhomirov@542: return generateLines(totalRemovedLines(), firstRemovedLine()); tikhomirov@542: } tikhomirov@542: tikhomirov@542: private String[] generateLines(int count, int startFrom) { tikhomirov@542: String[] rv = new String[count]; tikhomirov@542: for (int i = 0; i < count; i++) { tikhomirov@543: rv[i] = String.format("LINE %d", startFrom + i+1); tikhomirov@542: } tikhomirov@542: return rv; tikhomirov@542: } tikhomirov@545: tikhomirov@545: @Override tikhomirov@545: public String toString() { tikhomirov@545: if (s2DeletePoint == -1) { tikhomirov@545: return String.format("@@ -%d,0 +%d,%d @@", insertedAt(), firstAddedLine(), totalAddedLines()); tikhomirov@545: } else if (s1InsertPoint == -1) { tikhomirov@545: // delete only tikhomirov@545: return String.format("@@ -%d,%d +%d,0 @@", firstRemovedLine(), totalRemovedLines(), removedAt()); tikhomirov@545: } tikhomirov@545: return String.format("@@ -%d,%d +%d,%d @@", firstRemovedLine(), totalRemovedLines(), firstAddedLine(), totalAddedLines()); tikhomirov@545: } tikhomirov@542: } tikhomirov@549: tikhomirov@551: static class EqualBlocksCollector implements DiffHelper.MatchInspector { tikhomirov@549: private final IntVector matches = new IntVector(10*3, 2*3); tikhomirov@549: tikhomirov@549: public void begin(LineSequence s1, LineSequence s2) { tikhomirov@549: } tikhomirov@549: tikhomirov@549: public void match(int startSeq1, int startSeq2, int matchLength) { tikhomirov@549: matches.add(startSeq1); tikhomirov@549: matches.add(startSeq2); tikhomirov@549: matches.add(matchLength); tikhomirov@549: } tikhomirov@549: tikhomirov@549: public void end() { tikhomirov@549: } tikhomirov@549: tikhomirov@549: // true when specified line in origin is equal to a line in target tikhomirov@549: public boolean includesOriginLine(int ln) { tikhomirov@549: return includes(ln, 0); tikhomirov@549: } tikhomirov@549: tikhomirov@549: // true when specified line in target is equal to a line in origin tikhomirov@549: public boolean includesTargetLine(int ln) { tikhomirov@549: return includes(ln, 1); tikhomirov@549: } tikhomirov@549: tikhomirov@549: public void intersectWithTarget(int start, int length, IntVector result) { tikhomirov@549: int s = start; tikhomirov@549: for (int l = start, x = start + length; l < x; l++) { tikhomirov@549: if (!includesTargetLine(l)) { tikhomirov@549: if (l - s > 0) { tikhomirov@549: result.add(s); tikhomirov@549: result.add(l - s); tikhomirov@549: } tikhomirov@549: s = l+1; tikhomirov@549: } tikhomirov@549: } tikhomirov@549: if (s < start+length) { tikhomirov@549: result.add(s); tikhomirov@549: result.add((start + length) - s); tikhomirov@549: } tikhomirov@549: } tikhomirov@549: tikhomirov@549: /* tikhomirov@549: * intersects [start..start+length) with ranges of target lines, and based on the intersection tikhomirov@549: * breaks initial range into smaller ranges and records them into result, with marker to indicate tikhomirov@549: * whether the range is from initial range (markerSource) or is a result of the intersection with target tikhomirov@549: * (markerTarget) tikhomirov@549: */ tikhomirov@549: public void combineAndMarkRangesWithTarget(int start, int length, int markerSource, int markerTarget, IntVector result) { tikhomirov@549: int sourceStart = start, targetStart = start, sourceEnd = start + length; tikhomirov@549: for (int l = sourceStart; l < sourceEnd; l++) { tikhomirov@549: if (includesTargetLine(l)) { tikhomirov@549: // l is from target tikhomirov@549: if (sourceStart < l) { tikhomirov@549: // few lines from source range were not in the target, report them tikhomirov@549: result.add(markerSource); tikhomirov@549: result.add(sourceStart); tikhomirov@549: result.add(l - sourceStart); tikhomirov@549: } tikhomirov@549: // indicate the earliest line from source range to use tikhomirov@549: sourceStart = l + 1; tikhomirov@549: } else { tikhomirov@549: // l is not in target tikhomirov@549: if (targetStart < l) { tikhomirov@549: // report lines from target range tikhomirov@549: result.add(markerTarget); tikhomirov@549: result.add(targetStart); tikhomirov@549: result.add(l - targetStart); tikhomirov@549: } tikhomirov@549: // next line *may* be from target tikhomirov@549: targetStart = l + 1; tikhomirov@549: } tikhomirov@549: } tikhomirov@549: // if source range end with line from target, sourceStart would be == sourceEnd, and we need to add range with markerTarget tikhomirov@549: // if source range doesn't end with target line, targetStart == sourceEnd, while sourceStart < sourceEnd tikhomirov@549: if (sourceStart < sourceEnd) { tikhomirov@549: assert targetStart == sourceEnd; tikhomirov@549: // something left from the source range tikhomirov@549: result.add(markerSource); tikhomirov@549: result.add(sourceStart); tikhomirov@549: result.add(sourceEnd - sourceStart); tikhomirov@549: } else if (targetStart < sourceEnd) { tikhomirov@549: assert sourceStart == sourceEnd; tikhomirov@549: result.add(markerTarget); tikhomirov@549: result.add(targetStart); tikhomirov@549: result.add(sourceEnd - targetStart); tikhomirov@549: } tikhomirov@549: } tikhomirov@549: tikhomirov@549: private boolean includes(int ln, int o) { tikhomirov@549: for (int i = 2; i < matches.size(); o += 3, i+=3) { tikhomirov@549: int rangeStart = matches.get(o); tikhomirov@549: if (rangeStart > ln) { tikhomirov@549: return false; tikhomirov@549: } tikhomirov@549: int rangeLen = matches.get(i); tikhomirov@549: if (rangeStart + rangeLen > ln) { tikhomirov@549: return true; tikhomirov@549: } tikhomirov@549: } tikhomirov@549: return false; tikhomirov@549: } tikhomirov@549: } tikhomirov@549: tikhomirov@549: public static void main(String[] args) { tikhomirov@549: EqualBlocksCollector bc = new EqualBlocksCollector(); tikhomirov@549: bc.match(-1, 5, 3); tikhomirov@549: bc.match(-1, 10, 2); tikhomirov@549: bc.match(-1, 15, 3); tikhomirov@549: bc.match(-1, 20, 3); tikhomirov@549: assert !bc.includesTargetLine(4); tikhomirov@549: assert bc.includesTargetLine(7); tikhomirov@549: assert !bc.includesTargetLine(8); tikhomirov@549: assert bc.includesTargetLine(10); tikhomirov@549: assert !bc.includesTargetLine(12); tikhomirov@549: IntVector r = new IntVector(); tikhomirov@549: bc.intersectWithTarget(7, 10, r); tikhomirov@549: for (int i = 0; i < r.size(); i+=2) { tikhomirov@549: System.out.printf("[%d..%d) ", r.get(i), r.get(i) + r.get(i+1)); tikhomirov@549: } tikhomirov@549: System.out.println(); tikhomirov@549: r.clear(); tikhomirov@549: bc.combineAndMarkRangesWithTarget(0, 16, 508, 514, r); tikhomirov@549: for (int i = 0; i < r.size(); i+=3) { tikhomirov@549: System.out.printf("%d:[%d..%d) ", r.get(i), r.get(i+1), r.get(i+1) + r.get(i+2)); tikhomirov@549: } tikhomirov@549: } tikhomirov@542: }