xmlgraphics-fop-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Dario Laera <la...@cs.unibo.it>
Subject Layouts tree pruning for the prototype
Date Thu, 09 Oct 2008 14:29:31 GMT
Hi Vincent,

I wrote a new patch that implements a kind of ?-fit algorithm at page- 
level. Let N be the page number for the last page layout obtained and  
X a variable representing the depth of the layout tree I want to keep:  
each time N gets increased (and its value is greater than X) I perform  
a pruning of the layout tree choosing as new root the best layout for  
the page with index N-X. Here is an example: the two graphs below  
represents the trees of possible page layouts, in the first tree we  
have N=4. If X was set to 3, it's time to prune the tree by choosing  
the best subtree with a page-1 layout as root. In the example I  
suppose that 1a has lower demerits than 1b, so I prune the tree from  
1a. Alternatively I can choose the page-1 layout that has the best  
leaf as child (actually not implemented).

       ____0____
      /         \
    *1a*         1b
    /  \         |
   /    \        |
  2a     2b      2c
/  \   /  \    /  \
3a  3b 3c  3d  3e  3f
|
4a

     1a
    /  \
   /    \
  2a     2b
/  \   /  \
3a  3b 3c  3d
|
4a

The X value determine the trade off between good aesthetic results and  
time/memory performance: an high value should obtain results similar  
to total-fit, a low value, say 1, should obtain the fastest performance.

This approach would allow to finalize (create the areas, render) the  
page that has been chosen as new root and, if possible, to free memory  
that is no more necessary (also FO-tree object and relative LM). This  
possibility apart, it seems to me that in general the new prototype  
can benefit from this approach.

The implementation adds a low overhead in terms of memory and  
computation that is largely countervailed by the effect of pruning.  
Each LM has a new pointer (prevPage, pointing to the previous page  
layout in the path to the root) and the pageLM has three int for  
determining the time of pruning (N-X). The PageLM updates this  
integers each time a completedPart() is called. After calling the  
completedPart a LM ask the PageLM if it's time to prune; if so it  
performs the following operation on each active layout (AL):

  * extract the N-X page by walking down the prevPage links (only X  
step, not all layouts in this branch);
  * if it is the best page layout found until now, create a new  
ActiveLayouts object (eventually replacing the old one) and add to it  
the AL;
  * if it is the same best page layout, simply add the AL to the  
ActiveLayouts object previously created;
  * otherwise do nothing, this AL will be discarded.

Finally the new ActiveLayouts will replace the previous layout tree.


Comments are very welcome.
Dario






Mime
View raw message