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