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: public class QSequenceAlgorithm {
018:
019: // Constants ==============================================================
020:
021: public static final boolean ASSERTIONS = true;
022:
023: // Fields =================================================================
024:
025: private final QSequenceMedia mainMedia;
026: private final QSequenceSnakeRegister snakeRegister;
027: private final QSequenceMiddleSnakeFinder finder;
028:
029: // Setup ==================================================================
030:
031: public QSequenceAlgorithm(QSequenceMedia media,
032: QSequenceSnakeRegister snakeRegister, int maximumSearchDepth) {
033: QSequenceAssert.assertTrue(maximumSearchDepth >= 2); // Because for dee == 1, there is a special treatment in produceSnakesInOrder.
034:
035: this .mainMedia = media;
036: this .snakeRegister = snakeRegister;
037: this .finder = new QSequenceMiddleSnakeFinder(media
038: .getLeftLength(), media.getRightLength(),
039: maximumSearchDepth);
040: }
041:
042: // Accessing ==============================================================
043:
044: public void produceSnakesInOrder() throws QSequenceException {
045: final QSequenceRestrictedMedia media = new QSequenceRestrictedMedia(
046: mainMedia);
047: produceSnakesInOrder(media);
048: }
049:
050: // Utils ==================================================================
051:
052: private void produceSnakesInOrder(QSequenceRestrictedMedia media)
053: throws QSequenceException {
054: final int leftLength = media.getLeftLength();
055: final int rightLength = media.getRightLength();
056:
057: if (leftLength < 1 || rightLength < 1) {
058: return;
059: }
060:
061: final int dee = finder.determineMiddleSnake(media);
062: if (dee <= 0) {
063: registerSnake(media, 1, leftLength, 1, rightLength);
064: return;
065: }
066:
067: final int leftFrom = finder.getResult().getLeftFrom();
068: final int rightFrom = finder.getResult().getRightFrom();
069: final int leftTo = finder.getResult().getLeftTo();
070: final int rightTo = finder.getResult().getRightTo();
071:
072: if (dee == 1) {
073: if (rightLength == leftLength + 1) {
074: registerSnake(media, 1, leftFrom, 1, rightFrom - 1);
075: registerSnake(media, leftFrom + 1, leftTo,
076: rightFrom + 1, rightTo);
077: } else if (leftLength == rightLength + 1) {
078: registerSnake(media, 1, leftFrom - 1, 1, rightFrom);
079: registerSnake(media, leftFrom + 1, leftTo,
080: rightFrom + 1, rightTo);
081: } else {
082: QSequenceAssert.assertTrue(false);
083: }
084:
085: return;
086: }
087:
088: final int leftMin = media.getLeftMin();
089: final int rightMin = media.getRightMin();
090: final int leftMax = media.getLeftMax();
091: final int rightMax = media.getRightMax();
092:
093: try {
094: media.restrictTo(leftMin, leftMin + leftFrom - 1, rightMin,
095: rightMin + rightFrom - 1);
096: produceSnakesInOrder(media);
097: media.restrictTo(leftMin, leftMax, rightMin, rightMax);
098: registerSnake(media, leftFrom + 1, leftTo, rightFrom + 1,
099: rightTo);
100: media.restrictTo(leftMin + leftTo - 1 + 1, leftMax,
101: rightMin + rightTo - 1 + 1, rightMax);
102: produceSnakesInOrder(media);
103: } finally {
104: media.restrictTo(leftMin, leftMax, rightMin, rightMax);
105: }
106: }
107:
108: private void registerSnake(QSequenceRestrictedMedia media,
109: int leftFrom, int leftTo, int rightFrom, int rightTo)
110: throws QSequenceException {
111: QSequenceAssert.assertTrue(leftTo - leftFrom == rightTo
112: - rightFrom);
113:
114: if (leftFrom > leftTo || rightFrom > rightTo) {
115: return;
116: }
117:
118: for (int index = 0; index < leftTo - leftFrom; index++) {
119: QSequenceAssert.assertTrue(media.equals(leftFrom + index,
120: rightFrom + index));
121: }
122:
123: leftFrom = media.getLeftMin() + leftFrom - 1;
124: leftTo = media.getLeftMin() + leftTo - 1;
125: rightFrom = media.getRightMin() + rightFrom - 1;
126: rightTo = media.getRightMin() + rightTo - 1;
127: snakeRegister.registerSnake(leftFrom - 1, leftTo - 1,
128: rightFrom - 1, rightTo - 1);
129: }
130: }
|