/* * Copyright 1999-2004 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: LineLayoutManager.java,v 1.17 2004/04/02 10:38:29 cbowditch Exp $ */ package org.apache.fop.layoutmgr; import org.apache.fop.datatypes.Length; import org.apache.fop.fo.Constants; import org.apache.fop.fo.flow.Block; import org.apache.fop.fo.properties.CommonHyphenation; import org.apache.fop.hyphenation.Hyphenation; import org.apache.fop.hyphenation.Hyphenator; import org.apache.fop.area.LineArea; import org.apache.fop.area.Resolvable; import java.util.ListIterator; import java.util.Iterator; import java.util.List; import java.util.ArrayList; import java.util.LinkedList; import org.apache.fop.traits.MinOptMax; /** * LayoutManager for lines. It builds one or more lines containing * inline areas generated by its sub layout managers. * A break is found for each line which may contain one of more * breaks from the child layout managers. * Once a break is found then it is return for the parent layout * manager to handle. * When the areas are being added to the page this manager * creates a line area to contain the inline areas added by the * child layout managers. */ public class LineLayoutManager extends InlineStackingLayoutManager { private Block fobj; /** * Create a new Line Layout Manager. * This is used by the block layout manager to create * line managers for handling inline areas flowing into line areas. * * @param lh the default line height * @param l the default lead, from top to baseline * @param f the default follow, from baseline to bottom */ public LineLayoutManager(Block node, int lh, int l, int f, int ms) { super(node); fobj = node; // the child FObj are owned by the parent BlockLM // this LM has all its childLMs preloaded fobjIter = null; lineHeight = lh; lead = l; follow = f; middleShift = ms; initialize(); // Normally done when started by parent! } /** * @see org.apache.fop.layoutmgr.AbstractLayoutManager#initProperties() */ protected void initProperties() { bTextAlignment = fobj.getTextAlign(); bTextAlignmentLast = fobj.getTextAlignLast(); textIndent = fobj.getTextIndent(); hyphProps = fobj.getCommonHyphenation(); // if (bTextAlignment != EN_JUSTIFY && bTextAlignmentLast == EN_JUSTIFY) { effectiveAlignment = 0; } else { effectiveAlignment = bTextAlignment; } } /** * Private class to store information about inline breaks. * Each value holds the start and end indexes into a List of * inline break positions. */ private static class LineBreakPosition extends LeafPosition { // int iPos; double dAdjust; // Percentage to adjust (stretch or shrink) double ipdAdjust; // Percentage to adjust (stretch or shrink) int startIndent; int lineHeight; int baseline; LineBreakPosition(LayoutManager lm, int iBreakIndex, double ipdA, double adjust, int ind, int lh, int bl) { super(lm, iBreakIndex); // iPos = iBreakIndex; ipdAdjust = ipdA; dAdjust = adjust; startIndent = ind; lineHeight = lh; baseline = bl; } } /** Break positions returned by inline content. */ private List vecInlineBreaks = new ArrayList(); private BreakPoss prevBP = null; // Last confirmed break position private int bTextAlignment = EN_JUSTIFY; private int bTextAlignmentLast; private int effectiveAlignment; private Length textIndent; private CommonHyphenation hyphProps; private int lineHeight; private int lead; private int follow; // 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 int iCurrParIndex = 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 // returned by each LM private class Update { private InlineLevelLayoutManager inlineLM; private int iFirstIndex; public Update(InlineLevelLayoutManager lm, int index) { inlineLM = lm; iFirstIndex = index; } } // this class represents a paragraph private class Paragraph extends LinkedList { // number of KnuthElements added by the LineLayoutManager public int ignoreAtStart = 0; public int ignoreAtEnd = 0; // minimum space at the end of the last line (in millipoints) public int lineFillerWidth; public void startParagraph(int lineWidth) { // set the minimum amount of empty space at the end of the // last line if (bTextAlignment == EN_CENTER) { lineFillerWidth = 0; } else { lineFillerWidth = (int)(lineWidth / 12); } // add auxiliary elements at the beginning of the paragraph if (bTextAlignment == EN_CENTER && bTextAlignmentLast != EN_JUSTIFY) { this.add(new KnuthGlue(0, 3 * DEFAULT_SPACE_WIDTH, 0, null, false)); ignoreAtStart ++; } // add the element representing text indentation // at the beginning of the first paragraph if (knuthParagraphs.size() == 0 && textIndent.getValue() != 0) { this.add(new KnuthBox(textIndent.getValue(), 0, 0, 0, null, false)); ignoreAtStart ++; } } public void endParagraph() { // remove glue and penalty item at the end of the paragraph while (this.size() > ignoreAtStart && !((KnuthElement) this.get(this.size() - 1)).isBox()) { this.remove(this.size() - 1); } if (this.size() > ignoreAtStart) { if (bTextAlignment == EN_CENTER && bTextAlignmentLast != EN_JUSTIFY) { this.add(new KnuthGlue(0, 3 * DEFAULT_SPACE_WIDTH, 0, null, false)); this.add(new KnuthPenalty(0, -KnuthElement.INFINITE, false, null, false)); ignoreAtEnd = 2; } else if (bTextAlignmentLast != EN_JUSTIFY) { // add the elements representing the space // at the end of the last line // and the forced break this.add(new KnuthPenalty(0, KnuthElement.INFINITE, false, null, false)); this.add(new KnuthGlue(lineFillerWidth, 10000000, 0, null, false)); this.add(new KnuthPenalty(0, -KnuthElement.INFINITE, false, null, false)); ignoreAtEnd = 3; } else { // add only the element representing the forced break this.add(new KnuthPenalty(0, -KnuthElement.INFINITE, false, null, false)); ignoreAtEnd = 1; } knuthParagraphs.add(this); } } } /** * Call child layout managers to generate content. * This gets the next break which is a full line. * * @param context the layout context for finding breaks * @return the next break position */ public BreakPoss getNextBreakPoss(LayoutContext context) { // 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(); LayoutContext inlineLC = new LayoutContext(context); clearPrevIPD(); int iPrevLineEnd = vecInlineBreaks.size(); if (iPrevLineEnd == 0 && bTextAlignment == EN_START) { availIPD.subtract(new MinOptMax(textIndent.getValue())); } prevBP = null; // here starts Knuth's algorithm KnuthElement thisElement = null; LinkedList returnedList = null; LineBreakPosition lbp = null; if (knuthParagraphs == null) { // it's the first time this method is called knuthParagraphs = new ArrayList(); breakpoints = new ArrayList(); // convert all the text in a sequence of paragraphs made // of KnuthBox, KnuthGlue and KnuthPenalty objects boolean bPrevWasKnuthBox = false; KnuthBox prevBox = null; Paragraph knuthPar = new Paragraph(); knuthPar.startParagraph(availIPD.opt); while ((curLM = (InlineLevelLayoutManager) getChildLM()) != null) { if ((returnedList = curLM.getNextKnuthElements(inlineLC, effectiveAlignment)) != null) { // look at the first element thisElement = (KnuthElement) returnedList.getFirst(); if (thisElement.isBox() && !thisElement.isAuxiliary() && bPrevWasKnuthBox) { prevBox = (KnuthBox) knuthPar.removeLast(); // if there are two consecutive KnuthBoxes the // first one does not represent a whole word, // so it must be given one more letter space if (!prevBox.isAuxiliary()) { // if letter spacing is constant, // only prevBox needs to be replaced; knuthPar.addLast(((InlineLevelLayoutManager) prevBox.getLayoutManager()) .addALetterSpaceTo(prevBox)); } else { // prevBox is the last element // in the sub-sequence // // the letter space is added to , // while the other elements are not changed KnuthBox auxBox = prevBox; KnuthGlue auxGlue = (KnuthGlue) knuthPar.removeLast(); KnuthPenalty auxPenalty = (KnuthPenalty) knuthPar.removeLast(); prevBox = (KnuthBox) knuthPar.getLast(); knuthPar.addLast(auxPenalty); knuthPar.addLast(((InlineLevelLayoutManager) prevBox.getLayoutManager()) .addALetterSpaceTo(prevBox)); knuthPar.addLast(auxBox); } } // look at the last element KnuthElement lastElement = (KnuthElement) returnedList.getLast(); boolean bForceLinefeed = false; if (lastElement.isBox()) { bPrevWasKnuthBox = true; } else { bPrevWasKnuthBox = false; if (lastElement.isPenalty() && ((KnuthPenalty) lastElement).getP() == -KnuthPenalty.INFINITE) { // a penalty item whose value is -inf // represents a preserved linefeed, // wich forces a line break bForceLinefeed = true; returnedList.removeLast(); } } // add the new elements to the paragraph knuthPar.addAll(returnedList); if (bForceLinefeed) { knuthPar.endParagraph(); knuthPar = new Paragraph(); knuthPar.startParagraph(availIPD.opt); bPrevWasKnuthBox = false; } } else { // curLM returned null; this can happen // if it has nothing more to layout, // so just iterate once more to see // if there are other children } } knuthPar.endParagraph(); // emergency patch if (knuthParagraphs.size() == 0) { setFinished(true); return null; } // find the optimal line breaking points for each paragraph ListIterator paragraphsIterator = knuthParagraphs.listIterator(knuthParagraphs.size()); Paragraph currPar = null; while (paragraphsIterator.hasPrevious()) { currPar = (Paragraph) paragraphsIterator.previous(); findBreakingPoints(currPar, context.getStackLimit().opt); } } else { // this method has been called before // all line breaks are already calculated } // get a break point from the list lbp = (LineBreakPosition) breakpoints.get(iReturnedLBP ++); if (iReturnedLBP == breakpoints.size()) { setFinished(true); } BreakPoss curLineBP = new BreakPoss(lbp); curLineBP.setFlag(BreakPoss.ISLAST, isFinished()); curLineBP.setStackingSize(new MinOptMax(lbp.lineHeight)); return curLineBP; } /** * Find a set of breaking points. * This method is called only once by getNextBreakPoss, and it * subsequently calls the other findBreakingPoints() method with * different parameters, until a set of breaking points is found. * * @param par the list of elements that must be parted * into lines * @param lineWidth the desired length ot the lines */ private void findBreakingPoints(Paragraph par, int lineWidth) { // maximum adjustment ratio permitted float maxAdjustment = 1; // first try if (!findBreakingPoints(par, lineWidth, maxAdjustment, KNUTH_ALGORITHM)) { // 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) { // consider every hyphenation point as a legal break findHyphenationPoints(par); } else { // try with a higher threshold maxAdjustment = 5; } if (!findBreakingPoints(par, lineWidth, maxAdjustment, KNUTH_ALGORITHM)) { // 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)) { 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; } // 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) ? bTextAlignment : bTextAlignmentLast; indent += (textAlign == EN_CENTER) ? difference / 2 : (textAlign == EN_END) ? difference : 0; indent += (bestActiveNode.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; } } if (algorithm == KNUTH_ALGORITHM && activeList.size() > 0) { // bestDeactivatedNode is useless, as the algorithm did not fail bestDeactivatedNode = null; } return (activeList.size() > 0); } private void makeLineBreakPosition(Paragraph par, int firstElementIndex, int lastElementIndex, int insertIndex, double ratio, int indent) { // line height calculation int halfLeading = (lineHeight - lead - follow) / 2; // height above the main baseline int lineLead = lead + halfLeading; // maximum size of top and bottom alignment int maxtb = follow + halfLeading; // max size of middle alignment above and below the middle baseline int middlefollow = maxtb; ListIterator inlineIterator = par.listIterator(firstElementIndex); for (int j = firstElementIndex; j <= lastElementIndex; j++) { KnuthElement element = (KnuthElement) inlineIterator.next(); if (element.isBox()) { if (((KnuthBox) element).getLead() > lineLead) { lineLead = ((KnuthBox) element).getLead(); } if (((KnuthBox) element).getTotal() > maxtb) { maxtb = ((KnuthBox) element).getTotal(); } if (((KnuthBox) element).getMiddle() > lineLead + middleShift) { lineLead += ((KnuthBox) element).getMiddle() - lineLead - middleShift; } if (((KnuthBox) element).getMiddle() > middlefollow - middleShift) { middlefollow += ((KnuthBox) element).getMiddle() - middlefollow + middleShift; } } } if (maxtb - lineLead > middlefollow) { middlefollow = maxtb - lineLead; } breakpoints.add(insertIndex, new LineBreakPosition(this, lastElementIndex , ratio, 0, indent, lineLead + middlefollow, 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 * @ param currPar the paragraph whose words will be hyphenated */ private void findHyphenationPoints(Paragraph currPar){ // hyphenate every word ListIterator currParIterator = currPar.listIterator(currPar.ignoreAtStart); // list of TLM involved in hyphenation LinkedList updateList = new LinkedList(); KnuthElement firstElement = null; KnuthElement nextElement = null; // current InlineLevelLayoutManager InlineLevelLayoutManager currLM = null; // number of KnuthBox elements containing word fragments int boxCount; // number of auxiliary KnuthElements between KnuthBoxes int auxCount; StringBuffer sbChars = null; // find all hyphenation points while (currParIterator.hasNext()) { firstElement = (KnuthElement) currParIterator.next(); // if (firstElement.getLayoutManager() != currLM) { currLM = (InlineLevelLayoutManager) firstElement.getLayoutManager(); if (currLM != null) { updateList.add(new Update(currLM, currParIterator.previousIndex())); } else { break; } } // collect word fragments, ignoring auxiliary elements; // each word fragment was created by a different TextLM if (firstElement.isBox() && !firstElement.isAuxiliary()) { boxCount = 1; auxCount = 0; sbChars = new StringBuffer(); currLM.getWordChars(sbChars, firstElement.getPosition()); // look if next elements are boxes too while (currParIterator.hasNext()) { nextElement = (KnuthElement) currParIterator.next(); if (nextElement.isBox() && !nextElement.isAuxiliary()) { // a non-auxiliary KnuthBox: append word chars if (currLM != nextElement.getLayoutManager()) { currLM = (InlineLevelLayoutManager) nextElement.getLayoutManager(); updateList.add(new Update(currLM, currParIterator.previousIndex())); } // append text to recreate the whole word boxCount ++; currLM.getWordChars(sbChars, nextElement.getPosition()); } else if (!nextElement.isAuxiliary()) { // a non-auxiliary non-box KnuthElement: stop // go back to the last box or auxiliary element currParIterator.previous(); break; } else { // an auxiliary KnuthElement: simply ignore it auxCount ++; } } log.trace(" Word to hyphenate: " + sbChars.toString()); // find hyphenation points HyphContext hc = getHyphenContext(sbChars); // ask each LM to hyphenate its word fragment if (hc != null) { KnuthElement element = null; for (int i = 0; i < (boxCount + auxCount); i++) { currParIterator.previous(); } for (int i = 0; i < (boxCount + auxCount); i++) { element = (KnuthElement) currParIterator.next(); if (element.isBox() && !element.isAuxiliary()) { ((InlineLevelLayoutManager) element.getLayoutManager()).hyphenate(element.getPosition(), hc); } else { // nothing to do, element is an auxiliary KnuthElement } } } } } // create iterator for the updateList ListIterator updateListIterator = updateList.listIterator(); Update currUpdate = null; int iPreservedElements = 0; int iAddedElements = 0; int iRemovedElements = 0; while (updateListIterator.hasNext()) { // ask the LMs to apply the changes and return // the new KnuthElements to replace the old ones currUpdate = (Update) updateListIterator.next(); int fromIndex = currUpdate.iFirstIndex; int toIndex; if (updateListIterator.hasNext()) { Update nextUpdate = (Update) updateListIterator.next(); toIndex = nextUpdate.iFirstIndex; updateListIterator.previous(); } else { // maybe this is not always correct! toIndex = currPar.size() - currPar.ignoreAtEnd - iAddedElements; } // applyChanges() returns true if the LM modifies its data, // so it must return new KnuthElements to replace the old ones if (((InlineLevelLayoutManager) currUpdate.inlineLM) .applyChanges(currPar.subList(fromIndex + iAddedElements, toIndex + iAddedElements))) { // insert the new KnuthElements LinkedList newElements = null; newElements = currUpdate.inlineLM.getChangedKnuthElements (currPar.subList(fromIndex + iAddedElements, toIndex + iAddedElements), flaggedPenalty, effectiveAlignment); // remove the old elements currPar.subList(fromIndex + iAddedElements, toIndex + iAddedElements).clear(); // insert the new elements currPar.addAll(fromIndex + iAddedElements, newElements); iAddedElements += newElements.size() - (toIndex - fromIndex); } } updateListIterator = null; updateList.clear(); } private void resetBP(BreakPoss resetBP) { if (resetBP == null) { reset((Position) null); } else { while (vecInlineBreaks.get(vecInlineBreaks.size() - 1) != resetBP) { vecInlineBreaks.remove(vecInlineBreaks.size() - 1); } reset(resetBP.getPosition()); } } private void reset() { resetBP(prevBP); } protected boolean couldEndLine(BreakPoss bp) { if (bp.canBreakAfter()) { return true; // no keep, ends on break char } else if (bp.isSuppressible()) { // NOTE: except at end of content for this LM!! // Never break after only space chars or any other sequence // of areas which would be suppressed at the end of the line. return false; } else { // See if could break before next area // TODO: do we need to set anything on the layout context? LayoutContext lc = new LayoutContext(0); LayoutManager nextLM = getChildLM(); return (nextLM == null || nextLM.canBreakBefore(lc)); } } private BreakPoss getBestBP(ArrayList vecPossEnd) { if (vecPossEnd.size() == 1) { return ((BreakCost) vecPossEnd.get(0)).getBP(); } // Choose the best break (use a sort on cost!) Iterator iter = vecPossEnd.iterator(); int minCost = Integer.MAX_VALUE; BreakPoss bestBP = null; while (iter.hasNext()) { BreakCost bc = (BreakCost) iter.next(); if (bc.getCost() < minCost) { minCost = bc.getCost(); bestBP = bc.getBP(); } } return bestBP; } /** Line area is always considered to act as a fence. */ protected boolean hasLeadingFence(boolean bNotFirst) { return true; } /** Line area is always considered to act as a fence. */ protected boolean hasTrailingFence(boolean bNotLast) { return true; } /** Return true if we are at the end of this LM, and BPs after prev have been added to vecInlineBreaks and all breakposs in vecInlineBreaks back to and excluding prev are suppressible */ private boolean condAllAreSuppressible(BreakPoss prev) { if (!isFinished()) { return false; } if (vecInlineBreaks.get(vecInlineBreaks.size() - 1) == prev) { return false; } return allAreSuppressible(prev); } /** Test whether all breakposs in vecInlineBreaks back to and excluding prev are suppressible */ private boolean allAreSuppressible(BreakPoss prev) { ListIterator bpIter = vecInlineBreaks.listIterator(vecInlineBreaks.size()); boolean allAreSuppressible = true; BreakPoss bp; while (bpIter.hasPrevious() && (bp = (BreakPoss) bpIter.previous()) != prev && (allAreSuppressible = bp.isSuppressible())) { } return allAreSuppressible; } /** Remove all BPs from the end back to and excluding prev from vecInlineBreaks*/ private void removeAllBP(BreakPoss prev) { int iPrev; if (prev == null) { vecInlineBreaks.clear(); } else if ((iPrev = vecInlineBreaks.indexOf(prev)) != -1) { for (int i = vecInlineBreaks.size()-1; iPrev < i; --i) { vecInlineBreaks.remove(i); } } } private HyphContext getHyphenContext(StringBuffer sbChars) { // Find all hyphenation points in this word // (get in an array of offsets) // hyphProps are from the block level?. // Note that according to the spec, // they also "apply to" fo:character. // I don't know what that means, since // if we change language in the middle of a "word", // the effect would seem quite strange! // Or perhaps in that case, we say that it's several words. // We probably should bring the hyphenation props up from the actual // TextLM which generate the hyphenation buffer, // since these properties inherit and could be specified // on an inline or wrapper below the block level. Hyphenation hyph = Hyphenator.hyphenate(hyphProps.language, hyphProps.country, sbChars.toString(), hyphProps.hyphenationRemainCharacterCount, hyphProps.hyphenationPushCharacterCount); // They hyph structure contains the information we need // Now start from prev: reset to that position, ask that LM to get // a Position for the first hyphenation offset. If the offset isn't in // its characters, it returns null, // but must tell how many chars it had. // Keep looking at currentBP using next hyphenation point until the // returned size is greater than the available size // or no more hyphenation points remain. Choose the best break. if (hyph != null) { return new HyphContext(hyph.getHyphenationPoints()); } else { return null; } } /** * Make a line break for returning as the next break. * This makes the line break and calculates the height and * ipd adjustment factors. * * @param prevLineEnd previous line break index * @param target the target ipd value * @param textalign the text align in operation for this line * @return the line break position */ private BreakPoss makeLineBreak(int prevLineEnd, MinOptMax target, int textalign) { // make a new BP // Store information needed to make areas in the LineBreakPosition! // lead to baseline is // max of: baseline fixed alignment and middle/2 // after baseline is // max: top height-lead, middle/2 and bottom height-lead int halfLeading = (lineHeight - lead - follow) / 2; // height before baseline int lineLead = lead + halfLeading; // maximum size of top and bottom alignment int maxtb = follow + halfLeading; // max size of middle alignment below baseline int middlefollow = maxtb; // calculate actual ipd MinOptMax actual = new MinOptMax(); BreakPoss lastBP = null; LayoutManager lastLM = null; for (Iterator iter = vecInlineBreaks.listIterator(prevLineEnd); iter.hasNext();) { BreakPoss bp = (BreakPoss) iter.next(); if (bp.getLead() > lineLead) { lineLead = bp.getLead(); } if (bp.getTotal() > maxtb) { maxtb = bp.getTotal(); } if (bp.getMiddle() > middlefollow) { middlefollow = bp.getMiddle(); } // the stacking size of textLM accumulate for each break // so the ipd is only added at the end of each LM if (bp.getLayoutManager() != lastLM) { if (lastLM != null) { actual.add(lastBP.getStackingSize()); } lastLM = bp.getLayoutManager(); } lastBP = bp; } if (lastBP != null) { // add final ipd actual.add(lastBP.getStackingSize()); // ATTENTION: make sure this hasn't gotten start space for next // LM added onto it! actual.add(lastBP.resolveTrailingSpace(true)); } if (maxtb - lineLead > middlefollow) { middlefollow = maxtb - lineLead; } // in 7.21.4 the spec suggests that the leader and other // similar min/opt/max areas should be adjusted before // adjusting word spacing // Calculate stretch or shrink factor double ipdAdjust = 0; int targetWith = target.opt; int realWidth = actual.opt; if (actual.opt > targetWith) { if (actual.opt - targetWith < (actual.opt - actual.min)) { ipdAdjust = -(actual.opt - targetWith) / (float) (actual.opt - actual.min); realWidth = targetWith; } else { ipdAdjust = -1; realWidth = actual.min; } } else { if (targetWith - actual.opt < actual.max - actual.opt) { ipdAdjust = (targetWith - actual.opt) / (float) (actual.max - actual.opt); realWidth = targetWith; } else { ipdAdjust = 1; realWidth = actual.max; } } // if justifying then set the space adjustment // after the normal ipd adjustment double dAdjust = 0.0; int indent = 0; switch (textalign) { case EN_JUSTIFY: if (realWidth != 0) { dAdjust = (double) (targetWith - realWidth) / realWidth; } break; case EN_START: if (prevLineEnd == 0) { indent = textIndent.getValue(); } break; case EN_CENTER: indent = (targetWith - realWidth) / 2; break; case EN_END: indent = targetWith - realWidth; break; } LineBreakPosition lbp; lbp = new LineBreakPosition(this, vecInlineBreaks.size() - 1, ipdAdjust, dAdjust, indent, lineLead + middlefollow, lineLead); BreakPoss curLineBP = new BreakPoss(lbp); curLineBP.setFlag(BreakPoss.ISLAST, isFinished()); curLineBP.setStackingSize(new MinOptMax(lineLead + middlefollow)); return curLineBP; } /** * Reset the positions to the given position. * * @param resetPos the position to reset to */ public void resetPosition(Position resetPos) { if (resetPos == null) { setFinished(false); iReturnedLBP = 0; } else { if (isFinished()) { // if isFinished is true, iReturned LBP == breakpoints.size() // and breakpoints.get(iReturnedLBP) would generate // an IndexOutOfBoundException setFinished(false); iReturnedLBP--; } while ((LineBreakPosition) breakpoints.get(iReturnedLBP) != (LineBreakPosition) resetPos) { iReturnedLBP --; } iReturnedLBP ++; } } /** * Add the areas with the break points. * * @param parentIter the iterator of break positions * @param context the context for adding areas */ public void addAreas(PositionIterator parentIter, LayoutContext context) { addAreas(parentIter, 0.0); //vecInlineBreaks.clear(); prevBP = null; } // Generate and add areas to parent area // Set size etc // dSpaceAdjust should reference extra space in the BPD /** * Add the areas with the associated space adjustment. * * @param parentIter the iterator of breaks positions * @param dSpaceAdjust the space adjustment */ public void addAreas(PositionIterator parentIter, double dSpaceAdjust) { LayoutManager childLM; LayoutContext lc = new LayoutContext(0); iCurrParIndex = 0; while (parentIter.hasNext()) { ListIterator paragraphIterator = null; KnuthElement tempElement = null; // the TLM which created the last KnuthElement in this line LayoutManager lastLM = null; LineBreakPosition lbp = (LineBreakPosition) parentIter.next(); LineArea lineArea = new LineArea(); lineArea.setStartIndent(lbp.startIndent); lineArea.setBPD(lbp.lineHeight); lc.setBaseline(lbp.baseline); lc.setLineHeight(lbp.lineHeight); lc.setMiddleShift(middleShift); setCurrentArea(lineArea); Paragraph currPar = (Paragraph) knuthParagraphs.get(iCurrParIndex); iEndElement = lbp.getLeafPos(); // ignore the first elements added by the LineLayoutManager iStartElement += (iStartElement == 0) ? currPar.ignoreAtStart : 0; // ignore the last elements added by the LineLayoutManager iEndElement -= (iEndElement == (currPar.size() - 1)) ? currPar.ignoreAtEnd : 0; // ignore the last element in the line if it is a KnuthGlue object paragraphIterator = currPar.listIterator(iEndElement); tempElement = (KnuthElement) paragraphIterator.next(); if (tempElement.isGlue()) { iEndElement --; // this returns the same KnuthElement paragraphIterator.previous(); tempElement = (KnuthElement) paragraphIterator.previous(); } lastLM = tempElement.getLayoutManager(); // ignore KnuthGlue and KnuthPenalty objects // at the beginning of the line paragraphIterator = currPar.listIterator(iStartElement); tempElement = (KnuthElement) paragraphIterator.next(); while (!tempElement.isBox() && paragraphIterator.hasNext()) { tempElement = (KnuthElement) paragraphIterator.next(); iStartElement ++; } // Add the inline areas to lineArea PositionIterator inlinePosIter = new KnuthPossPosIter(currPar, iStartElement, iEndElement + 1); iStartElement = lbp.getLeafPos() + 1; if (iStartElement == currPar.size()) { // advance to next paragraph iCurrParIndex++; iStartElement = 0; } lc.setSpaceAdjust(lbp.dAdjust); lc.setIPDAdjust(lbp.ipdAdjust); lc.setLeadingSpace(new SpaceSpecifier(true)); lc.setTrailingSpace(new SpaceSpecifier(false)); lc.setFlags(LayoutContext.RESOLVE_LEADING_SPACE, true); setChildContext(lc); while ((childLM = inlinePosIter.getNextChildLM()) != null) { lc.setFlags(LayoutContext.LAST_AREA, (childLM == lastLM)); childLM.addAreas(inlinePosIter, lc); lc.setLeadingSpace(lc.getTrailingSpace()); lc.setTrailingSpace(new SpaceSpecifier(false)); } // when can this be null? if (lc.getTrailingSpace() != null) { addSpace(lineArea, lc.getTrailingSpace().resolve(true), lc.getSpaceAdjust()); } parentLM.addChild(lineArea); } setCurrentArea(null); // ?? necessary } /** * Add an unresolved area. * If a child layout manager needs to add an unresolved area * for page reference or linking then this intercepts it for * line area handling. * A line area may need to have the inline areas adjusted * to properly fill the line area. This adds a resolver that * resolves the inline area and can do the necessary * adjustments to the line and inline areas. * * @param id the id reference of the resolvable * @param res the resolvable object */ public void addUnresolvedArea(String id, Resolvable res) { // create a resolvable class that handles ipd // adjustment for the current line parentLM.addUnresolvedArea(id, res); } }