You are viewing a plain text version of this content. The canonical link for it is here.
Posted to fop-dev@xmlgraphics.apache.org by Jeremias Maerki <de...@greenmail.ch> on 2005/03/22 13:58:37 UTC
Creating combined element lists for a table row from cell element lists
At first, I thought this wouldn't be difficult for easy cases but it
gets harder very quickly. Since the Wiki is currently served from the
backup servers in Amsterdam and therefore is read-only, I'll post here
on the list.
A simple example first:
<fo:table-row>
<fo:table-cell line-height="15pt" id="cell1">
<fo:block>block1</fo:block>
<fo:block>block2</fo:block>
<fo:block>block3</fo:block>
</fo:table-cell>
<fo:table-cell id="cell2">
<fo:block>
<fo:external-graphic src="something"
block-progression-dimension.minimum="15pt"
block-progression-dimension.optimum="30pt"
block-progression-dimension.maximum="45pt"/>
</fo:block>
</fo:table-cell>
</fo:table-row>
Cell1 list:
1) box w=15000
2) penalty w=0 p=0
--legal break
3) box w=15000
4) penalty w=0 p=0
--legal break
5) box w=15000
--cut-off point
6) penalty w=0 p=INF
7) glue w=0 y=INF z=0
8) penalty w=0 p=-INF flagged
Cell2 list:
1) box w=30000
2) penalty w=0 p=INF
3) glue w=0 y=15000 z=15000 (stretch for previous box)
--cut-off point
4) penalty w=0 p=INF
5) glue w=0 y=INF z=0
6) penalty w=0 p=-INF flagged
Creating a combined element list here is easy when I omit stretch and
shrink values:
step list between Cell1 and Cell2:
0, 15000, 30000, 45000
(the step list represents the dotted green lines on the graphic on
http://wiki.apache.org/xmlgraphics-fop/TableLayout)
combined list for row without stretch/shrink:
1) box w=15000 [C1: 1-2] [C2: empty]
2) penalty w=0 p=0
3) box w=15000 [C1: 3-4] [C2: 1-3]
4) penalty w=0 p=0
5) box w=15000 [C1: 5-5] [C2: empty]
-------------------------------------------------------------
So let's just complicate things a lot... :-)
<fo:table-row>
<fo:table-cell line-height="15pt" id="cell1">
<fo:block>block1</fo:block>
<fo:block>block2</fo:block>
<fo:block>block3</fo:block>
</fo:table-cell>
<fo:table-cell id="cell2a">
<fo:block>
<fo:external-graphic src="something"
block-progression-dimension="33pt"/>
</fo:block>
<fo:block line-height="8pt" font-size="8pt">Caption for the above image</fo:block>
</fo:table-cell>
</fo:table-row>
Cell2a list:
1) box w=33000
2) penalty w=0 p=0
--legal break
3) box w=8000
--cut-off point
4) penalty w=0 p=INF
5) glue w=0 y=INF z=0
6) penalty w=0 p=-INF flagged
step list between Cell1 and Cell2a
0, 15000, 30000, 33000, 41000, 45000
There are suddenly a lot more possible break points.
I thought I could come up with a combined element list for this one, too,
but so far I haven't managed. For those who want to join the mind game,
here are the expected results from the broken lists:
break at first legal break:
Part 1 (height -> 15):
Part 2 (height -> 41):
break at second legal break:
Part 1 (height -> 30):
Part 2 (height -> 41):
break at third legal break:
Part 1 (height -> 33):
Part 2 (height -> 15):
break at fourth legal break:
Part 1 (height -> 41):
Part 2 (height -> 15):
no breaks:
Part 1 (height -> 45):
---------------------------------------------------
An alternative approach might be to do create "combined stretch boxes"
(actually box+pen(inf)+glue)
Cell1, combined stretch box: w=45000 y=30000 z=0
Cell2, combined stretch box: w=30000 y=15000 z=15000
Cell2a, combined stretch box: w=41000 y=8000 z=0
The combined stretch box for the whole row is easily calculated:
row combined stretch box in both cases (2 and 2a) is:
w=45000 y=30000 z=0
The LM tries to fit as much as possible into the available area (similar
to block-container with fixed BPD). The rest that doesn't fit at the end
is deferred for the next page where a new combined stretch box is
calculated. The consequence of this is the loss of look-ahead
possibility, since the combined stretch box doesn't know how much can
really fit on the previous page, and a new block list needs to be built.
A point I still have to think about for both approaches is how exactly
to handle row spanning, although I suspect it'll be easier for the first
approach.
I hope this is understandable. Additional ideas welcome...
Jeremias Maerki
RE: Creating combined element lists for a table row from cell element lists
Posted by "Andreas L. Delmelle" <a_...@pandora.be>.
> -----Original Message-----
> From: Jeremias Maerki [mailto:dev.jeremias@greenmail.ch]
>
> It was no distraction. We'll have to look at this as soon as we decided
> on how to attack tables. Your ideas come in shortly after that. I'm not
> discarding what you bring in. It's only about priorities.
Just so we don't create any misunderstanding: that was exactly how I
interpreted it.
The background of my ravings is probably more inspired by the 'known
problems' (i.e. memory issues) with tables in FOP 0.20.5. The key difficulty
being that 'a block is a block' where 'a table is always at _least_ a table,
a column, a body, a row and a cell'.
Anyway, it helps a great deal to try and explain this to someone other than
myself. It certainly gave me a clearer view on what exactly I was trying to
achieve. I guess many of you know the feeling... :-)
Thanks for listening/reading/commenting!
Cheers,
Andreas
Re: Creating combined element lists for a table row from cell element lists
Posted by Jeremias Maerki <de...@greenmail.ch>.
It was no distraction. We'll have to look at this as soon as we decided
on how to attack tables. Your ideas come in shortly after that. I'm not
discarding what you bring in. It's only about priorities.
On 29.03.2005 23:23:41 Andreas L. Delmelle wrote:
<snip/>
> > I understand your idea but I don't see (yet) how this can work out. For
> > the moment anyway, I have a different problem. I still need too figure
> > out how to handle page breaking for tables in the Knuth model. This
> > seems to be a rather critical point to me ATM.
>
> Oh, of course. I just saw the opportunity to unleash some of my ideas, but I
> see now that it is indeed not really relevant to the initial topic of this
> thread --sorry 'bout the unnecessary distractions.
>
> > It all sounds nice and easy in theory but I'm currently
> > at a loss determining how to actually implement it in a
> > not too complicated way.
>
> Nothing you should be worrying about right now. Stay focused on whatever
> you're doing, and don't let it distract you too much --it's clear that I am
> the one who needs to give this more thought, while keeping a closer eye on
> what you're doing :-)
>
>
> Cheers,
>
> Andreas
Jeremias Maerki
RE: Creating combined element lists for a table row from cell element lists
Posted by "Andreas L. Delmelle" <a_...@pandora.be>.
> -----Original Message-----
> From: Jeremias Maerki [mailto:dev.jeremias@greenmail.ch]
> > Me:
> > However, instead of mapping both possibilities to a
> > structure with rows, we could go almost the other way
> > round ...
>
> You may not have a first cell for every row. Take this example:
>
> table
> table-body
> table-row
> cell rowspan=3
> cell rowspan=2
> table-row height=50
> table-row height=20
> cell
>
> In this example you don't have a first cell for the second row.
<snip />
> A more realistic example would be a dominant border in the
> third row for the after edge. You need to have a way to collect all
> relevant borders for each border segment and I currently don't see how
> you would do that.
Very good point indeed!
I even think that *that* was the point where I eventually had to stop and
breathe --slowly, to keep my head from over-heating :-)
Anyway: agreed 1000% --yes, a thousand--, as long as one really needs an
fo:table-cell node in the source document to trigger the instantiation of a
TableCell (or subclass) FONode...
I guess what I'm suggesting would, in your constructed example, come down
to:
table
table-body
cell rowspan=3 starts-row=true row-border=...
border=...
cell rowspan=2 border=...
cell starts-row=true row-height=50 row-border=...
cell starts-row=true row-height=20 row-border=...
cell border=...
The fact that the first of the above cells spans 3 rows, would mean that the
third and fourth cells' *only* possible function is exactly to store the
row's properties.
We wouldn't lose these properties, they would just 'move' to a different
location (and they would still be considered separately from the
cell-particular properties --think of it as a cell with two 'bundles' of
properties)
BTW: the cells' column-number also appears to be pretty crucial in the
approach I'm trying to describe...
<snip />
> I understand your idea but I don't see (yet) how this can work out. For
> the moment anyway, I have a different problem. I still need too figure
> out how to handle page breaking for tables in the Knuth model. This
> seems to be a rather critical point to me ATM.
Oh, of course. I just saw the opportunity to unleash some of my ideas, but I
see now that it is indeed not really relevant to the initial topic of this
thread --sorry 'bout the unnecessary distractions.
> It all sounds nice and easy in theory but I'm currently
> at a loss determining how to actually implement it in a
> not too complicated way.
Nothing you should be worrying about right now. Stay focused on whatever
you're doing, and don't let it distract you too much --it's clear that I am
the one who needs to give this more thought, while keeping a closer eye on
what you're doing :-)
Cheers,
Andreas
Re: Creating combined element lists for a table row from cell element lists
Posted by Jeremias Maerki <de...@greenmail.ch>.
On 26.03.2005 16:05:46 Andreas L. Delmelle wrote:
> > -----Original Message-----
> > From: Jeremias Maerki [mailto:dev.jeremias@greenmail.ch]
> >
>
> <snip />
> > I haven't understood everything you wrote, yet. I think there's a spark
> > of an idea in there but ATM I can't get hold of it. I'd appreciate if
> > you could look at the current table layout code.
>
> Just did.
>
> > The change from first-fit to Knuth approach doesn't invalidate much of it.
>
> Indeed not. What I'm referring to goes more in the direction of 'interaction
> between FOTree and Layout', not so much the workings of the Layout system
> itself --although it's bound to have *some* impact on it, this should be
> minimal (and may even facilitate some of the work, but that's still a
> question-mark for me)
> It appears to me more an alternative to the current solution for bridging
> the gap between tables with and without table-rows.
>
> Currently both possiblities lead to the same structure in the FOTree, which
> is perfectly legitimate --RenderX performs table-normalizing in a
> pre-processing XSLT step, which deals with this amongst others (if I
> remember correctly.. I only had a very quick look and that was quite some
> time ago.)
>
> However, instead of mapping both possibilities to a structure with rows, we
> could go almost the other way round by using a structure with cells as
> direct descendants from the body, where the first cell of each row would be
> a special type (a subclass of TableCell?) that has the ability to store the
> row's properties (if fo:table-rows are explicitly used). The 'starts-row'
> property is there anyway, so it can be put to good use...
You may not have a first cell for every row. Take this example:
table
table-body
table-row
cell rowspan=3
cell rowspan=2
table-row height=50
table-row height=20
cell
In this example you don't have a first cell for the second row. If in
collapsing border model, the second row has a dominant border for start
and end edges, you're in trouble. Of course, this is a constructed
example, but maybe there are also real-world cases that may prove
problematic. A more realistic example would be a dominant border in the
third row for the after edge. You need to have a way to collect all
relevant borders for each border segment and I currently don't see how
you would do that.
> In the Layout Tree the RowLM's initialization would be triggered by these
> row-starting cells, but the RowLM would operate on the cells as direct
> descendants of the body. So the RowLM's cell-list would not correspond to
> the unique list of descendants of a corresponding TableRow, but rather to a
> sublist of the unique list of descendants of its parentLM's
> TableBody/-Header/-Footer. (IOW: the RowLM's could be made re-usable; at
> least, there would not *necessarily* have to be a one-to-one relation
> between fo:table-row, TableRow and RowLM --although it still remains
> possible where it *is* needed.)
>
> I'm still not sure whether it makes sense...
I understand your idea but I don't see (yet) how this can work out. For
the moment anyway, I have a different problem. I still need too figure
out how to handle page breaking for tables in the Knuth model. This
seems to be a rather critical point to me ATM. It all sounds nice and
easy in theory but I'm currently at a loss determining how to actually
implement it in a not too complicated way.
Jeremias Maerki
Re: cell iteration strategy (was: Re: Creating combined element lists for a table row from cell element lists)
Posted by Jeremias Maerki <de...@greenmail.ch>.
On 04.04.2005 20:39:43 Andreas L. Delmelle wrote:
> > -----Original Message-----
> > From: Jeremias Maerki [mailto:dev.jeremias@greenmail.ch]
> >
> > FYI, I've started coding a TableRowIterator which
> > incrementally fetches rows from the FO tree.
> <snip what="very interesting stuff" />
> > In so far it seems I don't really follow Andreas' suggestions even
> > though I borrowed a few ideas. I think the unit grid is necessary
> > because of the algorithm for combining element lists and of course
> > because of border resolution.
>
> ...and background-resolution --> see below
>
> AFAICT, this would indeed be the optimal way to implement what I was getting
> at...
>
> <snip />
> > What I'm not sure of yet is where to put background handling for table,
> > bodies, columns and rows. It'll be either TLM or TCLM.
>
> I'd say the TCLM, since that is by definition the context in which you have
> a reference to all the involved background-properties on all of the
> components of the table. In the most extreme cases, where all or most of the
> different backgrounds are partly visible, the TCLM seems to be the one that
> has access to all data necessary to 'draw' these on top of each other
> (table->body->column->row->cell?) in exactly the right proportions (taking
> into account resolved borders, padding ...)
Yes, I agree, although the real TableLM gets quite slim this way. But
I'll better just get on a bit and see where it leads. FYI, I've already
got rudimentary element list combination (i.e. without row-spanning).
I've been able to reuse most of my column/grid setup code. I expect the
same will be possible for border resolution. I'm currently determining
how best to do the addAreas stage with the infos I get from the Position
objects. The stuff is all carved into little pieces and I now have to
put it together again.
> > If you think I'm completely on the wrong track, stop me soon. The train
> > starts to roll now.... :-) I'm in a hurry. Sorry.
>
> Absolutely not! Train seems to be very much on the right track.
Good to hear. Thanks for the feedback!
Jeremias Maerki
RE: cell iteration strategy (was: Re: Creating combined element lists for a table row from cell element lists)
Posted by "Andreas L. Delmelle" <a_...@pandora.be>.
> -----Original Message-----
> From: Jeremias Maerki [mailto:dev.jeremias@greenmail.ch]
>
> FYI, I've started coding a TableRowIterator which
> incrementally fetches rows from the FO tree.
<snip what="very interesting stuff" />
> In so far it seems I don't really follow Andreas' suggestions even
> though I borrowed a few ideas. I think the unit grid is necessary
> because of the algorithm for combining element lists and of course
> because of border resolution.
...and background-resolution --> see below
AFAICT, this would indeed be the optimal way to implement what I was getting
at...
<snip />
> What I'm not sure of yet is where to put background handling for table,
> bodies, columns and rows. It'll be either TLM or TCLM.
I'd say the TCLM, since that is by definition the context in which you have
a reference to all the involved background-properties on all of the
components of the table. In the most extreme cases, where all or most of the
different backgrounds are partly visible, the TCLM seems to be the one that
has access to all data necessary to 'draw' these on top of each other
(table->body->column->row->cell?) in exactly the right proportions (taking
into account resolved borders, padding ...)
> If you think I'm completely on the wrong track, stop me soon. The train
> starts to roll now.... :-) I'm in a hurry. Sorry.
Absolutely not! Train seems to be very much on the right track.
Cheers,
Andreas
Re: cell iteration strategy (was: Re: Creating combined element lists for a table row from cell element lists)
Posted by Jeremias Maerki <de...@greenmail.ch>.
FYI, I've started coding a TableRowIterator which incrementally fetches
rows from the FO tree. I've (locally) disabled the code that replaces
groups cells into rows. GridUnit is a class I've written earlier. It can
be reused here and gets a reference to the TableCell element. From there
you can look up an optional row and the body it belongs to by inspecting
the parents. Furthermore the GridUnit will receive the resolved borders
(once for the non-break and once for the break case). The effective
half-border-width for the cell will be set on the primary cell of a
spanned cell (see "max border width / 2" comment in
http://wiki.apache.org/xmlgraphics-fop/CollapsingBorderModel), also for
both cases. I will probably subclass GridUnit to PrimaryGridUnit to save
runtime memory for the spanned grid units that don't need this info.
In so far it seems I don't really follow Andreas' suggestions even
though I borrowed a few ideas. I think the unit grid is necessary
because of the algorithm for combining element lists and of course
because of border resolution. And furthermore it's lightweight (a list
of arrays of GridUnit instances). The TableContentLM is probably
something like Andreas' reusable RowLM. It looks like I can pack a lot
of preparational work into that TableRowIterator thus making the
TableContentLM lighter (which will probably be a blessing):
- starts-row|ends-row resolution
- border resolution including "half max border width" calculation
- cell overlap check
- implicit column handling (columns will also get their own container)
- GridUnit factory including setup for CellLM on primary cells
- easy navigation on the grid for the TCLM
What I'm not sure of yet is where to put background handling for table,
bodies, columns and rows. It'll be either TLM or TCLM.
If you think I'm completely on the wrong track, stop me soon. The train
starts to roll now.... :-) I'm in a hurry. Sorry.
On 01.04.2005 11:33:58 Jeremias Maerki wrote:
> Now that I'm mostly finished with the element generation for tables I
> can have another look at this because I need to implement all this now.
> On second thought, I'd like to go into more detail here because I think
> it might indeed be worthwhile to consider going down that road.
>
> Overall, I found exactly one point that needs attention when going away
> from always iterating over rows: The background of a row. This one is
> painted separately and will need some special attention, although I
> think this should be no big problem. I've disregarded
> visibility="collapse" for the moment which is interested only for
> interactive use. This can be done later.
>
> Earlier, I implemented a normalizer in the FO tree that converts a rucksack
> full of cells into rows with their cells at the right position. If we
> take this out we have to move the functionality into a special iterator
> that puts the cells in the appropriate slots at any given step/row.
> Andreas hinted at that already.
>
> What I still think will be necessary is to have a grid for all grid
> units so we can handle the border resolution (and painting) right. This
> means total no. of effective row * total no. of effective columns grid
> unit instances. But parts of the array can be freed when the addAreas
> stage is over. The array can also be used to jump to a position during
> addAreas; we simply need to keep track what index the first row in the
> array has after previous rows have been released. Possibly the array
> will also be instrumental when we get around to implement auto layout.
> Based on the element generation for tables I wrote I will also need to
> find and remember row groups (not those defined in the spec but those
> defined in the Wiki).
>
> Apart from the RowLM we can also get rid of the BodyLM because it's
> mostly the same issue. The body is mostly relevant for border resolution
> and background painting. The only problem there are header and footer.
> I'm thinking along the lines of creating a class owned by the TableLM
> that handles the whole table contents. Headers and footers will probably
> be handled in a special sublass. So in the end we have the TableLM, a
> TableContentLM (or something like that) and CellLM which handles the
> contents of each cell.
>
> I'm still in the process if figuring out how exactly to implement all
> this and I don't know if I'm making any sense here. But feedback and
> help is appreciated.
>
> On 26.03.2005 16:05:46 Andreas L. Delmelle wrote:
> > > -----Original Message-----
> > > From: Jeremias Maerki [mailto:dev.jeremias@greenmail.ch]
> > >
> >
> > <snip />
> > > I haven't understood everything you wrote, yet. I think there's a spark
> > > of an idea in there but ATM I can't get hold of it. I'd appreciate if
> > > you could look at the current table layout code.
> >
> > Just did.
> >
> > > The change from first-fit to Knuth approach doesn't invalidate much of it.
> >
> > Indeed not. What I'm referring to goes more in the direction of 'interaction
> > between FOTree and Layout', not so much the workings of the Layout system
> > itself --although it's bound to have *some* impact on it, this should be
> > minimal (and may even facilitate some of the work, but that's still a
> > question-mark for me)
> > It appears to me more an alternative to the current solution for bridging
> > the gap between tables with and without table-rows.
> >
> > Currently both possiblities lead to the same structure in the FOTree, which
> > is perfectly legitimate --RenderX performs table-normalizing in a
> > pre-processing XSLT step, which deals with this amongst others (if I
> > remember correctly.. I only had a very quick look and that was quite some
> > time ago.)
> >
> > However, instead of mapping both possibilities to a structure with rows, we
> > could go almost the other way round by using a structure with cells as
> > direct descendants from the body, where the first cell of each row would be
> > a special type (a subclass of TableCell?) that has the ability to store the
> > row's properties (if fo:table-rows are explicitly used). The 'starts-row'
> > property is there anyway, so it can be put to good use...
> >
> > In the Layout Tree the RowLM's initialization would be triggered by these
> > row-starting cells, but the RowLM would operate on the cells as direct
> > descendants of the body. So the RowLM's cell-list would not correspond to
> > the unique list of descendants of a corresponding TableRow, but rather to a
> > sublist of the unique list of descendants of its parentLM's
> > TableBody/-Header/-Footer. (IOW: the RowLM's could be made re-usable; at
> > least, there would not *necessarily* have to be a one-to-one relation
> > between fo:table-row, TableRow and RowLM --although it still remains
> > possible where it *is* needed.)
> >
> > I'm still not sure whether it makes sense...
> >
> > Cheers,
> >
> > Andreas
>
>
>
> Jeremias Maerki
Jeremias Maerki
cell iteration strategy (was: Re: Creating combined element lists for a table row from cell element lists)
Posted by Jeremias Maerki <de...@greenmail.ch>.
Now that I'm mostly finished with the element generation for tables I
can have another look at this because I need to implement all this now.
On second thought, I'd like to go into more detail here because I think
it might indeed be worthwhile to consider going down that road.
Overall, I found exactly one point that needs attention when going away
from always iterating over rows: The background of a row. This one is
painted separately and will need some special attention, although I
think this should be no big problem. I've disregarded
visibility="collapse" for the moment which is interested only for
interactive use. This can be done later.
Earlier, I implemented a normalizer in the FO tree that converts a rucksack
full of cells into rows with their cells at the right position. If we
take this out we have to move the functionality into a special iterator
that puts the cells in the appropriate slots at any given step/row.
Andreas hinted at that already.
What I still think will be necessary is to have a grid for all grid
units so we can handle the border resolution (and painting) right. This
means total no. of effective row * total no. of effective columns grid
unit instances. But parts of the array can be freed when the addAreas
stage is over. The array can also be used to jump to a position during
addAreas; we simply need to keep track what index the first row in the
array has after previous rows have been released. Possibly the array
will also be instrumental when we get around to implement auto layout.
Based on the element generation for tables I wrote I will also need to
find and remember row groups (not those defined in the spec but those
defined in the Wiki).
Apart from the RowLM we can also get rid of the BodyLM because it's
mostly the same issue. The body is mostly relevant for border resolution
and background painting. The only problem there are header and footer.
I'm thinking along the lines of creating a class owned by the TableLM
that handles the whole table contents. Headers and footers will probably
be handled in a special sublass. So in the end we have the TableLM, a
TableContentLM (or something like that) and CellLM which handles the
contents of each cell.
I'm still in the process if figuring out how exactly to implement all
this and I don't know if I'm making any sense here. But feedback and
help is appreciated.
On 26.03.2005 16:05:46 Andreas L. Delmelle wrote:
> > -----Original Message-----
> > From: Jeremias Maerki [mailto:dev.jeremias@greenmail.ch]
> >
>
> <snip />
> > I haven't understood everything you wrote, yet. I think there's a spark
> > of an idea in there but ATM I can't get hold of it. I'd appreciate if
> > you could look at the current table layout code.
>
> Just did.
>
> > The change from first-fit to Knuth approach doesn't invalidate much of it.
>
> Indeed not. What I'm referring to goes more in the direction of 'interaction
> between FOTree and Layout', not so much the workings of the Layout system
> itself --although it's bound to have *some* impact on it, this should be
> minimal (and may even facilitate some of the work, but that's still a
> question-mark for me)
> It appears to me more an alternative to the current solution for bridging
> the gap between tables with and without table-rows.
>
> Currently both possiblities lead to the same structure in the FOTree, which
> is perfectly legitimate --RenderX performs table-normalizing in a
> pre-processing XSLT step, which deals with this amongst others (if I
> remember correctly.. I only had a very quick look and that was quite some
> time ago.)
>
> However, instead of mapping both possibilities to a structure with rows, we
> could go almost the other way round by using a structure with cells as
> direct descendants from the body, where the first cell of each row would be
> a special type (a subclass of TableCell?) that has the ability to store the
> row's properties (if fo:table-rows are explicitly used). The 'starts-row'
> property is there anyway, so it can be put to good use...
>
> In the Layout Tree the RowLM's initialization would be triggered by these
> row-starting cells, but the RowLM would operate on the cells as direct
> descendants of the body. So the RowLM's cell-list would not correspond to
> the unique list of descendants of a corresponding TableRow, but rather to a
> sublist of the unique list of descendants of its parentLM's
> TableBody/-Header/-Footer. (IOW: the RowLM's could be made re-usable; at
> least, there would not *necessarily* have to be a one-to-one relation
> between fo:table-row, TableRow and RowLM --although it still remains
> possible where it *is* needed.)
>
> I'm still not sure whether it makes sense...
>
> Cheers,
>
> Andreas
Jeremias Maerki
RE: Creating combined element lists for a table row from cell element lists
Posted by "Andreas L. Delmelle" <a_...@pandora.be>.
> -----Original Message-----
> From: Jeremias Maerki [mailto:dev.jeremias@greenmail.ch]
>
<snip />
> I haven't understood everything you wrote, yet. I think there's a spark
> of an idea in there but ATM I can't get hold of it. I'd appreciate if
> you could look at the current table layout code.
Just did.
> The change from first-fit to Knuth approach doesn't invalidate much of it.
Indeed not. What I'm referring to goes more in the direction of 'interaction
between FOTree and Layout', not so much the workings of the Layout system
itself --although it's bound to have *some* impact on it, this should be
minimal (and may even facilitate some of the work, but that's still a
question-mark for me)
It appears to me more an alternative to the current solution for bridging
the gap between tables with and without table-rows.
Currently both possiblities lead to the same structure in the FOTree, which
is perfectly legitimate --RenderX performs table-normalizing in a
pre-processing XSLT step, which deals with this amongst others (if I
remember correctly.. I only had a very quick look and that was quite some
time ago.)
However, instead of mapping both possibilities to a structure with rows, we
could go almost the other way round by using a structure with cells as
direct descendants from the body, where the first cell of each row would be
a special type (a subclass of TableCell?) that has the ability to store the
row's properties (if fo:table-rows are explicitly used). The 'starts-row'
property is there anyway, so it can be put to good use...
In the Layout Tree the RowLM's initialization would be triggered by these
row-starting cells, but the RowLM would operate on the cells as direct
descendants of the body. So the RowLM's cell-list would not correspond to
the unique list of descendants of a corresponding TableRow, but rather to a
sublist of the unique list of descendants of its parentLM's
TableBody/-Header/-Footer. (IOW: the RowLM's could be made re-usable; at
least, there would not *necessarily* have to be a one-to-one relation
between fo:table-row, TableRow and RowLM --although it still remains
possible where it *is* needed.)
I'm still not sure whether it makes sense...
Cheers,
Andreas
Re: Creating combined element lists for a table row from cell element lists
Posted by Jeremias Maerki <de...@greenmail.ch>.
On 24.03.2005 02:21:59 Andreas L. Delmelle wrote:
> > -----Original Message-----
> > From: Jeremias Maerki [mailto:dev.jeremias@greenmail.ch]
> >
>
> (Just trying to join in the conversation with no specific knowledge about
> the code yet --still catching up on the recent changes--, but I remember
> that, a while ago, I had also been struggling with tables. The code will
> have changed a lot I guess, but some of the options I considered could be of
> use... I hope)
>
> > I tend to think by now that the first approach I presented earlier is
> > illusory and too complicated. The second should work out just fine, even
> > with row span.
>
> Speaking of rowspan: I don't really know if it's even possible, but one of
> the options that kept haunting me --and thus, seemed promising to me-- was
> to not create a rowLM for every cell-list (to bridge the gap between
> 'rowless' and 'explicit rows'), but rather use one rowLM as a sort of 'comb'
> (if the analogy makes sense).
> A cellLM for a fo:table-cell spanning multiple rows --and its children--
> would remain in the rowLM until the cellLM's 'remaining' rowspan becomes
> zero (span here being relative to the page to accommodate cells spanning
> multiple pages). The rowLM _can_ receive its properties from the current
> fo:row, if there is one. If not, these props can be null-ified.
> WRT the column props, my attention had been drawn to the fact that a
> columnList was created for _every_ row, since these:
the columns variable is only a reference to the column list. It's not
rebuilt for every row. What is rebuilt is the gridUnits list but that's
necessary because the borders in collapsing border model [1] depend on
the individual grid units. Each and every segment of a cell border must
be evaluated according to the rules in the spec.
[1] http://wiki.apache.org/xmlgraphics-fop/CollapsingBorderModel
> a. basically stay the same for the whole table in the easiest cases
> b. for the harder cases they are (very) roughly constant for a
> cross-section of
> 1. region of the page (static or flow; possibly multi-column itself)
> 2. (table-header +) table-body (+ table-footer)
>
> Recreating a reference to a list with references to the columns for every
> row seemed to be inefficient somehow --very much so in case of a table
> spanning across many pages containing hundreds, possibly thousands of rows,
> even with only seven or eight columns...
Yes, but I don't think this can be avoided.
> My main motivation for considering such a construct was the fact that, at
> the Area Tree level, there *is* no row, only the union of the areas
> generated by its children, so it seemed to make sense to diminish the
> importance of the row-concept when progressing from FO Tree --multiple-- to
> Layout Tree --one, maybe two or three, but no more-- to Area Tree --zero.
>
> With a few helper rows, it also seemed attractive from the POV of 'marking'
> the earlier described cross-section. Convenient to iterate --in both
> directions-- over the elements in the table (body|header|footer)'s element
> list (the cellLMs), and perform multiple passes, since the first and last
> row on a page contain the necessary references to the bounding elements in
> the element-sublist in question. Go for a 'rough sketch' pass first, if this
> is not sufficient --which conditions exactly?--, iterate over the altered
> elements.
>
> > I'll start with the helpers for keeping track of accumulated BPD.
> > In the meantime I hope there's enough time so you guys can comment on
> this.
>
> Well, possibly more detailed, code-oriented description to follow...
>
> I hope there's a 'Aha!-Erlebnis' in there somewhere for someone.
> If not, I hope you at least enjoyed the rant :-)
> If not --errm... my apologies.
I haven't understood everything you wrote, yet. I think there's a spark
of an idea in there but ATM I can't get hold of it. I'd appreciate if
you could look at the current table layout code. The change from
first-fit to Knuth approach doesn't invalidate much of it.
Jeremias Maerki
Re: Creating combined element lists for a table row from cell element lists
Posted by Jeremias Maerki <de...@greenmail.ch>.
Adding backtracking functionality turns out not to be as simple as I'd
hoped. There are several elements to this:
- tracking on the fly if there are already enough elements created to
fill at least one flow reference area. If that limit is reached return
early and don't let the Knuth algorithm try to distribute the trailing
elements.
- after determining the break, you get a PageBreakPosition. With it it
is possible to find the last element in the current block list. Based in
the Position element of that element you have to reset the layout
managers much like this is done in the first-fit approach in CVS HEAD.
This turns out to be one of the more difficult parts as there are helper
elements that don't have so much information on them to do a proper
reset so for the next page the elements are started to be recreated
exactly where the previous page left off. So it may be necessary to
iterate the block list in forward direction until a key element (like a
normal line or block-container with fixed BPD) is found that has enough
information to do the reset. At least we still have nested position
elements so this is not impossible.
- the blocklist is rendered until the PageBreakPosition is reached, the
rest is discarded. Then the process is repeated with the LMs now reset
so they continue generating Knuth elements where the previous
page/column stopped.
One point in all this is also, how well the early-return point can be
determined to minimize the number of discarded elements. To make it even
more complicated (and to optimize) the elements could be reused if it is
determined that the same elements would be produced anyway because the
available IPD is the same for the next part/page.
Writing this stuff down really helps, but my head's giving smoke signs.
Gonna take a break now...
Jeremias Maerki
RE: Creating combined element lists for a table row from cell element lists
Posted by "Andreas L. Delmelle" <a_...@pandora.be>.
> -----Original Message-----
> From: Jeremias Maerki [mailto:dev.jeremias@greenmail.ch]
>
(Just trying to join in the conversation with no specific knowledge about
the code yet --still catching up on the recent changes--, but I remember
that, a while ago, I had also been struggling with tables. The code will
have changed a lot I guess, but some of the options I considered could be of
use... I hope)
> I tend to think by now that the first approach I presented earlier is
> illusory and too complicated. The second should work out just fine, even
> with row span.
Speaking of rowspan: I don't really know if it's even possible, but one of
the options that kept haunting me --and thus, seemed promising to me-- was
to not create a rowLM for every cell-list (to bridge the gap between
'rowless' and 'explicit rows'), but rather use one rowLM as a sort of 'comb'
(if the analogy makes sense).
A cellLM for a fo:table-cell spanning multiple rows --and its children--
would remain in the rowLM until the cellLM's 'remaining' rowspan becomes
zero (span here being relative to the page to accommodate cells spanning
multiple pages). The rowLM _can_ receive its properties from the current
fo:row, if there is one. If not, these props can be null-ified.
WRT the column props, my attention had been drawn to the fact that a
columnList was created for _every_ row, since these:
a. basically stay the same for the whole table in the easiest cases
b. for the harder cases they are (very) roughly constant for a
cross-section of
1. region of the page (static or flow; possibly multi-column itself)
2. (table-header +) table-body (+ table-footer)
Recreating a reference to a list with references to the columns for every
row seemed to be inefficient somehow --very much so in case of a table
spanning across many pages containing hundreds, possibly thousands of rows,
even with only seven or eight columns...
My main motivation for considering such a construct was the fact that, at
the Area Tree level, there *is* no row, only the union of the areas
generated by its children, so it seemed to make sense to diminish the
importance of the row-concept when progressing from FO Tree --multiple-- to
Layout Tree --one, maybe two or three, but no more-- to Area Tree --zero.
With a few helper rows, it also seemed attractive from the POV of 'marking'
the earlier described cross-section. Convenient to iterate --in both
directions-- over the elements in the table (body|header|footer)'s element
list (the cellLMs), and perform multiple passes, since the first and last
row on a page contain the necessary references to the bounding elements in
the element-sublist in question. Go for a 'rough sketch' pass first, if this
is not sufficient --which conditions exactly?--, iterate over the altered
elements.
> I'll start with the helpers for keeping track of accumulated BPD.
> In the meantime I hope there's enough time so you guys can comment on
this.
Well, possibly more detailed, code-oriented description to follow...
I hope there's a 'Aha!-Erlebnis' in there somewhere for someone.
If not, I hope you at least enjoyed the rant :-)
If not --errm... my apologies.
Greetz,
AD
Re: Creating combined element lists for a table row from cell element lists
Posted by Jeremias Maerki <de...@greenmail.ch>.
I tend to think by now that the first approach I presented earlier is
illusory and too complicated. The second should work out just fine, even
with row span. As I said this would result in the loss of look-ahead,
but this goes in the exact same direction as handling different
available IPD would. I think I'll try to extend the current algorithm
and the LMs so they keep track of how much BPD (min/opt/max) they build
up on lists so they can stop returning elements when one page/part is
completely filled (combined min BPD >= available BPD). This should
minimize the number of discarded elements because of recalculations.
I'll start with the helpers for keeping track of accumulated BPD. In the
meantime I hope there's enough time so you guys can comment on this. I'm
especially keen of reading Luca's thoughts on the topic.
Jeremias Maerki
Re: Creating combined element lists for a table row from cell element lists
Posted by Jeremias Maerki <de...@greenmail.ch>.
Absolutely not. This whole thing here is exactly about page breaking.
I'm just stuck at the moment. That's all. Luca now gave me some new
input I'm currently playing through. As soon as we figure out what
direction to take I'll resume coding. We're currently at that bloody
critical point where it is decided if the Knuth approach will really
work out or not.
On 29.03.2005 16:40:49 Glen Mazza wrote:
> Jeremias, did you discontinue your work on the page
> breaking? I missed the email.
Jeremias Maerki
Re: Creating combined element lists for a table row from cell element lists
Posted by Jeremias Maerki <de...@greenmail.ch>.
Does anyone have any input on the issue of creating Knuth elements for
tables? We talked about handling headers and footers earlier and that
part is pretty clear to me. However, the part about creating Knuth
elements for multi-column tables... I'm pretty clueless ATM. I think
that my second approach could still work but it seems very complicated
to implement and I think there's got to be an easier solution which I
don't see ATM.
Even looking at other layouting systems I get the impression that they
are avoiding breaks inside table-cells. Lout for example doesn't allow
it. Does anyone know how (and if) this is done inside TeX? I don't get a
clue from looking at the TeXBook or the sources.
Jeremias Maerki
Re: Creating combined element lists for a table row from cell element lists
Posted by Jeremias Maerki <de...@greenmail.ch>.
Just to answer this quickly: yes, page breaks inside table-rows (or
rather table-cells) are allowed by default and you use keep-together
when you don't want it split. The spec says: "The fo:table-cell
formatting object generates one or more normal reference-areas."
Keep-together's default is "auto" which allows breaks.
Specifying height or block-progression-dimension (i.e. autoheight=false)
might have the same result as a keep-together but we're not sure how
exactly to handle this case. We talked about that two months ago.
I'll work through the rest of your message shortly.
On 29.03.2005 13:56:59 Luca Furini wrote:
> Jeremias Maerki wrote:
>
> > I thought I could come up with a combined element list for this one, too,
> > but so far I haven't managed.
>
> At last I'm here!
> I start with a question I could not find an answer to: is row splitting
> allowed by default and forbidden using keep-together, or is it forbidden
> unless otherwise specified? (in other words, is this problematic situation
> the most common one, or the most unlikely?)
Jeremias Maerki
Re: Creating combined element lists for a table row from cell element lists
Posted by Jeremias Maerki <de...@greenmail.ch>.
On 29.03.2005 13:56:59 Luca Furini wrote:
> Jeremias Maerki wrote:
<snip/>
> > For those who want to join the mind game,
> > here are the expected results from the broken lists:
> >
> > break at first legal break:
> > Part 1 (height -> 15):
> > Part 2 (height -> 41):
> >
> > break at second legal break:
> > Part 1 (height -> 30):
> > Part 2 (height -> 41):
> >
> > break at third legal break:
> > Part 1 (height -> 33):
> > Part 2 (height -> 15):
> >
> > break at fourth legal break:
> > Part 1 (height -> 41):
> > Part 2 (height -> 15):
> >
> > no breaks:
> > Part 1 (height -> 45):
>
> This could be the procedure that creates the combined elements, at least
> when there is no stretch nor shrink;
I'm impressed!
> with this assumption, the resulting
> sequence will contain only boxes and penalties.
I guess the sequence will have to be post-processed to add penalties for
table-header/footer but that shouldn't be a problem. "before" and "after"
cell borders will also be no big problem. Just saying this so we have
the whole picture.
> First of all, we must know the total height of the row, if it is not split
> between pages.
>
> totalHeight = 0
> for each cell-list
> height[i] = compute the total height of each cell-list
> if (height[i] > totalHeight)
> totalHeight = height[i]
>
> The sequence we are going to create must be totalHeight long when it is
> not divided.
>
> step = 0
> addedBoxHeight = 0;
> while step < totalHeight
> step = nextStep()
> penaltyHeight = step + maxRemainingHeight() - totalHeight
> boxHeight = step - addedBoxHeight - penaltyHeight
> addedBoxHeight += boxHeight
> sequence.add(new box(boxHeight))
> sequence.add(new penalty(penaltyHeight, 0))
>
> For each cell-list, we must know, besides the total height, the height of
> the elements already combined into the new ones.
> The nextStep() method looks at each cell-list, computing the height of the
> first sub-sequence, chooses the smallest increase and updates in each list
> the height of the elements already combined; maxRemainingHeight() returns
> the greatest difference between the total height of a cell-list and the
> height of the elements already combined.
>
> Using your example, the behaviour of this algorithm is this:
>
> totalHeight = 45
>
> 1st step: step = 15
> maxRemaingHeight = 41
> addedBoxHeight = 0
> penaltyHeight = 15 + 41 - 45 = 11
> boxHeight = 15 - 0 - 11 = 4
>
> 2nd step: step = 30
> maxRemaingHeight = 41
> addedBoxHeight = 4
> penaltyHeight = 30 + 41 - 45 = 26
> boxHeight = 30 - 4 - 26 = 0
>
> 3rd step: step = 33
> maxRemaingHeight = 15
> addedBoxHeight = 4
> penaltyHeight = 33 + 15 - 45 = 3
> boxHeight = 33 - 4 - 3 = 26
>
> 4th step: step = 41
> maxRemaingHeight = 15
> addedBoxHeight = 30
> penaltyHeight = 41 + 15 - 45 = 11
> boxHeight = 41 - 30 - 11 = 0
>
> 5th step: step = 45
> maxRemaingHeight = 0
> addedBoxHeight = 30
> penaltyHeight = 45 + 0 - 45 = 0
> boxHeight = 45 - 30 - 0 = 15
>
>
> combined elements, with their width and what happens if a penalty is used:
>
> box 4
> penalty 11 ----> 15+41
> box 0
> penalty 26 ----> 30+41
> box 26
> penalty 3 ----> 33+15
> box 0
> penalty 11 ----> 41+15
> box 15 ----> 45
Wow.
> I think this procedure could be quite easily extended in order to take
> into account stretch and shrink.
I'm not so sure. I agree that some degree of stretch and shrink we be no
problem for the algorithm, but depending on the amount of shrinkability
and stretchability you might get different step constellations you
probably can't construct like this. We probably have to play a few
scenarios through here.
> > An alternative approach might be to do create "combined stretch boxes"
> > (actually box+pen(inf)+glue)
> >
> > Cell1, combined stretch box: w=45000 y=30000 z=0
> > Cell2, combined stretch box: w=30000 y=15000 z=15000
> > Cell2a, combined stretch box: w=41000 y=8000 z=0
> >
> > The combined stretch box for the whole row is easily calculated:
> >
> > row combined stretch box in both cases (2 and 2a) is:
> > w=45000 y=30000 z=0
> >
> > The LM tries to fit as much as possible into the available area (similar
> > to block-container with fixed BPD). The rest that doesn't fit at the end
> > is deferred for the next page where a new combined stretch box is
> > calculated. The consequence of this is the loss of look-ahead
> > possibility, since the combined stretch box doesn't know how much can
> > really fit on the previous page, and a new block list needs to be built.
>
> Yes, I think we should use this approach only if we don't find a better
> one ...
But still, we have to realize that the "combined list approach" cannot
handle auto layout when there's different available IPD between pages or
if the auto layout algorithm to be written should calculate new column
widths for every page.
Maybe sooner or later we may have to implement some kind of back
tracking functionality, so we can discard some already generated
elements and recreate them using new parameters. If we can do without it
for the moment that would be good (80:20 rule). I don't think this will
invalidate the work on combined lists. After all, it will only be a way
to restart at an earlier point. However, the implementation itself will
probably not be so easy (but I may be wrong).
You gave me hope that we can use the "combined list" approach which I
would me more comfortable with, except that stretch is probably easier
with the "stretch box" approach.
> > A point I still have to think about for both approaches is how exactly
> > to handle row spanning, although I suspect it'll be easier for the first
> > approach.
>
> I did not think about this yet, but I agree with you.
I'll try to construct an example based on your algorithm.
Jeremias Maerki
Re: Creating combined element lists for a table row from cell element lists
Posted by Jeremias Maerki <de...@greenmail.ch>.
It looks like row spanning is not that difficult. What needs to be done
is to extend the meaning of "totalHeight" in Luca's algorithm for the
combined list. totalHeight will not only be the total height of a single
row, but of a row group. A row group in this context is the minimum
number of consecutive rows which contains all spanned grid units of its
cells. An example:
+----------+-------+----------+
| | | |
+----------+-------+----------+
| | |
| | |
| +-------+----------+
| | | |
| +-------+ |
| | | |
+----------+-------+ |
| | | |
+----------+-------+----------+
Here we'd have two such row groups, the first is equivalent to the first
row, the second contains rows 2 to 5. Note that we can't just sum up the
heights of the individual cells in the row group per column. We have to
add the space used by the cell borders (and optional cell spacing in
separate mode), too, because they are also elements that create steps in
the algorithm.
Handling stretch and shrink is still somewhat beyond me.
-----
A little goodie for those who want to see how the easiest case in Luca's
algorithm turns out:
Simplest example:
Table with one cell (three one-line blocks)
height = (3,3,3)
totalHeight = 3
Step1:
stepw = 1;
maxRemHeight = 2
penaltyHeight = 1 + 2 - 3 = 0;
boxHeight = 1 - 0 - 0 = 1
addedBoxHeight now 1
Step 2:
stepw = 1 + 1 = 2
maxRemHeight = 1
penaltyHeight = 2 + 1 - 3 = 0
boxHeight = 2 - 1 - 0 = 1
addedBoxHeight now 2
Step 3:
stepw = 2 + 1 = 3
maxRemHeight = 0
penaltyHeight = 3 + 0 - 3 = 0
boxHeight = 3 - 2 - 0 = 1
addedBoxHeight now 3
breaks:
1/2
2/1
3/0
box 1
penalty 0
box 1
penalty 0
box 1
(penalty 0)
On 29.03.2005 13:56:59 Luca Furini wrote:
> > A point I still have to think about for both approaches is how exactly
> > to handle row spanning, although I suspect it'll be easier for the first
> > approach.
>
> I did not think about this yet, but I agree with you.
Jeremias Maerki