Automatically reorder floats to fill page
I have a document consisting only of floats, and I would like to order them so as to use the least number of pages. In my case, each float contains song lyrics, but they could easily be poems or code snippets or images. I don't care how they're ordered, but I would like LaTeX to automatically reorder them so that each page is as close to full as possible.
Is there a way to do this with plain LaTeX? If not, I assume I'd have to write some code which would calculate the size of each float and then implement my own ordering algorithm - any hints about how I would go about doing that?
A dummy example is below. In this example, box 2 won't fit on the first page, but box 4 will. Ideally, the result should only take two pages rather than three.
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}
Possible ordering algorithm (as requested by 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
floats page-breaking sorting
edited Jan 7 '12 at 11:50
lockstep
190k52585719
asked Dec 20 '11 at 18:17
Steven Bell
26316
|
show 2 more comments
I have a document consisting only of floats, and I would like to order them so as to use the least number of pages. In my case, each float contains song lyrics, but they could easily be poems or code snippets or images. I don't care how they're ordered, but I would like LaTeX to automatically reorder them so that each page is as close to full as possible.
Is there a way to do this with plain LaTeX? If not, I assume I'd have to write some code which would calculate the size of each float and then implement my own ordering algorithm - any hints about how I would go about doing that?
A dummy example is below. In this example, box 2 won't fit on the first page, but box 4 will. Ideally, the result should only take two pages rather than three.
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}
Possible ordering algorithm (as requested by 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
floats page-breaking sorting
edited Jan 7 '12 at 11:50
lockstep
190k52585719
asked Dec 20 '11 at 18:17
Steven Bell
26316
5
If you care to outline yourordering algorithm, its exceptions and rules the macros are the easy part.
– Yiannis Lazarides
Dec 20 '11 at 19:07
(1) Are all boxes one page wide? (2) Does each box have a rigid vertical size? e.g., if they have stretchable space between the title and body of song, the answer is no.
– Bruno Le Floch
Jan 5 '12 at 1:24
@Bruno: Yes, all of the boxes are one page wide, and have a fixed height.
– Steven Bell
Jan 5 '12 at 14:32
@StevenBell Also, if you have a pointer to typical algorithms for that ("bag packing"?), it would be useful. I can look them up, but that's this much more time taken away from coding.
– Bruno Le Floch
Jan 5 '12 at 19:56
@BrunoLeFloch I added a brief description of the "decreasing first fit" algorithm to the end of my question. Wikipedia has a more complete discussion under "Bin Packing Problem"
– Steven Bell
Jan 6 '12 at 0:20
|
show 2 more comments
I have a document consisting only of floats, and I would like to order them so as to use the least number of pages. In my case, each float contains song lyrics, but they could easily be poems or code snippets or images. I don't care how they're ordered, but I would like LaTeX to automatically reorder them so that each page is as close to full as possible.
Is there a way to do this with plain LaTeX? If not, I assume I'd have to write some code which would calculate the size of each float and then implement my own ordering algorithm - any hints about how I would go about doing that?
A dummy example is below. In this example, box 2 won't fit on the first page, but box 4 will. Ideally, the result should only take two pages rather than three.
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}
Possible ordering algorithm (as requested by 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
floats page-breaking sorting
edited Jan 7 '12 at 11:50
lockstep
190k52585719
asked Dec 20 '11 at 18:17
Steven Bell
26316
I have a document consisting only of floats, and I would like to order them so as to use the least number of pages. In my case, each float contains song lyrics, but they could easily be poems or code snippets or images. I don't care how they're ordered, but I would like LaTeX to automatically reorder them so that each page is as close to full as possible.
Is there a way to do this with plain LaTeX? If not, I assume I'd have to write some code which would calculate the size of each float and then implement my own ordering algorithm - any hints about how I would go about doing that?
A dummy example is below. In this example, box 2 won't fit on the first page, but box 4 will. Ideally, the result should only take two pages rather than three.
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}
Possible ordering algorithm (as requested by 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
floats page-breaking sorting
floats page-breaking sorting
edited Jan 7 '12 at 11:50
lockstep
190k52585719
asked Dec 20 '11 at 18:17
Steven Bell
26316
edited Jan 7 '12 at 11:50
lockstep
190k52585719
asked Dec 20 '11 at 18:17
Steven Bell
26316
edited Jan 7 '12 at 11:50
lockstep
190k52585719
edited Jan 7 '12 at 11:50
lockstep
190k52585719
edited Jan 7 '12 at 11:50
lockstep
190k52585719
190k52585719
asked Dec 20 '11 at 18:17
Steven Bell
26316
asked Dec 20 '11 at 18:17
Steven Bell
26316
asked Dec 20 '11 at 18:17
Steven Bell
26316
26316
5
If you care to outline yourordering algorithm, its exceptions and rules the macros are the easy part.
– Yiannis Lazarides
Dec 20 '11 at 19:07
(1) Are all boxes one page wide? (2) Does each box have a rigid vertical size? e.g., if they have stretchable space between the title and body of song, the answer is no.
– Bruno Le Floch
Jan 5 '12 at 1:24
@Bruno: Yes, all of the boxes are one page wide, and have a fixed height.
– Steven Bell
Jan 5 '12 at 14:32
@StevenBell Also, if you have a pointer to typical algorithms for that ("bag packing"?), it would be useful. I can look them up, but that's this much more time taken away from coding.
– Bruno Le Floch
Jan 5 '12 at 19:56
@BrunoLeFloch I added a brief description of the "decreasing first fit" algorithm to the end of my question. Wikipedia has a more complete discussion under "Bin Packing Problem"
– Steven Bell
Jan 6 '12 at 0:20
|
show 2 more comments
5
If you care to outline yourordering algorithm, its exceptions and rules the macros are the easy part.
– Yiannis Lazarides
Dec 20 '11 at 19:07
(1) Are all boxes one page wide? (2) Does each box have a rigid vertical size? e.g., if they have stretchable space between the title and body of song, the answer is no.
– Bruno Le Floch
Jan 5 '12 at 1:24
@Bruno: Yes, all of the boxes are one page wide, and have a fixed height.
– Steven Bell
Jan 5 '12 at 14:32
@StevenBell Also, if you have a pointer to typical algorithms for that ("bag packing"?), it would be useful. I can look them up, but that's this much more time taken away from coding.
– Bruno Le Floch
Jan 5 '12 at 19:56
@BrunoLeFloch I added a brief description of the "decreasing first fit" algorithm to the end of my question. Wikipedia has a more complete discussion under "Bin Packing Problem"
– Steven Bell
Jan 6 '12 at 0:20
5
5
If you care to outline your
ordering algorithm, its exceptions and rules the macros are the easy part.– Yiannis Lazarides
Dec 20 '11 at 19:07
If you care to outline your
ordering algorithm, its exceptions and rules the macros are the easy part.– Yiannis Lazarides
Dec 20 '11 at 19:07
(1) Are all boxes one page wide? (2) Does each box have a rigid vertical size? e.g., if they have stretchable space between the title and body of song, the answer is no.
– Bruno Le Floch
Jan 5 '12 at 1:24
(1) Are all boxes one page wide? (2) Does each box have a rigid vertical size? e.g., if they have stretchable space between the title and body of song, the answer is no.
– Bruno Le Floch
Jan 5 '12 at 1:24
@Bruno: Yes, all of the boxes are one page wide, and have a fixed height.
– Steven Bell
Jan 5 '12 at 14:32
@Bruno: Yes, all of the boxes are one page wide, and have a fixed height.
– Steven Bell
Jan 5 '12 at 14:32
@StevenBell Also, if you have a pointer to typical algorithms for that ("bag packing"?), it would be useful. I can look them up, but that's this much more time taken away from coding.
– Bruno Le Floch
Jan 5 '12 at 19:56
@StevenBell Also, if you have a pointer to typical algorithms for that ("bag packing"?), it would be useful. I can look them up, but that's this much more time taken away from coding.
– Bruno Le Floch
Jan 5 '12 at 19:56
@BrunoLeFloch I added a brief description of the "decreasing first fit" algorithm to the end of my question. Wikipedia has a more complete discussion under "Bin Packing Problem"
– Steven Bell
Jan 6 '12 at 0:20
@BrunoLeFloch I added a brief description of the "decreasing first fit" algorithm to the end of my question. Wikipedia has a more complete discussion under "Bin Packing Problem"
– Steven Bell
Jan 6 '12 at 0:20
|
show 2 more comments
2 Answers
2
active
oldest
votes
I was slower than Frank because I spent a long time fine-tuning the sorting algorithms in LaTeX3. To run the code below, you should grab the "trial" l3sort package from the svn repository, or wait for us to decide to move it to a proper experimental package, on CTAN.
Apart from that, the whole thing is a pretty naive implementation of the algorithm you describe (see in particular the structure of BinPackOutput).
First collect all the boxes in a common
main_box, one after the other, keeping track of the vertical size of each box, together where they appear in themain_box(boxes are stacked starting at the bottom of that main box, which can be accessed with the TeX primitivelastbox).Then sort the list of pairs
{index}{dimension}by decreasing dimension.Loop through those pairs (
seq_map_inline:Nn g_binpack_main_seq). For each one, try pages in turn (prg_stepwise_inline:nnnn), testing if the new box fits (dim_compare:nNnF). If it does, then put the box there and break out of the loop over possible pages. If none of the pages had space, make a new page, and put the box there.In step 3, we construct for each page a sequence of the boxes that we plan to put there. Extracting a given box from the
main_boxis done in a dirty way:box_gset_to_last:Nremoves the last box and assigns it to the given variable. If we repeat that asignment, we remove boxes one by one. Hence, the method I decided to use is to copy themain_box, then remove boxes N times and grabbing the (N+1)-st one, which is item N in themain_box.
Boxes are typeset in a frame, and we add a vfil amount of space around each. It turns out that my particular example is very full; in general boxes will be separated each by the same amount, hence are spread out nicely along the page.
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 - 2fboxsep - 2fboxrule }
dim_gset:Nn g_binpack_extra_dim { 2fboxsep + 2fboxrule }
}
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}
answered Jan 7 '12 at 20:48
Bruno Le Floch
33.8k5114211
add a comment |
Here is a sketch of a solution implemented in expl3. To make my life easy I assume that all floats are stored in external files (though of course one could do this differently). To be workable one would need to provide a user interface and finish of the typesetting part of the implementation.
I left in a few show_... commands (commented out) to show intermediate steps if anybody is interested what is inside the various data structures.
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:Npnprg_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}
answered Jan 7 '12 at 11:03
Frank Mittelbach
60.3k6177247
add a comment |
Your Answer
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "85"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2ftex.stackexchange.com%2fquestions%2f38939%2fautomatically-reorder-floats-to-fill-page%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
I was slower than Frank because I spent a long time fine-tuning the sorting algorithms in LaTeX3. To run the code below, you should grab the "trial" l3sort package from the svn repository, or wait for us to decide to move it to a proper experimental package, on CTAN.
Apart from that, the whole thing is a pretty naive implementation of the algorithm you describe (see in particular the structure of BinPackOutput).
First collect all the boxes in a common
main_box, one after the other, keeping track of the vertical size of each box, together where they appear in themain_box(boxes are stacked starting at the bottom of that main box, which can be accessed with the TeX primitivelastbox).Then sort the list of pairs
{index}{dimension}by decreasing dimension.Loop through those pairs (
seq_map_inline:Nn g_binpack_main_seq). For each one, try pages in turn (prg_stepwise_inline:nnnn), testing if the new box fits (dim_compare:nNnF). If it does, then put the box there and break out of the loop over possible pages. If none of the pages had space, make a new page, and put the box there.In step 3, we construct for each page a sequence of the boxes that we plan to put there. Extracting a given box from the
main_boxis done in a dirty way:box_gset_to_last:Nremoves the last box and assigns it to the given variable. If we repeat that asignment, we remove boxes one by one. Hence, the method I decided to use is to copy themain_box, then remove boxes N times and grabbing the (N+1)-st one, which is item N in themain_box.
Boxes are typeset in a frame, and we add a vfil amount of space around each. It turns out that my particular example is very full; in general boxes will be separated each by the same amount, hence are spread out nicely along the page.
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 - 2fboxsep - 2fboxrule }
dim_gset:Nn g_binpack_extra_dim { 2fboxsep + 2fboxrule }
}
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}
answered Jan 7 '12 at 20:48
Bruno Le Floch
33.8k5114211
add a comment |
I was slower than Frank because I spent a long time fine-tuning the sorting algorithms in LaTeX3. To run the code below, you should grab the "trial" l3sort package from the svn repository, or wait for us to decide to move it to a proper experimental package, on CTAN.
Apart from that, the whole thing is a pretty naive implementation of the algorithm you describe (see in particular the structure of BinPackOutput).
First collect all the boxes in a common
main_box, one after the other, keeping track of the vertical size of each box, together where they appear in themain_box(boxes are stacked starting at the bottom of that main box, which can be accessed with the TeX primitivelastbox).Then sort the list of pairs
{index}{dimension}by decreasing dimension.Loop through those pairs (
seq_map_inline:Nn g_binpack_main_seq). For each one, try pages in turn (prg_stepwise_inline:nnnn), testing if the new box fits (dim_compare:nNnF). If it does, then put the box there and break out of the loop over possible pages. If none of the pages had space, make a new page, and put the box there.In step 3, we construct for each page a sequence of the boxes that we plan to put there. Extracting a given box from the
main_boxis done in a dirty way:box_gset_to_last:Nremoves the last box and assigns it to the given variable. If we repeat that asignment, we remove boxes one by one. Hence, the method I decided to use is to copy themain_box, then remove boxes N times and grabbing the (N+1)-st one, which is item N in themain_box.
Boxes are typeset in a frame, and we add a vfil amount of space around each. It turns out that my particular example is very full; in general boxes will be separated each by the same amount, hence are spread out nicely along the page.
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 - 2fboxsep - 2fboxrule }
dim_gset:Nn g_binpack_extra_dim { 2fboxsep + 2fboxrule }
}
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}
answered Jan 7 '12 at 20:48
Bruno Le Floch
33.8k5114211
add a comment |
I was slower than Frank because I spent a long time fine-tuning the sorting algorithms in LaTeX3. To run the code below, you should grab the "trial" l3sort package from the svn repository, or wait for us to decide to move it to a proper experimental package, on CTAN.
Apart from that, the whole thing is a pretty naive implementation of the algorithm you describe (see in particular the structure of BinPackOutput).
First collect all the boxes in a common
main_box, one after the other, keeping track of the vertical size of each box, together where they appear in themain_box(boxes are stacked starting at the bottom of that main box, which can be accessed with the TeX primitivelastbox).Then sort the list of pairs
{index}{dimension}by decreasing dimension.Loop through those pairs (
seq_map_inline:Nn g_binpack_main_seq). For each one, try pages in turn (prg_stepwise_inline:nnnn), testing if the new box fits (dim_compare:nNnF). If it does, then put the box there and break out of the loop over possible pages. If none of the pages had space, make a new page, and put the box there.In step 3, we construct for each page a sequence of the boxes that we plan to put there. Extracting a given box from the
main_boxis done in a dirty way:box_gset_to_last:Nremoves the last box and assigns it to the given variable. If we repeat that asignment, we remove boxes one by one. Hence, the method I decided to use is to copy themain_box, then remove boxes N times and grabbing the (N+1)-st one, which is item N in themain_box.
Boxes are typeset in a frame, and we add a vfil amount of space around each. It turns out that my particular example is very full; in general boxes will be separated each by the same amount, hence are spread out nicely along the page.
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 - 2fboxsep - 2fboxrule }
dim_gset:Nn g_binpack_extra_dim { 2fboxsep + 2fboxrule }
}
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}
answered Jan 7 '12 at 20:48
Bruno Le Floch
33.8k5114211
I was slower than Frank because I spent a long time fine-tuning the sorting algorithms in LaTeX3. To run the code below, you should grab the "trial" l3sort package from the svn repository, or wait for us to decide to move it to a proper experimental package, on CTAN.
Apart from that, the whole thing is a pretty naive implementation of the algorithm you describe (see in particular the structure of BinPackOutput).
First collect all the boxes in a common
main_box, one after the other, keeping track of the vertical size of each box, together where they appear in themain_box(boxes are stacked starting at the bottom of that main box, which can be accessed with the TeX primitivelastbox).Then sort the list of pairs
{index}{dimension}by decreasing dimension.Loop through those pairs (
seq_map_inline:Nn g_binpack_main_seq). For each one, try pages in turn (prg_stepwise_inline:nnnn), testing if the new box fits (dim_compare:nNnF). If it does, then put the box there and break out of the loop over possible pages. If none of the pages had space, make a new page, and put the box there.In step 3, we construct for each page a sequence of the boxes that we plan to put there. Extracting a given box from the
main_boxis done in a dirty way:box_gset_to_last:Nremoves the last box and assigns it to the given variable. If we repeat that asignment, we remove boxes one by one. Hence, the method I decided to use is to copy themain_box, then remove boxes N times and grabbing the (N+1)-st one, which is item N in themain_box.
Boxes are typeset in a frame, and we add a vfil amount of space around each. It turns out that my particular example is very full; in general boxes will be separated each by the same amount, hence are spread out nicely along the page.
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 - 2fboxsep - 2fboxrule }
dim_gset:Nn g_binpack_extra_dim { 2fboxsep + 2fboxrule }
}
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}
answered Jan 7 '12 at 20:48
Bruno Le Floch
33.8k5114211
edited 16 mins ago
answered Jan 7 '12 at 20:48
Bruno Le Floch
33.8k5114211
answered Jan 7 '12 at 20:48
Bruno Le Floch
33.8k5114211
answered Jan 7 '12 at 20:48
Bruno Le Floch
33.8k5114211
33.8k5114211
add a comment |
add a comment |
Here is a sketch of a solution implemented in expl3. To make my life easy I assume that all floats are stored in external files (though of course one could do this differently). To be workable one would need to provide a user interface and finish of the typesetting part of the implementation.
I left in a few show_... commands (commented out) to show intermediate steps if anybody is interested what is inside the various data structures.
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:Npnprg_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}
answered Jan 7 '12 at 11:03
Frank Mittelbach
60.3k6177247
add a comment |
Here is a sketch of a solution implemented in expl3. To make my life easy I assume that all floats are stored in external files (though of course one could do this differently). To be workable one would need to provide a user interface and finish of the typesetting part of the implementation.
I left in a few show_... commands (commented out) to show intermediate steps if anybody is interested what is inside the various data structures.
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:Npnprg_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}
answered Jan 7 '12 at 11:03
Frank Mittelbach
60.3k6177247
add a comment |
Here is a sketch of a solution implemented in expl3. To make my life easy I assume that all floats are stored in external files (though of course one could do this differently). To be workable one would need to provide a user interface and finish of the typesetting part of the implementation.
I left in a few show_... commands (commented out) to show intermediate steps if anybody is interested what is inside the various data structures.
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:Npnprg_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}
answered Jan 7 '12 at 11:03
Frank Mittelbach
60.3k6177247
Here is a sketch of a solution implemented in expl3. To make my life easy I assume that all floats are stored in external files (though of course one could do this differently). To be workable one would need to provide a user interface and finish of the typesetting part of the implementation.
I left in a few show_... commands (commented out) to show intermediate steps if anybody is interested what is inside the various data structures.
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:Npnprg_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}
answered Jan 7 '12 at 11:03
Frank Mittelbach
60.3k6177247
answered Jan 7 '12 at 11:03
Frank Mittelbach
60.3k6177247
answered Jan 7 '12 at 11:03
Frank Mittelbach
60.3k6177247
answered Jan 7 '12 at 11:03
Frank Mittelbach
60.3k6177247
60.3k6177247
add a comment |
add a comment |
Thanks for contributing an answer to TeX - LaTeX Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2ftex.stackexchange.com%2fquestions%2f38939%2fautomatically-reorder-floats-to-fill-page%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
5
If you care to outline your
ordering algorithm, its exceptions and rules the macros are the easy part.– Yiannis Lazarides
Dec 20 '11 at 19:07
(1) Are all boxes one page wide? (2) Does each box have a rigid vertical size? e.g., if they have stretchable space between the title and body of song, the answer is no.
– Bruno Le Floch
Jan 5 '12 at 1:24
@Bruno: Yes, all of the boxes are one page wide, and have a fixed height.
– Steven Bell
Jan 5 '12 at 14:32
@StevenBell Also, if you have a pointer to typical algorithms for that ("bag packing"?), it would be useful. I can look them up, but that's this much more time taken away from coding.
– Bruno Le Floch
Jan 5 '12 at 19:56
@BrunoLeFloch I added a brief description of the "decreasing first fit" algorithm to the end of my question. Wikipedia has a more complete discussion under "Bin Packing Problem"
– Steven Bell
Jan 6 '12 at 0:20