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: import junit.framework.*;
016:
017: import de.regnis.q.sequence.core.*;
018: import de.regnis.q.sequence.media.*;
019:
020: /**
021: * @author Marc Strapetz
022: */
023: public class QSequenceDifferenceAssemblyTest extends TestCase {
024:
025: // Constants ==============================================================
026:
027: private static final int LINE_LENGTH = 3;
028: private static final int ALPHABET_SIZE = 10;
029:
030: // Static =================================================================
031:
032: public static String[] createLines(int lineCount, Random random) {
033: final String[] lines = new String[lineCount];
034: for (int lineIndex = 0; lineIndex < lines.length; lineIndex++) {
035: String line = createLine(random);
036: lines[lineIndex] = line;
037: }
038:
039: return lines;
040: }
041:
042: public static String[] alterLines(String[] leftLines, double pMod,
043: double pAddRemove, Random random) {
044: final List rightLines = new ArrayList();
045: for (int leftIndex = 0; leftIndex < leftLines.length; leftIndex++) {
046: if (random.nextDouble() < pMod) {
047: rightLines.add(createLine(random));
048: continue;
049: } else if (random.nextDouble() < pAddRemove) {
050: continue;
051: }
052:
053: rightLines.add(leftLines[leftIndex]);
054:
055: if (random.nextDouble() < pAddRemove) {
056: rightLines.add(createLine(random));
057: }
058: }
059: return (String[]) rightLines.toArray(new String[0]);
060: }
061:
062: // Fields =================================================================
063:
064: private Random random;
065:
066: // Implemented ============================================================
067:
068: protected void setUp() throws Exception {
069: super .setUp();
070: random = new Random(0);
071: }
072:
073: // Accessing ==============================================================
074:
075: public void test() throws QSequenceException {
076: testVariousLength(0.001, 0.001);
077: testVariousLength(0.01, 0.05);
078: testVariousLength(0.5, 0.5);
079: }
080:
081: // Utils ==================================================================
082:
083: private void testVariousLength(double pMod, double pAddRemove)
084: throws QSequenceException {
085: for (int size = 10; size <= 1000; size += 50) {
086: testOneLength(size, pMod, pAddRemove);
087: }
088: }
089:
090: private void testOneLength(int lineCount, double pMod,
091: double pAddRemove) throws QSequenceException {
092: final String[] left = createLines(lineCount, random);
093: final String[] right = alterLines(left, pMod, pAddRemove,
094: random);
095: testDiff(left, right);
096: }
097:
098: private boolean areLinesEqual(String[] diff, String[] right) {
099: if (diff.length != right.length) {
100: return false;
101: }
102:
103: for (int index = 0; index < diff.length; index++) {
104: if (!diff[index].equals(right[index])) {
105: return false;
106: }
107: }
108:
109: return true;
110: }
111:
112: private static String createLine(Random random) {
113: String line = "";
114: for (int charIndex = 0; charIndex < LINE_LENGTH; charIndex++) {
115: line += String.valueOf((char) ('a' + (char) (Math
116: .abs(random.nextInt()) % ALPHABET_SIZE)));
117: }
118: return line;
119: }
120:
121: private void testDiff(String[] left, String[] right)
122: throws QSequenceException {
123: testDiff(left, right, Integer.MAX_VALUE);
124: testDiff(left, right, (int) Math.sqrt(left.length
125: + right.length));
126: testDiff(left, right, 2);
127: }
128:
129: private void testDiff(String[] left, String[] right,
130: int maximumSearchDepth) throws QSequenceException {
131: final QSequenceTestMedia testMedia = QSequenceTestMedia
132: .createStringMedia(left, right);
133: testDiff(left, right, testMedia,
134: new QSequenceMediaDummyIndexTransformer(testMedia
135: .getLeftLength(), testMedia.getRightLength()),
136: null, maximumSearchDepth);
137:
138: final QSequenceCachingMedia cachingMedia = new QSequenceCachingMedia(
139: testMedia, new QSequenceDummyCanceller());
140: final QSequenceDiscardingMedia media = new QSequenceDiscardingMedia(
141: cachingMedia,
142: new QSequenceDiscardingMediaNoConfusionDectector(true),
143: new QSequenceDummyCanceller());
144: testDiff(left, right, media, media, cachingMedia,
145: maximumSearchDepth);
146: }
147:
148: private void testDiff(String[] left, String[] right,
149: QSequenceMedia media,
150: QSequenceMediaIndexTransformer indexTransformer,
151: QSequenceCachingMedia cachingMedia, int maximumSearchDepth)
152: throws QSequenceException {
153: final List blocks = new QSequenceDifference(media,
154: indexTransformer, maximumSearchDepth).getBlocks();
155: if (cachingMedia != null) {
156: new QSequenceDifferenceBlockShifter(cachingMedia,
157: cachingMedia).shiftBlocks(blocks);
158: }
159:
160: final List diffLines = new ArrayList();
161: int lastLeftTo = -1;
162: for (int index = 0; index < blocks.size(); index++) {
163: final QSequenceDifferenceBlock block = (QSequenceDifferenceBlock) blocks
164: .get(index);
165: for (int leftIndex = lastLeftTo + 1; leftIndex < block
166: .getLeftFrom(); leftIndex++) {
167: diffLines.add(left[leftIndex]);
168: }
169:
170: lastLeftTo = block.getLeftTo();
171:
172: for (int rightIndex = block.getRightFrom(); rightIndex <= block
173: .getRightTo(); rightIndex++) {
174: diffLines.add(right[rightIndex]);
175: }
176: }
177:
178: for (int leftIndex = lastLeftTo + 1; leftIndex < left.length; leftIndex++) {
179: diffLines.add(left[leftIndex]);
180: }
181:
182: final String[] diff = (String[]) diffLines
183: .toArray(new String[0]);
184: if (!areLinesEqual(diff, right)) {
185: fail();
186: }
187: }
188: }
|