[Xmlgraphics-fop Wiki] Update of "TableLayout/KnuthElementsForTables" by JeremiasMaerki

[Apache Wiki <wi...@apache.org>]

Dear Wiki user,

You have subscribed to a wiki page or wiki category on "Xmlgraphics-fop Wiki" for change notification.

The following page has been changed by JeremiasMaerki:
http://wiki.apache.org/xmlgraphics-fop/TableLayout/KnuthElementsForTables

The comment on the change is:
Documenting the Knuth element generation for tables

New page:
##language:en
#pragma section-numbers off

= Knuth element generation for tables =

== Overview ==

At the moment we see two fundamental approachs for generating Knuth elements for tables. Note: Some of the considerations made here can also be applied to lists.

=== 1. Combined element list ===

In this approach the individual element lists of each cell are combined to a single element list that can be used in page breaking. The approach is described in detail further down.

=== 2. Combined stretch boxes ===

In this approach for each cell a single box plus stretchable penalty is created to represent the cell as a whole. All the boxes for a row are combined to one which is used for page breaking. The approach is described here: [http://mail-archives.eu.apache.org/mod_mbox/xmlgraphics-fop-dev/200503.mbox/%3c20050322132704.9D77.DEV.JEREMIAS@greenmail.ch%3e link]

== Combined element list ==

=== Simple case ===

{{{
<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 we 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
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]
}}}

=== The next step ===

Let's modify the original example a bit:

{{{
<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.

The challenge was to come up with an algorithm to create the combined list for the more complicated case. 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)

=== The proposed algorithm ===

Luca Furini came up with the following algorithm:

This could be the procedure that creates the combined elements, at least
when there is no stretch nor shrink; with this assumption, the resulting
sequence will contain only boxes and penalties.

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.

=== Handling the second example above ===

Using the example above, 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 length 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
}}}

=== Handling the easiest example ===

The easiest example would look like this us with the algorithm above:

{{{
Table with one cell (three one-line blocks)
height = (3,3,3) (each line has a height of 1 in this example)
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)
}}}

=== Handling row spanning with this approach ===

The meaning of "totalHeight" in the above algorithm needs to be extended 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's the delimiter between two row groups
|          |                  |
|          |                  |
|          +-------+----------+
|          |       |          |
|          +-------+          |
|          |       |          |
+----------+-------+          |
|          |       |          |
+----------+-------+----------+
}}}

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.