Package org.apache.fop.layoutmgr
Class BreakingAlgorithm
java.lang.Object
org.apache.fop.layoutmgr.BreakingAlgorithm
- Direct Known Subclasses:
BalancingColumnBreakingAlgorithm
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' } }
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprotected class
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
Class recording all the informations of a feasible breaking point. -
Field Summary
FieldsModifier and TypeFieldDescriptionprotected BreakingAlgorithm.KnuthNode[]
The set of active nodes in ascending line order.protected int
The number of active nodes.protected int
Alignment of the paragraph/page.protected int
Alignment of the paragraph's last line.static final int
All feasible breaks are ok.protected BreakingAlgorithm.BestRecords
Best records.protected boolean
If set to true, doesn't ignore break possibilities which are definitely too short.protected int
The highest + 1 available line in the set of active nodes.protected int
Demerit for consecutive lines belonging to incompatible fitness classes .protected boolean
Used to handle the text-indent property (indent the first line of a paragraph).protected static final int
Maximum adjustment rationprotected int
The width of a line (or height of a column in page-breaking mode).protected static final org.apache.commons.logging.Log
the logger for the classprotected int
Maximum number of consecutive lines ending with a flagged penalty.static final int
This forbids hyphenation.static final int
wrap-option = "no-wrap".protected KnuthSequence
The paragraph of KnuthElements.protected int
Demerit for consecutive lines ending at flagged penalties.protected int
The lowest available line in the set of active nodes.protected int
The total shrink of all elements handled so far.protected int
The total stretch of all elements handled so far.protected int
The total width of all elements handled so far. -
Constructor Summary
ConstructorsConstructorDescriptionBreakingAlgorithm
(int align, int alignLast, boolean first, boolean partOverflowRecovery, int maxFlagCount) Create a new instance. -
Method Summary
Modifier and TypeMethodDescriptionprotected void
activateNode
(BreakingAlgorithm.KnuthNode node, int difference, double r, double demerits, int fitnessClass, int availableShrink, int availableStretch) Activate the given node.protected void
addNode
(int line, BreakingAlgorithm.KnuthNode node) Add a node at the end of the given line's existing active nodes.protected void
calculateBreakPoints
(BreakingAlgorithm.KnuthNode node, KnuthSequence par, int total) Determines the set of optimal breakpoints corresponding to the given active node.protected BreakingAlgorithm.KnuthNode
Compare two KnuthNodes and return the node with the least demerit.protected double
computeAdjustmentRatio
(BreakingAlgorithm.KnuthNode activeNode, int difference) Return the adjustment ratio 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 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) 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 void
deactivateNode
(BreakingAlgorithm.KnuthNode node, int line) Deactivate the given nodeprotected void
protected boolean
elementCanEndLine
(KnuthElement element, int line, int difference) Check if the givenKnuthElement
can end the line with the given number.protected abstract int
Filter active nodes.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()
Hook for subclasses to trigger special behavior after ending the main loop infindBreakingPoints(KnuthSequence,int,double,boolean,int)
protected void
forceNode
(BreakingAlgorithm.KnuthNode node, int line, int elementIdx, int difference, double r, double demerits, int fitnessClass, int availableShrink, int availableStretch) Force the givenBreakingAlgorithm.KnuthNode
, and register it.int
int
protected KnuthElement
getElement
(int idx) Return the element at index idx in the paragraph.protected int
obtain ipd differenceprotected BreakingAlgorithm.KnuthNode
protected final BreakingAlgorithm.KnuthNode
Return the last node that yielded a too short line.protected int
protected int
getLineWidth
(int line) Returns the line/part width of a given line/part.protected int
protected BreakingAlgorithm.KnuthNode
getNode
(int line) Returns the first active node for the given line.protected void
Handle aKnuthBox
.protected final KnuthElement
handleElementAt
(int position, boolean previousIsBox, int allowedBreaks) Generic handler for aKnuthElement
at the givenposition
, taking into account whether the preceding element was a box, and which type(s) of breaks are allowed.protected int
protected void
handleGlueAt
(KnuthGlue glue, int position, boolean previousIsBox, int allowedBreaks) Handle aKnuthGlue
at the given position, taking into account the additional parameters.protected int
handle ipd changeprotected void
handlePenaltyAt
(KnuthPenalty penalty, int position, int allowedBreaks) Handle aKnuthPenalty
at the given position, taking into account the type of breaks allowed.protected boolean
protected void
Initializes the algorithm's variables.protected boolean
Controls the behaviour of the algorithm in cases where the first element of a part overflows a line/page.protected BreakingAlgorithm.KnuthNode
Recover from an overflow condition.protected BreakingAlgorithm.KnuthNode
recoverFromTooLong
(BreakingAlgorithm.KnuthNode lastTooLong) Recover from aBreakingAlgorithm.KnuthNode
leading to a line that is too long.protected void
removeNode
(int line, BreakingAlgorithm.KnuthNode node) Remove the given active node registered for the given line.protected final void
Replace the last too-long or too-short node by the last deactivated node, if applicable.protected int
restartFrom
(BreakingAlgorithm.KnuthNode restartingNode, int currentIndex) Restart from the given node at the given index.void
setConstantLineWidth
(int lineWidth) 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.
-
Field Details
-
log
protected static final org.apache.commons.logging.Log logthe logger for the class -
INFINITE_RATIO
protected static final int INFINITE_RATIOMaximum adjustment ration- See Also:
-
ALL_BREAKS
public static final int ALL_BREAKSAll feasible breaks are ok.- See Also:
-
NO_FLAGGED_PENALTIES
public static final int NO_FLAGGED_PENALTIESThis forbids hyphenation.- See Also:
-
ONLY_FORCED_BREAKS
public static final int ONLY_FORCED_BREAKSwrap-option = "no-wrap".- See Also:
-
repeatedFlaggedDemerit
protected int repeatedFlaggedDemeritDemerit for consecutive lines ending at flagged penalties. -
incompatibleFitnessDemerit
protected int incompatibleFitnessDemeritDemerit for consecutive lines belonging to incompatible fitness classes . -
maxFlaggedPenaltiesCount
protected int maxFlaggedPenaltiesCountMaximum number of consecutive lines ending with a flagged penalty. Only a value >= 1 is a significant limit. -
par
The paragraph of KnuthElements. -
lineWidth
protected int lineWidthThe 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 considerTooShortIf set to true, doesn't ignore break possibilities which are definitely too short. -
alignment
protected int alignmentAlignment of the paragraph/page. One of EN_START, EN_JUSTIFY, etc. -
alignmentLast
protected int alignmentLastAlignment of the paragraph's last line. -
indentFirstPart
protected boolean indentFirstPartUsed to handle the text-indent property (indent the first line of a paragraph). -
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 activeNodeCountThe number of active nodes. -
startLine
protected int startLineThe lowest available line in the set of active nodes. -
endLine
protected int endLineThe highest + 1 available line in the set of active nodes. -
totalWidth
protected int totalWidthThe total width of all elements handled so far. -
totalStretch
protected int totalStretchThe total stretch of all elements handled so far. -
totalShrink
protected int totalShrinkThe total shrink of all elements handled so far. -
best
Best records.
-
-
Constructor Details
-
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 ofConstants.EN_START
,Constants.EN_JUSTIFY
,Constants.EN_CENTER
,Constants.EN_END
. For pages,Constants.EN_BEFORE
andConstants.EN_AFTER
are mapped to the corresponding inline properties,Constants.EN_START
andConstants.EN_END
.alignLast
- alignment of the paragraph's last linefirst
- 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/partmaxFlagCount
- maximum allowed number of consecutive lines ending at a flagged penalty item
-
-
Method Details
-
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.
-
getLastTooLong
-
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 nodedemerits
- 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 breakpointssequence
- the corresponding paragraphtotal
- 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, double threshold, boolean force, int allowedBreaks) - Parameters:
par
- the paragraph to breakthreshold
- upper bound of the adjustment ratioforce
-true
if a set of breakpoints must be found, even if there are no feasible onesallowedBreaks
- the type(s) of breaks allowed. One ofONLY_FORCED_BREAKS
,NO_FLAGGED_PENALTIES
orALL_BREAKS
.- Returns:
- the number of effective breaks
- See Also:
-
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 breakstartIndex
- index of the Knuth element at which the breaking must startthreshold
- upper bound of the adjustment ratioforce
-true
if a set of breakpoints must be found, even if there are no feasible onesallowedBreaks
- the type(s) of breaks allowed. One ofONLY_FORCED_BREAKS
,NO_FLAGGED_PENALTIES
orALL_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
Recover from aBreakingAlgorithm.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 sequenceline
- number of the line ending at the breakpointfitness
- 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 breakpointtotalStretch
- accumulated stretchability of the KnuthElements up to after the breakpointtotalShrink
- accumulated shrinkability of the KnuthElements up to after the breakpointadjustRatio
- adjustment ratio if the line ends at this breakpointavailableShrink
- available stretch of the line ending at this breakpointavailableStretch
- available shrink of the line ending at this breakpointdifference
- difference between target and actual line widthtotalDemerits
- minimum total demerits up to the breakpointprevious
- 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 sequenceline
- number of the line ending at the breakpointfitness
- 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 breakpointtotalStretch
- accumulated stretchability of the KnuthElements up to after the breakpointtotalShrink
- accumulated shrinkability of the KnuthElements up to after the breakpoint- Returns:
- a new node
- See Also:
-
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 aKnuthElement
at the givenposition
, 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)
orhandlePenaltyAt(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 paragraphpreviousIsBox
-true
if the previous element is a boxallowedBreaks
- the type(s) of breaks allowed; should be one ofALL_BREAKS
,NO_FLAGGED_PENALTIES
orONLY_FORCED_BREAKS
- Returns:
- the handled element
-
handleBox
Handle aKnuthBox
.
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 callsuper.handleBox(box)
to avoid unwanted side-effects.- Parameters:
box
- theKnuthBox
to handle
-
handleGlueAt
Handle aKnuthGlue
at the given position, taking into account the additional parameters.- Parameters:
glue
- theKnuthGlue
to handleposition
- the position of the glue in the listpreviousIsBox
-true
if the preceding element is a boxallowedBreaks
- the type of breaks that are allowed
-
handlePenaltyAt
Handle aKnuthPenalty
at the given position, taking into account the type of breaks allowed.- Parameters:
penalty
- theKnuthPenalty
to handleposition
- the position of the penalty in the listallowedBreaks
- 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
Recover from an overflow condition.- Returns:
- the new
lastForced
node
-
restartFrom
Restart from the given node at the given index.- Parameters:
restartingNode
- theBreakingAlgorithm.KnuthNode
to restart fromcurrentIndex
- the current position index- Returns:
- the index of the restart point
-
considerLegalBreak
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 considerelementIdx
- the element's index inside the paragraph
-
elementCanEndLine
Check if the givenKnuthElement
can end the line with the given number.- Parameters:
element
- the elementline
- the line numberdifference
- 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 givenBreakingAlgorithm.KnuthNode
, and register it.- Parameters:
node
- the nodeline
- the line numberelementIdx
- the position index of the elementdifference
- the difference between content-length and available widthr
- the adjustment ratiodemerits
- demerits produced by the nodefitnessClass
- the fitness classavailableShrink
- the available amount of shrinkavailableStretch
- 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 givenBreakingAlgorithm.KnuthNode
being registered as a feasible breakpoint, if thedemerits
are better than that of the best node registered for the givenfitnessClass
.- Parameters:
node
- the nodedifference
- the difference between content-length and available widthr
- the adjustment ratiodemerits
- demerits produced by the nodefitnessClass
- the fitness classavailableShrink
- the available amount of shrinkavailableStretch
- the available amount of stretch
-
deactivateNode
Deactivate the given node- Parameters:
node
- the nodeline
- the line number
-
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 breakpointelement
- currently considered breakpointelementIndex
- 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
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 nodedifference
- 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 breakelement
- considered current line breakfitnessClass
- fitness of the current liner
- adjustment ratio for the current line- Returns:
- the demerit of the current line
-
finish
protected void finish()Hook for subclasses to trigger special behavior after ending the main loop infindBreakingPoints(KnuthSequence,int,double,boolean,int)
-
getElement
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
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 breakpointnode
- the active node to add
-
removeNode
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 breakpointnode
- the node to deactivate
-
getNode
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
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
Determines the set of optimal breakpoints corresponding to the given active node.- Parameters:
node
- the active nodepar
- the corresponding paragraphtotal
- 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()
-