Finn Bock wrote:
> 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).
Advertising
Hmmm. I guess it depends on where the N in "N pages of lookahead" comes
from. If that can be set to include the entire page-sequence, then you can
call it a Knuth-style algorithm. Otherwise, I think you have something less,
which is OK for those who don't want the performance hit.
> My own insecurity comes from figuring out which penalty values and
> demerit algorihtm to use to get keeps and orphans right.
Yes. Fortunately, the XSL-FO standard provides some guidance here, but I
agree that this part will be a challenge.
Good luck. I am glad to see you guys heading down this path. Let me know if
there is anything I can do to help.
Victor Mote
