0001: /*
0002: * Licensed to the Apache Software Foundation (ASF) under one or more
0003: * contributor license agreements. See the NOTICE file distributed with
0004: * this work for additional information regarding copyright ownership.
0005: * The ASF licenses this file to You under the Apache License, Version 2.0
0006: * (the "License"); you may not use this file except in compliance with
0007: * the License. You may obtain a copy of the License at
0008: *
0009: * http://www.apache.org/licenses/LICENSE-2.0
0010: *
0011: * Unless required by applicable law or agreed to in writing, software
0012: * distributed under the License is distributed on an "AS IS" BASIS,
0013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0014: * See the License for the specific language governing permissions and
0015: * limitations under the License.
0016: */
0017:
0018: /* $Id: BreakingAlgorithm.java 501453 2007-01-30 16:37:11Z lfurini $ */
0019:
0020: package org.apache.fop.layoutmgr;
0021:
0022: import org.apache.commons.logging.Log;
0023: import org.apache.commons.logging.LogFactory;
0024:
0025: import org.apache.fop.fo.FONode;
0026:
0027: /**
0028: * The set of nodes is sorted into lines indexed into activeLines.
0029: * The nodes in each line are linked together in a single linked list by the
0030: * KnuthNode.next field. The activeLines array contains a link to the head of
0031: * the linked list in index 'line*2' and a link to the tail at index 'line*2+1'.
0032: * <p>
0033: * The set of active nodes can be traversed by
0034: * <pre>
0035: * for (int line = startLine; line < endLine; line++) {
0036: * for (KnuthNode node = getNode(line); node != null; node = node.next) {
0037: * // Do something with 'node'
0038: * }
0039: * }
0040: * </pre>
0041: */
0042: public abstract class BreakingAlgorithm {
0043:
0044: /** the logger for the class */
0045: protected static Log log = LogFactory
0046: .getLog(BreakingAlgorithm.class);
0047:
0048: /** Maximum adjustment ration */
0049: protected static final int INFINITE_RATIO = 1000;
0050:
0051: private static final int MAX_RECOVERY_ATTEMPTS = 5;
0052:
0053: // constants identifying a subset of the feasible breaks
0054: /** All feasible breaks are ok. */
0055: public static final int ALL_BREAKS = 0;
0056: /** This forbids hyphenation. */
0057: public static final int NO_FLAGGED_PENALTIES = 1;
0058: /** wrap-option = "no-wrap". */
0059: public static final int ONLY_FORCED_BREAKS = 2;
0060:
0061: // parameters of Knuth's algorithm:
0062: /** Penalty value for flagged penalties. */
0063: private int flaggedPenalty = 50;
0064: /** Demerit for consecutive lines ending at flagged penalties. */
0065: protected int repeatedFlaggedDemerit = 50;
0066: /** Demerit for consecutive lines belonging to incompatible fitness classes . */
0067: protected int incompatibleFitnessDemerit = 50;
0068: /** Maximum number of consecutive lines ending with a flagged penalty.
0069: * Only a value >= 1 is a significant limit.
0070: */
0071: protected int maxFlaggedPenaltiesCount;
0072:
0073: /**
0074: * The threshold for considering breaks to be acceptable. The adjustment ratio must be
0075: * inferior to this threshold.
0076: */
0077: private double threshold;
0078:
0079: /**
0080: * The paragraph of KnuthElements.
0081: */
0082: protected KnuthSequence par;
0083:
0084: /**
0085: * The width of a line (or height of a column in page-breaking mode).
0086: * -1 indicates that the line widths are different for each line.
0087: */
0088: protected int lineWidth = -1;
0089: /** Force the algorithm to find a set of breakpoints, even if no feasible breakpoints
0090: * exist.
0091: */
0092: private boolean force = false;
0093: /** If set to true, doesn't ignore break possibilities which are definitely too short. */
0094: protected boolean considerTooShort = false;
0095:
0096: /** When in forced mode, the best node leading to a too long line. The line will be
0097: * too long anyway, but this one will lead to a paragraph with fewest demerits.
0098: */
0099: private KnuthNode lastTooLong;
0100: /** When in forced mode, the best node leading to a too short line. The line will be
0101: * too short anyway, but this one will lead to a paragraph with fewest demerits.
0102: */
0103: private KnuthNode lastTooShort;
0104: /** The node to be reactivated if no set of feasible breakpoints can be found for this
0105: * paragraph.
0106: */
0107: private KnuthNode lastDeactivated;
0108:
0109: /** Alignment of the paragraph/page. One of EN_START, EN_JUSTIFY, etc. */
0110: protected int alignment;
0111: /** Alignment of the paragraph's last line. */
0112: protected int alignmentLast;
0113: /** Used to handle the text-indent property (indent the first line of a paragraph). */
0114: protected boolean bFirst;
0115:
0116: /**
0117: * The set of active nodes in ascending line order. For each line l, activeLines[2l] contains a
0118: * link to l's first active node, and activeLines[2l+1] a link to l's last active node. The
0119: * line number l corresponds to the number of the line ending at the node's breakpoint.
0120: */
0121: protected KnuthNode[] activeLines;
0122:
0123: /**
0124: * The number of active nodes.
0125: */
0126: protected int activeNodeCount;
0127:
0128: /**
0129: * The lowest available line in the set of active nodes.
0130: */
0131: protected int startLine = 0;
0132:
0133: /**
0134: * The highest + 1 available line in the set of active nodes.
0135: */
0136: protected int endLine = 0;
0137:
0138: /**
0139: * The total width of all elements handled so far.
0140: */
0141: protected int totalWidth;
0142:
0143: /**
0144: * The total stretch of all elements handled so far.
0145: */
0146: protected int totalStretch = 0;
0147:
0148: /**
0149: * The total shrink of all elements handled so far.
0150: */
0151: protected int totalShrink = 0;
0152:
0153: protected BestRecords best;
0154:
0155: /** @see #isPartOverflowRecoveryActivated() */
0156: private boolean partOverflowRecoveryActivated = true;
0157: private KnuthNode lastRecovered;
0158:
0159: /**
0160: * Create a new instance.
0161: * @param align alignment of the paragraph/page. One of EN_START, EN_JUSTIFY, etc. For
0162: * pages EN_BEFORE, EN_AFTER are mapped to the corresponding inline properties
0163: * (EN_START, EN_END)
0164: * @param alignLast alignment of the paragraph's last line
0165: * @param first for the text-indent property (indent the first line of a paragraph)
0166: * @param partOverflowRecovery true if too long elements should be moved to the next line/part
0167: * @param maxFlagCount maximum allowed number of consecutive lines ending at a flagged penalty
0168: * item
0169: */
0170: public BreakingAlgorithm(int align, int alignLast, boolean first,
0171: boolean partOverflowRecovery, int maxFlagCount) {
0172: alignment = align;
0173: alignmentLast = alignLast;
0174: bFirst = first;
0175: this .partOverflowRecoveryActivated = partOverflowRecovery;
0176: this .best = new BestRecords();
0177: maxFlaggedPenaltiesCount = maxFlagCount;
0178: }
0179:
0180: /**
0181: * Class recording all the informations of a feasible breaking point.
0182: */
0183: public class KnuthNode {
0184: /** index of the breakpoint represented by this node */
0185: public int position;
0186:
0187: /** number of the line ending at this breakpoint */
0188: public int line;
0189:
0190: /** fitness class of the line ending at this breakpoint. One of 0, 1, 2, 3. */
0191: public int fitness;
0192:
0193: /** accumulated width of the KnuthElements up to after this breakpoint. */
0194: public int totalWidth;
0195:
0196: /** accumulated stretchability of the KnuthElements up to after this breakpoint. */
0197: public int totalStretch;
0198:
0199: /** accumulated shrinkability of the KnuthElements up to after this breakpoint. */
0200: public int totalShrink;
0201:
0202: /** adjustment ratio if the line ends at this breakpoint */
0203: public double adjustRatio;
0204:
0205: /** available stretch of the line ending at this breakpoint */
0206: public int availableShrink;
0207:
0208: /** available shrink of the line ending at this breakpoint */
0209: public int availableStretch;
0210:
0211: /** difference between target and actual line width */
0212: public int difference;
0213:
0214: /** minimum total demerits up to this breakpoint */
0215: public double totalDemerits;
0216:
0217: /** best node for the preceding breakpoint */
0218: public KnuthNode previous;
0219:
0220: /** next possible node in the same line */
0221: public KnuthNode next;
0222:
0223: /**
0224: * Holds the number of subsequent recovery attempty that are made to get content fit
0225: * into a line.
0226: */
0227: public int fitRecoveryCounter = 0;
0228:
0229: public KnuthNode(int position, int line, int fitness,
0230: int totalWidth, int totalStretch, int totalShrink,
0231: double adjustRatio, int availableShrink,
0232: int availableStretch, int difference,
0233: double totalDemerits, KnuthNode previous) {
0234: this .position = position;
0235: this .line = line;
0236: this .fitness = fitness;
0237: this .totalWidth = totalWidth;
0238: this .totalStretch = totalStretch;
0239: this .totalShrink = totalShrink;
0240: this .adjustRatio = adjustRatio;
0241: this .availableShrink = availableShrink;
0242: this .availableStretch = availableStretch;
0243: this .difference = difference;
0244: this .totalDemerits = totalDemerits;
0245: this .previous = previous;
0246: }
0247:
0248: public String toString() {
0249: return "<KnuthNode at " + position + " " + totalWidth + "+"
0250: + totalStretch + "-" + totalShrink + " line:"
0251: + line + " prev:"
0252: + (previous != null ? previous.position : -1)
0253: + " dem:" + totalDemerits + ">";
0254: }
0255: }
0256:
0257: /** Class that stores, for each fitness class, the best active node that could start
0258: * a line of the corresponding fitness ending at the current element.
0259: */
0260: protected class BestRecords {
0261: private static final double INFINITE_DEMERITS = Double.POSITIVE_INFINITY;
0262: //private static final double INFINITE_DEMERITS = 1E11;
0263:
0264: private double[] bestDemerits = new double[4];
0265: private KnuthNode[] bestNode = new KnuthNode[4];
0266: private double[] bestAdjust = new double[4];
0267: private int[] bestDifference = new int[4];
0268: private int[] bestAvailableShrink = new int[4];
0269: private int[] bestAvailableStretch = new int[4];
0270: /** Points to the fitness class which currently leads to the best demerits. */
0271: private int bestIndex = -1;
0272:
0273: public BestRecords() {
0274: reset();
0275: }
0276:
0277: /** Registers the new best active node for the given fitness class.
0278: * @param demerits the total demerits of the new optimal set of breakpoints
0279: * @param node the node starting the line ending at the current element
0280: * @param adjust adjustment ratio of the current line
0281: * @param availableShrink how much the current line can be shrinked
0282: * @param availableStretch how much the current line can be stretched
0283: * @param difference difference between the width of the considered line and the
0284: * width of the "real" line
0285: * @param fitness fitness class of the current line
0286: */
0287: public void addRecord(double demerits, KnuthNode node,
0288: double adjust, int availableShrink,
0289: int availableStretch, int difference, int fitness) {
0290: if (demerits > bestDemerits[fitness]) {
0291: log
0292: .error("New demerits value greater than the old one");
0293: }
0294: bestDemerits[fitness] = demerits;
0295: bestNode[fitness] = node;
0296: bestAdjust[fitness] = adjust;
0297: bestAvailableShrink[fitness] = availableShrink;
0298: bestAvailableStretch[fitness] = availableStretch;
0299: bestDifference[fitness] = difference;
0300: if (bestIndex == -1 || demerits < bestDemerits[bestIndex]) {
0301: bestIndex = fitness;
0302: }
0303: }
0304:
0305: public boolean hasRecords() {
0306: return (bestIndex != -1);
0307: }
0308:
0309: /**
0310: * @param fitness fitness class (0, 1, 2 or 3, i.e. "tight" to "very loose")
0311: * @return true if there is a set of feasible breakpoints registered for the
0312: * given fitness.
0313: */
0314: public boolean notInfiniteDemerits(int fitness) {
0315: return (bestDemerits[fitness] != INFINITE_DEMERITS);
0316: }
0317:
0318: public double getDemerits(int fitness) {
0319: return bestDemerits[fitness];
0320: }
0321:
0322: public KnuthNode getNode(int fitness) {
0323: return bestNode[fitness];
0324: }
0325:
0326: public double getAdjust(int fitness) {
0327: return bestAdjust[fitness];
0328: }
0329:
0330: public int getAvailableShrink(int fitness) {
0331: return bestAvailableShrink[fitness];
0332: }
0333:
0334: public int getAvailableStretch(int fitness) {
0335: return bestAvailableStretch[fitness];
0336: }
0337:
0338: public int getDifference(int fitness) {
0339: return bestDifference[fitness];
0340: }
0341:
0342: public double getMinDemerits() {
0343: if (bestIndex != -1) {
0344: return getDemerits(bestIndex);
0345: } else {
0346: // anyway, this should never happen
0347: return INFINITE_DEMERITS;
0348: }
0349: }
0350:
0351: /** Reset when a new breakpoint is being considered. */
0352: public void reset() {
0353: for (int i = 0; i < 4; i++) {
0354: bestDemerits[i] = INFINITE_DEMERITS;
0355: // there is no need to reset the other arrays
0356: }
0357: bestIndex = -1;
0358: }
0359: }
0360:
0361: /**
0362: * @return the number of times the algorithm should try to move overflowing content to the
0363: * next line/page.
0364: */
0365: protected int getMaxRecoveryAttempts() {
0366: return MAX_RECOVERY_ATTEMPTS;
0367: }
0368:
0369: /**
0370: * Controls the behaviour of the algorithm in cases where the first element of a part
0371: * overflows a line/page.
0372: * @return true if the algorithm should try to send the element to the next line/page.
0373: */
0374: protected boolean isPartOverflowRecoveryActivated() {
0375: return this .partOverflowRecoveryActivated;
0376: }
0377:
0378: /** Empty method, hook for subclasses. Called before determining the optimal
0379: * breakpoints corresponding to a given active node.
0380: * @param total number of lines for the active node
0381: * @param demerits total demerits of the paragraph for the active node
0382: */
0383: public abstract void updateData1(int total, double demerits);
0384:
0385: /** Empty method, hook for subclasses. Called when determining the optimal breakpoints
0386: * for a given active node.
0387: * @param bestActiveNode a node in the chain of best active nodes, corresponding to
0388: * one of the optimal breakpoints
0389: * @param sequence the corresponding paragraph
0390: * @param total the number of lines into which the paragraph will be broken
0391: * @see #calculateBreakPoints(KnuthNode, KnuthSequence, int)
0392: */
0393: public abstract void updateData2(KnuthNode bestActiveNode,
0394: KnuthSequence sequence, int total);
0395:
0396: public void setConstantLineWidth(int lineWidth) {
0397: this .lineWidth = lineWidth;
0398: }
0399:
0400: /** @see #findBreakingPoints(KnuthSequence, int, double, boolean, int) */
0401: public int findBreakingPoints(KnuthSequence par, /*int lineWidth,*/
0402: double threshold, boolean force, int allowedBreaks) {
0403: return findBreakingPoints(par, 0, threshold, force,
0404: allowedBreaks);
0405: }
0406:
0407: /** Finds an optimal set of breakpoints for the given paragraph.
0408: * @param par the paragraph to break
0409: * @param startIndex index of the Knuth element at which the breaking must start
0410: * @param threshold upper bound of the adjustment ratio
0411: * @param force true if a set of breakpoints must be found even if there are no
0412: * feasible ones
0413: * @param allowedBreaks one of ONLY_FORCED_BREAKS, NO_FLAGGED_PENALTIES, ALL_BREAKS
0414: */
0415: public int findBreakingPoints(KnuthSequence par, int startIndex,
0416: /*int lineWidth,*/
0417: double threshold, boolean force, int allowedBreaks) {
0418: this .par = par;
0419: this .threshold = threshold;
0420: this .force = force;
0421: //this.lineWidth = lineWidth;
0422: initialize();
0423:
0424: activeLines = new KnuthNode[20];
0425:
0426: // reset lastTooShort and lastTooLong, as they could be not null
0427: // because of previous calls to findBreakingPoints
0428: lastTooShort = lastTooLong = null;
0429: // reset startLine and endLine
0430: startLine = endLine = 0;
0431: // current element in the paragraph
0432: KnuthElement this Element = null;
0433: // previous element in the paragraph is a KnuthBox?
0434: boolean previousIsBox = false;
0435:
0436: // index of the first KnuthBox in the sequence
0437: int firstBoxIndex = startIndex;
0438: if (alignment != org.apache.fop.fo.Constants.EN_CENTER) {
0439: while (par.size() > firstBoxIndex
0440: && !((KnuthElement) par.get(firstBoxIndex)).isBox()) {
0441: firstBoxIndex++;
0442: }
0443: }
0444:
0445: // create an active node representing the starting point
0446: activeLines = new KnuthNode[20];
0447: addNode(0, createNode(firstBoxIndex, 0, 1, 0, 0, 0, 0, 0, 0, 0,
0448: 0, null));
0449:
0450: if (log.isTraceEnabled()) {
0451: log.trace("Looping over " + (par.size() - startIndex)
0452: + " elements");
0453: }
0454:
0455: KnuthNode lastForced = getNode(0);
0456:
0457: // main loop
0458: for (int i = startIndex; i < par.size(); i++) {
0459: this Element = getElement(i);
0460: if (this Element.isBox()) {
0461: // a KnuthBox object is not a legal line break
0462: totalWidth += this Element.getW();
0463: previousIsBox = true;
0464: handleBox((KnuthBox) this Element);
0465: } else if (this Element.isGlue()) {
0466: // a KnuthGlue object is a legal line break
0467: // only if the previous object is a KnuthBox
0468: // consider these glues according to the value of allowedBreaks
0469: if (previousIsBox
0470: && !(allowedBreaks == ONLY_FORCED_BREAKS)) {
0471: considerLegalBreak(this Element, i);
0472: }
0473: totalWidth += this Element.getW();
0474: totalStretch += this Element.getY();
0475: totalShrink += this Element.getZ();
0476: previousIsBox = false;
0477: } else {
0478: // a KnuthPenalty is a legal line break
0479: // only if its penalty is not infinite;
0480: // consider all penalties, non-flagged penalties or non-forcing penalties
0481: // according to the value of allowedBreaks
0482: if (((KnuthPenalty) this Element).getP() < KnuthElement.INFINITE
0483: && (!(allowedBreaks == NO_FLAGGED_PENALTIES) || !(((KnuthPenalty) this Element)
0484: .isFlagged()))
0485: && (!(allowedBreaks == ONLY_FORCED_BREAKS) || ((KnuthPenalty) this Element)
0486: .getP() == -KnuthElement.INFINITE)) {
0487: considerLegalBreak(this Element, i);
0488: }
0489: previousIsBox = false;
0490: }
0491: if (activeNodeCount == 0) {
0492: if (!force) {
0493: log
0494: .debug("Could not find a set of breaking points "
0495: + threshold);
0496: return 0;
0497: }
0498: // lastDeactivated was a "good" break, while lastTooShort and lastTooLong
0499: // were "bad" breaks since the beginning;
0500: // if it is not the node we just restarted from, lastDeactivated can
0501: // replace either lastTooShort or lastTooLong
0502: if (lastDeactivated != null
0503: && lastDeactivated != lastForced) {
0504: if (lastDeactivated.adjustRatio > 0) {
0505: lastTooShort = lastDeactivated;
0506: } else {
0507: lastTooLong = lastDeactivated;
0508: }
0509: }
0510: if (lastTooShort == null
0511: || lastForced.position == lastTooShort.position) {
0512: if (isPartOverflowRecoveryActivated()) {
0513: if (this .lastRecovered == null) {
0514: this .lastRecovered = lastTooLong;
0515: if (log.isDebugEnabled()) {
0516: log.debug("Recovery point: "
0517: + lastRecovered);
0518: }
0519: }
0520: // content would overflow, insert empty line/page and try again
0521: KnuthNode node = createNode(
0522: lastTooLong.previous.position,
0523: lastTooLong.previous.line + 1, 1, 0, 0,
0524: 0, 0, 0, 0, 0, 0, lastTooLong.previous);
0525: lastForced = node;
0526: node.fitRecoveryCounter = lastTooLong.previous.fitRecoveryCounter + 1;
0527: if (log.isDebugEnabled()) {
0528: log
0529: .debug("first part doesn't fit into line, recovering: "
0530: + node.fitRecoveryCounter);
0531: }
0532: if (node.fitRecoveryCounter > getMaxRecoveryAttempts()) {
0533: while (lastForced.fitRecoveryCounter > 0) {
0534: lastForced = lastForced.previous;
0535: lastDeactivated = lastForced.previous;
0536: startLine--;
0537: endLine--;
0538: }
0539: lastForced = this .lastRecovered;
0540: this .lastRecovered = null;
0541: startLine = lastForced.line;
0542: endLine = lastForced.line;
0543: log.debug("rolled back...");
0544: }
0545: } else {
0546: lastForced = lastTooLong;
0547: }
0548: } else {
0549: lastForced = lastTooShort;
0550: this .lastRecovered = null;
0551: }
0552:
0553: if (log.isDebugEnabled()) {
0554: log.debug("Restarting at node " + lastForced);
0555: }
0556: i = restartFrom(lastForced, i);
0557: }
0558: }
0559: finish();
0560: if (log.isTraceEnabled()) {
0561: log.trace("Main loop completed " + activeNodeCount);
0562: log.trace("Active nodes=" + toString(""));
0563: }
0564:
0565: // there is at least one set of breaking points
0566: // select one or more active nodes, removing the others from the list
0567: int line = filterActiveNodes();
0568:
0569: // for each active node, create a set of breaking points
0570: for (int i = startLine; i < endLine; i++) {
0571: for (KnuthNode node = getNode(i); node != null; node = node.next) {
0572: updateData1(node.line, node.totalDemerits);
0573: calculateBreakPoints(node, par, node.line);
0574: }
0575: }
0576:
0577: activeLines = null;
0578: return line;
0579: }
0580:
0581: /**
0582: * This method tries to find the context FO for a position in a KnuthSequence.
0583: * @param seq the KnuthSequence to inspect
0584: * @param position the index of the position in the KnuthSequence
0585: * @return the requested context FO note or null, if no context node could be determined
0586: */
0587: private FONode findContextFO(KnuthSequence seq, int position) {
0588: ListElement el = seq.getElement(position);
0589: while (el.getLayoutManager() == null
0590: && position < seq.size() - 1) {
0591: position++;
0592: el = seq.getElement(position);
0593: }
0594: Position pos = (el != null ? el.getPosition() : null);
0595: LayoutManager lm = (pos != null ? pos.getLM() : null);
0596: while (pos instanceof NonLeafPosition) {
0597: pos = ((NonLeafPosition) pos).getPosition();
0598: if (pos != null && pos.getLM() != null) {
0599: lm = pos.getLM();
0600: }
0601: }
0602: if (lm != null) {
0603: return lm.getFObj();
0604: } else {
0605: return null;
0606: }
0607: }
0608:
0609: /** Resets the algorithm's variables. */
0610: protected void initialize() {
0611: this .totalWidth = 0;
0612: this .totalStretch = 0;
0613: this .totalShrink = 0;
0614: }
0615:
0616: /** Creates a new active node for a feasible breakpoint at the given position. Only
0617: * called in forced mode.
0618: * @param position index of the element in the Knuth sequence
0619: * @param line number of the line ending at the breakpoint
0620: * @param fitness fitness class of the line ending at the breakpoint. One of 0, 1, 2, 3.
0621: * @param totalWidth accumulated width of the KnuthElements up to after the breakpoint
0622: * @param totalStretch accumulated stretchability of the KnuthElements up to after the
0623: * breakpoint
0624: * @param totalShrink accumulated shrinkability of the KnuthElements up to after the
0625: * breakpoint
0626: * @param adjustRatio adjustment ratio if the line ends at this breakpoint
0627: * @param availableShrink available stretch of the line ending at this breakpoint
0628: * @param availableStretch available shrink of the line ending at this breakpoint
0629: * @param difference difference between target and actual line width
0630: * @param totalDemerits minimum total demerits up to the breakpoint
0631: * @param previous active node for the preceding breakpoint
0632: */
0633: protected KnuthNode createNode(int position, int line, int fitness,
0634: int totalWidth, int totalStretch, int totalShrink,
0635: double adjustRatio, int availableShrink,
0636: int availableStretch, int difference, double totalDemerits,
0637: KnuthNode previous) {
0638: return new KnuthNode(position, line, fitness, totalWidth,
0639: totalStretch, totalShrink, adjustRatio,
0640: availableShrink, availableStretch, difference,
0641: totalDemerits, previous);
0642: }
0643:
0644: /** Creates a new active node for a break from the best active node of the given
0645: * fitness class to the element at the given position.
0646: * @see #createNode(int, int, int, int, int, int, double, int, int, int, double, KnuthNode)
0647: * @see BreakingAlgorithm.BestRecords
0648: */
0649: protected KnuthNode createNode(int position, int line, int fitness,
0650: int totalWidth, int totalStretch, int totalShrink) {
0651: return new KnuthNode(position, line, fitness, totalWidth,
0652: totalStretch, totalShrink, best.getAdjust(fitness),
0653: best.getAvailableShrink(fitness), best
0654: .getAvailableStretch(fitness), best
0655: .getDifference(fitness), best
0656: .getDemerits(fitness), best.getNode(fitness));
0657: }
0658:
0659: /** Empty method, hook for subclasses. */
0660: protected void handleBox(KnuthBox box) {
0661: }
0662:
0663: protected int restartFrom(KnuthNode restartingNode, int currentIndex) {
0664: restartingNode.totalDemerits = 0;
0665: addNode(restartingNode.line, restartingNode);
0666: startLine = restartingNode.line;
0667: endLine = startLine + 1;
0668: totalWidth = restartingNode.totalWidth;
0669: totalStretch = restartingNode.totalStretch;
0670: totalShrink = restartingNode.totalShrink;
0671: lastTooShort = null;
0672: lastTooLong = null;
0673: // the width, stretch and shrink already include the width,
0674: // stretch and shrink of the suppressed glues;
0675: // advance in the sequence in order to avoid taking into account
0676: // these elements twice
0677: int restartingIndex = restartingNode.position;
0678: while (restartingIndex + 1 < par.size()
0679: && !(getElement(restartingIndex + 1).isBox())) {
0680: restartingIndex++;
0681: }
0682: return restartingIndex;
0683: }
0684:
0685: /** Determines if the given breakpoint is a feasible breakpoint. That is, if a decent
0686: * line may be built between one of the currently active nodes and this breakpoint.
0687: * @param element the paragraph's element to consider
0688: * @param elementIdx the element's index inside the paragraph
0689: */
0690: protected void considerLegalBreak(KnuthElement element,
0691: int elementIdx) {
0692:
0693: if (log.isTraceEnabled()) {
0694: log.trace("considerLegalBreak() at " + elementIdx + " ("
0695: + totalWidth + "+" + totalStretch + "-"
0696: + totalShrink + "), parts/lines: " + startLine
0697: + "-" + endLine);
0698: log.trace("\tCurrent active node list: " + activeNodeCount
0699: + " " + this .toString("\t"));
0700: }
0701:
0702: lastDeactivated = null;
0703: lastTooLong = null;
0704: for (int line = startLine; line < endLine; line++) {
0705: for (KnuthNode node = getNode(line); node != null; node = node.next) {
0706: if (node.position == elementIdx) {
0707: continue;
0708: }
0709: int difference = computeDifference(node, element,
0710: elementIdx);
0711: double r = computeAdjustmentRatio(node, difference);
0712: int availableShrink = totalShrink - node.totalShrink;
0713: int availableStretch = totalStretch - node.totalStretch;
0714: if (log.isTraceEnabled()) {
0715: log.trace("\tr=" + r + " difference=" + difference);
0716: log.trace("\tline=" + line);
0717: }
0718:
0719: // The line would be too long.
0720: if (r < -1 || element.isForcedBreak()) {
0721: // Deactivate node.
0722: if (log.isTraceEnabled()) {
0723: log.trace("Removing " + node);
0724: }
0725: removeNode(line, node);
0726: lastDeactivated = compareNodes(lastDeactivated,
0727: node);
0728: }
0729:
0730: // The line is within the available shrink and the threshold.
0731: if (r >= -1 && r <= threshold) {
0732: int fitnessClass = computeFitness(r);
0733: double demerits = computeDemerits(node, element,
0734: fitnessClass, r);
0735:
0736: if (log.isTraceEnabled()) {
0737: log.trace("\tDemerits=" + demerits);
0738: log.trace("\tFitness class=" + fitnessClass);
0739: }
0740:
0741: if (demerits < best.getDemerits(fitnessClass)) {
0742: // updates best demerits data
0743: best.addRecord(demerits, node, r,
0744: availableShrink, availableStretch,
0745: difference, fitnessClass);
0746: lastTooShort = null;
0747: }
0748: }
0749:
0750: // The line is way too short, but we are in forcing mode, so a node is
0751: // calculated and stored in lastValidNode.
0752: if (force && (r <= -1 || r > threshold)) {
0753: int fitnessClass = computeFitness(r);
0754: double demerits = computeDemerits(node, element,
0755: fitnessClass, r);
0756: int newWidth = totalWidth;
0757: int newStretch = totalStretch;
0758: int newShrink = totalShrink;
0759:
0760: // add the width, stretch and shrink of glue elements after
0761: // the break
0762: // this does not affect the dimension of the line / page, only
0763: // the values stored in the node; these would be as if the break
0764: // was just before the next box element, thus ignoring glues and
0765: // penalties between the "real" break and the following box
0766: for (int i = elementIdx; i < par.size(); i++) {
0767: KnuthElement tempElement = getElement(i);
0768: if (tempElement.isBox()) {
0769: break;
0770: } else if (tempElement.isGlue()) {
0771: newWidth += tempElement.getW();
0772: newStretch += tempElement.getY();
0773: newShrink += tempElement.getZ();
0774: } else if (tempElement.isForcedBreak()
0775: && i != elementIdx) {
0776: break;
0777: }
0778: }
0779:
0780: if (r <= -1) {
0781: if (lastTooLong == null
0782: || demerits < lastTooLong.totalDemerits) {
0783: lastTooLong = createNode(elementIdx,
0784: line + 1, fitnessClass, newWidth,
0785: newStretch, newShrink, r,
0786: availableShrink, availableStretch,
0787: difference, demerits, node);
0788: if (log.isTraceEnabled()) {
0789: log.trace("Picking tooLong "
0790: + lastTooLong);
0791: }
0792: }
0793: } else {
0794: if (lastTooShort == null
0795: || demerits <= lastTooShort.totalDemerits) {
0796: if (considerTooShort) {
0797: //consider possibilities which are too short
0798: best.addRecord(demerits, node, r,
0799: availableShrink,
0800: availableStretch, difference,
0801: fitnessClass);
0802: }
0803: lastTooShort = createNode(elementIdx,
0804: line + 1, fitnessClass, newWidth,
0805: newStretch, newShrink, r,
0806: availableShrink, availableStretch,
0807: difference, demerits, node);
0808: if (log.isTraceEnabled()) {
0809: log.trace("Picking tooShort "
0810: + lastTooShort);
0811: }
0812: }
0813: }
0814: }
0815: }
0816: addBreaks(line, elementIdx);
0817: }
0818: }
0819:
0820: /**
0821: * Adds new active nodes for breaks at the given element.
0822: * @param line number of the previous line; this element will end line number (line+1)
0823: * @param elementIdx the element's index
0824: */
0825: private void addBreaks(int line, int elementIdx) {
0826: if (!best.hasRecords()) {
0827: return;
0828: }
0829:
0830: int newWidth = totalWidth;
0831: int newStretch = totalStretch;
0832: int newShrink = totalShrink;
0833:
0834: // add the width, stretch and shrink of glue elements after
0835: // the break
0836: // this does not affect the dimension of the line / page, only
0837: // the values stored in the node; these would be as if the break
0838: // was just before the next box element, thus ignoring glues and
0839: // penalties between the "real" break and the following box
0840: for (int i = elementIdx; i < par.size(); i++) {
0841: KnuthElement tempElement = getElement(i);
0842: if (tempElement.isBox()) {
0843: break;
0844: } else if (tempElement.isGlue()) {
0845: newWidth += tempElement.getW();
0846: newStretch += tempElement.getY();
0847: newShrink += tempElement.getZ();
0848: } else if (tempElement.isForcedBreak() && i != elementIdx) {
0849: break;
0850: }
0851: }
0852:
0853: // add nodes to the active nodes list
0854: double minimumDemerits = best.getMinDemerits()
0855: + incompatibleFitnessDemerit;
0856: for (int i = 0; i <= 3; i++) {
0857: if (best.notInfiniteDemerits(i)
0858: && best.getDemerits(i) <= minimumDemerits) {
0859: // the nodes in activeList must be ordered
0860: // by line number and position;
0861: if (log.isTraceEnabled()) {
0862: log.trace("\tInsert new break in list of "
0863: + activeNodeCount + " from fitness class "
0864: + i);
0865: }
0866: KnuthNode newNode = createNode(elementIdx, line + 1, i,
0867: newWidth, newStretch, newShrink);
0868: addNode(line + 1, newNode);
0869: }
0870: }
0871: best.reset();
0872: }
0873:
0874: /**
0875: * Return the difference between the natural width of a line that would be made
0876: * between the given active node and the given element, and the available width of the
0877: * real line.
0878: * @param activeNode node for the previous breakpoint
0879: * @param element currently considered breakpoint
0880: * @return The difference in width. Positive numbers mean extra space in the line,
0881: * negative number that the line overflows.
0882: */
0883: protected int computeDifference(KnuthNode activeNode,
0884: KnuthElement element, int elementIndex) {
0885: // compute the adjustment ratio
0886: int actualWidth = totalWidth - activeNode.totalWidth;
0887: if (element.isPenalty()) {
0888: actualWidth += element.getW();
0889: }
0890: return getLineWidth() - actualWidth;
0891: }
0892:
0893: /**
0894: * Return the adjust ration needed to make up for the difference. A ration of
0895: * <ul>
0896: * <li>0 means that the break has the exact right width</li>
0897: * <li>>= -1 && < 0 means that the break is wider than the line,
0898: * but within the minimim values of the glues.</li>
0899: * <li>>0 && < 1 means that the break is smaller than the line width,
0900: * but within the maximum values of the glues.</li>
0901: * <li>> 1 means that the break is too small to make up for the glues.</li>
0902: * </ul>
0903: * @param activeNode
0904: * @param difference
0905: * @return The ration.
0906: */
0907: protected double computeAdjustmentRatio(KnuthNode activeNode,
0908: int difference) {
0909: // compute the adjustment ratio
0910: if (difference > 0) {
0911: int maxAdjustment = totalStretch - activeNode.totalStretch;
0912: if (maxAdjustment > 0) {
0913: return (double) difference / maxAdjustment;
0914: } else {
0915: return INFINITE_RATIO;
0916: }
0917: } else if (difference < 0) {
0918: int maxAdjustment = totalShrink - activeNode.totalShrink;
0919: if (maxAdjustment > 0) {
0920: return (double) difference / maxAdjustment;
0921: } else {
0922: return -INFINITE_RATIO;
0923: }
0924: } else {
0925: return 0;
0926: }
0927: }
0928:
0929: /**
0930: * Figure out the fitness class of this line (tight, loose,
0931: * very tight or very loose).
0932: * See the section on "More Bells and Whistles" in Knuth's
0933: * "Breaking Paragraphs Into Lines".
0934: * @param r
0935: * @return the fitness class
0936: */
0937: private int computeFitness(double r) {
0938: if (r < -0.5) {
0939: return 0;
0940: } else if (r <= 0.5) {
0941: return 1;
0942: } else if (r <= 1) {
0943: return 2;
0944: } else {
0945: return 3;
0946: }
0947: }
0948:
0949: /**
0950: * Computes the demerits of the current breaking (that is, up to the given element),
0951: * if the next-to-last chosen breakpoint is the given active node. This adds to the
0952: * total demerits of the given active node, the demerits of a line starting at this
0953: * node and ending at the given element.
0954: * @param activeNode considered preceding line break
0955: * @param element considered current line break
0956: * @param fitnessClass fitness of the current line
0957: * @param r adjustment ratio for the current line
0958: * @return the demerit of the current line
0959: */
0960: protected double computeDemerits(KnuthNode activeNode,
0961: KnuthElement element, int fitnessClass, double r) {
0962: double demerits = 0;
0963: // compute demerits
0964: double f = Math.abs(r);
0965: f = 1 + 100 * f * f * f;
0966: if (element.isPenalty() && element.getP() >= 0) {
0967: f += element.getP();
0968: demerits = f * f;
0969: } else if (element.isPenalty() && !element.isForcedBreak()) {
0970: double penalty = element.getP();
0971: demerits = f * f - penalty * penalty;
0972: } else {
0973: demerits = f * f;
0974: }
0975:
0976: if (element.isPenalty()
0977: && ((KnuthPenalty) element).isFlagged()
0978: && getElement(activeNode.position).isPenalty()
0979: && ((KnuthPenalty) getElement(activeNode.position))
0980: .isFlagged()) {
0981: // add demerit for consecutive breaks at flagged penalties
0982: demerits += repeatedFlaggedDemerit;
0983: // there are at least two consecutive lines ending with a flagged penalty;
0984: // check if the previous line end with a flagged penalty too,
0985: // and if this situation is allowed
0986: int flaggedPenaltiesCount = 2;
0987: for (KnuthNode prevNode = activeNode.previous; prevNode != null
0988: && flaggedPenaltiesCount <= maxFlaggedPenaltiesCount; prevNode = prevNode.previous) {
0989: KnuthElement prevElement = getElement(prevNode.position);
0990: if (prevElement.isPenalty()
0991: && ((KnuthPenalty) prevElement).isFlagged()) {
0992: // the previous line ends with a flagged penalty too
0993: flaggedPenaltiesCount++;
0994: } else {
0995: // the previous line does not end with a flagged penalty,
0996: // exit the loop
0997: break;
0998: }
0999: }
1000: if (maxFlaggedPenaltiesCount >= 1
1001: && flaggedPenaltiesCount > maxFlaggedPenaltiesCount) {
1002: // add infinite demerits, so this break will not be chosen
1003: // unless there isn't any alternative break
1004: demerits += BestRecords.INFINITE_DEMERITS;
1005: }
1006: }
1007: if (Math.abs(fitnessClass - activeNode.fitness) > 1) {
1008: // add demerit for consecutive breaks
1009: // with very different fitness classes
1010: demerits += incompatibleFitnessDemerit;
1011: }
1012: demerits += activeNode.totalDemerits;
1013: return demerits;
1014: }
1015:
1016: protected void finish() {
1017: }
1018:
1019: /**
1020: * Return the element at index idx in the paragraph.
1021: * @param idx index of the element.
1022: * @return the element at index idx in the paragraph.
1023: */
1024: protected KnuthElement getElement(int idx) {
1025: return (KnuthElement) par.get(idx);
1026: }
1027:
1028: /**
1029: * Compare two KnuthNodes and return the node with the least demerit.
1030: * @param node1 The first knuth node.
1031: * @param node2 The other knuth node.
1032: * @return the node with the least demerit.
1033: */
1034: protected KnuthNode compareNodes(KnuthNode node1, KnuthNode node2) {
1035: if (node1 == null || node2.position > node1.position) {
1036: return node2;
1037: }
1038: if (node2.position == node1.position) {
1039: if (node2.totalDemerits < node1.totalDemerits) {
1040: return node2;
1041: }
1042: }
1043: return node1;
1044: }
1045:
1046: /**
1047: * Add a node at the end of the given line's existing active nodes.
1048: * If this is the first node in the line, adjust endLine accordingly.
1049: * @param line number of the line ending at the node's corresponding breakpoint
1050: * @param node the active node to add
1051: */
1052: protected void addNode(int line, KnuthNode node) {
1053: int headIdx = line * 2;
1054: if (headIdx >= activeLines.length) {
1055: KnuthNode[] oldList = activeLines;
1056: activeLines = new KnuthNode[headIdx + headIdx];
1057: System
1058: .arraycopy(oldList, 0, activeLines, 0,
1059: oldList.length);
1060: }
1061: node.next = null;
1062: if (activeLines[headIdx + 1] != null) {
1063: activeLines[headIdx + 1].next = node;
1064: } else {
1065: activeLines[headIdx] = node;
1066: endLine = line + 1;
1067: }
1068: activeLines[headIdx + 1] = node;
1069: activeNodeCount++;
1070: }
1071:
1072: /**
1073: * Remove the given active node registered for the given line. If there are no more active nodes
1074: * for this line, adjust the startLine accordingly.
1075: * @param line number of the line ending at the node's corresponding breakpoint
1076: * @param node the node to deactivate
1077: */
1078: protected void removeNode(int line, KnuthNode node) {
1079: int headIdx = line * 2;
1080: KnuthNode n = getNode(line);
1081: if (n != node) {
1082: // nodes could be rightly deactivated in a different order
1083: KnuthNode prevNode = null;
1084: while (n != node) {
1085: prevNode = n;
1086: n = n.next;
1087: }
1088: prevNode.next = n.next;
1089: if (prevNode.next == null) {
1090: activeLines[headIdx + 1] = prevNode;
1091: }
1092: } else {
1093: activeLines[headIdx] = node.next;
1094: if (node.next == null) {
1095: activeLines[headIdx + 1] = null;
1096: }
1097: while (startLine < endLine && getNode(startLine) == null) {
1098: startLine++;
1099: }
1100: }
1101: activeNodeCount--;
1102: }
1103:
1104: /**
1105: * Returns the first active node for the given line.
1106: * @param line the line/part number
1107: * @return the requested active node
1108: */
1109: protected KnuthNode getNode(int line) {
1110: return activeLines[line * 2];
1111: }
1112:
1113: /**
1114: * Returns the line/part width of a given line/part.
1115: * @param line the line/part number
1116: * @return the width/length in millipoints
1117: */
1118: protected int getLineWidth(int line) {
1119: if (this .lineWidth < 0) {
1120: throw new IllegalStateException(
1121: "lineWidth must be set"
1122: + (this .lineWidth != 0 ? " and positive, but it is: "
1123: + this .lineWidth
1124: : ""));
1125: } else {
1126: return this .lineWidth;
1127: }
1128: }
1129:
1130: /** @return the constant line/part width or -1 if there is no such value */
1131: protected int getLineWidth() {
1132: return this .lineWidth;
1133: }
1134:
1135: /**
1136: * Creates a string representation of the active nodes. Used for debugging.
1137: * @param prepend a string to prepend on each entry
1138: * @return the requested string
1139: */
1140: public String toString(String prepend) {
1141: StringBuffer sb = new StringBuffer();
1142: sb.append("[\n");
1143: for (int i = startLine; i < endLine; i++) {
1144: for (KnuthNode node = getNode(i); node != null; node = node.next) {
1145: sb.append(prepend + "\t" + node + ",\n");
1146: }
1147: }
1148: sb.append(prepend + "]");
1149: return sb.toString();
1150: }
1151:
1152: protected abstract int filterActiveNodes();
1153:
1154: /**
1155: * Determines the set of optimal breakpoints corresponding to the given active node.
1156: * @param node the active node
1157: * @param par the corresponding paragraph
1158: * @param total the number of lines into which the paragraph will be broken
1159: */
1160: private void calculateBreakPoints(KnuthNode node,
1161: KnuthSequence par, int total) {
1162: KnuthNode bestActiveNode = node;
1163: // use bestActiveNode to determine the optimum breakpoints
1164: for (int i = node.line; i > 0; i--) {
1165: updateData2(bestActiveNode, par, total);
1166: bestActiveNode = bestActiveNode.previous;
1167: }
1168: }
1169:
1170: /** @return the alignment for normal lines/parts */
1171: public int getAlignment() {
1172: return this .alignment;
1173: }
1174:
1175: /** @return the alignment for the last line/part */
1176: public int getAlignmentLast() {
1177: return this.alignmentLast;
1178: }
1179:
1180: }
|