src/livarot/float-line.cpp

   1 /**
   2  *  \file livarot/float-line.cpp
   3  *
   4  * Implementation of coverage with floating-point values.
   5  *
   6  *  \author Fred
   7  *
   8  *  public domain
   9  *
  10  */
  11
  12 #ifdef faster_flatten
  13 # include <cmath>  // std::abs(float)
  14 #endif
  15 #include "livarot/float-line.h"
  16 #include "livarot/int-line.h"
  17
  18 FloatLigne::FloatLigne()
  19 {
  20     s_first = s_last = -1;
  21 }
  22
  23
  24 FloatLigne::~FloatLigne()
  25 {
  26
  27 }
  28
  29 /// Reset the line to  empty (boundaries and runs).
  30 void FloatLigne::Reset()
  31 {
  32     bords.clear();
  33     runs.clear();
  34     s_first = s_last = -1;
  35 }
  36
  37 /**
  38  * Add a coverage portion.
  39  *
  40  * \param guess Position from where we should try to insert the first
  41  * boundary, or -1 if we don't have a clue.
  42  */
  43 int FloatLigne::AddBord(float spos, float sval, float epos, float eval, int guess)
  44 {
  45 //  if ( showCopy ) printf("b= %f %f -> %f %f \n",spos,sval,epos,eval);
  46     if ( spos >= epos ) {
  47         return -1;
  48     }
  49
  50     float pente = (eval - sval) / (epos - spos);
  51
  52 #ifdef faster_flatten
  53     if ( std::abs(epos - spos) < 0.001 || std::abs(pente) > 1000 ) {
  54         return -1;
  55         epos = spos;
  56         pente = 0;
  57     }
  58 #endif
  59
  60     if ( guess >= int(bords.size()) ) {
  61         guess = -1;
  62     }
  63
  64     // add the left boundary
  65     float_ligne_bord b;
  66     int n = bords.size();
  67     b.pos = spos;
  68     b.val = sval;
  69     b.start = true;
  70     b.other = n + 1;
  71     b.pente = pente;
  72     b.s_prev = b.s_next = -1;
  73     bords.push_back(b);
  74
  75     // insert it in the doubly-linked list
  76     InsertBord(n, spos, guess);
  77
  78     // add the right boundary
  79     n = bords.size();
  80     b.pos = epos;
  81     b.val = eval;
  82     b.start = false;
  83     b.other = n-1;
  84     b.pente = pente;
  85     b.s_prev = b.s_next = -1;
  86     bords.push_back(b);
  87
  88     // insert it in the doubly-linked list, knowing that boundary at index n-1 is not too far before me
  89     InsertBord(n, epos, n - 1);
  90
  91     return n;
  92 }
  93
  94 /**
  95  * Add a coverage portion.
  96  *
  97  * \param guess Position from where we should try to insert the first
  98  * boundary, or -1 if we don't have a clue.
  99  */
 100 int FloatLigne::AddBord(float spos, float sval, float epos, float eval, float pente, int guess)
 101 {
 102 //  if ( showCopy ) printf("b= %f %f -> %f %f \n",spos,sval,epos,eval);
 103     if ( spos >= epos ) {
 104         return -1;
 105     }
 106
 107 #ifdef faster_flatten
 108     if ( std::abs(epos - spos) < 0.001 || std::abs(pente) > 1000 ) {
 109         return -1;
 110         epos = spos;
 111         pente = 0;
 112     }
 113 #endif
 114
 115     if ( guess >= int(bords.size()) ) {
 116         guess=-1;
 117     }
 118
 119     float_ligne_bord b;
 120     int n = bords.size();
 121     b.pos = spos;
 122     b.val = sval;
 123     b.start = true;
 124     b.other = n + 1;
 125     b.pente = pente;
 126     b.s_prev = b.s_next = -1;
 127     bords.push_back(b);
 128
 129     n = bords.size();
 130     b.pos = epos;
 131     b.val = eval;
 132     b.start = false;
 133     b.other = n - 1;
 134     b.pente = pente;
 135     b.s_prev = b.s_next = -1;
 136     bords.push_back(b);
 137
 138     InsertBord(n - 1, spos, guess);
 139     InsertBord(n, epos, n - 1);
 140 /*      if ( bords[n-1].s_next < 0 ) {
 141                 bords[n].s_next=-1;
 142                 s_last=n;
 143
 144                 bords[n].s_prev=n-1;
 145                 bords[n-1].s_next=n;
 146         } else if ( bords[bords[n-1].s_next].pos >= epos ) {
 147                 bords[n].s_next=bords[n-1].s_next;
 148                 bords[bords[n].s_next].s_prev=n;
 149
 150                 bords[n].s_prev=n-1;
 151                 bords[n-1].s_next=n;
 152         } else {
 153                 int c=bords[bords[n-1].s_next].s_next;
 154                 while ( c >= 0 && bords[c].pos < epos ) c=bords[c].s_next;
 155                 if ( c < 0 ) {
 156                         bords[n].s_prev=s_last;
 157                         bords[s_last].s_next=n;
 158                         s_last=n;
 159                 } else {
 160                         bords[n].s_prev=bords[c].s_prev;
 161                         bords[bords[n].s_prev].s_next=n;
 162
 163                         bords[n].s_next=c;
 164                         bords[c].s_prev=n;
 165                 }
 166
 167         }*/
 168     return n;
 169 }
 170
 171 /**
 172  * Add a coverage portion.
 173  *
 174  * \param guess Position from where we should try to insert the last
 175  * boundary, or -1 if we don't have a clue.
 176  */
 177 int FloatLigne::AddBordR(float spos, float sval, float epos, float eval, float pente, int guess)
 178 {
 179 //  if ( showCopy ) printf("br= %f %f -> %f %f \n",spos,sval,epos,eval);
 180 //      return AddBord(spos,sval,epos,eval,pente,guess);
 181     if ( spos >= epos ){
 182         return -1;
 183     }
 184
 185 #ifdef faster_flatten
 186     if ( std::abs(epos - spos) < 0.001 || std::abs(pente) > 1000 ) {
 187         return -1;
 188         epos = spos;
 189         pente = 0;
 190     }
 191 #endif
 192
 193     if ( guess >= int(bords.size()) ) {
 194         guess=-1;
 195     }
 196
 197     float_ligne_bord b;
 198     int n = bords.size();
 199     b.pos = spos;
 200     b.val = sval;
 201     b.start = true;
 202     b.other = n + 1;
 203     b.pente = pente;
 204     b.s_prev = b.s_next = -1;
 205     bords.push_back(b);
 206
 207     n = bords.size();
 208     b.pos = epos;
 209     b.val = eval;
 210     b.start = false;
 211     b.other = n - 1;
 212     b.pente = pente;
 213     b.s_prev = b.s_next = -1;
 214     bords.push_back(b);
 215
 216     InsertBord(n, epos, guess);
 217     InsertBord(n - 1, spos, n);
 218
 219 /*      if ( bords[n].s_prev < 0 ) {
 220                 bords[n-1].s_prev=-1;
 221                 s_first=n-1;
 222
 223                 bords[n-1].s_next=n;
 224                 bords[n].s_prev=n-1;
 225         } else if ( bords[bords[n].s_prev].pos <= spos ) {
 226                 bords[n-1].s_prev=bords[n].s_prev;
 227                 bords[bords[n-1].s_prev].s_next=n-1;
 228
 229                 bords[n-1].s_next=n;
 230                 bords[n].s_prev=n-1;
 231         } else {
 232                 int c=bords[bords[n].s_prev].s_prev;
 233                 while ( c >= 0 && bords[c].pos > spos ) c=bords[c].s_prev;
 234                 if ( c < 0 ) {
 235                         bords[n-1].s_next=s_first;
 236                         bords[s_first].s_prev=n-1;
 237                         s_first=n-1;
 238                 } else {
 239                         bords[n-1].s_next=bords[c].s_next;
 240                         bords[bords[n-1].s_next].s_prev=n-1;
 241
 242                         bords[n-1].s_prev=c;
 243                         bords[c].s_next=n-1;
 244                 }
 245
 246                 }*/
 247     return n - 1;
 248 }
 249
 250 /**
 251  * Add a coverage portion by appending boundaries at the end of the list.
 252  *
 253  * This works because we know they are on the right.
 254  */
 255 int FloatLigne::AppendBord(float spos, float sval, float epos, float eval, float pente)
 256 {
 257 //  if ( showCopy ) printf("b= %f %f -> %f %f \n",spos,sval,epos,eval);
 258 //      return AddBord(spos,sval,epos,eval,pente,s_last);
 259     if ( spos >= epos ) {
 260         return -1;
 261     }
 262
 263 #ifdef faster_flatten
 264     if ( std::abs(epos - spos) < 0.001 || std::abs(pente) > 1000 ) {
 265         return -1;
 266         epos = spos;
 267         pente = 0;
 268     }
 269 #endif
 270
 271     int n = bords.size();
 272     float_ligne_bord b;
 273     b.pos = spos;
 274     b.val = sval;
 275     b.start = true;
 276     b.other = n + 1;
 277     b.pente = pente;
 278     b.s_prev = s_last;
 279     b.s_next = n + 1;
 280     bords.push_back(b);
 281
 282     if ( s_last >=  0 ) {
 283         bords[s_last].s_next = n;
 284     }
 285
 286     if ( s_first < 0 ) {
 287         s_first = n;
 288     }
 289
 290     n = bords.size();
 291     b.pos = epos;
 292     b.val = eval;
 293     b.start = false;
 294     b.other = n - 1;
 295     b.pente = pente;
 296     b.s_prev = n - 1;
 297     b.s_next = -1;
 298     bords.push_back(b);
 299
 300     s_last = n;
 301
 302     return n;
 303 }
 304
 305
 306
 307 // insertion in a boubly-linked list. nothing interesting here
 308 void FloatLigne::InsertBord(int no, float p, int guess)
 309 {
 310     if ( no < 0 || no >= int(bords.size()) ) {
 311         return;
 312     }
 313
 314     if ( s_first < 0 ) {
 315         s_first = s_last = no;
 316         bords[no].s_prev = -1;
 317         bords[no].s_next = -1;
 318         return;
 319     }
 320
 321     if ( guess < 0 || guess >= int(bords.size()) ) {
 322         int c = s_first;
 323         while ( c >= 0 && c < int(bords.size()) && CmpBord(bords[c], bords[no]) < 0 ) {
 324             c = bords[c].s_next;
 325         }
 326
 327         if ( c < 0 || c >= int(bords.size()) ) {
 328             bords[no].s_prev = s_last;
 329             bords[s_last].s_next = no;
 330             s_last = no;
 331         } else {
 332             bords[no].s_prev = bords[c].s_prev;
 333             if ( bords[no].s_prev >= 0 ) {
 334                 bords[bords[no].s_prev].s_next = no;
 335             } else {
 336                 s_first = no;
 337             }
 338             bords[no].s_next = c;
 339             bords[c].s_prev = no;
 340         }
 341     } else {
 342         int c = guess;
 343         int stTst = CmpBord(bords[c], bords[no]);
 344
 345         if ( stTst == 0 ) {
 346
 347             bords[no].s_prev = bords[c].s_prev;
 348             if ( bords[no].s_prev >= 0 ) {
 349                 bords[bords[no].s_prev].s_next = no;
 350             } else {
 351                 s_first = no;
 352             }
 353             bords[no].s_next = c;
 354             bords[c].s_prev = no;
 355
 356         } else if ( stTst > 0 ) {
 357
 358             while ( c >= 0 && c < int(bords.size()) && CmpBord(bords[c], bords[no]) > 0 ) {
 359                 c = bords[c].s_prev;
 360             }
 361
 362             if ( c < 0 || c >= int(bords.size()) ) {
 363                 bords[no].s_next = s_first;
 364                 bords[s_first].s_prev =no; // s_first != -1
 365                 s_first = no;
 366             } else {
 367                 bords[no].s_next = bords[c].s_next;
 368                 if ( bords[no].s_next >= 0 ) {
 369                     bords[bords[no].s_next].s_prev = no;
 370                 } else {
 371                     s_last = no;
 372                 }
 373                 bords[no].s_prev = c;
 374                 bords[c].s_next = no;
 375             }
 376
 377         } else {
 378
 379             while ( c >= 0 && c < int(bords.size()) && CmpBord(bords[c],bords[no]) < 0 ) {
 380                 c = bords[c].s_next;
 381             }
 382
 383             if ( c < 0 || c >= int(bords.size()) ) {
 384                 bords[no].s_prev = s_last;
 385                 bords[s_last].s_next = no;
 386                 s_last = no;
 387             } else {
 388                 bords[no].s_prev = bords[c].s_prev;
 389                 if ( bords[no].s_prev >= 0 ) {
 390                     bords[bords[no].s_prev].s_next = no;
 391                 } else {
 392                     s_first = no;
 393                 }
 394                 bords[no].s_next = c;
 395                 bords[c].s_prev = no;
 396             }
 397         }
 398     }
 399 }
 400
 401 /**
 402  * Computes the sum of the coverages of the runs currently being scanned,
 403  * of which there are "pending".
 404  */
 405 float FloatLigne::RemainingValAt(float at, int pending)
 406 {
 407     float sum = 0;
 408 /*      int     no=firstAc;
 409         while ( no >= 0 && no < bords.size() ) {
 410                 int   nn=bords[no].other;
 411                 sum+=bords[nn].val+(at-bords[nn].pos)*bords[nn].pente;
 412 //                              sum+=((at-bords[nn].pos)*bords[no].val+(bords[no].pos-at)*bords[nn].val)/(bords[no].pos-bords[nn].pos);
 413 //              sum+=ValAt(at,bords[nn].pos,bords[no].pos,bords[nn].val,bords[no].val);
 414                 no=bords[no].next;
 415         }*/
 416   // for each portion being scanned, compute coverage at position "at" and sum.
 417   // we could simply compute the sum of portion coverages as a "f(x)=ux+y" and evaluate it at "x=at",
 418   // but there are numerical problems with this approach, and it produces ugly lines of incorrectly
 419   // computed alpha values, so i reverted to this "safe but slow" version
 420
 421     for (int i=0; i < pending; i++) {
 422         int const nn = bords[i].pend_ind;
 423         sum += bords[nn].val + (at - bords[nn].pos) * bords[nn].pente;
 424     }
 425
 426     return sum;
 427 }
 428
 429
 430 /**
 431  * Extract a set of non-overlapping runs from the boundaries.
 432  *
 433  * We scan the boundaries left to right, maintaining a set of coverage
 434  * portions currently being scanned. For each such portion, the function
 435  * will add the index of its first boundary in an array; but instead of
 436  * allocating another array, it uses a field in float_ligne_bord: pend_ind.
 437  * The outcome is that an array of float_ligne_run is produced.
 438  */
 439 void FloatLigne::Flatten()
 440 {
 441     if ( int(bords.size()) <= 1 ) {
 442         Reset();
 443         return;
 444     }
 445
 446     runs.clear();
 447
 448 //      qsort(bords,bords.size(),sizeof(float_ligne_bord),FloatLigne::CmpBord);
 449 //      SortBords(0,bords.size()-1);
 450
 451     float totPente = 0;
 452     float totStart = 0;
 453     float totX = bords[0].pos;
 454
 455     bool startExists = false;
 456     float lastStart = 0;
 457     float lastVal = 0;
 458     int pending = 0;
 459
 460 //      for (int i=0;i<bords.size();) {
 461     // read the list from left to right, adding a run for each boundary crossed, minus runs with alpha=0
 462     for (int i=/*0*/s_first; i>=0 && i < int(bords.size()) ;) {
 463
 464         float cur = bords[i].pos;  // position of the current boundary (there may be several boundaries at this position)
 465         float leftV = 0;  // deltas in coverage value at this position
 466         float rightV = 0;
 467         float leftP = 0; // deltas in coverage increase per unit length at this position
 468         float rightP = 0;
 469
 470         // more precisely, leftV is the sum of decreases of coverage value,
 471         // while rightV is the sum of increases, so that leftV+rightV is the delta.
 472         // idem for leftP and rightP
 473
 474         // start by scanning all boundaries that end a portion at this position
 475         while ( i >= 0 && i < int(bords.size()) && bords[i].pos == cur && bords[i].start == false ) {
 476             leftV += bords[i].val;
 477             leftP += bords[i].pente;
 478
 479 #ifndef faster_flatten
 480             // we need to remove the boundary that started this coverage portion for the pending list
 481             if ( bords[i].other >= 0 && bords[i].other < int(bords.size()) ) {
 482                 // so we use the pend_inv "array"
 483                 int const k = bords[bords[i].other].pend_inv;
 484                 if ( k >= 0 && k < pending ) {
 485                     // and update the pend_ind array and its inverse pend_inv
 486                     bords[k].pend_ind = bords[pending - 1].pend_ind;
 487                     bords[bords[k].pend_ind].pend_inv = k;
 488                 }
 489             }
 490 #endif
 491
 492             // one less portion pending
 493             pending--;
 494             // and we move to the next boundary in the doubly linked list
 495             i=bords[i].s_next;
 496             //i++;
 497         }
 498
 499         // then scan all boundaries that start a portion at this position
 500         while ( i >= 0 && i < int(bords.size()) && bords[i].pos == cur && bords[i].start == true ) {
 501             rightV += bords[i].val;
 502             rightP += bords[i].pente;
 503 #ifndef faster_flatten
 504             bords[pending].pend_ind=i;
 505             bords[i].pend_inv=pending;
 506 #endif
 507             pending++;
 508             i = bords[i].s_next;
 509             //i++;
 510         }
 511
 512         // coverage value at end of the run will be "start coverage"+"delta per unit length"*"length"
 513         totStart = totStart + totPente * (cur - totX);
 514
 515         if ( startExists ) {
 516             // add that run
 517             AddRun(lastStart, cur, lastVal, totStart, totPente);
 518         }
 519         // update "delta coverage per unit length"
 520         totPente += rightP - leftP;
 521         // not really needed here
 522         totStart += rightV - leftV;
 523         // update position
 524         totX = cur;
 525         if ( pending > 0 ) {
 526             startExists = true;
 527
 528 #ifndef faster_flatten
 529             // to avoid accumulation of numerical errors, we compute an accurate coverage for this position "cur"
 530             totStart = RemainingValAt(cur, pending);
 531 #endif
 532             lastVal = totStart;
 533             lastStart = cur;
 534         } else {
 535             startExists = false;
 536             totStart = 0;
 537             totPente = 0;
 538         }
 539     }
 540 }
 541
 542
 543 /// Debug dump of the instance.
 544 void FloatLigne::Affiche()
 545 {
 546     printf("%lu : \n", (long unsigned int) bords.size());
 547     for (int i = 0; i < int(bords.size()); i++) {
 548         printf("(%f %f %f %i) ",bords[i].pos,bords[i].val,bords[i].pente,(bords[i].start?1:0)); // localization ok
 549     }
 550
 551     printf("\n");
 552     printf("%lu : \n", (long unsigned int) runs.size());
 553
 554     for (int i = 0; i < int(runs.size()); i++) {
 555         printf("(%f %f -> %f %f / %f)",
 556                runs[i].st, runs[i].vst, runs[i].en, runs[i].ven, runs[i].pente); // localization ok
 557     }
 558
 559     printf("\n");
 560 }
 561
 562
 563 int FloatLigne::AddRun(float st, float en, float vst, float ven)
 564 {
 565     return AddRun(st, en, vst, ven, (ven - vst) / (en - st));
 566 }
 567
 568
 569 int FloatLigne::AddRun(float st, float en, float vst, float ven, float pente)
 570 {
 571     if ( st >= en ) {
 572         return -1;
 573     }
 574
 575     int const n = runs.size();
 576     float_ligne_run r;
 577     r.st = st;
 578     r.en = en;
 579     r.vst = vst;
 580     r.ven = ven;
 581     r.pente = pente;
 582     runs.push_back(r);
 583
 584     return n;
 585 }
 586
 587 void FloatLigne::Copy(FloatLigne *a)
 588 {
 589     if ( a->runs.empty() ) {
 590         Reset();
 591         return;
 592     }
 593
 594     bords.clear();
 595     runs = a->runs;
 596 }
 597
 598 void FloatLigne::Copy(IntLigne *a)
 599 {
 600     if ( a->nbRun ) {
 601         Reset();
 602         return;
 603     }
 604
 605     bords.clear();
 606     runs.resize(a->nbRun);
 607
 608     for (int i = 0; i < int(runs.size()); i++) {
 609         runs[i].st = a->runs[i].st;
 610         runs[i].en = a->runs[i].en;
 611         runs[i].vst = a->runs[i].vst;
 612         runs[i].ven = a->runs[i].ven;
 613     }
 614 }
 615
 616 /// Cuts the parts having less than tresh coverage.
 617 void FloatLigne::Min(FloatLigne *a, float tresh, bool addIt)
 618 {
 619     Reset();
 620     if ( a->runs.empty() ) {
 621         return;
 622     }
 623
 624     bool startExists = false;
 625     float lastStart=0;
 626     float lastEnd = 0;
 627
 628     for (int i = 0; i < int(a->runs.size()); i++) {
 629         float_ligne_run runA = a->runs[i];
 630         if ( runA.vst <= tresh ) {
 631             if ( runA.ven <= tresh ) {
 632                 if ( startExists ) {
 633                     if ( lastEnd >= runA.st - 0.00001 ) {
 634                         lastEnd = runA.en;
 635                     } else {
 636                         if ( addIt ) {
 637                             AddRun(lastStart, lastEnd, tresh, tresh);
 638                         }
 639                         lastStart = runA.st;
 640                         lastEnd = runA.en;
 641                     }
 642                 } else {
 643                     lastStart = runA.st;
 644                     lastEnd = runA.en;
 645                 }
 646                 startExists = true;
 647             } else {
 648                 float cutPos = (runA.st * (tresh - runA.ven) + runA.en * (runA.vst - tresh)) / (runA.vst - runA.ven);
 649                 if ( startExists ) {
 650                     if ( lastEnd >= runA.st - 0.00001 ) {
 651                         if ( addIt ) {
 652                             AddRun(lastStart, cutPos, tresh, tresh);
 653                         }
 654                         AddRun(cutPos,runA.en, tresh, runA.ven);
 655                     } else {
 656                         if ( addIt ) {
 657                             AddRun(lastStart, lastEnd, tresh, tresh);
 658                         }
 659                         if ( addIt ) {
 660                             AddRun(runA.st, cutPos, tresh, tresh);
 661                         }
 662                         AddRun(cutPos, runA.en, tresh, runA.ven);
 663                     }
 664                 } else {
 665                     if ( addIt ) {
 666                         AddRun(runA.st, cutPos, tresh, tresh);
 667                     }
 668                     AddRun(cutPos, runA.en, tresh, runA.ven);
 669                 }
 670                 startExists = false;
 671             }
 672
 673         } else {
 674
 675             if ( runA.ven <= tresh ) {
 676                 float cutPos = (runA.st * (runA.ven - tresh) + runA.en * (tresh - runA.vst)) / (runA.ven - runA.vst);
 677                 if ( startExists ) {
 678                     if ( addIt ) {
 679                         AddRun(lastStart, lastEnd, tresh, tresh);
 680                     }
 681                 }
 682                 AddRun(runA.st, cutPos, runA.vst, tresh);
 683                 startExists = true;
 684                 lastStart = cutPos;
 685                 lastEnd = runA.en;
 686             } else {
 687                 if ( startExists ) {
 688                     if ( addIt ) {
 689                         AddRun(lastStart, lastEnd, tresh, tresh);
 690                     }
 691                 }
 692                 startExists = false;
 693                 AddRun(runA.st, runA.en, runA.vst, runA.ven);
 694             }
 695         }
 696     }
 697
 698     if ( startExists ) {
 699         if ( addIt ) {
 700             AddRun(lastStart, lastEnd, tresh, tresh);
 701         }
 702     }
 703 }
 704
 705 /**
 706  * Cuts the coverage a in 2 parts.
 707  *
 708  * over will receive the parts where coverage > tresh, while the present
 709  * FloatLigne will receive the parts where coverage <= tresh.
 710  */
 711 void FloatLigne::Split(FloatLigne *a, float tresh, FloatLigne *over)
 712 {
 713     Reset();
 714     if ( a->runs.empty() ) {
 715         return;
 716     }
 717
 718     for (int i = 0; i < int(a->runs.size()); i++) {
 719         float_ligne_run runA = a->runs[i];
 720         if ( runA.vst >= tresh ) {
 721             if ( runA.ven >= tresh ) {
 722                 if ( over ) {
 723                     over->AddRun(runA.st, runA.en, runA.vst, runA.ven);
 724                 }
 725             } else {
 726                 float cutPos = (runA.st * (tresh - runA.ven) + runA.en * (runA.vst - tresh)) / (runA.vst - runA.ven);
 727                 if ( over ) {
 728                     over->AddRun(runA.st, cutPos, runA.vst, tresh);
 729                 }
 730                 AddRun(cutPos, runA.en, tresh, runA.ven);
 731             }
 732         } else {
 733             if ( runA.ven >= tresh ) {
 734                 float cutPos = (runA.st * (runA.ven - tresh) + runA.en * (tresh-runA.vst)) / (runA.ven - runA.vst);
 735                 AddRun(runA.st, cutPos, runA.vst, tresh);
 736                 if ( over ) {
 737                     over->AddRun(cutPos, runA.en, tresh, runA.ven);
 738                 }
 739             } else {
 740                 AddRun(runA.st, runA.en, runA.vst, runA.ven);
 741             }
 742         }
 743     }
 744 }
 745
 746 /**
 747  * Clips the coverage runs to tresh.
 748  *
 749  * If addIt == false, it only leaves the parts that are not entirely under
 750  * tresh. If addIt == true, it's the coverage clamped to tresh.
 751  */
 752 void FloatLigne::Max(FloatLigne *a, float tresh, bool addIt)
 753 {
 754     Reset();
 755     if ( a->runs.empty() <= 0 ) {
 756         return;
 757     }
 758
 759     bool startExists = false;
 760     float lastStart = 0;
 761     float lastEnd = 0;
 762     for (int i = 0; i < int(a->runs.size()); i++) {
 763         float_ligne_run runA = a->runs[i];
 764         if ( runA.vst >= tresh ) {
 765             if ( runA.ven >= tresh ) {
 766                 if ( startExists ) {
 767                     if ( lastEnd >= runA.st-0.00001 ) {
 768                         lastEnd = runA.en;
 769                     } else {
 770                         if ( addIt ) {
 771                             AddRun(lastStart,lastEnd,tresh,tresh);
 772                         }
 773                         lastStart = runA.st;
 774                         lastEnd = runA.en;
 775                     }
 776                 } else {
 777                     lastStart = runA.st;
 778                     lastEnd = runA.en;
 779                 }
 780                 startExists = true;
 781             } else {
 782                 float cutPos = (runA.st * (tresh - runA.ven) + runA.en * (runA.vst - tresh)) / (runA.vst - runA.ven);
 783                 if ( startExists ) {
 784                     if ( lastEnd >= runA.st-0.00001 ) {
 785                         if ( addIt ) {
 786                             AddRun(lastStart, cutPos, tresh, tresh);
 787                         }
 788                         AddRun(cutPos, runA.en, tresh, runA.ven);
 789                     } else {
 790                         if ( addIt ) {
 791                             AddRun(lastStart, lastEnd, tresh, tresh);
 792                         }
 793                         if ( addIt ) {
 794                             AddRun(runA.st, cutPos, tresh, tresh);
 795                         }
 796                         AddRun(cutPos, runA.en, tresh, runA.ven);
 797                     }
 798                 } else {
 799                     if ( addIt ) {
 800                         AddRun(runA.st, cutPos, tresh, tresh);
 801                     }
 802                     AddRun(cutPos, runA.en, tresh, runA.ven);
 803                 }
 804                 startExists = false;
 805             }
 806
 807         } else {
 808
 809             if ( runA.ven >= tresh ) {
 810                 float cutPos = (runA.st * (runA.ven - tresh) + runA.en * (tresh - runA.vst)) / (runA.ven - runA.vst);
 811                 if ( startExists ) {
 812                     if ( addIt ) {
 813                         AddRun(lastStart,lastEnd,tresh,tresh);
 814                     }
 815                 }
 816                 AddRun(runA.st, cutPos, runA.vst, tresh);
 817                 startExists = true;
 818                 lastStart = cutPos;
 819                 lastEnd = runA.en;
 820             } else {
 821                 if ( startExists ) {
 822                     if ( addIt ) {
 823                         AddRun(lastStart,lastEnd,tresh,tresh);
 824                     }
 825                 }
 826                 startExists = false;
 827                 AddRun(runA.st, runA.en, runA.vst, runA.ven);
 828             }
 829         }
 830     }
 831
 832     if ( startExists ) {
 833         if ( addIt ) {
 834             AddRun(lastStart, lastEnd, tresh, tresh);
 835         }
 836     }
 837 }
 838
 839 /// Extract the parts where coverage > tresh.
 840 void FloatLigne::Over(FloatLigne *a, float tresh)
 841 {
 842     Reset();
 843     if ( a->runs.empty() ) {
 844         return;
 845     }
 846
 847     bool startExists = false;
 848     float lastStart = 0;
 849     float lastEnd = 0;
 850
 851     for (int i = 0; i < int(a->runs.size()); i++) {
 852         float_ligne_run runA = a->runs[i];
 853         if ( runA.vst >= tresh ) {
 854             if ( runA.ven >= tresh ) {
 855                 if ( startExists ) {
 856                     if ( lastEnd >= runA.st - 0.00001 ) {
 857                         lastEnd = runA.en;
 858                     } else {
 859                         AddRun(lastStart, lastEnd, tresh, tresh);
 860                         lastStart = runA.st;
 861                         lastEnd = runA.en;
 862                     }
 863                 } else {
 864                     lastStart = runA.st;
 865                     lastEnd = runA.en;
 866                 }
 867                 startExists = true;
 868
 869             } else {
 870
 871                 float cutPos = (runA.st * (tresh - runA.ven) + runA.en * (runA.vst - tresh)) / (runA.vst - runA.ven);
 872                 if ( startExists ) {
 873                     if ( lastEnd >= runA.st - 0.00001 ) {
 874                         AddRun(lastStart, cutPos, tresh, tresh);
 875                     } else {
 876                         AddRun(lastStart, lastEnd, tresh, tresh);
 877                         AddRun(runA.st, cutPos, tresh, tresh);
 878                     }
 879                 } else {
 880                     AddRun(runA.st, cutPos, tresh, tresh);
 881                 }
 882                 startExists = false;
 883             }
 884
 885         } else {
 886             if ( runA.ven >= tresh ) {
 887                 float cutPos = (runA.st * (runA.ven - tresh) + runA.en * (tresh - runA.vst)) / (runA.ven - runA.vst);
 888                 if ( startExists ) {
 889                     AddRun(lastStart, lastEnd, tresh, tresh);
 890                 }
 891                 startExists = true;
 892                 lastStart = cutPos;
 893                 lastEnd = runA.en;
 894             } else {
 895                 if ( startExists ) {
 896                     AddRun(lastStart, lastEnd, tresh, tresh);
 897                 }
 898                 startExists = false;
 899             }
 900         }
 901     }
 902
 903     if ( startExists ) {
 904         AddRun(lastStart, lastEnd, tresh, tresh);
 905     }
 906 }
 907
 908
 909 /*
 910   Local Variables:
 911   mode:c++
 912   c-file-style:"stroustrup"
 913   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
 914   indent-tabs-mode:nil
 915   fill-column:99
 916   End:
 917 */
 918 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :