fop 0.95

org.apache.fop.layoutmgr
Class BreakingAlgorithm

java.lang.Object
  extended by org.apache.fop.layoutmgr.BreakingAlgorithm
Direct Known Subclasses:
BalancingColumnBreakingAlgorithm

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 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'
     }
 }
 


Nested Class Summary
protected  class BreakingAlgorithm.BestRecords
          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 BreakingAlgorithm.KnuthNode
          Class recording all the informations of a feasible breaking point.
 
Field Summary
protected  BreakingAlgorithm.KnuthNode[] activeLines
          The set of active nodes in ascending line order.
protected  int activeNodeCount
          The number of active nodes.
protected  int alignment
          Alignment of the paragraph/page.
protected  int alignmentLast
          Alignment of the paragraph's last line.
static int ALL_BREAKS
          All feasible breaks are ok.
protected  BreakingAlgorithm.BestRecords best
           
protected  boolean bFirst
          Used to handle the text-indent property (indent the first line of a paragraph).
protected  boolean considerTooShort
          If set to true, doesn't ignore break possibilities which are definitely too short.
protected  int endLine
          The highest + 1 available line in the set of active nodes.
protected  int incompatibleFitnessDemerit
          Demerit for consecutive lines belonging to incompatible fitness classes .
protected static int INFINITE_RATIO
          Maximum adjustment ration
protected  int lineWidth
          The width of a line (or height of a column in page-breaking mode).
protected static org.apache.commons.logging.Log log
          the logger for the class
protected  int maxFlaggedPenaltiesCount
          Maximum number of consecutive lines ending with a flagged penalty.
static int NO_FLAGGED_PENALTIES
          This forbids hyphenation.
static int ONLY_FORCED_BREAKS
          wrap-option = "no-wrap".
protected  KnuthSequence par
          The paragraph of KnuthElements.
protected  int repeatedFlaggedDemerit
          Demerit for consecutive lines ending at flagged penalties.
protected  int startLine
          The lowest available line in the set of active nodes.
protected  int totalShrink
          The total shrink of all elements handled so far.
protected  int totalStretch
          The total stretch of all elements handled so far.
protected  int totalWidth
          The total width of all elements handled so far.
 
Constructor Summary
BreakingAlgorithm(int align, int alignLast, boolean first, boolean partOverflowRecovery, int maxFlagCount)
          Create a new instance.
 
Method Summary
protected  void addNode(int line, BreakingAlgorithm.KnuthNode node)
          Add a node at the end of the given line's existing active nodes.
protected  BreakingAlgorithm.KnuthNode compareNodes(BreakingAlgorithm.KnuthNode node1, BreakingAlgorithm.KnuthNode node2)
          Compare two KnuthNodes and return the node with the least demerit.
protected  double computeAdjustmentRatio(BreakingAlgorithm.KnuthNode activeNode, int difference)
          Return the adjust ration needed to make up for the difference.
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.
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.
protected  void considerLegalBreak(KnuthElement element, int elementIdx)
          Determines if the given breakpoint is a feasible breakpoint.
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.
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.
protected abstract  int filterActiveNodes()
           
 int findBreakingPoints(KnuthSequence par, double threshold, boolean force, int allowedBreaks)
           
 int findBreakingPoints(KnuthSequence par, int startIndex, double threshold, boolean force, int allowedBreaks)
          Finds an optimal set of breakpoints for the given paragraph.
protected  void finish()
           
 int getAlignment()
           
 int getAlignmentLast()
           
protected  KnuthElement getElement(int idx)
          Return the element at index idx in the paragraph.
protected  int getLineWidth()
           
protected  int getLineWidth(int line)
          Returns the line/part width of a given line/part.
protected  int getMaxRecoveryAttempts()
           
protected  BreakingAlgorithm.KnuthNode getNode(int line)
          Returns the first active node for the given line.
protected  void handleBox(KnuthBox box)
          Empty method, hook for subclasses.
protected  void initialize()
          Resets the algorithm's variables.
protected  boolean isPartOverflowRecoveryActivated()
          Controls the behaviour of the algorithm in cases where the first element of a part overflows a line/page.
protected  void removeNode(int line, BreakingAlgorithm.KnuthNode node)
          Remove the given active node registered for the given line.
protected  int restartFrom(BreakingAlgorithm.KnuthNode restartingNode, int currentIndex)
           
 void setConstantLineWidth(int lineWidth)
           
 java.lang.String toString(java.lang.String prepend)
          Creates a string representation of the active nodes.
abstract  void updateData1(int total, double demerits)
          Empty method, hook for subclasses.
abstract  void updateData2(BreakingAlgorithm.KnuthNode bestActiveNode, KnuthSequence sequence, int total)
          Empty method, hook for subclasses.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

log

protected static 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.


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.


considerTooShort

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


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.


bFirst

protected boolean bFirst
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.


best

protected BreakingAlgorithm.BestRecords best
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 EN_START, EN_JUSTIFY, etc. For pages EN_BEFORE, EN_AFTER are mapped to the corresponding inline properties (EN_START, EN_END)
alignLast - alignment of the paragraph's last line
first - for the text-indent property (indent the first line of a paragraph)
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
See Also:
calculateBreakPoints(KnuthNode, KnuthSequence, int)

setConstantLineWidth

public void setConstantLineWidth(int lineWidth)

findBreakingPoints

public int findBreakingPoints(KnuthSequence par,
                              double threshold,
                              boolean force,
                              int allowedBreaks)
See Also:
findBreakingPoints(KnuthSequence, int, double, boolean, int)

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 - one of ONLY_FORCED_BREAKS, NO_FLAGGED_PENALTIES, ALL_BREAKS

initialize

protected void initialize()
Resets 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

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.

See Also:
createNode(int, int, int, int, int, int, double, int, int, int, double, org.apache.fop.layoutmgr.BreakingAlgorithm.KnuthNode), BreakingAlgorithm.BestRecords

handleBox

protected void handleBox(KnuthBox box)
Empty method, hook for subclasses.


restartFrom

protected int restartFrom(BreakingAlgorithm.KnuthNode restartingNode,
                          int currentIndex)

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

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
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 adjust ration needed to make up for the difference. A ration of

Parameters:
activeNode -
difference -
Returns:
The ration.

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

finish

protected void finish()

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.

compareNodes

protected BreakingAlgorithm.KnuthNode compareNodes(BreakingAlgorithm.KnuthNode node1,
                                                   BreakingAlgorithm.KnuthNode node2)
Compare two KnuthNodes and return the node with the least demerit.

Parameters:
node1 - The first knuth node.
node2 - The other knuth node.
Returns:
the node with the least demerit.

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

getAlignment

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

getAlignmentLast

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

fop 0.95

Copyright 1999-2008 The Apache Software Foundation. All Rights Reserved.