From a392d777f6ab4c12ce5b6caaf179ad3f18032092 Mon Sep 17 00:00:00 2001 From: Jeremias Maerki Date: Tue, 8 Mar 2005 15:03:06 +0000 Subject: [PATCH] Refactoring of Knuth line breaking code (including some speed improvements) Bugzilla: #32612 Submitted by: Finn Bock git-svn-id: https://svn.apache.org/repos/asf/xmlgraphics/fop/trunk@198474 13f79535-47bb-0310-9956-ffa450edef68 --- .../org/apache/fop/layoutmgr/KnuthBox.java | 8 +- .../apache/fop/layoutmgr/KnuthElement.java | 32 +- .../org/apache/fop/layoutmgr/KnuthGlue.java | 8 +- .../apache/fop/layoutmgr/KnuthParagraph.java | 747 ++++++++++++++++++ .../apache/fop/layoutmgr/KnuthPenalty.java | 12 +- .../fop/layoutmgr/LineLayoutManager.java | 655 ++------------- .../fop/layoutmgr/TextLayoutManager.java | 3 +- src/java/org/apache/fop/traits/MinOptMax.java | 36 +- 8 files changed, 880 insertions(+), 621 deletions(-) create mode 100644 src/java/org/apache/fop/layoutmgr/KnuthParagraph.java diff --git a/src/java/org/apache/fop/layoutmgr/KnuthBox.java b/src/java/org/apache/fop/layoutmgr/KnuthBox.java index 76f56eb4e..8479f77d6 100644 --- a/src/java/org/apache/fop/layoutmgr/KnuthBox.java +++ b/src/java/org/apache/fop/layoutmgr/KnuthBox.java @@ -1,5 +1,5 @@ /* - * Copyright 2004 The Apache Software Foundation. + * Copyright 2004-2005 The Apache Software Foundation. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -47,12 +47,16 @@ public class KnuthBox extends KnuthElement { * @param bAux is this box auxiliary? */ public KnuthBox(int w, int l, int t, int m, Position pos, boolean bAux) { - super(KNUTH_BOX, w, pos, bAux); + super(w, pos, bAux); lead = l; total = t; middle = m; } + public boolean isBox() { + return true; + } + /** * Return the height of this box above the main baseline. */ diff --git a/src/java/org/apache/fop/layoutmgr/KnuthElement.java b/src/java/org/apache/fop/layoutmgr/KnuthElement.java index 77d85555e..74db99634 100644 --- a/src/java/org/apache/fop/layoutmgr/KnuthElement.java +++ b/src/java/org/apache/fop/layoutmgr/KnuthElement.java @@ -1,5 +1,5 @@ /* - * Copyright 2004 The Apache Software Foundation. + * Copyright 2004-2005 The Apache Software Foundation. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -28,13 +28,8 @@ package org.apache.fop.layoutmgr; */ public abstract class KnuthElement { - public static final int KNUTH_BOX = 0; - public static final int KNUTH_GLUE = 1; - public static final int KNUTH_PENALTY = 2; - public static final int INFINITE = 1000; - private int type; private int width; private Position position; private boolean bIsAuxiliary; @@ -48,8 +43,7 @@ public abstract class KnuthElement { * @param pos the Position stored in this element * @param bAux is this an auxiliary element? */ - protected KnuthElement(int t, int w, Position pos, boolean bAux) { - type = t; + protected KnuthElement(int w, Position pos, boolean bAux) { width = w; position = pos; bIsAuxiliary = bAux; @@ -59,21 +53,21 @@ public abstract class KnuthElement { * Return true if this element is a KnuthBox. */ public boolean isBox() { - return (type == KNUTH_BOX); + return false; } /** * Return true if this element is a KnuthGlue. */ public boolean isGlue() { - return (type == KNUTH_GLUE); + return false; } /** * Return true if this element is a KnuthPenalty. */ public boolean isPenalty() { - return (type == KNUTH_PENALTY); + return false; } /** @@ -90,6 +84,22 @@ public abstract class KnuthElement { return width; } + public int getP() { + throw new RuntimeException("Element is not a penalty"); + } + + public int getY() { + throw new RuntimeException("Element is not a glue"); + } + + public int getZ() { + throw new RuntimeException("Element is not a glue"); + } + + public boolean isForcedBreak() { + return false; + } + /** * Return the Position stored in this element. */ diff --git a/src/java/org/apache/fop/layoutmgr/KnuthGlue.java b/src/java/org/apache/fop/layoutmgr/KnuthGlue.java index f26b540ce..e377ce351 100644 --- a/src/java/org/apache/fop/layoutmgr/KnuthGlue.java +++ b/src/java/org/apache/fop/layoutmgr/KnuthGlue.java @@ -1,5 +1,5 @@ /* - * Copyright 2004 The Apache Software Foundation. + * Copyright 2004-2005 The Apache Software Foundation. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -58,11 +58,15 @@ public class KnuthGlue extends KnuthElement { * @param bAux is this glue auxiliary? */ public KnuthGlue(int w, int y, int z, Position pos, boolean bAux) { - super(KNUTH_GLUE, w, pos, bAux); + super(w, pos, bAux); stretchability = y; shrinkability = z; } + public boolean isGlue() { + return true; + } + /** * Return the stretchability of this glue. */ diff --git a/src/java/org/apache/fop/layoutmgr/KnuthParagraph.java b/src/java/org/apache/fop/layoutmgr/KnuthParagraph.java new file mode 100644 index 000000000..baf3492d6 --- /dev/null +++ b/src/java/org/apache/fop/layoutmgr/KnuthParagraph.java @@ -0,0 +1,747 @@ +/* + * Copyright 2004-2005 The Apache Software Foundation. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/* $Id$ */ +package org.apache.fop.layoutmgr; + +import java.util.ArrayList; + +import org.apache.commons.logging.Log; +import org.apache.commons.logging.LogFactory; + +import org.apache.fop.traits.MinOptMax; + +/** + * A knuth paragraph + * + * The set is sorted into lines indexed into activeLines. + * The nodes in each line is linked together in a single linked list by the + * KnuthNode.next field. The activeLines array contains a link to the head of + * the linked list in index 'line*2' and a link to the tail at index 'line*2+1'. + *

+ * The set of active nodes can be traversed by + * 

+ * for (int line = startLine; line < endLine; line++) {
+ *     for (KnuthNode node = getNode(line); node != null; node = node.next) {
+ *         // Do something with 'node'
+ *     }
+ * }
+ *
+ */ +public class KnuthParagraph { + // parameters of Knuth's algorithm: + // penalty value for flagged penalties + private int flaggedPenalty = 50; + // demerit for consecutive lines ending at flagged penalties + private int repeatedFlaggedDemerit = 50; + // demerit for consecutive lines belonging to incompatible fitness classes + private int incompatibleFitnessDemerit = 50; + // suggested modification to the "optimum" number of lines + private int looseness = 0; + + /** + * The threshold for considering breaks to be acceptable. + */ + private double threshold; + + /** + * The paragraph of KnuthElements. + */ + private ArrayList par; + + /** + * The width of a line. + */ + private int lineWidth = 0; + private boolean force = false; + + private KnuthNode lastTooLong; + private KnuthNode lastTooShort; + private KnuthNode lastDeactivated; + + /** + * The set of active nodes. + */ + private KnuthNode[] activeLines; + + /** + * The number of active nodes. + */ + private int activeNodeCount; + + /** + * The lowest available line in the set of active nodes. + */ + private int startLine = 0; + + /** + * The highest + 1 available line in the set of active nodes. + */ + private int endLine = 0; + + /** + * The total width of all elements handled so far. + */ + private int totalWidth; + + /** + * The total stretch of all elements handled so far. + */ + private int totalStretch = 0; + + /** + * The total shrink of all elements handled so far. + */ + private int totalShrink = 0; + + private BestRecords best; + private KnuthNode[] positions; + + private static final int INFINITE_RATIO = 1000; + + protected static Log log = LogFactory.getLog(KnuthParagraph.class); + + public KnuthParagraph(ArrayList par) { + this.best = new BestRecords(); + this.par = par; + } + + + // this class represent a feasible breaking point + private class KnuthNode { + // index of the breakpoint represented by this node + public int position; + + // number of the line ending at this breakpoint + public int line; + + // fitness class of the line ending at his breakpoint + public int fitness; + + // accumulated width of the KnuthElements + public int totalWidth; + + public int totalStretch; + + public int totalShrink; + + // adjustment ratio if the line ends at this breakpoint + public double adjustRatio; + + // difference between target and actual line width + public int difference; + + // minimum total demerits up to this breakpoint + public double totalDemerits; + + // best node for the preceding breakpoint + public KnuthNode previous; + + // Next possible node in the same line + public KnuthNode next; + + + public KnuthNode(int position, int line, int fitness, + int totalWidth, int totalStretch, int totalShrink, + double adjustRatio, int difference, + double totalDemerits, KnuthNode previous) { + this.position = position; + this.line = line; + this.fitness = fitness; + this.totalWidth = totalWidth; + this.totalStretch = totalStretch; + this.totalShrink = totalShrink; + this.adjustRatio = adjustRatio; + this.difference = difference; + this.totalDemerits = totalDemerits; + this.previous = previous; + } + + public String toString() { + return ""; + } + } + + // this class stores information about how the nodes + // which could start a line + // ending at the current element + private class BestRecords { + private static final double INFINITE_DEMERITS = Double.POSITIVE_INFINITY; + + private double bestDemerits[] = new double[4]; + private KnuthNode bestNode[] = new KnuthNode[4]; + private double bestAdjust[] = new double[4]; + private int bestDifference[] = new int[4]; + private int bestIndex = -1; + + public BestRecords() { + reset(); + } + + public void addRecord(double demerits, KnuthNode node, double adjust, + int difference, int fitness) { + if (demerits > bestDemerits[fitness]) { + log.error("New demerits value greter than the old one"); + } + bestDemerits[fitness] = demerits; + bestNode[fitness] = node; + bestAdjust[fitness] = adjust; + bestDifference[fitness] = difference; + if (bestIndex == -1 || demerits < bestDemerits[bestIndex]) { + bestIndex = fitness; + } + } + + public boolean hasRecords() { + return (bestIndex != -1); + } + + public boolean notInfiniteDemerits(int fitness) { + return (bestDemerits[fitness] != INFINITE_DEMERITS); + } + + public double getDemerits(int fitness) { + return bestDemerits[fitness]; + } + + public KnuthNode getNode(int fitness) { + return bestNode[fitness]; + } + + public double getAdjust(int fitness) { + return bestAdjust[fitness]; + } + + public int getDifference(int fitness) { + return bestDifference[fitness]; + } + + public double getMinDemerits() { + if (bestIndex != -1) { + return getDemerits(bestIndex); + } else { + // anyway, this should never happen + return INFINITE_DEMERITS; + } + } + + public void reset() { + bestDemerits[0] = INFINITE_DEMERITS; + bestDemerits[1] = INFINITE_DEMERITS; + bestDemerits[2] = INFINITE_DEMERITS; + bestDemerits[3] = INFINITE_DEMERITS; + bestIndex = -1; + } + } + + public int findBreakPoints(int lineWidth, double threshold, boolean force) { + this.lineWidth = lineWidth; + this.totalWidth = 0; + this.totalStretch = 0; + this.totalShrink = 0; + this.threshold = threshold; + this.force = force; + + activeLines = new KnuthNode[20]; + addNode(0, new KnuthNode(0, 0, 1, 0, 0, 0, 0, 0, 0, null)); + + boolean bForced = false; + + // previous element in the paragraph is a KnuthBox + boolean previousIsBox = false; + + if (log.isTraceEnabled()) { + log.trace("Looping over " + par.size() + " box objects"); + } + + KnuthNode lastForced = getNode(0); + + // main loop + for (int i = 0; i < par.size(); i++) { + KnuthElement element = getElement(i); + if (element.isBox()) { + // a KnuthBox object is not a legal line break + totalWidth += element.getW(); + previousIsBox = true; + } else if (element.isGlue()) { + // a KnuthGlue object is a legal line break + // only if the previous object is a KnuthBox + if (previousIsBox) { + considerLegalBreak(element, i); + } + totalWidth += element.getW(); + totalStretch += element.getY(); + totalShrink += element.getZ(); + previousIsBox = false; + } else { + // a KnuthPenalty is a legal line break + // only if its penalty is not infinite + if (element.getP() < KnuthElement.INFINITE) { + considerLegalBreak(element, i); + } + previousIsBox = false; + } + if (activeNodeCount == 0) { + if (!force) { + log.debug("Could not find a set of breaking points " + threshold); + return 0; + } + /* + if (lastForced != null && lastForced.position == lastDeactivated.position) { + lastForced = lastTooShort != null ? lastTooShort : lastTooLong; + } else { + lastForced = lastDeactivated; + } + */ + if (lastTooShort == null || lastForced.position == lastTooShort.position) { + lastForced = lastTooLong; + } else { + lastForced = lastTooShort; + } + + log.debug("Restarting at node " + lastForced); + lastForced.totalDemerits = 0; + addNode(lastForced.line, lastForced); + i = lastForced.position; + startLine = lastForced.line; + endLine = startLine + 1; + totalWidth = lastForced.totalWidth; + totalStretch = lastForced.totalStretch; + totalShrink = lastForced.totalShrink; + lastTooShort = lastTooLong = null; + } + } + if (log.isTraceEnabled()) { + log.trace("Main loop completed " + activeNodeCount); + log.trace("Active nodes=" + toString("")); + } + + // there is at least one set of breaking points + // choose the active node with fewest total demerits + KnuthNode bestActiveNode = findBestNode(); + int line = bestActiveNode.line; +/* + if (looseness != 0) { + // choose the appropriate active node + int s = 0; + double bestDemerits = 0; + for (int i = 0; i < activeList.size(); i++) { + KnuthNode node = getNode(i); + int delta = node.line - line; + if (looseness <= delta && delta < s + || s < delta && delta <= looseness) { + s = delta; + bestActiveNode = node; + bestDemerits = node.totalDemerits; + } else if (delta == s + && node.totalDemerits < bestDemerits) { + bestActiveNode = node; + bestDemerits = node.totalDemerits; + } + } + line = bestActiveNode.line; + } +*/ + // Reverse the list of nodes from bestActiveNode. + positions = new KnuthNode[line]; + // use the chosen node to determine the optimum breakpoints + for (int i = line - 1; i >= 0; i--) { + positions[i] = bestActiveNode; + bestActiveNode = bestActiveNode.previous; + } + activeLines = null; + return positions.length; + } + + private void considerLegalBreak(KnuthElement element, int elementIdx) { + + if (log.isTraceEnabled()) { + log.trace("Feasible breakpoint at " + par.indexOf(element) + " " + totalWidth + "+" + totalStretch + "-" + totalShrink); + log.trace("\tCurrent active node list: " + activeNodeCount + " " + this.toString("\t")); + } + + lastDeactivated = null; + lastTooLong = null; + for (int line = startLine; line < endLine; line++) { + for (KnuthNode node = getNode(line); node != null; node = node.next) { + if (node.position == elementIdx) { + continue; + } + int difference = computeDifference(node, element); + double r = computeAdjustmentRatio(node, difference); + if (log.isTraceEnabled()) { + log.trace("\tr=" + r); + log.trace("\tline=" + line); + } + + // The line would be too long. + if (r < -1 || element.isForcedBreak()) { + // Deactivate node. + if (log.isTraceEnabled()) { + log.trace("Removing " + node); + } + removeNode(line, node); + lastDeactivated = compareNodes(lastDeactivated, node); + } + + // The line is within the available shrink and the threshold. + if (r >= -1 && r <= threshold) { + int fitnessClass = computeFitness(r); + double demerits = computeDemerits(node, element, fitnessClass, r); + + if (log.isTraceEnabled()) { + log.trace("\tDemerits=" + demerits); + log.trace("\tFitness class=" + fitnessClass); + } + + if (demerits < best.getDemerits(fitnessClass)) { + // updates best demerits data + best.addRecord(demerits, node, r, difference, fitnessClass); + } + } + + // The line is way too short, but we are in forcing mode, so a node is + // calculated and stored in lastValidNode. + if (force && (r <= -1 || r > threshold)) { + int fitnessClass = computeFitness(r); + double demerits = computeDemerits(node, element, fitnessClass, r); + if (r <= -1) { + if (lastTooLong == null || demerits < lastTooLong.totalDemerits) { + lastTooLong = new KnuthNode(elementIdx, line + 1, fitnessClass, + totalWidth, totalStretch, totalShrink, + r, difference, demerits, node); + if (log.isTraceEnabled()) { + log.trace("Picking tooLong " + lastTooLong); + } + } + } else { + if (lastTooShort == null || demerits <= lastTooShort.totalDemerits) { + lastTooShort = new KnuthNode(elementIdx, line + 1, fitnessClass, + totalWidth, totalStretch, totalShrink, + r, difference, demerits, node); + if (log.isTraceEnabled()) { + log.trace("Picking tooShort " + lastTooShort); + } + } + } + } + } + addBreaks(line, elementIdx); + } + } + + + private void addBreaks(int line, int elementIdx) { + if (!best.hasRecords()) { + return; + } + + int newWidth = totalWidth; + int newStretch = totalStretch; + int newShrink = totalShrink; + + for (int i = elementIdx; i < par.size(); i++) { + KnuthElement tempElement = getElement(i); + if (tempElement.isBox()) { + break; + } else if (tempElement.isGlue()) { + newWidth += tempElement.getW(); + newStretch += tempElement.getY(); + newShrink += tempElement.getZ(); + } else if (tempElement.isForcedBreak() && i != elementIdx) { + break; + } + } + + // add nodes to the active nodes list + double minimumDemerits = best.getMinDemerits() + incompatibleFitnessDemerit; + for (int i = 0; i <= 3; i++) { + if (best.notInfiniteDemerits(i) && best.getDemerits(i) <= minimumDemerits) { + // the nodes in activeList must be ordered + // by line number and position; + if (log.isTraceEnabled()) { + log.trace("\tInsert new break in list of " + activeNodeCount); + } + KnuthNode newNode = new KnuthNode(elementIdx, line + 1, i, + newWidth, newStretch, newShrink, + best.getAdjust(i), + best.getDifference(i), + best.getDemerits(i), + best.getNode(i)); + addNode(line + 1, newNode); + } + } + best.reset(); + } + + /** + * Return the difference between the line width and the width of the break that + * ends in 'element'. + * @param activeNode + * @param element + * @return The difference in width. Positive numbers mean extra space in the line, + * negative number that the line overflows. + */ + private int computeDifference(KnuthNode activeNode, KnuthElement element) { + // compute the adjustment ratio + int actualWidth = totalWidth - activeNode.totalWidth; + if (element.isPenalty()) { + actualWidth += element.getW(); + } + return lineWidth - actualWidth; + } + + /** + * Return the adjust ration needed to make up for the difference. A ration of + *
    + *
  • 0 means that the break has the exact right width
    • + *
  • >= -1 && < 0 means that the break is to wider than the line, + * but within the minimim values of the glues.
    • + *
  • >0 && < 1 means that the break is smaller than the line width, + * but within the maximum values of the glues.
    • + *
  • > 1 means that the break is too small to make up for the glues.
    • + *
+ * @param activeNode + * @param difference + * @return The ration. + */ + private double computeAdjustmentRatio(KnuthNode activeNode, int difference) { + // compute the adjustment ratio + if (difference > 0) { + int maxAdjustment = totalStretch - activeNode.totalStretch; + if (maxAdjustment > 0) { + return (double) difference / maxAdjustment; + } else { + return INFINITE_RATIO; + } + } else if (difference < 0) { + int maxAdjustment = totalShrink - activeNode.totalShrink; + if (maxAdjustment > 0) { + return (double) difference / maxAdjustment; + } else { + return -INFINITE_RATIO; + } + } else { + return 0; + } + } + + /** + * Figure out the fitness class of this line (tight, loose, + * very tight or very loose). + * @param r + * @return + */ + private int computeFitness(double r) { + int newFitnessClass; + if (r < -0.5) { + return 0; + } else if (r <= 0.5) { + return 1; + } else if (r <= 1) { + return 2; + } else { + return 3; + } + } + + /** + * Find and return the KnuthNode in the active set of nodes with the + * lowest demerit. + */ + private KnuthNode findBestNode() { + // choose the active node with fewest total demerits + KnuthNode bestActiveNode = null; + for (int i = startLine; i < endLine; i++) { + for (KnuthNode node = getNode(i); node != null; node = node.next) { + bestActiveNode = compareNodes(bestActiveNode, node); + } + } + if (log.isTraceEnabled()) { + log.trace("Best demerits " + bestActiveNode.totalDemerits + " for paragraph size " + par.size()); + } + return bestActiveNode; + } + + /** + * Compare two KnuthNodes and return the node with the least demerit. + * @param node1 The first knuth node. + * @param node2 The other knuth node. + * @return + */ + private KnuthNode compareNodes(KnuthNode node1, KnuthNode node2) { + if (node1 == null || node2.position > node1.position) { + return node2; + } + if (node2.position == node1.position) { + if (node2.totalDemerits < node1.totalDemerits) { + return node2; + } + } + return node1; + } + + private double computeDemerits(KnuthNode activeNode, KnuthElement element, + int fitnessClass, double r) { + double demerits = 0; + // compute demerits + double f = Math.abs(r); + f = 1 + 100 * f * f * f; + if (element.isPenalty() && element.getP() >= 0) { + f += element.getP(); + demerits = f * f; + } else if (element.isPenalty() && !element.isForcedBreak()) { + double penalty = element.getP(); + demerits = f * f - penalty * penalty; + } else { + demerits = f * f; + } + + if (element.isPenalty() && ((KnuthPenalty) element).isFlagged() + && getElement(activeNode.position).isPenalty() + && ((KnuthPenalty) getElement(activeNode.position)).isFlagged()) { + // add demerit for consecutive breaks at flagged penalties + demerits += repeatedFlaggedDemerit; + } + if (Math.abs(fitnessClass - activeNode.fitness) > 1) { + // add demerit for consecutive breaks + // with very different fitness classes + demerits += incompatibleFitnessDemerit; + } + demerits += activeNode.totalDemerits; + return demerits; + } + + /** + * Return the element at index idx in the paragraph. + * @param idx index of the element. + * @return + */ + private KnuthElement getElement(int idx) { + return (KnuthElement) par.get(idx); + } + + /** + * Add a KnuthNode at the end of line 'line'. + * If this is the first node in the line, adjust endLine accordingly. + * @param line + * @param node + */ + private void addNode(int line, KnuthNode node) { + int headIdx = line * 2; + if (headIdx >= activeLines.length) { + KnuthNode[] oldList = activeLines; + activeLines = new KnuthNode[headIdx + headIdx]; + System.arraycopy(oldList, 0, activeLines, 0, oldList.length); + } + node.next = null; + if (activeLines[headIdx + 1] != null) { + activeLines[headIdx + 1].next = node; + } else { + activeLines[headIdx] = node; + endLine = line+1; + } + activeLines[headIdx + 1] = node; + activeNodeCount++; + } + + /** + * Remove the first node in line 'line'. If the line then becomes empty, adjust the + * startLine accordingly. + * @param line + * @param node + */ + private void removeNode(int line, KnuthNode node) { + KnuthNode n = getNode(line); + if (n != node) { + log.error("Should be first"); + } else { + activeLines[line*2] = node.next; + if (node.next == null) { + activeLines[line*2+1] = null; + } + while (startLine < endLine && getNode(startLine) == null) { + startLine++; + } + } + activeNodeCount--; + } + + private KnuthNode getNode(int line) { + return activeLines[line * 2]; + } + + /** + * Return true if the position 'idx' is a legal breakpoint. + * @param idx + * @return + */ + private boolean isLegalBreakpoint(int idx) { + KnuthElement elm = getElement(idx); + if (elm.isPenalty() && elm.getP() != KnuthElement.INFINITE) { + return true; + } else if (idx > 0 && elm.isGlue() && getElement(idx-1).isBox()) { + return true; + } else { + return false; + } + } + + public int getDifference(int line) { + return positions[line].difference; + } + + public double getAdjustRatio(int line) { + return positions[line].adjustRatio; + } + + public int getStart(int line) { + KnuthNode previous = positions[line].previous; + return line == 0 ? 0 : previous.position + 1; + } + + public int getEnd(int line) { + return positions[line].position; + } + + /** + * Return a string representation of a MinOptMax in the form of a + * "width+stretch-shrink". Useful only for debugging. + * @param mom + * @return + */ + private static String width(MinOptMax mom) { + return mom.opt + "+" + (mom.max - mom.opt) + "-" + (mom.opt - mom.min); + + } + + public String toString(String prepend) { + StringBuffer sb = new StringBuffer(); + sb.append("[\n"); + for (int i = startLine; i < endLine; i++) { + for (KnuthNode node = getNode(i); node != null; node = node.next) { + sb.append(prepend + "\t" + node + ",\n"); + } + } + sb.append(prepend + "]"); + return sb.toString(); + } +} \ No newline at end of file diff --git a/src/java/org/apache/fop/layoutmgr/KnuthPenalty.java b/src/java/org/apache/fop/layoutmgr/KnuthPenalty.java index 0af1f3210..83b013132 100644 --- a/src/java/org/apache/fop/layoutmgr/KnuthPenalty.java +++ b/src/java/org/apache/fop/layoutmgr/KnuthPenalty.java @@ -1,5 +1,5 @@ /* - * Copyright 2004 The Apache Software Foundation. + * Copyright 2004-2005 The Apache Software Foundation. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -50,11 +50,15 @@ public class KnuthPenalty extends KnuthElement { * @param bAux is this penalty auxiliary? */ public KnuthPenalty(int w, int p, boolean f, Position pos, boolean bAux) { - super(KNUTH_PENALTY, w, pos, bAux); + super(w, pos, bAux); penalty = p; bFlagged = f; } + public boolean isPenalty() { + return true; + } + /** * Return the penalty value of this penalty. */ @@ -68,4 +72,8 @@ public class KnuthPenalty extends KnuthElement { public boolean isFlagged() { return bFlagged; } + + public boolean isForcedBreak() { + return penalty == -KnuthElement.INFINITE; + } } diff --git a/src/java/org/apache/fop/layoutmgr/LineLayoutManager.java b/src/java/org/apache/fop/layoutmgr/LineLayoutManager.java index 8acbc244b..c4a79a982 100644 --- a/src/java/org/apache/fop/layoutmgr/LineLayoutManager.java +++ b/src/java/org/apache/fop/layoutmgr/LineLayoutManager.java @@ -133,153 +133,22 @@ public class LineLayoutManager extends InlineStackingLayoutManager { // offset of the middle baseline with respect to the main baseline private int middleShift; - // inline start pos when adding areas - private int iStartPos = 0; - private ArrayList knuthParagraphs = null; - private LinkedList activeList = null; private ArrayList breakpoints = null; private int iReturnedLBP = 0; private int iStartElement = 0; private int iEndElement = 0; - private KnuthNode bestDeactivatedNode = null; - // parameters of Knuth's algorithm: // penalty value for flagged penalties private int flaggedPenalty = 50; - // demerit for consecutive lines ending at flagged penalties - private int repeatedFlaggedDemerit = 50; - // demerit for consecutive lines belonging to incompatible fitness classes - private int incompatibleFitnessDemerit = 50; - // suggested modification to the "optimum" number of lines - private int looseness = 0; // this constant is used to create elements when text-align is center: // every TextLM descendant of LineLM must use the same value, // otherwise the line breaking algorithm does not find the right // break point public static final int DEFAULT_SPACE_WIDTH = 3336; - private static final int INFINITE_RATIO = 1000; - private static final int MAX_DEMERITS_INCREASE = 1000; - // constants identifying the line breaking algorithm used - private static final int KNUTH_ALGORITHM = 0; - private static final int FIRST_FIT_ALGORITHM = 1; - - // this class represent a feasible breaking point - private class KnuthNode { - // index of the breakpoint represented by this node - public int position; - - // number of the line ending at this breakpoint - public int line; - - // fitness class of the line ending at his breakpoint - public int fitness; - - // accumulated width of the KnuthElements - public int totalWidth; - - // accumulated stretchability of the KnuthElements - public int totalStretch; - - // accumulated shrinkability of the KnuthElements - public int totalShrink; - - // adjustment ratio if the line ends at this breakpoint - public double adjustRatio; - - // difference between target and actual line width - public int difference; - - // minimum total demerits up to this breakpoint - public double totalDemerits; - - // best node for the preceding breakpoint - public KnuthNode previous; - - public KnuthNode(int position, int line, int fitness, - int totalWidth, int totalStretch, int totalShrink, - double adjustRatio, int difference, - double totalDemerits, KnuthNode previous) { - this.position = position; - this.line = line; - this.fitness = fitness; - this.totalWidth = totalWidth; - this.totalStretch = totalStretch; - this.totalShrink = totalShrink; - this.adjustRatio = adjustRatio; - this.difference = difference; - this.totalDemerits = totalDemerits; - this.previous = previous; - } - } - - // this class stores information about how the nodes - // which could start a line - // ending at the current element - private class BestRecords { - private static final double INFINITE_DEMERITS = 1E11; - - private double bestDemerits[] = { - INFINITE_DEMERITS, INFINITE_DEMERITS, - INFINITE_DEMERITS, INFINITE_DEMERITS - }; - private KnuthNode bestNode[] = {null, null, null, null}; - private double bestAdjust[] = {0.0, 0.0, 0.0, 0.0}; - private int bestDifference[] = {0, 0, 0, 0}; - private int bestIndex = -1; - - public BestRecords() { - } - - public void addRecord(double demerits, KnuthNode node, double adjust, - int difference, int fitness) { - if (demerits > bestDemerits[fitness]) { - log.error("New demerits value greter than the old one"); - } - bestDemerits[fitness] = demerits; - bestNode[fitness] = node; - bestAdjust[fitness] = adjust; - bestDifference[fitness] = difference; - if (bestIndex == -1 || demerits < bestDemerits[bestIndex]) { - bestIndex = fitness; - } - } - - public boolean hasRecords() { - return (bestIndex != -1); - } - - public boolean notInfiniteDemerits(int fitness) { - return (bestDemerits[fitness] != INFINITE_DEMERITS); - } - - public double getDemerits(int fitness) { - return bestDemerits[fitness]; - } - - public KnuthNode getNode(int fitness) { - return bestNode[fitness]; - } - - public double getAdjust(int fitness) { - return bestAdjust[fitness]; - } - public int getDifference(int fitness) { - return bestDifference[fitness]; - } - - public double getMinDemerits() { - if (bestIndex != -1) { - return getDemerits(bestIndex); - } else { - // anyway, this should never happen - return INFINITE_DEMERITS; - } - } - } // this class is used to remember // which was the first element in the paragraph @@ -295,7 +164,7 @@ public class LineLayoutManager extends InlineStackingLayoutManager { } // this class represents a paragraph - private class Paragraph extends LinkedList { + public class Paragraph extends ArrayList { // number of KnuthElements added by the LineLayoutManager public int ignoreAtStart = 0; public int ignoreAtEnd = 0; @@ -362,6 +231,22 @@ public class LineLayoutManager extends InlineStackingLayoutManager { knuthParagraphs.add(this); } } + + public KnuthElement getLast() { + int idx = size(); + if (idx == 0) { + return null; + } + return (KnuthElement) get(idx - 1); + } + + public KnuthElement removeLast() { + int idx = size(); + if (idx == 0) { + return null; + } + return (KnuthElement) remove(idx - 1); + } } @@ -376,10 +261,6 @@ public class LineLayoutManager extends InlineStackingLayoutManager { // Get a break from currently active child LM // Set up constraints for inline level managers InlineLevelLayoutManager curLM ; // currently active LM - BreakPoss prev = null; - BreakPoss bp = null; // proposed BreakPoss - - ArrayList vecPossEnd = new ArrayList(); // IPD remaining in line MinOptMax availIPD = context.getStackLimit(); @@ -427,7 +308,7 @@ public class LineLayoutManager extends InlineStackingLayoutManager { if (!prevBox.isAuxiliary()) { // if letter spacing is constant, // only prevBox needs to be replaced; - knuthPar.addLast(((InlineLevelLayoutManager) + knuthPar.add(((InlineLevelLayoutManager) prevBox.getLayoutManager()) .addALetterSpaceTo(prevBox)); } else { @@ -442,11 +323,11 @@ public class LineLayoutManager extends InlineStackingLayoutManager { KnuthPenalty auxPenalty = (KnuthPenalty) knuthPar.removeLast(); prevBox = (KnuthBox) knuthPar.getLast(); - knuthPar.addLast(auxPenalty); - knuthPar.addLast(((InlineLevelLayoutManager) + knuthPar.add(auxPenalty); + knuthPar.add(((InlineLevelLayoutManager) prevBox.getLayoutManager()) .addALetterSpaceTo(prevBox)); - knuthPar.addLast(auxBox); + knuthPar.add(auxBox); } } @@ -545,8 +426,7 @@ public class LineLayoutManager extends InlineStackingLayoutManager { float maxAdjustment = 1; // first try - if (!findBreakingPoints(par, lineWidth, - maxAdjustment, KNUTH_ALGORITHM)) { + if (!findBreakingPoints(par, lineWidth, maxAdjustment, false)) { // the first try failed, now try something different log.debug("No set of breaking points found with maxAdjustment = " + maxAdjustment); if (hyphProps.hyphenate == Constants.EN_TRUE) { @@ -557,182 +437,55 @@ public class LineLayoutManager extends InlineStackingLayoutManager { maxAdjustment = 5; } - if (!findBreakingPoints(par, lineWidth, - maxAdjustment, KNUTH_ALGORITHM)) { + if (!findBreakingPoints(par, lineWidth, maxAdjustment, false)) { // the second try failed too, try with a huge threshold; // if this fails too, use a different algorithm log.debug("No set of breaking points found with maxAdjustment = " + maxAdjustment + (hyphProps.hyphenate == Constants.EN_TRUE ? " and hyphenation" : "")); maxAdjustment = 20; - if (!findBreakingPoints(par, lineWidth, - maxAdjustment, KNUTH_ALGORITHM)) { + if (!findBreakingPoints(par, lineWidth, maxAdjustment, true)) { log.debug("No set of breaking points found, using first-fit algorithm"); - findBreakingPoints(par, lineWidth, - maxAdjustment, FIRST_FIT_ALGORITHM); } } } - - // now: - // * if the Knuth's algorithm found at least a set of breaking point, - // activeList.size() >= 1 and bestDeactivatedNode == null - // * if the Knuth's algorithm failed, and the first-fit algorithm was - // called, activeList.size() == 1 and bestDeactivatedNode != null - - // number of lines that will be created - int line = 0; - // node representing the chosen last breakpoint - KnuthNode bestActiveNode = null; - - // if there are different sets of breaking points - // choose the active node with fewest total demerits - ListIterator activeListIterator = activeList.listIterator(); - KnuthNode tempNode = null; - double bestDemerits = BestRecords.INFINITE_DEMERITS; - while (activeListIterator.hasNext()) { - tempNode = (KnuthNode) activeListIterator.next(); - if (tempNode.totalDemerits < bestDemerits) { - bestActiveNode = tempNode; - bestDemerits = bestActiveNode.totalDemerits; - } + } + + private boolean findBreakingPoints(Paragraph par, int lineWidth, + double threshold, boolean force) { + KnuthParagraph knuthPara = new KnuthParagraph(par); + int lines = knuthPara.findBreakPoints(lineWidth, threshold, force); + if (lines == 0) { + return false; } - line = bestActiveNode.line; - - if (looseness != 0) { - // choose the appropriate active node - activeListIterator = activeList.listIterator(); - int s = 0; - while (activeListIterator.hasNext()) { - tempNode = (KnuthNode) activeListIterator.next(); - int delta = tempNode.line - line; - if (looseness <= delta && delta < s - || s < delta && delta <= looseness) { - s = delta; - bestActiveNode = tempNode; - bestDemerits = tempNode.totalDemerits; - } else if (delta == s - && tempNode.totalDemerits < bestDemerits) { - bestActiveNode = tempNode; - bestDemerits = tempNode.totalDemerits; - } + + for (int i = lines-1; i >= 0; i--) { + int line = i+1; + if (log.isTraceEnabled()) { + log.trace("Making line from " + knuthPara.getStart(i) + " to " + + knuthPara.getEnd(i)); } - line = bestActiveNode.line; - } - - // use the chosen node to determine the optimum breakpoints - for (int i = line; i > 0; i--) { // compute indent and adjustment ratio, according to // the value of text-align and text-align-last - int indent = 0; - int difference = (bestActiveNode.line < line) - ? bestActiveNode.difference - : bestActiveNode.difference + par.lineFillerWidth; - int textAlign = (bestActiveNode.line < line) + + int difference = knuthPara.getDifference(i); + if (line == lines) { + difference += par.lineFillerWidth; + } + int textAlign = (line < lines) ? bTextAlignment : bTextAlignmentLast; - indent += (textAlign == EN_CENTER) + int indent = (textAlign == EN_CENTER) ? difference / 2 : (textAlign == EN_END) ? difference : 0; - indent += (bestActiveNode.line == 1 - && knuthParagraphs.indexOf(par) == 0) + indent += (line == 1 && knuthParagraphs.indexOf(par) == 0) ? textIndent.getValue() : 0; double ratio = (textAlign == EN_JUSTIFY) - ? bestActiveNode.adjustRatio : 0; - - makeLineBreakPosition(par, - (i > 1 ? bestActiveNode.previous.position + 1: 0), - bestActiveNode.position, - 0, ratio, indent); - - bestActiveNode = bestActiveNode.previous; - } - activeList.clear(); - } - - /** - * Perform a line-breaking algorithm. - * - * @param par the list of elements that must be parted - * into lines - * @param lineWidth the desired length ot the lines - * @param threshold the maximum adjustment ratio permitted - * @param algorithm a constant identifying the algorithm to perform - * @return true if the algorithm succeeded, false if it failed - */ - private boolean findBreakingPoints(Paragraph par, int lineWidth, - double threshold, int algorithm) { - int totalWidth = 0; - int totalStretch = 0; - int totalShrink = 0; - - // current element in the paragraph - KnuthElement thisElement = null; - // previous element in the paragraph is a KnuthBox - boolean previousIsBox = false; - - // create an active node representing the starting point - activeList = new LinkedList(); - if (algorithm == KNUTH_ALGORITHM) { - bestDeactivatedNode = null; - activeList.add(new KnuthNode(0, 0, 1, 0, 0, 0, 0, 0, 0, null)); - } else { - activeList.add(new KnuthNode(bestDeactivatedNode.position, - bestDeactivatedNode.line, - 1, 0, 0, 0, - bestDeactivatedNode.adjustRatio, - bestDeactivatedNode.difference, 0, - bestDeactivatedNode.previous)); - } - - // main loop - ListIterator paragraphIterator = par.listIterator(); - while (paragraphIterator.hasNext()) { - thisElement = (KnuthElement) paragraphIterator.next(); - if (thisElement.isBox()) { - // a KnuthBox object is not a legal line break - totalWidth += thisElement.getW(); - previousIsBox = true; - } else if (thisElement.isGlue()) { - // a KnuthGlue object is a legal line break - // only if the previous object is a KnuthBox - if (previousIsBox) { - if (algorithm == KNUTH_ALGORITHM) { - considerLegalBreakKnuth(par, lineWidth, thisElement, - totalWidth, totalStretch, totalShrink, - threshold); - } else { - considerLegalBreakFirstFit(par, lineWidth, thisElement, - totalWidth, totalStretch, totalShrink, - threshold); - } - } - totalWidth += thisElement.getW(); - totalStretch += ((KnuthGlue) thisElement).getY(); - totalShrink += ((KnuthGlue) thisElement).getZ(); - previousIsBox = false; - } else { - // a KnuthPenalty is a legal line break - // only if its penalty is not infinite - if (((KnuthPenalty) thisElement).getP() - < KnuthElement.INFINITE) { - if (algorithm == KNUTH_ALGORITHM) { - considerLegalBreakKnuth(par, lineWidth, thisElement, - totalWidth, totalStretch, totalShrink, - threshold); - } else { - considerLegalBreakFirstFit(par, lineWidth, thisElement, - totalWidth, totalStretch, totalShrink, - threshold); - } - } - previousIsBox = false; - } - } + ? knuthPara.getAdjustRatio(i) : 0; - if (algorithm == KNUTH_ALGORITHM && activeList.size() > 0) { - // bestDeactivatedNode is useless, as the algorithm did not fail - bestDeactivatedNode = null; + int start = knuthPara.getStart(i); + int end = knuthPara.getEnd(i); + makeLineBreakPosition(par, start, end, 0, ratio, indent); } - return (activeList.size() > 0); + return true; } private void makeLineBreakPosition(Paragraph par, @@ -785,307 +538,7 @@ public class LineLayoutManager extends InlineStackingLayoutManager { lineLead)); } - private void considerLegalBreakKnuth(LinkedList par, int lineWidth, - KnuthElement element, - int totalWidth, int totalStretch, - int totalShrink, double threshold) { - KnuthNode activeNode = null; - - ListIterator activeListIterator = activeList.listIterator(); - if (activeListIterator.hasNext()) { - activeNode = (KnuthNode) activeListIterator.next(); - } else { - activeNode = null; - } - - while (activeNode != null) { - BestRecords best = new BestRecords(); - - // these are the new values that must be computed - // in order to define a new active node - int newLine = 0; - int newFitnessClass = 0; - int newWidth = 0; - int newStretch = 0; - int newShrink = 0; - double newIPDAdjust = 0; - double newDemerits = 0; - - while (activeNode != null) { - // compute the line number - newLine = activeNode.line + 1; - - // compute the adjustment ratio - int actualWidth = totalWidth - activeNode.totalWidth; - if (element.isPenalty()) { - actualWidth += element.getW(); - } - int neededAdjustment = lineWidth - actualWidth; - int maxAdjustment = 0; - if (neededAdjustment > 0) { - maxAdjustment = totalStretch - activeNode.totalStretch; - if (maxAdjustment > 0) { - newIPDAdjust - = (double) neededAdjustment / maxAdjustment; - } else { - newIPDAdjust = INFINITE_RATIO; - } - } else if (neededAdjustment < 0) { - maxAdjustment = totalShrink - activeNode.totalShrink; - if (maxAdjustment > 0) { - newIPDAdjust - = (double) neededAdjustment / maxAdjustment; - } else { - newIPDAdjust = INFINITE_RATIO; - } - } else { - // neededAdjustment == 0 - newIPDAdjust = 0; - } - if (newIPDAdjust < -1 - || (element.isPenalty() - && ((KnuthPenalty) element).getP() - == -KnuthElement.INFINITE) - && !(activeNode.position == par.indexOf(element))) { - // deactivate activeNode: - // just remove it from the activeList; as long as there is - // an active node pointing to it, it will not be deleted - KnuthNode tempNode - = (KnuthNode) activeListIterator.previous(); - int iCallNext = 0; - while (tempNode != activeNode) { - // this is not the node we meant to remove! - tempNode = (KnuthNode) activeListIterator.previous(); - iCallNext ++; - } - // use bestDeactivatedNode to keep a pointer to a "good" - // node that could be used if the algorithm fails - if (bestDeactivatedNode == null - || tempNode.line == bestDeactivatedNode.line - && tempNode.totalDemerits < bestDeactivatedNode.totalDemerits - || tempNode.line > bestDeactivatedNode.line - && tempNode.totalDemerits < bestDeactivatedNode.totalDemerits + MAX_DEMERITS_INCREASE) { - bestDeactivatedNode = tempNode; - } - activeListIterator.remove(); - for (int i = 0; i < iCallNext; i++) { - activeListIterator.next(); - } - } - - if ((-1 <= newIPDAdjust) && (newIPDAdjust <= threshold)) { - // compute demerits and fitness class - if (element.isPenalty() - && ((KnuthPenalty) element).getP() >= 0) { - newDemerits - = Math.pow((1 - + 100 * Math.pow(Math.abs(newIPDAdjust), 3) - + ((KnuthPenalty) element).getP()), 2); - } else if (element.isPenalty() - && ((KnuthPenalty) element).getP() - > -INFINITE_RATIO) { - newDemerits - = Math.pow((1 - + 100 * Math.pow(Math.abs(newIPDAdjust), 3)), 2) - - Math.pow(((KnuthPenalty) element).getP(), 2); - } else { - newDemerits - = Math.pow((1 - + 100 * Math.pow(Math.abs(newIPDAdjust), 3)), 2); - } - if (element.isPenalty() - && ((KnuthPenalty) element).isFlagged() - && ((KnuthElement) par.get(activeNode.position)).isPenalty() - && ((KnuthPenalty) par.get(activeNode.position)).isFlagged()) { - // add demerit for consecutive breaks at flagged penalties - newDemerits += repeatedFlaggedDemerit; - } - if (newIPDAdjust < -0.5) { - newFitnessClass = 0; - } else if (newIPDAdjust <= 0.5) { - newFitnessClass = 1; - } else if (newIPDAdjust <= 1) { - newFitnessClass = 2; - } else { - newFitnessClass = 3; - } - if (Math.abs(newFitnessClass - activeNode.fitness) > 1) { - // add demerit for consecutive breaks - // with very different fitness classes - newDemerits += incompatibleFitnessDemerit; - } - newDemerits += activeNode.totalDemerits; - if (newDemerits < best.getDemerits(newFitnessClass)) { - // updates best demerits data - best.addRecord(newDemerits, activeNode, newIPDAdjust, - neededAdjustment, newFitnessClass); - } - } - - - if (activeListIterator.hasNext()) { - activeNode = (KnuthNode) activeListIterator.next(); - } else { - activeNode = null; - break; - } - if (activeNode.line >= newLine) { - break; - } - } // end of the inner while - - if (best.hasRecords()) { - // compute width, stratchability and shrinkability - newWidth = totalWidth; - newStretch = totalStretch; - newShrink = totalShrink; - ListIterator tempIterator - = par.listIterator(par.indexOf(element)); - while (tempIterator.hasNext()) { - KnuthElement tempElement - = (KnuthElement) tempIterator.next(); - if (tempElement.isBox()) { - break; - } else if (tempElement.isGlue()) { - newWidth += ((KnuthGlue) tempElement).getW(); - newStretch += ((KnuthGlue) tempElement).getY(); - newShrink += ((KnuthGlue) tempElement).getZ(); - } else if (((KnuthPenalty) tempElement).getP() - == -KnuthElement.INFINITE - && tempElement != element) { - break; - } - } - - // add nodes to the active nodes list - for (int i = 0; i <= 3; i++) { - if (best.notInfiniteDemerits(i) - && best.getDemerits(i) - <= (best.getMinDemerits() - + incompatibleFitnessDemerit)) { - // the nodes in activeList must be ordered - // by line number and position; - // so: - // 1) advance in the list until the end, - // or a node with a higher line number, is reached - int iStepsForward = 0; - KnuthNode tempNode; - while (activeListIterator.hasNext()) { - iStepsForward ++; - tempNode = (KnuthNode) activeListIterator.next(); - if (tempNode.line > (best.getNode(i).line + 1)) { - activeListIterator.previous(); - iStepsForward --; - break; - } - } - // 2) add the new node - activeListIterator.add - (new KnuthNode(par.indexOf(element), - best.getNode(i).line + 1, i, - newWidth, newStretch, newShrink, - best.getAdjust(i), - best.getDifference(i), - best.getDemerits(i), - best.getNode(i))); - // 3) go back - for (int j = 0; - j <= iStepsForward; - j ++) { - activeListIterator.previous(); - } - } - } - } - if (activeNode == null) { - break; - } - } // end of the outer while - } - - private void considerLegalBreakFirstFit(LinkedList par, int lineWidth, - KnuthElement element, - int totalWidth, int totalStretch, - int totalShrink, double threshold) { - KnuthNode startNode; - KnuthNode endNode; - endNode = (KnuthNode) activeList.getFirst(); - if (endNode.previous != null) { - startNode = endNode.previous; - } else { - startNode = endNode; - endNode = null; - } - // these are the new values that must be computed - // in order to define a new active node - int newWidth; - int newStretch; - int newShrink; - int newDifference; - double newRatio; - - // compute width, stretch and shrink of the new node - newWidth = totalWidth; - newStretch = totalStretch; - newShrink = totalShrink; - ListIterator tempIterator = par.listIterator(par.indexOf(element)); - while (tempIterator.hasNext()) { - KnuthElement tempElement = (KnuthElement)tempIterator.next(); - if (tempElement.isBox()) { - break; - } else if (tempElement.isGlue()) { - newWidth += ((KnuthGlue) tempElement).getW(); - newStretch += ((KnuthGlue) tempElement).getY(); - newShrink += ((KnuthGlue) tempElement).getZ(); - } else if (((KnuthPenalty) tempElement).getP() - == -KnuthElement.INFINITE - && tempElement != element) { - break; - } - } - - if (endNode == null - || totalWidth + (element.isPenalty() ? element.getW() : 0) - startNode.totalWidth <= lineWidth - || bTextAlignment == EN_JUSTIFY - && totalWidth + (element.isPenalty() ? element.getW() : 0)- startNode.totalWidth - (totalShrink - startNode.totalShrink) <= lineWidth) { - // add content to the same line - // compute difference and ratio - int actualWidth = totalWidth - startNode.totalWidth; - if (element.isPenalty()) { - actualWidth += element.getW(); - } - newDifference = lineWidth - actualWidth; - int available = newDifference >= 0 ? totalStretch - startNode.totalStretch - : totalShrink - startNode.totalShrink; - newRatio = available != 0 ? (float) newDifference / available - : 0; - - activeList.removeFirst(); - activeList.add(new KnuthNode(par.indexOf(element), startNode.line + 1, 0, - newWidth, newStretch, newShrink, - newRatio, newDifference, 0.0, - startNode)); - } else { - // start a new line - // compute difference and ratio - int actualWidth = totalWidth - endNode.totalWidth; - if (element.isPenalty()) { - actualWidth += element.getW(); - } - newDifference = lineWidth - actualWidth; - int available = newDifference >= 0 ? totalStretch - endNode.totalStretch - : totalShrink - endNode.totalShrink; - newRatio = available != 0 ? (float) newDifference / available - : 0; - - activeList.removeFirst(); - activeList.add(new KnuthNode(par.indexOf(element), endNode.line + 1, 0, - newWidth, newStretch, newShrink, - newRatio, newDifference, 0.0, - endNode)); - } - } /** * find hyphenation points for every word int the current paragraph @@ -1174,9 +627,9 @@ public class LineLayoutManager extends InlineStackingLayoutManager { // create iterator for the updateList ListIterator updateListIterator = updateList.listIterator(); Update currUpdate = null; - int iPreservedElements = 0; + //int iPreservedElements = 0; int iAddedElements = 0; - int iRemovedElements = 0; + //int iRemovedElements = 0; while (updateListIterator.hasNext()) { // ask the LMs to apply the changes and return @@ -1250,7 +703,7 @@ public class LineLayoutManager extends InlineStackingLayoutManager { } } - private BreakPoss getBestBP(ArrayList vecPossEnd) { + private BreakPoss getBestBP(List vecPossEnd) { if (vecPossEnd.size() == 1) { return ((BreakCost) vecPossEnd.get(0)).getBP(); } diff --git a/src/java/org/apache/fop/layoutmgr/TextLayoutManager.java b/src/java/org/apache/fop/layoutmgr/TextLayoutManager.java index 186b9c089..1a70afdd2 100644 --- a/src/java/org/apache/fop/layoutmgr/TextLayoutManager.java +++ b/src/java/org/apache/fop/layoutmgr/TextLayoutManager.java @@ -793,8 +793,7 @@ public class TextLayoutManager extends AbstractLayoutManager && textArray[iTempStart] != NBSPACE && textArray[iTempStart] != NEWLINE; iTempStart++) { - wordIPD.add( - new MinOptMax(fs.getCharWidth(textArray[iTempStart]))); + wordIPD.add(fs.getCharWidth(textArray[iTempStart])); } wordIPD.add(MinOptMax.multiply(letterSpaceIPD, (iTempStart - iThisStart - 1))); vecAreaInfo.add diff --git a/src/java/org/apache/fop/traits/MinOptMax.java b/src/java/org/apache/fop/traits/MinOptMax.java index b9a1e8d68..7f61a1297 100644 --- a/src/java/org/apache/fop/traits/MinOptMax.java +++ b/src/java/org/apache/fop/traits/MinOptMax.java @@ -1,5 +1,5 @@ /* - * Copyright 1999-2004 The Apache Software Foundation. + * Copyright 1999-2005 The Apache Software Foundation. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -60,6 +60,19 @@ public class MinOptMax implements java.io.Serializable, Cloneable { this.max = max; } + /** + * New min/opt/max with the three values. + * + * @param min the minimum value + * @param opt the optimum value + * @param max the maximum value + */ + public MinOptMax(MinOptMax op) { + this.min = op.min; + this.opt = op.opt; + this.max = op.max; + } + /** * @see java.lang.Object#clone() */ @@ -115,6 +128,27 @@ public class MinOptMax implements java.io.Serializable, Cloneable { max += op.max; } + /** + * Adds another MinOptMax instance to this one. + * @param op the other instance + */ + public void add(int min, int opt, int max) { + this.min += min; + this.opt += opt; + this.max += max; + } + + /** + * Adds another MinOptMax instance to this one. + * @param op the other instance + */ + public void add(int len) { + this.min += len; + this.opt += len; + this.max += len; + } + + /** * Subtracts from this instance using another. * @param op the other instance -- 2.39.5