Hi vincent,
thanks for your reply! Comments below.
Il giorno 05/set/08, alle ore 20:20, Vincent Hennebert ha scritto:
In LegalBreakHandler:
A lot of things here need changes... My (wrong) assumption was that
backtracking was needed only for best fit at line level and this
invalidate my backtracking implementation.
- what is the purpose of the countLayoutClass variable?
It's one of the ugly hack I was talking about ;) In best fit at line
level whenever a line ends only the best layout will be kept, so for
each layout class there can be only one layout: together with
classIter.hasNext(), countLayoutClass tell us if we are iterating the
unique layoutclass and so if we are going to remove the only layout
available. This is obviously no more valid for any other *fit algorithm.
- mind the second part of the ‘if (ratio < -1.0 || p.isForcedBreak())’
test: are you sure your modifications inside this if branch are meant
to apply to such a case?
What I do here is removing the layout if it's not the only available,
but as I wrote before this check is wrong.
- why are you removing the last element from the layout?
This is backtracking: in that case the line is overflowing the line
box, this layout should be removed but because this the only one we
remove the last element (so we are sure we don't overflow) and add it
to feasebleBreak: KnuthIterator will reconsider the removed element.
- the ‘removed’ boolean will be set to true as soon as one layout
overflows its containing part (l.78). But that doesn’t mean that,
inside the ‘if (best != null)’ branch, the best layout will be this
overflowing layout, does it? What if there is another feasible layout
that appears to have fewer demerits than the overflowing one?
Same story, it's the only layout in best fit at line level but, again,
it's a wrong assumption.
- plus, the demerits that will be computed for the overflowing layout
will correspond to the overflowing part (line/page); not to that part
after the last element has been removed. In that case the demerits
may
be completely different, possibly lower, or higher if the part
becomes
underfull.
... Ooops! My bad, I forgot to pass the modified layout to
computeDemerits.
In ParagraphLayoutManager:
- what do you mean by ‘paragraph best fit’ actually?
When the end of the paragraph is reached I keep only the best layout.
- I didn’t get the purpose of the oldMinPageNum and newMinPageNum
variables. I understand it’s to trigger the selection of the
best-fitting page, but why does the fact that those variables become
different mean that it’s time to proceed with the page selection?
I'm not sure this is correct, but that is my idea: I want to choose
the best layout for a page among all possible layouts for it.
Initially all layouts have 0 as page number, at some point one layout
will reach a page break and its page number will become 1: obviously
we don't know if this is the best layout. Until there's a layout
working on the first page we don't have all possible layouts for that
page and *MinPageNum is still 0; as soon as the last layout working on
page 0 reaches the page break, newMinPage become 1 and differs from
oldPageNum: we have all possible layout for page 1, I can choose the
best one. Actually I keep only the best of all layout when I reach
this point, but keeping all layout starting from the layout for the
first page would be a better solution. In other words, if I have two
possible layouts for the first page and the best of those have two
childs layout when I'm going choose the best page I should keep both.
- why did you implement page best-fit in this class? What happens for
a document solely made of blocks (or paragraphs of 1 line)?
Yes, I need to extend the implementation to other LMs.
From a higher level point of vue, my hope is to be able to do without
any backtracking, that would cost much processing time and memory. I
do
realize that this pretty much kills your whole approach :-\
Basically the algorithm would remain the same; only, steps would be
introduced at judicious places (!) where some layouts would be early
discarded. For first fit, as soon as a part is completed all of the
other layouts corresponding to the same part would be discarded. For
best fit, you keep one layout per layout class: in a call to next(),
you
compare each completed layout with the current layout of the same
class,
and you keep the best of them.
I suggest you not to bother about recovering right now, and make your
examples such that a final layout will be found in any case. The
recovering mechanism is a separate concern IMO (basically, the idea
will
be to keep an underfull layout under the hand, ‘just in case’).
It's not a problem, I agree, remember I was just coding as an exercise
to understand your code. In the past days I was already working on my
code to make backtracking independent from any *Fit algorithm and to
make backtracking working for page break too (think if you have two
layouts with same line breaking but one of them have just done a page
break and the other one not... bad things can happens if at line level
you keep the layout that will be discarded by the page breaker). It's
not wasted time, I've increased my understanding.
Just keep in mind my primary aim: rendering pages as soon as possible
to free memory. For this purpose I think a best fit at page level
algorithm it's mandatory. To allow nice layout the idea is to keep all
possible layouts for the last N pages starting from the best layout
for page N-1. For N=10, when laying out the page 11 consider only the
children layouts of the best page 1.
Getting tables working would allow me to validate the approach I
think,
since it’s one of the most complex typesetting objects. The next
step is
then to validate the design: for example working on tables made me
bring
major architectural changes. Implementing a few other features like
widows and orphans, keeps and breaks, maybe side-floats, would allow
me
to ensure the prototype has the right shape. The rationale being that
heavy refactoring is much easier on a prototype of a few thousand
lines,
rather than on a software of hundreds of thousand of lines...
Ok, thanks, for all your comments and suggestions. The next week I'll
meet Luca Furini and we will consider how to proceed. As soos as you
can share your code on tables handling I'll look in to it.
Dario
