* 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 $ */

* 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.

*/

                               implements BlockLevelLayoutManager {

    private Block fobj;

   

    public void initialize() {

        textAlignment = fobj.getTextAlign();

        textAlignmentLast = fobj.getTextAlignLast();

        textIndent = fobj.getTextIndent();

        lastLineEndIndent = fobj.getLastLineEndIndent();

        hyphenationProperties = fobj.getCommonHyphenation();

        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 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,

                                      LineLayoutManager llm) {

            super(textAlign, textAlignLast, first, false);

            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;

            }

            //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

                        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),

                                        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());