org.apache.xmlgraphics/fop/2.3 : org/apache/fop/layoutmgr/BreakingAlgorithm.java

BreakingAlgorithm
http://xmlgraphics.apache.org/fop/: Apache FOP (Formatting Objects Processor) is the world's first print formatter driven by XSL formatting objects (XSL-FO) and the world's first output independent formatter. It is a Java application that reads a formatting object (FO) tree and renders the resulting pages to a specified output. Output formats currently supported include PDF, PCL, PS, AFP, TIFF, PNG, SVG, XML (area tree representation), Print, AWT and TXT. The primary output target is PDF. (Apache Software Foundation)
The Apache Software License, Version 2.0
/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You 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: BreakingAlgorithm.java 1805173 2017-08-16 10:50:04Z ssteiner $ */

package org.apache.fop.layoutmgr;

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;

import org.apache.fop.fo.Constants;

The set of nodes is sorted into lines indexed into activeLines. The nodes in each line are linked together in a single linked list by the KnuthNode.next field. The activeLines array contains a link to the head of the linked list in index 'line*2' and a link to the tail at index 'line*2+1'. 
The set of active nodes can be traversed by
for (int line = startLine; line < endLine; line++) {
    for (KnuthNode node = getNode(line); node != null; node = node.next) {
        // Do something with 'node'
    }
}

/**
 * The set of nodes is sorted into lines indexed into activeLines.
 * The nodes in each line are linked together in a single linked list by the
 * {@link KnuthNode#next} field. The activeLines array contains a link to the head of
 * the linked list in index 'line*2' and a link to the tail at index 'line*2+1'.
 * <p>
 * The set of active nodes can be traversed by
 * <pre>
 * for (int line = startLine; line &lt; endLine; line++) {
 *     for (KnuthNode node = getNode(line); node != null; node = node.next) {
 *         // Do something with 'node'
 *     }
 * }
 * </pre>
 */
public abstract class BreakingAlgorithm {

    the logger for the class /** the logger for the class */
    protected static final Log log = LogFactory.getLog(BreakingAlgorithm.class);

    Maximum adjustment ration /** Maximum adjustment ration */
    protected static final int INFINITE_RATIO = 1000;

    private static final int MAX_RECOVERY_ATTEMPTS = 5;

    // constants identifying a subset of the feasible breaks
    All feasible breaks are ok. /** All feasible breaks are ok. */
    public static final int ALL_BREAKS = 0;
    This forbids hyphenation. /** This forbids hyphenation. */
    public static final int NO_FLAGGED_PENALTIES = 1;
    wrap-option = "no-wrap". /** wrap-option = "no-wrap". */
    public static final int ONLY_FORCED_BREAKS = 2;

    Holder for symbolic literals for the fitness classes /** Holder for symbolic literals for the fitness classes */
    static final class FitnessClasses {

        private FitnessClasses() {
        }

        static final int VERY_TIGHT = 0;
        static final int TIGHT = 1;
        static final int LOOSE = 2;
        static final int VERY_LOOSE = 3;

        static final String[] NAMES = {
            "VERY TIGHT", "TIGHT", "LOOSE", "VERY LOOSE"
        };

        Figure out the fitness class of this line (tight, loose,
very tight or very loose).
See the section on "More Bells and Whistles" in Knuth's
"Breaking Paragraphs Into Lines".
Params: adjustRatio – the adjustment ratio
Returns: the fitness class/**
         * Figure out the fitness class of this line (tight, loose,
         * very tight or very loose).
         * See the section on "More Bells and Whistles" in Knuth's
         * "Breaking Paragraphs Into Lines".
         *
         * @param adjustRatio the adjustment ratio
         * @return the fitness class
         */
        static int computeFitness(double adjustRatio) {
            if (adjustRatio < -0.5) {
                return FitnessClasses.VERY_TIGHT;
            } else if (adjustRatio <= 0.5) {
                return FitnessClasses.TIGHT;
            } else if (adjustRatio <= 1.0) {
                return FitnessClasses.LOOSE;
            } else {
                return FitnessClasses.VERY_LOOSE;
            }
        }
    }

    // parameters of Knuth's algorithm:
    Demerit for consecutive lines ending at flagged penalties. /** Demerit for consecutive lines ending at flagged penalties. */
    protected int repeatedFlaggedDemerit = KnuthPenalty.FLAGGED_PENALTY;
    Demerit for consecutive lines belonging to incompatible fitness classes . /** Demerit for consecutive lines belonging to incompatible fitness classes . */
    protected int incompatibleFitnessDemerit = KnuthPenalty.FLAGGED_PENALTY;
    Maximum number of consecutive lines ending with a flagged penalty.
Only a value >= 1 is a significant limit.
/** Maximum number of consecutive lines ending with a flagged penalty.
     * Only a value &gt;= 1 is a significant limit.
     */
    protected int maxFlaggedPenaltiesCount;

    The threshold for considering breaks to be acceptable. The adjustment ratio must be
inferior to this threshold.
/**
     * The threshold for considering breaks to be acceptable. The adjustment ratio must be
     * inferior to this threshold.
     */
    private double threshold;

    The paragraph of KnuthElements.
/**
     * The paragraph of KnuthElements.
     */
    protected KnuthSequence par;

    The width of a line (or height of a column in page-breaking mode).
-1 indicates that the line widths are different for each line.
/**
     * The width of a line (or height of a column in page-breaking mode).
     * -1 indicates that the line widths are different for each line.
     */
    protected int lineWidth = -1;
    Force the algorithm to find a set of breakpoints, even if no feasible breakpoints
exist.
/** Force the algorithm to find a set of breakpoints, even if no feasible breakpoints
     * exist.
     */
    private boolean force;
    If set to true, doesn't ignore break possibilities which are definitely too short. /** If set to true, doesn't ignore break possibilities which are definitely too short. */
    protected boolean considerTooShort;

    When in forced mode, the best node leading to a too long line. The line will be
too long anyway, but this one will lead to a paragraph with fewest demerits.
/** When in forced mode, the best node leading to a too long line. The line will be
     * too long anyway, but this one will lead to a paragraph with fewest demerits.
     */
    private KnuthNode lastTooLong;
    When in forced mode, the best node leading to a too short line. The line will be
too short anyway, but this one will lead to a paragraph with fewest demerits.
/** When in forced mode, the best node leading to a too short line. The line will be
     * too short anyway, but this one will lead to a paragraph with fewest demerits.
     */
    private KnuthNode lastTooShort;
    The node to be reactivated if no set of feasible breakpoints can be found for this
paragraph.
/** The node to be reactivated if no set of feasible breakpoints can be found for this
     * paragraph.
     */
    private KnuthNode lastDeactivated;

    Alignment of the paragraph/page. One of EN_START, EN_JUSTIFY, etc. /** Alignment of the paragraph/page. One of EN_START, EN_JUSTIFY, etc. */
    protected int alignment;
    Alignment of the paragraph's last line. /** Alignment of the paragraph's last line. */
    protected int alignmentLast;
    Used to handle the text-indent property (indent the first line of a paragraph). /** Used to handle the text-indent property (indent the first line of a paragraph). */
    protected boolean indentFirstPart;

    The set of active nodes in ascending line order. For each line l, activeLines[2l] contains a
link to l's first active node, and activeLines[2l+1] a link to l's last active node. The
line number l corresponds to the number of the line ending at the node's breakpoint.
/**
     * The set of active nodes in ascending line order. For each line l, activeLines[2l] contains a
     * link to l's first active node, and activeLines[2l+1] a link to l's last active node. The
     * line number l corresponds to the number of the line ending at the node's breakpoint.
     */
    protected KnuthNode[] activeLines;

    The number of active nodes.
/**
     * The number of active nodes.
     */
    protected int activeNodeCount;

    The lowest available line in the set of active nodes.
/**
     * The lowest available line in the set of active nodes.
     */
    protected int startLine;

    The highest + 1 available line in the set of active nodes.
/**
     * The highest + 1 available line in the set of active nodes.
     */
    protected int endLine;

    The total width of all elements handled so far.
/**
     * The total width of all elements handled so far.
     */
    protected int totalWidth;

    The total stretch of all elements handled so far.
/**
     * The total stretch of all elements handled so far.
     */
    protected int totalStretch;

    The total shrink of all elements handled so far.
/**
     * The total shrink of all elements handled so far.
     */
    protected int totalShrink;

    Best records.
/**
     * Best records.
     */
    protected BestRecords best;

    private boolean partOverflowRecoveryActivated = true;
    private KnuthNode lastRecovered;

    Create a new instance.
Params: align –  alignment of the paragraph/page. One of Constants.EN_START, Constants.EN_JUSTIFY, Constants.EN_CENTER, Constants.EN_END. For pages, Constants.EN_BEFORE and Constants.EN_AFTER are mapped to the corresponding inline properties, Constants.EN_START and Constants.EN_END.
alignLast – alignment of the paragraph's last line
first –  for the text-indent property (true if the first line of a paragraph should be indented)
partOverflowRecovery –  true if too long elements should be moved to the next line/part
maxFlagCount –  maximum allowed number of consecutive lines ending at a flagged penalty
                     item/**
     * Create a new instance.
     *
     * @param align     alignment of the paragraph/page. One of {@link Constants#EN_START},
     *                  {@link Constants#EN_JUSTIFY}, {@link Constants#EN_CENTER},
     *                  {@link Constants#EN_END}.
     *                  For pages, {@link Constants#EN_BEFORE} and {@link Constants#EN_AFTER}
     *                  are mapped to the corresponding inline properties,
     *                  {@link Constants#EN_START} and {@link Constants#EN_END}.
     * @param alignLast alignment of the paragraph's last line
     * @param first     for the text-indent property ({@code true} if the first line
     *                  of a paragraph should be indented)
     * @param partOverflowRecovery  {@code true} if too long elements should be moved to
     *                              the next line/part
     * @param maxFlagCount  maximum allowed number of consecutive lines ending at a flagged penalty
     *                      item
     */
    public BreakingAlgorithm(int align, int alignLast,
                             boolean first, boolean partOverflowRecovery,
                             int maxFlagCount) {
        this.alignment = align;
        this.alignmentLast = alignLast;
        this.indentFirstPart = first;
        this.partOverflowRecoveryActivated = partOverflowRecovery;
        this.best = new BestRecords();
        this.maxFlaggedPenaltiesCount = maxFlagCount;
    }


    Class recording all the informations of a feasible breaking point.
/**
     * Class recording all the informations of a feasible breaking point.
     */
    public class KnuthNode {
        index of the breakpoint represented by this node /** index of the breakpoint represented by this node */
        public final int position;

        number of the line ending at this breakpoint /** number of the line ending at this breakpoint */
        public final int line;

        fitness class of the line ending at this breakpoint. One of 0, 1, 2, 3. /** fitness class of the line ending at this breakpoint. One of 0, 1, 2, 3. */
        public final int fitness;

        accumulated width of the KnuthElements up to after this breakpoint. /** accumulated width of the KnuthElements up to after this breakpoint. */
        public final int totalWidth;

        accumulated stretchability of the KnuthElements up to after this breakpoint. /** accumulated stretchability of the KnuthElements up to after this breakpoint. */
        public final int totalStretch;

        accumulated shrinkability of the KnuthElements up to after this breakpoint. /** accumulated shrinkability of the KnuthElements up to after this breakpoint. */
        public final int totalShrink;

        adjustment ratio if the line ends at this breakpoint /** adjustment ratio if the line ends at this breakpoint */
        public final double adjustRatio;

        available stretch of the line ending at this breakpoint /** available stretch of the line ending at this breakpoint */
        public final int availableShrink;

        available shrink of the line ending at this breakpoint /** available shrink of the line ending at this breakpoint */
        public final int availableStretch;

        difference between target and actual line width /** difference between target and actual line width */
        public final int difference;

        minimum total demerits up to this breakpoint /** minimum total demerits up to this breakpoint */
        public double totalDemerits;

        best node for the preceding breakpoint /** best node for the preceding breakpoint */
        public KnuthNode previous;

        next possible node in the same line /** next possible node in the same line */
        public KnuthNode next;

        Holds the number of subsequent recovery attempty that are made to get content fit
into a line.
/**
         * Holds the number of subsequent recovery attempty that are made to get content fit
         * into a line.
         */
        public int fitRecoveryCounter;

        Construct node.
Params: position – an integer
line – an integer
fitness – an integer
totalWidth – an integer
totalStretch – an integer
totalShrink – an integer
adjustRatio – a real number
availableShrink – an integer
availableStretch – an integer
difference – an integer
totalDemerits – a real number
previous – a node/**
         * Construct node.
         * @param position an integer
         * @param line an integer
         * @param fitness an integer
         * @param totalWidth an integer
         * @param totalStretch an integer
         * @param totalShrink an integer
         * @param adjustRatio a real number
         * @param availableShrink an integer
         * @param availableStretch an integer
         * @param difference an integer
         * @param totalDemerits a real number
         * @param previous a node
         */
        public KnuthNode(int position, int line, int fitness,
                int totalWidth, int totalStretch, int totalShrink,
                double adjustRatio, int availableShrink, int availableStretch,
                int difference, double totalDemerits, KnuthNode previous) {
            this.position = position;
            this.line = line;
            this.fitness = fitness;
            this.totalWidth = totalWidth;
            this.totalStretch = totalStretch;
            this.totalShrink = totalShrink;
            this.adjustRatio = adjustRatio;
            this.availableShrink = availableShrink;
            this.availableStretch = availableStretch;
            this.difference = difference;
            this.totalDemerits = totalDemerits;
            this.previous = previous;
        }

        {@inheritDoc} /** {@inheritDoc} */
        public String toString() {
            return "<KnuthNode at " + position + " "
                    + totalWidth + "+" + totalStretch + "-" + totalShrink
                    + " line:" + line + " prev:" + (previous != null ? previous.position : -1)
                    + " dem:" + totalDemerits
                    + " fitness:" + FitnessClasses.NAMES[fitness] + ">";
        }
    }

    Class that stores, for each fitness class, the best active node that could start
a line of the corresponding fitness ending at the current element.
/** Class that stores, for each fitness class, the best active node that could start
     * a line of the corresponding fitness ending at the current element.
     */
    protected class BestRecords {
        private static final double INFINITE_DEMERITS = Double.POSITIVE_INFINITY;

        private final double[] bestDemerits = new double[4];
        private final KnuthNode[] bestNode = new KnuthNode[4];
        private final double[] bestAdjust = new double[4];
        private final int[] bestDifference = new int[4];
        private final int[] bestAvailableShrink = new int[4];
        private final int[] bestAvailableStretch = new int[4];
        Points to the fitness class which currently leads to the best demerits. /** Points to the fitness class which currently leads to the best demerits. */
        private int bestIndex = -1;

        default constructor /** default constructor */
        public BestRecords() {
            reset();
        }

        Registers the new best active node for the given fitness class.
Params: demerits – the total demerits of the new optimal set of breakpoints
node – the node starting the line ending at the current element
adjust – adjustment ratio of the current line
availableShrink – how much the current line can be shrinked
availableStretch – how much the current line can be stretched
difference – difference between the width of the considered line and the
width of the "real" line
fitness – fitness class of the current line/** Registers the new best active node for the given fitness class.
         * @param demerits the total demerits of the new optimal set of breakpoints
         * @param node the node starting the line ending at the current element
         * @param adjust adjustment ratio of the current line
         * @param availableShrink how much the current line can be shrinked
         * @param availableStretch how much the current line can be stretched
         * @param difference difference between the width of the considered line and the
         * width of the "real" line
         * @param fitness fitness class of the current line
         */
        public void addRecord(double demerits, KnuthNode node, double adjust,
                              int availableShrink, int availableStretch,
                              int difference, int fitness) {
            if (demerits > bestDemerits[fitness]) {
                log.error("New demerits value greater than the old one");
            }
            bestDemerits[fitness] = demerits;
            bestNode[fitness] = node;
            bestAdjust[fitness] = adjust;
            bestAvailableShrink[fitness] = availableShrink;
            bestAvailableStretch[fitness] = availableStretch;
            bestDifference[fitness] = difference;
            if (bestIndex == -1 || demerits < bestDemerits[bestIndex]) {
                bestIndex = fitness;
            }
        }

        Returns: true if has records (best index not -1)/** @return true if has records (best index not -1) */
        public boolean hasRecords() {
            return (bestIndex != -1);
        }

        Params: fitness – fitness class (0, 1, 2 or 3, i.e. "tight" to "very loose")
Returns: true if there is a set of feasible breakpoints registered for the
             given fitness./**
         * @param fitness fitness class (0, 1, 2 or 3, i.e. "tight" to "very loose")
         * @return true if there is a set of feasible breakpoints registered for the
         *              given fitness.
         */
        public boolean notInfiniteDemerits(int fitness) {
            return (bestDemerits[fitness] != INFINITE_DEMERITS);
        }

        Params: fitness – to use
Returns: best demerits/**
         * @param fitness to use
         * @return best demerits
         */
        public double getDemerits(int fitness) {
            return bestDemerits[fitness];
        }

        Params: fitness – to use
Returns: best node/**
         * @param fitness to use
         * @return best node
         */
        public KnuthNode getNode(int fitness) {
            return bestNode[fitness];
        }

        Params: fitness – to use
Returns: adjustment/**
         * @param fitness to use
         * @return adjustment
         */
        public double getAdjust(int fitness) {
            return bestAdjust[fitness];
        }

        Params: fitness – to use
Returns: available shrink/**
         * @param fitness to use
         * @return available shrink
         */
        public int getAvailableShrink(int fitness) {
            return bestAvailableShrink[fitness];
        }

        Params: fitness – to use
Returns: available stretch/**
         * @param fitness to use
         * @return available stretch
         */
        public int getAvailableStretch(int fitness) {
            return bestAvailableStretch[fitness];
        }

        Params: fitness – to use
Returns: difference/**
         * @param fitness to use
         * @return difference
         */
        public int getDifference(int fitness) {
            return bestDifference[fitness];
        }

        Returns: minimum demerits/** @return minimum demerits */
        public double getMinDemerits() {
            if (bestIndex != -1) {
                return getDemerits(bestIndex);
            } else {
                // anyway, this should never happen
                return INFINITE_DEMERITS;
            }
        }

        Reset when a new breakpoint is being considered. /** Reset when a new breakpoint is being considered. */
        public void reset() {
            for (int i = 0; i < 4; i++) {
                bestDemerits[i] = INFINITE_DEMERITS;
                // there is no need to reset the other arrays
            }
            bestIndex = -1;
        }
    }

    Returns: the number of times the algorithm should try to move overflowing content to the
next line/page./**
     * @return the number of times the algorithm should try to move overflowing content to the
     * next line/page.
     */
    protected int getMaxRecoveryAttempts() {
        return MAX_RECOVERY_ATTEMPTS;
    }

    Controls the behaviour of the algorithm in cases where the first element of a part
overflows a line/page.
Returns: true if the algorithm should try to send the element to the next line/page./**
     * Controls the behaviour of the algorithm in cases where the first element of a part
     * overflows a line/page.
     * @return true if the algorithm should try to send the element to the next line/page.
     */
    protected boolean isPartOverflowRecoveryActivated() {
        return this.partOverflowRecoveryActivated;
    }

    protected KnuthNode getLastTooLong() {
        return lastTooLong;
    }

    Empty method, hook for subclasses. Called before determining the optimal
breakpoints corresponding to a given active node.
Params: total – number of lines for the active node
demerits – total demerits of the paragraph for the active node/**
     * Empty method, hook for subclasses. Called before determining the optimal
     * breakpoints corresponding to a given active node.
     * @param total number of lines for the active node
     * @param demerits total demerits of the paragraph for the active node
     */
    public abstract void updateData1(int total, double demerits);

    Empty method, hook for subclasses. Called when determining the optimal breakpoints
for a given active node.
Params: bestActiveNode – a node in the chain of best active nodes, corresponding to
one of the optimal breakpoints
sequence – the corresponding paragraph
total – the number of lines into which the paragraph will be broken/**
     * Empty method, hook for subclasses. Called when determining the optimal breakpoints
     * for a given active node.
     * @param bestActiveNode a node in the chain of best active nodes, corresponding to
     * one of the optimal breakpoints
     * @param sequence the corresponding paragraph
     * @param total the number of lines into which the paragraph will be broken
     */
    public abstract void updateData2(KnuthNode bestActiveNode,
                                     KnuthSequence sequence,
                                     int total);

    Params: lineWidth – the line width/** @param lineWidth the line width */
    public void setConstantLineWidth(int lineWidth) {
        this.lineWidth = lineWidth;
    }

    Params: par –           the paragraph to break
threshold –     upper bound of the adjustment ratio
force –  true if a set of breakpoints must be found, even if there are no feasible ones
allowedBreaks – the type(s) of breaks allowed. One of ONLY_FORCED_BREAKS, NO_FLAGGED_PENALTIES or ALL_BREAKS.
See Also: findBreakingPoints(KnuthSequence, int, double, boolean, int)
Returns:  the number of effective breaks/**
     * @param par           the paragraph to break
     * @param threshold     upper bound of the adjustment ratio
     * @param force         {@code true} if a set of breakpoints must be found, even
     *                      if there are no feasible ones
     * @param allowedBreaks the type(s) of breaks allowed. One of {@link #ONLY_FORCED_BREAKS},
     *                      {@link #NO_FLAGGED_PENALTIES} or {@link #ALL_BREAKS}.
     *
     * @return  the number of effective breaks
     * @see #findBreakingPoints(KnuthSequence, int, double, boolean, int)
     */
    public int findBreakingPoints(KnuthSequence par,
                                  double threshold,
                                  boolean force,
                                  int allowedBreaks) {
        return findBreakingPoints(par, 0, threshold, force, allowedBreaks);
    }

    Finds an optimal set of breakpoints for the given paragraph.
Params: par –           the paragraph to break
startIndex –    index of the Knuth element at which the breaking must start
threshold –     upper bound of the adjustment ratio
force –  true if a set of breakpoints must be found, even if there are no feasible ones
allowedBreaks – the type(s) of breaks allowed. One of ONLY_FORCED_BREAKS, NO_FLAGGED_PENALTIES or ALL_BREAKS.
Returns:  the number of effective breaks/**
     * Finds an optimal set of breakpoints for the given paragraph.
     *
     * @param par           the paragraph to break
     * @param startIndex    index of the Knuth element at which the breaking must start
     * @param threshold     upper bound of the adjustment ratio
     * @param force         {@code true} if a set of breakpoints must be found, even
     *                      if there are no feasible ones
     * @param allowedBreaks the type(s) of breaks allowed. One of {@link #ONLY_FORCED_BREAKS},
     *                      {@link #NO_FLAGGED_PENALTIES} or {@link #ALL_BREAKS}.
     *
     * @return  the number of effective breaks
     */
    public int findBreakingPoints(KnuthSequence par, int startIndex,
                                  double threshold, boolean force,
                                  int allowedBreaks) {
        this.par = par;
        this.threshold = threshold;
        this.force = force;

        // initialize the algorithm
        initialize();

        // previous element in the paragraph is a KnuthBox?
        boolean previousIsBox = false;

        // index of the first KnuthBox in the sequence, in case of non-centered
        // alignment. For centered alignment, we need to take into account preceding
        // penalties+glues used for the filler spaces
        int previousPosition = startIndex;
        if (alignment != Constants.EN_CENTER) {
            int firstBoxIndex = par.getFirstBoxIndex(startIndex);
            previousPosition = (firstBoxIndex >= par.size()) ? startIndex : firstBoxIndex - 1;
        }
        previousPosition = (previousPosition < 0) ? 0 : previousPosition;

        // create an active node representing the starting point
        addNode(0, createNode(previousPosition, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, null));
        KnuthNode lastForced = getNode(0);

        if (log.isTraceEnabled()) {
            log.trace("Looping over " + (par.size() - startIndex) + " elements");
            log.trace(par);
        }

        // main loop
        for (int elementIndex = startIndex; elementIndex < par.size(); elementIndex++) {

            previousIsBox = handleElementAt(
                    elementIndex, previousIsBox, allowedBreaks).isBox();

            if (activeNodeCount == 0) {
                if (handlingFloat()) {
                    return handleFloat();
                }
                if (getIPDdifference() != 0) {
                    return handleIpdChange();
                }
                if (!force) {
                    log.debug("Could not find a set of breaking points " + threshold);
                    return 0;
                }

                // lastDeactivated was a "good" break, while lastTooShort and lastTooLong
                // were "bad" breaks since the beginning;
                // if it is not the node we just restarted from, lastDeactivated can
                // replace either lastTooShort or lastTooLong
                if (lastDeactivated != null
                        && lastDeactivated != lastForced) {
                    replaceLastDeactivated();
                }

                if (lastTooShort == null
                        || lastForced.position == lastTooShort.position) {
                    lastForced = recoverFromOverflow();
                } else {
                    lastForced = lastTooShort;
                    this.lastRecovered = null;
                }
                elementIndex = restartFrom(lastForced, elementIndex);
            }

        }

        finish();

        // there is at least one set of breaking points
        // select one or more active nodes, removing the others from the list
        int line = filterActiveNodes();

        // for each active node, create a set of breaking points
        for (int i = startLine; i < endLine; i++) {
            for (KnuthNode node = getNode(i); node != null; node = node.next) {
                updateData1(node.line, node.totalDemerits);
                calculateBreakPoints(node, par, node.line);
            }
        }

        activeLines = null;
        return line;
    }

    obtain ipd difference
Returns: an integer/**
     * obtain ipd difference
     * @return an integer
     */
    protected int getIPDdifference() {
        return 0;
    }

    handle ipd change
Returns: an integer/**
     * handle ipd change
     * @return an integer
     */
    protected int handleIpdChange() {
        throw new IllegalStateException();
    }

    Recover from a KnuthNode leading to a line that is too long. The default implementation creates a new node corresponding to a break point after the previous node that led to a line that was too short. 
Params: lastTooLong –   the node that leads to a "too long" line
Returns:  node corresponding to a breakpoint after the previous "too short" line/**
     * Recover from a {@link KnuthNode} leading to a line that is too long.
     * The default implementation creates a new node corresponding to a break
     * point after the previous node that led to a line that was too short.
     *
     * @param lastTooLong   the node that leads to a "too long" line
     * @return  node corresponding to a breakpoint after the previous "too short" line
     */
    protected KnuthNode recoverFromTooLong(KnuthNode lastTooLong) {
        if (log.isDebugEnabled()) {
            log.debug("Recovering from too long: " + lastTooLong);
        }

        // if lastTooLong would be the very first break in the blockList, and
        // the first element in the paragraph is not a penalty, add an auxiliary
        // penalty now to make it possible to create a genuine 'empty' node that
        // represents a break before the first box/glue
        if (lastTooLong.previous.previous == null) {
            ListElement el = (ListElement)this.par.get(0);
            if (!el.isPenalty()) {
                this.par.add(0, KnuthPenalty.DUMMY_ZERO_PENALTY);
            }
        }

        // content would overflow, insert empty line/page and try again
        return createNode(
                lastTooLong.previous.position, lastTooLong.previous.line + 1, 1,
                0, 0, 0,
                0, 0, 0,
                0, 0, lastTooLong.previous);
    }

    Initializes the algorithm's variables. /** Initializes the algorithm's variables. */
    protected void initialize() {
        this.totalWidth = 0;
        this.totalStretch = 0;
        this.totalShrink = 0;
        this.lastTooShort = null;
        this.lastTooLong = null;
        this.startLine = 0;
        this.endLine = 0;
        this.activeLines = new KnuthNode[20];
    }

    Creates a new active node for a feasible breakpoint at the given position. Only
called in forced mode.
Params: position – index of the element in the Knuth sequence
line – number of the line ending at the breakpoint
fitness – fitness class of the line ending at the breakpoint. One of 0, 1, 2, 3.
totalWidth – accumulated width of the KnuthElements up to after the breakpoint
totalStretch – accumulated stretchability of the KnuthElements up to after the
breakpoint
totalShrink – accumulated shrinkability of the KnuthElements up to after the
breakpoint
adjustRatio – adjustment ratio if the line ends at this breakpoint
availableShrink – available stretch of the line ending at this breakpoint
availableStretch – available shrink of the line ending at this breakpoint
difference – difference between target and actual line width
totalDemerits – minimum total demerits up to the breakpoint
previous – active node for the preceding breakpoint
Returns: a new node/**
     * Creates a new active node for a feasible breakpoint at the given position. Only
     * called in forced mode.
     *
     * @param position index of the element in the Knuth sequence
     * @param line number of the line ending at the breakpoint
     * @param fitness fitness class of the line ending at the breakpoint. One of 0, 1, 2, 3.
     * @param totalWidth accumulated width of the KnuthElements up to after the breakpoint
     * @param totalStretch accumulated stretchability of the KnuthElements up to after the
     * breakpoint
     * @param totalShrink accumulated shrinkability of the KnuthElements up to after the
     * breakpoint
     * @param adjustRatio adjustment ratio if the line ends at this breakpoint
     * @param availableShrink available stretch of the line ending at this breakpoint
     * @param availableStretch available shrink of the line ending at this breakpoint
     * @param difference difference between target and actual line width
     * @param totalDemerits minimum total demerits up to the breakpoint
     * @param previous active node for the preceding breakpoint
     * @return a new node
     */
    protected KnuthNode createNode(int position, int line, int fitness,
            int totalWidth, int totalStretch, int totalShrink,
            double adjustRatio, int availableShrink, int availableStretch,
            int difference, double totalDemerits, KnuthNode previous) {
        return new KnuthNode(position, line, fitness,
                             totalWidth, totalStretch, totalShrink,
                             adjustRatio, availableShrink, availableStretch,
                             difference, totalDemerits, previous);
    }

    Creates a new active node for a break from the best active node of the given
fitness class to the element at the given position.
Params: position – index of the element in the Knuth sequence
line – number of the line ending at the breakpoint
fitness – fitness class of the line ending at the breakpoint. One of 0, 1, 2, 3.
totalWidth – accumulated width of the KnuthElements up to after the breakpoint
totalStretch – accumulated stretchability of the KnuthElements up to after the
breakpoint
totalShrink – accumulated shrinkability of the KnuthElements up to after the
breakpoint
See Also: createNode(int, int, int, int, int, int, double, int, int, int, double, KnuthNode)
BestRecords
Returns: a new node/** Creates a new active node for a break from the best active node of the given
     * fitness class to the element at the given position.
     * @param position index of the element in the Knuth sequence
     * @param line number of the line ending at the breakpoint
     * @param fitness fitness class of the line ending at the breakpoint. One of 0, 1, 2, 3.
     * @param totalWidth accumulated width of the KnuthElements up to after the breakpoint
     * @param totalStretch accumulated stretchability of the KnuthElements up to after the
     * breakpoint
     * @param totalShrink accumulated shrinkability of the KnuthElements up to after the
     * breakpoint
     * @return a new node
     * @see #createNode(int, int, int, int, int, int, double, int, int, int, double,
     * org.apache.fop.layoutmgr.BreakingAlgorithm.KnuthNode)
     * @see BreakingAlgorithm.BestRecords
     */
    protected KnuthNode createNode(int position, int line, int fitness,
                                   int totalWidth, int totalStretch, int totalShrink) {
        return new KnuthNode(position, line, fitness,
                             totalWidth, totalStretch, totalShrink, best.getAdjust(fitness),
                             best.getAvailableShrink(fitness), best.getAvailableStretch(fitness),
                             best.getDifference(fitness), best.getDemerits(fitness),
                             best.getNode(fitness));
    }

    Return the last node that yielded a too short line.
Returns:  the node corresponding to the last too short line/**
     * Return the last node that yielded a too short line.
     * @return  the node corresponding to the last too short line
     */
    protected final KnuthNode getLastTooShort() {
        return this.lastTooShort;
    }

    Generic handler for a KnuthElement at the given position, taking into account whether the preceding element was a box, and which type(s) of breaks are allowed. Non-overridable. This method simply serves to route the call to one of the more specific handlers (handleBox(KnuthBox), handleGlueAt(KnuthGlue, int, boolean, int) or handlePenaltyAt(KnuthPenalty, int, int). The specialized handlers can be overridden by subclasses to add to or modify the default behavior for the different types of elements. 
Params: position –      the position index of the element in the paragraph
previousIsBox – true if the previous element is a box
allowedBreaks – the type(s) of breaks allowed; should be one of ALL_BREAKS, NO_FLAGGED_PENALTIES or ONLY_FORCED_BREAKS
Returns:  the handled element/**
     * Generic handler for a {@link KnuthElement} at the given {@code position},
     * taking into account whether the preceding element was a box, and which
     * type(s) of breaks are allowed.
     * Non-overridable. This method simply serves to route the call to one of the
     * more specific handlers ({@link #handleBox(KnuthBox)},
     * {@link #handleGlueAt(KnuthGlue,int,boolean,int)} or
     * {@link #handlePenaltyAt(KnuthPenalty,int,int)}. The specialized handlers
     * can be overridden by subclasses to add to or modify the default behavior
     * for the different types of elements.
     *
     * @param position      the position index of the element in the paragraph
     * @param previousIsBox {@code true} if the previous element is a box
     * @param allowedBreaks the type(s) of breaks allowed; should be one
     *                      of {@link #ALL_BREAKS}, {@link #NO_FLAGGED_PENALTIES}
     *                      or {@link #ONLY_FORCED_BREAKS}
     * @return  the handled element
     */
    protected final KnuthElement handleElementAt(int position,
                                                 boolean previousIsBox,
                                                 int allowedBreaks) {
        KnuthElement element = getElement(position);
        if (element.isBox()) {
            handleBox((KnuthBox) element);
        } else if (element.isGlue()) {
            handleGlueAt((KnuthGlue) element, position, previousIsBox, allowedBreaks);
        } else if (element.isPenalty()) {
            handlePenaltyAt((KnuthPenalty) element, position, allowedBreaks);
        } else {
            throw new IllegalArgumentException(
                    "Unknown KnuthElement type: expecting KnuthBox, KnuthGlue or KnuthPenalty");
        }
        return element;
    }

    Handle a KnuthBox. 
Note: default implementation just adds the box's width to the total content width. Subclasses that do not keep track of this themselves, but override this method, should remember to call super.handleBox(box) to avoid unwanted side-effects.
Params: box –  the KnuthBox to handle/**
     * Handle a {@link KnuthBox}.
     * <br><em>Note: default implementation just adds the box's width
     * to the total content width. Subclasses that do not keep track
     * of this themselves, but override this method, should remember
     * to call {@code super.handleBox(box)} to avoid unwanted side-effects.</em>
     *
     * @param box   the {@link KnuthBox} to handle
     */
    protected void handleBox(KnuthBox box) {
        // a KnuthBox object is not a legal line break,
        // just add the width to the total
        totalWidth += box.getWidth();
    }

    Handle a KnuthGlue at the given position, taking into account the additional parameters. 
Params: glue –  the KnuthGlue to handle
position –   the position of the glue in the list
previousIsBox – true if the preceding element is a box
allowedBreaks – the type of breaks that are allowed/**
     * Handle a {@link KnuthGlue} at the given position,
     * taking into account the additional parameters.
     *
     * @param glue   the {@link KnuthGlue} to handle
     * @param position   the position of the glue in the list
     * @param previousIsBox {@code true} if the preceding element is a box
     * @param allowedBreaks the type of breaks that are allowed
     */
    protected void handleGlueAt(KnuthGlue glue, int position,
                                boolean previousIsBox, int allowedBreaks) {
        // a KnuthGlue object is a legal line break
        // only if the previous object is a KnuthBox
        // consider these glues according to the value of allowedBreaks
        if (previousIsBox
            && !(allowedBreaks == ONLY_FORCED_BREAKS)) {
            considerLegalBreak(glue, position);
        }
        totalWidth += glue.getWidth();
        totalStretch += glue.getStretch();
        totalShrink += glue.getShrink();
    }

    Handle a KnuthPenalty at the given position, taking into account the type of breaks allowed. 
Params: penalty –  the KnuthPenalty to handle
position –  the position of the penalty in the list
allowedBreaks – the type of breaks that are allowed/**
     * Handle a {@link KnuthPenalty} at the given position,
     * taking into account the type of breaks allowed.
     *
     * @param penalty   the {@link KnuthPenalty} to handle
     * @param position  the position of the penalty in the list
     * @param allowedBreaks the type of breaks that are allowed
     */
    protected void handlePenaltyAt(KnuthPenalty penalty, int position,
                                   int allowedBreaks) {
        // a KnuthPenalty is a legal line break
        // only if its penalty is not infinite;
        // consider all penalties, non-flagged penalties or non-forcing penalties
        // according to the value of allowedBreaks
        if (((penalty.getPenalty() < KnuthElement.INFINITE)
                && (!(allowedBreaks == NO_FLAGGED_PENALTIES) || !penalty.isPenaltyFlagged())
                && (!(allowedBreaks == ONLY_FORCED_BREAKS)
                        || penalty.isForcedBreak()))) {
            considerLegalBreak(penalty, position);
        }
    }

    Replace the last too-long or too-short node by the last deactivated
node, if applicable.
/**
     * Replace the last too-long or too-short node by the last deactivated
     * node, if applicable.
     */
    protected final void replaceLastDeactivated() {
        if (lastDeactivated.adjustRatio > 0) {
            //last deactivated was too short
            lastTooShort = lastDeactivated;
        } else {
            //last deactivated was too long or exactly the right width
            lastTooLong = lastDeactivated;
        }
    }

    Recover from an overflow condition.
Returns:  the new lastForced node/**
     * Recover from an overflow condition.
     *
     * @return  the new {@code lastForced} node
     */
    protected KnuthNode recoverFromOverflow() {
        KnuthNode lastForced;
        if (isPartOverflowRecoveryActivated()) {
            if (lastRecovered == null) {
                lastRecovered = lastTooLong;
                if (log.isDebugEnabled()) {
                    log.debug("Recovery point: " + lastRecovered);
                }
            }
            KnuthNode node = recoverFromTooLong(lastTooLong);
            lastForced = node;
            node.fitRecoveryCounter = lastTooLong.previous.fitRecoveryCounter + 1;
            if (log.isDebugEnabled()) {
                log.debug("first part doesn't fit into line, recovering: "
                        + node.fitRecoveryCounter);
            }
            if (node.fitRecoveryCounter > getMaxRecoveryAttempts()) {
                while (lastForced.fitRecoveryCounter > 0
                        && lastForced.previous != null) {
                    lastForced = lastForced.previous;
                    lastDeactivated = lastForced.previous;
                }
                lastForced = lastRecovered;
                lastRecovered = null;
                startLine = lastForced.line;
                endLine = lastForced.line;
                log.debug("rolled back...");
            }
        } else {
            lastForced = lastTooLong;
        }
        return lastForced;
    }

    Restart from the given node at the given index.
Params: restartingNode –  the KnuthNode to restart from
currentIndex –      the current position index
Returns:  the index of the restart point/**
     * Restart from the given node at the given index.
     *
     * @param restartingNode    the {@link KnuthNode} to restart from
     * @param currentIndex      the current position index
     * @return  the index of the restart point
     */
    protected int restartFrom(KnuthNode restartingNode, int currentIndex) {
        if (log.isDebugEnabled()) {
            log.debug("Restarting at node " + restartingNode);
        }

        restartingNode.totalDemerits = 0;
        addNode(restartingNode.line, restartingNode);
        startLine = restartingNode.line;
        endLine = startLine + 1;
        totalWidth = restartingNode.totalWidth;
        totalStretch = restartingNode.totalStretch;
        totalShrink = restartingNode.totalShrink;
        lastTooShort = null;
        lastTooLong = null;
        // the width, stretch and shrink already include the width,
        // stretch and shrink of the suppressed glues;
        // advance in the sequence in order to avoid taking into account
        // these elements twice
        int restartingIndex = restartingNode.position;
        while (restartingIndex + 1 < par.size()
               && !(getElement(restartingIndex + 1).isBox())) {
            restartingIndex++;
        }
        return restartingIndex;
    }

    Determines if the given breakpoint is a feasible breakpoint. That is, if a decent
line may be built between one of the currently active nodes and this breakpoint.
Params: element – the paragraph's element to consider
elementIdx – the element's index inside the paragraph/**
     * Determines if the given breakpoint is a feasible breakpoint. That is, if a decent
     * line may be built between one of the currently active nodes and this breakpoint.
     * @param element the paragraph's element to consider
     * @param elementIdx the element's index inside the paragraph
     */
    protected void considerLegalBreak(KnuthElement element, int elementIdx) {

        if (log.isTraceEnabled()) {
            log.trace("considerLegalBreak() at " + elementIdx
                    + " (" + totalWidth + "+" + totalStretch + "-" + totalShrink
                    + "), parts/lines: " + startLine + "-" + endLine);
            log.trace("\tCurrent active node list: " + activeNodeCount + " " + this.toString("\t"));
        }

        lastDeactivated = null;
        lastTooLong = null;
        for (int line = startLine; line < endLine; line++) {
            for (KnuthNode node = getNode(line); node != null; node = node.next) {
                if (node.position == elementIdx) {
                    continue;
                }
                int difference = computeDifference(node, element, elementIdx);
                if (!elementCanEndLine(element, endLine, difference)) {
                    log.trace("Skipping legal break");
                    break;
                }

                double r = computeAdjustmentRatio(node, difference);
                int availableShrink = totalShrink - node.totalShrink;
                int availableStretch = totalStretch - node.totalStretch;

                if (log.isTraceEnabled()) {
                    log.trace("\tr=" + r + " difference=" + difference);
                    log.trace("\tline=" + line);
                }

                if (element.isForcedBreak() && handlingFloat()) {
                    disableFloatHandling(); // so that we do not create a float edge position later
                }
                // The line would be too long.
                if (r < -1 || element.isForcedBreak() || handlingFloat()) {
                    deactivateNode(node, line);
                }

                int fitnessClass = FitnessClasses.computeFitness(r);
                double demerits = computeDemerits(node, element, fitnessClass, r);
                // The line is within the available shrink and the threshold.
                if (r >= -1 && r <= threshold) {
                    activateNode(node, difference, r,
                            demerits, fitnessClass, availableShrink, availableStretch);
                }

                // The line is way too short/long, but we are in forcing mode, so a node is
                // calculated and stored in lastValidNode.
                if (force && (r <= -1 || r > threshold)) {
                    forceNode(node, line, elementIdx, difference, r,
                            demerits, fitnessClass, availableShrink, availableStretch);
                }
            }
            addBreaks(line, elementIdx);
        }
    }

    Check if the given KnuthElement can end the line with the given number. 
Params: element –   the element
line –      the line number
difference – an integer
Returns:  true if the element can end the line/**
     * Check if the given {@link KnuthElement} can end the line with the given
     * number.
     * @param element   the element
     * @param line      the line number
     * @param difference an integer
     * @return  {@code true} if the element can end the line
     */
    protected boolean elementCanEndLine(KnuthElement element, int line, int difference) {
        return (!element.isPenalty()
                || element.getPenalty() < KnuthElement.INFINITE);
    }

    Force the given KnuthNode, and register it. 
Params: node –  the node
line –  the line number
elementIdx –    the position index of the element
difference –    the difference between content-length and available width
r –     the adjustment ratio
demerits –  demerits produced by the node
fitnessClass –  the fitness class
availableShrink –   the available amount of shrink
availableStretch –  tha available amount of stretch/**
     * Force the given {@link KnuthNode}, and register it.
     *
     * @param node  the node
     * @param line  the line number
     * @param elementIdx    the position index of the element
     * @param difference    the difference between content-length and available width
     * @param r     the adjustment ratio
     * @param demerits  demerits produced by the node
     * @param fitnessClass  the fitness class
     * @param availableShrink   the available amount of shrink
     * @param availableStretch  tha available amount of stretch
     */
    protected void forceNode(KnuthNode node,
                             int line,
                             int elementIdx,
                             int difference,
                             double r,
                             double demerits,
                             int fitnessClass,
                             int availableShrink,
                             int availableStretch) {

        int newWidth = totalWidth;
        int newStretch = totalStretch;
        int newShrink = totalShrink;

        // add the width, stretch and shrink of glue elements after
        // the break
        // this does not affect the dimension of the line / page, only
        // the values stored in the node; these would be as if the break
        // was just before the next box element, thus ignoring glues and
        // penalties between the "real" break and the following box
        for (int i = elementIdx; i < par.size(); i++) {
            KnuthElement tempElement = getElement(i);
            if (tempElement.isBox()) {
                break;
            } else if (tempElement.isGlue()) {
                newWidth += tempElement.getWidth();
                newStretch += tempElement.getStretch();
                newShrink += tempElement.getShrink();
            } else if (tempElement.isForcedBreak() && i != elementIdx) {
                break;
            }
        }

        createForcedNodes(node, line, elementIdx, difference, r, demerits, fitnessClass, availableShrink,
                availableStretch, newWidth, newStretch, newShrink);
    }

    protected void createForcedNodes(KnuthNode node, int line, int elementIdx, int difference, double r,
            double demerits, int fitnessClass, int availableShrink, int availableStretch, int newWidth,
            int newStretch, int newShrink) {
        if (r <= -1) {
            log.debug("Considering tooLong, demerits=" + demerits);
            if (lastTooLong == null || demerits < lastTooLong.totalDemerits) {
                lastTooLong = createNode(elementIdx, line + 1, fitnessClass,
                        newWidth, newStretch, newShrink,
                        r, availableShrink, availableStretch,
                        difference, demerits, node);
                if (log.isTraceEnabled()) {
                    log.trace("Picking tooLong " + lastTooLong);
                }
            }
        } else {
            if (lastTooShort == null || demerits <= lastTooShort.totalDemerits) {
                if (considerTooShort) {
                    // consider possibilities which are too short
                    best.addRecord(demerits, node, r, availableShrink, availableStretch, difference,
                            fitnessClass);
                }
                lastTooShort = createNode(elementIdx, line + 1, fitnessClass,
                        newWidth, newStretch, newShrink,
                        r, availableShrink, availableStretch,
                        difference, demerits, node);
                if (log.isTraceEnabled()) {
                    log.trace("Picking tooShort " + lastTooShort);
                }
            }
        }
    }

    Activate the given node. Will result in the given KnuthNode being registered as a feasible breakpoint, if the demerits are better than that of the best node registered for the given fitnessClass. 
Params: node –  the node
difference –    the difference between content-length and available width
r –     the adjustment ratio
demerits –  demerits produced by the node
fitnessClass –  the fitness class
availableShrink –   the available amount of shrink
availableStretch –  the available amount of stretch/**
     * Activate the given node. Will result in the given {@link KnuthNode}
     * being registered as a feasible breakpoint, if the {@code demerits} are better
     * than that of the best node registered for the given {@code fitnessClass}.
     *
     * @param node  the node
     * @param difference    the difference between content-length and available width
     * @param r     the adjustment ratio
     * @param demerits  demerits produced by the node
     * @param fitnessClass  the fitness class
     * @param availableShrink   the available amount of shrink
     * @param availableStretch  the available amount of stretch
     */
    protected void activateNode(KnuthNode node,
                                int difference,
                                double r,
                                double demerits,
                                int fitnessClass,
                                int availableShrink,
                                int availableStretch) {

        if (log.isTraceEnabled()) {
            log.trace("\tDemerits=" + demerits);
            log.trace("\tFitness class=" + FitnessClasses.NAMES[fitnessClass]);
        }

        if (demerits < best.getDemerits(fitnessClass)) {
            // updates best demerits data
            best.addRecord(demerits, node, r, availableShrink, availableStretch,
                           difference, fitnessClass);
            lastTooShort = null;
        }
    }

    Deactivate the given node
Params: node –  the node
line –  the line number/**
     * Deactivate the given node
     *
     * @param node  the node
     * @param line  the line number
     */
    protected void deactivateNode(KnuthNode node, int line) {
        // Deactivate node...
        if (log.isTraceEnabled()) {
            log.trace("Removing " + node);
        }
        removeNode(line, node);
        // ... and remember it, if it was a good candidate
        lastDeactivated = compareNodes(lastDeactivated, node);
    }

    Adds new active nodes for breaks at the given element.
Params: line – number of the previous line; this element will end line number (line+1)
elementIdx – the element's index/**
     * Adds new active nodes for breaks at the given element.
     * @param line number of the previous line; this element will end line number (line+1)
     * @param elementIdx the element's index
     */
    private void addBreaks(int line, int elementIdx) {
        if (!best.hasRecords()) {
            return;
        }

        int newWidth = totalWidth;
        int newStretch = totalStretch;
        int newShrink = totalShrink;

        // add the width, stretch and shrink of glue elements after
        // the break
        // this does not affect the dimension of the line / page, only
        // the values stored in the node; these would be as if the break
        // was just before the next box element, thus ignoring glues and
        // penalties between the "real" break and the following box
        for (int i = elementIdx; i < par.size(); i++) {
            KnuthElement tempElement = getElement(i);
            if (tempElement.isBox()) {
                break;
            } else if (tempElement.isGlue()) {
                newWidth += tempElement.getWidth();
                newStretch += tempElement.getStretch();
                newShrink += tempElement.getShrink();
            } else if (tempElement.isForcedBreak() && i != elementIdx) {
                break;
            }
        }

        // add nodes to the active nodes list
        double minimumDemerits = best.getMinDemerits() + incompatibleFitnessDemerit;
        for (int i = 0; i <= 3; i++) {
            if (best.notInfiniteDemerits(i) && best.getDemerits(i) <= minimumDemerits) {
                // the nodes in activeList must be ordered
                // by line number and position;
                if (log.isTraceEnabled()) {
                    log.trace("\tInsert new break in list of " + activeNodeCount
                            + " from fitness class " + FitnessClasses.NAMES[i]);
                }
                KnuthNode newNode = createNode(elementIdx, line + 1, i,
                                               newWidth, newStretch, newShrink);
                addNode(line + 1, newNode);
            }
        }
        best.reset();
    }

    Return the difference between the natural width of a line that would be made
between the given active node and the given element, and the available width of the
real line.
Params: activeNode –    node for the previous breakpoint
element –       currently considered breakpoint
elementIndex –  index of the element that is considered as a breakpoint
Returns: The difference in width. Positive numbers mean extra space in the line,
negative number that the line overflows./**
     * Return the difference between the natural width of a line that would be made
     * between the given active node and the given element, and the available width of the
     * real line.
     * @param activeNode    node for the previous breakpoint
     * @param element       currently considered breakpoint
     * @param elementIndex  index of the element that is considered as a breakpoint
     * @return The difference in width. Positive numbers mean extra space in the line,
     * negative number that the line overflows.
     */
    protected int computeDifference(KnuthNode activeNode, KnuthElement element,
                                    int elementIndex) {
        // compute the adjustment ratio
        int actualWidth = totalWidth - activeNode.totalWidth;
        if (element.isPenalty()) {
            actualWidth += element.getWidth();
        }
        return getLineWidth() - actualWidth;
    }

    Return the adjustment ratio needed to make up for the difference. A ratio of

   0 means that the break has the exact right width
   >= -1 && < 0  means that the break is wider than the line,
       but within the minimim values of the glues.
   >0 && < 1 means that the break is smaller than the line width,
       but within the maximum values of the glues.
   > 1 means that the break is too small to make up for the glues.

Params: activeNode –    the currently active node
difference –    the difference between content-length and available width
Returns: The adjustment ratio./**
     * Return the adjustment ratio needed to make up for the difference. A ratio of
     * <ul>
     *    <li>0 means that the break has the exact right width</li>
     *    <li>&gt;= -1 &amp;&amp; &lt; 0  means that the break is wider than the line,
     *        but within the minimim values of the glues.</li>
     *    <li>&gt;0 &amp;&amp; &lt; 1 means that the break is smaller than the line width,
     *        but within the maximum values of the glues.</li>
     *    <li>&gt; 1 means that the break is too small to make up for the glues.</li>
     * </ul>
     * @param activeNode    the currently active node
     * @param difference    the difference between content-length and available width
     * @return The adjustment ratio.
     */
    protected double computeAdjustmentRatio(KnuthNode activeNode, int difference) {
        // compute the adjustment ratio
        if (difference > 0) {
            int maxAdjustment = totalStretch - activeNode.totalStretch;
            if (maxAdjustment > 0) {
                return (double) difference / maxAdjustment;
            } else {
                return INFINITE_RATIO;
            }
        } else if (difference < 0) {
            int maxAdjustment = totalShrink - activeNode.totalShrink;
            if (maxAdjustment > 0) {
                return (double) difference / maxAdjustment;
            } else {
                return -INFINITE_RATIO;
            }
        } else {
            return 0;
        }
    }

    Computes the demerits of the current breaking (that is, up to the given element),
if the next-to-last chosen breakpoint is the given active node. This adds to the
total demerits of the given active node, the demerits of a line starting at this
node and ending at the given element.
Params: activeNode – considered preceding line break
element – considered current line break
fitnessClass – fitness of the current line
r – adjustment ratio for the current line
Returns: the demerit of the current line/**
     * Computes the demerits of the current breaking (that is, up to the given element),
     * if the next-to-last chosen breakpoint is the given active node. This adds to the
     * total demerits of the given active node, the demerits of a line starting at this
     * node and ending at the given element.
     * @param activeNode considered preceding line break
     * @param element considered current line break
     * @param fitnessClass fitness of the current line
     * @param r adjustment ratio for the current line
     * @return the demerit of the current line
     */
    protected double computeDemerits(KnuthNode activeNode, KnuthElement element,
                                  int fitnessClass, double r) {
        double demerits = 0;
        // compute demerits
        double f = Math.abs(r);
        f = 1 + 100 * f * f * f;
        if (element.isPenalty()) {
            double penalty = element.getPenalty();
            if (penalty >= 0) {
                f += penalty;
                demerits = f * f;
            } else if (!element.isForcedBreak()) {
                demerits = f * f - penalty * penalty;
            } else {
                demerits = f * f;
            }
        } else {
            demerits = f * f;
        }

        if (element.isPenalty() && ((KnuthPenalty) element).isPenaltyFlagged()
            && getElement(activeNode.position).isPenalty()
            && ((KnuthPenalty) getElement(activeNode.position)).isPenaltyFlagged()) {
            // add demerit for consecutive breaks at flagged penalties
            demerits += repeatedFlaggedDemerit;
            // there are at least two consecutive lines ending with a flagged penalty;
            // check if the previous line end with a flagged penalty too,
            // and if this situation is allowed
            int flaggedPenaltiesCount = 2;
            for (KnuthNode prevNode = activeNode.previous;
                 prevNode != null && flaggedPenaltiesCount <= maxFlaggedPenaltiesCount;
                 prevNode = prevNode.previous) {
                KnuthElement prevElement = getElement(prevNode.position);
                if (prevElement.isPenalty()
                    && ((KnuthPenalty) prevElement).isPenaltyFlagged()) {
                    // the previous line ends with a flagged penalty too
                    flaggedPenaltiesCount++;
                } else {
                    // the previous line does not end with a flagged penalty,
                    // exit the loop
                    break;
                }
            }
            if (maxFlaggedPenaltiesCount >= 1
                && flaggedPenaltiesCount > maxFlaggedPenaltiesCount) {
                // add infinite demerits, so this break will not be chosen
                // unless there isn't any alternative break
                demerits += BestRecords.INFINITE_DEMERITS;
            }
        }
        if (Math.abs(fitnessClass - activeNode.fitness) > 1) {
            // add demerit for consecutive breaks
            // with very different fitness classes
            demerits += incompatibleFitnessDemerit;
        }
        demerits += activeNode.totalDemerits;
        return demerits;
    }

    Hook for subclasses to trigger special behavior after ending the main loop in findBreakingPoints(KnuthSequence, int, double, boolean, int) /**
     * Hook for subclasses to trigger special behavior after ending the
     * main loop in {@link #findBreakingPoints(KnuthSequence,int,double,boolean,int)}
     */
    protected void finish() {
        if (log.isTraceEnabled()) {
            log.trace("Main loop completed " + activeNodeCount);
            log.trace("Active nodes=" + toString(""));
        }
    }

    Return the element at index idx in the paragraph.
Params: idx – index of the element.
Returns: the element at index idx in the paragraph./**
     * Return the element at index idx in the paragraph.
     * @param idx index of the element.
     * @return the element at index idx in the paragraph.
     */
    protected KnuthElement getElement(int idx) {
        return (KnuthElement) par.get(idx);
    }

    Compare two KnuthNodes and return the node with the least demerit.
Params: node1 – The first knuth node.
node2 – The other knuth node.
Returns: the node with the least demerit./**
     * Compare two KnuthNodes and return the node with the least demerit.
     * @param node1 The first knuth node.
     * @param node2 The other knuth node.
     * @return the node with the least demerit.
     */
    protected KnuthNode compareNodes(KnuthNode node1, KnuthNode node2) {
        if (node1 == null || node2.position > node1.position) {
            return node2;
        }
        if (node2.position == node1.position) {
            if (node2.totalDemerits < node1.totalDemerits) {
                return node2;
            }
        }
        return node1;
    }

    Add a node at the end of the given line's existing active nodes.
If this is the first node in the line, adjust endLine accordingly.
Params: line – number of the line ending at the node's corresponding breakpoint
node – the active node to add/**
     * Add a node at the end of the given line's existing active nodes.
     * If this is the first node in the line, adjust endLine accordingly.
     * @param line number of the line ending at the node's corresponding breakpoint
     * @param node the active node to add
     */
    protected void addNode(int line, KnuthNode node) {
        int headIdx = line * 2;
        if (headIdx >= activeLines.length) {
            KnuthNode[] oldList = activeLines;
            activeLines = new KnuthNode[headIdx + headIdx];
            System.arraycopy(oldList, 0, activeLines, 0, oldList.length);
        }
        node.next = null;
        if (activeLines[headIdx + 1] != null) {
            activeLines[headIdx + 1].next = node;
        } else {
            activeLines[headIdx] = node;
            endLine = line + 1;
        }
        activeLines[headIdx + 1] = node;
        activeNodeCount++;
    }

    Remove the given active node registered for the given line. If there are no more active nodes
for this line, adjust the startLine accordingly.
Params: line – number of the line ending at the node's corresponding breakpoint
node – the node to deactivate/**
     * Remove the given active node registered for the given line. If there are no more active nodes
     * for this line, adjust the startLine accordingly.
     * @param line number of the line ending at the node's corresponding breakpoint
     * @param node the node to deactivate
     */
    protected void removeNode(int line, KnuthNode node) {
        int headIdx = line * 2;
        KnuthNode n = getNode(line);
        if (n != node) {
            // nodes could be rightly deactivated in a different order
            KnuthNode prevNode = null;
            while (n != node) {
                prevNode = n;
                n = n.next;
            }
            prevNode.next = n.next;
            if (prevNode.next == null) {
                activeLines[headIdx + 1] = prevNode;
            }
        } else {
            activeLines[headIdx] = node.next;
            if (node.next == null) {
                activeLines[headIdx + 1] = null;
            }
            while (startLine < endLine && getNode(startLine) == null) {
                startLine++;
            }
        }
        activeNodeCount--;
    }

    Returns the first active node for the given line.
Params: line – the line/part number
Returns: the requested active node/**
     * Returns the first active node for the given line.
     * @param line the line/part number
     * @return the requested active node
     */
    protected KnuthNode getNode(int line) {
        return activeLines[line * 2];
    }

    Returns the line/part width of a given line/part.
Params: line – the line/part number
Returns: the width/length in millipoints/**
     * Returns the line/part width of a given line/part.
     * @param line the line/part number
     * @return the width/length in millipoints
     */
    protected int getLineWidth(int line) {
        assert lineWidth >= 0;
        return this.lineWidth;
    }

    Returns: the constant line/part width or -1 if there is no such value/** @return the constant line/part width or -1 if there is no such value */
    protected int getLineWidth() {
        return this.lineWidth;
    }

    Creates a string representation of the active nodes. Used for debugging.
Params: prepend – a string to prepend on each entry
Returns: the requested string/**
     * Creates a string representation of the active nodes. Used for debugging.
     * @param prepend a string to prepend on each entry
     * @return the requested string
     */
    public String toString(String prepend) {
        StringBuffer sb = new StringBuffer();
        sb.append("[\n");
        for (int i = startLine; i < endLine; i++) {
            for (KnuthNode node = getNode(i); node != null; node = node.next) {
                sb.append(prepend).append('\t').append(node).append(",\n");
            }
        }
        sb.append(prepend).append("]");
        return sb.toString();
    }

    Filter active nodes.
Returns: an integer/**
     * Filter active nodes.
     * @return an integer
     */
    protected abstract int filterActiveNodes();

    Determines the set of optimal breakpoints corresponding to the given active node.
Params: node – the active node
par – the corresponding paragraph
total – the number of lines into which the paragraph will be broken/**
     * Determines the set of optimal breakpoints corresponding to the given active node.
     * @param node the active node
     * @param par the corresponding paragraph
     * @param total the number of lines into which the paragraph will be broken
     */
    protected void calculateBreakPoints(KnuthNode node, KnuthSequence par,
                                      int total) {
        KnuthNode bestActiveNode = node;
        // use bestActiveNode to determine the optimum breakpoints
        for (int i = node.line; i > 0; i--) {
            updateData2(bestActiveNode, par, total);
            bestActiveNode = bestActiveNode.previous;
        }
    }

    Returns: the alignment for normal lines/parts/** @return the alignment for normal lines/parts */
    public int getAlignment() {
        return this.alignment;
    }

    Returns: the alignment for the last line/part/** @return the alignment for the last line/part */
    public int getAlignmentLast() {
        return this.alignmentLast;
    }

    protected boolean handlingFloat() {
        return false;
    }

    protected int handleFloat() {
        throw new IllegalStateException();
    }

    protected void disableFloatHandling() {
        throw new IllegalStateException();
    }
}
Params:	adjustRatio – the adjustment ratio
Returns:	the fitness class
Params:	fitness – fitness class (0, 1, 2 or 3, i.e. "tight" to "very loose")
Returns:	true if there is a set of feasible breakpoints registered for the given fitness.
Params:	par – the paragraph to break threshold – upper bound of the adjustment ratio force – `true` if a set of breakpoints must be found, even if there are no feasible ones allowedBreaks – the type(s) of breaks allowed. One of `ONLY_FORCED_BREAKS`, `NO_FLAGGED_PENALTIES` or `ALL_BREAKS`.
See Also:	findBreakingPoints(KnuthSequence, int, double, boolean, int)
Returns:	the number of effective breaks
Params:	par – the paragraph to break startIndex – index of the Knuth element at which the breaking must start threshold – upper bound of the adjustment ratio force – `true` if a set of breakpoints must be found, even if there are no feasible ones allowedBreaks – the type(s) of breaks allowed. One of `ONLY_FORCED_BREAKS`, `NO_FLAGGED_PENALTIES` or `ALL_BREAKS`.
Returns:	the number of effective breaks
Params:	lastTooLong – the node that leads to a "too long" line
Returns:	node corresponding to a breakpoint after the previous "too short" line
Params:	position – index of the element in the Knuth sequence line – number of the line ending at the breakpoint fitness – fitness class of the line ending at the breakpoint. One of 0, 1, 2, 3. totalWidth – accumulated width of the KnuthElements up to after the breakpoint totalStretch – accumulated stretchability of the KnuthElements up to after the breakpoint totalShrink – accumulated shrinkability of the KnuthElements up to after the breakpoint
See Also:	createNode(int, int, int, int, int, int, double, int, int, int, double, KnuthNode) BestRecords
Returns:	a new node
Params:	position – the position index of the element in the paragraph previousIsBox – `true` if the previous element is a box allowedBreaks – the type(s) of breaks allowed; should be one of `ALL_BREAKS`, `NO_FLAGGED_PENALTIES` or `ONLY_FORCED_BREAKS`
Returns:	the handled element
Params:	restartingNode – the `KnuthNode` to restart from currentIndex – the current position index
Returns:	the index of the restart point
Params:	element – the element line – the line number difference – an integer
Returns:	`true` if the element can end the line
Params:	activeNode – node for the previous breakpoint element – currently considered breakpoint elementIndex – index of the element that is considered as a breakpoint
Returns:	The difference in width. Positive numbers mean extra space in the line, negative number that the line overflows.
Params:	activeNode – the currently active node difference – the difference between content-length and available width
Returns:	The adjustment ratio.
Params:	activeNode – considered preceding line break element – considered current line break fitnessClass – fitness of the current line r – adjustment ratio for the current line
Returns:	the demerit of the current line
Params:	idx – index of the element.
Returns:	the element at index idx in the paragraph.
Params:	node1 – The first knuth node. node2 – The other knuth node.
Returns:	the node with the least demerit.
Params:	line – the line/part number
Returns:	the requested active node
Params:	prepend – a string to prepend on each entry
Returns:	the requested string
/

org.apache.xmlgraphics/ fop/ 2.3/ org/apache/fop/layoutmgr/BreakingAlgorithm.java
