001: /*
002: * ====================================================================
003: * Copyright (c) 2004 Marc Strapetz, marc.strapetz@smartsvn.com.
004: * All rights reserved.
005: *
006: * This software is licensed as described in the file COPYING, which
007: * you should have received as part of this distribution. Use is
008: * subject to license terms.
009: * ====================================================================
010: */
011:
012: package de.regnis.q.sequence;
013:
014: import java.util.*;
015:
016: import de.regnis.q.sequence.core.*;
017: import de.regnis.q.sequence.media.*;
018:
019: /**
020: * @author Marc Strapetz
021: */
022: public class QSequenceDifferenceBlockShifter {
023:
024: // Static =================================================================
025:
026: public static void joinBlocks(List blocks) {
027: QSequenceDifferenceBlock lastBlock = null;
028: for (int index = 0; index < blocks.size();) {
029: final QSequenceDifferenceBlock block = (QSequenceDifferenceBlock) blocks
030: .get(index);
031: if (lastBlock == null) {
032: index++;
033: lastBlock = block;
034: continue;
035: }
036:
037: QSequenceAssert.assertTrue(lastBlock.getLeftTo() < block
038: .getLeftFrom());
039: QSequenceAssert.assertTrue(lastBlock.getRightTo() < block
040: .getRightFrom());
041:
042: if (lastBlock.getLeftTo() + 1 != block.getLeftFrom()) {
043: QSequenceAssert
044: .assertTrue(lastBlock.getRightTo() != block
045: .getRightFrom() + 1);
046: lastBlock = block;
047: index++;
048: continue;
049: }
050:
051: if (lastBlock.getRightTo() + 1 != block.getRightFrom()) {
052: QSequenceAssert
053: .assertTrue(lastBlock.getLeftTo() != block
054: .getLeftFrom() + 1);
055: lastBlock = block;
056: index++;
057: continue;
058: }
059:
060: lastBlock.setLeftTo(block.getLeftTo());
061: lastBlock.setRightTo(block.getRightTo());
062: blocks.remove(index);
063: continue;
064: }
065: }
066:
067: // Fields =================================================================
068:
069: private final QSequenceMedia media;
070: private final QSequenceMediaComparer comparer;
071:
072: // Setup ==================================================================
073:
074: public QSequenceDifferenceBlockShifter(QSequenceMedia media,
075: QSequenceMediaComparer comparer) {
076: QSequenceAssert.assertNotNull(media);
077: QSequenceAssert.assertNotNull(comparer);
078:
079: this .media = media;
080: this .comparer = comparer;
081: }
082:
083: // Accessing ==============================================================
084:
085: public void shiftBlocks(List blocks) throws QSequenceException {
086: if (blocks.isEmpty()) {
087: return;
088: }
089:
090: joinBlocks(blocks);
091:
092: for (int index = 0; index < blocks.size();) {
093: if (tryShiftUp(blocks, index, true)) {
094: continue;
095: }
096:
097: index++;
098: }
099:
100: for (int index = 0; index < blocks.size();) {
101: if (tryShiftDown(blocks, index)) {
102: continue;
103: }
104:
105: index++;
106: }
107: }
108:
109: public boolean tryShiftUp(List blocks, int blockIndex,
110: boolean requireMerge) throws QSequenceException {
111: if (blockIndex == 0) {
112: return false;
113: }
114:
115: final QSequenceDifferenceBlock prevBlock = (QSequenceDifferenceBlock) blocks
116: .get(blockIndex - 1);
117: final QSequenceDifferenceBlock block = (QSequenceDifferenceBlock) blocks
118: .get(blockIndex);
119:
120: final int prevLeftTo = prevBlock.getLeftTo();
121: final int prevRightTo = prevBlock.getRightTo();
122:
123: int leftFrom = block.getLeftFrom();
124: int leftTo = block.getLeftTo();
125: int rightFrom = block.getRightFrom();
126: int rightTo = block.getRightTo();
127:
128: QSequenceAssert.assertTrue(leftFrom > prevLeftTo);
129: QSequenceAssert.assertTrue(rightFrom > prevRightTo);
130: QSequenceAssert.assertTrue(leftFrom <= leftTo
131: || rightFrom <= rightTo);
132:
133: if (leftFrom - prevLeftTo != rightFrom - prevRightTo) {
134: return false;
135: }
136:
137: while (leftFrom > prevLeftTo + 1) {
138: if (leftFrom <= leftTo
139: && !comparer.equalsLeft(leftFrom - 1, leftTo)) {
140: break;
141: }
142:
143: if (rightFrom <= rightTo
144: && !comparer.equalsRight(rightFrom - 1, rightTo)) {
145: break;
146: }
147:
148: leftFrom--;
149: leftTo--;
150: rightFrom--;
151: rightTo--;
152: }
153:
154: if (leftFrom > prevLeftTo + 1) {
155: if (requireMerge) {
156: return false;
157: }
158:
159: block.setLeftFrom(leftFrom);
160: block.setLeftTo(leftTo);
161: block.setRightFrom(rightFrom);
162: block.setRightTo(rightTo);
163: } else {
164: prevBlock.setLeftTo(prevBlock.getLeftTo()
165: + (leftTo - leftFrom + 1));
166: prevBlock.setRightTo(prevBlock.getRightTo()
167: + (rightTo - rightFrom + 1));
168: blocks.remove(blockIndex);
169: }
170:
171: return true;
172: }
173:
174: public boolean tryShiftDown(List blocks, int blockIndex)
175: throws QSequenceException {
176: final QSequenceDifferenceBlock nextBlock = blockIndex < blocks
177: .size() - 1 ? (QSequenceDifferenceBlock) blocks
178: .get(blockIndex + 1) : null;
179: final QSequenceDifferenceBlock block = (QSequenceDifferenceBlock) blocks
180: .get(blockIndex);
181:
182: final int nextLeftFrom = nextBlock != null ? nextBlock
183: .getLeftFrom() : media.getLeftLength();
184: final int nextRightFrom = nextBlock != null ? nextBlock
185: .getRightFrom() : media.getRightLength();
186:
187: int leftFrom = block.getLeftFrom();
188: int leftTo = block.getLeftTo();
189: int rightFrom = block.getRightFrom();
190: int rightTo = block.getRightTo();
191:
192: QSequenceAssert.assertTrue(leftTo < nextLeftFrom);
193: QSequenceAssert.assertTrue(rightTo < nextRightFrom);
194: QSequenceAssert.assertTrue(leftFrom <= leftTo
195: || rightFrom <= rightTo);
196:
197: while (leftTo < nextLeftFrom - 1 && rightTo < nextRightFrom - 1) {
198: if (leftFrom <= leftTo
199: && !comparer.equalsLeft(leftFrom, leftTo + 1)) {
200: break;
201: }
202:
203: if (rightFrom <= rightTo
204: && !comparer.equalsRight(rightFrom, rightTo + 1)) {
205: break;
206: }
207:
208: leftFrom++;
209: leftTo++;
210: rightFrom++;
211: rightTo++;
212: }
213:
214: if (nextBlock != null && leftTo == nextLeftFrom - 1
215: && rightTo == nextRightFrom - 1) {
216: nextBlock.setLeftFrom(nextBlock.getLeftFrom()
217: - (leftTo - leftFrom + 1));
218: nextBlock.setRightFrom(nextBlock.getRightFrom()
219: - (rightTo - rightFrom + 1));
220: blocks.remove(blockIndex);
221: return true;
222: }
223:
224: block.setLeftFrom(leftFrom);
225: block.setLeftTo(leftTo);
226: block.setRightFrom(rightFrom);
227: block.setRightTo(rightTo);
228: return false;
229: }
230: }
|