You are viewing a plain text version of this content. The canonical link for it is here.
Posted to fop-commits@xmlgraphics.apache.org by je...@apache.org on 2005/03/08 16:03:06 UTC
cvs commit: xml-fop/src/java/org/apache/fop/traits MinOptMax.java
jeremias 2005/03/08 07:03:06
Modified: src/java/org/apache/fop/layoutmgr TextLayoutManager.java
KnuthPenalty.java KnuthGlue.java KnuthElement.java
KnuthBox.java LineLayoutManager.java
src/java/org/apache/fop/traits MinOptMax.java
Added: src/java/org/apache/fop/layoutmgr KnuthParagraph.java
Log:
Refactoring of Knuth line breaking code (including some speed improvements)
Bugzilla: #32612
Submitted by: Finn Bock <bckfnn.at.worldonline.dk>
Revision Changes Path
1.31 +1 -2 xml-fop/src/java/org/apache/fop/layoutmgr/TextLayoutManager.java
Index: TextLayoutManager.java
===================================================================
RCS file: /home/cvs/xml-fop/src/java/org/apache/fop/layoutmgr/TextLayoutManager.java,v
retrieving revision 1.30
retrieving revision 1.31
diff -u -r1.30 -r1.31
--- TextLayoutManager.java 2 Feb 2005 15:03:55 -0000 1.30
+++ TextLayoutManager.java 8 Mar 2005 15:02:59 -0000 1.31
@@ -793,8 +793,7 @@
&& 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
1.4 +11 -3 xml-fop/src/java/org/apache/fop/layoutmgr/KnuthPenalty.java
Index: KnuthPenalty.java
===================================================================
RCS file: /home/cvs/xml-fop/src/java/org/apache/fop/layoutmgr/KnuthPenalty.java,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -r1.3 -r1.4
--- KnuthPenalty.java 6 Dec 2004 11:55:18 -0000 1.3
+++ KnuthPenalty.java 8 Mar 2005 15:02:59 -0000 1.4
@@ -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 @@
* @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 boolean isFlagged() {
return bFlagged;
}
+
+ public boolean isForcedBreak() {
+ return penalty == -KnuthElement.INFINITE;
+ }
}
1.4 +7 -3 xml-fop/src/java/org/apache/fop/layoutmgr/KnuthGlue.java
Index: KnuthGlue.java
===================================================================
RCS file: /home/cvs/xml-fop/src/java/org/apache/fop/layoutmgr/KnuthGlue.java,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -r1.3 -r1.4
--- KnuthGlue.java 6 Dec 2004 11:55:18 -0000 1.3
+++ KnuthGlue.java 8 Mar 2005 15:02:59 -0000 1.4
@@ -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 @@
* @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.
*/
1.4 +22 -12 xml-fop/src/java/org/apache/fop/layoutmgr/KnuthElement.java
Index: KnuthElement.java
===================================================================
RCS file: /home/cvs/xml-fop/src/java/org/apache/fop/layoutmgr/KnuthElement.java,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -r1.3 -r1.4
--- KnuthElement.java 6 Dec 2004 11:55:18 -0000 1.3
+++ KnuthElement.java 8 Mar 2005 15:02:59 -0000 1.4
@@ -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 @@
*/
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 @@
* @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 @@
* 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 @@
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.
*/
1.4 +7 -3 xml-fop/src/java/org/apache/fop/layoutmgr/KnuthBox.java
Index: KnuthBox.java
===================================================================
RCS file: /home/cvs/xml-fop/src/java/org/apache/fop/layoutmgr/KnuthBox.java,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -r1.3 -r1.4
--- KnuthBox.java 6 Dec 2004 11:55:18 -0000 1.3
+++ KnuthBox.java 8 Mar 2005 15:02:59 -0000 1.4
@@ -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 @@
* @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.
*/
1.41 +55 -602 xml-fop/src/java/org/apache/fop/layoutmgr/LineLayoutManager.java
Index: LineLayoutManager.java
===================================================================
RCS file: /home/cvs/xml-fop/src/java/org/apache/fop/layoutmgr/LineLayoutManager.java,v
retrieving revision 1.40
retrieving revision 1.41
diff -u -r1.40 -r1.41
--- LineLayoutManager.java 10 Feb 2005 15:54:03 -0000 1.40
+++ LineLayoutManager.java 8 Mar 2005 15:02:59 -0000 1.41
@@ -133,153 +133,22 @@
// 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 @@
}
// 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 @@
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 @@
// 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 @@
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 @@
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 @@
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 @@
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;
- }
- }
- 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;
- }
- }
- line = bestActiveNode.line;
+ }
+
+ 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;
}
-
- // use the chosen node to determine the optimum breakpoints
- for (int i = line; i > 0; i--) {
+
+ 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));
+ }
// 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);
+ ? knuthPara.getAdjustRatio(i) : 0;
- bestActiveNode = bestActiveNode.previous;
+ int start = knuthPara.getStart(i);
+ int end = knuthPara.getEnd(i);
+ makeLineBreakPosition(par, start, end, 0, ratio, indent);
}
- 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;
- }
- }
-
- if (algorithm == KNUTH_ALGORITHM && activeList.size() > 0) {
- // bestDeactivatedNode is useless, as the algorithm did not fail
- bestDeactivatedNode = null;
- }
- return (activeList.size() > 0);
+ return true;
}
private void makeLineBreakPosition(Paragraph par,
@@ -785,307 +538,7 @@
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 @@
// 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 @@
}
}
- private BreakPoss getBestBP(ArrayList vecPossEnd) {
+ private BreakPoss getBestBP(List vecPossEnd) {
if (vecPossEnd.size() == 1) {
return ((BreakCost) vecPossEnd.get(0)).getBP();
}
1.1 xml-fop/src/java/org/apache/fop/layoutmgr/KnuthParagraph.java
Index: KnuthParagraph.java
===================================================================
/*
* 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: KnuthParagraph.java,v 1.1 2005/03/08 15:02:59 jeremias Exp $ */
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'.
* <p>
* The set of active nodes can be traversed by
* <pre>
* for (int line = startLine; line < endLine; line++) {
* for (KnuthNode node = getNode(line); node != null; node = node.next) {
* // Do something with 'node'
* }
* }
* </pre>
*/
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 "<KnuthNode at " + position + " " +
totalWidth + "+" + totalStretch + "-" + totalShrink +
" line:" + line +
" prev:" + (previous != null ? previous.position : -1) +
" dem:" + totalDemerits +
">";
}
}
// 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
* <ul>
* <li>0 means that the break has the exact right width</li>
* <li>>= -1 && < 0 means that the break is to wider than the line,
* but within the minimim values of the glues.</li>
* <li>>0 && < 1 means that the break is smaller than the line width,
* but within the maximum values of the glues.</li>
* <li>> 1 means that the break is too small to make up for the glues.</li>
* </ul>
* @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();
}
}
1.4 +36 -2 xml-fop/src/java/org/apache/fop/traits/MinOptMax.java
Index: MinOptMax.java
===================================================================
RCS file: /home/cvs/xml-fop/src/java/org/apache/fop/traits/MinOptMax.java,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -r1.3 -r1.4
--- MinOptMax.java 27 Feb 2004 17:56:25 -0000 1.3
+++ MinOptMax.java 8 Mar 2005 15:03:06 -0000 1.4
@@ -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.
@@ -61,6 +61,19 @@
}
/**
+ * 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()
*/
public Object clone() {
@@ -116,6 +129,27 @@
}
/**
+ * 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
*/
---------------------------------------------------------------------
To unsubscribe, e-mail: fop-cvs-unsubscribe@xml.apache.org
For additional commands, e-mail: fop-cvs-help@xml.apache.org