Back to index

texmacs  1.0.7.15
stacker.cpp
Go to the documentation of this file.
00001 
00002 /******************************************************************************
00003 * MODULE     : stacker.cpp
00004 * DESCRIPTION: Vertical formatting of paragraphs
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 "Stack/stacker.hpp"
00013 #include "Boxes/construct.hpp"
00014 
00015 /******************************************************************************
00016 * Constructors and basic routines for stackers
00017 ******************************************************************************/
00018 
00019 stacker_rep::stacker_rep ():
00020   l (0), unit_flag (false), unit_start (0) {}
00021 
00022 void
00023 stacker_rep::set_env_vars (
00024   SI height2, SI sep2, SI hor_sep2, SI ver_sep2, SI bot2, SI top2)
00025 {
00026   sb->height_before = sb->height = height2;
00027   sb->sep_before    = sb->sep    = sep2;
00028   sb->hor_sep_before= sb->hor_sep= hor_sep2;
00029   sb->ver_sep_before= sb->ver_sep= ver_sep2;
00030   sb->bot           = bot2;
00031   sb->top           = top2;
00032 }
00033 
00034 /******************************************************************************
00035 * Compute the degree of inshoveability between two successive lines
00036 ******************************************************************************/
00037 
00038 #include "merge_sort.hpp"
00039 
00040 static int
00041 get_pos (array<SI> a, SI which) {
00042   int step, test;
00043   step= test= N(a)>>1;
00044   while (a[test] != which) {
00045     step= step >> 1;
00046     if (step==0) {
00047       if (which < a[test]) return test-1;
00048       else return test+1;
00049     }
00050     else {
00051       if (which < a[test]) test= max (0, test- step);
00052       else test= min (N(a)-1, test+ step);
00053     }
00054   }
00055   return test;
00056 }
00057 
00058 static SI
00059 shove_in (box b1, box b2, SI hor_sep, SI top, SI bot) {
00060   // quick test whether there are collisions
00061   int i, j;
00062   SI min1= PLUS_INFINITY, max1= MINUS_INFINITY;
00063   SI min2= PLUS_INFINITY, max2= MINUS_INFINITY;
00064   for (i=0; i<N(b1); i++)
00065     if (b1[i]->w() > 0) {
00066       if (b1->sx1(i) < min1) min1= b1->sx1(i);
00067       if (b1->sx2(i) > max1) max1= b1->sx2(i);
00068     }
00069   for (i=0; i<N(b2); i++)
00070     if (b2[i]->w() > 0) {
00071       if (b2->sx1(i) < min2) min2= b2->sx1(i);
00072       if (b2->sx2(i) > max2) max2= b2->sx2(i);
00073     }
00074   if ((max1 + hor_sep < min2) || (max2 + hor_sep < min1)) return 0;
00075 
00076   // longer determination of height after shoving
00077   array<SI> hpos;
00078   for (i=0; i<N(b1); i++)
00079     if (b1[i]->w() > 0)
00080       hpos << (b1->sx1(i)- hor_sep) << (b1->sx2(i)+ hor_sep);
00081   for (i=0; i<N(b2); i++) 
00082     if (b2[i]->w() > 0)
00083       hpos << (b2->sx1(i)- hor_sep) << (b2->sx2(i)+ hor_sep);
00084   merge_sort (hpos);  
00085 
00086   int n= N(hpos)-1;
00087   array<SI> vpos1 (n);
00088   array<SI> vpos2 (n);
00089   for (i=0; i<n; i++) {
00090     vpos1[i]= bot;
00091     vpos2[i]= top;
00092   }
00093 
00094   for (i=0; i<N(b1); i++) {
00095     SI  y    = b1->sy1(i);
00096     int start= get_pos (hpos, b1->sx1(i)- hor_sep);
00097     int end  = get_pos (hpos, b1->sx2(i)+ hor_sep);
00098     if (end>n) end= n;
00099     for (j=start; j<end; j++)
00100       vpos1[j]= min (vpos1[j], y);
00101   }
00102   for (i=0; i<N(b2); i++) {
00103     SI  y    = b2->sy2(i);
00104     int start= get_pos (hpos, b2->sx1(i)- hor_sep);
00105     int end  = get_pos (hpos, b2->sx2(i)+ hor_sep);
00106     if (end>n) end= n;
00107     for (j=start; j<end; j++)
00108       vpos2[j]= max (vpos2[j], y);
00109   }
00110 
00111   SI m= vpos2[0]-vpos1[0];
00112   for (i=1; i<n; i++)
00113     m= max (m, vpos2[i]-vpos1[i]);
00114   return m;
00115 }
00116 
00117 // FIXME: from TeXmacs-1.0.4.1 on, the separation parameters between
00118 // successive lines are the maximum of the parameters for each line.
00119 // This may be further refined by allowing a "par-sep before and after",
00120 // and similarly for par-hor-sep, par-ver-sep, etc. Ideally speaking,
00121 // the parameters would be determined for individual boxes on each line
00122 // and the maxima of the individual values are taken on each line.
00123 
00124 static void
00125 shove (page_item& item1, page_item& item2, stack_border sb, stack_border sb2) {
00126   SI  height = max (sb->height , sb2->height_before );
00127   SI  sep    = max (sb->sep    , sb2->sep_before    );
00128   SI  hor_sep= max (sb->hor_sep, sb2->hor_sep_before);
00129   SI  ver_sep= max (sb->ver_sep, sb2->ver_sep_before);
00130   SI  bot    = sb->bot;
00131   SI  top    = sb2->top;
00132 
00133   box b1= item1->b, b2= item2->b;
00134   // cout << "Shove: " << sb->height << ", " << sb2->height_before
00135   // << "; " << b1->y1 << ", " << b2->y2
00136   // << "; " << top << ", " << bot << LF;
00137 
00138   while (true) {
00139     int type= b1->get_type ();
00140     if ((type == MOVE_BOX) && (b1->sx(0) == 0)) b1= b1[0];
00141     else if ((type == STACK_BOX) && (N(b1)>0)) {
00142       int i= N(b1)-1;
00143       while ((i >= 1) && (b1[i]->h() == 0)) i--;
00144       b1= b1[i];
00145     }
00146     else break;
00147   }
00148   while (true) {
00149     int type= b2->get_type ();
00150     if ((type == MOVE_BOX) && (b2->sx(0) == 0)) b2= b2[0];
00151     else if ((type == STACK_BOX) && (N(b2)>0)) {
00152       int i= 0, n= N(b2);
00153       while ((i < n-1) && (b2[i]->h() == 0)) i++;
00154       b2= b2[i];
00155     }
00156     else break;
00157   }
00158 
00159   if ((b2->y2- b1->y1) < (height- max (sep, ver_sep))) {
00160     // enough place
00161     // cout << "  Normal" << LF;
00162     item1->spc= item1->spc + space (height- (b2->y2- b1->y1));
00163   }
00164   else {
00165     SI sh= shove_in (b1, b2, hor_sep, top, bot);
00166     //cout << "  Shove: " << sh << LF;
00167     //cout << "    b1= " << b1 << "\n";
00168     //cout << "    b2= " << b2 << "\n";
00169     if (sh == 0 ||
00170        b1->get_type() == SCROLL_BOX ||
00171        b2->get_type() == SCROLL_BOX)
00172     {
00173       SI h= max (height, max (b2->y2, b2->y2 - b1->y1 - (top - bot)));
00174       item1->spc= item1->spc + space (h- (b2->y2- b1->y1));
00175     }
00176     else {
00177       // collisions
00178       SI h= max (height, sh + ver_sep);
00179       item1->spc= item1->spc + space (h- (b2->y2- b1->y1));
00180     }
00181   }
00182 }
00183 
00184 /******************************************************************************
00185 * Printing to a stacker
00186 ******************************************************************************/
00187 
00188 void
00189 stacker_rep::print (box b, array<lazy> fl, int nr_cols) {
00190   int i= N(l)-1;
00191   while ((i>=0) && (l[i]->type == PAGE_CONTROL_ITEM)) i--;
00192   l << page_item (b, fl, nr_cols);
00193   if ((!unit_flag) && (i>=0)) {
00194     l[i]= copy (l[i]);
00195     shove (l[i], l[N(l)-1], sb, sb);
00196   }
00197   unit_flag= false;
00198 }
00199 
00200 void
00201 stacker_rep::print (tree t, int nr_cols, bool before) {
00202   if (before) l << page_item (t, nr_cols);
00203   else unit_ctrl << page_item (t, nr_cols);
00204 }
00205 
00206 void
00207 stacker_rep::print (space spc) {
00208   int i= N(l)-1;
00209   while ((i>=0) && (l[i]->type == PAGE_CONTROL_ITEM)) i--;
00210   if (i<0) return;
00211   l[i]->spc = l[i]->spc + spc;
00212 }
00213 
00214 /******************************************************************************
00215 * Merging stacks
00216 ******************************************************************************/
00217 
00218 void
00219 merge_stack (array<page_item>& l, stack_border& sb,
00220             array<page_item> l2, stack_border sb2)
00221 {
00222   int i= N(l)-1, j=0;
00223   while ((i >= 0) && (l[i]->type != PAGE_LINE_ITEM)) i--;
00224   while ((j < N(l2)) && (l2[j]->type != PAGE_LINE_ITEM)) j++;
00225 
00226   if (j >= N(l2)) {
00227     // no real lines in l2
00228     sb->vspc_after = max (sb->vspc_after, sb2->vspc_after);
00229     sb->nobr_after = sb->nobr_after || sb2->nobr_after;
00230   }
00231   else {
00232     if (i < 0) {
00233       // no real lines in l1
00234       sb->height_before  = sb2->height_before;
00235       sb->sep_before     = sb2->sep_before;
00236       sb->ver_sep_before = sb2->ver_sep_before;
00237       sb->hor_sep_before = sb2->hor_sep_before;
00238       sb->top            = sb2->top;
00239       sb->vspc_before    = max (sb->vspc_before, sb2->vspc_before);
00240       sb->nobr_before    = sb->nobr_before || sb2->nobr_before;
00241       //sb->vspc_before    = sb2->vspc_before;
00242       //sb->nobr_before    = sb2->nobr_before;
00243     }
00244     else {
00245       // normal case
00246       l[i]= copy (l[i]);
00247       shove (l[i], l2[j], sb, sb2);
00248       l[i]->spc= l[i]->spc + max (sb->vspc_after, sb2->vspc_before);
00249       if (sb->nobr_after || sb2->nobr_before) l[i]->penalty= HYPH_INVALID;
00250     }
00251     sb->height    = sb2->height;
00252     sb->sep       = sb2->sep;
00253     sb->ver_sep   = sb2->ver_sep;
00254     sb->hor_sep   = sb2->hor_sep;
00255     sb->bot       = sb2->bot;
00256     sb->vspc_after= sb2->vspc_after;
00257     sb->nobr_after= sb2->nobr_after;
00258   }
00259 
00260   l << l2;
00261 }
00262 
00263 /******************************************************************************
00264 * Other routines
00265 ******************************************************************************/
00266 
00267 void
00268 stacker_rep::new_paragraph (space par_sep) {
00269   if (unit_start == 0) {
00270     sb->vspc_before= unit_sb->vspc_before + par_sep;
00271     sb->vspc_after = unit_sb->vspc_after + par_sep;
00272     sb->nobr_before= unit_sb->nobr_before;
00273     sb->nobr_after = unit_sb->nobr_after;
00274   }
00275   else {
00276     int i= unit_start-1;
00277     while ((i>=0) && (l[i]->type == PAGE_CONTROL_ITEM)) i--;
00278     if (i<0) return;
00279     l[i]->spc= l[i]->spc + unit_sb->vspc_before;
00280     sb->vspc_after= unit_sb->vspc_after;
00281     if (unit_sb->nobr_before) l[i]->penalty= HYPH_INVALID;
00282     sb->nobr_after= unit_sb->nobr_after;
00283   }
00284 
00285   int i1= unit_start, i2= N(l)-1, mul= 100;
00286   while ((i1<=i2) && (mul>1)) {
00287     while ((i1<i2) && (l[i1]->type == PAGE_CONTROL_ITEM)) i1++;
00288     while ((i1<i2) && (l[i2]->type == PAGE_CONTROL_ITEM)) i2--;
00289     if (l[i1]->type != PAGE_CONTROL_ITEM)
00290       if (l[i1]->penalty < HYPH_INVALID)
00291        l[i1]->penalty *= mul;
00292     if (l[i2]->type != PAGE_CONTROL_ITEM)
00293       if (l[i2]->penalty < HYPH_INVALID)
00294        if (i1<i2) l[i2]->penalty *= mul;
00295     mul /= 10; i1++; i2--;
00296   }
00297 
00298   unit_sb->vspc_before= unit_sb->vspc_after;
00299   unit_sb->vspc_after = space (0);
00300   unit_sb->nobr_before= unit_sb->nobr_after;
00301   unit_sb->nobr_after = false;
00302   unit_start          = N(l);
00303 }
00304 
00305 void
00306 stacker_rep::vspace_before (space spc) {
00307   unit_sb->vspc_before= max (unit_sb->vspc_before, spc);
00308 }
00309 
00310 void
00311 stacker_rep::vspace_after (space spc) {
00312   unit_sb->vspc_after= max (unit_sb->vspc_after, spc);
00313 }
00314 
00315 void
00316 stacker_rep::no_page_break_before () {
00317   unit_sb->nobr_before= true;
00318 }
00319 
00320 void
00321 stacker_rep::no_page_break_after () {
00322   unit_sb->nobr_after= true;
00323 }
00324 
00325 void
00326 stacker_rep::penalty (int pen) {
00327   int i= N(l)-1;
00328   while ((i>=0) && (l[i]->type == PAGE_CONTROL_ITEM)) i--;
00329   if (i<0) return;
00330   l[i]->penalty = pen;  
00331 }
00332 
00333 void
00334 stacker_rep::flush () {
00335   l << unit_ctrl;
00336   unit_ctrl= array<page_item> (0);
00337 }
00338 
00339 /******************************************************************************
00340 * User interface
00341 ******************************************************************************/
00342 
00343 box
00344 typeset_as_stack (edit_env env, tree t, path ip) {
00345   // cout << "Typeset as stack " << t << "\n";
00346   int i, n= N(t);
00347   stacker sss= tm_new<stacker_rep> ();
00348   SI sep       = env->get_length (PAR_SEP);
00349   SI hor_sep   = env->get_length (PAR_HOR_SEP);
00350   SI ver_sep   = env->get_length (PAR_VER_SEP);
00351   SI height    = env->as_length (string ("1fn"))+ sep;
00352   SI bot       = 0;
00353   SI top       = env->fn->yx;
00354   sss->set_env_vars (height, sep, hor_sep, ver_sep, bot, top);
00355   for (i=0; i<n; i++)
00356     sss->print (typeset_as_concat (env, t[i], descend (ip, i)));
00357 
00358   n= N(sss->l);
00359   array<box> lines_bx (n);
00360   array<SI>  lines_ht (n);
00361   for (i=0; i<n; i++) {
00362     page_item item= copy (sss->l[i]);
00363     lines_bx[i]= item->b;
00364     lines_ht[i]= item->spc->def;
00365   }
00366 
00367   tm_delete (sss);
00368   box b= stack_box (ip, lines_bx, lines_ht);
00369   SI dy= n==0? 0: b[0]->y2;
00370   return move_box (ip, stack_box (ip, lines_bx, lines_ht), 0, dy);
00371 }