Back to index

texmacs  1.0.7.15
page_breaker.cpp
Go to the documentation of this file.
00001 
00002 /******************************************************************************
00003 * MODULE     : page_breaker.cpp
00004 * DESCRIPTION: Page breaking
00005 * COPYRIGHT  : (C) 1999  Joris van der Hoeven
00006 *******************************************************************************
00007 * This software falls under the GNU general public license version 3 or later.
00008 * It comes WITHOUT ANY WARRANTY WHATSOEVER. For details, see the file LICENSE
00009 * in the root directory or <http://www.gnu.org/licenses/gpl-3.0.html>.
00010 ******************************************************************************/
00011 
00012 #include "Line/lazy_vstream.hpp"
00013 #include "vpenalty.hpp"
00014 #include "skeleton.hpp"
00015 
00016 #include "merge_sort.hpp"
00017 void sort (pagelet& pg);
00018 vpenalty as_vpenalty (SI diff);
00019 
00020 typedef array<int>               vbreak;
00021 typedef array<int>               ladder;
00022 #define MAIN_FLOW    0
00023 #define FNOTE_FLOW   1
00024 #define FLOAT_FLOW   2
00025 #define NR_FLOWS     3
00026 
00027 #define INVALID_BREAK  0
00028 #define BAD_BREAK      1
00029 #define VALID_BREAK    2
00030 
00031 /******************************************************************************
00032 * The page_breaker class
00033 ******************************************************************************/
00034 
00035 struct page_breaker_rep {
00036   array<page_item> l;
00037   int   papyrus_mode;
00038   int   sub_start;
00039   int   sub_end;
00040   space height;
00041   space fn_sep;
00042   space fnote_sep;
00043   space float_sep;
00044   font  fn;
00045   bool  last_page_flag;
00046 
00047   int                 nr_flows;   // number of flows;
00048   hashmap<path,int>   flow_id;    // unique number for each flow
00049   array<path>         flow_fl;    // flow associated to flow identifier
00050   array<array<path> >  flow;       // for each flow the paths to all page_items
00051   array<array<space> > flow_ht;    // the heights of these page_items
00052   array<array<space> > flow_cor;   // top and bottom corrections of page_items
00053   array<array<space> > flow_tot;   // total heights up to a certain index
00054   array<array<int> >   flow_cont;  // number of contiguous blocks until here
00055 
00056   array<vbreak>       brk;        // possible break points
00057   array<space>        brk_tot;    // (estimated) total height until breaks
00058   array<vbreak>       tmp;        // temporary space during sort
00059   array<space>        tmp_tot;    // temporary space during sort
00060   hashmap<vbreak,int> brk_nr;     // find number of break from break
00061   array<ladder>       brk_prev;   // maximal previous incomparable breaks
00062   array<ladder>       brk_next;   // minimal next incomparable breaks
00063   int                 brk_first;  // first break
00064   int                 brk_last;   // last break
00065 
00066   int                 tc_start;   // two column start
00067   int                 tc_middle;  // two column middle
00068   int                 tc_end;     // two column end
00069   int                 tc_ref;     // two column reference
00070   ladder              tc_ld;      // two column ladder
00071   int                 tc_bmid;    // best middle
00072   vpenalty            tc_bpen;    // corresponding penalty
00073   pagelet             tc_bpg1;    // & left column
00074   pagelet             tc_bpg2;    // & right column
00075 
00076   int                 quality;    // quality of page breaking
00077   int                 cur_start;  // current start of page
00078   int                 cur_end;    // current end of page
00079   int                 cur_ref;    // current approximation of best end
00080   ladder              cur_ld;     // current ladder for untreated tries
00081   int                 best_end;   // best end of page for given start
00082   vpenalty            best_pen;   // corresponding penalty
00083   pagelet             best_pg;    // & pagelet
00084   array<int>          best_prev;  // best previous break points
00085   array<vpenalty>     best_pens;  // corresponding penalties
00086   array<pagelet>      best_pgs;   // & pagelets
00087 
00088   page_breaker_rep (array<page_item> l, space ph, int quality,
00089                       space fn_sep, space fnote_sep,
00090                       space float_sep, font fn);
00091 
00092   void init_flows (int start, int end);
00093   void init_flows (array<page_item> l, int start, int end, path p, path flb);
00094   void show_penalties ();
00095 
00096   bool correct_break (vbreak br, int id);
00097   bool correct_break (vbreak br);
00098   void spool_break (vbreak& br, path flb, path start);
00099   void rewind_break (vbreak& br, path flb, int& id, path& p);
00100   bool float_property (path p, char c);
00101   array<vbreak> generate_breaks (vbreak br, int id);
00102   array<vbreak> generate_breaks (vbreak br, int id, path flb);
00103   space compute_total_height (vbreak br);
00104   void init_breaks ();
00105   void sort_breaks (int start, int end);
00106   void sort_breaks ();
00107 
00108   void init_ladders ();
00109   ladder inc_merge (ladder ld1, ladder ld2);
00110   ladder dec_merge (ladder ld1, ladder ld2);
00111 
00112   bool correct_pagelet (int start, int end);
00113   bool last_break (int start, int end, int id);
00114   insertion make_insertion (int id, int ch, int i1, int i2, bool flag);
00115   pagelet make_pagelet (int start, int end, path flb, int nr_cols);
00116   vpenalty format_insertion (insertion& ins, double stretch);
00117   vpenalty format_pagelet (pagelet& pg, double stretch);
00118   vpenalty format_pagelet (pagelet& pg, space ht, bool last_page);
00119 
00120   void search_mcol_breaks (vbreak br1, vbreak br2, array<array<int> > part,
00121                         path p1, path p2, int& i1, int& i2);
00122   insertion make_multi_column (skeleton sk, int real_nr_cols);
00123   insertion make_multi_column (int start, int end, path flb, int nr_cols);
00124   int tc_propose_break (path flb);
00125   insertion make_two_column (int start, int end, path flb);
00126 
00127   void fast_break_page (int i1, int& first_end);
00128   void fast_assemble_skeleton (skeleton& sk, int end);
00129   void fast_assemble_skeleton (skeleton& sk);
00130 
00131   int propose_break ();
00132   void find_next_breaks ();
00133   void assemble_skeleton (skeleton& sk, int last);
00134   void assemble_skeleton (skeleton& sk);
00135   void assemble_skeleton (skeleton& sk, int start, int end);
00136   skeleton make_skeleton ();
00137 };
00138 
00139 /******************************************************************************
00140 * Constructor
00141 ******************************************************************************/
00142 
00143 page_breaker_rep::page_breaker_rep (
00144   array<page_item> l2, space ph, int quality2,
00145   space fn_sep2, space fnote_sep2, space float_sep2, font fn2):
00146     l (l2), papyrus_mode (ph == (MAX_SI >> 1)), height (ph),
00147     fn_sep (fn_sep2), fnote_sep (fnote_sep2), float_sep (float_sep2),
00148     fn (fn2), flow_id (-1), brk_nr (-1), quality (quality2)
00149 {}
00150 
00151 /******************************************************************************
00152 * Subroutines
00153 ******************************************************************************/
00154 
00155 bool
00156 var_path_inf_eq (path p1, path p2) {
00157   if (is_nil (p1) || is_nil (p2)) return is_nil (p1);
00158   if (p1->item<p2->item) return true;
00159   if (p1->item>p2->item) return false;
00160   return var_path_inf_eq (p1->next, p2->next);
00161 }
00162 
00163 static int
00164 fast_find (array<path> a, path p) {
00165   int n= N(a), step= n, i= n>>1;
00166   while (step>1) {
00167     step= (step+1)>>1;
00168     if (var_path_inf_eq (p, a[i])) i= max (0, i-step);
00169     else i= min (n-1, i+step);
00170   }
00171   if (!var_path_inf_eq (p, a[i])) i= i+1;
00172   return i;
00173 }
00174 
00175 static int
00176 find_length (array<space> a, int start, SI ht) {
00177   int n= N(a)- start, step= n, i= (start + N(a))>>1;
00178   while (step>1) {
00179     step= (step+1)>>1;
00180     if (ht <= a[i]->def) i= max (start, i-step);
00181     else i= min (N(a)-1, i+step);
00182   }
00183   if (ht > a[i]->def) i= min (N(a)-1, i+1);
00184   return i;
00185 }
00186 
00187 static int
00188 find_end_block (array<path> a, int start, int end) {
00189   if (a[end-1] == path_add (a[start], end-1-start)) return end;
00190   int n= end-start, step= n, i= (start+end+1)>>1;
00191   while (step>1) {
00192     step= (step+1)>>1;
00193     if ((i>start) && (a[i-1] != path_add (a[start], i-1-start)))
00194       i= max (start, i-step);
00195     else i= min (end-1, i+step);
00196   }
00197   if ((i>start) && (a[i-1] != path_add (a[start], i-1-start))) i--;
00198   return i;
00199 }
00200 
00201 /*static*/ page_item
00202 access (array<page_item> l, path p) {
00203   page_item item= l[p->item];
00204   if (is_nil (p->next)) return item;
00205   else {
00206     lazy_vstream ins= (lazy_vstream) item->fl[p->next->item];
00207     return access (ins->l, p->next->next);
00208   }
00209 }
00210 
00211 /*static*/ array<page_item>
00212 sub (array<page_item> l, path p, path q) {
00213   if (is_atom (p) && is_atom (q)) {
00214     int i= p->item, j= q->item, k;
00215     array<page_item> r (j-i);
00216     for (k=i; k<j; k++) r[k-i]= l[k];
00217     return r;
00218   }
00219   else {
00220     if ((N(p) <= 2) || (N(q) <= 2)) {
00221       cerr << "\nThe paths were " << p << " and " << q << "\n";
00222       FAILED ("paths to short");
00223     }
00224     if ((p->item != q->item) || (p->next->item != q->next->item)) {
00225       cerr << "\nThe paths were " << p << " and " << q << "\n";
00226       FAILED ("paths don't match");
00227     }
00228     page_item item= l[p->item];
00229     lazy_vstream ins= (lazy_vstream) item->fl[p->next->item];
00230     return sub (ins->l, p->next->next, q->next->next);
00231   }
00232 }
00233 
00234 static inline bool
00235 starts (path p, path q) {
00236   return (N(p) >= N(q)) && (head (p, N(q)) == q);
00237 }
00238 
00239 /******************************************************************************
00240 * Initialize flows
00241 ******************************************************************************/
00242 
00243 void
00244 page_breaker_rep::init_flows (int start, int end) {
00245   sub_start= start;
00246   sub_end  = end;
00247   nr_flows = 0;
00248   flow_id  = hashmap<path,int> (-1);
00249   flow_fl  = array<path> (0);
00250   flow     = array<array<path> > (0);
00251   flow_ht  = array<array<space> > (0);
00252   flow_cor = array<array<space> > (0);
00253   flow_tot = array<array<space> > (0);
00254   flow_cont= array<array<int> > (0);
00255   init_flows (l, start, end, path (), path ());
00256 }
00257 
00258 void
00259 page_breaker_rep::init_flows (
00260   array<page_item> l, int start, int end, path p, path flb)
00261 {
00262   int i;
00263   for (i=start; i<end; i++) {
00264     path fl= flb * l[i]->nr_cols;
00265     if (!flow_id->contains (fl)) {
00266       flow_id (fl)= nr_flows;
00267       flow_fl   << fl;
00268       flow      << array<path> (0);
00269       flow_ht   << array<space> (0);
00270       flow_cor  << array<space> (0);
00271       flow_tot  << array<space> (0);
00272       flow_cont << array<int> (0);
00273       nr_flows++;
00274     }
00275     int  id= flow_id (fl);
00276     int  nr= N (flow_tot [id]);
00277     SI   bot_cor= max (0, l[i]->b->y1- fn->y1);
00278     SI   bod_cor= l[i]->b->h ();
00279     SI   top_cor= max (0, fn->y2- l[i]->b->y2);
00280     bool cont= (nr>0) && (path_up (flow[id][nr-1]) == p);
00281     flow     [id] << (p * i);
00282     flow_ht  [id] << (space (l[i]->b->h()) + l[i]->spc);
00283     flow_cor [id] << space (bot_cor, bod_cor, top_cor);
00284     flow_tot [id] << (nr==0? space(0): flow_tot[id][nr-1]) + flow_ht[id][nr];
00285     flow_cont[id] << (nr==0? 1: flow_cont[id][nr-1] + (cont? 0: 1));
00286     if ((i==end-1) || (l[i]->nr_cols!=l[i+1]->nr_cols)) l[i]->penalty=0;
00287   }
00288 
00289   for (i=start; i<end; i++) {
00290     path fl= flb * l[i]->nr_cols;
00291     int j, k= N (l[i]->fl);
00292     for (j=0; j<k; j++) {
00293       int ch= -1;
00294       lazy_vstream ins= (lazy_vstream) l[i]->fl[j];
00295       array<page_item> sub_l= ins->l;
00296       if (is_tuple (ins->channel, "footnote")) ch= 0;
00297       else if (is_tuple (ins->channel, "float")) ch= 1;
00298       init_flows (sub_l, 0, N(sub_l), p * path (i, j), fl * ch);
00299     }
00300   }
00301 }
00302 
00303 void
00304 page_breaker_rep::show_penalties () {
00305   int id, i;
00306   for (id=0; id<nr_flows; id++)
00307     for (i=0; i<N(flow[id]); i++)
00308       cout << id << ", " << i << ":\t" << flow[id][i] << " -> "
00309           << access (l, flow[id][i])->penalty << "\n";
00310 }
00311 
00312 /******************************************************************************
00313 * Initialize possible breaks
00314 ******************************************************************************/
00315 
00316 bool
00317 page_breaker_rep::correct_break (vbreak br, int id) {
00318   if ((br[id] > 0) && (br[id] < N(flow[id]))) {
00319     path p= flow[id][br[id]-1];
00320     if (path_inc (p) != flow[id][br[id]]) return true;
00321     if (access (l, p)->penalty >= HYPH_INVALID) return false;
00322   }
00323   return true;
00324 }
00325 
00326 
00327 bool
00328 page_breaker_rep::correct_break (vbreak br) {
00329   int id;
00330   for (id=0; id<nr_flows; id++)
00331     if (!correct_break (br, id)) return false;
00332   return true;
00333 }
00334 
00335 void
00336 page_breaker_rep::spool_break (vbreak& br, path flb, path start) {
00337   int id;
00338   for (id=0; id<nr_flows; id++)
00339     if (path_up (flow_fl[id]) == flb)
00340       br[id]= fast_find (flow[id], start);
00341 }
00342 
00343 void
00344 page_breaker_rep::rewind_break (
00345   vbreak& br, path flb, int& best_id, path& best_p)
00346 {
00347   int id;
00348   best_id= -1;
00349   best_p = path ();
00350   for (id=0; id<nr_flows; id++)
00351     if (path_up (flow_fl[id]) == flb)
00352       if ((br[id]>0) && var_path_inf_eq (best_p, flow[id][br[id]-1])) {
00353        best_id= id;
00354        best_p = flow[id][br[id]-1];
00355       }
00356   if (best_id != -1) br[best_id]--;
00357 }
00358 
00359 bool
00360 page_breaker_rep::float_property (path p, char c) {
00361   int i;
00362   page_item item= access (l, path_up (p, 2));
00363   lazy_vstream ins= (lazy_vstream) item->fl [last_item (path_up (p))];
00364   string s= as_string (ins->channel[1]);
00365   for (i=0; i<N(s); i++)
00366     if (s[i] == c) return true;
00367   return false;
00368 }
00369 
00370 array<vbreak>
00371 page_breaker_rep::generate_breaks (vbreak br, int id)
00372   // generate all breaks by filling in the (-1) entries in 'br'
00373   // by break points for subflows of the flow with identifier 'id'
00374 {
00375   // cout << "Generate breaks " << br << ", " << id << LF;
00376 
00377   path flb= path_up (flow_fl[id]);
00378   int sid;
00379   for (sid=0; sid<nr_flows; sid++) 
00380     if (br[sid] == -1) {
00381       path sflb= path_up (flow_fl[sid]);
00382       if ((N(sflb) == (N(flb)+2)) && starts (sflb, flb)) break;
00383     }
00384   if (sid == nr_flows) {
00385     array<vbreak> brk (1);
00386     brk[0]= br;
00387     return brk;
00388   }
00389   else {
00390     int j;
00391     array<vbreak> brk;
00392     array<vbreak> ref=
00393       generate_breaks (copy (br), id, path_up (flow_fl[sid]));
00394     for (j=0; j<N(ref); j++)
00395       brk << generate_breaks (copy (ref[j]), id);
00396     return brk;
00397   }
00398 }
00399 
00400 array<vbreak>
00401 page_breaker_rep::generate_breaks (vbreak br, int id, path flb)
00402   // generate all breaks by filling in the (-1) entries in 'br'
00403   // by break points for subflows of the form 'flb * nr_cols' and
00404   // only those break points which are relevant for the given break 'br[id]'
00405   // for the flow with identifier 'id' (which may be -1 for the top flow)
00406 {
00407   // cout << "Generate breaks " << br << ", " << id << ", " << flb << LF;
00408 
00409   int sid;
00410   path halt;
00411   if (id == -1) {
00412     halt= path (sub_end);
00413     for (sid=0; sid<nr_flows; sid++)
00414       if (is_atom (flow_fl[sid]))
00415        br[sid]= 0;
00416   }
00417   else if (br[id]==0) {
00418     halt= path (0);
00419     for (sid=0; sid<nr_flows; sid++)
00420       if (path_up (flow_fl[sid]) == flb)
00421        br[sid]=0;
00422   }
00423   else {
00424     halt= path_inc (flow[id][br[id]-1]);
00425     path start= flow[id][br[id]-1];
00426     while (last_item (start) != 0) {
00427       if (access (l, path_dec (start))->penalty < HYPH_INVALID) break;
00428       start= path_dec (start);
00429     }
00430     if ((!is_nil (flb)) && (last_item (flb) == 1)) {
00431       int credit= 3;
00432       spool_break (br, flb, halt);
00433       while (true) {
00434        path p;
00435        vbreak old= copy (br);
00436        rewind_break (br, flb, sid, p);
00437        if ((sid == -1) || (br == old)) break;
00438        if (float_property (flow[sid][br[sid]], 'f')) {
00439          br= old;
00440          break;
00441        }
00442        if (var_path_inf_eq (p, start)) {
00443          if (correct_break (br)) credit--;
00444          if (credit == 0) break;
00445        }
00446       }
00447     }
00448     else spool_break (br, flb, start);
00449   }
00450 
00451   array<vbreak> brk (0);
00452   if (correct_break (br)) {
00453     int  best_sid= -1;
00454     path best_p (MAX_SI);
00455     for (sid=0; sid<nr_flows; sid++)
00456       if (path_up (flow_fl[sid]) == flb) {
00457        int pos= br[sid];
00458        if (best_sid == -1) best_sid= sid;
00459        if ((pos > 0) && path_inf (flow[sid][pos-1], best_p)) {
00460          best_sid= sid;
00461          best_p  = flow[sid][pos-1];
00462        }
00463       }
00464     ASSERT (best_sid != -1, "flow not found");
00465     brk << generate_breaks (copy (br), best_sid);
00466   }
00467 
00468   while (true) {
00469     int  best_sid= -1;
00470     path best_p= halt;
00471     for (sid=0; sid<nr_flows; sid++)
00472       if (path_up (flow_fl[sid]) == flb) {
00473        int pos= br[sid];
00474        if ((pos < N(flow[sid])) && path_inf (flow[sid][pos], best_p)) {
00475          best_sid= sid;
00476          best_p  = flow[sid][pos];
00477        }
00478       }
00479     if (best_sid == -1) break;
00480     br[best_sid]++;
00481     if (correct_break (br))
00482       brk << generate_breaks (copy (br), best_sid);
00483   }
00484   return brk;
00485 }
00486 
00487 space
00488 page_breaker_rep::compute_total_height (vbreak br) {
00489   int id;
00490   space tot;
00491   // cout << "Total height of break " << br << LF;
00492   for (id=0; id<nr_flows; id++) {
00493     path fl= flow_fl[id];
00494     space stot= br[id]==0? space (0): copy (flow_tot[id][br[id]-1]);
00495     if (!is_atom (fl)) {
00496       int ch  = last_item (path_up (fl));
00497       int cont= br[id]==0? 0: flow_cont[id][br[id]-1];
00498       if (ch == 0)
00499        stot += space (0, cont * fnote_sep->def / 2, cont * fnote_sep->max);
00500       if (ch == 1)
00501        stot += space (cont * float_sep->min,
00502                      (3 * cont * float_sep->def) / 2,
00503                      2 * cont * float_sep->max);
00504     }
00505     int nr_cols= last_item (fl);
00506     // cout << "  " << id << ", " << br[id] << ":\t" << (stot/nr_cols) << LF;
00507     tot += stot / nr_cols;
00508   }
00509   return tot;
00510 }
00511 
00512 void
00513 page_breaker_rep::init_breaks () {
00514   int id;
00515   vbreak br (nr_flows);
00516   for (id=0; id<nr_flows; id++) br[id]= -1;
00517   brk= generate_breaks (copy (br), -1, path ());
00518 
00519   int i, brn= N(brk);
00520   brk_tot= array<space> (brn);
00521   for (i=0; i<brn; i++)
00522     brk_tot[i]= compute_total_height (brk[i]);
00523 }
00524 
00525 /******************************************************************************
00526 * Sort the breaks on expected default total height
00527 ******************************************************************************/
00528 
00529 void
00530 page_breaker_rep::sort_breaks (int start, int end) {
00531   if (end-start<=1) return;
00532   if (end-start==2) {
00533     if (!(brk_tot[start]->def <= brk_tot[start+1]->def)) {
00534       tmp    [start]  = brk    [start];
00535       tmp_tot[start]  = brk_tot[start];
00536       brk    [start]  = brk    [start+1];
00537       brk_tot[start]  = brk_tot[start+1];
00538       brk    [start+1]= tmp    [start];
00539       brk_tot[start+1]= tmp_tot[start];
00540     }
00541     return;
00542   }
00543   int middle= (start+end) >> 1; 
00544   sort_breaks (start, middle);
00545   sort_breaks (middle, end);
00546   int i, j, k;
00547   for (i= start, j= middle, k= start; (i<middle) && (j<end); )
00548     if (brk_tot[i]->def <= brk_tot[j]->def) {
00549       tmp    [k]= brk    [i];
00550       tmp_tot[k]= brk_tot[i];
00551       k++; i++;
00552     }
00553     else {
00554       tmp    [k]= brk    [j];
00555       tmp_tot[k]= brk_tot[j];
00556       k++; j++;
00557     }
00558   j= k;
00559   while (i!=middle) {
00560     brk    [k]= brk    [i];
00561     brk_tot[k]= brk_tot[i];
00562     k++; i++;
00563   }
00564   for (i=start; i<j; i++) {
00565     brk    [i]= tmp    [i];
00566     brk_tot[i]= tmp_tot[i];
00567   }
00568 }
00569 
00570 void
00571 page_breaker_rep::sort_breaks () {
00572   int i, nrb= N(brk);
00573   tmp= array<vbreak> (nrb);
00574   tmp_tot= array<space> (nrb);
00575   sort_breaks (0, nrb);
00576   for (i=0; i<nrb; i++)
00577     brk_nr (brk[i])= i;
00578 }
00579 
00580 /******************************************************************************
00581 * Initialization and manipulation of ladders
00582 ******************************************************************************/
00583 
00584 bool
00585 inf_eq (vbreak br1, vbreak br2) {
00586   int i, n= N(br1);
00587   for (i=0; i<n; i++)
00588     if (br1[i] > br2[i]) return false;
00589   return true;
00590 }
00591 
00592 void
00593 page_breaker_rep::init_ladders () {
00594   int i, j, nrb= N(brk);
00595   brk_prev= array<ladder> (nrb);
00596   brk_next= array<ladder> (nrb);
00597 
00598   ladder ld;
00599   for (i=0; i<nrb; i++) {
00600     ladder new_ld (1);
00601     new_ld[0]= i;
00602     for (j=0; j<N(ld); j++)
00603       if (!inf_eq (brk[ld[j]], brk[i]))
00604        new_ld << ld[j];
00605     ld= new_ld;
00606     brk_prev[i]= ld;
00607   }
00608 
00609   ld= ladder ();
00610   for (i=nrb-1; i>=0; i--) {
00611     ladder new_ld (1);
00612     new_ld[0]= i;
00613     for (j=0; j<N(ld); j++)
00614       if (!inf_eq (brk[i], brk[ld[j]]))
00615        new_ld << ld[j];
00616     ld= new_ld;
00617     brk_next[i]= ld;
00618   }
00619 
00620   for (i=0; i<nrb; i++) {
00621     bool flag= true;
00622     for (j=0; j<nr_flows; j++)
00623       flag= flag && (brk[i][j] == 0);
00624     if (flag) { brk_first= i; break; }
00625   }
00626 
00627   for (i=nrb-1; i>=0; i--) {
00628     bool flag= true;
00629     for (j=0; j<nr_flows; j++)
00630       flag= flag && (brk[i][j] == N(flow[j]));
00631     if (flag) { brk_last= i; break; }
00632   }
00633 }
00634 
00635 static ladder
00636 sub (ladder ld, int start, int end) {
00637   // cout << "sub " << ld << ", " << start << ", " << end;
00638   int i, n= end-start;
00639   ladder ret (n);
00640   for (i=0; i<n; i++)
00641     ret[i]= ld[start+i];
00642   // cout << " -> " << ret << LF;
00643   return ret;
00644 }
00645 
00646 ladder
00647 page_breaker_rep::dec_merge (ladder ld1, ladder ld2) {
00648   // cout << "Decreasing merge " << ld1 << ", " << ld2;
00649   int i, j, k;
00650   ladder ld;
00651   for (i=0, j=0; (i<N(ld1)) || (j<N(ld2)); ) {
00652     if ((j == N(ld2)) || ((i < N(ld1)) && (ld1[i] > ld2[j]))) {
00653       for (k=0; k<N(ld2); k++)
00654        if (inf_eq (brk[ld1[i]], brk[ld2[k]]))
00655          break;
00656       if (k == N(ld2)) ld << ld1[i];
00657       i++;
00658       continue;
00659     }
00660     if ((i == N(ld1)) || ((j < N(ld2)) && (ld2[j] > ld1[i]))) {
00661       for (k=0; k<N(ld1); k++)
00662        if (inf_eq (brk[ld2[j]], brk[ld1[k]]))
00663          break;
00664       if (k == N(ld1)) ld << ld2[j];
00665       j++;
00666       continue;
00667     }
00668     ld << ld1[i];
00669     i++, j++;
00670   }
00671   // cout << " -> " << ld << LF;
00672   return ld;
00673 }
00674 
00675 ladder
00676 page_breaker_rep::inc_merge (ladder ld1, ladder ld2) {
00677   // cout << "Increasing merge " << ld1 << ", " << ld2;
00678   int i, j, k;
00679   ladder ld;
00680   for (i=0, j=0; (i<N(ld1)) || (j<N(ld2)); ) {
00681     if ((j == N(ld2)) || ((i < N(ld1)) && (ld1[i] < ld2[j]))) {
00682       for (k=0; k<N(ld2); k++)
00683        if (inf_eq (brk[ld2[k]], brk[ld1[i]]))
00684          break;
00685       if (k == N(ld2)) ld << ld1[i];
00686       i++;
00687       continue;
00688     }
00689     if ((i == N(ld1)) || ((j < N(ld2)) && (ld2[j] < ld1[i]))) {
00690       for (k=0; k<N(ld1); k++)
00691        if (inf_eq (brk[ld1[k]], brk[ld2[j]]))
00692          break;
00693       if (k == N(ld1)) ld << ld2[j];
00694       j++;
00695       continue;
00696     }
00697     ld << ld1[i];
00698     i++, j++;
00699   }
00700   // cout << " -> " << ld << LF;
00701   return ld;
00702 }
00703 
00704 /******************************************************************************
00705 * Format pagelets
00706 ******************************************************************************/
00707 
00708 bool
00709 page_breaker_rep::correct_pagelet (int start, int end) {
00710   int id, mid;
00711   for (id=0; id<nr_flows; id++)
00712     if (brk[start][id] > brk[end][id])
00713       return false;
00714   for (id=0; id<nr_flows; id++)
00715     if ((!is_atom (flow_fl[id])) && (last_item (path_up (flow_fl[id])) == 1))
00716       for (mid= 0; mid<nr_flows; mid++)
00717        if ((brk[start][mid] < brk[end][mid]) &&
00718            (flow_fl[mid] == path_up (flow_fl[id], 2)))
00719          {
00720            int idb= brk[end][id], midb= brk[start][mid];
00721            if ((idb == N(flow[id])) || (midb == N(flow[mid]))) {
00722              if (idb < N(flow[id])) return false;
00723            }
00724            else if (var_path_inf_eq (flow[id][idb], flow[mid][midb]))
00725              return false;
00726          }
00727   return true;
00728 }
00729 
00730 bool
00731 page_breaker_rep::last_break (int start, int end, int id1) {
00732   int id2;
00733   vbreak br1= brk[start], br2= brk[end];
00734   for (id2=0; id2<nr_flows; id2++)
00735     if ((id2 != id1) &&
00736        (br1[id2] < br2[id2]) &&
00737        (path_up (flow_fl[id2]) == path_up (flow_fl[id1])) &&
00738        var_path_inf_eq (flow[id1][br2[id1]-1], flow[id2][br2[id2]-1]))
00739       return false;
00740   return true;
00741 }
00742 
00743 insertion
00744 page_breaker_rep::make_insertion (int id, int ch, int i1, int i2, bool flag) {
00745   path p1= flow[id][i1];
00746   path p2= path_inc (flow[id][i2-1]);
00747   space spc;
00748   if (i1 == 0) { if (i2 > 1) spc= copy (flow_tot[id][i2-2]); }
00749   else spc= flow_tot[id][i2-2] - flow_tot[id][i1-1];
00750   SI top_cor= flow_cor[id][i1]->max;
00751   SI bot_cor= flow_cor[id][i2-1]->min;
00752   spc += space (top_cor + flow_cor[id][i2-1]->def + bot_cor);
00753 
00754   tree type= "";
00755   if (ch == 0) type= tuple ("footnote");
00756   else if (ch == 1) {
00757     // -- Why did we perform the first test before David's correction?
00758     // if ((i1>1) && (p1 != path_inc (flow[id][i1-1])))
00759     // type= tuple ("float", "t");
00760     // else if (float_property (p1, 'h')) type= tuple ("float", "h");
00761     if (float_property (p1, 'h')) type= tuple ("float", "h");
00762     else if (float_property (p1, 'b')) type= tuple ("float", "b");
00763     else type= tuple ("float", "t");
00764   }
00765 
00766   insertion ins (type, p1, p2);
00767   ins->ht     = spc;
00768   ins->top_cor= top_cor;
00769   ins->bot_cor= bot_cor;
00770   if (flag) ins->pen= access (l, flow[id][i2-1])->penalty;
00771   return ins;
00772 }
00773 
00774 pagelet
00775 page_breaker_rep::make_pagelet (int start, int end, path flb, int nr_cols) {
00776   // cout << "Make pagelet "
00777   //      << start << " " << brk[start] << ", "
00778   //      << end   << " " << brk[end  ] << ", " << nr_cols << LF << INDENT;
00779 
00780   // break flows into consecutive blocks
00781   int id, sid;
00782   array<array<int> > part (nr_flows);
00783   for (id=0; id<nr_flows; id++)
00784     if (brk[start][id] < brk[end][id])
00785       if (starts (flow_fl[id], flb)) {
00786        int i, i1= brk[start][id], i2= brk[end][id];
00787        part[id] << i1;
00788        for (i=i1; i<i2; ) {
00789          i= find_end_block (flow[id], i, i2);
00790          part[id] << i;
00791        }
00792       }
00793 
00794   // handle floats which may be placed inside text
00795   for (sid=0; sid<nr_flows; sid++)
00796     if (N(part[sid]) != 0) {
00797       path sfl= flow_fl[sid];
00798       if ((!is_atom (sfl)) && (last_item (path_up (sfl)) == 1) &&
00799          (last_item (path_up (sfl, 2)) == nr_cols))
00800        {
00801          int i, j;
00802          array<int> extra (0);
00803          id= flow_id (path_up (sfl, 2));
00804          for (i=0; i<N(part[sid])-1; i++) {
00805            int spos= part[sid][i];
00806            bool flag= float_property (flow[sid][spos], 'h');
00807            if (flag) {
00808              int pos= fast_find (flow[id], flow[sid][spos]);
00809              for (j=0; j<N(part[id])-1; j++)
00810               if ((pos >= part[id][j]+3) && (pos <= part[id][j+1]-3))
00811                 extra << pos;
00812            }
00813          }
00814          merge_sort (extra);
00815          array<int> merge (0);
00816          for (i=0, j=0; i<N(part[id]); ) {
00817            if ((j == N(extra)) || (part[id][i] <= extra[j]))
00818              merge << part[id][i++];
00819            else {
00820              if ((N(merge) == 0) || (merge[N(merge)-1] != extra[j]))
00821               merge << extra[j];
00822              j++;
00823            }
00824          }
00825          part[id]= merge;
00826        }
00827     }
00828 
00829   // fill pagelet with insertions of consecutive blocks
00830   pagelet pg (0);
00831   for (id=0; id<nr_flows; id++)
00832     if (brk[start][id] < brk[end][id])
00833       if (starts (flow_fl[id], flb)) {
00834        int i, ch=-1;
00835        path fl= flow_fl[id];
00836        if (!is_atom (fl)) ch= last_item (path_up (fl));
00837        for (i=1; i<N(part[id]); i++) {
00838          insertion ins;
00839          if (last_item (flow_fl[id]) == nr_cols) {
00840            bool flag= (i == N(part[id])-1) && last_break (start, end, id);
00841            ins= make_insertion (id, ch, part[id][i-1], part[id][i], flag);
00842            // cout << "flow " << id << " : "
00843            //      << part[id][i-1] << " -- " << part[id][i] << " " << ins->ht
00844            //      << ", cor= " << ins->bot_cor << ", " << ins->top_cor
00845            //      << ", penalty= " << ins->pen << LF;
00846            pg << ins;
00847          }
00848          else if ((nr_cols == 1) && (path_up (flow_fl[id]) == flb)) {
00849            path p1= flow[id][part[id][i-1]];
00850            path p2= path_inc (flow[id][part[id][i]-1]);
00851            int i1, i2;
00852            search_mcol_breaks (brk[start], brk[end], part, p1, p2, i1, i2);
00853            ins= make_multi_column (i1, i2, flb, last_item (flow_fl[id]));
00854            // cout << "flow " << id << " : "
00855            //      << part[id][i-1] << " -- " << part[id][i] << " " << ins->ht
00856            //      << ", cor= " << ins->bot_cor << ", " << ins->top_cor
00857            //      << ", penalty= " << ins->pen << LF;
00858            pg << ins;
00859          }
00860        }
00861       }
00862 
00863   // sort and compute height
00864   sort (pg);
00865   int i, n= N(pg->ins);
00866   for (i=0; i<n-1; i++) {
00867     insertion ins= pg->ins[i];
00868     insertion next= pg->ins[i+1];
00869     if (ins->type != next->type) {
00870       if (is_tuple (next->type, "footnote")) {
00871        // cout << "add    : footnote " << fnote_sep << LF;
00872        pg << fnote_sep;
00873       }
00874       else if (is_tuple (ins->type, "float")) {
00875        if (!is_tuple (next->type, "float")) {
00876          // cout << "add    : float " << float_sep << LF;
00877          pg << float_sep;
00878        }
00879       }
00880       else if (is_tuple (ins->type, "multi-column") ||
00881               is_tuple (next->type, "multi-column")) {
00882        page_item item= access (l, path_dec (ins->end));
00883        // cout << "add    : multi-column " << item->spc << LF;
00884        pg << item->spc;
00885       }
00886     }
00887     if (is_tuple (ins->type, "footnote"))
00888       if (is_tuple (next->type, "footnote")) {
00889        page_item item= access (l, path_dec (ins->end));
00890        // cout << "add    : inter-footnote " << (item->spc+fn_sep) << LF;
00891        pg << (item->spc + fn_sep);
00892       }
00893     if (is_tuple (next->type, "float")) {
00894       // cout << "add    : float " << float_sep << LF;
00895       pg << float_sep;
00896     }
00897   }
00898 
00899   // cout << "height : " << pg->ht << LF;
00900   // cout << "penalty: " << pg->pen << LF;
00901   // cout << UNINDENT << "Pagelet: " << pg << LF << LF;
00902   return pg;
00903 }
00904 
00905 SI
00906 stretch_space (space spc, double stretch) {
00907   if (stretch > 0.0) return (SI) (spc->def + stretch * (spc->max - spc->def));
00908   if (stretch < 0.0) return (SI) (spc->def + stretch * (spc->def - spc->min));
00909   return spc->def;
00910 }
00911 
00912 vpenalty
00913 page_breaker_rep::format_insertion (insertion& ins, double stretch) {
00914   // cout << "Stretch " << ins << ": " << stretch << LF;
00915   ins->stretch= stretch;
00916   skeleton sk = ins->sk;
00917   if (N(sk) == 0) return vpenalty ();
00918 
00919   int i, k=N(sk);
00920   vpenalty pen;
00921   SI ht= stretch_space (ins->ht, stretch);
00922   // cout << "Formatting multicolumn " << ins->ht
00923   //      << " stretch " << stretch
00924   //      << " -> height " << ht << LF << INDENT;
00925   for (i=0; i<k; i++) {
00926     pagelet& pg= sk[i];
00927     // cout << i << ": " << pg->ht;
00928     double pg_stretch= 0.0;
00929     if (ht > pg->ht->max) pg_stretch= 1.0;
00930     else if (ht < pg->ht->min) pg_stretch= -1.0;
00931     else if ((ht > pg->ht->def) && (pg->ht->max > pg->ht->def))
00932       pg_stretch=
00933        ((double) (ht - pg->ht->def)) /
00934        ((double) (pg->ht->max - pg->ht->def));
00935     else if ((ht < pg->ht->def) && (pg->ht->def > pg->ht->min))
00936       pg_stretch=
00937        ((double) (ht - pg->ht->def)) /
00938        ((double) (pg->ht->def - pg->ht->min));
00939     // cout << " -> " << pg_stretch << LF;
00940     pen += format_pagelet (pg, pg_stretch);
00941     pen += pg->pen + as_vpenalty (pg->ht->def - ht);
00942   }
00943   // cout << UNINDENT << "Formatted multicolumn, penalty= " << pen << LF;
00944   return pen;
00945 }
00946 
00947 vpenalty
00948 page_breaker_rep::format_pagelet (pagelet& pg, double stretch) {
00949   // cout << "Stretch " << pg << ": " << stretch << LF;
00950   int i;
00951   vpenalty pen;
00952   pg->stretch= stretch;
00953   for (i=0; i<N(pg->ins); i++)
00954     pen += format_insertion (pg->ins[i], stretch);
00955   return pen;
00956 }
00957 
00958 vpenalty
00959 page_breaker_rep::format_pagelet (pagelet& pg, space ht, bool last_page) {
00960   // cout << "Formatting " << pg << ", " << ht << LF << INDENT;
00961   float stretch= 0.0;
00962   vpenalty pen;
00963 
00964   if (last_page && (pg->ht->def <= ht->def)) {
00965     // cout << "Eject last page" << LF;
00966     stretch= 0.0;
00967   }
00968   else if ((ht->def >= pg->ht->min) && (ht->def <= pg->ht->max)) {
00969     if (ht->def > pg->ht->def) {
00970       // cout << "Stretch" << LF;
00971       stretch=
00972        ((double) (ht->def - pg->ht->def)) /
00973        ((double) (pg->ht->max - pg->ht->def));
00974     }
00975     else if (ht->def < pg->ht->def) {
00976       // cout << "Shrink" << LF;
00977       stretch=
00978        ((double) (ht->def - pg->ht->def)) /
00979        ((double) (pg->ht->def - pg->ht->min));
00980     }
00981     pen= as_vpenalty (ht->def- pg->ht->def);
00982   }
00983   else if ((ht->def < pg->ht->min) && (ht->max >= pg->ht->min)) {
00984     // cout << "Extend page" << LF;
00985     stretch= -1.0;
00986     pen= vpenalty (EXTEND_PAGE_PENALTY) + as_vpenalty (ht->def- pg->ht->def);
00987   }
00988   else if ((ht->def > pg->ht->max) && (ht->min <= pg->ht->max)) {
00989     // cout << "Reduce page" << LF;
00990     stretch= 1.0;
00991     pen= vpenalty (REDUCE_PAGE_PENALTY) + as_vpenalty (ht->def- pg->ht->def);
00992   }
00993   else if (ht->max < pg->ht->min) {
00994     // cout << "Overfull page" << LF;
00995     stretch= -1.0;
00996     double factor= ((double) max (pg->ht->def, 1))/((double) max (ht->def, 1));
00997     if (factor < 1.0  ) factor= 1.0;
00998     if (factor > 100.0) factor= 100.0;
00999     pen= vpenalty ((int) (factor * TOO_LONG_PENALTY));
01000   }
01001   else {
01002     // cout << "Underfull page" << LF;
01003     stretch= 1.0;
01004     double factor= ((double) max (pg->ht->def, 1))/((double) max (ht->def, 1));
01005     if (factor < 0.0 ) factor= 0.0;
01006     if (factor > 0.99) factor= 0.99;
01007     pen= vpenalty ((int) ((1.0 - factor) * TOO_SHORT_PENALTY));
01008   }
01009   pen += format_pagelet (pg, stretch);
01010   // cout << UNINDENT << "Formatted [ stretch= " << stretch
01011   //      << ", penalty= " << (pg->pen + pen) << " ]" << LF << LF;
01012   return pg->pen + pen;
01013 }
01014 
01015 /******************************************************************************
01016 * Multi column breaking routines
01017 ******************************************************************************/
01018 
01019 void
01020 page_breaker_rep::search_mcol_breaks (
01021   vbreak br1, vbreak br2, array<array<int> > part,
01022   path p1, path p2, int& i1, int& i2)
01023 {
01024   // cout << "Search " << p1 << " -- " << p2 << " among parts " << part << LF;
01025   int id, i;
01026   br1= copy (br1);
01027   br2= copy (br2);
01028   for (id=0; id<nr_flows; id++) {
01029     /*
01030     for (i=0; i<N(part[id])-1; i++)
01031       cout << "  Flow " << id << ": "
01032           << flow[id][part[id][i]] << " -- "
01033           << path_inc (flow[id][part[id][i+1]-1]) << LF;
01034     */
01035     for (i=0; i<N(part[id])-1; i++)
01036       if (var_path_inf_eq (path_inc (flow[id][part[id][i+1]-1]), p1))
01037        br1[id]= part[id][i+1];
01038     for (i=N(part[id])-2; i>=0; i--)
01039       if (var_path_inf_eq (p2, flow[id][part[id][i]]))
01040        br2[id]= part[id][i];
01041   }
01042 
01043   // cout << "Search breaks " << br1 << " -- " << br2 << LF;
01044   ASSERT (brk_nr->contains (br1) && brk_nr->contains (br2),
01045          "break not found");
01046   i1= brk_nr[br1];
01047   i2= brk_nr[br2];
01048 }
01049 
01050 insertion
01051 page_breaker_rep::make_multi_column (skeleton sk, int real_nr_cols) {
01052   int i, nr_cols= N(sk);
01053   space    ht = copy (sk[0]->ht);
01054   vpenalty pen= sk[0]->pen;
01055   for (i=1; i<nr_cols; i++) {
01056     ht->min= max (ht->min, sk[i]->ht->min);
01057     ht->def += sk[i]->ht->def;
01058     ht->max= min (ht->max, sk[i]->ht->max);
01059     pen += sk[i]->pen;
01060   }
01061   ht->def /= nr_cols;
01062   if (ht->max < ht->min) {
01063     ht->def= ht->max= ht->min;
01064     pen += UNBALANCED_COLUMNS;
01065     for (i=1; i<nr_cols; i++)
01066       if (sk[i-1]->ht->min < sk[i]->ht->min)
01067        pen += LONGER_LATTER_COLUMN;
01068   }
01069   else {
01070     if (ht->def < ht->min) ht->def= ht->min;
01071     if (ht->def > ht->max) ht->def= ht->max;
01072   }
01073   insertion ins (tuple ("multi-column", as_string (real_nr_cols)), sk);
01074   ins->ht     = ht;
01075   ins->pen    = pen;
01076   ins->top_cor= 0;
01077   ins->bot_cor= 0;
01078   return ins;
01079 }
01080 
01081 insertion
01082 page_breaker_rep::make_multi_column (
01083   int start, int end, path flb, int nr_cols)
01084 {
01085   if ((quality>1) && (nr_cols == 2))
01086     return make_two_column (start, end, flb);
01087   // cout << "Make multicolumn "
01088   //      << start << " " << brk[start] << ", "
01089   //      << end   << " " << brk[end  ] << LF << LF << INDENT;
01090 
01091   skeleton sk;
01092   int col, col_start= start, col_end= start;
01093   int mcid= flow_id[flb * nr_cols];
01094   page_item item= access (l, flow[mcid][brk[end][mcid]-1]);
01095   SI col_ht= brk_tot[end]->def - brk_tot[start]->def;
01096   col_ht -= item->spc->def/(nr_cols-1);
01097   // already divided by nr_cols
01098   // cout << "Column height= " << col_ht << LF;
01099   for (col=0; col<nr_cols; col++) {
01100     col_end= col_start;
01101     // avoids bug: a bizar change in col_end occurs between end of loop and
01102     //             the start of the loop at the next iteration
01103     if (col_end >= end) break;
01104     SI tot= brk_tot[col_start]->def + (col_ht / nr_cols);
01105     int col_end= find_length (brk_tot, col_start, tot);
01106     col_end= max (col_start+1, col_end-2);
01107     if (col == nr_cols-1) col_end= end;
01108     while (col_end < end) {
01109       if (correct_pagelet (col_start, col_end) &&
01110          correct_pagelet (col_end, end))
01111        {
01112          pagelet pg= make_pagelet (col_start, col_end, flb, nr_cols);
01113          if ((pg->pen < vpenalty (HYPH_INVALID)) &&
01114              (pg->ht->def >= col_ht))
01115            {
01116              if (N(pg->ins) != 0) sk << pg;
01117              break;
01118            }
01119        }
01120       col_end++;
01121     }
01122     if (col_end == end) {
01123       pagelet pg= make_pagelet (col_start, col_end, flb, nr_cols);
01124       if (N(pg->ins) != 0) sk << pg;
01125     }
01126     col_start= col_end;
01127   }
01128 
01129   // cout << UNINDENT << "Multicolumn: " << sk << LF;
01130   return make_multi_column (sk, nr_cols);
01131 }
01132 
01133 int
01134 page_breaker_rep::tc_propose_break (path flb) {
01135   if (!correct_pagelet (tc_start, tc_middle)) return INVALID_BREAK;
01136   if (!correct_pagelet (tc_middle, tc_end)) return INVALID_BREAK;
01137   pagelet pg1= make_pagelet (tc_start, tc_middle, flb, 2);
01138   pagelet pg2= make_pagelet (tc_middle, tc_end, flb, 2);
01139   bool first_longer = (pg1->ht->min > pg2->ht->max);
01140   bool second_longer= (pg2->ht->min > pg1->ht->max);
01141 
01142   vpenalty pen= pg1->pen + pg2->pen + as_vpenalty (pg2->ht->def - pg1->ht->def);
01143   if (first_longer || second_longer) pen += UNBALANCED_COLUMNS;
01144   if (second_longer) pen += LONGER_LATTER_COLUMN;
01145   if (is_nil (tc_bpg1) || (pen < tc_bpen)) {
01146     tc_bmid= tc_middle;
01147     tc_bpen= pen;
01148     tc_bpg1= pg1;
01149     tc_bpg2= pg2;
01150   }
01151   if (first_longer && (tc_middle >= tc_ref)) return BAD_BREAK;
01152   if (second_longer && (tc_middle < tc_ref)) return BAD_BREAK;
01153   return VALID_BREAK;
01154 }
01155 
01156 insertion
01157 page_breaker_rep::make_two_column (int start, int end, path flb) {
01158   // cout << "Make two column "
01159   //      << start << " " << brk[start] << ", "
01160   //      << end   << " " << brk[end  ] << LF << LF << INDENT;
01161 
01162   skeleton sk;
01163   int mcid= flow_id[flb * 2];
01164   page_item item= access (l, flow[mcid][brk[end][mcid]-1]);
01165   SI col_ht= brk_tot[end]->def - brk_tot[start]->def - item->spc->def;
01166   // already divided by 2
01167   // cout << "Column height= " << col_ht << LF;
01168   SI tot= brk_tot[start]->def + (col_ht / 2);
01169   tc_ref= find_length (brk_tot, start, tot);
01170 
01171   tc_start= start;
01172   tc_end  = end;
01173   tc_bmid = end;
01174   tc_bpen = vpenalty (MAX_SI, MAX_SI);
01175   tc_bpg1 = pagelet ();
01176   tc_bpg2 = pagelet ();
01177 
01178   tc_ld   = ladder ();
01179   if ((tc_ref > tc_start) && (tc_ref < tc_end)) tc_ld << tc_ref;
01180   while (N(tc_ld) != 0) {
01181     // cout << "Two column ladder= " << tc_ld << LF;
01182     tc_middle= tc_ld[0];
01183     int status= tc_propose_break (flb);
01184     if ((status == BAD_BREAK) && (tc_bpen < vpenalty (HYPH_INVALID)))
01185       tc_ld= sub (tc_ld, 1, N(tc_ld));
01186     else {
01187       if (tc_middle+1 >= tc_end) tc_ld= ladder ();
01188       else tc_ld= inc_merge (brk_next[tc_middle+1], sub (tc_ld, 1, N(tc_ld)));
01189     }
01190   }
01191 
01192   tc_ld= ladder ();
01193   if (((tc_ref-1) > tc_start) && ((tc_ref-1) < tc_end)) tc_ld << (tc_ref-1);
01194   while (N(tc_ld) != 0) {
01195     // cout << "Two column ladder= " << tc_ld << LF;
01196     tc_middle= tc_ld[0];
01197     int status= tc_propose_break (flb);
01198     if ((status == BAD_BREAK) && (tc_bpen < vpenalty (HYPH_INVALID)))
01199       tc_ld= sub (tc_ld, 1, N(tc_ld));
01200     else {
01201       if (tc_middle-1 <= tc_start) tc_ld= ladder ();
01202       else tc_ld= dec_merge (brk_prev[tc_middle-1], sub (tc_ld, 1, N(tc_ld)));
01203     }
01204   }
01205 
01206   if (is_nil (tc_bpg1))
01207     sk << make_pagelet (tc_start, tc_end, flb, 2);
01208   else {
01209     sk << tc_bpg1;
01210     sk << tc_bpg2;
01211   }
01212 
01213   // cout << UNINDENT << "Two column: " << sk << LF;
01214   return make_multi_column (sk, 2);
01215 }
01216 
01217 /******************************************************************************
01218 * Fast page breaking routines
01219 ******************************************************************************/
01220 
01221 void
01222 page_breaker_rep::fast_break_page (int i1, int& first_end) {
01223   first_end= max (i1+1, first_end);
01224   bool ok= false;
01225   int i2= first_end, n= N(flow[0]);
01226   while (true) {
01227     space spc;
01228     if (i1 == 0) { if (i2 > 1) spc= copy (flow_tot[0][i2-2]); }
01229     else spc= flow_tot[0][i2-2] - flow_tot[0][i1-1];
01230     SI top_cor= flow_cor[0][i1]->max;
01231     SI bot_cor= flow_cor[0][i2-1]->min;
01232     spc += space (top_cor + flow_cor[0][i2-1]->def + bot_cor);
01233 
01234     int bpen= access (l, flow[0][i2-1])->penalty;
01235     if (i2 >= n) bpen= 0;
01236     if (bpen < HYPH_INVALID) {
01237       ok= true;
01238       if (spc->max < height->min) first_end= i2;
01239       vpenalty pen= best_pens[i1] + vpenalty (bpen);
01240       if ((i2 < n) || (!last_page_flag))
01241        pen += as_vpenalty (spc->def - height->def);
01242       if (((i2 < n) || (!last_page_flag)) && (spc->max < height->def)) {
01243        if (spc->max >= height->min) pen += EXTEND_PAGE_PENALTY;
01244        else {
01245          double factor=
01246            ((double) max (spc->def, 1))/((double) max (height->def, 1));
01247          if (factor < 0.0 ) factor= 0.0;
01248          if (factor > 0.99) factor= 0.99;
01249          pen= vpenalty ((int) ((1.0 - factor) * TOO_SHORT_PENALTY));
01250        }
01251       }
01252       else if (spc->min > height->def) {
01253        if (spc->min <= height->max) pen += REDUCE_PAGE_PENALTY;
01254        else {
01255          double factor=
01256            ((double) max (spc->def, 1))/((double) max (height->def, 1));
01257          if (factor < 1.0  ) factor= 1.0;
01258          if (factor > 100.0) factor= 100.0;
01259          pen= vpenalty ((int) (factor * TOO_LONG_PENALTY));
01260        }
01261       }
01262       if (pen < best_pens[i2]) {
01263        best_prev[i2]= i1;
01264        best_pens[i2]= pen;
01265       }
01266     }
01267     if ((i2 >= n) || (ok && (spc->min > height->max))) break;
01268     i2++;
01269   }
01270 }
01271 
01272 void
01273 page_breaker_rep::fast_assemble_skeleton (skeleton& sk, int end) {
01274   int start= best_prev[end], n= N(flow[0]);
01275   if (start < 0) return;
01276   fast_assemble_skeleton (sk, start);
01277   insertion ins= make_insertion (0, -1, start, end, end == n);
01278   pagelet pg (0);
01279   pg << ins;
01280   bool last_page= last_page_flag && (end == n);
01281   format_pagelet (pg, height, last_page);
01282   sk << pg;
01283 }
01284 
01285 void
01286 page_breaker_rep::fast_assemble_skeleton (skeleton& sk) {
01287   int i, n= N(flow[0]);
01288   best_prev= array<int> (n+1);
01289   best_pens= array<vpenalty> (n+1);
01290   for (i=0; i<=n; i++) {
01291     best_prev [i]= -1;
01292     best_pens [i]= HYPH_INVALID;
01293   }
01294   best_prev[0]= -2;
01295   best_pens[0]= vpenalty (0, 0);
01296   
01297   int first_end= 0;
01298   for (i=0; i<n; i++)
01299     if (best_prev[i] != -1)
01300       fast_break_page (i, first_end);
01301   fast_assemble_skeleton (sk, n);
01302 }
01303 
01304 /******************************************************************************
01305 * Page breaking routines
01306 ******************************************************************************/
01307 
01308 int
01309 page_breaker_rep::propose_break () {
01310   if (!correct_pagelet (cur_start, cur_end)) return INVALID_BREAK;
01311   pagelet pg= make_pagelet (cur_start, cur_end, path (), 1);
01312 
01313   /*
01314     bool newpage=
01315     (l[ins->end->item-1]->type == PAGE_CONTROL_ITEM) &&
01316     (l[ins->end->item-1]->t == NEW_PAGE);
01317   */
01318   bool last_page= last_page_flag && (cur_end == brk_last);
01319   vpenalty pen= format_pagelet (pg, height, last_page);
01320   if (is_nil (best_pg) || (pen < best_pen)) {
01321     best_end= cur_end;
01322     best_pen= pen;
01323     best_pg = pg;
01324   }
01325 
01326   if (quality>0) {
01327     vpenalty tot_pen= pen + best_pens[cur_start];
01328     if (is_nil (best_pgs[cur_end]) || (tot_pen < best_pens[cur_end])) {
01329       best_prev[cur_end]= cur_start;
01330       best_pens[cur_end]= tot_pen;
01331       best_pgs [cur_end]= pg;
01332     }
01333   }
01334 
01335   if (last_page && (pg->ht->def <= height->def)) return VALID_BREAK;
01336   if ((height->max < pg->ht->min) && (cur_end >= cur_ref)) return BAD_BREAK;
01337   if ((height->min > pg->ht->max) && (cur_end <  cur_ref)) return BAD_BREAK;
01338   return VALID_BREAK;
01339 }
01340 
01341 void
01342 page_breaker_rep::find_next_breaks () {
01343   SI tot  = brk_tot[cur_start]->def + height->def;
01344   cur_ref = find_length (brk_tot, cur_start, tot);
01345   best_end= brk_last;
01346   best_pen= vpenalty (MAX_SI, MAX_SI);
01347   best_pg = pagelet ();
01348 
01349   // int credit= 10;
01350   cur_ld= ladder ();
01351   cur_ld << cur_ref;
01352   while (N(cur_ld) != 0) {
01353     // if ((--credit) <= 0) break;
01354     // cout << "Current ladder= " << cur_ld << LF;
01355     cur_end= cur_ld[0];
01356     int status= propose_break ();
01357     if ((status == BAD_BREAK) && (best_pen < vpenalty (HYPH_INVALID)))
01358       cur_ld= sub (cur_ld, 1, N(cur_ld));
01359     else {
01360       if (cur_end+1 >= N(brk)) cur_ld= ladder ();
01361       else cur_ld= inc_merge (brk_next[cur_end+1], sub (cur_ld, 1, N(cur_ld)));
01362     }
01363   }
01364 
01365   // credit= 10;
01366   cur_ld= ladder ();
01367   if (cur_ref-1 > cur_start) cur_ld << (cur_ref-1);
01368   while (N(cur_ld) != 0) {
01369     // if ((--credit) <= 0) break;
01370     // cout << "Current ladder= " << cur_ld << LF;
01371     cur_end= cur_ld[0];
01372     int status= propose_break ();
01373     if ((status == BAD_BREAK) && (best_pen < vpenalty (HYPH_INVALID)))
01374       cur_ld= sub (cur_ld, 1, N(cur_ld));
01375     else {
01376       if (cur_end-1 <= cur_start) cur_ld= ladder ();
01377       else cur_ld= dec_merge (brk_prev[cur_end-1], sub (cur_ld, 1, N(cur_ld)));
01378     }
01379   }
01380 }
01381 
01382 void
01383 page_breaker_rep::assemble_skeleton (skeleton& sk, int last) {
01384   // cout << "Assemble until " << last << LF;
01385   if (last == brk_first) return;
01386   ASSERT (best_prev[last] != -1, "unfinished skeleton");
01387   assemble_skeleton (sk, best_prev[last]);
01388   sk << best_pgs[last];
01389 }
01390 
01391 void
01392 page_breaker_rep::assemble_skeleton (skeleton& sk) {
01393   int i, nrb= N(brk), nrinit= (quality>0? nrb: 0);
01394   best_prev= array<int>      (nrinit);
01395   best_pens= array<vpenalty> (nrinit);
01396   best_pgs = array<pagelet>  (nrinit);
01397   for (i=0; i<nrinit; i++) {
01398     best_prev[i]= -1;
01399     best_pens[i]= vpenalty (MAX_SI, MAX_SI);
01400     best_pgs [i]= pagelet ();
01401   }
01402   if (quality>0) {
01403     best_prev[brk_first]= -2;
01404     best_pens[brk_first]= vpenalty (0, 0);
01405   }
01406 
01407   cur_start= brk_first;
01408   if (quality>0) {
01409     while (cur_start != brk_last) {
01410       if (best_prev[cur_start] != -1)
01411        find_next_breaks ();
01412       // cout << HRULE << LF << LF;
01413       cur_start++;
01414     }
01415     assemble_skeleton (sk, brk_last);
01416   }
01417   else {
01418     while (cur_start != brk_last) {
01419       find_next_breaks ();
01420       // cout << HRULE << LF;
01421       // cout << "Eject " << best_pg << LF;
01422       // cout << HRULE << LF << LF;
01423       sk << best_pg;
01424       cur_start= best_end;
01425     }
01426   }
01427 }
01428 
01429 void
01430 page_breaker_rep::assemble_skeleton (skeleton& sk, int start, int end) {
01431   // cout << "Building skeleton " << start << " -- " << end << "\n";
01432   init_flows (start, end);
01433   // cout << "Flows done" << LF;
01434   // cout << "nr_flows = " << nr_flows << LF;
01435   // cout << "flow_id  = " << flow_id << LF;
01436   // cout << "flow_fl  = " << flow_fl << LF;
01437   // cout << "flow     = " << flow << LF;
01438   // cout << "flow_ht  = " << flow_ht << LF;
01439   // cout << "flow_cor = " << flow_cor << LF;
01440   // cout << "flow_tot = " << flow_tot << LF;
01441   // cout << "flow_cont= " << flow_cont << LF;
01442   // show_penalties ();
01443   if ((nr_flows == 1) && (flow_fl[0] == path (1))) {
01444     fast_assemble_skeleton (sk);
01445     // cout << "Skeleton done" << LF;
01446     // cout << "sk= " << sk << LF;
01447     return;
01448   }
01449   init_breaks ();
01450   // cout << "Breaks done" << LF;
01451   // cout << "brk      = " << brk << LF;
01452   // cout << "brk_tot  = " << brk_tot << LF;
01453   sort_breaks ();
01454   // cout << "Sorting done" << LF;
01455   // cout << "brk      = " << brk << LF;
01456   // cout << "brk_tot  = " << brk_tot << LF;
01457   init_ladders ();
01458   // cout << "Ladders done" << LF;
01459   // cout << "brk_prev = " << brk_prev << LF;
01460   // cout << "brk_next = " << brk_next << LF;
01461   // cout << "brk_first= " << brk_first << LF;
01462   // cout << "brk_last = " << brk_last << LF;
01463   assemble_skeleton (sk);
01464   // cout << "Skeleton done" << LF;
01465   // cout << "sk= " << sk << LF;
01466   // cout << HRULE << LF << LF;
01467 }
01468 
01469 skeleton
01470 page_breaker_rep::make_skeleton () {
01471   skeleton sk;
01472   int i, j, n= N(l);
01473   bool dpage_flag= false;
01474   for (i=0, j=0; j<n; j++) {
01475     if ((!papyrus_mode) && (l[j]->type == PAGE_CONTROL_ITEM))
01476       if ((l[j]->t == PAGE_BREAK) ||
01477          (l[j]->t == NEW_PAGE) || (l[j]->t == NEW_DPAGE))
01478        {
01479          if (dpage_flag && ((N(sk)&1) == 1))
01480            sk << pagelet (space (0));
01481          dpage_flag= (l[j]->t == NEW_DPAGE);
01482          last_page_flag= (l[j]->t != PAGE_BREAK);
01483          if (i<j) assemble_skeleton (sk, i, j);
01484          i=j+1;
01485        }
01486   }
01487   if (i<j) {
01488     if (dpage_flag && ((N(sk)&1) == 1))
01489       sk << pagelet (space (0));
01490     last_page_flag= true;
01491     assemble_skeleton (sk, i, j);
01492   }
01493   return sk;
01494 }
01495 
01496 /******************************************************************************
01497 * The exported page breaking routine
01498 ******************************************************************************/
01499 
01500 skeleton
01501 break_pages (array<page_item> l, space ph, int qual,
01502             space fn_sep, space fnote_sep, space float_sep, font fn)
01503 {
01504   page_breaker_rep* H=
01505     tm_new<page_breaker_rep> (l, ph, qual, fn_sep, fnote_sep, float_sep, fn);
01506   // cout << HRULE << LF;
01507   skeleton sk= H->make_skeleton ();
01508   tm_delete (H);
01509   return sk;
01510 }