path: root/src/java/org/apache/fop/layoutmgr/inline/LineLayoutManager.java

/*
 * 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.
 * 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.inline;

import org.apache.fop.datatypes.Length;
import org.apache.fop.datatypes.Numeric;
import org.apache.fop.fo.Constants;
import org.apache.fop.fo.FONode;
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.layoutmgr.BlockLevelLayoutManager;
import org.apache.fop.layoutmgr.BreakElement;
import org.apache.fop.layoutmgr.BreakingAlgorithm;
import org.apache.fop.layoutmgr.ElementListObserver;
import org.apache.fop.layoutmgr.KnuthBlockBox;
import org.apache.fop.layoutmgr.KnuthBox;
import org.apache.fop.layoutmgr.KnuthElement;
import org.apache.fop.layoutmgr.KnuthGlue;
import org.apache.fop.layoutmgr.KnuthPenalty;
import org.apache.fop.layoutmgr.KnuthPossPosIter;
import org.apache.fop.layoutmgr.KnuthSequence;
import org.apache.fop.layoutmgr.LayoutContext;
import org.apache.fop.layoutmgr.LayoutManager;
import org.apache.fop.layoutmgr.LeafPosition;
import org.apache.fop.layoutmgr.NonLeafPosition;
import org.apache.fop.layoutmgr.Position;
import org.apache.fop.layoutmgr.PositionIterator;
import org.apache.fop.layoutmgr.SpaceSpecifier;
import org.apache.fop.area.Area;
import org.apache.fop.area.LineArea;
import org.apache.fop.area.inline.InlineArea;

import java.util.ListIterator;
import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;
import org.apache.fop.area.Trait;
import org.apache.fop.fonts.Font;

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 
                               implements BlockLevelLayoutManager {

    private Block fobj; 
    
    public void initialize() {
        textAlignment = fobj.getTextAlign();
        textAlignmentLast = fobj.getTextAlignLast();
        textIndent = fobj.getTextIndent();
        lastLineEndIndent = fobj.getLastLineEndIndent();
        hyphenationProperties = fobj.getCommonHyphenation();
        hyphenationLadderCount = fobj.getHyphenationLadderCount();
        wrapOption = fobj.getWrapOption();
        //
        effectiveAlignment = getEffectiveAlignment(textAlignment, textAlignmentLast);
    }

    private int getEffectiveAlignment(int alignment, int alignmentLast) {
        if (textAlignment != EN_JUSTIFY && textAlignmentLast == EN_JUSTIFY) {
            return 0;
        } else {
            return textAlignment;
        }
    }
    
    /**
     * 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 {
        private int iParIndex; // index of the Paragraph this Position refers to
        private int availableShrink;
        private int availableStretch;
        private int difference;
        private double dAdjust; // Percentage to adjust (stretch or shrink)
        private double ipdAdjust; // Percentage to adjust (stretch or shrink)
        private int startIndent;
        private int lineHeight;
        private int lineWidth;
        private int spaceBefore;
        private int spaceAfter;
        private int baseline;

        LineBreakPosition(LayoutManager lm, int index, int iBreakIndex,
                          int shrink, int stretch, int diff,
                          double ipdA, double adjust, int ind,
                          int lh, int lw, int sb, int sa, int bl) {
            super(lm, iBreakIndex);
            availableShrink = shrink;
            availableStretch = stretch;
            difference = diff;
            iParIndex = index;
            ipdAdjust = ipdA;
            dAdjust = adjust;
            startIndent = ind;
            lineHeight = lh;
            lineWidth = lw;
            spaceBefore = sb;
            spaceAfter = sa;
            baseline = bl;
        }
        
    }


    private int textAlignment = EN_JUSTIFY;
    private int textAlignmentLast;
    private int effectiveAlignment;
    private Length textIndent;
    private Length lastLineEndIndent;
    private int iIndents = 0;
    private CommonHyphenation hyphenationProperties;
    private Numeric hyphenationLadderCount;
    private int wrapOption = EN_WRAP;
    //private LayoutProps layoutProps;

    private Length lineHeight;
    private int lead;
    private int follow;
    private AlignmentContext alignmentContext = null;

    private List knuthParagraphs = null;
    private int iReturnedLBP = 0;
    private int iStartElement = 0;
    private int iEndElement = 0;

    //     parameters of Knuth's algorithm:
    // penalty value for flagged penalties
    private int flaggedPenalty = 50;

    private LineLayoutPossibilities lineLayouts;
    private List lineLayoutsList;
    private int iLineWidth = 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;


    /**
     * 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 KnuthSequence {
        // space at the end of the last line (in millipoints)
        private MinOptMax lineFiller;
        private int textAlignment;
        private int textAlignmentLast;
        private int textIndent;
        private int lastLineEndIndent;
        private int lineWidth;
        // the LM which created the paragraph
        private LineLayoutManager layoutManager;

        public Paragraph(LineLayoutManager llm, int alignment, int alignmentLast,
                         int indent, int endIndent) {
            super(true);
            layoutManager = llm;
            textAlignment = alignment;
            textAlignmentLast = alignmentLast;
            textIndent = indent;
            lastLineEndIndent = endIndent;
        }

        public void startParagraph(int lw) {
            lineWidth = lw;
            startSequence();
        }

        public void startSequence() {
            // set the minimum amount of empty space at the end of the
            // last line
            if (textAlignment == EN_CENTER) {
                lineFiller = new MinOptMax(lastLineEndIndent); 
            } else {
                lineFiller = new MinOptMax(lastLineEndIndent, lastLineEndIndent, lineWidth); 
            }

            // add auxiliary elements at the beginning of the paragraph
            if (textAlignment == EN_CENTER && textAlignmentLast != 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
                        && fobj.getTextIndent().getValue(layoutManager) != 0) {
                this.add(new KnuthInlineBox(fobj.getTextIndent().getValue(layoutManager), null, 
                                      null, false));
                ignoreAtStart++;
            }
        }

        public void endParagraph() {
            KnuthSequence finishedPar = this.endSequence();
            if (finishedPar != null) {
                knuthParagraphs.add(finishedPar);
            }
        }

        public KnuthSequence endSequence() {
            // remove elements representig spaces at the end of the paragraph
            removeElementsForTrailingSpaces();
            if (this.size() > ignoreAtStart) {
                if (textAlignment == EN_CENTER
                    && textAlignmentLast != EN_JUSTIFY) {
                    this.add(new KnuthGlue(0, 3 * DEFAULT_SPACE_WIDTH, 0,
                                           null, false));
                    this.add(new KnuthPenalty(lineFiller.opt, -KnuthElement.INFINITE,
                                              false, null, false));
                    ignoreAtEnd = 2;
                } else if (textAlignmentLast != 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(0, 
                            lineFiller.max - lineFiller.opt, 
                            lineFiller.opt - lineFiller.min, null, false));
                    this.add(new KnuthPenalty(lineFiller.opt, -KnuthElement.INFINITE,
                                              false, null, false));
                    ignoreAtEnd = 3;
                } else {
                    // add only the element representing the forced break
                    this.add(new KnuthPenalty(lineFiller.opt, -KnuthElement.INFINITE,
                                              false, null, false));
                    ignoreAtEnd = 1;
                }
                return this;
            } else {
                this.clear();
                return null;
            }
        }

        /**
         * remove elements representing spaces at the end of the paragraph;
         * the text could have one or more trailing spaces, each of them
         * being either a normal space or a non-breaking space;
         * according to the alignment, the sub-sequence of elements
         * representing each space has a different "pattern"
         */
        private void removeElementsForTrailingSpaces() {
            LinkedList removedElements;
            InlineLevelLayoutManager inlineLM;
            int effectiveAlignment = getEffectiveAlignment(textAlignment, textAlignmentLast);
            while (this.size() > ignoreAtStart
                   && ((KnuthElement) this.get(this.size() - 1)).isGlue()) {
                removedElements = new LinkedList();
                inlineLM = (InlineLevelLayoutManager)
                    ((KnuthElement) this.get(this.size() - 1)).getLayoutManager();
                if (effectiveAlignment == EN_CENTER
                    || this.size() > 6
                       && ((KnuthElement) this.get(this.size() - 6)).isGlue()
                       && ((KnuthElement) this.get(this.size() - 5)).isPenalty()
                       && ((KnuthElement) this.get(this.size() - 4)).isGlue()
                       && ((KnuthElement) this.get(this.size() - 3)).isBox()
                       && ((KnuthElement) this.get(this.size() - 2)).isPenalty()) {
                    // centered text (or text with inline borders and padding): the pattern is
                    //     <glue> <penaly> <glue> <box> <penaly> <glue>
                    removedElements.addFirst((KnuthGlue) this.remove(this.size() - 1));
                    removedElements.addFirst((KnuthPenalty) this.remove(this.size() - 1));
                    removedElements.addFirst((KnuthBox) this.remove(this.size() - 1));
                    removedElements.addFirst((KnuthGlue) this.remove(this.size() - 1));
                    removedElements.addFirst((KnuthPenalty) this.remove(this.size() - 1));
                    removedElements.addFirst((KnuthGlue) this.remove(this.size() - 1));
                } else if (effectiveAlignment == EN_START || effectiveAlignment == EN_END) {
                    // left- or right-aligned text: the pattern is
                    //     <glue> <penalty> <glue>
                    removedElements.addFirst((KnuthGlue) this.remove(this.size() - 1));
                    removedElements.addFirst((KnuthPenalty) this.remove(this.size() - 1));
                    removedElements.addFirst((KnuthGlue) this.remove(this.size() - 1));
                } else {
                    // justified text: the pattern is
                    //     <glue>
                    removedElements.add((KnuthGlue) this.remove(this.size() - 1));
                }
                // if the space was a non-breaking one, there is also a penalty
                if (this.size() > ignoreAtStart
                    && ((KnuthElement) this.get(this.size() - 1)).isPenalty()) {
                    removedElements.addFirst((KnuthPenalty) this.remove(this.size() - 1));
                }
                inlineLM.removeWordSpace(removedElements);
            }
        }

        private void addALetterSpace() {
            KnuthBox prevBox = (KnuthBox) removeLast();
            LinkedList oldList = new LinkedList();
            // 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;
                oldList.add(prevBox);
            } else {
                // prevBox is the last element
                // in the sub-sequence
                //   <box> <aux penalty> <aux glue> <aux box>
                // the letter space is added to <aux glue>,
                // while the other elements are not changed
                oldList.add(prevBox);
                oldList.addFirst((KnuthGlue) removeLast());
                oldList.addFirst((KnuthPenalty) removeLast());
                oldList.addFirst((KnuthBox) removeLast());
            }
            // adding a letter space could involve, according to the text
            // represented by oldList, replacing a glue element or adding
            // new elements
            addAll(((InlineLevelLayoutManager)
                         prevBox.getLayoutManager())
                        .addALetterSpaceTo(oldList));
            if (((KnuthInlineBox) prevBox).isAnchor()) {
                // prevBox represents a footnote citation: copy footnote info
                // from prevBox to the new box
                KnuthInlineBox newBox = (KnuthInlineBox) getLast();
                newBox.setFootnoteBodyLM(((KnuthInlineBox) prevBox).getFootnoteBodyLM());
            }
        }
    }

    private class LineBreakingAlgorithm extends BreakingAlgorithm {
        private LineLayoutManager thisLLM;
        private int pageAlignment;
        private int activePossibility;
        private int addedPositions;
        private int textIndent;
        private int fillerMinWidth;
        private int lineHeight;
        private int lead;
        private int follow;
        private int maxDiff;
        private static final double MAX_DEMERITS = 10e6;

        public LineBreakingAlgorithm (int pageAlign,
                                      int textAlign, int textAlignLast,
                                      int indent, int fillerWidth,
                                      int lh, int ld, int fl, boolean first,
                                      int maxFlagCount, LineLayoutManager llm) {
            super(textAlign, textAlignLast, first, false, maxFlagCount);
            pageAlignment = pageAlign;
            textIndent = indent;
            fillerMinWidth = fillerWidth;
            lineHeight = lh;
            lead = ld;
            follow = fl;
            thisLLM = llm;
            activePossibility = -1;
            maxDiff = fobj.getWidows() >= fobj.getOrphans() 
                    ? fobj.getWidows()
                    : fobj.getOrphans();
        }

        public void updateData1(int lineCount, double demerits) {
            lineLayouts.addPossibility(lineCount, demerits);
            log.trace("Layout possibility in " + lineCount + " lines; break at position:");
        }

        public void updateData2(KnuthNode bestActiveNode,
                                KnuthSequence par,
                                int total) {
            // compute indent and adjustment ratio, according to
            // the value of text-align and text-align-last
            int indent = 0;
            int difference = bestActiveNode.difference;
            int textAlign = (bestActiveNode.line < total) ? alignment : alignmentLast;
            indent += (textAlign == Constants.EN_CENTER) ?
                          difference / 2 : (textAlign == Constants.EN_END) ? difference : 0;
            indent += (bestActiveNode.line == 1 && bFirst) ? textIndent : 0;
            double ratio = (textAlign == Constants.EN_JUSTIFY
                || difference < 0 && -difference <= bestActiveNode.availableShrink)
                        ? bestActiveNode.adjustRatio : 0;

            // add nodes at the beginning of the list, as they are found
            // backwards, from the last one to the first one

            // the first time this method is called, initialize activePossibility
            if (activePossibility == -1) {
                activePossibility = 0;
                addedPositions = 0;
            }

            if (addedPositions == lineLayouts.getLineCount(activePossibility)) {
                activePossibility++;
                addedPositions = 0;
            }

            if (difference + bestActiveNode.availableShrink < 0) {
                if (log.isWarnEnabled()) {
                    log.warn(FONode.decorateWithContextInfo(
                            "Line " + (addedPositions + 1) 
                            + " of a paragraph overflows the available area.", getFObj()));
                }
            }
            
            //log.debug("LLM> (" + (lineLayouts.getLineNumber(activePossibility) - addedPositions) 
            //    + ") difference = " + difference + " ratio = " + ratio);
            lineLayouts.addBreakPosition(makeLineBreakPosition(par,
                   (bestActiveNode.line > 1 ? bestActiveNode.previous.position + 1 : 0),
                   bestActiveNode.position,
                   bestActiveNode.availableShrink - (addedPositions > 0 
                       ? 0 : ((Paragraph)par).lineFiller.opt - ((Paragraph)par).lineFiller.min), 
                   bestActiveNode.availableStretch, 
                   difference, ratio, indent), activePossibility);
            addedPositions++;
        }

        /* reset activePossibility, as if breakpoints have not yet been computed
         */
        public void resetAlgorithm() {
            activePossibility = -1;
        }

        private LineBreakPosition makeLineBreakPosition(KnuthSequence par,
                                                        int firstElementIndex,
                                                        int lastElementIndex,
                                                        int availableShrink, 
                                                        int availableStretch, 
                                                        int difference,
                                                        double ratio,
                                                        int indent) {
            // line height calculation - spaceBefore may differ from spaceAfter
            // by 1mpt due to rounding
            int spaceBefore = (lineHeight - lead - follow) / 2;
            int spaceAfter = lineHeight - lead - follow - spaceBefore;
            // height before the main baseline
            int lineLead = lead;
            // maximum follow 
            int lineFollow = follow;
            // true if this line contains only zero-height, auxiliary boxes
            // and the actual line width is 0; in this case, the line "collapses"
            // i.e. the line area will have bpd = 0
            boolean bZeroHeightLine = (difference == iLineWidth);

            // if line-stacking-strategy is "font-height", the line height
            // is not affected by its content
            if (fobj.getLineStackingStrategy() != EN_FONT_HEIGHT) {
                ListIterator inlineIterator
                    = par.listIterator(firstElementIndex);
                AlignmentContext lastAC = null;
                int maxIgnoredHeight = 0; // See spec 7.13
                for (int j = firstElementIndex;
                     j <= lastElementIndex;
                     j++) {
                    KnuthElement element = (KnuthElement) inlineIterator.next();
                    if (element instanceof KnuthInlineBox ) {
                        AlignmentContext ac = ((KnuthInlineBox) element).getAlignmentContext();
                        if (ac != null && lastAC != ac) {
                            if (!ac.usesInitialBaselineTable()
                                || ac.getAlignmentBaselineIdentifier() != EN_BEFORE_EDGE
                                   && ac.getAlignmentBaselineIdentifier() != EN_AFTER_EDGE) {
                                int alignmentOffset = ac.getTotalAlignmentBaselineOffset();
                                if (alignmentOffset + ac.getAltitude() > lineLead) {
                                    lineLead = alignmentOffset + ac.getAltitude();
                                }
                                if (ac.getDepth() - alignmentOffset > lineFollow)  {
                                    lineFollow = ac.getDepth() - alignmentOffset;
                                }
                            } else {
                                if (ac.getHeight() > maxIgnoredHeight) {
                                    maxIgnoredHeight = ac.getHeight();
                                }
                            }
                            lastAC = ac;
                        }
                        if (bZeroHeightLine
                            && (!element.isAuxiliary() || ac != null && ac.getHeight() > 0)) {
                            bZeroHeightLine = false;
                        }
                    }
                }

                if (lineFollow < maxIgnoredHeight - lineLead) {
                    lineFollow = maxIgnoredHeight - lineLead;
                }
            }

            constantLineHeight = lineLead + lineFollow;

            if (bZeroHeightLine) {
                return new LineBreakPosition(thisLLM,
                                             knuthParagraphs.indexOf(par),
                                             lastElementIndex,
                                             availableShrink, availableStretch, difference, ratio, 0, indent,
                                             0, iLineWidth, 0, 0, 0);
            } else {
                return new LineBreakPosition(thisLLM,
                                             knuthParagraphs.indexOf(par),
                                             lastElementIndex,
                                             availableShrink, availableStretch, difference, ratio, 0, indent,
                                             lineLead + lineFollow, 
                                             iLineWidth, spaceBefore, spaceAfter,
                                             lineLead);
            }
        }

        public int findBreakingPoints(Paragraph par, /*int lineWidth,*/
                                      double threshold, boolean force,
                                      int allowedBreaks) {
            return super.findBreakingPoints(par, /*lineWidth,*/ 
                    threshold, force, allowedBreaks);
        }

        protected int filterActiveNodes() {
            KnuthNode bestActiveNode = null;

            if (pageAlignment == EN_JUSTIFY) {
                // leave all active nodes and find the optimum line number
                //log.debug("LBA.filterActiveNodes> " + activeNodeCount + " layouts");
                for (int i = startLine; i < endLine; i++) {
                    for (KnuthNode node = getNode(i); node != null; node = node.next) {
                        //log.debug("                       + lines = " + node.line + " demerits = " + node.totalDemerits);
                        bestActiveNode = compareNodes(bestActiveNode, node);
                    }
                }

                // scan the node set once again and remove some nodes
                //log.debug("LBA.filterActiveList> layout selection");
                for (int i = startLine; i < endLine; i++) {
                    for (KnuthNode node = getNode(i); node != null; node = node.next) {
                        //if (Math.abs(node.line - bestActiveNode.line) > maxDiff) {
                        //if (false) {
                        if (node.line != bestActiveNode.line
                            && node.totalDemerits > MAX_DEMERITS) {
                            //log.debug("                     XXX lines = " + node.line + " demerits = " + node.totalDemerits);
                            removeNode(i, node);
                        } else {
                            //log.debug("                      ok lines = " + node.line + " demerits = " + node.totalDemerits);
                        }
                    }
                }
            } else {
                // leave only the active node with fewest total demerits
                for (int i = startLine; i < endLine; i++) {
                    for (KnuthNode node = getNode(i); node != null; node = node.next) {
                        bestActiveNode = compareNodes(bestActiveNode, node);
                        if (node != bestActiveNode) {
                            removeNode(i, node);
                        }
                    }
                }
            }
            return bestActiveNode.line;
        }
    }

      
    private int constantLineHeight = 12000;
      

    /**
     * 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 block the block formatting object
     * @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 block, Length lh, int l, int f) {
        super(block);
        fobj = block;
        // the child FObj are owned by the parent BlockLM
        // this LM has all its childLMs preloaded
        fobjIter = null;
        lineHeight = lh;
        lead = l;
        follow = f;
    }

    /** @see org.apache.fop.layoutmgr.LayoutManager */
    public LinkedList getNextKnuthElements(LayoutContext context, int alignment) {
        Font fs = fobj.getCommonFont().getFontState(fobj.getFOEventHandler().getFontInfo(), this);
        alignmentContext = new AlignmentContext(fs, lineHeight.getValue(this), context.getWritingMode());
        context.setAlignmentContext(alignmentContext);
        // Get a break from currently active child LM
        // Set up constraints for inline level managers
        InlineLevelLayoutManager curLM; // currently active LM

        // IPD remaining in line
        MinOptMax availIPD = context.getStackLimit();

        clearPrevIPD();

        //PHASE 1: Create Knuth elements
        if (knuthParagraphs == null) {
            // it's the first time this method is called
            knuthParagraphs = new ArrayList();

            // here starts Knuth's algorithm
            //TODO availIPD should not really be used here, so we can later support custom line
            //widths for for each line (side-floats, differing available IPD after page break)
            collectInlineKnuthElements(context, availIPD);
        } else {
            // this method has been called before
            // all line breaks are already calculated
        }

        // return finished when there's no content
        if (knuthParagraphs.size() == 0) {
            setFinished(true);
            return null;
        }

        //PHASE 2: Create line breaks
        return createLineBreaks(context.getBPAlignment(), context);
        /*
        LineBreakPosition lbp = null;
        if (breakpoints == null) {
            // find the optimal line breaking points for each paragraph
            breakpoints = new ArrayList();
            ListIterator paragraphsIterator
                = knuthParagraphs.listIterator(knuthParagraphs.size());
            Paragraph currPar = null;
            while (paragraphsIterator.hasPrevious()) {
                currPar = (Paragraph) paragraphsIterator.previous();
                findBreakingPoints(currPar, context.getStackLimit().opt);
            }
        }*/

        //PHASE 3: Return lines

        /*
        // 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;
        */
    }

    /**
     * Phase 1 of Knuth algorithm: Collect all inline Knuth elements before determining line breaks.
     * @param context the LayoutContext
     * @param availIPD available IPD for line (should be removed!) 
     */
    private void collectInlineKnuthElements(LayoutContext context, MinOptMax availIPD) {
        LayoutContext inlineLC = new LayoutContext(context);

        InlineLevelLayoutManager curLM;
        LinkedList returnedList = null;
        iLineWidth = context.getStackLimit().opt;

        // convert all the text in a sequence of paragraphs made
        // of KnuthBox, KnuthGlue and KnuthPenalty objects
        boolean bPrevWasKnuthBox = false;

        StringBuffer trace = new StringBuffer("LineLM:");

        Paragraph lastPar = null;

        while ((curLM = (InlineLevelLayoutManager) getChildLM()) != null) {
            if ((returnedList
                 = curLM.getNextKnuthElements(inlineLC,
                                              effectiveAlignment))
                != null) {
                if (returnedList.size() == 0) {
                    continue;
                }

                if (lastPar != null) {
                    Object firstObj;
                    KnuthSequence firstSeq = null;
                    firstObj = returnedList.getFirst();
                    if (firstObj instanceof KnuthSequence) {
                        firstSeq = (KnuthSequence) firstObj;
                    }
                    
                    // finish last paragraph before a new block sequence
                    if (firstSeq != null && !firstSeq.isInlineSequence()) {
                        lastPar.endParagraph();
                        ElementListObserver.observe(lastPar, "line", null);
                        lastPar = null;
                        if (log.isTraceEnabled()) {
                            trace.append(" ]");
                        }
                        bPrevWasKnuthBox = false;
                    }
                
                    // does the first element of the first paragraph add to an existing word?
                    if (lastPar != null) {
                        KnuthElement thisElement;
                        if (firstObj instanceof KnuthElement) {
                            thisElement = (KnuthElement) firstObj;
                        } else {
                            thisElement = (KnuthElement) firstSeq.get(0);
                        }
                        if (thisElement.isBox() && !thisElement.isAuxiliary()
                                && bPrevWasKnuthBox) {
                            lastPar.addALetterSpace();
                        }
                    }

                }

                
                // loop over the KnuthSequences (and single KnuthElements) in returnedList
                // (LeafNodeLM descendants may also skip wrapping elements in KnuthSequences
                // to cause fewer container structures)
                // TODO the mixture here adds a little to the complexity. Decide whether:
                // - to leave as is and save some container instances
                // - to use KnuthSequences exclusively (adjustments on leaf-type LMs necessary)
                // See also FootnoteLM.addAnchor() as well as right above this comment
                // for similar code. Or see http://svn.apache.org/viewcvs?rev=230779&view=rev 
                ListIterator iter = returnedList.listIterator();
                while (iter.hasNext()) {
                    Object obj = iter.next();
                    KnuthElement singleElement = null;
                    KnuthSequence sequence = null;
                    if (obj instanceof KnuthElement) {
                        singleElement = (KnuthElement)obj;
                    } else {
                        sequence = (KnuthSequence)obj;
                    }
                    // the sequence contains inline Knuth elements
                    if (singleElement != null || sequence.isInlineSequence()) {
                        // look at the last element 
                        KnuthElement lastElement;
                        if (singleElement != null) {
                            lastElement = singleElement;
                        } else {
                            lastElement = (KnuthElement) sequence.getLast();
                            if (lastElement == null) {
                                throw new NullPointerException(
                                        "Sequence was empty! lastElement is null");
                            }
                        }
                        bPrevWasKnuthBox = lastElement.isBox();

                        // if last paragraph is open, add the new elements to the paragraph
                        // else this is the last paragraph
                        if (lastPar == null) { 
                            lastPar = new Paragraph(this, 
                                                    textAlignment, textAlignmentLast, 
                                                    textIndent.getValue(this), lastLineEndIndent.getValue(this));
                            lastPar.startParagraph(availIPD.opt);
                            if (log.isTraceEnabled()) {
                                trace.append(" [");
                            }
                        } else {
                            if (log.isTraceEnabled()) {
                                trace.append(" +");
                            }
                        }
                        if (singleElement != null) {
                            lastPar.add(singleElement);
                        } else {
                            lastPar.addAll(sequence);
                        }
                        if (log.isTraceEnabled()) {
                            trace.append(" I");
                        }

                        // finish last paragraph if it was closed with a linefeed
                        if (lastElement.isPenalty()
                                && ((KnuthPenalty) lastElement).getP()
                                    == -KnuthPenalty.INFINITE) {
                            // a penalty item whose value is -inf
                            // represents a preserved linefeed,
                            // wich forces a line break
                            lastPar.removeLast();
                            if (lastPar.size() == 0) {
                                //only a forced linefeed on this line 
                                //-> compensate with a zero width box
                                lastPar.add(new KnuthInlineBox(0, null, null, false));
                            }
                            lastPar.endParagraph();
                            ElementListObserver.observe(lastPar, "line", null);
                            lastPar = null;
                            if (log.isTraceEnabled()) {
                                trace.append(" ]");
                            }
                            bPrevWasKnuthBox = false;
                        }
                    } else { // the sequence is a block sequence
/*                        // "wrap" the Position stored in each element of returnedList
                        ListIterator listIter = sequence.listIterator();
                        while (listIter.hasNext()) {
                            KnuthElement returnedElement = (KnuthElement) listIter.next();
                            returnedElement.setPosition
                                (new NonLeafPosition(this,
                                                     returnedElement.getPosition()));
                        }
*/                        knuthParagraphs.add(sequence);
                        if (log.isTraceEnabled()) {
                            trace.append(" B");
                        }
                    }
                } // end of loop over returnedList
            } 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
            }
        }
        if (lastPar != null) {
            lastPar.endParagraph();
            ElementListObserver.observe(lastPar, "line", null);
            if (log.isTraceEnabled()) {
                trace.append(" ]");
            }
        }
        log.trace(trace);
    }

    /**
     * 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, false)) {
            // the first try failed, now try something different
            log.debug("No set of breaking points found with maxAdjustment = " + maxAdjustment);
            if (hyphenationProperties.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, 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
                          + (hyphenationProperties.hyphenate == Constants.EN_TRUE ? " and hyphenation" : ""));
                maxAdjustment = 20;
                if (!findBreakingPoints(par, lineWidth, maxAdjustment, true)) {
                    log.debug("No set of breaking points found, using first-fit algorithm");
                }
            }
        }
    }
    
    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;
        }
        
        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 difference = knuthPara.getDifference(i);
            if (line == lines) {
                difference += par.lineFillerWidth;
            }    
            int textAlign = (line < lines)
                ? textAlignment : textAlignmentLast;
            int indent = (textAlign == EN_CENTER)
                ? difference / 2
                : (textAlign == EN_END) ? difference : 0;
            indent += (line == 1 && knuthParagraphs.indexOf(par) == 0)
                ? textIndent.getValue(this) : 0;
            double ratio = (textAlign == EN_JUSTIFY)
                ? knuthPara.getAdjustRatio(i) : 0;

            int start = knuthPara.getStart(i);
            int end = knuthPara.getEnd(i);
            makeLineBreakPosition(par, start, end, 0, ratio, indent);
        }
        return true;        
    }

    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 lineFollow = follow + halfLeading;

        ListIterator inlineIterator
            = par.listIterator(firstElementIndex);
        for (int j = firstElementIndex;
             j <= lastElementIndex;
             j++) {
            KnuthElement element = (KnuthElement) inlineIterator.next();
            if (element.isBox()) {
                KnuthInlineBox box = (KnuthInlineBox)element;
                if (box.getLead() > lineLead) {
                    lineLead = box.getLead();
                }
                if (box.getTotal() > lineFollow) {
                    lineFollow = box.getTotal();
                }
                if (box.getMiddle() > lineLead + middleShift) {
                    lineLead += box.getMiddle()
                                - lineLead - middleShift;
                }
                if (box.getMiddle() > middlefollow - middleShift) {
                    middlefollow += box.getMiddle()
                                    - middlefollow + middleShift;
                }
            }
        }

        if (lineFollow - lineLead > middlefollow) {
                    middlefollow = lineFollow - lineLead;
        }

        breakpoints.add(insertIndex,
                        new LineBreakPosition(this,
                                              knuthParagraphs.indexOf(par),
                                              lastElementIndex ,
                                              ratio, 0, indent,
                                              lineLead + middlefollow,
                                              lineLead));
    }*/

    
    /**
     * Phase 2 of Knuth algorithm: find optimal break points.
     * @param alignment alignment in BP direction of the paragraph
     * @param context the layout context
     * @return a list of Knuth elements representing broken lines
     */
    private LinkedList createLineBreaks(int alignment, LayoutContext context) {

        // find the optimal line breaking points for each paragraph
        ListIterator paragraphsIterator
            = knuthParagraphs.listIterator(knuthParagraphs.size());
        lineLayoutsList = new ArrayList(knuthParagraphs.size());
        while (paragraphsIterator.hasPrevious()) {
            KnuthSequence seq = (KnuthSequence) paragraphsIterator.previous();
            if (!seq.isInlineSequence()) {
                lineLayouts = createBlockLineBreak(seq);
            } else {
                lineLayouts = findOptimalBreakingPoints(alignment, (Paragraph) seq);
            }
            lineLayoutsList.add(0, lineLayouts);
        }
        
        setFinished(true);
    
        //Post-process the line breaks found
        return postProcessLineBreaks(alignment, context);
    }

    /**
     * create a single line layout possibility with a single linebreak
     * for a block sequence
     * @param seq the Knuth sequence for which the linebreak is created
     * @return the line layout possibilities for the paragraph
     */
    private LineLayoutPossibilities createBlockLineBreak(KnuthSequence seq) {
        //TODO Should this really create only a single LineBreakPosition???
        //This creates an implicit keep-together on the nested block-level FOs.
        lineLayouts = new LineLayoutPossibilities();
        lineLayouts.addPossibility(1, 0);
        int lineHeight = 0, lineStretch = 0, lineShrink = 0;
        ListIterator seqIterator = seq.listIterator();
        while (seqIterator.hasNext()) {
            KnuthElement element = (KnuthElement) seqIterator.next();
            lineHeight += element.getW();
            if (element.isGlue()) {
                lineStretch += element.getY();
                lineShrink += element.getZ();
            }
        }
        LineBreakPosition lbp = new LineBreakPosition(this,
                knuthParagraphs.indexOf(seq), seq.size() - 1,
                lineShrink, lineStretch, 0, 0, 0, 0, lineHeight,
                iLineWidth, 0, 0, 0);
        lineLayouts.addBreakPosition(lbp, 0);
        return lineLayouts;
    }

    /**
     * Fint the optimal linebreaks for a paragraph
     * @param alignment alignment of the paragraph
     * @param currPar the Paragraph for which the linebreaks are found
     * @return the line layout possibilities for the paragraph
     */
    private LineLayoutPossibilities findOptimalBreakingPoints(int alignment, Paragraph currPar) {
        lineLayouts = new LineLayoutPossibilities();
        double maxAdjustment = 1;
        int iBPcount = 0;
        LineBreakingAlgorithm alg = new LineBreakingAlgorithm(alignment,
                                        textAlignment, textAlignmentLast,
                                        textIndent.getValue(this), currPar.lineFiller.opt,
                                        lineHeight.getValue(this), lead, follow,
                                        (knuthParagraphs.indexOf(currPar) == 0),
                                        hyphenationLadderCount.getEnum() == EN_NO_LIMIT ?
                                                0 : hyphenationLadderCount.getValue(),
                                        this);
   
        if (hyphenationProperties.hyphenate == EN_TRUE) {
            findHyphenationPoints(currPar);
        }
   
        // first try
        int allowedBreaks;
        if (wrapOption == EN_NO_WRAP) {
            allowedBreaks = BreakingAlgorithm.ONLY_FORCED_BREAKS;
        } else {
            allowedBreaks = BreakingAlgorithm.NO_FLAGGED_PENALTIES;
        }
        alg.setConstantLineWidth(iLineWidth);
        iBPcount = alg.findBreakingPoints(currPar,
                                          maxAdjustment, false, allowedBreaks);
        if (iBPcount == 0 || alignment == EN_JUSTIFY) {
            // if the first try found a set of breaking points, save them
            if (iBPcount > 0) {
                alg.resetAlgorithm();
                lineLayouts.savePossibilities(false);
            } else {
                // the first try failed
                log.debug("No set of breaking points found with maxAdjustment = " + maxAdjustment);
            }
   
            // now try something different
            log.debug("Hyphenation possible? " + (hyphenationProperties.hyphenate == EN_TRUE));
            if (hyphenationProperties.hyphenate == EN_TRUE
                && !(allowedBreaks == BreakingAlgorithm.ONLY_FORCED_BREAKS)) {
                // consider every hyphenation point as a legal break
                allowedBreaks = BreakingAlgorithm.ALL_BREAKS;
            } else {
                // try with a higher threshold
                maxAdjustment = 5;
            }
   
            if ((iBPcount
                 = alg.findBreakingPoints(currPar,
                                          maxAdjustment, false, allowedBreaks)) == 0) {
                // the second try failed too, try with a huge threshold
                // and force the algorithm to find
                // a set of breaking points
                log.debug("No set of breaking points found with maxAdjustment = " + maxAdjustment
                                 + (hyphenationProperties.hyphenate == EN_TRUE ? " and hyphenation" : ""));
                maxAdjustment = 20;
                iBPcount
                    = alg.findBreakingPoints(currPar,
                                             maxAdjustment, true, allowedBreaks);
            }
   
            // use non-hyphenated breaks, when possible
            lineLayouts.restorePossibilities();
   
            /* extension (not in the XSL FO recommendation): if vertical alignment
               is justify and the paragraph has only one layout, try using 
               shorter or longer lines */
            //TODO This code snippet is disabled. Reenable?
            if (false && alignment == EN_JUSTIFY && textAlignment == EN_JUSTIFY) {
                //log.debug("LLM.getNextKnuthElements> layouts with more lines? " + lineLayouts.canUseMoreLines());
                //log.debug("                          layouts with fewer lines? " + lineLayouts.canUseLessLines());
                if (!lineLayouts.canUseMoreLines()) {
                    alg.resetAlgorithm();
                    lineLayouts.savePossibilities(true);
                    // try with shorter lines
                    int savedLineWidth = iLineWidth;
                    iLineWidth = (int) (iLineWidth * 0.95);
                    iBPcount = alg.findBreakingPoints(currPar,
                             maxAdjustment, true, allowedBreaks);
                    // use normal lines, when possible
                    lineLayouts.restorePossibilities();
                    iLineWidth = savedLineWidth;
                }
                if (!lineLayouts.canUseLessLines()) {
                    alg.resetAlgorithm();
                    lineLayouts.savePossibilities(true);
                    // try with longer lines
                    int savedLineWidth = iLineWidth;
                    iLineWidth = (int) (iLineWidth * 1.05);
                    alg.setConstantLineWidth(iLineWidth);
                    iBPcount = alg.findBreakingPoints(currPar,
                            maxAdjustment, true, allowedBreaks);
                    // use normal lines, when possible
                    lineLayouts.restorePossibilities();
                    iLineWidth = savedLineWidth;
                }
                //log.debug("LLM.getNextKnuthElements> now, layouts with more lines? " + lineLayouts.canUseMoreLines());
                //log.debug("                          now, layouts with fewer lines? " + lineLayouts.canUseLessLines());
            }
        }
        return lineLayouts;
    }

    /**
     * Creates the element list in BP direction for the broken lines.
     * @param alignment the currently applicable vertical alignment
     * @param context the layout context
     * @return the newly built element list
     */
    private LinkedList postProcessLineBreaks(int alignment, LayoutContext context) {
    
        LinkedList returnList = new LinkedList();
        
        for (int p = 0; p < knuthParagraphs.size(); p++) {
            // null penalty between paragraphs
            if (p > 0 && !((BlockLevelLayoutManager) parentLM).mustKeepTogether()) {
                returnList.add(new BreakElement(
                        new Position(this), 0, context));
                //returnList.add(new KnuthPenalty(0, 0, false, new Position(this), false));
            }
        
            lineLayouts = (LineLayoutPossibilities)lineLayoutsList.get(p);
            KnuthSequence seq = (KnuthSequence) knuthParagraphs.get(p);

            if (!seq.isInlineSequence()) {
                LinkedList targetList = new LinkedList();
                ListIterator listIter = seq.listIterator();
                while (listIter.hasNext()) {
                    KnuthElement tempElement;
                    tempElement = (KnuthElement) listIter.next();
                    if (tempElement.getLayoutManager() != this) {
                        tempElement.setPosition(notifyPos(new NonLeafPosition(this,
                                tempElement.getPosition())));
                    }
                    targetList.add(tempElement);
                }
                returnList.addAll(targetList); 
            } else if (seq.isInlineSequence() && alignment == EN_JUSTIFY) {
                /* justified vertical alignment (not in the XSL FO recommendation):
                   create a multi-layout sequence whose elements will contain 
                   a conventional Position */
                Position returnPosition = new LeafPosition(this, p);
                createElements(returnList, lineLayouts, returnPosition);
            } else {
                /* "normal" vertical alignment: create a sequence whose boxes
                   represent effective lines, and contain LineBreakPositions */
                Position returnPosition = new LeafPosition(this, p);
                int startIndex = 0;
                for (int i = 0;
                        i < lineLayouts.getChosenLineCount();
                        i++) {
                    if (!((BlockLevelLayoutManager) parentLM).mustKeepTogether()
                            && i >= fobj.getOrphans()
                            && i <= lineLayouts.getChosenLineCount() - fobj.getWidows()
                            && returnList.size() > 0) {
                        // null penalty allowing a page break between lines
                        returnList.add(new BreakElement(
                                returnPosition, 0, context));
                        //returnList.add(new KnuthPenalty(0, 0, false, returnPosition, false));
                    }
                    int endIndex = ((LineBreakPosition) lineLayouts.getChosenPosition(i)).getLeafPos();
                    // create a list of the FootnoteBodyLM handling footnotes 
                    // whose citations are in this line
                    LinkedList footnoteList = new LinkedList();
                    ListIterator elementIterator = seq.listIterator(startIndex);
                    while (elementIterator.nextIndex() <= endIndex) {
                        KnuthElement element = (KnuthElement) elementIterator.next();
                        if (element instanceof KnuthInlineBox
                            && ((KnuthInlineBox) element).isAnchor()) {
                            footnoteList.add(((KnuthInlineBox) element).getFootnoteBodyLM());
                        } else if (element instanceof KnuthBlockBox) {
                            footnoteList.addAll(((KnuthBlockBox) element).getFootnoteBodyLMs());
                        }
                    }
                    startIndex = endIndex + 1;
                    LineBreakPosition lbp = (LineBreakPosition) lineLayouts.getChosenPosition(i);
                    returnList.add(new KnuthBlockBox(lbp.lineHeight + lbp.spaceBefore + lbp.spaceAfter
                                                    , footnoteList, lbp, false));
                    /* // add stretch and shrink to the returnlist
                    if (!seq.isInlineSequence()
                            && lbp.availableStretch != 0 || lbp.availableShrink != 0) {
                        returnList.add(new KnuthPenalty(0, -KnuthElement.INFINITE,
                                false, new Position(this), false));
                        returnList.add(new KnuthGlue(0, lbp.availableStretch, lbp.availableShrink,
                                new Position(this), false));
                    }
                    */
                }
            }
        }
        
        return returnList;
    }


    private void createElements(List list, LineLayoutPossibilities lineLayouts,
                                Position elementPosition) {
        /* number of normal, inner lines */
        int nInnerLines = 0;
        /* number of lines that can be used in order to fill more space */
        int nOptionalLines = 0;
        /* number of lines that can be used in order to fill more space
           only if the paragraph is not parted */
        int nConditionalOptionalLines = 0;
        /* number of lines that can be omitted in order to fill less space */
        int nEliminableLines = 0;
        /* number of lines that can be omitted in order to fill less space
           only if the paragraph is not parted */
        int nConditionalEliminableLines = 0;
        /* number of the first unbreakable lines */
        int nFirstLines = fobj.getOrphans();
        /* number of the last unbreakable lines */
        int nLastLines = fobj.getWidows();
        /* sub-sequence used to separate the elements representing different lines */
        List breaker = new LinkedList();

        /* comment out the next lines in order to test particular situations */
        if (fobj.getOrphans() + fobj.getWidows() <= lineLayouts.getMinLineCount()) {
            nInnerLines = lineLayouts.getMinLineCount() - (fobj.getOrphans() + fobj.getWidows());
            nOptionalLines = lineLayouts.getMaxLineCount() - lineLayouts.getOptLineCount();
            nEliminableLines = lineLayouts.getOptLineCount() - lineLayouts.getMinLineCount();
        } else if (fobj.getOrphans() + fobj.getWidows() <= lineLayouts.getOptLineCount()) {
            nOptionalLines = lineLayouts.getMaxLineCount() - lineLayouts.getOptLineCount();
            nEliminableLines = lineLayouts.getOptLineCount() - (fobj.getOrphans() + fobj.getWidows());
            nConditionalEliminableLines = (fobj.getOrphans() + fobj.getWidows()) - lineLayouts.getMinLineCount();
        } else if (fobj.getOrphans() + fobj.getWidows() <= lineLayouts.getMaxLineCount()) {
            nOptionalLines = lineLayouts.getMaxLineCount() - (fobj.getOrphans() + fobj.getWidows());
            nConditionalOptionalLines = (fobj.getOrphans() + fobj.getWidows()) - lineLayouts.getOptLineCount();
            nConditionalEliminableLines = lineLayouts.getOptLineCount() - lineLayouts.getMinLineCount();
            nFirstLines -= nConditionalOptionalLines;
        } else {
            nConditionalOptionalLines = lineLayouts.getMaxLineCount() - lineLayouts.getOptLineCount();
            nConditionalEliminableLines = lineLayouts.getOptLineCount() - lineLayouts.getMinLineCount();
            nFirstLines = lineLayouts.getOptLineCount();
            nLastLines = 0;
        }
        /* comment out the previous lines in order to test particular situations */

        /* use these lines to test particular situations
        nInnerLines = 0;
        nOptionalLines = 1;
        nConditionalOptionalLines = 2;
        nEliminableLines = 0;
        nConditionalEliminableLines = 0;
        nFirstLines = 1;
        nLastLines = 3;
        */

        if (nLastLines != 0
            && (nConditionalOptionalLines > 0 || nConditionalEliminableLines > 0)) {
            breaker.add(new KnuthPenalty(0, KnuthElement.INFINITE, false, elementPosition, false));
            breaker.add(new KnuthGlue(0, -nConditionalOptionalLines * constantLineHeight,
                                        -nConditionalEliminableLines * constantLineHeight,
                                        LINE_NUMBER_ADJUSTMENT, elementPosition, false));
            breaker.add(new KnuthPenalty(nConditionalOptionalLines * constantLineHeight,
                                           0, false, elementPosition, false));
            breaker.add(new KnuthGlue(0, nConditionalOptionalLines * constantLineHeight,
                                        nConditionalEliminableLines * constantLineHeight,
                                        LINE_NUMBER_ADJUSTMENT, elementPosition, false));
        } else if (nLastLines != 0) {
            breaker.add(new KnuthPenalty(0, 0, false, elementPosition, false));
        }

        //log.debug("first=" + nFirstLines + " inner=" + nInnerLines
        //                   + " optional=" + nOptionalLines + " eliminable=" + nEliminableLines
        //                   + " last=" + nLastLines
        //                   + " (condOpt=" + nConditionalOptionalLines + " condEl=" + nConditionalEliminableLines + ")");

        // creation of the elements:
        // first group of lines
        list.add(new KnuthBox(nFirstLines * constantLineHeight, elementPosition,
                              (nLastLines == 0
                               && nConditionalOptionalLines == 0
                               && nConditionalEliminableLines == 0 ? true : false)));
        if (nConditionalOptionalLines > 0
            || nConditionalEliminableLines > 0) {
            list.add(new KnuthPenalty(0, KnuthElement.INFINITE, false, elementPosition, false));
            list.add(new KnuthGlue(0, nConditionalOptionalLines * constantLineHeight,
                                   nConditionalEliminableLines * constantLineHeight,
                                   LINE_NUMBER_ADJUSTMENT, elementPosition, false));
            list.add(new KnuthBox(0, elementPosition,
                                  (nLastLines == 0 ? true : false)));
        }

        // optional lines
        for (int i = 0; i < nOptionalLines; i++) {
            list.addAll(breaker);
            list.add(new KnuthBox(0, elementPosition, false));
            list.add(new KnuthPenalty(0, KnuthElement.INFINITE, false, elementPosition, false));
            list.add(new KnuthGlue(0, 1 * constantLineHeight, 0,
                                   LINE_NUMBER_ADJUSTMENT, elementPosition, false));
            list.add(new KnuthBox(0, elementPosition, false));
        }

        // eliminable lines
        for (int i = 0; i < nEliminableLines; i++) {
            list.addAll(breaker);
            list.add(new KnuthBox(1 * constantLineHeight, elementPosition, false));
            list.add(new KnuthPenalty(0, KnuthElement.INFINITE, false, elementPosition, false));
            list.add(new KnuthGlue(0, 0, 1 * constantLineHeight,
                                   LINE_NUMBER_ADJUSTMENT, elementPosition, false));
            list.add(new KnuthBox(0, elementPosition, false));
        }

        // inner lines
        for (int i = 0; i < nInnerLines; i++) {
            list.addAll(breaker);
            list.add(new KnuthBox(1 * constantLineHeight, elementPosition, false));
        }

        // last group of lines
        if (nLastLines > 0) {
            list.addAll(breaker);
            list.add(new KnuthBox(nLastLines * constantLineHeight,
                                  elementPosition, true));
        }
    }

    /**
     * @see org.apache.fop.layoutmgr.BlockLevelLayoutManager#mustKeepTogether
     */
    public boolean mustKeepTogether() {
        return false;
    }

    /**
     * @see org.apache.fop.layoutmgr.BlockLevelLayoutManager#mustKeepWithPrevious
     */
    public boolean mustKeepWithPrevious() {
        return false;
    }

    /**
     * @see org.apache.fop.layoutmgr.BlockLevelLayoutManager#mustKeepWithNext
     */
    public boolean mustKeepWithNext() {
        return false;
    }

    /**
     * @see org.apache.fop.layoutmgr.BlockLevelLayoutManager#negotiateBPDAdjustment(int, org.apache.fop.layoutmgr.KnuthElement)
     */
    public int negotiateBPDAdjustment(int adj, KnuthElement lastElement) {
        LeafPosition pos = (LeafPosition)lastElement.getPosition();
        int totalAdj = adj;
        //if (lastElement.isPenalty()) {
        //    totalAdj += lastElement.getW();
        //}
        //int lineNumberDifference = (int)((double) totalAdj / constantLineHeight);
        int lineNumberDifference = (int) Math.round((double) totalAdj / constantLineHeight + (adj > 0 ? - 0.4 : 0.4));
        //log.debug("   LLM> variazione calcolata = " + ((double) totalAdj / constantLineHeight) + " variazione applicata = " + lineNumberDifference);
        lineLayouts = (LineLayoutPossibilities)lineLayoutsList.get(pos.getLeafPos());
        lineNumberDifference = lineLayouts.applyLineCountAdjustment(lineNumberDifference);
        return lineNumberDifference * constantLineHeight;
    }

    /**
     * @see org.apache.fop.layoutmgr.BlockLevelLayoutManager#discardSpace(KnuthGlue)
     */
    public void discardSpace(KnuthGlue spaceGlue) {
    }

    /**
     * @see org.apache.fop.layoutmgr.LayoutManager#getChangedKnuthElements(List, int)
     */
    public LinkedList getChangedKnuthElements(List oldList, int alignment) {
        LinkedList returnList = new LinkedList();
        for (int p = 0; p < knuthParagraphs.size(); p++) {
            lineLayouts = (LineLayoutPossibilities)lineLayoutsList.get(p);
            //log.debug("demerits of the chosen layout: " + lineLayouts.getChosenDemerits());
            for (int i = 0; i < lineLayouts.getChosenLineCount(); i++) {
                if (!((BlockLevelLayoutManager) parentLM).mustKeepTogether()
                    && i >= fobj.getOrphans()
                    && i <= lineLayouts.getChosenLineCount() - fobj.getWidows()) {
                    // null penalty allowing a page break between lines
                    returnList.add(new KnuthPenalty(0, 0, false, new Position(this), false));
                }
                LineBreakPosition lbp = (LineBreakPosition) lineLayouts.getChosenPosition(i);
                //log.debug("LLM.getChangedKnuthElements> lineWidth= " + lbp.lineWidth + " difference= " + lbp.difference);
                //log.debug("                             shrink= " + lbp.availableShrink + " stretch= " + lbp.availableStretch);

                //log.debug("linewidth= " + lbp.lineWidth + " difference= " + lbp.difference + " indent= " + lbp.startIndent);
                MinOptMax contentIPD;
                if (alignment == EN_JUSTIFY) {
                    contentIPD = new MinOptMax(
                        lbp.lineWidth - lbp.difference - lbp.availableShrink, 
                        lbp.lineWidth - lbp.difference, 
                        lbp.lineWidth - lbp.difference + lbp.availableStretch);
                } else if (alignment == EN_CENTER) {
                    contentIPD = new MinOptMax(lbp.lineWidth - 2 * lbp.startIndent);
                } else if (alignment == EN_END) {
                    contentIPD = new MinOptMax(lbp.lineWidth - lbp.startIndent);
                } else {
                    contentIPD = new MinOptMax(lbp.lineWidth - lbp.difference + lbp.startIndent);
                }
                returnList.add(new KnuthBlockBox(lbp.lineHeight,
                                                 contentIPD,
                                                 (lbp.ipdAdjust != 0 ? lbp.lineWidth - lbp.difference : 0),
                                                 lbp, false));
            }
        }
        return returnList;
    }

    /**
     * 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 {
                        if (currLM != nextElement.getLayoutManager()) {
                            currLM = (InlineLevelLayoutManager) nextElement.getLayoutManager();
                            updateList.add(new Update(currLM, currParIterator.previousIndex()));
                        }
                        // 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();
    }

    /**
     * Line area is always considered to act as a fence.
     * @param isNotFirst ignored
     * @return always true
     */
    protected boolean hasLeadingFence(boolean isNotFirst) {
        return true;
    }

    /**
     * Line area is always considered to act as a fence.
     * @param isNotLast ignored
     * @return always true
     */
    protected boolean hasTrailingFence(boolean isNotLast) {
        return true;
    }

    private HyphContext getHyphenContext(StringBuffer sbChars) {
        // Find all hyphenation points in this word
        // (get in an array of offsets)
        // hyphenationProperties 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(hyphenationProperties.language,
                                   hyphenationProperties.country, sbChars.toString(),
                                   hyphenationProperties.hyphenationRemainCharacterCount,
                                   hyphenationProperties.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;
        }
    }

    /**
     * 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) lineLayouts.getChosenPosition(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) {
        LayoutManager childLM;
        LayoutContext lc = new LayoutContext(0);
        lc.setAlignmentContext(alignmentContext);
        int iCurrParIndex;
        while (parentIter.hasNext()) {
            Position pos = (Position) parentIter.next();
            if (pos instanceof LineBreakPosition) {
                ListIterator seqIterator = null;
                KnuthElement tempElement = null;
                // the TLM which created the last KnuthElement in this line
                LayoutManager lastLM = null;
    
                LineBreakPosition lbp = (LineBreakPosition) pos;
                iCurrParIndex = lbp.iParIndex;
                KnuthSequence seq = (KnuthSequence) knuthParagraphs.get(iCurrParIndex); 
                iEndElement = lbp.getLeafPos();
    
                LineArea lineArea = new LineArea((lbp.getLeafPos() < seq.size() - 1 ? textAlignment : textAlignmentLast),
                                                 lbp.difference, lbp.availableStretch, lbp.availableShrink);
                lineArea.setStartIndent(lbp.startIndent);
                lineArea.setBPD(lbp.lineHeight);
                lineArea.setIPD(lbp.lineWidth);
                lineArea.addTrait(Trait.SPACE_BEFORE, new Integer(lbp.spaceBefore));
                lineArea.addTrait(Trait.SPACE_AFTER, new Integer(lbp.spaceAfter));
                alignmentContext.resizeLine(lbp.lineHeight, lbp.baseline);

                if (seq instanceof Paragraph) {
                    Paragraph currPar = (Paragraph) seq;
                    // ignore the first elements added by the LineLayoutManager
                    iStartElement += (iStartElement == 0) ? currPar.ignoreAtStart : 0;
                    
                    // if this is the last line area that for this paragraph,
                    // ignore the last elements added by the LineLayoutManager and
                    // subtract the last-line-end-indent from the area ipd
                    if (iEndElement == (currPar.size() - 1)) {
                        iEndElement -= currPar.ignoreAtEnd;
                        lineArea.setIPD(lineArea.getIPD() - lastLineEndIndent.getValue(this));
                    }
                }
                
                // ignore the last element in the line if it is a KnuthGlue object
                seqIterator = seq.listIterator(iEndElement);
                tempElement = (KnuthElement) seqIterator.next();
                if (tempElement.isGlue()) {
                    iEndElement--;
                    // this returns the same KnuthElement
                    seqIterator.previous();
                    tempElement = (KnuthElement) seqIterator.previous();
                }
                lastLM = tempElement.getLayoutManager();
    
                // ignore KnuthGlue and KnuthPenalty objects
                // at the beginning of the line
                seqIterator = seq.listIterator(iStartElement);
                tempElement = (KnuthElement) seqIterator.next();
                while (!tempElement.isBox() && seqIterator.hasNext()) {
                    tempElement = (KnuthElement) seqIterator.next();
                    iStartElement++;
                }
    
                // Add the inline areas to lineArea
                PositionIterator inlinePosIter
                    = new KnuthPossPosIter(seq, iStartElement,
                                           iEndElement + 1);
    
                iStartElement = lbp.getLeafPos() + 1;
                if (iStartElement == seq.size()) {
                    // advance to next paragraph
                    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);

                /* extension (not in the XSL FO recommendation): if the left and right margins
                   have been optimized, recompute indents and / or adjust ratio, according
                   to the paragraph horizontal alignment */
                if (false && textAlignment == EN_JUSTIFY) {
                    // re-compute space adjust ratio
                    int updatedDifference = context.getStackLimit().opt - lbp.lineWidth + lbp.difference;
                    double updatedRatio = 0.0;
                    if (updatedDifference > 0) {
                        updatedRatio = (float) updatedDifference / lbp.availableStretch;
                    } else if (updatedDifference < 0) {
                        updatedRatio = (float) updatedDifference / lbp.availableShrink;
                    }
                    lc.setIPDAdjust(updatedRatio);
                    //log.debug("LLM.addAreas> old difference = " + lbp.difference + " new difference = " + updatedDifference);
                    //log.debug("              old ratio = " + lbp.ipdAdjust + " new ratio = " + updatedRatio);
                } else if (false && textAlignment == EN_CENTER) {
                    // re-compute indent
                    int updatedIndent = lbp.startIndent
                                            + (context.getStackLimit().opt - lbp.lineWidth) / 2;
                    lineArea.setStartIndent(updatedIndent);
                } else if (false && textAlignment == EN_END) {
                    // re-compute indent
                    int updatedIndent = lbp.startIndent 
                                            + (context.getStackLimit().opt - lbp.lineWidth);
                    lineArea.setStartIndent(updatedIndent);
                }

                setCurrentArea(lineArea);
                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 display-align is distribute, add space after 
                if (context.getSpaceAfter() > 0
                    && (!context.isLastArea() || parentIter.hasNext())) {
                    lineArea.setBPD(lineArea.getBPD() + context.getSpaceAfter());
                }
                lineArea.finalize();
                parentLM.addChildArea(lineArea);
            } else if (pos instanceof NonLeafPosition) {
                // Nested block-level content;
                // go down the LM stack again;
                // collect all consecutive NonLeafPosition objects,
                // "unwrap" them and put the child positions in a new list.
                LinkedList positionList = new LinkedList();
                Position innerPosition;
                innerPosition = ((NonLeafPosition) pos).getPosition();
                positionList.add(innerPosition);
                while (parentIter.hasNext()) {
                    pos = (Position)parentIter.peekNext();
                    if (!(pos instanceof NonLeafPosition)) {
                        break;
                    }
                    pos = (Position) parentIter.next();
                    innerPosition = ((NonLeafPosition) pos).getPosition();
                    positionList.add(innerPosition);
                }
                
                // do we have the last LM?
                LayoutManager lastLM = null;
                if (!parentIter.hasNext()) {
                    lastLM = innerPosition.getLM();
                }

                // this may be wrong; not all areas belong inside a single line area
                // see InlineStackingLM.addChildArea
                LineArea lineArea = new LineArea();
                setCurrentArea(lineArea);
                setChildContext(lc);

                PositionIterator childPosIter = new StackingIter(positionList.listIterator());
                LayoutContext blocklc = new LayoutContext(0);
                blocklc.setLeadingSpace(new SpaceSpecifier(true));
                blocklc.setTrailingSpace(new SpaceSpecifier(false));
                blocklc.setFlags(LayoutContext.RESOLVE_LEADING_SPACE, true);
                while ((childLM = childPosIter.getNextChildLM()) != null) {
                    // set last area flag
                    blocklc.setFlags(LayoutContext.LAST_AREA,
                            (context.isLastArea() && childLM == lastLM));
                    blocklc.setStackLimit(context.getStackLimit());
                    // Add the line areas to Area
                    childLM.addAreas(childPosIter, blocklc);
                    blocklc.setLeadingSpace(blocklc.getTrailingSpace());
                    blocklc.setTrailingSpace(new SpaceSpecifier(false));
                }
                lineArea.updateExtentsFromChildren();
                parentLM.addChildArea(lineArea);
            } else {
                // pos was the Position inside a penalty item, nothing to do
            }
        }
        setCurrentArea(null); // ?? necessary
    }

    /**
     * @see org.apache.fop.layoutmgr.LayoutManager#addChildArea(Area)
     */
    public void addChildArea(Area childArea) {
        // Make sure childArea is inline area
        if (childArea instanceof InlineArea) {
            Area parent = getCurrentArea();
            if (getContext().resolveLeadingSpace()) {
                addSpace(parent,
                         getContext().getLeadingSpace().resolve(false),
                         getContext().getSpaceAdjust());
            }
            parent.addChildArea(childArea);
        }
    }

    // --------- Property Resolution related functions --------- //
    
    /**
     * @see org.apache.fop.layoutmgr.LayoutManager#getGeneratesBlockArea
     */
    public boolean getGeneratesBlockArea() {
        return true;
    }
   
    /**
     * @see org.apache.fop.layoutmgr.LayoutManager#getGeneratesLineArea
     */
    public boolean getGeneratesLineArea() {
        return true;
    }
}