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 classClass that stores, for each fitness class, the best active node that could start a line of the corresponding fitness ending at the current element.classClass 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 intThe number of active nodes.protected intAlignment of the paragraph/page.protected intAlignment of the paragraph's last line.static final intAll feasible breaks are ok.protected BreakingAlgorithm.BestRecordsBest records.protected booleanIf set to true, doesn't ignore break possibilities which are definitely too short.protected intThe highest + 1 available line in the set of active nodes.protected intDemerit for consecutive lines belonging to incompatible fitness classes .protected booleanUsed to handle the text-indent property (indent the first line of a paragraph).protected static final intMaximum adjustment rationprotected intThe width of a line (or height of a column in page-breaking mode).protected static final org.apache.commons.logging.Logthe logger for the classprotected intMaximum number of consecutive lines ending with a flagged penalty.static final intThis forbids hyphenation.static final intwrap-option = "no-wrap".protected KnuthSequence<KnuthElement> The paragraph of KnuthElements.protected intDemerit for consecutive lines ending at flagged penalties.protected intThe lowest available line in the set of active nodes.protected intThe total shrink of all elements handled so far.protected intThe total stretch of all elements handled so far.protected intThe 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 voidactivateNode(BreakingAlgorithm.KnuthNode node, int difference, double r, double demerits, int fitnessClass, int availableShrink, int availableStretch) Activate the given node.protected voidaddNode(int line, BreakingAlgorithm.KnuthNode node) Add a node at the end of the given line's existing active nodes.protected voidcalculateBreakPoints(BreakingAlgorithm.KnuthNode node, KnuthSequence par, int total) Determines the set of optimal breakpoints corresponding to the given active node.protected BreakingAlgorithm.KnuthNodeCompare two KnuthNodes and return the node with the least demerit.protected doublecomputeAdjustmentRatio(BreakingAlgorithm.KnuthNode activeNode, int difference) Return the adjustment ratio needed to make up for the difference.protected doublecomputeDemerits(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 intcomputeDifference(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 voidconsiderLegalBreak(KnuthElement element, int elementIdx) Determines if the given breakpoint is a feasible breakpoint.protected voidcreateForcedNodes(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.KnuthNodecreateNode(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.KnuthNodecreateNode(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 voiddeactivateNode(BreakingAlgorithm.KnuthNode node, int line) Deactivate the given nodeprotected voidprotected booleanelementCanEndLine(KnuthElement element, int line, int difference) Check if the givenKnuthElementcan end the line with the given number.protected abstract intFilter active nodes.intfindBreakingPoints(KnuthSequence par, double threshold, boolean force, int allowedBreaks) intfindBreakingPoints(KnuthSequence par, int startIndex, double threshold, boolean force, int allowedBreaks) Finds an optimal set of breakpoints for the given paragraph.protected voidfinish()Hook for subclasses to trigger special behavior after ending the main loop infindBreakingPoints(KnuthSequence,int,double,boolean,int)protected voidforceNode(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.intintprotected KnuthElementgetElement(int idx) Return the element at index idx in the paragraph.protected intobtain ipd differenceprotected BreakingAlgorithm.KnuthNodeprotected final BreakingAlgorithm.KnuthNodeReturn the last node that yielded a too short line.protected intprotected intgetLineWidth(int line) Returns the line/part width of a given line/part.protected intprotected BreakingAlgorithm.KnuthNodegetNode(int line) Returns the first active node for the given line.protected voidHandle aKnuthBox.protected final KnuthElementhandleElementAt(int position, boolean previousIsBox, int allowedBreaks) Generic handler for aKnuthElementat the givenposition, taking into account whether the preceding element was a box, and which type(s) of breaks are allowed.protected intprotected voidhandleGlueAt(KnuthGlue glue, int position, boolean previousIsBox, int allowedBreaks) Handle aKnuthGlueat the given position, taking into account the additional parameters.protected inthandle ipd changeprotected voidhandlePenaltyAt(KnuthPenalty penalty, int position, int allowedBreaks) Handle aKnuthPenaltyat the given position, taking into account the type of breaks allowed.protected booleanprotected voidInitializes the algorithm's variables.protected booleanControls the behaviour of the algorithm in cases where the first element of a part overflows a line/page.protected BreakingAlgorithm.KnuthNodeRecover from an overflow condition.protected BreakingAlgorithm.KnuthNoderecoverFromTooLong(BreakingAlgorithm.KnuthNode lastTooLong) Recover from aBreakingAlgorithm.KnuthNodeleading to a line that is too long.protected voidremoveNode(int line, BreakingAlgorithm.KnuthNode node) Remove the given active node registered for the given line.protected final voidReplace the last too-long or too-short node by the last deactivated node, if applicable.protected intrestartFrom(BreakingAlgorithm.KnuthNode restartingNode, int currentIndex) Restart from the given node at the given index.voidsetConstantLineWidth(int lineWidth) Creates a string representation of the active nodes.abstract voidupdateData1(int total, double demerits) Empty method, hook for subclasses.abstract voidupdateData2(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_BEFOREandConstants.EN_AFTERare mapped to the corresponding inline properties,Constants.EN_STARTandConstants.EN_END.alignLast- alignment of the paragraph's last linefirst- for the text-indent property (trueif the first line of a paragraph should be indented)partOverflowRecovery-trueif 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-trueif 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_PENALTIESorALL_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-trueif 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_PENALTIESorALL_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.KnuthNodeleading 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 aKnuthElementat 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-trueif the previous element is a boxallowedBreaks- the type(s) of breaks allowed; should be one ofALL_BREAKS,NO_FLAGGED_PENALTIESorONLY_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- theKnuthBoxto handle
-
handleGlueAt
Handle aKnuthGlueat the given position, taking into account the additional parameters.- Parameters:
glue- theKnuthGlueto handleposition- the position of the glue in the listpreviousIsBox-trueif the preceding element is a boxallowedBreaks- the type of breaks that are allowed
-
handlePenaltyAt
Handle aKnuthPenaltyat the given position, taking into account the type of breaks allowed.- Parameters:
penalty- theKnuthPenaltyto 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
lastForcednode
-
restartFrom
Restart from the given node at the given index.- Parameters:
restartingNode- theBreakingAlgorithm.KnuthNodeto 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 givenKnuthElementcan end the line with the given number.- Parameters:
element- the elementline- the line numberdifference- an integer- Returns:
trueif 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.KnuthNodebeing registered as a feasible breakpoint, if thedemeritsare 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()
-