org.apache.fop.layoutmgr

Class BreakingAlgorithm


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

static int
ALL_BREAKS
All feasible breaks are ok.
protected static int
INFINITE_RATIO
Maximum adjustment ration
static int
NO_FLAGGED_PENALTIES
This forbids hyphenation.
static int
ONLY_FORCED_BREAKS
wrap-option = "no-wrap".
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.
protected boolean
bFirst
Used to handle the text-indent property (indent the first line of a paragraph).
protected BreakingAlgorithm.BestRecords
best
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 int
lineWidth
The width of a line (or height of a column in page-breaking mode).
protected static Log
log
the logger for the class
protected int
maxFlaggedPenaltiesCount
Maximum number of consecutive lines ending with a flagged penalty.
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)
String
toString(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.

Field Details

ALL_BREAKS

public static final int ALL_BREAKS
All feasible breaks are ok.
Field Value:
0

INFINITE_RATIO

protected static final int INFINITE_RATIO
Maximum adjustment ration
Field Value:
1000

NO_FLAGGED_PENALTIES

public static final int NO_FLAGGED_PENALTIES
This forbids hyphenation.
Field Value:
1

ONLY_FORCED_BREAKS

public static final int ONLY_FORCED_BREAKS
wrap-option = "no-wrap".
Field Value:
2

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.

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

best

protected BreakingAlgorithm.BestRecords best

considerTooShort

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

endLine

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

incompatibleFitnessDemerit

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

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.

log

protected static Log log
the logger for the class

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.

repeatedFlaggedDemerit

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

startLine

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

totalShrink

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

totalStretch

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

totalWidth

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

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 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 Details

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

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.

computeAdjustmentRatio

protected double computeAdjustmentRatio(BreakingAlgorithm.KnuthNode activeNode,
                                        int difference)
Return the adjust ration needed to make up for the difference. A ration 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 -
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

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.

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

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.

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

filterActiveNodes

protected abstract int filterActiveNodes()

findBreakingPoints

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

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

finish

protected void finish()

getAlignment

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

getAlignmentLast

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

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.

getLineWidth

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

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

getMaxRecoveryAttempts

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

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

handleBox

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

initialize

protected void initialize()
Resets the algorithm's variables.

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.

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

restartFrom

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

setConstantLineWidth

public void setConstantLineWidth(int lineWidth)

toString

public String toString(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

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)

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