Alice goes floatingFrank Mittelbach
TUG 2016, Toronto, Canada, July 2016

/Alice goes floatingThis morning I like to take you on a journey to Alice in Wonderland to see how she isfloating among all her pictures.
So sit back, relax and enjoy!
/Alice goes floating/Typesetting Alice

Like the rabbit we need to be concerned about time passed so that shows up on theslides as well.
/Alice goes floating/Typesetting Alice/Download Alice in Wonderland f...

In preparation I downloaded the original text from the Gutenberg Project,- did some minimal adjustments so that we a few headings,- changed „underscores“ indicating emphasis- and made sure that „poems“ and similar items are treated as unbreakable blocks
I also hunted up the original drawings and placed them in their appropriate places inthe source/Alice goes floating/Typesetting Alice/General settings

For typesetting I chose fairly standard settings with some slightly more rigid values, forexample,- widows and orphans are totally forbidden- and there is no extra flexibility in vertical spacing between paragraphs
Another characteristic is that heading at the top of a columns are encouraged\textheight = 550.0pt (46 lines a 12pt)\textwidth = 229.5pt (approx 50-55 characters per line)\clubpenalty= 10000 % no orphans\widowpenalty = 10000 % no widows\parskip= 0pt% no paragraph separation flexibility\@beginparpenalty = 9999 % strongly discourage breaks in front of% „verse“ and similar environments\@secpenalty= -9000 % strongly encourage section breaks\tolerance= 4000% allow fairly loose paragraphs/Alice goes floating/Typesetting Alice/Run this through standard LaTe...

…

Typesetting
Alice
Rollup: 11 Minuten

Add \section* commands
Change _foo_ to \emph{foo}Download Alice in Wonderland from Project
Gutenberg and apply minimal text adaptions
2 Minuten

Force a few „poems“ etc. to be on a single page by
putting them into a box and hinting that a break
before would be bad (penalty 9999)

Add in all the drawings in their appropriate places

Two columns (46 lines) with \flushbottom

no widows or orphans no \parskip flexibility

General settings

favor headings on top of column

1 Minute

encourage „pre-text“ + display env. kept together

reasonably flexible \tolerance to allow for narrow columns

Run this through standard LaTeX we obtain …
3 Minuten

/Alice goes floating/Typesetting Alice/Run this through standard LaTe.../… a document with a bunch ofi...

Running this through standard LaTeX (with the above settings) we obtain a documentwith a bunch of issues:check out

phase0-stdlatex-with-floats.pdf/Alice goes floating/Typesetting Alice/Can we do better?

Can we do better?
/Alice goes floating/Typesetting Alice/Can we do better?/Yes, but …

The answer is „yes we can“ but there is a lot of manual labor involved —and I speak from experience having done that kind of work for a number of books andup with up to 30% manual pagination + rewriting/Alice goes floating/Typesetting Alice/Can we do better?/DemoShow life demo paginating Alice with strict settings (no \parskip flexibility,
no widows and orphans) but using global optimization.
/Alice goes floating/Typesetting Alice/Can we do better?/Demo/… an adjusted document

The result isphase4-strict-texflex-firstpagedrop.pdf/Alice goes floating/How?/First … some standard LaTeX ex...

First the results from some more sample documents this time without any floats.
All documents have been set in two columns with a width of 8 cm.
Each column could hold 46 lines of text and the paragraph requirements have been
fairly strict: no widows or orphans and only a small amount of flexibility (+1pt) for theparagraph separation.
This means that in each column one could gain a flexibility of up to 2 lines(but only when there are 8 or more paragraphs in the column and we accept a stretchof up to 3 times the nominal value which corresponds to a badness of 2700).
As it can be immediately seen, all documents show problematic page/column breaks(in the range of 4%-16%). If we remove the \parskip flexibility we will see up to 30%
bad breaks.

PDF… a document with a bunch of issues
DOCX

Can we do better?
5 Minuten

… it means a lot of manual labor to fix it

It’s an iterative process, thus time-consuming
Yes, but …
The source gets cluttered with formatting
instructions — not suitable for other formattings

How many hours of labor do you reckon?

… it means a lot of manual labor to fix it

It’s an iterative process, thus time-consuming
Yes, but …
The source gets cluttered with formatting
instructions — not suitable for other formattings

How many hours of labor do you reckon?

< 2 minutes

well, about 25 years thinking about it + half ayear development + 1 minute processing

Demo

PDF

… an adjusted document
DOCX

How?
Rollup: 16 Minuten

All examples are straight text without floats
First … some standard LaTeX
examples1 Minute

Standard LaTeX here means the „greedy“ algorithmwith small flexibility between paragraphs (\parskip)
and no widows and orphans

Alice in Wonderland
Call of the Wild
Grimm’s Fairy Tales
Pride and Prejudice

document
columns
72
78
236
316

paragraphs
total
833
340
1041
2127

vertical badness
good bad ugly/infinite
69
0
2+1
64
1
9+4
212
6
6+12
292
8
7+9

(4.1%)(16.6%)(7.6%)(5.1%)

/Alice goes floating/How?/Idea

The idea is the following: paragraph breaking and page breaking are fairly similar inthat- we have a similar about of breakpoints per line compared to breakpoints in acolumns- and the number of lines in a typical paragraph are not so much diﬀerent to thenumber of columns in a chapter
So let’s try to apply a suitably adapted version of the Knuth/Plass algorithm topagination?
(Do we need a recap how Knuth/Plass works?)/Alice goes floating/How?/Idea/A quick recap: how does the Kn.../Dynamic programming approach

Dynamic programming only works with certain type of problems that have the following
characteristics:- an optimal solution to the whole problem consists of optimal partial solutions
that is if we have a sub-optimal solution for, say the first 4 pages then it is not possiblethat this is part of the overall optimal solution- subproblems overlap, that is if we try to find the optimal solution we would resolve
the same subproblem many times

A typical column has a similar amount of breakpoints as a typical linewith hyphenation (roughly 45-55 compared 30) and a typical chapter
has not that many more pages than a typical paragraph has lines

Idea
6 Minuten

So applying Knuth/Plass (suitably changed) to pagination to achievea globally optimized document should be possible

A quick recap: how does the Knuth/Plass
algorithm work?

Dynamic programming approach
A quick recap: how does the Knuth/Plass
algorithm work?
High-level algorithm

Partial solutions of the optimal solution areitself optimal (optimality principle)
Requirements:
Subproblems overlap, i.e., the same subproblem
appears several times different partial solutions
Given:
Dynamic programming approach
Then:

Therefore:

Question:

Answer:

Partial solutions of the optimal solution areitself optimal (optimality principle)
Requirements:
Subproblems overlap, i.e., the same subproblem
appears several times different partial solutions
Given:
Dynamic programming approach
Then:

Therefore:

Question:

Answer:a breakpoint for a column + „some conditions“Partial solutions of the optimal solution areitself optimal (optimality principle)
Requirements:
Subproblems overlap, i.e., the same subproblem
appears several times different partial solutions
Given:

a breakpoint for a column + „some conditions“Then:choosing the best sequence of further breakpoints is independentof how we reached this breakpoint under „some conditions“Dynamic programming approach

Therefore:

Question:

Answer:

Partial solutions of the optimal solution areitself optimal (optimality principle)
Requirements:
Subproblems overlap, i.e., the same subproblem
appears several times different partial solutions
Given:

a breakpoint for a column + „some conditions“Then:choosing the best sequence of further breakpoints is independentof how we reached this breakpoint under „some conditions“Dynamic programming approach
we only need to remember the best way to end
column k at breakpoint b (under „some conditions“)
Therefore:
because it is not important through which way we reachedit, so we can drop inferior partial solutions at this point
Question:

Answer:Requirements:

Given:

a breakpoint for a column + „some conditions“Then:choosing the best sequence of further breakpoints is independentof how we reached this breakpoint under „some conditions“
we only need to remember the best way to end
column k at breakpoint b (under „some conditions“)

Dynamic programming approach
Therefore:

because it is not important through which way we reachedit, so we can drop inferior partial solutions at this point
Question:

Answer:What are the „some conditions“ above?

Requirements:

Given:

a breakpoint for a column + „some conditions“Then:choosing the best sequence of further breakpoints is independentof how we reached this breakpoint under „some conditions“
we only need to remember the best way to end
column k at breakpoint b (under „some conditions“)

Dynamic programming approach
Therefore:

because it is not important through which way we reachedit, so we can drop inferior partial solutions at this point
Question:

What are the „some conditions“ above?

Answer:Any condition that is needed to make the optimality
principle hold — i.e., independence of later subproblems
on earlier choices (we will see examples later)

/Alice goes floating/How?/Idea/A quick recap: how does the Kn.../High-level algorithm

So let’s give a very high-level overview of the algorithm applied to pagination …
We loop through all possible breakpoints in the document …
… and maintain a list of „active“ breakpoints representing the best way of ending somecolumn under some condition.
Initially this list will only contain a single entry representing the start of the document.
So: one active element initially … now … If
- we can form a column from any element in the active list to the current breakpointwith an acceptable quality then this becomes a candidate solution for the next column- out of the candidates we choose the best and add it to the active list
- if we have diﬀerent conditions, then we have to choose the best among all with thesame condition (so we may have to add several new elements to the active list)
Then we move to the next breakpoint.
(Two points here: we apply the optimality principle by only adding the „best“ candidate
and this is the part where the active list grows.)
Once an element of the active list is too far out to be able to form a column with thecurrent breakpoint then we remove that element from the active list.
(For example, if the we are looking at more and more breakpoints, there will come apoint when it is impossible to squeeze all the material from the start of the document tothis breakpoint into a single column. So then re remove the element representing thestart of the document. For all later breakpoints the situation would even be worse.)
Finally when we reach the end of the document we can construct the optimal solution
by simply moving backwards through the selections we made early to reach the bestsolution for the last column. (Requires some housekeeping, but otherwise is straightforward).
The interesting point here is that the algorithm runs in linear time if the active list isbounded by a constant, otherwise it runs in quadratic time (in the number ofbreakpoints)/Alice goes floating/How?/So we should be able to apply .../Standard LaTeX examples optimi...

If we apply globally optimized pagination we fail in nearly all cases because we run outof alternatives (i.e., the active list gets empty along the way).
TUG-table-std-LaTeX-examples-optimized.png

We loop through all
breakpoints …
If …
High-level algorithm
Once …

Finally …

… maintaining an „active list“ of breakpoints that represent
the best way to end some column under „some condition“.
We loop through all
breakpoints …
Initially this will only contain one element representing thestart of the document.
High-level algorithm
If …

Once …

Finally …

We loop through all
breakpoints …

… the current breakpoint can form a new column(many can’t) with any element in the active list, thenthis becomes a candidate solution for the next column.

If …
High-level algorithm

Out of all candidates at the current breakpoint
we choose the best (under „some conditions“)and add it to the active list (recording throughwhich active list element we reached it)

Optimality principle applied!

active list grows
Then we move to the next breakpoint

Once …

Finally …

We loop through all
breakpoints …
If …
High-level algorithm
Once …

Finally …

… an element in the active list is too far awayfrom the current breakpoint we remove it fromthe active list.
active list shrinks

We loop through all
breakpoints …
If …
High-level algorithm

Once …

Finally …

… when we arrive at the end of the document we use thebest candidate and move backwards through the recorded
active list elements that were used to reach it, to obtainthe fully optimized pagination.

Algorithm runs in O(c×n) with c being the
average length of the active list

If c ≠ O(1) i.e., not bounded by a constant,this means the algorithm runs in O(n²)

There is a big difference between paragraph and page breaking
as in contrast to paragraphs pages have little to no flexibility

So we should be able to apply Knuth/Plass
Or not?

So if you optimize a simple text document (such as Alice without
floats) you are most likely running out of options and get the aequivalent of „overfull lines“

2 MinutenStandard LaTeX examples optimized

Standard LaTeX examples optimized

document
columns blocks
Alice in Wonderland 72
base
–
6947
Call of the Wild 78
base
–
9148
Grimm’s Fairy Tales 236
base
–
27908
Pride and Prejudice 316
base 318 34645

active list
max average
37paragraphs
total
833

12
340

9

2
1041

22

4
2127

39

14

vertical badness
good bad ugly/infinite
69
0
2+1
no solution
64
1
9+4
no solution
212
6
6+12
no solution
292
8
7+9
318
–
–

/Alice goes floating/How?/So what now?

So what now?
Basically we have to find ways to introduce more flexibility on the page.
/Alice goes floating/How?/So what now?/Options

For this we have basically 4 options:- allow non-sequential ordering of textual elements
For most document types that is not an option as the order of presentation is essential
for the readers understanding. However, with journals or newsletters and similar types
reordering of independent „stories“ will introduce some extra flexibility.
- allow variations in column heights
A typical trick of the craft is running all columns of a double spread a line short or long.
- allow variations in the height of textual elements
It may be possible to format paragraphs to diﬀerent numbers of lines (without
sacrificing the quality) or to format tables and figures to diﬀerent heights(A variation of this is to change the content of textual elements —you have that option
if you are not only the typesetter but also the author)- include float placement in optimization
Placing floats onto diﬀerent columns/pages will change the column height that remains
for textual material and thus provides additional flexibility for pagination.

So what now?
7 Minuten

Introduce additional flexibility on the page

Options

Running spreads short orlong (briefly)

So what now?

Variation in textual
element height (briefly)

7 Minuten

Optimality principle
conditions:

Optimized examples

allow non-sequential ordering of textual elementsallow variations in column heights
Options
allow variations in the height of textual elements

include float placement in optimization

Running spreads short orlong (briefly)

Provide additional flexibility by running double
spreads one line long or short
A standard trick of the craftProvide additional flexibility by providing
different paragraph formattings if possible

Variation in textual
element height (briefly)

TeX’s \looseness is naive: value >0 will resultin a last line with one (partial) word
Resolution: massage the hlist and add higher
penalties near the end so that TeX will not likebreaking there, then try \looseness/Alice goes floating/How?/So what now?/Optimality principle condition...

So let’s see what this means for the extra conditions needed to make the optimality
principle work …
When all columns are the same (or all columns after a certain point) then we have no
extra conditions and the algorithm runs in linear time.
However, when the vary in general, then breakpoints must end the same column when
we choose among the candidates and this is the worst scenario that gives us quadratic
run-time.
When we run spreads short or long then the breakpoint must end the same column
on a spread and all columns have to use the same variation (long or short) unless wehave just started a new spread. In that case the algorithm still runs in linear time but
much slower as the active list will be 3 times the number of columns larger.
With variation in textual element height we do not have extra conditions for the
optimality principle but the number of breaks in material of roughly a column height will
be much higher so again the active list can get much larger (typical factor is between
10 and 50 without going into details here).
Finally, if floats are involved, the breakpoint ending a column must have exactly thesame floats placed up to this point. The complexity is not easy to determine, so weare not going to cover this here.
/Alice goes floating/How?/So what now?/Optimized examples

If we now take another look at our sample documents (without float) and apply theadditional flexibility options (spread, paragraph variations, and both combined) we’ll
see that global optimizing becomes possible for all documents (with the exception of
Carroll it is even enough to apply only one method).
TUG-table-optimized-extended.png/Alice goes floating/Adding floats

So let’s add floats (and hopefully the Mad Hatter will help us) …

We are at some breakpoint in the document …

column heights are all the same

column heights vary (generally)
Optimality principle
conditions:spreads run short/long

variations in textual
element heightfloats involvedWe are at some breakpoint in the document …

column heights are all the same

column heights vary (generally)
Optimality principle
conditions:spreads run short/long

variations in textual
element heightfloats involved

Algorithm runs in O(n)no extra condition

We are at some breakpoint in the document …
Algorithm runs in O(n²)
column heights are all the same

column heights vary (generally)
Optimality principle
conditions:spreads run short/long

variations in textual
element heightfloats involved

breakpoint must end the same column

We are at some breakpoint in the document …

column heights are all the same

column heights vary (generally)

breakpoint must end thesame column on the spread
Optimality principle
conditions:spreads run short/long

variations in textual
element heightfloats involved

column must have same
variation as others (unless it
is the first column of a
spread)Algorithm runs in O(c×n) withc = 3 × cols compared to thebase algorithmWe are at some breakpoint in the document …

column heights are all the same

column heights vary (generally)
Optimality principle
conditions:

Algorithm runs in O(c×n) with approx
10 < c < 50 compared to the basealgorithm

spreads run short/long

variations in textual
element heightfloats involved

no extra condition, but the number of possible
breakpoints per column is much higher and the„distance“ between any two breakpoints dependon the variations chosen along the wayWe are at some breakpoint in the document …

column heights are all the same

column heights vary (generally)
Optimality principle
conditions:spreads run short/long

variations in textual
element heightfloats involved

Algorithm runs in O(?)

if the breakpoint ends a spread then the same
floats must have been placed up to this point

we cover this later

Optimized examples

document
columns blocks
Alice in Wonderland 72
base
–
6947
+ spread–6947+ variations–
9498+ variations, spread 70
9498
Call of the Wild 78
base
–
9148
+ spread 78
9148+ variations 78
14970+ variations, spread 78
14970
Grimm’s Fairy Tales 236
base
–
27908
+ spread 234 27908+ variations 238 59111+ variations, spread 236 59111
Pride and Prejudice 316
base 318 34645+ spread 316 34645+ variations 320 56861+ variations, spread 316 56861

active list
max average
37
432
598
7076

12
122
54
488

9
263
263
3156

2
134
67
704

paragraphs
total variable
833

available looseness-1/0 -1/1 -1/2 0/1 0/2

111

6

15

0

89

1

139

11

3

0

124 1

441

10

50

21 318 42

483

10

51

6

340

1041
22
485
437
5532

4
319
90
1030

39
486
633
7596

14
347
70
837

2127

397 19vertical badness
good bad
ugly
69
0
2+1
no solution
no solution
73
1
–
71
1
–
64
1
9+4
no solution
78
–
–
78
–
–
78
–
–
212
6
6+12
no solution
234
–
–
238
–
–
236
–
–
292
8
7+9
318
–
–
318
–
–
320
–
–
316
–
–

Adding floats
Rollup: 16 Minuten

/Alice goes floating/Adding floats/Basic requirements

In most documents float placement needs to obey certain rules, e.g.,- sequential order of floats- placement after (or at least visible from) the main call-out
While the above rules usually have to be enforced, the requirement that floats should
be visible from their call-out is more a „wish“, as technically this is often simply
impossible to guarantee for all floats.
With such rules in force there are still many possible placements that need to be
judged according to some quality measurement. So one important question to ask is:what are good quality measures that distinguish diﬀerent placements?
/Alice goes floating/Adding floats/Issues

Diﬀerent float placements add flexibility to the pagination process as they change thecolumn heights available for text.
However, this also means that (nearly) all placements need to be evaluated separately
and that candidate solutions can only be collapsed if the same set of floats has beentypeset at a particular breakpoint.
/Alice goes floating/Adding floats/Issues/With different placement areas...

4 columns top + bottom (no span) = 9 areas#trials = (n+ m)! / ( n! m! )So if we have one additional float we increase by a factor ofn=3 m=9n=4 m=9
n= 5
n=6
n=7
n=8

(n+1+m) / (n+1)-> trials = 220-> trials = 715-> trials = 2002-> trials = 5005-> trials = 11404-> trials = 24310/Alice goes floating/Adding floats/Pruning approaches

It is therefore important to identify inferior placements early on to ensure that thealgorithm performs in acceptable time.
At the same time it is necessary to keep enough candidate placements to ensure thatthe algorithm does not run out of options.

Floats are placed in sequential order(at least within each float class)

Floats are not placed before their main call-out(or are at least visible from there)
Basic requirements
2 Minuten

Wish: Floats are visible from their main call-out(or at least close by)What are good ways to measure the quality of a placement?

We count the number of page turns necessary to see
floats from their call-out and add demerits for each turn
Main approach:
Quality measures

Important: such demerits are added
for each spread the float is not seen

3 Minuten

One could think of applying weights to different
placements (layouts) involving the same floats

linear cost, but does not require to
remember where the call-out wasAs float placement changes column height, all (or nearlyall) different placements need to be evaluated separately
Issues3 Minuten

With different placement areas (top, bottom, …) the
number of possible placements grows very fast

By this factor the active list grows!

If we do not drop infeasible placements fast, thenthe running time of the algorithm will be very slow
If, on the other hand, we drop too many, we
may not find any solution at all
Pruning approaches
4 Minuten

Different situations will require different approaches

Examples:Conclusion

Perhaps start with rigorous settings andrelax if we run out of placement options

/Alice goes floating/Adding floats/Pruning approaches/Examples:One of the problems in this area is that for all pruning techniques one can find counterexamples where they should not be applied.

/Alice goes floating/Adding floats/Pruning approaches/Conclusion

Conclusion: this is definitely an area that needs further research!
/Alice goes floating/Adding floats/Interfaces

Interfaces implemented in the current algorithm:- spread(s) setup
Defines where on the spread floats can be placed, how many floats are allowed in
total, and the number/order and initial height of individual columns.
- float area(s) setup
Number of floats in an area, eﬀect on columns if float is placed and eﬀect on otherareas if float a float is added (e.g., other areas may be forbidden to receive floats or
floats of a certain type).
- call-out constraints
Restricting floats to come after the call-out, not on an earlier column, not on an earlier
page or not on an earlier spread.
- manual placement options
Possibility to require a float to appear on a certain spread or in a certain area or both.
Possible, but not implemented extension would be to allow several such options inparallel.
/Alice goes floating/The pagination framework/General approach

The pagination framework implemented by the author is based on the LuaTeX engine.
It can be directly used with any TeX distribution that provides this engine. It is largely
transparent to LaTeX so that all/most packages and extensions can be used with it,
without adjustment. It does however, require the use of LuaTeX to interface with innerprocessing of the TeX engine.
It is a framework as adjustments and extensions to the algorithm can be easily
integrated. It consists of four major phases.

Do not allow too many deferred floats

There should not be many deferred floats if
previous columns have no floats allocatedBut documents may have
many call-outs close by
But only if the floats could haveplaced there (diﬃcult to check)

Examples:A float was deferred for too long…

This creates dependencies between
subproblems, thus violate the optimality principle,
so that is not easy to implement correctlyIf we do not drop infeasible placements fast, thenthe running time of the algorithm will be very slow
If, on the other hand, we drop too many, we
may not find any solution at all
Pruning approaches
4 Minuten

Different situations will require different approaches

Examples:Conclusion

Further research needed!

Perhaps start with rigorous settings andrelax if we run out of placement options

Spread(s) setup

Float area(s) setup
Interfaces
4 Minuten

call-out contraints

manual placement options

very experimental

how many columns

initial height of each column (can vary)
Spread(s) setup
areas available on this spread

how many floats in totals allowednumber of floats that are allowed

Float area(s) setup

effect on columns (if any) if float is added

effect on other areas if float is addedspreadfloat can go anywhere on the spread with the call-out

page

float can go anywhere on the page with the call-out

columnstandard LaTeX behavior

after

flafter package behavior

call-out contraintsrequire a float on a certain spread (or spreads?)

manual placement options

require a float in a certain area (or areas?)both of the above

very experimental

The pagination
framework
3 Minuten

Use LuaTeX to interface with the TeX engine

General approach

Implement the pagination algorithm outside of
TeX, using Lua as the programming engine
Consequence: the framework can be useddirectly with most modern TeX distributions

/Alice goes floating/The pagination framework/phase1

The document, which consists of standard TEX files, is processed by a TEX engine
without any modification
until all implicit content (e.g., table of content, bibliography, etc.) is generated and all
cross-references are resolved.
The cross-references are not necessarily final (as the final pagination will be
determined later) but this way they have hopefully the same space characteristics.
If that assumption does not hold, it is likely that you end up with an „impossible
document“ that can not be processed with a globally optimizing pagination approach!

phase1

Task: Initially prepare the document

/Alice goes floating/The pagination framework/phase2

The engine is modified to interact with TEX’s way of filling the main vertical list (fromwhich, in an asynchronous way, TEX later cuts column material for pagination).
In particular, whenever TEX is ready to move new vertical material to the main verticallist this material is intercepted and analyzed. Information about each block (verticalsize, depth, stretchability if any and penalty of a breakpoint) is then gathered andwritten out to an external file. If possible, data is accumulated, e.g., several objects in a
row without any possibility for breaking them up are written out as a single data point
to reduce later processing.
The modification is also able to interpret special flags (implemented as new types of“whatsit nodes” in TEX engine lingo) that can signal the start/end or switch of an
explicit variation in the input source. This information is then used to structure thecorresponding data in the output file for later processing.
The second modification to the engine is to intercept the generation of paragraphs
targeted for the main galley prior to TEX applying line breaking:•For each horizontal list that is passed to the line-breaking algorithm theframework algorithm then determines the number of acceptable variations in“looseness” within the specified parameter settings.
•
For each possible variation it then does a paragraph breaking trial todetermine the exact sequence of lines, vertical spaces and associated penalties undera specific “looseness” value.
•
The results of each trial is externally recorded together with the associated“looseness” value of the variation.
•
Finally, instead of adding a vertical list representing the paragraph to the main
vertical list, a single special node is passed so that the paragraph material is notcollected again by the first modification described above.
As the result of this phase the external file will hold an abstraction of the document
galley material including marked up variations for each paragraph.

/Alice goes floating/The pagination framework/phase 2b

This phase is a sub-phase of phase 2 (could be done in one go) and provides the callout positions within the symbolic galley representation as a separate list for fasterprocessing during gloabl optimization.

phase2

Task: Generate a symbolic representationof all material subject to pagination

phase 2b

Task: Produce a float callout list

/Alice goes floating/The pagination framework/phase3

The result of phase 2 and 2b is used as input to a global optimizing algorithm modeled
after the Knuth/Plass algorithm for line breaking that uses dynamic programming todetermine an optimal sequence of page/ column breaks throughout the whole
document. Com- pared to the line-breaking algorithm this page-breaking algorithm
provides the following additional features:•Support for variations within the input: This is used to automatically manage
variant break sequences resulting from diﬀerent paragraph breakings calculated inphase 2, but could also be used to support, for example, variations of figures in
diﬀerent size or similar applications.
•Support for shortening or lengthening the vertical size of double spreads toenable better columns/ page breaks across the whole document.
•
Global optimization is guided by parameters that allow a document designer
to balance the importance of individual aspects (e.g., avoiding widows againstchanging the page length or using sub- optimal paragraphs) against each other.
The result of this phase will be a sequence of optimal page break positions within the
input together with length information for all pages/columns for which it applies. Also
recorded is which of the variants have been chosen when selecting the optimal
sequence.

phase3

Task: Determine the optimal pagination

/Alice goes floating/The pagination framework/phase4This phase again uses a modified TEX engine that is capable of interpreting and using
the results of the previous phases. For this it hooks into the same places as themodifications in phase 2, but this time applying diﬀerent actions:- To begin with, the vertical target size for gathering a complete column will be
artificially set to the largest legal dimension so that by itself the TEX algorithm will not
mistakenly break up the galley at an unwanted place due to some unusual combinationof data.
- Whenever TEX gets ready to apply line breaking to paragraph material for the main
vertical list the modification looks up with which “looseness” this paragraph should betypeset and adjusts the necessary parameters so that TEX generates the lines
corresponding to the variation selected in the optimal break sequence for the whole
document determined in pagination phase 3.
- While TEX is moving objects to the main vertical list the algorithm keeps track of thegalley blocks seen so far and when it is time for a column break according to the
optimal solution it will explicitly place a suitable forcing penalty onto the main verticallist so that TEX is guaranteed to use this place to end the current column or page.
Again as a safety measure other penalties seen at this point that should not result in acolumn break will be either dropped or otherwise rendered harmless so that TEX’s
internal (greedy) page-breaking algorithm is not misinterpreting them as a“best break” by mistake.
- Finally, whenever TEX has finished a column (due to the fact that we have added an
explicit penalty in the previous step) we will arrange for the correct target dimensions
for the current column according to the data from pagination phase 3. This is done
immediately after TEX has decided what part of the galley it will pack up for use in its“output routine” (which is a set of TEX macros) but before this routine is actually called.
The result is a paginated document with optimized column breaks across the whole
document.
It is however not necessarily a correctly formatted document (in case generated text
depends on the final pagination) as explained earlier.

phase4

Task: Produce the final document

/Alice goes floating/The „emergency stretch“ idea

The line-breaking algorithm of TeX implements the idea of „emergency stretch“ if thealgorithm runs out of alternatives to optimize.
A similar approach can be used when globally optimizing the pagination.
As a result more pagination options are bing considered and those that originally had„infinite“ badness are now becoming measurable and comparable.
However in contrast to line breaking, pagination often has to deal with columns withlittle or no flexibility whatsoever. If there is no flexibility then the approach is invalid andwould result in solutions that would look horrendous.
It is therefore important to only apply this method with columns that do have at least
some initial flexibility. In that case, all experiments so far have shown good results.
/Alice goes floating/Examples

On this slide we show the performance and results produced by the algorithm when
paginating Alice in Wonderland using diﬀerent parameter settings and more or lessflexibility added through diﬀerent options provided by the algorithm.
/Alice goes floating/Open issues

Current state of aﬀairs …
/Alice goes floating/Open issues/code

There are a number of issues with the current code, e.g., it is still based on LuaTeX 0.8
and will not run without adjustments on the current version of the engine. (Basically,
during the implementation a number of problems have been identified in the engine
and those have since then been corrected — however, the code still implements
workarounds based on the earlier interfaces)
Footnotes are somewhat similar to floats and are currently not fully supported (inparticular the ability to split footnotes across columns).
The pruning logic for float placements is still in its infancy and needs further thoughts.
And of course there are most likely other bugs (some of which are known, others
probably not).
/Alice goes floating/Open issues/clumsy/bad interfaces

All customization interfaces so far are really just prove of concept implementations andneed to be provided in a diﬀerent ways for end users.

The „emergency
stretch“ idea
3 Minuten

… restart assuming an additionalamount of (non-existent) flexibility
available per column

Idea: If global optimization
runs out of alternatives tochoose from …

Result:The „emergency
stretch“ idea
Conclusion:

3 Minuten

… restart assuming an additionalamount of (non-existent) flexibility
available per column

Idea: If global optimization
runs out of alternatives tochoose from …

Formerly „infeasible“ column breaks become
available as options
Those hiding behind „infinite“ badness now
become measurable

Result:The „emergency
stretch“ idea
3 Minuten

No good on columns that have no
flexibility whatsoever!
Conclusion:

… restart assuming an additionalamount of (non-existent) flexibility
available per column

Idea: If global optimization
runs out of alternatives tochoose from …

Result:Don’t apply this on columns without flexibility
The „emergency
stretch“ idea
On all others proceed with fingers crossed

In most cases this will give you reasonable results!

Conclusion:

3 Minuten

Examples
6 Minuten\parskip = 0pt

strictglobal optimization (no extra flexibility)

some minor spacing issues

8 seconds processing

Results:\parskip = 0pt plus 1pt

flexible

global optimization (no extra flexibility)

Example 1

Example 2

no spacing issues
8 seconds processing

Results:

but perhaps the float placements could be better\parskip = 0pt plus 1pt

flexible

Manually adjusting float
placements

Examplesglobal optimization (no extra flexibility)

Example 3

everything is fine9 seconds processing

Results:

but adjusting floats is likely to be an iterative process\parskip = 0pt

strictglobal optimization (with spread + para variation extension)

everything fine48 seconds processing

Results:

Example 4

6 Minuten

code

clumsy/bad interfaces
Open issues
3 Minutenlua code currently based on 0.80

footnotes not properly handled

pruning logic for float placements needs improving
makes generated text like crossreferences likely to be wrong

phase1 currently fully drops floats (as theirplacement interferes with galley block construction)some bugs lurking in endgame handlingcodespread + area setup
clumsy/bad interfaces
manual float placement

/Alice goes floating/Conclusions

In conclusion, the work so far looks fairly promising, but to turn this into a generally
usable product a lot of work is still necessary.

Conclusions
2 Minuten

promising (imho)

still a lot of work to do

Thanks …

Conclusions
2 Minuten

Thanks …

… to the LuaTeX team for providing themethods that made this possible… and to you for listening for so long

Alice goes floatingFrank Mittelbach
TUG 2016, Toronto, Canada, July 2016