2
/******************************************************************************
3
* MODULE : page_breaker.cpp
4
* DESCRIPTION: Page breaking
5
* COPYRIGHT : (C) 1999 Joris van der Hoeven
6
*******************************************************************************
7
* This software falls under the GNU general public license and comes WITHOUT
8
* ANY WARRANTY WHATSOEVER. See the file $TEXMACS_PATH/LICENSE for more details.
9
* If you don't have this file, write to the Free Software Foundation, Inc.,
10
* 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
11
******************************************************************************/
13
#include "Line/lazy_vstream.hpp"
14
#include "vpenalty.hpp"
15
#include "skeleton.hpp"
17
#include "merge_sort.hpp"
18
void sort (pagelet& pg);
19
vpenalty as_vpenalty (SI diff);
21
typedef array<int> vbreak;
22
typedef array<int> ladder;
28
#define INVALID_BREAK 0
32
/******************************************************************************
33
* The page_breaker class
34
******************************************************************************/
36
struct page_breaker_rep {
48
int nr_flows; // number of flows;
49
hashmap<path,int> flow_id; // unique number for each flow
50
array<path> flow_fl; // flow associated to flow identifier
51
array<array<path> > flow; // for each flow the paths to all page_items
52
array<array<space> > flow_ht; // the heights of these page_items
53
array<array<space> > flow_cor; // top and bottom corrections of page_items
54
array<array<space> > flow_tot; // total heights up to a certain index
55
array<array<int> > flow_cont; // number of contiguous blocks until here
57
array<vbreak> brk; // possible break points
58
array<space> brk_tot; // (estimated) total height until breaks
59
array<vbreak> tmp; // temporary space during sort
60
array<space> tmp_tot; // temporary space during sort
61
hashmap<vbreak,int> brk_nr; // find number of break from break
62
array<ladder> brk_prev; // maximal previous incomparable breaks
63
array<ladder> brk_next; // minimal next incomparable breaks
64
int brk_first; // first break
65
int brk_last; // last break
67
int tc_start; // two column start
68
int tc_middle; // two column middle
69
int tc_end; // two column end
70
int tc_ref; // two column reference
71
ladder tc_ld; // two column ladder
72
int tc_bmid; // best middle
73
vpenalty tc_bpen; // corresponding penalty
74
pagelet tc_bpg1; // & left column
75
pagelet tc_bpg2; // & right column
77
int quality; // quality of page breaking
78
int cur_start; // current start of page
79
int cur_end; // current end of page
80
int cur_ref; // current approximation of best end
81
ladder cur_ld; // current ladder for untreated tries
82
int best_end; // best end of page for given start
83
vpenalty best_pen; // corresponding penalty
84
pagelet best_pg; // & pagelet
85
array<int> best_prev; // best previous break points
86
array<vpenalty> best_pens; // corresponding penalties
87
array<pagelet> best_pgs; // & pagelets
89
page_breaker_rep (array<page_item> l, space ph, int quality,
90
space fn_sep, space fnote_sep,
91
space float_sep, font fn);
93
void init_flows (int start, int end);
94
void init_flows (array<page_item> l, int start, int end, path p, path flb);
95
void show_penalties ();
97
bool correct_break (vbreak br, int id);
98
bool correct_break (vbreak br);
99
void spool_break (vbreak& br, path flb, path start);
100
void rewind_break (vbreak& br, path flb, int& id, path& p);
101
bool float_property (path p, char c);
102
array<vbreak> generate_breaks (vbreak br, int id);
103
array<vbreak> generate_breaks (vbreak br, int id, path flb);
104
space compute_total_height (vbreak br);
106
void sort_breaks (int start, int end);
109
void init_ladders ();
110
ladder inc_merge (ladder ld1, ladder ld2);
111
ladder dec_merge (ladder ld1, ladder ld2);
113
bool correct_pagelet (int start, int end);
114
bool last_break (int start, int end, int id);
115
insertion make_insertion (int id, int ch, int i1, int i2, bool flag);
116
pagelet make_pagelet (int start, int end, path flb, int nr_cols);
117
vpenalty format_insertion (insertion& ins, double stretch);
118
vpenalty format_pagelet (pagelet& pg, double stretch);
119
vpenalty format_pagelet (pagelet& pg, space ht, bool last_page);
121
void search_mcol_breaks (vbreak br1, vbreak br2, array<array<int> > part,
122
path p1, path p2, int& i1, int& i2);
123
insertion make_multi_column (skeleton sk, int real_nr_cols);
124
insertion make_multi_column (int start, int end, path flb, int nr_cols);
125
int tc_propose_break (path flb);
126
insertion make_two_column (int start, int end, path flb);
128
void fast_break_page (int i1, int& first_end);
129
void fast_assemble_skeleton (skeleton& sk, int end);
130
void fast_assemble_skeleton (skeleton& sk);
132
int propose_break ();
133
void find_next_breaks ();
134
void assemble_skeleton (skeleton& sk, int last);
135
void assemble_skeleton (skeleton& sk);
136
void assemble_skeleton (skeleton& sk, int start, int end);
137
skeleton make_skeleton ();
140
/******************************************************************************
142
******************************************************************************/
144
page_breaker_rep::page_breaker_rep (
145
array<page_item> l2, space ph, int quality2,
146
space fn_sep2, space fnote_sep2, space float_sep2, font fn2):
147
l (l2), papyrus_mode (ph == (MAX_SI >> 1)), height (ph),
148
fn_sep (fn_sep2), fnote_sep (fnote_sep2), float_sep (float_sep2),
149
fn (fn2), flow_id (-1), brk_nr (-1), quality (quality2)
152
/******************************************************************************
154
******************************************************************************/
157
var_path_inf_eq (path p1, path p2) {
158
if (nil (p1) || nil (p2)) return nil (p1);
159
if (p1->item<p2->item) return true;
160
if (p1->item>p2->item) return false;
161
return var_path_inf_eq (p1->next, p2->next);
165
fast_find (array<path> a, path p) {
166
int n= N(a), step= n, i= n>>1;
169
if (var_path_inf_eq (p, a[i])) i= max (0, i-step);
170
else i= min (n-1, i+step);
172
if (!var_path_inf_eq (p, a[i])) i= i+1;
177
find_length (array<space> a, int start, SI ht) {
178
int n= N(a)- start, step= n, i= (start + N(a))>>1;
181
if (ht <= a[i]->def) i= max (start, i-step);
182
else i= min (N(a)-1, i+step);
184
if (ht > a[i]->def) i= min (N(a)-1, i+1);
189
find_end_block (array<path> a, int start, int end) {
190
if (a[end-1] == path_add (a[start], end-1-start)) return end;
191
int n= end-start, step= n, i= (start+end+1)>>1;
194
if ((i>start) && (a[i-1] != path_add (a[start], i-1-start)))
195
i= max (start, i-step);
196
else i= min (end-1, i+step);
198
if ((i>start) && (a[i-1] != path_add (a[start], i-1-start))) i--;
203
access (array<page_item> l, path p) {
204
page_item item= l[p->item];
205
if (nil (p->next)) return item;
207
lazy_vstream ins= (lazy_vstream) item->fl[p->next->item];
208
return access (ins->l, p->next->next);
212
/*static*/ array<page_item>
213
sub (array<page_item> l, path p, path q) {
214
if (atom (p) && atom (q)) {
215
int i= p->item, j= q->item, k;
216
array<page_item> r (j-i);
217
for (k=i; k<j; k++) r[k-i]= l[k];
221
if ((N(p) <= 2) || (N(q) <= 2)) {
222
cerr << "\nThe paths were " << p << " and " << q << "\n";
223
fatal_error ("paths to short", "sub (array<page_item>, path, path)");
225
if ((p->item != q->item) || (p->next->item != q->next->item)) {
226
cerr << "\nThe paths were " << p << " and " << q << "\n";
227
fatal_error ("paths don't match", "sub (array<page_item>, path, path)");
229
page_item item= l[p->item];
230
lazy_vstream ins= (lazy_vstream) item->fl[p->next->item];
231
return sub (ins->l, p->next->next, q->next->next);
236
starts (path p, path q) {
237
return (N(p) >= N(q)) && (head (p, N(q)) == q);
240
/******************************************************************************
242
******************************************************************************/
245
page_breaker_rep::init_flows (int start, int end) {
249
flow_id = hashmap<path,int> (-1);
250
flow_fl = array<path> (0);
251
flow = array<array<path> > (0);
252
flow_ht = array<array<space> > (0);
253
flow_cor = array<array<space> > (0);
254
flow_tot = array<array<space> > (0);
255
flow_cont= array<array<int> > (0);
256
init_flows (l, start, end, path (), path ());
260
page_breaker_rep::init_flows (
261
array<page_item> l, int start, int end, path p, path flb)
264
for (i=start; i<end; i++) {
265
path fl= flb * l[i]->nr_cols;
266
if (!flow_id->contains (fl)) {
267
flow_id (fl)= nr_flows;
269
flow << array<path> (0);
270
flow_ht << array<space> (0);
271
flow_cor << array<space> (0);
272
flow_tot << array<space> (0);
273
flow_cont << array<int> (0);
276
int id= flow_id (fl);
277
int nr= N (flow_tot [id]);
278
SI bot_cor= max (0, l[i]->b->y1- fn->y1);
279
SI bod_cor= l[i]->b->h ();
280
SI top_cor= max (0, fn->y2- l[i]->b->y2);
281
bool cont= (nr>0) && (path_up (flow[id][nr-1]) == p);
282
flow [id] << (p * i);
283
flow_ht [id] << (space (l[i]->b->h()) + l[i]->spc);
284
flow_cor [id] << space (bot_cor, bod_cor, top_cor);
285
flow_tot [id] << (nr==0? space(0): flow_tot[id][nr-1]) + flow_ht[id][nr];
286
flow_cont[id] << (nr==0? 1: flow_cont[id][nr-1] + (cont? 0: 1));
287
if ((i==end-1) || (l[i]->nr_cols!=l[i+1]->nr_cols)) l[i]->penalty=0;
290
for (i=start; i<end; i++) {
291
path fl= flb * l[i]->nr_cols;
292
int j, k= N (l[i]->fl);
293
for (j=0; j<k; j++) {
295
lazy_vstream ins= (lazy_vstream) l[i]->fl[j];
296
array<page_item> sub_l= ins->l;
297
if (is_tuple (ins->channel, "footnote")) ch= 0;
298
else if (is_tuple (ins->channel, "float")) ch= 1;
299
init_flows (sub_l, 0, N(sub_l), p * path (i, j), fl * ch);
305
page_breaker_rep::show_penalties () {
307
for (id=0; id<nr_flows; id++)
308
for (i=0; i<N(flow[id]); i++)
309
cout << id << ", " << i << ":\t" << flow[id][i] << " -> "
310
<< access (l, flow[id][i])->penalty << "\n";
313
/******************************************************************************
314
* Initialize possible breaks
315
******************************************************************************/
318
page_breaker_rep::correct_break (vbreak br, int id) {
319
if ((br[id] > 0) && (br[id] < N(flow[id]))) {
320
path p= flow[id][br[id]-1];
321
if (path_inc (p) != flow[id][br[id]]) return true;
322
if (access (l, p)->penalty >= HYPH_INVALID) return false;
329
page_breaker_rep::correct_break (vbreak br) {
331
for (id=0; id<nr_flows; id++)
332
if (!correct_break (br, id)) return false;
337
page_breaker_rep::spool_break (vbreak& br, path flb, path start) {
339
for (id=0; id<nr_flows; id++)
340
if (path_up (flow_fl[id]) == flb)
341
br[id]= fast_find (flow[id], start);
345
page_breaker_rep::rewind_break (
346
vbreak& br, path flb, int& best_id, path& best_p)
351
for (id=0; id<nr_flows; id++)
352
if (path_up (flow_fl[id]) == flb)
353
if ((br[id]>0) && var_path_inf_eq (best_p, flow[id][br[id]-1])) {
355
best_p = flow[id][br[id]-1];
357
if (best_id != -1) br[best_id]--;
361
page_breaker_rep::float_property (path p, char c) {
363
page_item item= access (l, path_up (p, 2));
364
lazy_vstream ins= (lazy_vstream) item->fl [last_item (path_up (p))];
365
string s= as_string (ins->channel[1]);
366
for (i=0; i<N(s); i++)
367
if (s[i] == c) return true;
372
page_breaker_rep::generate_breaks (vbreak br, int id)
373
// generate all breaks by filling in the (-1) entries in 'br'
374
// by break points for subflows of the flow with identifier 'id'
376
// cout << "Generate breaks " << br << ", " << id << LF;
378
path flb= path_up (flow_fl[id]);
380
for (sid=0; sid<nr_flows; sid++)
382
path sflb= path_up (flow_fl[sid]);
383
if ((N(sflb) == (N(flb)+2)) && starts (sflb, flb)) break;
385
if (sid == nr_flows) {
386
array<vbreak> brk (1);
394
generate_breaks (copy (br), id, path_up (flow_fl[sid]));
395
for (j=0; j<N(ref); j++)
396
brk << generate_breaks (copy (ref[j]), id);
402
page_breaker_rep::generate_breaks (vbreak br, int id, path flb)
403
// generate all breaks by filling in the (-1) entries in 'br'
404
// by break points for subflows of the form 'flb * nr_cols' and
405
// only those break points which are relevant for the given break 'br[id]'
406
// for the flow with identifier 'id' (which may be -1 for the top flow)
408
// cout << "Generate breaks " << br << ", " << id << ", " << flb << LF;
413
halt= path (sub_end);
414
for (sid=0; sid<nr_flows; sid++)
415
if (atom (flow_fl[sid]))
418
else if (br[id]==0) {
420
for (sid=0; sid<nr_flows; sid++)
421
if (path_up (flow_fl[sid]) == flb)
425
halt= path_inc (flow[id][br[id]-1]);
426
path start= flow[id][br[id]-1];
427
while (last_item (start) != 0) {
428
if (access (l, path_dec (start))->penalty < HYPH_INVALID) break;
429
start= path_dec (start);
431
if ((!nil (flb)) && (last_item (flb) == 1)) {
433
spool_break (br, flb, halt);
436
vbreak old= copy (br);
437
rewind_break (br, flb, sid, p);
438
if ((sid == -1) || (br == old)) break;
439
if (float_property (flow[sid][br[sid]], 'f')) {
443
if (var_path_inf_eq (p, start)) {
444
if (correct_break (br)) credit--;
445
if (credit == 0) break;
449
else spool_break (br, flb, start);
452
array<vbreak> brk (0);
453
if (correct_break (br)) {
455
path best_p (MAX_SI);
456
for (sid=0; sid<nr_flows; sid++)
457
if (path_up (flow_fl[sid]) == flb) {
459
if (best_sid == -1) best_sid= sid;
460
if ((pos > 0) && path_inf (flow[sid][pos-1], best_p)) {
462
best_p = flow[sid][pos-1];
466
fatal_error ("flow not found", "page_breaker_rep::generate_breaks");
467
brk << generate_breaks (copy (br), best_sid);
473
for (sid=0; sid<nr_flows; sid++)
474
if (path_up (flow_fl[sid]) == flb) {
476
if ((pos < N(flow[sid])) && path_inf (flow[sid][pos], best_p)) {
478
best_p = flow[sid][pos];
481
if (best_sid == -1) break;
483
if (correct_break (br))
484
brk << generate_breaks (copy (br), best_sid);
490
page_breaker_rep::compute_total_height (vbreak br) {
493
// cout << "Total height of break " << br << LF;
494
for (id=0; id<nr_flows; id++) {
495
path fl= flow_fl[id];
496
space stot= br[id]==0? space (0): copy (flow_tot[id][br[id]-1]);
498
int ch = last_item (path_up (fl));
499
int cont= br[id]==0? 0: flow_cont[id][br[id]-1];
501
stot += space (0, cont * fnote_sep->def / 2, cont * fnote_sep->max);
503
stot += space (cont * float_sep->min,
504
(3 * cont * float_sep->def) / 2,
505
2 * cont * float_sep->max);
507
int nr_cols= last_item (fl);
508
// cout << " " << id << ", " << br[id] << ":\t" << (stot/nr_cols) << LF;
509
tot += stot / nr_cols;
515
page_breaker_rep::init_breaks () {
517
vbreak br (nr_flows);
518
for (id=0; id<nr_flows; id++) br[id]= -1;
519
brk= generate_breaks (copy (br), -1, path ());
522
brk_tot= array<space> (brn);
523
for (i=0; i<brn; i++)
524
brk_tot[i]= compute_total_height (brk[i]);
527
/******************************************************************************
528
* Sort the breaks on expected default total height
529
******************************************************************************/
532
page_breaker_rep::sort_breaks (int start, int end) {
533
if (end-start<=1) return;
535
if (!(brk_tot[start]->def <= brk_tot[start+1]->def)) {
536
tmp [start] = brk [start];
537
tmp_tot[start] = brk_tot[start];
538
brk [start] = brk [start+1];
539
brk_tot[start] = brk_tot[start+1];
540
brk [start+1]= tmp [start];
541
brk_tot[start+1]= tmp_tot[start];
545
int middle= (start+end) >> 1;
546
sort_breaks (start, middle);
547
sort_breaks (middle, end);
549
for (i= start, j= middle, k= start; (i<middle) && (j<end); )
550
if (brk_tot[i]->def <= brk_tot[j]->def) {
552
tmp_tot[k]= brk_tot[i];
557
tmp_tot[k]= brk_tot[j];
563
brk_tot[k]= brk_tot[i];
566
for (i=start; i<j; i++) {
568
brk_tot[i]= tmp_tot[i];
573
page_breaker_rep::sort_breaks () {
575
tmp= array<vbreak> (nrb);
576
tmp_tot= array<space> (nrb);
577
sort_breaks (0, nrb);
578
for (i=0; i<nrb; i++)
582
/******************************************************************************
583
* Initialization and manipulation of ladders
584
******************************************************************************/
587
inf_eq (vbreak br1, vbreak br2) {
590
if (br1[i] > br2[i]) return false;
595
page_breaker_rep::init_ladders () {
596
int i, j, nrb= N(brk);
597
brk_prev= array<ladder> (nrb);
598
brk_next= array<ladder> (nrb);
601
for (i=0; i<nrb; i++) {
604
for (j=0; j<N(ld); j++)
605
if (!inf_eq (brk[ld[j]], brk[i]))
612
for (i=nrb-1; i>=0; i--) {
615
for (j=0; j<N(ld); j++)
616
if (!inf_eq (brk[i], brk[ld[j]]))
622
for (i=0; i<nrb; i++) {
624
for (j=0; j<nr_flows; j++)
625
flag= flag && (brk[i][j] == 0);
626
if (flag) { brk_first= i; break; }
629
for (i=nrb-1; i>=0; i--) {
631
for (j=0; j<nr_flows; j++)
632
flag= flag && (brk[i][j] == N(flow[j]));
633
if (flag) { brk_last= i; break; }
638
sub (ladder ld, int start, int end) {
639
// cout << "sub " << ld << ", " << start << ", " << end;
644
// cout << " -> " << ret << LF;
649
page_breaker_rep::dec_merge (ladder ld1, ladder ld2) {
650
// cout << "Decreasing merge " << ld1 << ", " << ld2;
653
for (i=0, j=0; (i<N(ld1)) || (j<N(ld2)); ) {
654
if ((j == N(ld2)) || ((i < N(ld1)) && (ld1[i] > ld2[j]))) {
655
for (k=0; k<N(ld2); k++)
656
if (inf_eq (brk[ld1[i]], brk[ld2[k]]))
658
if (k == N(ld2)) ld << ld1[i];
662
if ((i == N(ld1)) || ((j < N(ld2)) && (ld2[j] > ld1[i]))) {
663
for (k=0; k<N(ld1); k++)
664
if (inf_eq (brk[ld2[j]], brk[ld1[k]]))
666
if (k == N(ld1)) ld << ld2[j];
673
// cout << " -> " << ld << LF;
678
page_breaker_rep::inc_merge (ladder ld1, ladder ld2) {
679
// cout << "Increasing merge " << ld1 << ", " << ld2;
682
for (i=0, j=0; (i<N(ld1)) || (j<N(ld2)); ) {
683
if ((j == N(ld2)) || ((i < N(ld1)) && (ld1[i] < ld2[j]))) {
684
for (k=0; k<N(ld2); k++)
685
if (inf_eq (brk[ld2[k]], brk[ld1[i]]))
687
if (k == N(ld2)) ld << ld1[i];
691
if ((i == N(ld1)) || ((j < N(ld2)) && (ld2[j] < ld1[i]))) {
692
for (k=0; k<N(ld1); k++)
693
if (inf_eq (brk[ld1[k]], brk[ld2[j]]))
695
if (k == N(ld1)) ld << ld2[j];
702
// cout << " -> " << ld << LF;
706
/******************************************************************************
708
******************************************************************************/
711
page_breaker_rep::correct_pagelet (int start, int end) {
713
for (id=0; id<nr_flows; id++)
714
if (brk[start][id] > brk[end][id])
716
for (id=0; id<nr_flows; id++)
717
if ((!atom (flow_fl[id])) && (last_item (path_up (flow_fl[id])) == 1))
718
for (mid= 0; mid<nr_flows; mid++)
719
if ((brk[start][mid] < brk[end][mid]) &&
720
(flow_fl[mid] == path_up (flow_fl[id], 2)))
722
int idb= brk[end][id], midb= brk[start][mid];
723
if ((idb == N(flow[id])) || (midb == N(flow[mid]))) {
724
if (idb < N(flow[id])) return false;
726
else if (var_path_inf_eq (flow[id][idb], flow[mid][midb]))
733
page_breaker_rep::last_break (int start, int end, int id1) {
735
vbreak br1= brk[start], br2= brk[end];
736
for (id2=0; id2<nr_flows; id2++)
738
(br1[id2] < br2[id2]) &&
739
(path_up (flow_fl[id2]) == path_up (flow_fl[id1])) &&
740
var_path_inf_eq (flow[id1][br2[id1]-1], flow[id2][br2[id2]-1]))
746
page_breaker_rep::make_insertion (int id, int ch, int i1, int i2, bool flag) {
747
path p1= flow[id][i1];
748
path p2= path_inc (flow[id][i2-1]);
750
if (i1 == 0) { if (i2 > 1) spc= copy (flow_tot[id][i2-2]); }
751
else spc= flow_tot[id][i2-2] - flow_tot[id][i1-1];
752
SI top_cor= flow_cor[id][i1]->max;
753
SI bot_cor= flow_cor[id][i2-1]->min;
754
spc += space (top_cor + flow_cor[id][i2-1]->def + bot_cor);
757
if (ch == 0) type= tuple ("footnote");
759
if (float_property (p1, 'h')) type= tuple ("float", "h");
760
else if (float_property (p1, 'b')) type= tuple ("float", "b");
761
else type= tuple ("float", "t");
764
insertion ins (type, p1, p2);
766
ins->top_cor= top_cor;
767
ins->bot_cor= bot_cor;
768
if (flag) ins->pen= access (l, flow[id][i2-1])->penalty;
773
page_breaker_rep::make_pagelet (int start, int end, path flb, int nr_cols) {
774
// cout << "Make pagelet "
775
// << start << " " << brk[start] << ", "
776
// << end << " " << brk[end ] << ", " << nr_cols << LF << INDENT;
778
// break flows into consecutive blocks
780
array<array<int> > part (nr_flows);
781
for (id=0; id<nr_flows; id++)
782
if (brk[start][id] < brk[end][id])
783
if (starts (flow_fl[id], flb)) {
784
int i, i1= brk[start][id], i2= brk[end][id];
787
i= find_end_block (flow[id], i, i2);
792
// handle floats which may be placed inside text
793
for (sid=0; sid<nr_flows; sid++)
794
if (N(part[sid]) != 0) {
795
path sfl= flow_fl[sid];
796
if ((!atom (sfl)) && (last_item (path_up (sfl)) == 1) &&
797
(last_item (path_up (sfl, 2)) == nr_cols))
800
array<int> extra (0);
801
id= flow_id (path_up (sfl, 2));
802
for (i=0; i<N(part[sid])-1; i++) {
803
int spos= part[sid][i];
804
bool flag= float_property (flow[sid][spos], 'h');
806
int pos= fast_find (flow[id], flow[sid][spos]);
807
for (j=0; j<N(part[id])-1; j++)
808
if ((pos >= part[id][j]+3) && (pos <= part[id][j+1]-3))
813
array<int> merge (0);
814
for (i=0, j=0; i<N(part[id]); ) {
815
if ((j == N(extra)) || (part[id][i] <= extra[j]))
816
merge << part[id][i++];
818
if ((N(merge) == 0) || (merge[N(merge)-1] != extra[j]))
827
// fill pagelet with insertions of consecutive blocks
829
for (id=0; id<nr_flows; id++)
830
if (brk[start][id] < brk[end][id])
831
if (starts (flow_fl[id], flb)) {
833
path fl= flow_fl[id];
834
if (!atom (fl)) ch= last_item (path_up (fl));
835
for (i=1; i<N(part[id]); i++) {
837
if (last_item (flow_fl[id]) == nr_cols) {
838
bool flag= (i == N(part[id])-1) && last_break (start, end, id);
839
ins= make_insertion (id, ch, part[id][i-1], part[id][i], flag);
840
// cout << "flow " << id << " : "
841
// << part[id][i-1] << " -- " << part[id][i] << " " << ins->ht
842
// << ", cor= " << ins->bot_cor << ", " << ins->top_cor
843
// << ", penalty= " << ins->pen << LF;
846
else if ((nr_cols == 1) && (path_up (flow_fl[id]) == flb)) {
847
path p1= flow[id][part[id][i-1]];
848
path p2= path_inc (flow[id][part[id][i]-1]);
850
search_mcol_breaks (brk[start], brk[end], part, p1, p2, i1, i2);
851
ins= make_multi_column (i1, i2, flb, last_item (flow_fl[id]));
852
// cout << "flow " << id << " : "
853
// << part[id][i-1] << " -- " << part[id][i] << " " << ins->ht
854
// << ", cor= " << ins->bot_cor << ", " << ins->top_cor
855
// << ", penalty= " << ins->pen << LF;
861
// sort and compute height
863
int i, n= N(pg->ins);
864
for (i=0; i<n-1; i++) {
865
insertion ins= pg->ins[i];
866
insertion next= pg->ins[i+1];
867
if (ins->type != next->type) {
868
if (is_tuple (next->type, "footnote")) {
869
// cout << "add : footnote " << fnote_sep << LF;
872
else if (is_tuple (ins->type, "float")) {
873
if (!is_tuple (next->type, "float")) {
874
// cout << "add : float " << float_sep << LF;
878
else if (is_tuple (ins->type, "multi-column") ||
879
is_tuple (next->type, "multi-column")) {
880
page_item item= access (l, path_dec (ins->end));
881
// cout << "add : multi-column " << item->spc << LF;
885
if (is_tuple (ins->type, "footnote"))
886
if (is_tuple (next->type, "footnote")) {
887
page_item item= access (l, path_dec (ins->end));
888
// cout << "add : inter-footnote " << (item->spc+fn_sep) << LF;
889
pg << (item->spc + fn_sep);
891
if (is_tuple (next->type, "float")) {
892
// cout << "add : float " << float_sep << LF;
897
// cout << "height : " << pg->ht << LF;
898
// cout << "penalty: " << pg->pen << LF;
899
// cout << UNINDENT << "Pagelet: " << pg << LF << LF;
904
stretch_space (space spc, double stretch) {
905
if (stretch > 0.0) return (SI) (spc->def + stretch * (spc->max - spc->def));
906
if (stretch < 0.0) return (SI) (spc->def + stretch * (spc->def - spc->min));
911
page_breaker_rep::format_insertion (insertion& ins, double stretch) {
912
// cout << "Stretch " << ins << ": " << stretch << LF;
913
ins->stretch= stretch;
914
skeleton sk = ins->sk;
915
if (N(sk) == 0) return vpenalty ();
919
SI ht= stretch_space (ins->ht, stretch);
920
// cout << "Formatting multicolumn " << ins->ht
921
// << " stretch " << stretch
922
// << " -> height " << ht << LF << INDENT;
923
for (i=0; i<k; i++) {
925
// cout << i << ": " << pg->ht;
926
double pg_stretch= 0.0;
927
if (ht > pg->ht->max) pg_stretch= 1.0;
928
else if (ht < pg->ht->min) pg_stretch= -1.0;
929
else if ((ht > pg->ht->def) && (pg->ht->max > pg->ht->def))
931
((double) (ht - pg->ht->def)) /
932
((double) (pg->ht->max - pg->ht->def));
933
else if ((ht < pg->ht->def) && (pg->ht->def > pg->ht->min))
935
((double) (ht - pg->ht->def)) /
936
((double) (pg->ht->def - pg->ht->min));
937
// cout << " -> " << pg_stretch << LF;
938
pen += format_pagelet (pg, pg_stretch);
939
pen += pg->pen + as_vpenalty (pg->ht->def - ht);
941
// cout << UNINDENT << "Formatted multicolumn, penalty= " << pen << LF;
946
page_breaker_rep::format_pagelet (pagelet& pg, double stretch) {
947
// cout << "Stretch " << pg << ": " << stretch << LF;
950
pg->stretch= stretch;
951
for (i=0; i<N(pg->ins); i++)
952
pen += format_insertion (pg->ins[i], stretch);
957
page_breaker_rep::format_pagelet (pagelet& pg, space ht, bool last_page) {
958
// cout << "Formatting " << pg << ", " << ht << LF << INDENT;
962
if (last_page && (pg->ht->def <= ht->def)) {
963
// cout << "Eject last page" << LF;
966
else if ((ht->def >= pg->ht->min) && (ht->def <= pg->ht->max)) {
967
if (ht->def > pg->ht->def) {
968
// cout << "Stretch" << LF;
970
((double) (ht->def - pg->ht->def)) /
971
((double) (pg->ht->max - pg->ht->def));
973
else if (ht->def < pg->ht->def) {
974
// cout << "Shrink" << LF;
976
((double) (ht->def - pg->ht->def)) /
977
((double) (pg->ht->def - pg->ht->min));
979
pen= as_vpenalty (ht->def- pg->ht->def);
981
else if ((ht->def < pg->ht->min) && (ht->max >= pg->ht->min)) {
982
// cout << "Extend page" << LF;
984
pen= vpenalty (EXTEND_PAGE_PENALTY) + as_vpenalty (ht->def- pg->ht->def);
986
else if ((ht->def > pg->ht->max) && (ht->min <= pg->ht->max)) {
987
// cout << "Reduce page" << LF;
989
pen= vpenalty (REDUCE_PAGE_PENALTY) + as_vpenalty (ht->def- pg->ht->def);
991
else if (ht->max < pg->ht->min) {
992
// cout << "Overfull page" << LF;
994
double factor= ((double) max (pg->ht->def, 1))/((double) max (ht->def, 1));
995
if (factor < 1.0 ) factor= 1.0;
996
if (factor > 100.0) factor= 100.0;
997
pen= vpenalty ((int) (factor * TOO_LONG_PENALTY));
1000
// cout << "Underfull page" << LF;
1002
double factor= ((double) max (pg->ht->def, 1))/((double) max (ht->def, 1));
1003
if (factor < 0.0 ) factor= 0.0;
1004
if (factor > 0.99) factor= 0.99;
1005
pen= vpenalty ((int) ((1.0 - factor) * TOO_SHORT_PENALTY));
1007
pen += format_pagelet (pg, stretch);
1008
// cout << UNINDENT << "Formatted [ stretch= " << stretch
1009
// << ", penalty= " << (pg->pen + pen) << " ]" << LF << LF;
1010
return pg->pen + pen;
1013
/******************************************************************************
1014
* Multi column breaking routines
1015
******************************************************************************/
1018
page_breaker_rep::search_mcol_breaks (
1019
vbreak br1, vbreak br2, array<array<int> > part,
1020
path p1, path p2, int& i1, int& i2)
1022
// cout << "Search " << p1 << " -- " << p2 << " among parts " << part << LF;
1026
for (id=0; id<nr_flows; id++) {
1028
for (i=0; i<N(part[id])-1; i++)
1029
cout << " Flow " << id << ": "
1030
<< flow[id][part[id][i]] << " -- "
1031
<< path_inc (flow[id][part[id][i+1]-1]) << LF;
1033
for (i=0; i<N(part[id])-1; i++)
1034
if (var_path_inf_eq (path_inc (flow[id][part[id][i+1]-1]), p1))
1035
br1[id]= part[id][i+1];
1036
for (i=N(part[id])-2; i>=0; i--)
1037
if (var_path_inf_eq (p2, flow[id][part[id][i]]))
1038
br2[id]= part[id][i];
1041
// cout << "Search breaks " << br1 << " -- " << br2 << LF;
1042
if ((!brk_nr->contains (br1)) || (!brk_nr->contains (br2)))
1043
fatal_error ("break not found", "page_breaker_rep::search_mcol_breaks");
1049
page_breaker_rep::make_multi_column (skeleton sk, int real_nr_cols) {
1050
int i, nr_cols= N(sk);
1051
space ht = copy (sk[0]->ht);
1052
vpenalty pen= sk[0]->pen;
1053
for (i=1; i<nr_cols; i++) {
1054
ht->min= max (ht->min, sk[i]->ht->min);
1055
ht->def += sk[i]->ht->def;
1056
ht->max= min (ht->max, sk[i]->ht->max);
1060
if (ht->max < ht->min) {
1061
ht->def= ht->max= ht->min;
1062
pen += UNBALANCED_COLUMNS;
1063
for (i=1; i<nr_cols; i++)
1064
if (sk[i-1]->ht->min < sk[i]->ht->min)
1065
pen += LONGER_LATTER_COLUMN;
1068
if (ht->def < ht->min) ht->def= ht->min;
1069
if (ht->def > ht->max) ht->def= ht->max;
1071
insertion ins (tuple ("multi-column", as_string (real_nr_cols)), sk);
1080
page_breaker_rep::make_multi_column (
1081
int start, int end, path flb, int nr_cols)
1083
if ((quality>1) && (nr_cols == 2))
1084
return make_two_column (start, end, flb);
1085
// cout << "Make multicolumn "
1086
// << start << " " << brk[start] << ", "
1087
// << end << " " << brk[end ] << LF << LF << INDENT;
1090
int col, col_start= start, col_end= start;
1091
int mcid= flow_id[flb * nr_cols];
1092
page_item item= access (l, flow[mcid][brk[end][mcid]-1]);
1093
SI col_ht= brk_tot[end]->def - brk_tot[start]->def;
1094
col_ht -= item->spc->def/(nr_cols-1);
1095
// already divided by nr_cols
1096
// cout << "Column height= " << col_ht << LF;
1097
for (col=0; col<nr_cols; col++) {
1099
// avoids bug: a bizar change in col_end occurs between end of loop and
1100
// the start of the loop at the next iteration
1101
if (col_end >= end) break;
1102
SI tot= brk_tot[col_start]->def + (col_ht / nr_cols);
1103
int col_end= find_length (brk_tot, col_start, tot);
1104
col_end= max (col_start+1, col_end-2);
1105
if (col == nr_cols-1) col_end= end;
1106
while (col_end < end) {
1107
if (correct_pagelet (col_start, col_end) &&
1108
correct_pagelet (col_end, end))
1110
pagelet pg= make_pagelet (col_start, col_end, flb, nr_cols);
1111
if ((pg->pen < vpenalty (HYPH_INVALID)) &&
1112
(pg->ht->def >= col_ht))
1114
if (N(pg->ins) != 0) sk << pg;
1120
if (col_end == end) {
1121
pagelet pg= make_pagelet (col_start, col_end, flb, nr_cols);
1122
if (N(pg->ins) != 0) sk << pg;
1127
// cout << UNINDENT << "Multicolumn: " << sk << LF;
1128
return make_multi_column (sk, nr_cols);
1132
page_breaker_rep::tc_propose_break (path flb) {
1133
if (!correct_pagelet (tc_start, tc_middle)) return INVALID_BREAK;
1134
if (!correct_pagelet (tc_middle, tc_end)) return INVALID_BREAK;
1135
pagelet pg1= make_pagelet (tc_start, tc_middle, flb, 2);
1136
pagelet pg2= make_pagelet (tc_middle, tc_end, flb, 2);
1137
bool first_longer = (pg1->ht->min > pg2->ht->max);
1138
bool second_longer= (pg2->ht->min > pg1->ht->max);
1140
vpenalty pen= pg1->pen + pg2->pen + as_vpenalty (pg2->ht->def - pg1->ht->def);
1141
if (first_longer || second_longer) pen += UNBALANCED_COLUMNS;
1142
if (second_longer) pen += LONGER_LATTER_COLUMN;
1143
if (nil (tc_bpg1) || (pen < tc_bpen)) {
1149
if (first_longer && (tc_middle >= tc_ref)) return BAD_BREAK;
1150
if (second_longer && (tc_middle < tc_ref)) return BAD_BREAK;
1155
page_breaker_rep::make_two_column (int start, int end, path flb) {
1156
// cout << "Make two column "
1157
// << start << " " << brk[start] << ", "
1158
// << end << " " << brk[end ] << LF << LF << INDENT;
1161
int mcid= flow_id[flb * 2];
1162
page_item item= access (l, flow[mcid][brk[end][mcid]-1]);
1163
SI col_ht= brk_tot[end]->def - brk_tot[start]->def - item->spc->def;
1164
// already divided by 2
1165
// cout << "Column height= " << col_ht << LF;
1166
SI tot= brk_tot[start]->def + (col_ht / 2);
1167
tc_ref= find_length (brk_tot, start, tot);
1172
tc_bpen = vpenalty (MAX_SI, MAX_SI);
1173
tc_bpg1 = pagelet ();
1174
tc_bpg2 = pagelet ();
1177
if ((tc_ref > tc_start) && (tc_ref < tc_end)) tc_ld << tc_ref;
1178
while (N(tc_ld) != 0) {
1179
// cout << "Two column ladder= " << tc_ld << LF;
1180
tc_middle= tc_ld[0];
1181
int status= tc_propose_break (flb);
1182
if ((status == BAD_BREAK) && (tc_bpen < vpenalty (HYPH_INVALID)))
1183
tc_ld= sub (tc_ld, 1, N(tc_ld));
1185
if (tc_middle+1 >= tc_end) tc_ld= ladder ();
1186
else tc_ld= inc_merge (brk_next[tc_middle+1], sub (tc_ld, 1, N(tc_ld)));
1191
if (((tc_ref-1) > tc_start) && ((tc_ref-1) < tc_end)) tc_ld << (tc_ref-1);
1192
while (N(tc_ld) != 0) {
1193
// cout << "Two column ladder= " << tc_ld << LF;
1194
tc_middle= tc_ld[0];
1195
int status= tc_propose_break (flb);
1196
if ((status == BAD_BREAK) && (tc_bpen < vpenalty (HYPH_INVALID)))
1197
tc_ld= sub (tc_ld, 1, N(tc_ld));
1199
if (tc_middle-1 <= tc_start) tc_ld= ladder ();
1200
else tc_ld= dec_merge (brk_prev[tc_middle-1], sub (tc_ld, 1, N(tc_ld)));
1205
sk << make_pagelet (tc_start, tc_end, flb, 2);
1211
// cout << UNINDENT << "Two column: " << sk << LF;
1212
return make_multi_column (sk, 2);
1215
/******************************************************************************
1216
* Fast page breaking routines
1217
******************************************************************************/
1220
page_breaker_rep::fast_break_page (int i1, int& first_end) {
1221
first_end= max (i1+1, first_end);
1223
int i2= first_end, n= N(flow[0]);
1226
if (i1 == 0) { if (i2 > 1) spc= copy (flow_tot[0][i2-2]); }
1227
else spc= flow_tot[0][i2-2] - flow_tot[0][i1-1];
1228
SI top_cor= flow_cor[0][i1]->max;
1229
SI bot_cor= flow_cor[0][i2-1]->min;
1230
spc += space (top_cor + flow_cor[0][i2-1]->def + bot_cor);
1232
int bpen= access (l, flow[0][i2-1])->penalty;
1233
if (i2 >= n) bpen= 0;
1234
if (bpen < HYPH_INVALID) {
1236
if (spc->max < height->min) first_end= i2;
1237
vpenalty pen= best_pens[i1] + vpenalty (bpen);
1238
if ((i2 < n) || (!last_page_flag))
1239
pen += as_vpenalty (spc->def - height->def);
1240
if (((i2 < n) || (!last_page_flag)) && (spc->max < height->def)) {
1241
if (spc->max >= height->min) pen += EXTEND_PAGE_PENALTY;
1244
((double) max (spc->def, 1))/((double) max (height->def, 1));
1245
if (factor < 0.0 ) factor= 0.0;
1246
if (factor > 0.99) factor= 0.99;
1247
pen= vpenalty ((int) ((1.0 - factor) * TOO_SHORT_PENALTY));
1250
else if (spc->min > height->def) {
1251
if (spc->min <= height->max) pen += REDUCE_PAGE_PENALTY;
1254
((double) max (spc->def, 1))/((double) max (height->def, 1));
1255
if (factor < 1.0 ) factor= 1.0;
1256
if (factor > 100.0) factor= 100.0;
1257
pen= vpenalty ((int) (factor * TOO_LONG_PENALTY));
1260
if (pen < best_pens[i2]) {
1265
if ((i2 >= n) || (ok && (spc->min > height->max))) break;
1271
page_breaker_rep::fast_assemble_skeleton (skeleton& sk, int end) {
1272
int start= best_prev[end], n= N(flow[0]);
1273
if (start < 0) return;
1274
fast_assemble_skeleton (sk, start);
1275
insertion ins= make_insertion (0, -1, start, end, end == n);
1278
bool last_page= last_page_flag && (end == n);
1279
format_pagelet (pg, height, last_page);
1284
page_breaker_rep::fast_assemble_skeleton (skeleton& sk) {
1285
int i, n= N(flow[0]);
1286
best_prev= array<int> (n+1);
1287
best_pens= array<vpenalty> (n+1);
1288
for (i=0; i<=n; i++) {
1290
best_pens [i]= HYPH_INVALID;
1293
best_pens[0]= vpenalty (0, 0);
1297
if (best_prev[i] != -1)
1298
fast_break_page (i, first_end);
1299
fast_assemble_skeleton (sk, n);
1302
/******************************************************************************
1303
* Page breaking routines
1304
******************************************************************************/
1307
page_breaker_rep::propose_break () {
1308
if (!correct_pagelet (cur_start, cur_end)) return INVALID_BREAK;
1309
pagelet pg= make_pagelet (cur_start, cur_end, path (), 1);
1313
(l[ins->end->item-1]->type == PAGE_CONTROL_ITEM) &&
1314
(l[ins->end->item-1]->t == NEW_PAGE);
1316
bool last_page= last_page_flag && (cur_end == brk_last);
1317
vpenalty pen= format_pagelet (pg, height, last_page);
1318
if (nil (best_pg) || (pen < best_pen)) {
1325
vpenalty tot_pen= pen + best_pens[cur_start];
1326
if (nil (best_pgs[cur_end]) || (tot_pen < best_pens[cur_end])) {
1327
best_prev[cur_end]= cur_start;
1328
best_pens[cur_end]= tot_pen;
1329
best_pgs [cur_end]= pg;
1333
if (last_page && (pg->ht->def <= height->def)) return VALID_BREAK;
1334
if ((height->max < pg->ht->min) && (cur_end >= cur_ref)) return BAD_BREAK;
1335
if ((height->min > pg->ht->max) && (cur_end < cur_ref)) return BAD_BREAK;
1340
page_breaker_rep::find_next_breaks () {
1341
SI tot = brk_tot[cur_start]->def + height->def;
1342
cur_ref = find_length (brk_tot, cur_start, tot);
1344
best_pen= vpenalty (MAX_SI, MAX_SI);
1345
best_pg = pagelet ();
1350
while (N(cur_ld) != 0) {
1351
// if ((--credit) <= 0) break;
1352
// cout << "Current ladder= " << cur_ld << LF;
1354
int status= propose_break ();
1355
if ((status == BAD_BREAK) && (best_pen < vpenalty (HYPH_INVALID)))
1356
cur_ld= sub (cur_ld, 1, N(cur_ld));
1358
if (cur_end+1 >= N(brk)) cur_ld= ladder ();
1359
else cur_ld= inc_merge (brk_next[cur_end+1], sub (cur_ld, 1, N(cur_ld)));
1365
if (cur_ref-1 > cur_start) cur_ld << (cur_ref-1);
1366
while (N(cur_ld) != 0) {
1367
// if ((--credit) <= 0) break;
1368
// cout << "Current ladder= " << cur_ld << LF;
1370
int status= propose_break ();
1371
if ((status == BAD_BREAK) && (best_pen < vpenalty (HYPH_INVALID)))
1372
cur_ld= sub (cur_ld, 1, N(cur_ld));
1374
if (cur_end-1 <= cur_start) cur_ld= ladder ();
1375
else cur_ld= dec_merge (brk_prev[cur_end-1], sub (cur_ld, 1, N(cur_ld)));
1381
page_breaker_rep::assemble_skeleton (skeleton& sk, int last) {
1382
// cout << "Assemble until " << last << LF;
1383
if (last == brk_first) return;
1384
if (best_prev[last] == -1)
1385
fatal_error ("unfinished skeleton", "page_breaker_rep::assemble_skeleton");
1386
assemble_skeleton (sk, best_prev[last]);
1387
sk << best_pgs[last];
1391
page_breaker_rep::assemble_skeleton (skeleton& sk) {
1392
int i, nrb= N(brk), nrinit= (quality>0? nrb: 0);
1393
best_prev= array<int> (nrinit);
1394
best_pens= array<vpenalty> (nrinit);
1395
best_pgs = array<pagelet> (nrinit);
1396
for (i=0; i<nrinit; i++) {
1398
best_pens[i]= vpenalty (MAX_SI, MAX_SI);
1399
best_pgs [i]= pagelet ();
1402
best_prev[brk_first]= -2;
1403
best_pens[brk_first]= vpenalty (0, 0);
1406
cur_start= brk_first;
1408
while (cur_start != brk_last) {
1409
if (best_prev[cur_start] != -1)
1410
find_next_breaks ();
1411
// cout << HRULE << LF << LF;
1414
assemble_skeleton (sk, brk_last);
1417
while (cur_start != brk_last) {
1418
find_next_breaks ();
1419
// cout << HRULE << LF;
1420
// cout << "Eject " << best_pg << LF;
1421
// cout << HRULE << LF << LF;
1423
cur_start= best_end;
1429
page_breaker_rep::assemble_skeleton (skeleton& sk, int start, int end) {
1430
// cout << "Building skeleton " << start << " -- " << end << "\n";
1431
init_flows (start, end);
1432
// cout << "Flows done" << LF;
1433
// cout << "nr_flows = " << nr_flows << LF;
1434
// cout << "flow_id = " << flow_id << LF;
1435
// cout << "flow_fl = " << flow_fl << LF;
1436
// cout << "flow = " << flow << LF;
1437
// cout << "flow_ht = " << flow_ht << LF;
1438
// cout << "flow_cor = " << flow_cor << LF;
1439
// cout << "flow_tot = " << flow_tot << LF;
1440
// cout << "flow_cont= " << flow_cont << LF;
1441
// show_penalties ();
1442
if ((nr_flows == 1) && (flow_fl[0] == path (1))) {
1443
fast_assemble_skeleton (sk);
1444
// cout << "Skeleton done" << LF;
1445
// cout << "sk= " << sk << LF;
1449
// cout << "Breaks done" << LF;
1450
// cout << "brk = " << brk << LF;
1451
// cout << "brk_tot = " << brk_tot << LF;
1453
// cout << "Sorting done" << LF;
1454
// cout << "brk = " << brk << LF;
1455
// cout << "brk_tot = " << brk_tot << LF;
1457
// cout << "Ladders done" << LF;
1458
// cout << "brk_prev = " << brk_prev << LF;
1459
// cout << "brk_next = " << brk_next << LF;
1460
// cout << "brk_first= " << brk_first << LF;
1461
// cout << "brk_last = " << brk_last << LF;
1462
assemble_skeleton (sk);
1463
// cout << "Skeleton done" << LF;
1464
// cout << "sk= " << sk << LF;
1465
// cout << HRULE << LF << LF;
1469
page_breaker_rep::make_skeleton () {
1472
for (i=0, j=0; j<n; j++) {
1473
if ((!papyrus_mode) && (l[j]->type == PAGE_CONTROL_ITEM))
1474
if ((l[j]->t == PAGE_BREAK) || (l[j]->t == NEW_PAGE)) {
1475
last_page_flag= (l[j]->t == NEW_PAGE);
1476
if (i<j) assemble_skeleton (sk, i, j);
1481
last_page_flag= true;
1482
assemble_skeleton (sk, i, j);
1487
/******************************************************************************
1488
* The exported page breaking routine
1489
******************************************************************************/
1492
break_pages (array<page_item> l, space ph, int qual,
1493
space fn_sep, space fnote_sep, space float_sep, font fn)
1495
page_breaker_rep* H=
1496
new page_breaker_rep (l, ph, qual, fn_sep, fnote_sep, float_sep, fn);
1497
// cout << HRULE << LF;
1498
skeleton sk= H->make_skeleton ();
added
removed
src/Typeset/Page/page_breaker.cpp
