Reflow text blocks in a page

Question

Friends, I have a simple layout to typeset a songsheet for my parish which consists of two columns provided by the multicol package and a custom environment that simply wraps each song. The following document might give you guys the idea of the layout (I added the colours just to visually indicate each block; these colours might help us understand my question later on):

\documentclass[a5]{article}

\usepackage{xcolor}
\usepackage{xparse}

\ExplSyntaxOn
\NewDocumentCommand{ \repeatword } { m m }
{
   \prg_replicate:nn { #1 } { #2 ~ }
}

\bool_gset_true:N \g_tmpa_bool

\NewDocumentCommand{ \getcolour } { }
{
  \bool_if:nTF \g_tmpa_bool
  {
    \color{blue}
    \bool_gset_false:N \g_tmpa_bool
  }
  {
     \color{red}
     \bool_gset_true:N \g_tmpa_bool
  }
}

\NewDocumentEnvironment{ textblock } { }
{
   \setlength{\parindent}{0pt}
   \getcolour
}
{ }
\ExplSyntaxOff


\usepackage{multicol}

\begin{document}

\begin{multicols*}{2}

\begin{textblock}
\repeatword{100}{duck}
\end{textblock}

\begin{textblock}
\repeatword{200}{goose}
\end{textblock}

\begin{textblock}
\repeatword{130}{parrot}
\end{textblock}

\begin{textblock}
\repeatword{100}{falcon}
\end{textblock}

\begin{textblock}
\repeatword{150}{owl}
\end{textblock}

\begin{textblock}
\repeatword{150}{swan}
\end{textblock}

\begin{textblock}
\repeatword{100}{chicken}
\end{textblock}

\begin{textblock}
\repeatword{50}{mallard}
\end{textblock}

\end{multicols*}

\end{document}

And I have the following output:

I'm using this layout for about one year now, and I noticed it works great on most of the cases, but sometimes we have some songs that start in one page and end in the next one. In my example, the owl block reflects what I meant: see the blue text ending in page 1 and continuing in page 2.

My first plan: well, let me make each song, well, unbreakable. :) Let's say I decide to enclose each text block in a \parbox. Now things work quite differently:

Now my songs don't break anymore. :) But I have some gaps in the text, since TeX preserves the order. Now let's take a closer look at page 1 from my first attempt:

Note that the parrot text block is smaller than the goose one; if I could change places between them, that is, if parrot could come first than goose, I would be able to fit three songs in the first page instead of just two:

I was wondering if there is a way to emulate some sort of float placement behaviour. Note that I'm well aware the problem is way harder than it looks. :) This is partitioning of regions and one interesting area of research in artificial intelligence. :)

Also note that I can live with a very naive solution, if any. I also accept a No, that isn't possible answer. :)

_{It's quite ironic that I have a paper with an approach on tackling this subject. :) The problem is: the method I discuss employs several variables that aren't available in the TeX context. :(}

Answer 1

Longer post

I would like to present you my solution. I have used a big gun: LuaTeX. The algorithm can be described as follows:

• Send LuaTeX \textheight and \columnwidth to save them.
• Process all the items/songs virtually in the box and send the heights to the LuaTeX.
• Optimize it. Send information to the terminal continuously during the process.
• Inform us about the rearrangements of the songs.
• Typeset the results into a real document (PDF).

When we enter your original data we are getting this information in the terminal:

Processing page 1...
Adding...   8   to  1
Processing page 2...
Adding...   3   to  2
Processing page 3...
Adding...   5   to  4
Processing page 4...
Adding...   7   to  6

  1  402.24998   1
  2  284.09523   2
  3  256.30554   2
  4  234.94444   3
  5  198.94444   3
  6  198.94444   4
  7  174.94444   4
  8  138.94444   1
The highest processed page is 4.

The first column is a number of the song, the second column is its height and the last column is a column where a song will be placed. Meaning that in the first column will be songs 1+8, in the second column songs 2+3 (it will be page 1), in the third column songs 4+5 and in the last one there will be songs 6+7 (that will form page 2). I believe that one picture is worth a thousand words.

Please allow me a couple of words about the optimization phase. There is no miracle going on (just kidding, Father).

• The first step is to order the heights in descending order.
• Start a new column.
• Then select the first unassigned song from top and put it on that page.
• Test all the unassigned songs in decreasing order if they fit in that column in remaining space. Mark them if they do.
• Move on to the next page until all songs are assigned.

In the original data we can see that we are having only two songs per column. I played a bit with it, I added two new songs and I started manually (it can be programmed as well) increasing the number of words to fill those two pages completely. This is it, if you increase any number by 1, you would get three pages. I have done it just for fun.

\repeatword{119}{duck}
\repeatword{234}{goose}
\repeatword{132}{parrot}
\repeatword{108}{falcon}
\repeatword{153}{owl}
\repeatword{154}{swan}
\repeatword{100}{chicken}
\repeatword{54}{mallard}
\repeatword{64}{pivo}
\repeatword{56}{mali}

The terminal says (in our example one page is one column):

Processing page 1...
Adding...   10  to  1
Processing page 2...
Adding...   3   to  2
Processing page 3...
Adding...   5   to  4
Adding...   9   to  4
Processing page 4...
Adding...   7   to  6
Adding...   8   to  6

  1  462.24998   1
  2  284.09523   2
  3  256.30554   2
  4  234.94444   3
  5  210.94444   3
  6  198.94444   4
  7  198.94444   4
  8  138.94444   4
  9   92.62303   3
 10   78.94444   1
The highest processed page is 4.

In plain English, it means these arrangements: songs 1+10 (column 1), 2+3 (column 2), 4+5+9 (column 3), and finally songs 6+7+8 will be typeset in the last column. This is a preview of the PDF file.

We cannot squeeze another word there. The only chance to get more words in that document would be to delete longer words, e.g. chicken, and then add smaller words instead, e.g. owl.

In the source code there is a new condition named \ifmychoice to choose data from the original data or the updated ones. This is a fine starting point playing with it and experimenting on your own.

I must say that my Lua code is far from optimal, I had some difficulties as I wasn't able to call table.maxn or tonumber as an argument of print, well, I used some workarounds.

There is a plenty of room for further improvements:

• Measuring and typesetting could be done in one run only (I am using two runs), I didn't risk it because of the memory limitations.
• Lua tables with removing items should be used during testing phase, otherwise I am testing already assigned items and skipping them repeteadly, it costs nothing on a small scale, but it would cost a lot (time, money) in real typesetting projects.
• I was thinking to replace commands, e.g. \repeatword{100}{duck}, by plain data, e.g. 100 duck, but it turned out to be a bad idea as the content for typesetting phase is unclear, generally speaking, of course.
• I am not sure if reports sent to the terminal are flushed, or not. That would require another small testing.
• There could be second or even more keys for sorting purposes, I am using just those heights (plus unintentionally the number of the song but it is done automatically as it is the order of receiving data from TeX commands).
• The program could sing a song for us. :-)

I enclose the code. Good luck with your songbook!

%! lualatex arrangeme.tex
\batchmode % Let's have some TeX fun...

\documentclass[letterpaper]{article}
\pagestyle{empty}
\parindent=0pt
\usepackage{xcolor}
\usepackage{multicol}
\usepackage{luacode}

\ifx\relax % A new approach and syntax...
\usepackage{xparse}
\ExplSyntaxOn % Wow, but I am not going to use it...
\NewDocumentCommand{\repeatword}{mm}{\getcolour\prg_replicate:nn{#1}{#2\ }\par}
\bool_gset_true:N\g_tmpa_bool
\NewDocumentCommand{\getcolour}{}
  {\bool_if:nTF\g_tmpa_bool {\color{blue}\bool_gset_false:N\g_tmpa_bool}{\color{red}\bool_gset_true:N\g_tmpa_bool}}
\NewDocumentEnvironment{textblock}{}{\setlength{\parindent}{0pt}\getcolour}{}
\ExplSyntaxOff
\fi % End of \ifx...


\begin{document}
% Initializing all the TeX variables...
\newcount\mywords
\newif\ifmycolour
\newbox\mybox
\newsavebox\mysavebox
\newdimen\mycolumn
\newdimen\mytotal
\newif\ifmyrun
\newcount\bigcount

% What is the column width? Save it!
\begin{multicols*}{2}
\global\mycolumn=\columnwidth
\end{multicols*}
% A width of the column is \the\mycolumn.

\bigcount=0
\def\repeatword#1#2{%
\savebox\mybox{\parbox{\mycolumn}{%
  \ifmycolour % Change of used colour...
    \color{blue}\global\mycolourfalse\else
    \color{red}\global\mycolourtrue
  \fi
  \mywords=0
  \loop % Typesetting all the words...
    \advance\mywords by 1%
    #2 % Send me the word and the space...
  \ifnum\mywords<#1\repeat
  }}% End of \parbox and \savebox...
  %Width of the box is \the\wd\mybox.\par
  %Height of the box is \the\ht\mybox.\par
  %Depth of the box is \the\dp\mybox.\par
  \mytotal=\ht\mybox
  \advance\mytotal by \dp\mybox\medskip
\ifnum\bigcount=0
  \directlua{collectthem("\the\mytotal","#1","#2")}% Analyse it only first!
\else
  \copy\mybox % This is the second run: typeset it, don't analyse it again.
\fi
  }% End of \repeatword...


\begin{luacode*}
-- An easy part of the code...
function collectme (textheighttemp)
  textheight=string.gsub(textheighttemp,"pt","") -- Substract "pt" from dimension.
  textheight=tonumber(textheight)
  --textheight=textheighttemp
  --print("textheight",textheight,"\n")
  --print("mycolumn",mycolumn)
end--of collectme

local songheight={}
function collectthem(songheighttemp,tosavea,tosaveb)
  --print(tosavea,tosaveb)
  temp=string.gsub(songheighttemp,"pt","")
  temp=tonumber(temp)
  table.insert(songheight, {temp,0,tosavea,tosaveb})
end--of collectthem


-- The core of the document processing...
function processthem()
table.sort(songheight, function(a,b) return a[1]>b[1] end)
for k, v in pairs (songheight) do 
  mymax=k
--mymax=table.maxn(songheight) -- This didn't work for me.
end

local malpage=0
for i=1,mymax do -- 
myvalue=songheight[i][1]
-- To be typeset on that page/column...

if songheight[i][2]==0 then -- Continue only if this is an unassigned item...

malpage=malpage+1
songheight[i][2]=malpage 
textpage=tostring(malpage)
print ("Processing page "..textpage.."...")

-- Could we add more items to that one? 
-- Two items or even more? Test them all from the highest values...
for j=i+1, mymax do

-- The main part of the core function...
-- This part can be optimized by a new table a removing items from it, instead of retesting already assigned values.
if songheight[j][2]==0 and myvalue+songheight[j][1]<textheight then
  print("Adding...",j,"to",i)
  myvalue=myvalue+songheight[j][1] -- Adding height.
  songheight[j][2]=malpage -- This item is occupied from now on.
end --of if songheight
end --of for j, the inner cycle
end --of unassigned item
end --of for i, the outer cycle

print() --An empty line, printing final results
for k, v in pairs (songheight) do
  print (string.format("%3s%11s%4s", k, v[1], v[2]))
end

textpage=tostring(malpage)
print("The highest processed page is "..textpage..".")
end --of function typesetthem


-- We will have a big time now... Typeset it all!
-- I rather typeset it again than hold all pieces in memory...
function typesetthem()
local finalpages=0
table.sort(songheight, function(a,b) return a[2]<b[2] end)
for k, v in pairs (songheight) do
if v[2]~=finalpage then 
  tex.print("\\vfill\\columnbreak")
  finalpage=v[2]
end --of if v[2]
--print(v[1],v[2],v[3],v[4])
tex.print("\\repeatword{"..v[3].."}{"..v[4].."}")
end --of for k, v
end --of function typesetthem
\end{luacode*}

\def\allsongs#1{%
  \directlua{collectme("\the\textheight")}% Save the textheight...
    #1% Collect all the necessary data...
  \global\bigcount=1% The second round of the same computations (saving memory)...
  \directlua{processthem()}% Rearranging items...
  \directlua{typesetthem()}% Typesetting them...
  }% End of \allsongs...

\newif\ifmychoice
% Do I want to process the original data?
%\mychoicetrue % or 
\mychoicefalse
\begin{multicols*}{2}
\allsongs{% To get dimensions and typeset the songs...
\ifmychoice % Yes, I do!
% The original values...
\repeatword{100}{duck}
\repeatword{200}{goose}
\repeatword{130}{parrot}
\repeatword{100}{falcon}
\repeatword{150}{owl}
\repeatword{150}{swan}
\repeatword{100}{chicken}
\repeatword{50}{mallard}
\else % No, I don't!
% The updated values (manually I must say)...
\repeatword{119}{duck}
\repeatword{234}{goose}
\repeatword{132}{parrot}
\repeatword{108}{falcon}
\repeatword{153}{owl}
\repeatword{154}{swan}
\repeatword{100}{chicken}
\repeatword{54}{mallard}
\repeatword{64}{pivo}
\repeatword{56}{mali}
\fi
}% End of \allsongs...
\end{multicols*}

\end{document}