我有一个仅由浮动元素组成的文档,我想对它们进行排序,以使用最少的页面。在我的例子中,每个浮动元素都包含歌词,但它们也可能是诗歌、代码片段或图像。我不在乎它们如何排序,但我希望 LaTeX 自动对它们进行重新排序,以便每页尽可能接近满页。
有没有办法用普通的 LaTeX 来实现这一点?如果没有,我想我必须编写一些代码来计算每个浮点数的大小,然后实现我自己的排序算法 - 有什么提示告诉我该怎么做吗?
下面是一个虚拟示例。在此示例中,框 2 无法放在第一页,但框 4 可以。理想情况下,结果应该只占用两页,而不是三页。
\documentclass{article}
\usepackage{float}
\floatstyle{boxed}
\newfloat{testbox}{p}{ext}
\begin{document}
\begin{testbox}
This is box one
\vspace{4in}
The end of box one%
\end{testbox}
\begin{testbox}
This is box two
\vspace{4in}
The end of box two%
\end{testbox}
\begin{testbox}
This is box three
\vspace{2in}
The end of box three%
\end{testbox}
\begin{testbox}
This is box four
\vspace{1in}
The end of box four%
\end{testbox}
\end{document}
可能的排序算法(按照 Yiannis 的要求):
Calculate the size of each box
Loop through all of the boxes:
Select the largest box
Put it on the first page which has space, starting a new page if necessary
答案1
我比 Frank 慢,因为我花了很长时间微调 LaTeX3 中的排序算法。要运行下面的代码,您应该l3sort
从svn 存储库或者等待我们决定将其移至 CTAN 上的适当实验包中。
除此之外,整个事情是你所描述的算法的一个相当简单的实现(特别是参见的结构\BinPackOutput
)。
首先将所有盒子收集到一个公共的 中
main_box
,一个接一个,跟踪每个盒子的垂直尺寸,以及它们在 中出现的位置main_box
(盒子从主盒子的底部开始堆叠,可以使用 TeX 基元 进行访问\lastbox
)。{index}{dimension}
然后按维度降序对列表进行排序。循环遍历这些对 (
\seq_map_inline:Nn \g_binpack_main_seq
)。对于每个对,依次尝试页面 (\prg_stepwise_inline:nnnn
),测试新盒子是否适合 (\dim_compare:nNnF
)。如果适合,则将盒子放在那里并跳出对可能页面的循环。如果所有页面都没有空间,则制作一个新页面,并将盒子放在那里。在步骤 3 中,我们为每一页构建一个我们计划放置在那里的盒子序列。从中提取给定的盒子
main_box
是以一种肮脏的方式完成的:删除最后一个盒子并将其分配给给定的变量。\box_gset_to_last:N
如果我们重复该分配,我们会逐个删除盒子。因此,我决定使用的方法是复制main_box
,然后删除盒子 N 次并抓取第 (N+1) 个,即 中的项目 N。main_box
框在框架中排版,我们vfil
在每个框周围添加一定量的空白。事实证明,我的特定示例非常饱满;通常,每个框之间的间距相同,因此可以很好地分布在页面上。
\documentclass{article}
\usepackage{lipsum}
\usepackage{expl3,l3sort}
\ExplSyntaxOn
\box_new:N \g_binpack_main_box
\box_new:N \g_binpack_tmpa_box
\box_new:N \g_binpack_tmpb_box
\int_new:N \g_binpack_label_int
\seq_new:N \g_binpack_main_seq
\dim_new:N \g_binpack_hsize_dim
\dim_new:N \g_binpack_vsize_dim
\dim_new:N \g_binpack_extra_dim
\int_new:N \g_binpack_page_int
\bool_new:N \g_binpack_success_bool
\newcommand{\BinPackInit}
{
\box_gclear:N \g_binpack_main_box
\box_gclear:N \g_binpack_tmpa_box
\box_gclear:N \g_binpack_tmpb_box
\seq_gclear:N \g_binpack_main_seq
\int_gzero:N \g_binpack_label_int
\int_gzero:N \g_binpack_page_int
\dim_gset:Nn \g_binpack_vsize_dim { \vsize }
\dim_gset:Nn \g_binpack_hsize_dim { \hsize - 2\fboxsep - 2\fboxrule }
\dim_gset:Nn \g_binpack_extra_dim { 2\fboxsep + 2\fboxrule }
}
\newenvironment {testbox}
{
\vbox_gset:Nw \g_binpack_tmpa_box
\color_group_begin: \color_ensure_current:
\dim_set_eq:NN \hsize \g_binpack_hsize_dim
}
{
\color_group_end:
\vbox_gset_end:
\binpack_gpush_box:N \g_binpack_tmpa_box
\int_gincr:N \g_binpack_label_int
}
\newcommand{\BinPackOutput}
{
\binpack_sort:
\binpack_pack:
\binpack_build:
}
\cs_new_protected:Npn \binpack_gpush_box:N #1
{
\seq_gpush:Nx \g_binpack_main_seq
{
{ \int_use:N \g_binpack_label_int }
{ \dim_eval:n { \box_ht:N #1 + \box_dp:N #1 + \g_binpack_extra_dim } }
}
\vbox_gset:Nn \g_binpack_main_box
{
\box_use:N #1
\vbox_unpack_clear:N \g_binpack_main_box
}
}
\cs_new_protected:Npn \binpack_box_item:n #1
{
\vbox_gset:Nn \g_binpack_tmpa_box
{
\vbox_unpack:N \g_binpack_main_box
\prg_replicate:nn { #1 + 1 }
{ \box_gset_to_last:N \g_binpack_tmpb_box }
}
\box_use_drop:N \g_binpack_tmpb_box
}
\cs_new_protected:Npn \binpack_sort:
{
\seq_gsort:Nn \g_binpack_main_seq
{ \binpack_sort_aux:nnnn ##1 ##2 }
}
\cs_new_protected:Npn \binpack_sort_aux:nnnn #1#2 #3#4
{
\dim_compare:nNnTF { #2 } < { #4 }
{ \sort_return_swapped: } { \sort_return_same: }
}
\cs_new_protected:Npn \binpack_pack:
{
\int_gzero:N \g_binpack_page_int
\seq_map_inline:Nn \g_binpack_main_seq { \binpack_pack:nn ##1 }
}
\cs_new_protected:Npn \binpack_pack:nn #1#2
{
\bool_gset_false:N \g_binpack_success_bool
\prg_stepwise_inline:nnnn
{ 0 } { 1 } { \g_binpack_page_int - 1 }
{
\dim_compare:nNnF
{ \dim_use:c { g_binpack_page_##1_dim } + #2 }
> \g_binpack_vsize_dim
{
\binpack_page_gput:nnn {##1} {#1} {#2}
\bool_gset_true:N \g_binpack_success_bool
\prg_map_break:
}
}
\bool_if:NF \g_binpack_success_bool
{
\binpack_page_new:
\binpack_page_gput:xnn
{ \int_eval:n { \g_binpack_page_int - 1 } } {#1} {#2}
}
}
\cs_new_protected:Npn \binpack_page_gput:nnn #1#2#3
{
\seq_gput_right:cn { g_binpack_page_#1_seq } {#2}
\dim_gadd:cn { g_binpack_page_#1_dim } {#3}
}
\cs_generate_variant:Nn \binpack_page_gput:nnn { x }
\cs_new_protected:Npn \binpack_page_new:
{
\dim_new:c { g_binpack_page_ \int_use:N \g_binpack_page_int _dim }
\seq_new:c { g_binpack_page_ \int_use:N \g_binpack_page_int _seq }
\int_gincr:N \g_binpack_page_int
}
\cs_new_protected:Npn \binpack_build:
{
\prg_stepwise_inline:nnnn
{ 0 } { 1 } { \g_binpack_page_int - 1 }
{
\iow_term:x
{ items:~\seq_map_function:cN { g_binpack_page_##1_seq } \c_space_tl }
\seq_map_inline:cn
{ g_binpack_page_##1_seq }
{
\binpack_frame_box:n { \binpack_box_item:n { ####1 } }
\tex_vfil:D
}
\clearpage
}
}
\cs_new_protected:Npn \binpack_frame_box:n #1
{
\vbox
{
\hrule height \fboxrule
\hbox
{
\vrule width \fboxrule
\kern \fboxsep
\vbox { \kern \fboxsep #1 \kern \fboxsep }
\kern \fboxsep
\vrule width \fboxrule
}
\hrule height \fboxrule
}
}
\ExplSyntaxOff
\begin{document}
\footnotesize
\BinPackInit
\begin{testbox}
\lipsum[1-2]
\end{testbox}
\begin{testbox}
\lipsum[3-4]
\end{testbox}
\begin{testbox}
\lipsum[1-3]
\end{testbox}
\begin{testbox}
\lipsum[3-5]
\end{testbox}
\begin{testbox}
\lipsum[1-5]
\end{testbox}
\begin{testbox}
\lipsum[3-6]
\end{testbox}
\begin{testbox}
\lipsum[2]
\end{testbox}
\begin{testbox}
\lipsum[3]
\end{testbox}
\clearpage
\BinPackOutput
\end{document}
答案2
这是 expl3 中实现的解决方案的草图。为了方便起见,我假设所有浮点数都存储在外部文件中(当然也可以用其他方法)。要使之可行,需要提供用户界面并完成实现的排版部分。
如果有人对各种数据结构里面的内容感兴趣,我留下了一些\show_...
命令(注释掉)来展示中间步骤。
\begin{filecontents*}{A}
This is box one
\vspace{4in}
The end of box one
\end{filecontents*}
\begin{filecontents*}{B}
This is box two
\vspace{4in}
The end of box two
\end{filecontents*}
\begin{filecontents*}{C}
This is box thre
\vspace{2in}
The end of box three
\end{filecontents*}
\begin{filecontents*}{D}
This is box four
\vspace{1in}
The end of box four
\end{filecontents*}
\documentclass{article}
\usepackage{expl3}
\ExplSyntaxOn
% use "fs" for "floats sorted" as module name
% ----------------------------------------------
% box for measuring float ht
\box_new:N \l_fs_float_box
% property list holding float heights (key float file name)
\prop_new:N \l_fs_float_hts_prop
% token list storing float names in braces for sorting
\tl_new:N \l_fs_floats_tl
% sequence holding floats sorted by size
\seq_new:N \l_fs_sorted_floats_seq
% counter for allocated pages
\int_new:N \l_fs_pages_int
% sequence of allocated pages
\seq_new:N \l_fs_alloced_pages_seq
% property list holding available space on page (key = page number)
\prop_new:N \l_fs_page_hts_prop
% ----------------------------------------------
% load a float file (arg = file name)
\cs_new:Npn \fs_load_float_file:n #1 {
% measure
\vbox_set:Nn \l_fs_float_box { \input{#1} }
\prop_put:NnV \l_fs_float_hts_prop {#1} { \box_ht:N \l_fs_float_box }
% store for sorting
\tl_put_right:Nn \l_fs_floats_tl { {#1} }
}
% ----------------------------------------------
% sorting
\cs_new:Npn \fs_sort_sizes: {
%set up definition for quicksort code
\cs_set_nopar:Npn \prg_quicksort_compare:nnTF ##1##2 {
% get two float heights and compare
\prop_get:NnN \l_fs_float_hts_prop {##1} \l_tmpa_tl
\prop_get:NnN \l_fs_float_hts_prop {##2} \l_tmpb_tl
\dim_compare:nNnTF \l_tmpa_tl < \l_tmpb_tl
}
% what to do with each item in the sorted sequence:
\cs_set_nopar:Npn\prg_quicksort_function:n ##1{\seq_put_right:Nn \l_fs_sorted_floats_seq{ ##1} }
% run the quicksort on the content of \l_fs_floats_tl
\exp_args:No \prg_quicksort:n \l_fs_floats_tl
}
% ----------------------------------------------
% place all floats according to the following algorithm:
%
% Loop through all of the boxes:
% Select the largest box
% Put it on the first page which has space, starting a new page if necessary
\cs_new:Npn \fs_place_floats:n #1 {
% map over all floats already sorted by size:
\seq_map_inline:Nn \l_fs_sorted_floats_seq
{
% being simpleminded ... we allocate a new page for every float just in case (may not use
% it later but then we know there is one if necessary :-)
\fs_alloc_new_page:n {#1}
% get the height of the current float
\prop_get:NnN \l_fs_float_hts_prop {##1} \l_tmpa_tl
% now map over all allocated pages so far:
\seq_map_inline:Nn \l_fs_alloced_pages_seq
{
% get the available space for current page:
\prop_get:NnN \l_fs_page_hts_prop {####1} \l_tmpb_tl
% compae that with float size
\dim_compare:nNnF \l_tmpa_tl > \l_tmpb_tl
{
% if the float fits onto the page then:
% - change the available space on that page
\dim_set:Nn \l_tmpa_dim { \l_tmpb_tl - \l_tmpa_tl }
\prop_put:NnV \l_fs_page_hts_prop {####1} \l_tmpa_dim
% - and save the float name in a sequence associated with the page
\seq_put_right:cn {fs_page_ ####1 _seq } {##1}
% - finally break out of this loop as we are done
\seq_map_break:
}
}
}
}
% ----------------------------------------------
% alloc a new page or rather the data structures for it. Arg is the iitial page height
\cs_new:Npn \fs_alloc_new_page:n #1 {
% use a number to generate page "names"
\int_incr:N \l_fs_pages_int
% put in an initial page height
\prop_put:Non \l_fs_page_hts_prop { \int_use:N \l_fs_pages_int} {#1}
% provide an empty sequence that later on hold floats put on this page
\seq_clear:c {fs_page_
\int_use:N \l_fs_pages_int
_seq }
% put the new page name into the sequence holding allocated pages
\seq_put_right:NV \l_fs_alloced_pages_seq \l_fs_pages_int
}
% ----------------------------------------------
% typeset the floats that should by now all be distrupted into the page sequences
\cs_new:Npn \fs_typeset_floats: {
% map over all allocated pages (one could put some randomness here so not to get first all the big floats)
\seq_map_inline:Nn \l_fs_alloced_pages_seq
{
% with out randomness the first page sequence without a float means we are done
\seq_if_empty:cTF {fs_page_ ##1 _seq }
{ \seq_map_break: }
{
% but if it contains float names ... we better typeset the floats one by one
\seq_map_inline:cn {fs_page_ ##1 _seq }
{ \fs_typeset_float:nn {##1} {####1} }
}
}
}
% I'm not actually doing any typesetting just saying what should happen ...
% which is why I also passed the page name as argument
\cs_new:Npn \fs_typeset_float:nn #1#2 {
\typeout { Typeset~ float~ '#2'~ on~ page~ '#1' }
}
% ----------------------------------------------
\begin{document}
% ------------------ load floats ...
\fs_load_float_file:n{A}
\fs_load_float_file:n{C}
\fs_load_float_file:n{D}
\fs_load_float_file:n{B}
%\prop_show:N \l_fs_float_hts_prop
%\tl_show:N \l_fs_floats_tl
% ---------------- sort them
\fs_sort_sizes:
%\seq_show:N \l_fs_sorted_floats_seq
% --------------- place them
\fs_place_floats:n{\textheight}
%\prop_show:N \l_fs_page_hts_prop
% \seq_show:c {fs_page_1_seq }
% \seq_show:c {fs_page_2_seq }
% \seq_show:c {fs_page_3_seq }
% --------------- typeset them
\fs_typeset_floats:
\end{document}