% \iffalse meta-comment
% Copyright 2020 Nelson Lago <lago@ime.usp.br>
%
% This work may be distributed and/or modified under the conditions of the
% LaTeX Project Public License, either version 1.3 of this license or (at
% your option) any later version. The latest version of this license can be
% found at http://www.latex-project.org/lppl.txt and version 1.3 or later
% is part of all distributions of LaTeX version 2005/12/01 or later.
%
% This work has the LPPL maintenance status `maintained'.
%
% The Current Maintainer of this work is Nelson Lago <lago@ime.usp.br>.
%
% \fi
% \iffalse
%
%<package>\NeedsTeXFormat{LaTeX2e}[2015/01/01]
%<package>\ProvidesPackage{pbalance}[2020/12/03 v1.0 Poor man's balance]
%
%<*driver>

\documentclass{ltxdoc}

\usepackage[hyperref,svgnames,x11names,table]{xcolor}
\usepackage{url}
\urlstyle{sf}
\usepackage{hyperref}
\hypersetup{
  pdfborder={0 0 .6},
  pdfborderstyle={/S/U/W .6},
  urlbordercolor=DodgerBlue,
  citebordercolor=White,
  linkbordercolor=White,
  filebordercolor=White,
}

\usepackage[draft]{pbalance}
\makeatletter
\dimgdef\@PBtmpHeight{0pt}
\dimgdef\@PBtmpLeftHeight{0pt}
\dimgdef\@PBtmpLeftFloatsHeight{0pt}
\dimgdef\@PBtmpRightHeight{0pt}
\dimgdef\@PBtmpRightFloatsHeight{0pt}
\dimgdef\@PBtmpUsedLeft{0pt}
\dimgdef\@PBtmpUsedRight{0pt}
\makeatother

\usepackage{libertinus}
\usepackage[scale=.85]{sourcecodepro}

%%\EnableCrossrefs
%%\CodelineIndex
%%\RecordChanges

%%\OnlyDescription

\begin{document}
\DocInput{pbalance.dtx}
\end{document}

%</driver>
%
% \fi
%
% \CheckSum{0}
%
% \changes{v1.0}{2020/09/14}{Initial version}
%
% \GetFileInfo{pbalance.sty}
%
% \title{The \textsf{pbalance} (poor man's balance) package\thanks{This
% document corresponds to \textsf{pbalance}~\fileversion, dated~\filedate.}}
%
% \author{
% Nelson Lago\\
% \texttt{lago@ime.usp.br}\\
% ~\\
% \url{https://gitlab.com/lago/pbalance}
%}
%
% \maketitle
%
% \begin{abstract}
%
% This package tries to \emph{safely} make the columns on the last page
% of a two-column document have approximately the same height. It should
% ``just work'' without user intervention, which is particularly useful
% for class authors, but also offers the user a command to control the
% result. There are, however, three caveats:
%
% \begin{enumerate}
% \item Results are adequate, but often not optimal;
% \item In some cases, the package may give up (the document is
%       generated correctly but the last page is not balanced);
% \item The package demands additional \LaTeX{} passes.
% \end{enumerate}
%
% \end{abstract}
%
% \section{Introduction and usage}
%
% First things first: this package is a \textbf{hack}. It is also
% \textbf{beta} quality. However, I believe it is \emph{safe},
% i.e., it should not generate incorrect output.
%
% In a two-column document, it is desirable for the columns in the last
% page to have the same height (the columns should be ``balanced''). Two
% packages (\texttt{balance} and \texttt{flushend}) try to provide this
% in \LaTeX, but both may generate defective output in some circumstances.
% This package tries to solve this problem.
%
% Balancing is often not possible: imagine a document with an odd number
% of lines on the last page, or with ten lines of text together with an
% image that takes the height of fifteen lines of text, or a document where
% making columns the same height would leave a sectioning comand at the
% bottom of the first column etc. Since such cases happen often, we consider
% it enough for the columns to be ``not too unequal'', even when equal
% heights might be possible (the algorithm cannot deliver better results
% and, in fact, striving to make columns exactly the same height with it
% may sometimes yield poor results, so we do not even try).
%
% To use the package, add \verb|\usepackage{pbalance}| to the preamble
% and things should ``just work''. However, the document will take more
% \LaTeX{} passes to compile, and minute changes to it that would normally
% need one additional \LaTeX{} pass will likely need three.
%
% If the last page does not have floats, footnotes, or marginpars, the
% package simply uses \verb|\balance|, from the \texttt{balance} package;
% otherwise it uses its own algorithm. You may instead use
% \verb|\shrinkLastPage{some-measurement}| to manually define how much
% shorter the first column of the last page should be. This, however, will
% not eliminate the need for extra passes (the package needs to find out
% which page is the last).
%
% \section{How does it work}
%
% This package works on two fronts:
%
% \begin{enumerate}
%
% \item It uses a \LaTeX{} pass to gather information: which is the last page?
%       Does it have floats? Footnotes? How much free space in each column?
%
% \item It uses this information in a subsequent pass to balance the last
%       page. If there are no floats or footnotes, it uses the balance
%       package; otherwise it uses the measurements collected to shrink
%       the first column (using \verb|\enlargethispage|) by a
%       ``reasonable'' amount.
%
% \end{enumerate}
%
% If measurements change between passes, this means the document was
% edited, so we forget the previously gathered data and start over.
% However, the package cannot detect changes that happen between the
% ``collect data'' pass and the ``balance for the first time'' pass:
% it has to assume that any change at this point is caused by the fact
% that we started balancing (it can, however, detect if the last text
% page changed; if this happens, we give up balancing). If the change is
% small, that is acceptable: we are not aiming at balancing perfectly
% anyway. If it is a big change (for example, the addition of the
% bibliography block), results will suffer.
%
% To prevent this, it would be ideal to only start the process after all
% passes needed to stabilize the document have run. In practice, however,
% this would be too hard to detect. What we do instead is simply wait for
% two consecutive passes to result in columns of the same size in the
% last page. When this happens, we proceed to balance in the next pass
% and assume (quite reasonably) that, as long as the document is not
% modified, the effect of further passes in the last page is small, so
% ignoring it disturbs the balancing only slightly\footnote{Like I said
% on the introduction: this package is a hack.}.
%
% \section{TODO / wish list}
%
% Some useful stuff we should consider implementing:
%
% \begin{itemize}
%
%   \item add \verb|\if@twocolumn| tests to prevent crashes and
%         other problems;
%
%   \item add options to (1) allow using the balance package on pages with
%         floats and (2) completely disable the balance package;
%
%   \item make the mechanism able to work with any page, not just the last,
%         and with more than one page at once. This is useful for book
%         chapters, for example;
%
%   \item on top of that:
%     \begin{enumerate}
%       \item create command to manually indicate the page numbers to balance
%       \item create command similar to \verb|\balance| from the
%             \texttt{balance} package
%       \item allow user to set manual balancing for each page independently
%     \end{enumerate}
%
% \end{itemize}
%
% \StopEventually{}
%
% \section{The implementation}
%
% We define \verb|\@PBlastPage| using \texttt{zref-abspage}; It is the page
% number for the last page of text. This might \emph{not} be the last page
% of the document: there may be one or more float pages after it. Still,
% it \emph{is} the page we want to balance. We do not act on it, however;
% instead, we save its value to the aux file as \verb|\@PBprevLastPage| and
% proceed to balance on the next \LaTeX{} pass.
%
% We also define two toggles:
%
% \begin{description}
% \item[\texttt{@PBstabilized}] There have been a few passes
%      already and the document has apparently stabilized.
% \item[\texttt{@PBimpossible}] We tried to balance on a
%      previous pass and failed.
% \end{description}
%
% \subsection{Initialization, required packages etc.}
%
% Besides some other required packages, here we load the \texttt{balance}
% package; if there are no floats or footnotes involved, we will simply use
% it. We need to load it after we modify \verb|\@outputdblcol|, so we use
% \verb|\AtEndOfPackage|.
%
% We also define the \texttt{draft} option, which disables processing.
%
%    \begin{macrocode}

\RequirePackage{etoolbox}
\RequirePackage{expl3}
\RequirePackage{atbegshi} % Manipulate the page output routine
\RequirePackage{atveryend} % Write to the aux file after processing ends
\RequirePackage{zref-abspage} % Figure out the current page

\AtEndOfPackage{\RequirePackage{balance}}

% See https://github.com/latex3/latex2e/issues/399#issuecomment-703081793
\gdef \@reinserts{%
  \ifvbox\@kludgeins\insert\@kludgeins
                      {\unvbox\@kludgeins}\fi
  \ifvoid\footins\else\insert\footins{\unvbox\footins}\fi
}

\providetoggle{@PBstabilized}
\providetoggle{@PBimpossible}

\newtoggle{@PBdraft}
\DeclareOption{draft}{\toggletrue{@PBdraft}}
\ProcessOptions\relax

%    \end{macrocode}

% \subsection{The balancing front}
%
% The basic balancing process is reasonably simple: right before each
% new page, check whether it should be balanced. If so, add the adequate
% code to the top of the page (either call \verb|\balance|, from the
% \texttt{balance} package, or add \verb|\enlargethispage|).
%
%    \begin{macrocode}

% Right before the first page
\AtBeginDocument{
  \@PBifShouldBalanceNascentPage
    {\@PBStartBalancing}
    {}
}

% Right before all other pages
\AtBeginShipout{
  \@PBifShouldBalanceNascentPage
    {\@PBStartBalancing}
    {}
}

\newcommand\@PBifShouldBalanceNascentPage[2]{
  \ifboolexpr
    {
      togl {@PBdraft}
      or not togl {@PBstabilized}
      or test {\ifdefvoid{\@PBprevLastPage}}
    }
    {#2}
    {
      % abspage refers to the finished page, not the nascent page
      \ifnumcomp{\@PBprevLastPage - 1}{=}{\value{abspage}} 
        {#1}
        {#2}
    }
}

% Let's give the user a chance to manually define what to do
\newcommand\shrinkLastPage[1]{\dimgdef\@PBslack{#1}}

\newcommand\@PBStartBalancing{
  \ifdefvoid{\@PBslack}
    {\@PBautomaticBalance}
    {\@PBshrinkPage}
}

\newcommand\@PBautomaticBalance{
  \@PBifBalancePossible
    {
      \@PBifBalancePkgPossible
        {\balance} % easy peasy, use the balance package
        {
          \@PBifPoorBalancePossible
            {
              % use the poor man's balance algorithm
              \@PBcalculateShrinkage
              \@PBshrinkPage
            }
            {}
        }
    }
    {}
}

% Calculate how much we should shrink the left column of the last
% page based on the measurements we took on previous LaTeX passes.
\newcommand\@PBcalculateShrinkage{

  % Let's use some shorter names, please
  \dimdef\@PBtmpH{\csuse{@PBunbalpg\@Roman{\@PBprevLastPage}Height}}
  \dimdef\@PBtmpUL{\csuse{@PBunbalpg\@Roman{\@PBprevLastPage}UsedLeft}}
  \dimdef\@PBtmpUR{\csuse{@PBunbalpg\@Roman{\@PBprevLastPage}UsedRight}}

  \dimdef\@PBtmpLH{\csuse{@PBunbalpg\@Roman{\@PBprevLastPage}LeftHeight}}
  \dimdef\@PBtmpLFH{\csuse{@PBunbalpg\@Roman{\@PBprevLastPage}LeftFloatsHeight}}
  \dimdef\@PBtmpRH{\csuse{@PBunbalpg\@Roman{\@PBprevLastPage}RightHeight}}
  \dimdef\@PBtmpRFH{\csuse{@PBunbalpg\@Roman{\@PBprevLastPage}RightFloatsHeight}}

  % Figure out the amount of unused space on the last page (both
  % cols); we will reduce the first column height by half that amount
  \dimgdef\@PBslack{2\dimexpr\@PBtmpH\relax - \@PBtmpUL - \@PBtmpUR}
  \dimgdef\@PBslack{.5\dimexpr\@PBslack\relax}

  % Actually, I lied. While half, as said above, sometimes yields
  % perfectly balanced columns, that is often not the case (the page
  % may have an odd number of lines, or textheight may not be a
  % multiple of baselineskip, or there may be glues etc.). Sometimes
  % the difference is very small, less than a line, which does not
  % look good at all, and sometimes the right column is slightly
  % higher than the left, which is also not ideal. Here, we force
  % the left column to always be somewhat taller than the left; the
  % result is often ``better''.
  \dimgdef\@PBslack{\@PBslack - 1.5\baselineskip}

  % If necessary, reduce @PBslack to prevent LaTeX from adding a page
  \@PBsafetyCheck
}

\def\@PBshrinkPage{
  % Zero obviously means ``do nothing''. We could
  % ``enlarge'' by 0, but IDK, maybe that would
  % trigger another LaTeX pass or something.
  \ifdimcomp{\@PBslack}{=}{0pt}
    {}
    {
      % Shrink the first column
      \enlargethispage{-\@PBslack}

      % Modify the behavior of \@outputdblcol
      % to raise footnotes in the second column.
      \global\let\@PBbalanceSecondColumn\@PBrealBalanceSecondColumn
    }
}

% If there are footnotes on the right column, it is better to
% ``push'' them up to be aligned with the end of the left column,
% especially if there are footnotes on the left column too. We
% do this by manipulating \@textbottom in \@outputdblcol.
\pretocmd{\@outputdblcol}{\@PBbalanceSecondColumn}{}{}

\let\@PBbalanceSecondColumn\relax

\def\@PBrealBalanceSecondColumn{
    \if@firstcolumn
      % Affects the next column
      \global\let\@PBorigtextbottom\@textbottom
      \gdef\@textbottom{\vskip \@PBslack plus .0001fil minus 10000fill\relax \@PBorigtextbottom}
    \else
      % Back to normal before starting the next page
      \global\let\@textbottom\@PBorigtextbottom
      \global\let\@PBbalanceSecondColumn\relax
    \fi
}

%    \end{macrocode}

% \subsection{The measuring front}
% For the mechanism above to work, we need to know:
%
% \begin{enumerate}
% \item The page number of the last page;
% \item Whether the last page has floats, footnotes etc.;
% \item The available height in the last page;
% \item The height of the columns in the last page.
% \end{enumerate}
%
% Let's collect this info for every page.
%
% \subsubsection{Are there floats, footnotes, or marginpars in the last page?}
%
%    \begin{macrocode}

% To check whether there are floats etc. in the last page,
% we will copy the fancyhdr package:
% https://tex.stackexchange.com/questions/56673/is-there-a-way-to-determine-if-there-is-a-float-on-a-page
% But we add the tests to a different place.
\newcommand\@PBifmidfloat[2]{\ifx\@midlist\empty #2\else #1\fi}
\newcommand\@PBiftopfloat[2]{\ifx\@toplist\empty #2\else #1\fi}
\newcommand\@PBifbotfloat[2]{\ifx\@botlist\empty #2\else #1\fi}
\newcommand\@PBiffootnote[2]{\ifvoid\footins #2\else #1\fi}
\newcommand\@PBiffloatcol[2]{\if@fcolmade #1\else #2\fi}
% dbltop floats are apparently ok with the balance package
%%%\newcommand\@PBifdbltopfloat[2]{\ifx\@dbltoplist\empty #2\else #1\fi}
% dblbotlist only exists with package stfloats
\newcommand\@PBifdblbotfloat[2]{%
  \ifdefvoid{\@dblbotlist}
    {#2}
    {\ifx\@dblbotlist\empty #2\else #1\fi}%
}

% If there are footnotes, floats or marginpars in
% the page, we should not use the balance package
\newtoggle{@PBtmpHasFootnotes}
\newtoggle{@PBtmpHasFloats}
\newtoggle{@PBtmpHasMarginpars}

\def\@PBcollectPageInfo{

  \ifboolexpr
    {
      test {\@PBifmidfloat} or test {\@PBiftopfloat} or
      test {\@PBifbotfloat} or test {\@PBifdblbotfloat}
    }
    {\global\toggletrue{@PBtmpHasFloats}}
    {}

  \@PBiffootnote
    {\global\toggletrue{@PBtmpHasFootnotes}}
    {}
}

\pretocmd{\@makecol}{\@PBcollectPageInfo}{}{}

% This only gets called if there is a marginpar, so that's easy
\pretocmd{\@addmarginpar}{\global\toggletrue{@PBtmpHasMarginpars}}{}{}

%    \end{macrocode}
%
% \subsubsection{What are the sizes of the floats in the left column?}
%
%    \begin{macrocode}

\ExplSyntaxOn
\seq_gclear_new:N \@PBtmpLeftFloatHeights
\seq_gclear_new:N \@PBtmpLeftFloatSpacesBelow
\def\@PBcollectFloatHeights{
  \if@firstcolumn
    \dimdef\@PBfloatHeight{\@textfloatsheight - \@PBtmpHeightBefore}
    \ifdimcomp{\@PBfloatHeight}{>}{0pt}
      {
        \global\seq_put_right:NV \@PBtmpLeftFloatHeights \@PBfloatHeight

        \dimdef\@PBspaceBelow{\@colroom - \@pageht - \@PBfloatHeight}
        % within \@addtocurcol, \@pageht corresponds to all
        % currently used space in the column, including footnotes
        % (check \@specialoutput in the LaTeX kernel). Let's
        % exclude the footnotes, we only want the space below
        % the float.
        \ifvoid\footins\else
          \dimdef\@PBspaceBelow{\@PBspaceBelow + \ht\footins + \skip\footins + \dp\footins}
        \fi

        % No idea why, but this can happen; maybe because of the page depth?
        \ifdimcomp{\@PBspaceBelow}{<}{0pt}
          {\dimdef\@PBspaceBelow{0pt}}
          {}

        \global\seq_put_right:NV \@PBtmpLeftFloatSpacesBelow \@PBspaceBelow
      }
      {}
  \fi
}
\ExplSyntaxOff

\pretocmd{\@addtocurcol}{\dimgdef{\@PBtmpHeightBefore}{\@textfloatsheight}}{}{}
\apptocmd{\@addtocurcol}{\@PBcollectFloatHeights}{}{}

%    \end{macrocode}
%
% \subsubsection{What is the size of each column? Is there a float column / floatpage?}
%
%    \begin{macrocode}

% If there is a float column in the page, it makes no sense to try to
% balance; if both columns are float columns, this page cannot be the
% final text page, i.e., we want to balance some other page.
\newtoggle{@PBtmpHasFloatcol}
\newtoggle{@PBtmpIsFloatPage}

\newcommand\@PBcollectColumnInfo{

  \if@firstcolumn

    \@PBiffloatcol
      {\global\toggletrue{@PBtmpHasFloatcol}}
      {}

    % Available vertical space excluding
    % dblfloats; the same for both columns
    \dimgdef\@PBtmpHeight{\@colht}

    % Available vertical space excluding top/bottom floats
    \dimgdef\@PBtmpLeftHeight{\@colroom}

    % Space used by \texttt{here} floats
    \dimgdef\@PBtmpLeftFloatsHeight{\@textfloatsheight}

  \else

    \@PBiffloatcol
      {
        \iftoggle{@PBtmpHasFloatcol}
          {\global\toggletrue{@PBtmpIsFloatPage}}
          {\global\toggletrue{@PBtmpHasFloatcol}}
      }
      {}

    \dimgdef\@PBtmpRightHeight{\@colroom}
    \dimgdef\@PBtmpRightFloatsHeight{\@textfloatsheight}

    \setbox\@tempboxa=\copy\@leftcolumn
    \setbox\@tempboxa=\vbox{\unvbox\@tempboxa\unskip\unskip}
    \dimgdef\@PBtmpUsedLeft{\ht\@tempboxa\relax}

    \setbox\@tempboxa=\copy\@outputbox
    \setbox\@tempboxa=\vbox{\unvbox\@tempboxa\unskip\unskip}
    \dimgdef\@PBtmpUsedRight{\ht\@tempboxa\relax}
  \fi
}

% The default LaTeX macro
\pretocmd{\@outputdblcol}{\@PBcollectColumnInfo}{}{}

% The version from the balance package
\AtEndOfPackage{
  \pretocmd{\@BAdblcol}{\@PBcollectColumnInfo}{}{}
  % Revert \balance before next page if it exists (it might be a float page)
  \patchcmd{\@BAdblcol}{\endgroup}{\endgroup\nobalance}{}{}
}

%    \end{macrocode}
%
% \subsubsection{Analyze the obtained information}
%
% We have inserted the hooks we need to collect data during
% the processing of each page and column. Now we inspect the
% collected data after each page is finalized.
%
%    \begin{macrocode}

\ExplSyntaxOn
\AtBeginShipout{
  \ifboolexpr
    {
      % A float page is not the last text page, ignore
      togl {@PBtmpIsFloatPage}
      or
      % A page with a float column on the left and an empty
      % column on the right is not the last text page, ignore
      (
        togl {@PBtmpHasFloatcol}
        and
        test {\ifdimcomp{\@PBtmpUsedRight}{=}{\topskip}}
      )
    }
    {}
    {
      % This page is a candidate to be the last page
      \xdef\@PBlastPage{\the\value{abspage}}
      \@PBcopyPageData{tmp}{candidate}
    }

    % Reset before processing next page
    \global\togglefalse{@PBtmpHasFloats}
    \global\togglefalse{@PBtmpHasFloatcol}
    \global\togglefalse{@PBtmpHasFootnotes}
    \global\togglefalse{@PBtmpHasMarginpars}
    \global\togglefalse{@PBtmpIsFloatPage}

    \seq_gclear_new:N \@PBtmpLeftFloatHeights
    \seq_gclear_new:N \@PBtmpLeftFloatSpacesBelow
}
\ExplSyntaxOff

%    \end{macrocode}
%
% All pages processed, the last candidate page is actually the last page.
% Instead of continuing to use the \texttt{@PBcandidate*} macros we already
% have, we will keep the information we just gathered associated with the
% page number. We do this because, in the future, we may want to add suport
% for balancing multiple pages (such as the last page of each chapter) and
% not only the last one. This also makes it easier to handle the situation
% where the document was modified and the last page has changed.
%
%    \begin{macrocode}

\AfterLastShipout{\@PBcopyPageData{candidate}{pg\@Roman{\@PBlastPage}}}

%    \end{macrocode}
%
% \subsubsection{Saving measurements}
% The whole document has already been processed and data about the last
% page has been collected in macros with names \texttt{@PBpgNUM*}. We now
% process this collected data and save whatever is relevant in the aux
% file for the next \LaTeX{} pass.
%
% In the first \LaTeX{} pass, we will save data to the aux file in macros
% with names \texttt{@PBunbalpgNUM*}. That is all we need for balancing.
% However, to detect whether the document has changed and, therefore,
% whether we should re-balance, we will also record the same data after
% balancing (during the second pass) in macros with names
% \texttt{@PBbalpgNUM*}. If, in the third or later \LaTeX{} passes,
% \texttt{@PBbalpgNUM*} differ from \texttt{@PBpgNUM*}, the document
% has been changed and we need to re-balance.
%
% So, we have:
%
% \begin{description}
% \item[\texttt{@PBpgNUM*}] data collected during the current pass;
% \item[\texttt{@PBunbalpgNUM*}] data collected in the first pass;
% \item[\texttt{@PBbalpgNUM*}] data collected in the second pass (after
%      balancing); in subsequent passes, these should always be equal
%      to \texttt{@PBpgNUM*}.
% \end{description}
%
% The last two are saved to / read from the aux file.
%
%    \begin{macrocode}

% Make sure the document has stabilized before using \@PBmanageBalancingPasses
\AfterLastShipout{
  % Reset \@PBimpossible if we are in draft mode,
  % so the user can start over if they want to.
  \iftoggle{@PBdraft}{\togglefalse{@PBimpossible}}{}

  \ifboolexpr{togl {@PBdraft} or togl {@PBimpossible}}
    {}
    {
      \ifdefvoid{\@PBprevLastPage}
        {\@PBsaveUnbalancedInfo\@PBnotifyRerun} % First pass
        {
          \iftoggle{@PBstabilized}
            {\@PBmanageBalancingPasses}
            {
              \@PBifSomethingChanged[unbal]
                % Document still changing; discard data from previous pass
                {\@PBsaveUnbalancedInfo[update]\@PBnotifyRerun}
                % No changes, so let's balance from now on (once @PBstabilized
                % becomes true, it never reverts back to false, unless the aux
                % file is deleted).
                {\toggletrue{@PBstabilized}\@PBsaveUnbalancedInfo\@PBnotifyRerun}
            }
        }
      \@PBsaveToggle{@PBstabilized}
    }

  \@PBsaveToggle{@PBimpossible}
  \immediate\write\@mainaux{\gdef\string\@PBprevLastPhysPage{\the\value{abspage}}}
}

\newcommand\@PBmanageBalancingPasses{
  % This is the second pass or later after we started balancing

  \providetoggle{@PBpg\@Roman{\@PBlastPage}alreadyBalanced}

  \iftoggle{@PBpg\@Roman{\@PBlastPage}alreadyBalanced}
    {
      % Third pass or later; document was already
      % balanced, so there should be no more changes
      \@PBifSomethingChanged
        % The document has changed, so we need to measure
        % stuff again; clear aux file and start over.
        {\@PBnotifyRerun}
        % Nothing changed, just write the same info down
        {\@PBsaveUnbalancedInfo\@PBsaveBalancedInfo}
    }
    % Second pass, which means something did change: we have just
    % balanced the columns for the first time.
    {
      \xdef\@tempa{\the\value{abspage}}
      \ifboolexpr
        {
          test {\ifdefstrequal{\@PBprevLastPage}{\@PBlastPage}}
          and
          test {\ifdefstrequal{\@PBprevLastPhysPage}{\@tempa}}
        }
        % All is well; save the new info
        {\@PBsaveUnbalancedInfo\@PBsaveBalancedInfo}
        % Oh, no! As we attempted to balance, we actually changed
        % the number of pages (maybe we added a float page, maybe
        % we turned the last float page into a text page etc.). If
        % we continue, the document might never converge (endless
        % ``please rerun LaTeX'' messages). Let's give up balancing.
        {\toggletrue{@PBimpossible}}
    }
}

%    \end{macrocode}
%
% \subsection{Auxiliary macros}
%
%    \begin{macrocode}

\newcommand\@PBifBalancePossible[2]{
  \iftoggle{@PBunbalpg\@Roman{\@PBprevLastPage}HasFloatcol}
    {#2}
    {#1}
}

% The balance package may fail badly in the presence of footnotes:
% they may end up in the middle of the text. Marginpars may end up
% on the wrong side of the page. Floats are usually ok, but in some
% cases the columns may become very badly balanced. For ordinary
% text, it works perfectly.
\newcommand\@PBifBalancePkgPossible[2]{
  \ifboolexpr
    {
      togl {@PBunbalpg\@Roman{\@PBprevLastPage}HasFloats}
      or
      togl {@PBunbalpg\@Roman{\@PBprevLastPage}HasFootnotes}
      or
      togl {@PBunbalpg\@Roman{\@PBprevLastPage}HasMarginpars}
    }
    {#2}
    {#1}
}

%    \end{macrocode}
%
% We only want to balance if:
%
% \begin{enumerate}
%
% \item The left column is higher than the right one. If that is not the
%       case, either things are already balanced or the right column is
%       higher, which means \LaTeX{} was forced into a bad solution already.
%
% \item This difference is ``large enough'' (6 lines), which means two things:
%     \begin{enumerate}
%
%         \item There will be an actual improvement in the result.
%
%         \item There is plenty of free space on the right column, so even if
%               our changes happen to take more space than before, \LaTeX{} will
%               hopefully not add a new page (but it might make the right
%               column higher than the left, which is not so great).
%     \end{enumerate}
%
% \end{enumerate}
%
% If there is material only on the left column, we want to balance even
% if the difference in height is not ``large enough'', as long as there
% are more than 4 lines to split among columns. This is actually quite
% unlikely: if there is so little material, the page probably has only
% normal text and we will use the balance package.
%
%    \begin{macrocode}

\newcommand\@PBifPoorBalancePossible[2]{

  % Let's use some shorter names, please
  \dimdef\@PBtmpH{\csuse{@PBunbalpg\@Roman{\@PBprevLastPage}Height}}
  \dimdef\@PBtmpUL{\csuse{@PBunbalpg\@Roman{\@PBprevLastPage}UsedLeft}}
  \dimdef\@PBtmpUR{\csuse{@PBunbalpg\@Roman{\@PBprevLastPage}UsedRight}}

  \dimdef\@PBtmpLH{\csuse{@PBunbalpg\@Roman{\@PBprevLastPage}LeftHeight}}
  \dimdef\@PBtmpLFH{\csuse{@PBunbalpg\@Roman{\@PBprevLastPage}LeftFloatsHeight}}
  \dimdef\@PBtmpRH{\csuse{@PBunbalpg\@Roman{\@PBprevLastPage}RightHeight}}
  \dimdef\@PBtmpRFH{\csuse{@PBunbalpg\@Roman{\@PBprevLastPage}RightFloatsHeight}}

  \ifboolexpr{
    % Plenty of space on right column, difference is worth it
    test {\ifdimcomp{\@PBtmpUL}{>}{\@PBtmpUR + 6\baselineskip}}
    or
    (
      test {\ifdimcomp{\@PBtmpUL}{>}{4\baselineskip}}
      and
      test {\ifdimcomp{\@PBtmpUR}{=}{\topskip}} % column is empty
    )
  }{#1}{#2}
}

%    \end{macrocode}
%
% If there are floats, things can get messy: imagine that we want to
% shrink by 50pt, but there is a 250pt float near the end of the left
% column that won't fit after we shrink, so it will move to the right.
% What if there is no room for such a large float there? Here, we try
% to prevent this situation and shrink by a smaller amount if there
% is a float that won't fit. Note that, if the float goes to the
% right column, there will be more room for text in the left column.
% Therefore, a float will not fit only if the floats on the right
% column take too much space. So, what we do here is, starting from
% the bottom, check whether the accumulated height of the floats
% from the left column fit in the right. If we find a float that
% will not fit, we know that we should limit shrinking to the space
% below that float.
%
% In the same vein, we do not want top/bottom floats from the left
% column that were deferred from a previous page to be pushed to
% the right column. To that end, we limit the shrinking amount to
% the space on the left column not taken by top/bottom floats.

% \textbf{TODO:} Top and bottom floats may appear in two cases: (1) they
%       were generated on a previous page and deferred or (2) the user
%       chose placement options \texttt{t} or \texttt{b}, without
%       \texttt{h}. Deferred floats are not a problem: we do not reduce
%       the space available for top/bottom floats, so they should
%       continue to fit. Floats on the left column with placement
%       options \texttt{t} and \texttt{b} without \texttt{h} can be
%       a problem: \LaTeX{} only considers putting a float on the
%       top/bottom of the current column if, at the point of its
%       definition, there is enough space for it. Since we are shrinking
%       the column, it may not fit and be deferred - something the
%       algorithm does not take into consideration. However, not all is
%       lost: most likely, the user will only use such placement
%       options when trying to manually adjust the page, which
%       means they will be able to detect and work around eventual
%       problems.
%
%    \begin{macrocode}

\ExplSyntaxOn
\def\@PBsafetyCheck{

  % Let's use some shorter names, please
  \dimdef\@PBtmpH{\csuse{@PBunbalpg\@Roman{\@PBprevLastPage}Height}}
  \dimdef\@PBtmpUL{\csuse{@PBunbalpg\@Roman{\@PBprevLastPage}UsedLeft}}
  \dimdef\@PBtmpUR{\csuse{@PBunbalpg\@Roman{\@PBprevLastPage}UsedRight}}

  \dimdef\@PBtmpLH{\csuse{@PBunbalpg\@Roman{\@PBprevLastPage}LeftHeight}}
  \dimdef\@PBtmpLFH{\csuse{@PBunbalpg\@Roman{\@PBprevLastPage}LeftFloatsHeight}}
  \dimdef\@PBtmpRH{\csuse{@PBunbalpg\@Roman{\@PBprevLastPage}RightHeight}}
  \dimdef\@PBtmpRFH{\csuse{@PBunbalpg\@Roman{\@PBprevLastPage}RightFloatsHeight}}


  % Make sure we do not push top/bottom floats out of the left col
  \dimdef\@PBmaxSlack{\@PBtmpLH}

  \dimdef\@PBtmpdim{0pt}

  % Start from the bottom
  \numdef{\@PBtmpcnt}{\seq_count:c {@PBunbalpg\@Roman{\@PBprevLastPage}LeftFloatHeights}}
  \int_while_do:nNnn {\@PBtmpcnt} > {0}
    {

      \dimdef\@PBcurrentFloatHeight
        {\seq_item:cn {@PBunbalpg\@Roman{\@PBprevLastPage}LeftFloatHeights} {\@PBtmpcnt}}

      \dimdef\@PBcurrentFloatSpaceBelow
        {\seq_item:cn {@PBunbalpg\@Roman{\@PBprevLastPage}LeftFloatSpacesBelow} {\@PBtmpcnt}}

      \dimdef{\@PBtmpdim}{\@PBtmpdim + \@PBcurrentFloatHeight}

      \ifboolexpr
        {
          % Does the float fit in the second column?
          test {\ifdimcomp{\@PBtmpdim}{<}{\@PBtmpRH - \@PBtmpRFH}}
          and
          % Is there something above this float, i.e., if we move
          % this float to the next column, will anything remain?
          test
            {
               \ifdimcomp
                 {\@PBcurrentFloatSpaceBelow + \@PBcurrentFloatHeight}
                 {<}
                 {\@PBtmpLH - 6\baselineskip}
            }
        }
        {\numdef{\@PBtmpcnt}{\@PBtmpcnt - 1}} % this one is ok; check next
        {
          % this one should not be moved, we found the limit
          \ifdimcomp{\@PBmaxSlack}{>}{\@PBcurrentFloatSpaceBelow}
            {\dimdef{\@PBmaxSlack}{\@PBcurrentFloatSpaceBelow}}
            {}
          \numdef{\@PBtmpcnt}{0} % exit the loop
        }
    }

  \ifdimcomp{\@PBmaxSlack}{<}{\@PBslack}
    {\dimgdef{\@PBslack}{\@PBmaxSlack}}
    {}
}
\ExplSyntaxOff

% Compare current measurements with previous ``bal'' or ``unbal'' measurements
\newcommand\@PBifSomethingChanged[3][bal]{
  \ifdefstrequal{\@PBprevLastPage}{\@PBlastPage}
  {
    \@PBifPageDataMatches
      {pg\@Roman{\@PBlastPage}}
      {#1pg\@Roman{\@PBlastPage}}
      {#3}
      {#2}
  }
  {#2}
}

\newcommand\@PBifPageDataMatches[4]{
  \ifboolexpr{
        test {\@PBifTogglesMatch{@PB#1HasFloats}{@PB#2HasFloats}}
    and test {\@PBifTogglesMatch{@PB#1HasFloatcol}{@PB#2HasFloatcol}}
    and test {\@PBifTogglesMatch{@PB#1HasFootnotes}{@PB#2HasFootnotes}}
    and test {\@PBifTogglesMatch{@PB#1HasMarginpars}{@PB#2HasMarginpars}}
    and test {\@PBifDimensionsMatch{@PB#1Height}{@PB#2Height}}
    and test {\@PBifDimensionsMatch{@PB#1LeftHeight}{@PB#2LeftHeight}}
    and test {\@PBifDimensionsMatch{@PB#1RightHeight}{@PB#2RightHeight}}
    and test {\@PBifDimensionsMatch{@PB#1UsedLeft}{@PB#2UsedLeft}}
    and test {\@PBifDimensionsMatch{@PB#1UsedRight}{@PB#2UsedRight}}
  }
  {#3}
  {#4}
}

% https://en.wikipedia.org/wiki/XNOR_gate
\newcommand\@PBifTogglesMatch[4]{
  \ifboolexpr{(togl{#1} or not togl{#2}) and (togl{#2} or not togl{#1})}
    {#3}
    {#4}
}

\newcommand\@PBifDimensionsMatch[4]{
  \ifdimcomp{\csuse{#1}}{=}{\csuse{#2}}
    {#3}
    {#4}
}

\newcommand\@PBsaveUnbalancedInfo[1][]{

  \immediate\write\@mainaux{\gdef\string\@PBprevLastPage{\@PBlastPage}}

  \ifboolexpr{test {\ifdefvoid{\@PBprevLastPage}} or test {\ifstrequal{#1}{update}}}
    % Columns are currently unbalanced, either because this is
    % the first pass (we do not have any previous information)
    % or because the document has not stabilized yet, so any
    % previous information is unreliable. Save the information
    % we just collected as ``unbalanced''.
    {\@PBsavePageDataAs{pg\@Roman{\@PBlastPage}}{unbalpg\@Roman{\@PBlastPage}}}
    % Not the first pass, so columns are possibly balanced;
    % to save the unbalanced information, repeat what was
    % gathered during the first pass.
    {\@PBsavePageData{unbalpg\@Roman{\@PBprevLastPage}}}
}

\def\@PBsaveBalancedInfo{
  \global\toggletrue{@PBpg\@Roman{\@PBlastPage}alreadyBalanced}
  \@PBsaveToggle{@PBpg\@Roman{\@PBlastPage}alreadyBalanced}

  \@PBsavePageDataAs{pg\@Roman{\@PBlastPage}}{balpg\@Roman{\@PBlastPage}}
}

\def\@PBnotifyRerun{
  \AtVeryEndDocument{
    \PackageWarningNoLine{pbalance}
    {Last page columns not balanced. Rerun LaTeX}
  }
}

\ExplSyntaxOn
\newcommand\@PBcopyPageData[2]{

  \global\providetoggle{@PB#2HasFloats}
  \global\providetoggle{@PB#2HasFloatcol}
  \global\providetoggle{@PB#2HasFootnotes}
  \global\providetoggle{@PB#2HasMarginpars}

  \iftoggle{@PB#1HasFloats}
    {\global\toggletrue{@PB#2HasFloats}}
    {\global\togglefalse{@PB#2HasFloats}}

  \iftoggle{@PB#1HasFloatcol}
    {\global\toggletrue{@PB#2HasFloatcol}}
    {\global\togglefalse{@PB#2HasFloatcol}}

  \iftoggle{@PB#1HasFootnotes}
    {\global\toggletrue{@PB#2HasFootnotes}}
    {\global\togglefalse{@PB#2HasFootnotes}}

  \iftoggle{@PB#1HasMarginpars}
    {\global\toggletrue{@PB#2HasMarginpars}}
    {\global\togglefalse{@PB#2HasMarginpars}}

  \csdimgdef{@PB#2Height}{\csuse{@PB#1Height}}
  \csdimgdef{@PB#2LeftHeight}{\csuse{@PB#1LeftHeight}}
  \csdimgdef{@PB#2LeftFloatsHeight}{\csuse{@PB#1LeftFloatsHeight}}
  \csdimgdef{@PB#2RightHeight}{\csuse{@PB#1RightHeight}}
  \csdimgdef{@PB#2RightFloatsHeight}{\csuse{@PB#1RightFloatsHeight}}
  \csdimgdef{@PB#2UsedLeft}{\csuse{@PB#1UsedLeft}}
  \csdimgdef{@PB#2UsedRight}{\csuse{@PB#1UsedRight}}

  \seq_gclear_new:c {@PB#2LeftFloatHeights}
  \seq_gclear_new:c {@PB#2LeftFloatSpacesBelow}
  \seq_gset_eq:cc {@PB#2LeftFloatHeights} {@PB#1LeftFloatHeights}
  \seq_gset_eq:cc {@PB#2LeftFloatSpacesBelow} {@PB#1LeftFloatSpacesBelow}
}
\ExplSyntaxOff

\newcommand\@PBsavePageDataAs[2]{
  \@PBsaveDimAs{@PB#1Height}{@PB#2Height}
  \@PBsaveDimAs{@PB#1LeftHeight}{@PB#2LeftHeight}
  \@PBsaveDimAs{@PB#1LeftFloatsHeight}{@PB#2LeftFloatsHeight}
  \@PBsaveDimAs{@PB#1RightHeight}{@PB#2RightHeight}
  \@PBsaveDimAs{@PB#1RightFloatsHeight}{@PB#2RightFloatsHeight}
  \@PBsaveDimAs{@PB#1UsedLeft}{@PB#2UsedLeft}
  \@PBsaveDimAs{@PB#1UsedRight}{@PB#2UsedRight}

  \@PBsaveToggleAs{@PB#1HasFloats}{@PB#2HasFloats}
  \@PBsaveToggleAs{@PB#1HasFloatcol}{@PB#2HasFloatcol}
  \@PBsaveToggleAs{@PB#1HasFootnotes}{@PB#2HasFootnotes}
  \@PBsaveToggleAs{@PB#1HasMarginpars}{@PB#2HasMarginpars}

  \@PBsaveSeqAs{@PB#1LeftFloatHeights}{@PB#2LeftFloatHeights}
  \@PBsaveSeqAs{@PB#1LeftFloatSpacesBelow}{@PB#2LeftFloatSpacesBelow}
}

\newcommand\@PBsavePageData[1]{
  \@PBsavePageDataAs{#1}{#1}
}

\newcommand\@PBsaveToggleAs[2]{
  \immediate\write\@mainaux{\providetoggle{#2}}
  \iftoggle{#1}
    {\immediate\write\@mainaux{\global\toggletrue{#2}}}
    {\immediate\write\@mainaux{\global\togglefalse{#2}}}
}

\newcommand\@PBsaveToggle[1]{
  \@PBsaveToggleAs{#1}{#1}
}

\newcommand\@PBsaveDimAs[2]{
  \immediate\write\@mainaux{\csdimgdef{#2}{\csuse{#1}}}
}

\newcommand\@PBsaveDim[1]{
  \@PBsaveDimAs{#1}{#1}
}

\ExplSyntaxOn
\newcommand\@PBsaveSeqAs[2]{
  \immediate\write\@mainaux{\string\ExplSyntaxOn}
  \immediate\write\@mainaux{\string\seq_gclear_new:c {#2}}
  \seq_map_inline:cn {#1}
    {\immediate\write\@mainaux{\string\global\string\seq_put_right:cn {#2}{##1}}}
  \immediate\write\@mainaux{\string\ExplSyntaxOff}
}
\ExplSyntaxOff

\newcommand\@PBsaveSeq[1]{
  \@PBsaveSeqAs{#1}{#1}
}

%    \end{macrocode}
% \Finale
