[The Web Maestro]
I don't know how the spec deals with this, but I doubt the spec cares which algorithm is used. That said, would it be a good idea to determine which algorithm to use based on something in userconfig.xml or something? If the Knuth system is more 'expensive' in terms of resources, we could make non-Knuth the default, and enable Knuth via a config file.
Yes indeed. But without measurements I would guess that knuth page breaking would be far less expensive than the knuth line breaking. The line breaking has to deal with far more elements and because of that a far larger set of active nodes.
But clearly a choice will be good, both for page and for line breaking.
[Victor]
The good news is that this is an excellent idea. The bad news is that FOP's determination to not even tolerate more than one algorithm is what drove FOP and FOray apart. So you have stumbled in to a somewhat sensitive area, which might explain the absence of responses (so far).
BTW, since it is relevant here, thanks for your kind comments last week in another thread. You are ever the peacemaker, a very useful role. As long as the differences remain as great as they are, we *need* more than one FO implementation. In the meantime, I am much more useful and productive outside of FOP than I am in it, and, the FOP developers probably are also.
To my perhaps still naive mind, layout consists of exactly two tasks: 1) finding line-breaks within logical blocks (nested blocks consisting of a new logical block), and 2) finding page-breaks between and within logical blocks. All other tasks can be conveniently handled within the two data structures, not being dependent on any strategy. The Knuth-style algorithm is by definition a total-fit algorithm. The scope of such an algorithm for the first task is the logical block itself. The scope of the second task is the page-sequence. So, to implement a Knuth-style algorithm (itself a good idea) for item 2, requires the ability to see an entire page-sequence in the AreaTree at one time.
Not at all. It is a rather trivial change to knuth to pick a page break when there is N pages of lookahead.
If we assume that finished page knuth element arrive one at time to the KnuthPage algorithm, the main loop becomes:
addKnuthElement(element) {
if element.isBox():
totalWidth += element.width
else if element.isGlue():
if (previous element is box):
considerLegalBreak()
totalWidth += element.width
totalStretch += element.stretch
totalShrink += element.shrink
else if element.isPenalty():
if element.penalty < INFINITE:
considerLegalBreak()
if activeList.startLine > currentPage + lookahead:
// In the activeList, find the node with the best demerit.
bestNode = findBestDemerit()
// Remove all nodes in activeList which does not have bestNode
// in their parentage.
clearActiveList(bestNode)
makePageBreak(bestNode)Here it is only clearActiveList() which does not have a fast implementation when using the usual implementation of ActiveNode. It will require a scan over all the active node and for each node a scan back thru the previous links to the node at currentPage+1.
clearActiveList(bestNode):
for node in activeList:
// jump back thru previous (node.page-currentPage) times.
while i++ < node.page - currentPage
previous = node.previous
if previous != bestNode:
activeList.remove(node)
The rest of the methods called are similar to the methods in my knuth line breaking patch (which is quite similar the current implementation).
My own insecurity comes from figuring out which penalty values and demerit algorihtm to use to get keeps and orphans right.
regards, finn
