The stonyroad tocomplex pagelayoutFrank
Mittelbach
The Ask

The stony road to complex page layout(and its road blocks)

Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

2013-10-23

The stonyroad tocomplex pagelayoutFrank
Mittelbach
The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

The old road
Hakone 2009

The stonyroad tocomplex pagelayoutTranslated . . .
When typesetting complex layouts

Frank
Mittelbach
The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

is not fully up to the task(unless we restrict the scenario)

The stonyroad tocomplex pagelayoutFrank
Mittelbach
The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

InsteadThe stonyroad tocomplex pagelayoutisFrank
Mittelbach
The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

needed?

Moving on . . .
The stonyroad tocomplex pagelayoutFrank
Mittelbach

1
2
3
4

The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

5

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

6

The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary
Typesetting Challenges
Balancing
Right to left
Spaces & penalties
Summary

The Ask
The stonyroad tocomplex pagelayoutFrank
Mittelbach
The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

The Ask
The stonyroad tocomplex pagelayoutFrank
Mittelbach
The Ask

For:

Some History

multiple columns

TEX’s Model

text balancing

User Wishlist

float positioning

Balancing & Floats
Columns
Column dependency

grid typesetting

Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary. . . and much moreConflicting goals
The stonyroad tocomplex pagelayoutVarying the number of columns on a pageFrank
Mittelbach

Balancing
The Ask
Some History
TEX’s Model
User Wishlist

Automatic float placement

Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges

Grid typesetting

Balancing
Right to left
Spaces & penalties

Summary

Do everything automaticallyConflicting goals
The stonyroad tocomplex pagelayoutFrank
Mittelbach

Varying the number of columns on a page
what happens with footnotes?
what happens with floats?

Balancing
The Ask
Some History
TEX’s Model
User Wishlist

Automatic float placement

Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges

Grid typesetting

Balancing
Right to left
Spaces & penalties

Summary

Do everything automaticallyConflicting goals
The stonyroad tocomplex pagelayoutFrank
Mittelbach

Varying the number of columns on a page
what happens with footnotes?
what happens with floats?

Balancing
The Ask
Some History

but have explicit columns breaks obeyed
but change typesetting based on columns

TEX’s Model
User Wishlist

Automatic float placement

Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges

Grid typesetting

Balancing
Right to left
Spaces & penalties

Summary

Do everything automaticallyConflicting goals
The stonyroad tocomplex pagelayoutFrank
Mittelbach

Varying the number of columns on a page
what happens with footnotes?
what happens with floats?

Balancing
The Ask
Some History

but have explicit columns breaks obeyed
but change typesetting based on columns

TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border

Automatic float placement
into and across columns
maintaining relationships to call-outs
and produce pleasing (and compact) layout

Wishlist summary

Typesetting
Challenges

Grid typesetting

Balancing
Right to left
Spaces & penalties

Summary

Do everything automaticallyConflicting goals
The stonyroad tocomplex pagelayoutFrank
Mittelbach

Varying the number of columns on a page
what happens with footnotes?
what happens with floats?

Balancing
The Ask
Some History

but have explicit columns breaks obeyed
but change typesetting based on columns

TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border

Automatic float placement
into and across columns
maintaining relationships to call-outs
and produce pleasing (and compact) layout

Wishlist summary

Typesetting
Challenges
Balancing

Grid typesetting
but use elements of varying and unknown heights

Right to left
Spaces & penalties

Summary

Do everything automaticallyConflicting goals
The stonyroad tocomplex pagelayoutFrank
Mittelbach

Varying the number of columns on a page
what happens with footnotes?
what happens with floats?

Balancing
The Ask
Some History

but have explicit columns breaks obeyed
but change typesetting based on columns

TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border

Automatic float placement
into and across columns
maintaining relationships to call-outs
and produce pleasing (and compact) layout

Wishlist summary

Typesetting
Challenges
Balancing

Grid typesetting
but use elements of varying and unknown heights

Right to left
Spaces & penalties

Summary

Do everything automaticallybut guess exceptions (without them being marked up)

Moving on . . .
The stonyroad tocomplex pagelayoutFrank
Mittelbach

1
2
3
4

The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

5

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

6

The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary
Typesetting Challenges
Balancing
Right to left
Spaces & penalties
Summary

Brief history on multi-column attempts in LATEXThe stonyroad tocomplex pagelayoutFrank
Mittelbach

1982 TEXbook describes code for index balancing
1988 multicol version 1.0a

The Ask
Some History

1993 balancing by Patrick Daly

TEX’s Model
User Wishlist

1999 ltxgrid by Arthur Ogawa

Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border

1999-2000 Prototype of xor

Wishlist summary

Typesetting
Challenges

2007 flowfram by Nicola Talbot

Balancing
Right to left
Spaces & penalties

Summary

2011 adjmulticol by Boris Veytsman

Brief history on multi-column attempts in LATEXThe stonyroad tocomplex pagelayoutFrank
Mittelbach

1982 TEXbook describes code for index balancing— specific use case only

1988 multicol version 1.0a — multiple columns,
restriction on floats and footnotes

The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns

1993 balancing by Patrick Daly
— manual adjustment needed1999 ltxgrid by Arthur Ogawa— two-column, potential loss of material

Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

1999-2000 Prototype of xor — general float handling, balancing,grids, but no production version
2007 flowfram by Nicola Talbot — general text blocks,
no balancing, limited float support

2011 adjmulticol by Boris Veytsman— fixing some multicol limitations

Brief history on multi-column attempts in LATEXThe stonyroad tocomplex pagelayoutFrank
Mittelbach

Or in summary:

The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns

30 years have passed since TEX82
Only a handful attempts
No general solution

Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

Why?

Moving on . . .
The stonyroad tocomplex pagelayoutFrank
Mittelbach

1
2
3
4

The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

5

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

6

The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary
Typesetting Challenges
Balancing
Right to left
Spaces & penalties
Summary

The TEX model
The stonyroad tocomplex pagelayoutFrank
Mittelbach
The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats

We probably don’t have the extra computer resources
for 100 people to typeset 40 or 50 page documents
during the daytime.

Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Donald Knuth, Stanford 1981

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

http://www.youtube.com/playlist?list=PL0AB2986EB62BB5FE

The TEX model
Design basics
The stonyroad tocomplex pagelayoutFrank
Mittelbach

TEX was designed for documents witha single column
left-to-right typesetting

The Ask

display mathematics (irregular baselines)

Some History

offering paragraph optimization

TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

The TEX model
Design basics
The stonyroad tocomplex pagelayoutFrank
Mittelbach

TEX was designed for documents witha single column
left-to-right typesetting

The Ask

display mathematics (irregular baselines)

Some History

offering paragraph optimization

TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency

The processing/typesetting is
unidirectional: paragraph → galley → page

Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

with some limited multi-stream functionality(e.g., footnotes)

The TEX model
Design basics
The stonyroad tocomplex pagelayoutFrank
Mittelbach

TEX was designed for documents witha single column
left-to-right typesetting

The Ask

display mathematics (irregular baselines)

Some History

offering paragraph optimization

TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency

The processing/typesetting is
unidirectional: paragraph → galley → page

Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges

with some limited multi-stream functionality(e.g., footnotes)

Balancing
Right to left
Spaces & penalties

Summary

Paragraph shapes are
specified by lines — not by vertical relationships

The TEX model
Consequences
The stonyroad tocomplex pagelayoutFrank
Mittelbach
The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

Processing freezes the horizontal widthwith no way to recover parts of an already typeset paragraphinstead, unset paragraph material needs to be kept
issues with reprocessing on macro level

The TEX model
Consequences
The stonyroad tocomplex pagelayoutFrank
Mittelbach

Processing freezes the horizontal widthwith no way to recover parts of an already typeset paragraphinstead, unset paragraph material needs to be kept
issues with reprocessing on macro level

The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

Size changes need to be modeled as paragraph shapes
conceptually wrong
precompiled paragraph shapes will give “incorrect results” iflines contain large objects

The TEX model
Consequences
The stonyroad tocomplex pagelayoutFrank
Mittelbach

Processing freezes the horizontal widthwith no way to recover parts of an already typeset paragraphinstead, unset paragraph material needs to be kept
issues with reprocessing on macro level

The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns

Size changes need to be modeled as paragraph shapes
conceptually wrong
precompiled paragraph shapes will give “incorrect results” iflines contain large objects

Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

No builtin concept for grids
the glue concept is effectively an orthogonal approach

The TEX model
Consequences
The stonyroad tocomplex pagelayoutFrank
Mittelbach

Processing freezes the horizontal widthwith no way to recover parts of an already typeset paragraphinstead, unset paragraph material needs to be kept
issues with reprocessing on macro level

The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns

Size changes need to be modeled as paragraph shapes
conceptually wrong
precompiled paragraph shapes will give “incorrect results” iflines contain large objects

Column dependency
Rules & Backgrounds
At the border
Wishlist summary

No builtin concept for grids
the glue concept is effectively an orthogonal approach

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

Relationship between different streams is only maintained
rudimentarily
loss of relationships inside the OR

Moving on . . .
The stonyroad tocomplex pagelayoutFrank
Mittelbach

1
2
3
4

The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

5

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

6

The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary
Typesetting Challenges
Balancing
Right to left
Spaces & penalties
SummaryFrom the user wishlist . . .
Balancing or not . . .
The stonyroad tocomplex pagelayoutFrank
Mittelbach

How do I fill the first column first?
How do I avoid stretching in the last column?

The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

How do I prevent balancing of short texts?

From the user wishlist . . .
Balancing or not . . .
The stonyroad tocomplex pagelayoutFrank
Mittelbach
The Ask

How do I fill the first column first?
— realized early on as multicols* environment

How do I avoid stretching in the last column?
— parameters, e.g., \finalcolumnbadness introduced

Some History

How do I prevent balancing of short texts?

TEX’s Model— tricky, what are good options?

User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

SummaryFrom the user wishlist . . .
Balancing or not . . .
The stonyroad tocomplex pagelayoutFrank
Mittelbach
The Ask

How do I fill the first column first?
— realized early on as multicols* environment

How do I avoid stretching in the last column?
— parameters, e.g., \finalcolumnbadness introduced

Some History

How do I prevent balancing of short texts?

TEX’s Model— tricky, what are good options?

User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing

Short text fragments
do not balance nicely.

How should this material be distributed

over the columns?

. . . or . . .
Short text fragments
do not balance nicely.
How should this ma-

terial be distributed
over the columns?

Right to left
Spaces & penalties

Summary— manual solution with unbalance— parameter for minmal number of lines (to be added)

From the user wishlist . . .
Floats
The stonyroad tocomplex pagelayoutFrank
Mittelbach

Can I have my floats automatically placed withmulticols?

The Ask
Some History
TEX’s Model

Can I have floats that span some of the columns?

User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

Why are full width floats never placed on the current page?

From the user wishlist . . .
Floats
The stonyroad tocomplex pagelayoutFrank
Mittelbach
The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border

Can I have my floats automatically placed withmulticols?
— not with the current approach used;balancing will throw off all placement calculations

Can I have floats that span some of the columns?
— not with the current approach used;— solutions could be (fairly easily) provided ifbalancing is restrictedfloats are manually placed by the user

Wishlist summary

Typesetting
Challenges

Why are full width floats never placed on the current page?

Balancing— to avoid backtracking and recalculations;

Right to left
Spaces & penalties

Summary— these days this could be improved

Side note
Float placement costs
The stonyroad tocomplex pagelayoutFrank
Mittelbach
The Askbruteforce(a, n) = (a + 1)ntrials(a, n) =n+aa

for a areas and n floats(1)(n + a)!
n!a!

(2)

!

=

Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

with a ≥ c(c + 1) for c columns on a page.
An additional float waiting increases the trials by n+a+1
n+1

Side note
Float placement costs
The stonyroad tocomplex pagelayoutFrank
Mittelbach
The Askbruteforce(a, n) = (a + 1)ntrials(a, n) =n+aa

for a areas and n floats(1)(n + a)!
n!a!

(2)

!

=

Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columnswith a ≥ c(c + 1) for c columns on a page.
An additional float waiting increases the trials by n+a+1
n+1

Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges

trials(8, 12) = 125.970

trials(10, 12) = 646.646

trials(6, 24) = 593.775

trials(8, 24) = 10.518.299

trials(3, 24) = 2.300

Balancing
Right to left
Spaces & penalties

SummaryThis is the search space for one page, no global optimization!

From the user wishlist . . .
Columns
The stonyroad tocomplex pagelayoutFrank
Mittelbach

Can I have columns of different width?
Can I have different number of columns per page?

The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

Can I have arbitrarily shaped columns?

From the user wishlist . . .
Columns
The stonyroad tocomplex pagelayout— not if the column content is automatically determinedFrank
Mittelbach

Can I have different number of columns per page?

The Ask
Some History

Can I have columns of different width?

— only if the page break is manually chosen

Can I have arbitrarily shaped columns?

TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary— not really in any generality

Reiterate . . .
Paragraph breaking
The stonyroad tocomplex pagelayoutFrank
Mittelbach

The situation:
Paragraphs are broken into lines as a whole
Formatted material cannot be reformatted (in general)

The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

SummaryReiterate . . .
Paragraph breaking
The stonyroad tocomplex pagelayoutFrank
Mittelbach

The situation:
Paragraphs are broken into lines as a whole
Formatted material cannot be reformatted (in general)

The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

The consequences:
For reformatting unformatted (macro level) material needs
to be captured and used
Any shape requirement (e.g., variation on horizontal widtha page boundery) has to be anticipated beforehand andtranslated into a suitable \parshape
However, TEX is not able to account for vertical variation,
except by trial and error

From the user wishlist . . .
Columns (cont.)
The stonyroad tocomplex pagelayoutCan I force multicols to skip to the next column if there
are only a few lines left?

Frank
Mittelbach
The AskCan I have (fixed) content at the top of each column?

Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns

Can I have variable content added the top of each column,e.g., a continuation line in an index?

Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

Can I get my table broken across several columns/pages(with table headers repeated)?

From the user wishlist . . .
Columns (cont.)
The stonyroad tocomplex pagelayoutFrank
Mittelbach

Can I force multicols to skip to the next column if there
are only a few lines left?
— yes, using the \vfilneg approach

The AskCan I have (fixed) content at the top of each column?

Some History— yes, fairly easily (no user interface provided)

TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds

Can I have variable content added the top of each column,e.g., a continuation line in an index?
— yes, implemented for the LATEX Companion index

At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

Can I get my table broken across several columns/pages(with table headers repeated)?
— partly; without table headers multicols and longtable
could be easily married— hard, with table headings or balancing requirements

From the user wishlist . . .
Act depending on current column
The stonyroad tocomplex pagelayoutFrank
Mittelbach
The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

Can I find out if some environment is typeset fully within asingle column?
Can I switch the line-numbering if the column changes?
Can I produce pull-quotes sticking into the margin on
outside columns?
Can I force multicols to start the next column only if in
the first column, but not if in the second column?

From the user wishlist . . .
Act depending on current column
The stonyroad tocomplex pagelayoutFrank
Mittelbach
The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats

Can I find out if some environment is typeset fully within asingle column?
Can I switch the line-numbering if the column changes?
Can I produce pull-quotes sticking into the margin on
outside columns?
Can I force multicols to start the next column only if in
the first column, but not if in the second column?

Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary— yes to all; it is possible to gather the necessary information witha two-pass algorithm and use it to provide typesetting variations

From the user wishlist . . .
Act depending on current column
The stonyroad tocomplex pagelayoutFrank
Mittelbach
The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats

Can I find out if some environment is typeset fully within asingle column?
Can I switch the line-numbering if the column changes?
Can I produce pull-quotes sticking into the margin on
outside columns?
Can I force multicols to start the next column only if in
the first column, but not if in the second column?

Columns
Column dependency
Rules & Backgrounds
At the border— yes to all; it is possible to gather the necessary information witha two-pass algorithm and use it to provide typesetting variations

Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary— if the typesetting significantly changes the column structure,
more passes may be necessary— worst case scenario may be an impossible document, i.e., adocument that alternates between two or more states

From the user wishlist . . .
Rules
The stonyroad tocomplex pagelayoutFrank
Mittelbach
The AskCan I have the column rules colored?
Can I have rules at the outside of multicols?
Can I have a rule just between the 4th and 5th column?

Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

Can I (arbitrarily) customize the column rules?

From the user wishlist . . .
Rules
The stonyroad tocomplex pagelayoutFrank
Mittelbach
The AskCan I have the column rules colored?
— yes, through \columnseprulecolor

Can I have rules at the outside of multicols?
Can I have a rule just between the 4th and 5th column?

Some History
TEX’s Model

Can I (arbitrarily) customize the column rules?

User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary— yes, all this could be easily implemented— only question: what is an adequate user interface?

From the user wishlist . . .
Shades and backgrounds
The stonyroad tocomplex pagelayoutCan I color the background behind a multicols
environment?

Frank
Mittelbach
The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

Can I add borders?

From the user wishlist . . .
Shades and backgrounds
The stonyroad tocomplex pagelayoutCan I color the background behind a multicols
environment?

Frank
Mittelbach
The Ask
Some History
TEX’s Model
User Wishlist

Can I add borders?

Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary— yes to both; column boxes and positions are known, so it iseasy to add background material— no official interface thoughFrom the user wishlist . . .
At the border
The stonyroad tocomplex pagelayoutWhy is there no one-column multicols environment?

Frank
Mittelbach
The Ask
Some History
TEX’s Model

How do I change the margins for a multicols
environment?

User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds

How can I interrupt multicols with single column
material?

At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

How can I avoid the indentation after a multicols
environment?

From the user wishlist . . .
At the border
The stonyroad tocomplex pagelayoutFrank
Mittelbach
The Ask
Some History
TEX’s Model
User Wishlist

Why is there no one-column multicols environment?
— simply because I didn’t forsee the need (and it was simpler)— provided by adjmulticol

How do I change the margins for a multicols
environment?
— provided by adjmulticol

Balancing & Floats
Columns
Column dependency
Rules & Backgrounds

How can I interrupt multicols with single column
material?

At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary— by stopping and restarting

How can I avoid the indentation after a multicols
environment?
— manually, using \noindentWishlist summary . . .
The stonyroad tocomplex pagelayoutFrank
Mittelbach
The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

Unresolvable wishes
combination of conflicting requirements

Wishlist summary . . .
The stonyroad tocomplex pagelayoutFrank
Mittelbach
The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

Unresolvable wishes
combination of conflicting requirements
Hard problems
touching TEX processing / model limitations
may limit the applicable scenarios
may result in fragile “hacks”

combination of requirements with layout interdependencies
multi-pass algorithms required
may result in impossible documents

huge search space
no efficient algorithms
may result in sub-optimal solutions

Wishlist summary . . .
The stonyroad tocomplex pagelayoutFrank
Mittelbach
The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

Unresolvable wishes
combination of conflicting requirements
Hard problems
touching TEX processing / model limitations
may limit the applicable scenarios
may result in fragile “hacks”

combination of requirements with layout interdependencies
multi-pass algorithms required
may result in impossible documents

huge search space
no efficient algorithms
may result in sub-optimal solutions

Wishlist summary . . .
The stonyroad tocomplex pagelayoutFrank
Mittelbach
The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

Unresolvable wishes
combination of conflicting requirements
Hard problems
touching TEX processing / model limitations
may limit the applicable scenarios
may result in fragile “hacks”

combination of requirements with layout interdependencies
multi-pass algorithms required
may result in impossible documents

huge search space
no efficient algorithms
may result in sub-optimal solutions

Wishlist summary . . .
The stonyroad tocomplex pagelayoutFrank
Mittelbach
The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing

Unresolvable wishes
combination of conflicting requirements
Hard problems
touching TEX processing / model limitations
may limit the applicable scenarios
may result in fragile “hacks”

combination of requirements with layout interdependencies
multi-pass algorithms required
may result in impossible documents

huge search space
no efficient algorithms
may result in sub-optimal solutions

Right to left
Spaces & penalties

Soft problems

Summary

missing (or bad) user interfaces

Moving on . . .
The stonyroad tocomplex pagelayoutFrank
Mittelbach

1
2
3
4

The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

5

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

6

The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary
Typesetting Challenges
Balancing
Right to left
Spaces & penalties
SummarySample typesetting challenges
Balancing considered harmful
The stonyroad tocomplex pagelayoutFrank
Mittelbach
The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

The steps of the algorithm:
Find a good starting column height
Trial-cut all material into columns of that heightSample typesetting challenges
Balancing considered harmful
The stonyroad tocomplex pagelayoutFrank
Mittelbach
The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

The steps of the algorithm:
Find a good starting column height
Trial-cut all material into columns of that height
We fail the trial if
the badness of any column is higher than columnbadness
the last column is larger than firsta forced break ends up in the last column
previous trial height < natural height of first column < trial
heightSample typesetting challenges
Balancing considered harmful
The stonyroad tocomplex pagelayoutFrank
Mittelbach
The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

The steps of the algorithm:
Find a good starting column height
Trial-cut all material into columns of that height
We fail the trial if
the badness of any column is higher than columnbadness
the last column is larger than firsta forced break ends up in the last column
previous trial height < natural height of first column < trial
heightIf the trail failed retry with a (slightly) larger column size

Sample typesetting challenges
Balancing considered harmful
The stonyroad tocomplex pagelayoutFrank
Mittelbach
The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

The steps of the algorithm:
Find a good starting column height
Trial-cut all material into columns of that height
We fail the trial if
the badness of any column is higher than columnbadness
the last column is larger than firsta forced break ends up in the last column
previous trial height < natural height of first column < trial
heightIf the trail failed retry with a (slightly) larger column size
If the trial succeeded and the final column has a highbadness (> finalcolumnbadness) set the column at its
natural height and not stretched out

Balancing considered harmful
The issues
The stonyroad tocomplex pagelayoutFrank
Mittelbach

Enlarging the column size may result in overflowing theavailable space

The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

The final result often shows compressed columns

Balancing considered harmful
The issues
The stonyroad tocomplex pagelayoutFrank
Mittelbach

Enlarging the column size may result in overflowing theavailable space— resolved by introducing \maxbalancingoverflow

The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

The final result often shows compressed columns

Balancing considered harmful
The issues
The stonyroad tocomplex pagelayoutFrank
Mittelbach

Enlarging the column size may result in overflowing theavailable space— resolved by introducing \maxbalancingoverflow

The Ask
Some History

The final result often shows compressed columns

TEX’s Model
User Wishlist
Balancing & Floats

1
2

Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary3

text 1text 2text 34text 45

text 5

Balancing considered harmful
The issues
The stonyroad tocomplex pagelayoutFrank
Mittelbach

Enlarging the column size may result in overflowing theavailable space— resolved by introducing \maxbalancingoverflow

The Ask
Some History

The final result often shows compressed columns

TEX’s Model
User Wishlist
Balancing & Floats

1
2

Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary3

text 1text 2text 34text 45

text 5

Balancing considered harmful
The issues
The stonyroad tocomplex pagelayoutFrank
Mittelbach

Enlarging the column size may result in overflowing theavailable space— resolved by introducing \maxbalancingoverflow

The Ask
Some History

The final result often shows compressed columns

TEX’s Model
User Wishlist
Balancing & Floats

1
2

Columns
Column dependency

3text 1text 2text 34
5

text 4text 5Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary— no (good) general solution possible— only alternative is to inspect the state of each column
and use this to fail a trial→ danger: adequate solutions are dropped

Sample typesetting challenges
Typesetting right to left
The stonyroad tocomplex pagelayoutFrank
Mittelbach
The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

Should be as easy as that . . . and the task for multicol issimple, isn’t it?

Typesetting right to left
The result (wrong!)
The stonyroad tocomplex pagelayoutFrank
Mittelbach
The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

Typesetting right to left
Corrected result
The stonyroad tocomplex pagelayoutFrank
Mittelbach
The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

SummarySample typesetting challenges
Space and penalty sequences
The stonyroad tocomplex pagelayoutFrank
Mittelbach
The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary\begin{multicols}{2}\begin{itemize}\item \verb=\addpenalty= and \verb=\addvspace=logic in \LaTeX{} has a flaw
\item \texttt{multicol} makes this apparent\end{itemize}\begin{itemize}\item \verb=\addpenalty= and \verb=\addvspace=logic in \LaTeX{} has a flaw
\item \texttt{multicol} makes this apparent\end{itemize}\end{multicols}Space and penalty sequences. . . and the result
The stonyroad tocomplex pagelayoutFrank
Mittelbach
The Ask
Some History
TEX’s Model
User Wishlist\addpenalty and\addvspace logic in
LATEX has a flaw
multicol makes thisapparent

Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

You see the issue?

\addpenalty and\addvspace logic in
LATEX has a flaw
multicol makes thisapparent

Space and penalty sequences. . . and the result
The stonyroad tocomplex pagelayoutFrank
Mittelbach
The Ask
Some History
TEX’s Model
User Wishlist\addpenalty and\addvspace logic in
LATEX has a flaw
multicol makes thisapparent

Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

You see the issue?
Right . . . the columns don’t line up\addpenalty and\addvspace logic in
LATEX has a flaw
multicol makes thisapparent

Space and penalty sequences
So what’s the problem?
The stonyroad tocomplex pagelayoutFrank
Mittelbach
The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary...\penalty -51% 1st \addpenalty...\glue 8.0 plus 2.0 minus 4.0% 1st \addvspace...\glue -8.0 plus -2.0 minus -4.0 % 2nd \addpenalty...\penalty -51%
dito...\glue 8.0 plus 2.0 minus 4.0%
dito...\glue(\parskip) 0.0 plus 1.0% start of \item...\hbox(6.83331+0.0)x345.0, glue set 323.88889fil

Space and penalty sequences
So what’s the problem?
The stonyroad tocomplex pagelayoutFrank
Mittelbach
The Ask
Some History
TEX’s Model...\penalty -51% 1st \addpenalty...\glue 8.0 plus 2.0 minus 4.0% 1st \addvspace...\glue -8.0 plus -2.0 minus -4.0 % 2nd \addpenalty...\penalty -51%
dito...\glue 8.0 plus 2.0 minus 4.0%
dito...\glue(\parskip) 0.0 plus 1.0% start of \item...\hbox(6.83331+0.0)x345.0, glue set 323.88889fil

User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border

LATEX generates a sequence of \addpenalty and\addvspace calls

Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

The break is taken at the second penalty
This leaves a zero space at the bottom of the column/page
making the baseline shift downwards as \prevdepth isgetting ignored

Moving on . . .
The stonyroad tocomplex pagelayoutFrank
Mittelbach

1
2
3
4

The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

5

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

6

The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary
Typesetting Challenges
Balancing
Right to left
Spaces & penalties
SummarySummary & Conclusion
The stonyroad tocomplex pagelayoutFrank
Mittelbach
The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

If we take off the shoes, i.e., restrict the use case scenarios
somewhat, then a lot can be achieved already within thelimitations of TEX (or LuaTEX)

Summary & Conclusion
The stonyroad tocomplex pagelayoutFrank
Mittelbach

If we take off the shoes, i.e., restrict the use case scenarios
somewhat, then a lot can be achieved already within thelimitations of TEX (or LuaTEX)

Some History

Good automatic float placement is still a largely unresolved
research area

TEX’s Model— Not an engine question at this point!

The AskUser Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

SummarySummary & Conclusion
The stonyroad tocomplex pagelayoutFrank
Mittelbach

If we take off the shoes, i.e., restrict the use case scenarios
somewhat, then a lot can be achieved already within thelimitations of TEX (or LuaTEX)

Some History

Good automatic float placement is still a largely unresolved
research area

TEX’s Model— Not an engine question at this point!

The AskUser Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

The paragraph shape model is defective— A typesetting engine needs to enable reformatting— Paragraph breaking algorithms should work on physical shapespecifications not on line counts

Summary & Conclusion
The stonyroad tocomplex pagelayoutFrank
Mittelbach

If we take off the shoes, i.e., restrict the use case scenarios
somewhat, then a lot can be achieved already within thelimitations of TEX (or LuaTEX)

Some History

Good automatic float placement is still a largely unresolved
research area

TEX’s Model— Not an engine question at this point!

The AskUser Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

The paragraph shape model is defective— A typesetting engine needs to enable reformatting— Paragraph breaking algorithms should work on physical shapespecifications not on line counts

Multi-directional typesetting may need a better model— TEX’s model is clearly defective, but LuaTEX’s (Omega) model
may need revisiting as well → looking forward to John’s talk

Summary & Conclusion you
The stonyroad tocomplex pagelayoutFrank
Mittelbach
The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

So is waiting necessary?
San Francisco 2010

Thank you
The stonyroad tocomplex pagelayoutFrank
Mittelbach
The Ask
Some History
TEX’s Model
User Wishlist
Balancing & Floats
Columns
Column dependency
Rules & Backgrounds
At the border
Wishlist summary

Typesetting
Challenges
Balancing
Right to left
Spaces & penalties

Summary

Or can it be helped a little?
Takayama 2009