Andreas L Delmelle wrote:
On Aug 23, 2006, at 21:16, Patrick Paul wrote:
Simon Pepping wrote:
On Tue, Aug 22, 2006 at 11:35:12PM +0200, Andreas L Delmelle wrote:
I've been doing some thinking myself about the separation between
element-list creation and actual line-breaking, and went
wandering through the related sources. Just checking here if my
initial estimates are correct.
Which problem are you trying to solve? Paragraph layout where the line
width changes in the paragraph?
I don't know exactly what Adreas has in mind be we actually need
this for the auto-table layout.
Simon's correct. I'll clarify a bit more. From what I could tell,
Patrick's patch has added code at the right places, it only seems a
bit awkward to me to import stuff related to table-layout into the
LineLayoutManager (even if it is nothing more than a TableHelper).
I have since improved the patch to use a getMinMaxContentWidths() method
that passes the values up the LMs. I will submit it soon. So the only
thing remaning in the way for now is the fact that the element lists are
created twice (since the line-breaking can be disabled using a switch).
(Note: this part was not wrong per se in the patch. It just seems
there currently is no other way, precisely because list-creation and
breaking are performed in the same method. The only place where it
can be entered is somewhere between those two statements --
collectInlineKnuthElements() and createLineBreaks().)
A more correct approach --a matter of taste?-- would be for the
TableContentLM to 'collect' the accumulated list of its descendant
LMs, perform the min/max-width calculation, update the LayoutContext,
and send it back down to the LineBreaker.
When you say 'collect' I suppose you mean that the TableContentLM whould
have to keep all the LinkedLists of elements for the entire table. I
haven't looked at this closely, but wouldn't that also imply some kind
of mechanism on the TableCellLM and BlockLMs when going back down to the
LineBreaker to perform the line-breaking?
If I understand all this correctly, it would imply holding the element
lists for an entire table. Wouldn't that be expensive in terms of memory?
Maybe someone sees another approach that I'm overlooking?
The breaking algorithm needs to be given a LayoutContext with a
certain available amount of ipd. Since the base element list does not
depend on this amount --apart from the start- or end-of-paragraph
elements-- this means it should be feasible to separate the former
from the latter.
This is how I see it too.
In auto-table layout, we have to take into account the possibility
that none of the column-widths are specified. Both minimum and
maximum depend on the content.
I think that this is not only a possibility but a common situation. I
find that I often want to let the formatter determine the optimal column
(and table) widths depending on the content.
Strictly speaking, apart from the arbitrary default 'available ipd /
# columns', you don't have a correct ipd to give to the Breaker. If
you do perform the breaking, however, the element list will also
contain elements that have been added by the Breaker.
A way around this is to give an arbitrarly large default available ipd
the first time you run through the algorithm. This reduces the extra
line-breaking.
Although I haven't done too much investigation on whether they
influence the content-width calculation, this still means these
elements are created for no reason at all.
IOW: this would be a wasted trip through the breaking algorithm.
Correct. This is what is happening for now. I run through the
getNextKnuthElements twice: the first time to determine the minimum and
maximum widths of the content, and the second to do the proper
line-breaking.
<snip />
This may be possible, but it does not seem to be in the spirit of the
algorithm. The algorithm calculates the best layout up to the current
linebreak. You can always interrupt the calculation and resume later,
provided you keep the list of active nodes. If you want N lines, then
you do not determine in advance the end element. You proceed until you
have all active nodes that end line N, and then determine the best of
them. But it is even better to continue to the end of the paragraph,
taking the modified line width into account. That gives you the best
total-fit for the whole paragraph. In that total-fit, the layout for
the first N lines may be suboptimal, but then it is offset by a better
result for the remaining lines.
OK. This makes sense. I'm going to chew some more on this.
The other consideration, but that would be for a more distant future,
is to be able to have three different threads:
- fo creation
- base layoutengine initialization
- actual breaking/layout
Those could run in concert, so the layoutengine initialization does
not need to wait for the endPageSequence() event, but could already
be started much earlier. If it reaches a point where it makes sense
to start with the break computation, the third thread can be started.
Ultimately, this will end up running out of input, and control will
be returned to the second thread. If the second thread runs out of
FOs, it returns control to the first.
In theory, it then also becomes possible, for both a total-fit and
first-fit algorithm, to release certain FOs before the layout for the
entire page-sequence is finished.
Cheers,
Andreas
Patrick