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