Class BreakingAlgorithm

  • Direct Known Subclasses:
    LineLayoutManager.LineBreakingAlgorithm, PageBreakingAlgorithm

    public abstract class BreakingAlgorithm
    extends java.lang.Object
    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 BreakingAlgorithm.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'
         }
     }
     
    • Field Detail

      • log

        protected static final org.apache.commons.logging.Log log
        the logger for the class
      • INFINITE_RATIO

        protected static final int INFINITE_RATIO
        Maximum adjustment ration
        See Also:
        Constant Field Values
      • ALL_BREAKS

        public static final int ALL_BREAKS
        All feasible breaks are ok.
        See Also:
        Constant Field Values
      • NO_FLAGGED_PENALTIES

        public static final int NO_FLAGGED_PENALTIES
        This forbids hyphenation.
        See Also:
        Constant Field Values
      • ONLY_FORCED_BREAKS

        public static final int ONLY_FORCED_BREAKS
        wrap-option = "no-wrap".
        See Also:
        Constant Field Values
      • repeatedFlaggedDemerit

        protected int repeatedFlaggedDemerit
        Demerit for consecutive lines ending at flagged penalties.
      • incompatibleFitnessDemerit

        protected int incompatibleFitnessDemerit
        Demerit for consecutive lines belonging to incompatible fitness classes .
      • maxFlaggedPenaltiesCount

        protected int maxFlaggedPenaltiesCount
        Maximum number of consecutive lines ending with a flagged penalty. Only a value >= 1 is a significant limit.
      • threshold

        private double threshold
        The threshold for considering breaks to be acceptable. The adjustment ratio must be inferior to this threshold.
      • par

        protected KnuthSequence par
        The paragraph of KnuthElements.
      • lineWidth

        protected int lineWidth
        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.
      • force

        private boolean force
        Force the algorithm to find a set of breakpoints, even if no feasible breakpoints exist.
      • considerTooShort

        protected boolean considerTooShort
        If set to true, doesn't ignore break possibilities which are definitely too short.
      • lastTooLong

        private BreakingAlgorithm.KnuthNode lastTooLong
        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.
      • lastTooShort

        private BreakingAlgorithm.KnuthNode lastTooShort
        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.
      • lastDeactivated

        private BreakingAlgorithm.KnuthNode lastDeactivated
        The node to be reactivated if no set of feasible breakpoints can be found for this paragraph.
      • alignment

        protected int alignment
        Alignment of the paragraph/page. One of EN_START, EN_JUSTIFY, etc.
      • alignmentLast

        protected int alignmentLast
        Alignment of the paragraph's last line.
      • indentFirstPart

        protected boolean indentFirstPart
        Used to handle the text-indent property (indent the first line of a paragraph).
      • activeLines

        protected BreakingAlgorithm.KnuthNode[] activeLines
        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.
      • activeNodeCount

        protected int activeNodeCount
        The number of active nodes.
      • startLine

        protected int startLine
        The lowest available line in the set of active nodes.
      • endLine

        protected int endLine
        The highest + 1 available line in the set of active nodes.
      • totalWidth

        protected int totalWidth
        The total width of all elements handled so far.
      • totalStretch

        protected int totalStretch
        The total stretch of all elements handled so far.
      • totalShrink

        protected int totalShrink
        The total shrink of all elements handled so far.
      • partOverflowRecoveryActivated

        private boolean partOverflowRecoveryActivated
    • Constructor Detail

      • BreakingAlgorithm

        public BreakingAlgorithm​(int align,
                                 int alignLast,
                                 boolean first,
                                 boolean partOverflowRecovery,
                                 int maxFlagCount)
        Create a new instance.
        Parameters:
        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
    • Method Detail

      • getMaxRecoveryAttempts

        protected int getMaxRecoveryAttempts()
        Returns:
        the number of times the algorithm should try to move overflowing content to the next line/page.
      • isPartOverflowRecoveryActivated

        protected boolean isPartOverflowRecoveryActivated()
        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.
      • updateData1

        public abstract void updateData1​(int total,
                                         double demerits)
        Empty method, hook for subclasses. Called before determining the optimal breakpoints corresponding to a given active node.
        Parameters:
        total - number of lines for the active node
        demerits - total demerits of the paragraph for the active node
      • updateData2

        public abstract void updateData2​(BreakingAlgorithm.KnuthNode bestActiveNode,
                                         KnuthSequence sequence,
                                         int total)
        Empty method, hook for subclasses. Called when determining the optimal breakpoints for a given active node.
        Parameters:
        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
      • setConstantLineWidth

        public void setConstantLineWidth​(int lineWidth)
        Parameters:
        lineWidth - the line width
      • findBreakingPoints

        public int findBreakingPoints​(KnuthSequence par,
                                      int startIndex,
                                      double threshold,
                                      boolean force,
                                      int allowedBreaks)
        Finds an optimal set of breakpoints for the given paragraph.
        Parameters:
        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
      • getIPDdifference

        protected int getIPDdifference()
        obtain ipd difference
        Returns:
        an integer
      • handleIpdChange

        protected int handleIpdChange()
        handle ipd change
        Returns:
        an integer
      • recoverFromTooLong

        protected BreakingAlgorithm.KnuthNode recoverFromTooLong​(BreakingAlgorithm.KnuthNode lastTooLong)
        Recover from a BreakingAlgorithm.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.
        Parameters:
        lastTooLong - the node that leads to a "too long" line
        Returns:
        node corresponding to a breakpoint after the previous "too short" line
      • initialize

        protected void initialize()
        Initializes the algorithm's variables.
      • createNode

        protected BreakingAlgorithm.KnuthNode createNode​(int position,
                                                         int line,
                                                         int fitness,
                                                         int totalWidth,
                                                         int totalStretch,
                                                         int totalShrink,
                                                         double adjustRatio,
                                                         int availableShrink,
                                                         int availableStretch,
                                                         int difference,
                                                         double totalDemerits,
                                                         BreakingAlgorithm.KnuthNode previous)
        Creates a new active node for a feasible breakpoint at the given position. Only called in forced mode.
        Parameters:
        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
      • createNode

        protected BreakingAlgorithm.KnuthNode createNode​(int position,
                                                         int line,
                                                         int fitness,
                                                         int totalWidth,
                                                         int totalStretch,
                                                         int totalShrink)
        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.
        Parameters:
        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
        Returns:
        a new node
        See Also:
        createNode(int, int, int, int, int, int, double, int, int, int, double, org.apache.fop.layoutmgr.BreakingAlgorithm.KnuthNode), BreakingAlgorithm.BestRecords
      • getLastTooShort

        protected final BreakingAlgorithm.KnuthNode getLastTooShort()
        Return the last node that yielded a too short line.
        Returns:
        the node corresponding to the last too short line
      • handleElementAt

        protected final KnuthElement handleElementAt​(int position,
                                                     boolean previousIsBox,
                                                     int allowedBreaks)
        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.
        Parameters:
        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
      • handleBox

        protected void handleBox​(KnuthBox box)
        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.
        Parameters:
        box - the KnuthBox to handle
      • handleGlueAt

        protected void handleGlueAt​(KnuthGlue glue,
                                    int position,
                                    boolean previousIsBox,
                                    int allowedBreaks)
        Handle a KnuthGlue at the given position, taking into account the additional parameters.
        Parameters:
        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
      • handlePenaltyAt

        protected void handlePenaltyAt​(KnuthPenalty penalty,
                                       int position,
                                       int allowedBreaks)
        Handle a KnuthPenalty at the given position, taking into account the type of breaks allowed.
        Parameters:
        penalty - the KnuthPenalty to handle
        position - the position of the penalty in the list
        allowedBreaks - the type of breaks that are allowed
      • replaceLastDeactivated

        protected final void replaceLastDeactivated()
        Replace the last too-long or too-short node by the last deactivated node, if applicable.
      • recoverFromOverflow

        protected BreakingAlgorithm.KnuthNode recoverFromOverflow()
        Recover from an overflow condition.
        Returns:
        the new lastForced node
      • restartFrom

        protected int restartFrom​(BreakingAlgorithm.KnuthNode restartingNode,
                                  int currentIndex)
        Restart from the given node at the given index.
        Parameters:
        restartingNode - the BreakingAlgorithm.KnuthNode to restart from
        currentIndex - the current position index
        Returns:
        the index of the restart point
      • considerLegalBreak

        protected void considerLegalBreak​(KnuthElement element,
                                          int elementIdx)
        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.
        Parameters:
        element - the paragraph's element to consider
        elementIdx - the element's index inside the paragraph
      • elementCanEndLine

        protected boolean elementCanEndLine​(KnuthElement element,
                                            int line,
                                            int difference)
        Check if the given KnuthElement can end the line with the given number.
        Parameters:
        element - the element
        line - the line number
        difference - an integer
        Returns:
        true if the element can end the line
      • forceNode

        protected void forceNode​(BreakingAlgorithm.KnuthNode node,
                                 int line,
                                 int elementIdx,
                                 int difference,
                                 double r,
                                 double demerits,
                                 int fitnessClass,
                                 int availableShrink,
                                 int availableStretch)
        Force the given BreakingAlgorithm.KnuthNode, and register it.
        Parameters:
        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
      • createForcedNodes

        protected void createForcedNodes​(BreakingAlgorithm.KnuthNode node,
                                         int line,
                                         int elementIdx,
                                         int difference,
                                         double r,
                                         double demerits,
                                         int fitnessClass,
                                         int availableShrink,
                                         int availableStretch,
                                         int newWidth,
                                         int newStretch,
                                         int newShrink)
      • activateNode

        protected void activateNode​(BreakingAlgorithm.KnuthNode node,
                                    int difference,
                                    double r,
                                    double demerits,
                                    int fitnessClass,
                                    int availableShrink,
                                    int availableStretch)
        Activate the given node. Will result in the given BreakingAlgorithm.KnuthNode being registered as a feasible breakpoint, if the demerits are better than that of the best node registered for the given fitnessClass.
        Parameters:
        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
      • deactivateNode

        protected void deactivateNode​(BreakingAlgorithm.KnuthNode node,
                                      int line)
        Deactivate the given node
        Parameters:
        node - the node
        line - the line number
      • addBreaks

        private void addBreaks​(int line,
                               int elementIdx)
        Adds new active nodes for breaks at the given element.
        Parameters:
        line - number of the previous line; this element will end line number (line+1)
        elementIdx - the element's index
      • computeDifference

        protected int computeDifference​(BreakingAlgorithm.KnuthNode activeNode,
                                        KnuthElement element,
                                        int elementIndex)
        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.
        Parameters:
        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.
      • computeAdjustmentRatio

        protected double computeAdjustmentRatio​(BreakingAlgorithm.KnuthNode activeNode,
                                                int difference)
        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.
        Parameters:
        activeNode - the currently active node
        difference - the difference between content-length and available width
        Returns:
        The adjustment ratio.
      • computeDemerits

        protected double computeDemerits​(BreakingAlgorithm.KnuthNode activeNode,
                                         KnuthElement element,
                                         int fitnessClass,
                                         double r)
        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.
        Parameters:
        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
      • getElement

        protected KnuthElement getElement​(int idx)
        Return the element at index idx in the paragraph.
        Parameters:
        idx - index of the element.
        Returns:
        the element at index idx in the paragraph.
      • addNode

        protected void addNode​(int line,
                               BreakingAlgorithm.KnuthNode node)
        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.
        Parameters:
        line - number of the line ending at the node's corresponding breakpoint
        node - the active node to add
      • removeNode

        protected void removeNode​(int line,
                                  BreakingAlgorithm.KnuthNode node)
        Remove the given active node registered for the given line. If there are no more active nodes for this line, adjust the startLine accordingly.
        Parameters:
        line - number of the line ending at the node's corresponding breakpoint
        node - the node to deactivate
      • getNode

        protected BreakingAlgorithm.KnuthNode getNode​(int line)
        Returns the first active node for the given line.
        Parameters:
        line - the line/part number
        Returns:
        the requested active node
      • getLineWidth

        protected int getLineWidth​(int line)
        Returns the line/part width of a given line/part.
        Parameters:
        line - the line/part number
        Returns:
        the width/length in millipoints
      • getLineWidth

        protected int getLineWidth()
        Returns:
        the constant line/part width or -1 if there is no such value
      • toString

        public java.lang.String toString​(java.lang.String prepend)
        Creates a string representation of the active nodes. Used for debugging.
        Parameters:
        prepend - a string to prepend on each entry
        Returns:
        the requested string
      • filterActiveNodes

        protected abstract int filterActiveNodes()
        Filter active nodes.
        Returns:
        an integer
      • calculateBreakPoints

        protected void calculateBreakPoints​(BreakingAlgorithm.KnuthNode node,
                                            KnuthSequence par,
                                            int total)
        Determines the set of optimal breakpoints corresponding to the given active node.
        Parameters:
        node - the active node
        par - the corresponding paragraph
        total - the number of lines into which the paragraph will be broken
      • getAlignment

        public int getAlignment()
        Returns:
        the alignment for normal lines/parts
      • getAlignmentLast

        public int getAlignmentLast()
        Returns:
        the alignment for the last line/part
      • handlingFloat

        protected boolean handlingFloat()
      • handleFloat

        protected int handleFloat()
      • disableFloatHandling

        protected void disableFloatHandling()