Formatting documents with floats
A new algorithm for LATEX 2ε∗c Frank Mittelbach
xo-pfloat.tex 1.9 2000/05/19 08:23:11 latex3 Exp

Contents

6

Layout Specification
6.1 Float type declarations . . . . . . . . . .
6.2 Float area declarations . . . . . . . . . .
6.3 Footnote formatting declarations . . . . .
6.4 Page setup declarations . . . . . . . . . .
6.5 Float formatting declarations . . . . . . .

8
8
8
9
9
10

1

Introduction

1

2

The document source model2

3

The document layout model
3.1 Columns . . . . . . . . . . . . . . . . . .
3.2 Balanced columns . . . . . . . . . . . . .
3.3 Float areas . . . . . . . . . . . . . . . . .
3.4 Float pages and columns . . . . . . . . .
3.5 Float types . . . . . . . . . . . . . . . . .
3.6 Margins . . . . . . . . . . . . . . . . . .
3.7 Footnotes . . . . . . . . . . . . . . . . .
3.8 Headers and footers . . . . . . . . . . . .

4

The processing model
4.1 Float placement concepts . . . . . . . . .
4.2 Float pages and columns . . . . . . . . .
4.3 Float storage . . . . . . . . . . . . . . . .
4.4 Caption processing . . . . . . . . . . . .
4.5 Flushing floats . . . . . . . . . . . . . . .
4.6 Float and call-out relations . . . . . . . .
4.7 Float and footnote relations . . . . . . . .
4.8 Area statuses . . . . . . . . . . . . . . .
4.9 Area constraints . . . . . . . . . . . . . .
4.10 To “Here” or not to “Here” . . . . . . . .

5User control
5.1 Column and page breaks . . . . . . . . .
5.2 Manual float flushing . . . . . . . . . . .
5.3 Specifying preferred areas . . . . . . . .
5.4 Manually position all floats . . . . . . . .
5.5 Tracing the algorithm’s behavior . . . . .

2
2
7 Performance of the algorithm
113
3 8 Outlook
113
3
3 Abstract
4
4 This paper describes an approach to placement of floats in
multicolumn documents.
4
The current version of LATEX was originally written for
4 single-column documents and extended to support two4 column documents by essentially building each column
5 independently from the other. As a result the current sys5 tem shows severe limitations in two column mode, such as
5 the fact that spanning floats are always deferred to at least
5 the next page or that numbering between column floats
5 and spanning floats can get out of sequence.
6
The new algorithm is intended to overcome these limi6 tations and at the same time extend the supported class of
6 document layouts to multiple columns with floats spanning an arbitrary number of columns.
66
7 1 Introduction
7
7 One problem with formatting documents containing floats
7 is the number of potential formatting solutions that need1

2

to be checked out. The number of trials grows combinatorially in the number of floats and areas which can receive
them. If we have n floats waiting to be placed and m areas in which we can place them on the current page being
built (not counting the “deferred area”) then the numberof different placements is given by#trials =n+m(n + m)!
=mn! m!

The document source model

The document source is a single stream of continuous text
containing call-outs to floating objects. (At the moment
the call-outs are marked by placing the objects into thestream but it would be possible to provide them as separate objects.) Floating objects (as of today) come in three
incarnations:(1)• Objects where the call-out and the placement requires a strict spatial relationship, e.g., same line in
the margin. An example would be marginal notes as
implemented by \marginpar in LATEX 2ε .

assuming that the order of floats has to be preserved, i.e.,
if the call-out of float fi is before the call-out of fj in the
text stream then the float fi will be placed in earlier than
float fj where “earlier” is a defined relation of float areas.

• Objects where the call-out and the placement is required to fall onto the same column/page/spread,e.g., footnotes.

For example, if we have 8 floats waiting to be distributed among 12 areas (which corresponds to a three column page with float areas at the top and bottom allowing
for partial spans) then we have to check 125970 possible
distributions; if two additional floats appear we end up
with 646646 trials.

• Objects where there is a defined relation between
call-out and object placement, e.g., “not in an earlier
column”, or “on the same page or later”, etc. These
are the traditional floats.

Even though a large number of these distributions
would be unacceptable and discardable straight away, after some initial test, the resulting running time of the algorithm would clearly be beyond any acceptable speed.
(Assuming we could do 1000 trials per second, which is
ridiculous high since many of them would require trialtypesetting the whole page, then the case of 646646 trials
would still take roughly 10 minutes to form a decision.)

Float objects in the last group are typed where the type isdefined by the logical content of the object, e.g., “figure”,“table”, and so on.
The document formatting is achieved using a minimal
but customizable lookahead (typically the considered galley material is the equivalent of one page/spread of textual
material ignoring the additional size taken up by embedded float objects).
While making up pages the main “quality” guidance
for the algorithm is to try to place each float as early as
possible without violating defined constraints.

Thus it is important to find algorithms with complexitythat is at worst linear in both the number of floats on thetrial list and the number of possible float areas, even if
this means that in a few cases a relatively good layout
will not be found. It is even better if they have minimal
redundancy.
Note that assessing the actual running time of TEX code
is not straightforward since some activities are very much
faster than others. For example, performing a test by using
a reasonable number of macro expansions and register assignments may be very much slower than running througha long typeset list and then doing a simple test.

3

The document layout model

3.1

Columns

The page layouts which are supported by the new algorithm support an arbitrary number of text columns ofequal width.
The number of columns per page as well as their width
can be changed at forced page breaks such as the start ofchapters.

The algorithm we have implemented fulfills the requirement of being (essentially) linear in the number offloats and the number of float areas.
2

3.2

Balanced columns

Figure 1: Overlapping float areas

Balancing columns (like the multicol package does) isplanned but not implemented. The major problem in thatarea is the handling of column floats during the balancing
process.

3.3

aaaaaaaaaaa 444
aaaaaaaaaaa 444
aaaaaaaaaaa 444
111 222111 222 bbbbbbb
111 222 bbbbbbb
111 222 bbbbbbb
111 222111 222 333 444
111 222 333 444
111 222 333 444

Float areas

Float objects are distributed into float areas which arerectangular in shape. Float areas span one or more text
columns, their horizontal size is therefore given by thefollowing formula (where c is the number of columns
spanned):The first formula describes the areas which partly over
lap from the left, the second formula describes those thatharea-widthi = c × hcol-widthi + hcol-sepi − hcol-sepi partly overlap from the right. Areas which are sub- or
super-areas, e.g., t31 and t22 do not affect each other.
Naming conventions for float areas is as follows:
The above restriction is necessary to prevent situations
hidentifierihspan-countihstart-columni.
like the one shown in figure 1 i.e., where the float areat23
(represented as b’s) would result in splitting the
The hidentifieri is a single letter denoting the type of area,
fourthcolumn into two independent text areas.
e.g., t for top, b for bottom. The hspan-counti is a sinThepossibilities, as well as the restrictions, are equalgle digit denoting the number of columns to span. Thefor
both
top and bottom areas. This means that the new1
hstart-columni is a single digit denoting the start column
schemeinparticular supports spanning bottom areas.
of the area. Thus t23 is a top area starting at column
three and spanning two columns, i.e., three and four. A
restriction due to the naming scheme is that currently nomore than 9 columns are possible.2
Only a subset of the float areas is allowed to be populated on a page. In essence the new algorithm does notsupport placements that result in “splitting” the text of acolumn due to a float (other than column ‘here’ floats).3
This means that population of some float areas must be
prevented, namely those satisfying these conditions whenpsc (where p = pos, s = span, c = column) has just been
populated:

3.4

Float pages and columns

Float pages, i.e., pages consisting only of floats, will besupported as well as float columns.

3.5

Float types

The type of float influences the formatting, e.g., where
the caption is placed in relation to the float body, how it
is formatted, what kind of fixed strings are added, etc. It
also restricts the placement algorithm in respect to which
float areas can be populated as explained below.

pij with j < c ≤ i + j < c + s
or

3.6

pij with j ≤ c + s < i + j ≤ hnumber-of-columnsi

Margins

The marginal areas can receive marginal notes which arealigned with the corresponding text line. In documentswith more than two columns marginal notes are currently not supported though one could envision allowing
them even there. If marginals have to compete for space
the later marginal will be moved downwards if there is

1 With a bit of care in the code this could be extended to allow morethan one digit.
2 The scheme is different from the original one used, where t23
would have denoted an area starting at column two and spanning until column three. Probably a final version will exchange hspan-counti
and hstart-columni as this seems to be more natural.
3 Perhaps this restriction will be lifted one day.

3

enough space on the page, otherwise the line containing
the marginal will be moved to the next column/page.4
An alternative usage of the margin is to place footnotes
into it. A prototype version of this is provided already, seesection 3.7.
Another potential use of the margin areas is to use them(or parts thereof) as float areas in their own right. The
problem with this would be that these float areas would
have a horizontal width which is different from the column width, thus allowing only a limited class of floats toappear therein.
Another potential extension would be to allow float areas that border on a margin to use the marginal space aspart of the float area, thereby allowing the filling of suchan area with floats which are wider than the nominal float
area. A special case of this, the placement of the caption
in the margin beside the float body, is already provided bychoosing a suitable caption formatting instance.

3.7

each mark class information about the top mark (i.e., themark active at the top of the column) the first mark andthe last mark is made available for retrieval.
This allows to produce correct running headers andfooters for various types of applications such as dictionaries, manuals, etc.

The processing model

4.1

Float placement concepts

To build a page(-spread) the algorithm first assembles
enough textual material to be able to fill the page without
placing any floats. During this process all floats that havetheir call-outs within the assembled galley are collected.
They form, together with unplaced floats from previous
pages, an ordered trial list of floats.
The allowed float areas on the page under construction
are totally ordered as well.
The algorithm proceeds by taking the first float from thetrial list and trying to place it into the first float area fromthe area list. It then checks if all constraints (see below)
are met and if not the algorithm will try to place the float
into the next area until either all constraints are met or theareas in the float area list are exhausted. A trial that does
not fail means that this distribution of floats becomes thebest solution so far and all further trials will be based on
adding to this solution (no backtracking) . If the algorithm
fails to place the float into any area it means that the float
will be deferred to a later page.
By adding floats to areas the constraints for further trials can change for several reasons: on one hand, the callout positions of various floats move since the float will
occupy space on the page; on the other hand, placing afloat in some area might result in disallowing the placement of other floats in the same or in other areas.

Footnotes

Footnotes can be regarded as a special type of floats. They
are objects which are associated with lines of text (theircall-out) but in contrast to normal floats such as “figures”
or “tables” their placement constraints are stronger, e.g.,they typically have to appear at the bottom of the column
which contains their call-outs, or at least they have to appear on the same page as their call-outs.
In its current version, the model supports footnotes beneath the call-out column (normal behavior); all footnotesin the last column (as with the ftnright package fortwo-column mode); all footnotes in the outer (or inner)
margin.
Without an extension to the page makeup algorithm(but instead with a suitable redefinition of the footnote
commands) they could be processed as marginal notes oralternatively as “end-notes”.

3.8

4

4.2

Headers and footers

Float pages and columns

At the moment there is only rudimentary support for float
pages available: at the start of each page the algorithm
will try to form a float page out of all floats that have beendeferred from previous pages. However there is no layout control available to define the conditions under whichsuch a trial will succeed.

The header and footer areas may use data received fromindividual columns. An extended version of TEX’s markmechanism is made available which allows the definitionof arbitrarily many independent classes of marks. Within
4 This is not yet implemented — right now they overprint each other.

4

4.3

Float storage

4.6 Float and call-out relations

Float bodies can be typeset into boxes at the point of ‘callout’, as with the figure and table environments in thestandard LATEX; it may also be possible to specify at thecall-out point a logical pointer to a float whose typesettingis specified elsewhere (e.g., an external file).
However, text sub-elements such as the caption, etc.,(e.g., from \caption) are not typeset at this stage but
are stored as token lists; this allows for trying different
possible layout specifications, e.g., for its measure, during
the float-positioning trials. At present this is confined toat most a single caption element per float.

The algorithm keeps track of the relation between a float
and its call-out. This allows one to define constraints
which guide the algorithm during the float placement
phase. It is always permissible to place a float “after” itscall-out, e.g., in a later column/page. At the moment thefollowing constraints can be specified:

4.4

column which means that the float can be placed before
the call-out as long as it is placed in the same column.

none which means that the relation between call-out andfloat placement is not relevant for placing floats.
page which means that the float can be placed anywhereon the page with the call-out (it is visible from thecall-out).

Caption processing

When a float is placed into an area the caption is trial formatted and mounted onto the float body. This process cantake into account various information about the float positioning trial, such as the area to format it into, the factthat it formats onto a verso or recto page, etc. It might
try several possibilities before making a decision, e.g., if
one formatting of the float results in violating some constraint(s) it might try a different formatting at this point.

after which means that the float has to be placed strictly
after the call-out.
When extending the algorithm to directly support spreads
the above list is going to be extended by an option thatallows floats to move backwards on the whole spread.

4.7
4.5

Flushing floats

Float and footnote relations

It is possible to direct the algorithm to check on each column if there are footnotes, and if so to prevent it fromplacing floats in the bottom area. In theory it might bepossible that a forbidden constellation might resolve itself
once the algorithm has added further floats, e.g., it could
be the case that by adding additional floats the offending footnote gets moved to a different column. However,checking for this would mean potentially large backtracking so the algorithm uses a conservative approach andsimply considers a trial as failed if footnotes and bottom
areas collide.
It is planned to allow a designer the choice of specifying where the footnotes should be placed in relation to
any bottom floats (if the combination is allowed). Right
now this is not implemented and column footnotes will
always appear below the text column, i.e., above any bottom floats.

It is possible to mark points in the source document asboundaries beyond which floats whose call-outs are prior
to the boundary cannot pass. In other words a “flush
point” directs the algorithm to place all affected floats into
areas which are “before” the flush point.
If due to other constraints the float could not be placedin such an area the algorithm first retries all potential areas using a less rigid set of constraints (for example, restrictions on the number of allowed floats per area aredropped) and if this still doesn’t enable the algorithm toplace the float properly it will as a last resort move theflush point to a later column.
Flushing of floats can be done either for all dangling
floats or on a per float type basis, e.g., it is possible toflush only floats of type “figure”.
54.8

Area statuses

actually needed to allow the specification for a reasonable
number of layouts.
For example, LATEX 2ε allows the designer to restrict
the maximum size of an area, but should one provide thisor should there be a constraint on the size of all stacked
areas? Or should there be both?

For each area the algorithm keeps track about whether or
not it is closed for individual float types, e.g., is not accepting any more floats of type “figure” or closed for all
types. The status of an area can change due to floats being placed into other areas (this might, for example, closeearlier areas, or areas that overlap) or it can change due tothe fact that the area became too full in some way (e.g., asize constraint or a number of floats constraint).
Some of these constraints can be “relaxed” in certain
situations, e.g., if the algorithm is directed to flush out remaining floats prior to a certain point in the galley it will
drop constraints related to number of floats per area orsize restrictions. However, if an area was closed due toa different float being placed into some other area, thisarea will stay closed in all circumstances to ensure proper
sequential placement of floats and to ensure that overlapping areas that are forbidden as explained in section 3.3
will not receive floats at the same time.

4.9

4.10

To “Here” or not to “Here”

LATEX 2ε allows the user to control the placement of an individual float by specifying one or more areas into which
the float would be allowed to move using single letters.
As a special notation an h would denote a so-called “here”
float. Its advertised semantics is to try placing the float “atthe position in the text where the environment appears”[1, p. 197]. If this is not feasible LATEX 2ε would try theremaining allowed possibilities on the next page, thus afloat with a ht specification would either appear within
the text or at the top of the next or a later page.5
In many cases people however prefer a “here” which
always means “here”. The latter form is implemented insome add-on packages for LATEX 2ε , however usually at
the cost of keeping the float sequence order in sync.
The new model supports only the absolute “here” form
for floats; however, correct ordering of floats in the output is guaranteed (if the tag generating the here float issues flushing of floats for the current type). If there is notenough space to place the float in a column, the float plus
the preceding text line6 is moved to the next column/page.

Area constraints

The algorithm offers several possibilities for the designer
to specify how and under what circumstances a float isallowed to be added to a certain area on the page.
As explained above all areas on a page are tried in a
specific order. This order can be specified and changed forspecific parts of the document. Areas that are closed forthe current type will be bypassed as well as areas which do
not span the right number of columns to fit the horizontal
size of the float. If these initial tests succeed the float may
still fail to be placed into a certain area if it doesn’t fulfill
the following set of constraints:• There is an upper limit on the total number of floats
that can be placed on an individual page.

5

User control

5.1

Column and page breaks

Breaking of columns and pages can be controlled fromthe source document by placing special tags into it. The\columnbreak command ends the current column after the current line (if used in horizontal mode). Similarly• Each area has an upper limit of floats that can go intoit.
• After placing the float the remaining space in the text
column must be larger than a specified value.

5 In two-column mode this can in fact result in a placement on the topof the second column even though the call-out position finally falls into
the middle of that column.
6 More precisely the column is broken at the last breakpoint preceding
the current position which is normally one line above but could be more(or less).

All such constraints are customizable.
Additional constraints will probably be implemented
once there has been some experience of what controls are
6

Page: 1 (1)Area: t31
Float: 4 (figure 4) []Area: b12
Float: 2 (figure 2) [mylab:fig1]
Area: t13
Float: 3 (figure 3) [mylab:fig2]

the \pagebreak command ends the current page.7

5.2

Manual float flushing

The flush float functionality is available within the source
document via the command \flushfloats. This command takes an optional argument which, if present, denotes the float type to flush. If used without the optional
argument all floats are flushed.

5.3

Area: hhh
Float: 11 (table 1) []Page: 2 (2)Area: t31
Float: 8 (figure 8) []Area: t22
Float: 5 (figure 5) []Area: b11
Float: 6 (figure 6) [mylab:fig3]
Area: b13
Float: 7 (figure 7) [mylab:fig4]

Specifying preferred areas

At the time of writing the document source interface for
specifying the group of areas into which a float is allowed
to move is not yet decided. One could envision keeping
the original LATEX interface to float environments with optional argument. In that case something like [t] could
be internally interpreted as “any top area that exists” andtranslated into a list such as t21 t11 t12. But otherinterfaces are conceivable as well.

Table 1: An example fpl file

Beside moving floats between float areas it will be possible to move floats in and out of the special area called
hhh which represents a list of all “here” floats on the
5.4 Manually position all floats
page. If a float is moved into the “here” area it means
Any algorithm that automatically places all floats may that it will be positioned as a here float at the point of its
fail to produce adequate results in some situations. In call-out.
LATEX 2ε the user was offered only the optional arguments
As an extension to this method we are experimentingof the float environments and by this method and by mov- with restricting the manual control only to parts of theing floats slightly in the source document one was finally document, e.g., allowing the user to manually fix a single
able to change the formatting as needed.
chapter but have the algorithm determine the remainder.
This was a time consuming and error prone manual task We also plan to integrate column length control in thisand any slight change in the source document text was way, so that it becomes easily possible to run a page or
likely to result in making this work obsolete.
double-spread long or short by specifying this externally
To improve on this situation the new algorithm can be rather than via tags in the source document.
directed to write out a file containing all of its float8 selections (an example is shown in table 1). By simple dragand drop the user can produce alterations to this selection. 5.5 Tracing the algorithm’s
If such a modified file is stored as \jobname.fpc thenbehavior
the algorithm will use these selections without attempting
to apply any of its internal rules. Thus the formatting will In contrast to the LATEX 2ε output routine, which is a blackbox as far as the user is concerned, the new algorithm tries
happen exactly as specified.9
hard to make its decision process comprehensible. Table 2
7 At the moment these commands force a break; there is no possibility, as in LATEX 2ε to suggest only that the current point is a good or badbreak.
8 Floats in this contect mean “traditional” floats, not footnotes or marginpars.
9 If the floats are stored within the source document at the point of

their call-outs, the algorithm will be able to position a float only if it has
already encountered the float in the source document. This means that
one can move a float arbitrarily forward but only to a limited extent before its call-out position. If the floats are stored externally to the source
document this restriction does not apply.

7

Table 2: Progress output of the algorithm=======================================================================STATS: floats waiting = 37 on page 2=======================================================================
Float: \bx@A{figure} {1.1}{a special one}area trial: t31 -> failed: span count t31 /= 1
area trial: t21 -> failed: span count t21 /= 1
area trial: t22 -> failed: span count t22 /= 1
area trial: t23 -> failed: span count t23 /= 1
area trial: t11 -> failed: t11 float not allowed by user control (t12)area trial: b11 -> failed: b11 float not allowed by user control (t12)area trial: t12 -> accepted
Float: \bx@B{figure} {1.2}{This is a figure caption for (1)}area trial: t31 -> failed: span count t31 /= 1
area trial: t21 -> failed: span count t21 /= 1
area trial: t22 -> failed: span count t22 /= 1
area trial: t23 -> failed: span count t23 /= 1
area trial: t11 -> failed: area closed for type figurearea trial: b11 -> failed: area closed for type figurearea trial: t12 -> accepted

6.1

shows a sample output produced by it. It shows for eachfloat which areas have been tried, why they were rejectedetc. There is also an option which produces about 100
times as much information but the latter is probably useful
only for debugging the system in case there are errors in
the code.

6

Float type declarations

Float
types
are
declaredusing
the\DeclareFloatType command which at the
moment takes two arguments: the name of the type which
is used to refer to it in various places, and a single letter
abbreviation which is used to produce the extension foran external file, e.g., to collect material for the list of
figures, etc.

Layout Specification\DeclareFloatType{figure}{f}\DeclareFloatType{table}{t}\DeclareFloatType{algorithms}{a}In the class file the designer is given control over the algorithm’s behavior in all the aspects described above (andseveral more).
The layout specifications are done through the newtemplate and instance concept, see [2]. Additional information such as experimental code, further documentation,etc. can be found on the LATEX project web site at:

Clearly additional information needs to be stored together
with the type, e.g., the representation of the float number,etc. This information is likely to be added to the typedeclaration by changing the second argument into a list of
key/value pairs comparable to the way the declaration ofareas is handled.
The declaration of a new float type automatically defines the necessary user document environments.

http://www.latex-project.org
In contrast to the algorithm itself, which in its basic
functionality now seems to be stable and reliable, the design interface is far more experimental. Thus the example
declarations given below represent only the current stateof thought and are likely to be modified at any moment.

6.2

Float area declarations

Any float area that is going to be used at some stage
by the algorithm needs to be declared beforehand. This8

6.3

is done through the \DeclareFloatArea command
which takes two arguments: the name of the area (which
has to follow the conventions explained in section 3.3)
and a list of key/value pairs describing the characteristicsof the area.

Footnote formatting declarations

The formatting of footnotes is specified by declaring instance(s) of type footnotesetup. At the moment
three templates are available though they should be considered only as prototypes: the template std produces
conventional footnotes below each column, the template
ftnright collects all footnotes and typesets them in therightmost column, and the margin template collects andtypesets them in the right outer margin.
The keys of the above templates are providing only arudimentary flexibility (to say it positively), in a production version all of them would need a large number ofextensions. As an example\DeclareFloatArea{t22}{type-close-list = {t11,b11},
all-close-list = {t21,t23},
max-float-num= 2,}
As of today an area is characterized through the
maximum number of floats it is allowed to receive(max-float-num) and through two lists which tell thealgorithm which other areas are affected by adding a float
to the current area. The list type-close-list enumerates all areas which are not allowed to receive additional floats of the type that has been placed into thecurrent area while the list all-close-list contains
the information about all areas that are to be completely
closed the moment a float is received in the current area.
The type-close-list key is primarily intended to
specify a partial order on the areas to ensure that floats are
not getting out of sequence in the output. For example,
the above declaration says: if a float is placed into areat22, i.e., a top area starting at column two and spanning
two columns, then the single column areas t11 and b11(i.e., those of the first column) are closed for floats of thesame type. However, assuming this example is part ofa declaration for a four column layout which could haveareas like t41 or t31, there is nothing said about closing
those areas. Thus in this particular layout a float spanning
three or four columns would still be allowed to go on top.
On the other hand the all-close-list key is available to ensure more visual constraints, e.g, “if t21 getsfilled we don’t want to have b21 filled as well, we only
want b22 in this case”. In addition it needs to implement
the restriction about overlapping float areas as describedin section 3.3, e.g., in the example declaration t21 andt23 are closed since they partly overlap with t22.10\DeclareInstance{footnotesetup}{mainmatter}{std}{text-sep= 14pt plus 3pt,
max-height = 8in,}would declare the named instance mainmatter thatprovides footnotes below columns with a separation of
14pt+ and a maximum height for footnotes per column
being 8in.
Instances like this can then be used in the declaration
for a particular page layout as explained below. Alternatively one could use unnamed instances there using the\UseTemplate method.

6.4

Page setup declarations

At the heart of the layout declaration are instances of
the type pagesetup2.11 An example setup showing all currently available keys is given in table 3.
The first four keys (column-num, column-width,column-height, and column-sep) describe the column structure of the page layout being defined, i.e., in thiscase a two-column layout.
The following three keys define the standard constraints
for the algorithm when placing floats: max-float-num
is the maximum number of floats that can go on a normal
page, float-callout-constraint defines whatkind of relations between float and call-out are allowed,

10 As mentioned before, this restriction might be lifted in a later version of the algorithm; as long as it is required one could alternatively
add those areas behind the scenes to avoid runtime problems.

11 The number 2 has historical reasons and will vanish again at somepoint in the future.

9

Table 3: Example declaration for the pagesetup2 template showing all keys
\DeclareInstance{pagesetup2}{mainmatter}{std}{column-num= 2,column-width= 220pt,
column-height= 610pt,
column-sep= 20pt,max-float-num= 3,
float-callout-constraint= page,bottom-float-footnote-constraint= forbidden,
flush-float-callout-constraint= page,flush-bottom-float-footnote-constraint = none,area-list= {t21,t11,b11,b21,t12,b12},defer-type-close-list= {t21,t11,b11,b21,t12,b12},defer-all-close-list= ,footnote-setup= mainmatter,}and bottom-float-footnote-constraint defines whether or not bottom floats are allowed in case offootnotes.
The last two constraints are replaced by flushfloat-callout-constraint
andflushbottom-float-footnote-constraint in caseflushing can’t be done without relaxing the conditions (max-float-num is disregarded in that caseautomatically).
The key area-list defines all float areas thatare allowed in this page layout as well as defining
the order in which the areas are tried when placing floats. The keys defer-type-close-list
and defer-all-close-list define the “closing actions” for the special area which receives the floats
that could not be placed.
E.g., if a float of acertain type can’t be placed then all areas listed indefer-type-close-list will be closed for thistype. In other words the two keys are comparable to theones available for area declarations.
Thus these keys together with the keys from the area
declarations are most important to guarantee a sensibleorder of floats on the formatted page.
In an earlier implementation of the algorithm a simpler scheme was used: there was a single area list which
was shortened whenever a float couldn’t be placed into it
thereby confining the remaining floats to this restricted se-

lection. This works fine as long as there are mainly single
column floats since in this case the area can be reasonably ordered into a single sequence. However the moment spanning floats are supported the situation gets lessstraightforward. Is the area t11 before or after t21?
It is quite likely that the current controls will turn out
to be too crude. This will be seen once a suitable number of layouts have been produced under this scheme (orcouldn’t be produced because they turned out to be unspecifiable).
Finally the key footnote-setup receives an instance of a footnotesetup template.

6.5

Float formatting declarations

For the attachment of captions to floats there exists a prototype interface using templates of the typebuildfloat. At the time of writing, available templates are centeredbelow, centeredabove, andbottomright, which center the caption below or above
the float body or place it to the right of it, aligned with thebottom of the float body. All of them would need to begeneralized for a production system to become more flexible.
When trial-formatting a float the algorithm checks forthe existence of a number of buildfloat instances anduses the first one that exists to build the float. More10

precisely it first checks if an instance with the namehareai-htypei exists, then it looks for hareai, then for
htypei, and finally, if none of them exists, for an instancewith the name default. So at least the latter instancehas to be declared by the class.
\DeclareInstance{buildfloat}{default}{centeredbelow}{}\DeclareInstance{buildfloat}{table}{centeredabove}{}\DeclareInstance{buildfloat}{t13}{bottomright}{}\DeclareInstance{buildfloat}{t22}{bottomright}{}
The example declaration above defines the placement of
captions above tables and below for all other types, withthe exception of the areas t13 and t22 where the captions are set to the side.

7

Performance of thealgorithm

STATS: floats waiting = 24 on page 1
STATS: trials = 286
STATS: floats waiting = 19 on page 2 (float page)
STATS: trials = 159
STATS: floats waiting = 37 on page 2
STATS: trials = 397
STATS: floats waiting = 19 on page 3 (float page)
STATS: trials = 166
STATS: floats waiting = 7 on page 4 (float page)
STATS: trials = 41
STATS: floats waiting = 20 on page 4
STATS: trials = 204
STATS: floats waiting = 5 on page 5 (float page)
STATS: trials = 27
STATS: floats waiting = 12 on page 5
STATS: trials = 108
STATS: floats waiting = 0 on page 6 (float page)
STATS: trials = 0
STATS: floats waiting = 6 on page 6
STATS: trials = 57...
STATS: floats waiting = 6 on page 12 (float page)
STATS: trials = 26
STATS: floats waiting = 6 on page 12
STATS: trials = 37
STATS: floats waiting = 0 on page 13
STATS: trials = 0

Table 4: Statistics from the algorithm

To test the performance of the algorithm we prepared asomewhat ridiculous test file containing three types offloats (“figures”, “tables”, and “algorithms”) with a total
number of 47 floats. The chosen layout had 3 columns
and 11 potential float areas. Figure captions have beenplaced below the float while with tables and algorithms
the caption was placed on top. The exception was the top
areas adjacent to the outer margin: floats placed there got
their captions placed to the right and partly into the margin. Footnotes were collected for all columns and placedin the outer margin.
Floats had to strictly follow their call-out and a maximum of ten floats was allowed per page, i.e., roughly three
per column.
Since the document contained many floats early on (24on page one) and the first of these was especially constructed to be not placeable the first time around, the algorithm had to work hard to place all the dangling floats. Table 4 shows some statistics as produced by the algorithm
on the number of trials necessary (the highest number was
397 for 37 floats; by comparison, formula (1) would give
22595200368 which would probably take a bit longer to11evaluate). Note that on the third page the algorithm wasable to produce a float page, on all other pages the float
page trial was unsuccessful.
Table 5 shows the running times needed to produce thefinal document of 13 pages when the algorithm is usedwith different tracing settings. The test machines werea Pentium 600 machine and an older laptop with a 486
processor. In both cases TEX was run straight from a TEX
Live 4 CD.
These times show that the algorithm has an acceptable
time performance since even on a 486 the average time to
produce a page is roughly 2 seconds.

8

Outlook

While the current algorithm performs well there are several areas in which its functionality could and probably
should be extended. The most important points are givenin the following list.

PIII (600MHz)

486DX4 (75MHz)

changes behavior could be made customizable sothat people with faster machines (or more patience)
could have the optimum running for as many floats
as they like.

no tracing
real
user
sys

0m1.533s
0m1.460s
0m0.050s

0m27.633s
0m26.940s
0m0.690s• The float call-out constraints should probably bemade more flexible; for example, if the design specifies column then a spanning float whose call-out
is in the second column will not be placed into thearea t21 since this area is above the first column (aswell as above the second) and the algorithm therefore
fails the trial. This behavior is debatable and shouldat least be made customizable.

progress information
real
user
sys

0m3.116s
0m1.740s
0m0.080s

real
user
sys

0m7.833s
0m2.720s
0m0.280s

0m36.885s
0m34.470s
0m2.420s
full tracing
1m22.480s
1m7.890s
0m12.360s• Instead of flushing floats in such a way that all floats
will appear before a certain point in the text column,
one does sometimes want only to ensure that the float
appears on a certain page. Such a “fuzzy-flush” concept is currently under investigation.

Table 5: Running times of the algorithm• Balancing of partial pages, comparable to the way
the multicol package works, should be implemented to allow for layouts where, for example, aheading should span across all columns.
• We intend to provide more control over the marginalareas, allowing for marginal floats as well as otherobjects in the margin, properly interacting with eachother.

References[1] Leslie Lamport. LATEX: A Document Preparation System. Addison-Wesley, Reading, Massachusetts, second edition, 1994.
[2] Frank Mittelbach, David Carlisle, and Chris Rowley. New interfaces for LATEX class design. TUGboat,20(3):214–216, September 1999.

• Without much effort the algorithm could be extended
to properly support double-spreads so this should be
added some time soon.
• Once the algorithm has decided which floats to place
onto a page one could add a post-processing step inwhich the placement could be reconsidered according to different rules. For example, if the call-out
relation is page then floats will tend to be placed in
the left-hand columns. This is fine as long as there
are many floats to process but on a page with only a
few floats one might want to redistribute them differently once it is clear which floats could go onto thepage.
• Since it is known beforehand how many floats areactively waiting to be placed, one could use a different algorithm that tries all possible combinations
as long as there are only a limited number of floats
to be placed. The boundary at which the algorithm
12