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

Reply via email to