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
pruneLayoutsTreeOk2.diff
Description: Binary data
