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.core;
013:
014: /**
015: * @author Marc Strapetz
016: */
017: class QSequenceMiddleSnakeFinder {
018:
019: // Fields =================================================================
020:
021: private final QSequenceDeePathForwardExtender forwardDeePathExtender;
022: private final QSequenceDeePathBackwardExtender backwardDeePathExtender;
023: private final QSequenceMiddleSnakeFinderResult result;
024: private final int maximumSearchDepth;
025:
026: // Setup ==================================================================
027:
028: public QSequenceMiddleSnakeFinder(int maximumMediaLeftLength,
029: int maximumMediaRightLength, int maximumSearchDepth) {
030: this .maximumSearchDepth = maximumSearchDepth;
031: this .forwardDeePathExtender = new QSequenceDeePathForwardExtender(
032: maximumMediaLeftLength, maximumMediaRightLength);
033: this .backwardDeePathExtender = new QSequenceDeePathBackwardExtender(
034: maximumMediaLeftLength, maximumMediaRightLength);
035: this .result = new QSequenceMiddleSnakeFinderResult();
036: }
037:
038: // Accessing ==============================================================
039:
040: public QSequenceMiddleSnakeFinderResult getResult() {
041: return result;
042: }
043:
044: public int determineMiddleSnake(QSequenceMedia media)
045: throws QSequenceException {
046: result.reset();
047: forwardDeePathExtender.reset(media);
048: backwardDeePathExtender.reset(media);
049:
050: final int delta = media.getLeftLength()
051: - media.getRightLength();
052: final int deeMax = (int) Math
053: .ceil(((double) media.getLeftLength() + (double) media
054: .getRightLength()) / 2);
055: for (int dee = 0; dee <= deeMax; dee++) {
056: for (int diagonal = (delta >= 0 ? dee : -dee); (delta >= 0 ? diagonal >= -dee
057: : diagonal <= dee); diagonal += (delta >= 0 ? -2
058: : 2)) {
059: forwardDeePathExtender.extendDeePath(media, dee,
060: diagonal);
061: if (checkForwardOverlapping(delta, diagonal, dee)) {
062: if (isForwardAndBackwardOverlapping(diagonal)) {
063: setMiddleSnake(result, forwardDeePathExtender,
064: diagonal);
065: return 2 * dee - 1;
066: }
067: }
068: }
069:
070: for (int diagonal = (delta >= 0 ? -dee : dee); (delta >= 0 ? diagonal <= dee
071: : diagonal >= -dee); diagonal += (delta >= 0 ? 2
072: : -2)) {
073: final int deltadDiagonal = diagonal + delta;
074: backwardDeePathExtender.extendDeePath(media, dee,
075: deltadDiagonal);
076: if (checkBackwardOverlapping(delta, diagonal, dee)) {
077: if (isForwardAndBackwardOverlapping(deltadDiagonal)) {
078: setMiddleSnake(result, backwardDeePathExtender,
079: deltadDiagonal);
080: return 2 * dee;
081: }
082: }
083: }
084:
085: if (dee < maximumSearchDepth) {
086: continue;
087: }
088:
089: return determineBestSnake(media, dee, delta);
090: }
091:
092: QSequenceAssert.assertTrue(false);
093: return 0;
094: }
095:
096: // Utils ==================================================================
097:
098: private boolean isForwardAndBackwardOverlapping(int diagonal) {
099: final int forwardLeft = forwardDeePathExtender
100: .getLeft(diagonal);
101: final int backwardLeft = backwardDeePathExtender
102: .getLeft(diagonal);
103: return forwardLeft >= backwardLeft;
104: }
105:
106: private int determineBestSnake(QSequenceMedia media, int dee,
107: final int delta) {
108: final int bestForwardDiagonal = getBestForwardDiagonal(dee,
109: delta);
110: final int bestBackwardDiagonal = getBestBackwardDiagonal(dee,
111: delta);
112:
113: if (forwardDeePathExtender.getProgress(bestForwardDiagonal) > backwardDeePathExtender
114: .getProgress(bestBackwardDiagonal)) {
115: final int left = forwardDeePathExtender
116: .getLeft(bestForwardDiagonal);
117: final int right = forwardDeePathExtender
118: .getRight(bestForwardDiagonal);
119: result.setMiddleSnake(left, right, left, right);
120: return 2 * dee - 1;
121: }
122: final int left = backwardDeePathExtender
123: .getLeft(bestBackwardDiagonal);
124: final int right = backwardDeePathExtender
125: .getRight(bestBackwardDiagonal);
126: if (left < 0 || right < 0) {
127: backwardDeePathExtender.print(media, -dee + delta, dee
128: + delta);
129: }
130:
131: result.setMiddleSnake(left, right, left, right);
132: return 2 * dee;
133: }
134:
135: private int getBestForwardDiagonal(int dee, int delta) {
136: int bestDiagonal = 0;
137: int bestProgress = 0;
138: for (int diagonal = (delta >= 0 ? dee : -dee); (delta >= 0 ? diagonal >= -dee
139: : diagonal <= dee); diagonal += (delta >= 0 ? -2 : 2)) {
140: final int progress = forwardDeePathExtender
141: .getProgress(diagonal);
142: if (progress > bestProgress) {
143: bestDiagonal = diagonal;
144: bestProgress = progress;
145: }
146: }
147:
148: return bestDiagonal;
149: }
150:
151: private int getBestBackwardDiagonal(int dee, int delta) {
152: int bestDiagonal = delta;
153: int bestProgress = 0;
154: for (int diagonal = (delta >= 0 ? -dee : dee); (delta >= 0 ? diagonal <= dee
155: : diagonal >= -dee); diagonal += (delta >= 0 ? 2 : -2)) {
156: final int deltadDiagonal = diagonal + delta;
157: final int progress = backwardDeePathExtender
158: .getProgress(deltadDiagonal);
159: if (progress > bestProgress) {
160: bestDiagonal = deltadDiagonal;
161: bestProgress = progress;
162: }
163: }
164:
165: return bestDiagonal;
166: }
167:
168: public static void setMiddleSnake(
169: QSequenceMiddleSnakeFinderResult result,
170: QSequenceDeePathExtender extender, int diagonal) {
171: result.setMiddleSnake(Math.min(extender.getLeft(diagonal),
172: extender.getSnakeStartLeft()), Math.min(extender
173: .getRight(diagonal), extender.getSnakeStartRight()),
174: Math.max(extender.getLeft(diagonal), extender
175: .getSnakeStartLeft()), Math.max(extender
176: .getRight(diagonal), extender
177: .getSnakeStartRight()));
178: }
179:
180: private static boolean checkForwardOverlapping(final int delta,
181: int diagonal, int dee) {
182: return diagonal >= (delta - (dee - 1))
183: && diagonal <= (delta + (dee - 1));
184: }
185:
186: private static boolean checkBackwardOverlapping(final int delta,
187: int diagonal, int dee) {
188: return diagonal + delta >= -dee && diagonal + delta <= dee;
189: }
190: }
|