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     if ( no < 0 || no >= int(bords.size()) ) {
 312         return;
 313     }
 314
 315     if ( s_first < 0 ) {
 316         s_first = s_last = no;
 317         bords[no].s_prev = -1;
 318         bords[no].s_next = -1;
 319         return;
 320     }
 321
 322     if ( guess < 0 || guess >= int(bords.size()) ) {
 323         int c = s_first;
 324         while ( c >= 0 && c < int(bords.size()) && CmpBord(bords[c], bords[no]) < 0 ) {
 325             c = bords[c].s_next;
 326         }
 327
 328         if ( c < 0 || c >= int(bords.size()) ) {
 329             bords[no].s_prev = s_last;
 330             bords[s_last].s_next = no;
 331             s_last = no;
 332         } else {
 333             bords[no].s_prev = bords[c].s_prev;
 334             if ( bords[no].s_prev >= 0 ) {
 335                 bords[bords[no].s_prev].s_next = no;
 336             } else {
 337                 s_first = no;
 338             }
 339             bords[no].s_next = c;
 340             bords[c].s_prev = no;
 341         }
 342     } else {
 343         int c = guess;
 344         int stTst = CmpBord(bords[c], bords[no]);
 345
 346         if ( stTst == 0 ) {
 347
 348             bords[no].s_prev = bords[c].s_prev;
 349             if ( bords[no].s_prev >= 0 ) {
 350                 bords[bords[no].s_prev].s_next = no;
 351             } else {
 352                 s_first = no;
 353             }
 354             bords[no].s_next = c;
 355             bords[c].s_prev = no;
 356
 357         } else if ( stTst > 0 ) {
 358
 359             while ( c >= 0 && c < int(bords.size()) && CmpBord(bords[c], bords[no]) > 0 ) {
 360                 c = bords[c].s_prev;
 361             }
 362
 363             if ( c < 0 || c >= int(bords.size()) ) {
 364                 bords[no].s_next = s_first;
 365                 bords[s_first].s_prev =no; // s_first != -1
 366                 s_first = no;
 367             } else {
 368                 bords[no].s_next = bords[c].s_next;
 369                 if ( bords[no].s_next >= 0 ) {
 370                     bords[bords[no].s_next].s_prev = no;
 371                 } else {
 372                     s_last = no;
 373                 }
 374                 bords[no].s_prev = c;
 375                 bords[c].s_next = no;
 376             }
 377
 378         } else {
 379
 380             while ( c >= 0 && c < int(bords.size()) && CmpBord(bords[c],bords[no]) < 0 ) {
 381                 c = bords[c].s_next;
 382             }
 383
 384             if ( c < 0 || c >= int(bords.size()) ) {
 385                 bords[no].s_prev = s_last;
 386                 bords[s_last].s_next = no;
 387                 s_last = no;
 388             } else {
 389                 bords[no].s_prev = bords[c].s_prev;
 390                 if ( bords[no].s_prev >= 0 ) {
 391                     bords[bords[no].s_prev].s_next = no;
 392                 } else {
 393                     s_first = no;
 394                 }
 395                 bords[no].s_next = c;
 396                 bords[c].s_prev = no;
 397             }
 398         }
 399     }
 400 }
 401
 402 /**
 403  * Computes the sum of the coverages of the runs currently being scanned,
 404  * of which there are "pending".
 405  */
 406 float FloatLigne::RemainingValAt(float at, int pending)
 407 {
 408     float sum = 0;
 409 /*      int     no=firstAc;
 410         while ( no >= 0 && no < bords.size() ) {
 411                 int   nn=bords[no].other;
 412                 sum+=bords[nn].val+(at-bords[nn].pos)*bords[nn].pente;
 413 //                              sum+=((at-bords[nn].pos)*bords[no].val+(bords[no].pos-at)*bords[nn].val)/(bords[no].pos-bords[nn].pos);
 414 //              sum+=ValAt(at,bords[nn].pos,bords[no].pos,bords[nn].val,bords[no].val);
 415                 no=bords[no].next;
 416         }*/
 417   // for each portion being scanned, compute coverage at position "at" and sum.
 418   // we could simply compute the sum of portion coverages as a "f(x)=ux+y" and evaluate it at "x=at",
 419   // but there are numerical problems with this approach, and it produces ugly lines of incorrectly
 420   // computed alpha values, so i reverted to this "safe but slow" version
 421
 422     for (int i=0; i < pending; i++) {
 423         int const nn = bords[i].pend_ind;
 424         sum += bords[nn].val + (at - bords[nn].pos) * bords[nn].pente;
 425     }
 426
 427     return sum;
 428 }
 429
 430
 431 /**
 432  * Extract a set of non-overlapping runs from the boundaries.
 433  *
 434  * We scan the boundaries left to right, maintaining a set of coverage
 435  * portions currently being scanned. For each such portion, the function
 436  * will add the index of its first boundary in an array; but instead of
 437  * allocating another array, it uses a field in float_ligne_bord: pend_ind.
 438  * The outcome is that an array of float_ligne_run is produced.
 439  */
 440 void FloatLigne::Flatten()
 441 {
 442     if ( int(bords.size()) <= 1 ) {
 443         Reset();
 444         return;
 445     }
 446
 447     runs.clear();
 448
 449 //      qsort(bords,bords.size(),sizeof(float_ligne_bord),FloatLigne::CmpBord);
 450 //      SortBords(0,bords.size()-1);
 451
 452     float totPente = 0;
 453     float totStart = 0;
 454     float totX = bords[0].pos;
 455
 456     bool startExists = false;
 457     float lastStart = 0;
 458     float lastVal = 0;
 459     int pending = 0;
 460
 461 //      for (int i=0;i<bords.size();) {
 462     // read the list from left to right, adding a run for each boundary crossed, minus runs with alpha=0
 463     for (int i=/*0*/s_first; i>=0 && i < int(bords.size()) ;) {
 464
 465         float cur = bords[i].pos;  // position of the current boundary (there may be several boundaries at this position)
 466         float leftV = 0;  // deltas in coverage value at this position
 467         float rightV = 0;
 468         float leftP = 0; // deltas in coverage increase per unit length at this position
 469         float rightP = 0;
 470
 471         // more precisely, leftV is the sum of decreases of coverage value,
 472         // while rightV is the sum of increases, so that leftV+rightV is the delta.
 473         // idem for leftP and rightP
 474
 475         // start by scanning all boundaries that end a portion at this position
 476         while ( i >= 0 && i < int(bords.size()) && bords[i].pos == cur && bords[i].start == false ) {
 477             leftV += bords[i].val;
 478             leftP += bords[i].pente;
 479
 480 #ifndef faster_flatten
 481             // we need to remove the boundary that started this coverage portion for the pending list
 482             if ( bords[i].other >= 0 && bords[i].other < int(bords.size()) ) {
 483                 // so we use the pend_inv "array"
 484                 int const k = bords[bords[i].other].pend_inv;
 485                 if ( k >= 0 && k < pending ) {
 486                     // and update the pend_ind array and its inverse pend_inv
 487                     bords[k].pend_ind = bords[pending - 1].pend_ind;
 488                     bords[bords[k].pend_ind].pend_inv = k;
 489                 }
 490             }
 491 #endif
 492
 493             // one less portion pending
 494             pending--;
 495             // and we move to the next boundary in the doubly linked list
 496             i=bords[i].s_next;
 497             //i++;
 498         }
 499
 500         // then scan all boundaries that start a portion at this position
 501         while ( i >= 0 && i < int(bords.size()) && bords[i].pos == cur && bords[i].start == true ) {
 502             rightV += bords[i].val;
 503             rightP += bords[i].pente;
 504 #ifndef faster_flatten
 505             bords[pending].pend_ind=i;
 506             bords[i].pend_inv=pending;
 507 #endif
 508             pending++;
 509             i = bords[i].s_next;
 510             //i++;
 511         }
 512
 513         // coverage value at end of the run will be "start coverage"+"delta per unit length"*"length"
 514         totStart = totStart + totPente * (cur - totX);
 515
 516         if ( startExists ) {
 517             // add that run
 518             AddRun(lastStart, cur, lastVal, totStart, totPente);
 519         }
 520         // update "delta coverage per unit length"
 521         totPente += rightP - leftP;
 522         // not really needed here
 523         totStart += rightV - leftV;
 524         // update position
 525         totX = cur;
 526         if ( pending > 0 ) {
 527             startExists = true;
 528
 529 #ifndef faster_flatten
 530             // to avoid accumulation of numerical errors, we compute an accurate coverage for this position "cur"
 531             totStart = RemainingValAt(cur, pending);
 532 #endif
 533             lastVal = totStart;
 534             lastStart = cur;
 535         } else {
 536             startExists = false;
 537             totStart = 0;
 538             totPente = 0;
 539         }
 540     }
 541 }
 542
 543
 544 /// Debug dump of the instance.
 545 void FloatLigne::Affiche()
 546 {
 547     printf("%lu : \n", (long unsigned int) bords.size());
 548     for (int i = 0; i < int(bords.size()); i++) {
 549         printf("(%f %f %f %i) ",bords[i].pos,bords[i].val,bords[i].pente,(bords[i].start?1:0)); // localization ok
 550     }
 551
 552     printf("\n");
 553     printf("%lu : \n", (long unsigned int) runs.size());
 554
 555     for (int i = 0; i < int(runs.size()); i++) {
 556         printf("(%f %f -> %f %f / %f)",
 557                runs[i].st, runs[i].vst, runs[i].en, runs[i].ven, runs[i].pente); // localization ok
 558     }
 559
 560     printf("\n");
 561 }
 562
 563
 564 int FloatLigne::AddRun(float st, float en, float vst, float ven)
 565 {
 566     return AddRun(st, en, vst, ven, (ven - vst) / (en - st));
 567 }
 568
 569
 570 int FloatLigne::AddRun(float st, float en, float vst, float ven, float pente)
 571 {
 572     if ( st >= en ) {
 573         return -1;
 574     }
 575
 576     int const n = runs.size();
 577     float_ligne_run r;
 578     r.st = st;
 579     r.en = en;
 580     r.vst = vst;
 581     r.ven = ven;
 582     r.pente = pente;
 583     runs.push_back(r);
 584
 585     return n;
 586 }
 587
 588 void FloatLigne::Copy(FloatLigne *a)
 589 {
 590     if ( a->runs.empty() ) {
 591         Reset();
 592         return;
 593     }
 594
 595     bords.clear();
 596     runs = a->runs;
 597 }
 598
 599 void FloatLigne::Copy(IntLigne *a)
 600 {
 601     if ( a->nbRun ) {
 602         Reset();
 603         return;
 604     }
 605
 606     bords.clear();
 607     runs.resize(a->nbRun);
 608
 609     for (int i = 0; i < int(runs.size()); i++) {
 610         runs[i].st = a->runs[i].st;
 611         runs[i].en = a->runs[i].en;
 612         runs[i].vst = a->runs[i].vst;
 613         runs[i].ven = a->runs[i].ven;
 614     }
 615 }
 616
 617 /// Cuts the parts having less than tresh coverage.
 618 void FloatLigne::Min(FloatLigne *a, float tresh, bool addIt)
 619 {
 620     Reset();
 621     if ( a->runs.empty() ) {
 622         return;
 623     }
 624
 625     bool startExists = false;
 626     float lastStart=0;
 627     float lastEnd = 0;
 628
 629     for (int i = 0; i < int(a->runs.size()); i++) {
 630         float_ligne_run runA = a->runs[i];
 631         if ( runA.vst <= tresh ) {
 632             if ( runA.ven <= tresh ) {
 633                 if ( startExists ) {
 634                     if ( lastEnd >= runA.st - 0.00001 ) {
 635                         lastEnd = runA.en;
 636                     } else {
 637                         if ( addIt ) {
 638                             AddRun(lastStart, lastEnd, tresh, tresh);
 639                         }
 640                         lastStart = runA.st;
 641                         lastEnd = runA.en;
 642                     }
 643                 } else {
 644                     lastStart = runA.st;
 645                     lastEnd = runA.en;
 646                 }
 647                 startExists = true;
 648             } else {
 649                 float cutPos = (runA.st * (tresh - runA.ven) + runA.en * (runA.vst - tresh)) / (runA.vst - runA.ven);
 650                 if ( startExists ) {
 651                     if ( lastEnd >= runA.st - 0.00001 ) {
 652                         if ( addIt ) {
 653                             AddRun(lastStart, cutPos, tresh, tresh);
 654                         }
 655                         AddRun(cutPos,runA.en, tresh, runA.ven);
 656                     } else {
 657                         if ( addIt ) {
 658                             AddRun(lastStart, lastEnd, tresh, tresh);
 659                         }
 660                         if ( addIt ) {
 661                             AddRun(runA.st, cutPos, tresh, tresh);
 662                         }
 663                         AddRun(cutPos, runA.en, tresh, runA.ven);
 664                     }
 665                 } else {
 666                     if ( addIt ) {
 667                         AddRun(runA.st, cutPos, tresh, tresh);
 668                     }
 669                     AddRun(cutPos, runA.en, tresh, runA.ven);
 670                 }
 671                 startExists = false;
 672             }
 673
 674         } else {
 675
 676             if ( runA.ven <= tresh ) {
 677                 float cutPos = (runA.st * (runA.ven - tresh) + runA.en * (tresh - runA.vst)) / (runA.ven - runA.vst);
 678                 if ( startExists ) {
 679                     if ( addIt ) {
 680                         AddRun(lastStart, lastEnd, tresh, tresh);
 681                     }
 682                 }
 683                 AddRun(runA.st, cutPos, runA.vst, tresh);
 684                 startExists = true;
 685                 lastStart = cutPos;
 686                 lastEnd = runA.en;
 687             } else {
 688                 if ( startExists ) {
 689                     if ( addIt ) {
 690                         AddRun(lastStart, lastEnd, tresh, tresh);
 691                     }
 692                 }
 693                 startExists = false;
 694                 AddRun(runA.st, runA.en, runA.vst, runA.ven);
 695             }
 696         }
 697     }
 698
 699     if ( startExists ) {
 700         if ( addIt ) {
 701             AddRun(lastStart, lastEnd, tresh, tresh);
 702         }
 703     }
 704 }
 705
 706 /**
 707  * Cuts the coverage a in 2 parts.
 708  *
 709  * over will receive the parts where coverage > tresh, while the present
 710  * FloatLigne will receive the parts where coverage <= tresh.
 711  */
 712 void FloatLigne::Split(FloatLigne *a, float tresh, FloatLigne *over)
 713 {
 714     Reset();
 715     if ( a->runs.empty() ) {
 716         return;
 717     }
 718
 719     for (int i = 0; i < int(a->runs.size()); i++) {
 720         float_ligne_run runA = a->runs[i];
 721         if ( runA.vst >= tresh ) {
 722             if ( runA.ven >= tresh ) {
 723                 if ( over ) {
 724                     over->AddRun(runA.st, runA.en, runA.vst, runA.ven);
 725                 }
 726             } else {
 727                 float cutPos = (runA.st * (tresh - runA.ven) + runA.en * (runA.vst - tresh)) / (runA.vst - runA.ven);
 728                 if ( over ) {
 729                     over->AddRun(runA.st, cutPos, runA.vst, tresh);
 730                 }
 731                 AddRun(cutPos, runA.en, tresh, runA.ven);
 732             }
 733         } else {
 734             if ( runA.ven >= tresh ) {
 735                 float cutPos = (runA.st * (runA.ven - tresh) + runA.en * (tresh-runA.vst)) / (runA.ven - runA.vst);
 736                 AddRun(runA.st, cutPos, runA.vst, tresh);
 737                 if ( over ) {
 738                     over->AddRun(cutPos, runA.en, tresh, runA.ven);
 739                 }
 740             } else {
 741                 AddRun(runA.st, runA.en, runA.vst, runA.ven);
 742             }
 743         }
 744     }
 745 }
 746
 747 /**
 748  * Clips the coverage runs to tresh.
 749  *
 750  * If addIt == false, it only leaves the parts that are not entirely under
 751  * tresh. If addIt == true, it's the coverage clamped to tresh.
 752  */
 753 void FloatLigne::Max(FloatLigne *a, float tresh, bool addIt)
 754 {
 755     Reset();
 756     if ( a->runs.empty() <= 0 ) {
 757         return;
 758     }
 759
 760     bool startExists = false;
 761     float lastStart = 0;
 762     float lastEnd = 0;
 763     for (int i = 0; i < int(a->runs.size()); i++) {
 764         float_ligne_run runA = a->runs[i];
 765         if ( runA.vst >= tresh ) {
 766             if ( runA.ven >= tresh ) {
 767                 if ( startExists ) {
 768                     if ( lastEnd >= runA.st-0.00001 ) {
 769                         lastEnd = runA.en;
 770                     } else {
 771                         if ( addIt ) {
 772                             AddRun(lastStart,lastEnd,tresh,tresh);
 773                         }
 774                         lastStart = runA.st;
 775                         lastEnd = runA.en;
 776                     }
 777                 } else {
 778                     lastStart = runA.st;
 779                     lastEnd = runA.en;
 780                 }
 781                 startExists = true;
 782             } else {
 783                 float cutPos = (runA.st * (tresh - runA.ven) + runA.en * (runA.vst - tresh)) / (runA.vst - runA.ven);
 784                 if ( startExists ) {
 785                     if ( lastEnd >= runA.st-0.00001 ) {
 786                         if ( addIt ) {
 787                             AddRun(lastStart, cutPos, tresh, tresh);
 788                         }
 789                         AddRun(cutPos, runA.en, tresh, runA.ven);
 790                     } else {
 791                         if ( addIt ) {
 792                             AddRun(lastStart, lastEnd, tresh, tresh);
 793                         }
 794                         if ( addIt ) {
 795                             AddRun(runA.st, cutPos, tresh, tresh);
 796                         }
 797                         AddRun(cutPos, runA.en, tresh, runA.ven);
 798                     }
 799                 } else {
 800                     if ( addIt ) {
 801                         AddRun(runA.st, cutPos, tresh, tresh);
 802                     }
 803                     AddRun(cutPos, runA.en, tresh, runA.ven);
 804                 }
 805                 startExists = false;
 806             }
 807
 808         } else {
 809
 810             if ( runA.ven >= tresh ) {
 811                 float cutPos = (runA.st * (runA.ven - tresh) + runA.en * (tresh - runA.vst)) / (runA.ven - runA.vst);
 812                 if ( startExists ) {
 813                     if ( addIt ) {
 814                         AddRun(lastStart,lastEnd,tresh,tresh);
 815                     }
 816                 }
 817                 AddRun(runA.st, cutPos, runA.vst, tresh);
 818                 startExists = true;
 819                 lastStart = cutPos;
 820                 lastEnd = runA.en;
 821             } else {
 822                 if ( startExists ) {
 823                     if ( addIt ) {
 824                         AddRun(lastStart,lastEnd,tresh,tresh);
 825                     }
 826                 }
 827                 startExists = false;
 828                 AddRun(runA.st, runA.en, runA.vst, runA.ven);
 829             }
 830         }
 831     }
 832
 833     if ( startExists ) {
 834         if ( addIt ) {
 835             AddRun(lastStart, lastEnd, tresh, tresh);
 836         }
 837     }
 838 }
 839
 840 /// Extract the parts where coverage > tresh.
 841 void FloatLigne::Over(FloatLigne *a, float tresh)
 842 {
 843     Reset();
 844     if ( a->runs.empty() ) {
 845         return;
 846     }
 847
 848     bool startExists = false;
 849     float lastStart = 0;
 850     float lastEnd = 0;
 851
 852     for (int i = 0; i < int(a->runs.size()); i++) {
 853         float_ligne_run runA = a->runs[i];
 854         if ( runA.vst >= tresh ) {
 855             if ( runA.ven >= tresh ) {
 856                 if ( startExists ) {
 857                     if ( lastEnd >= runA.st - 0.00001 ) {
 858                         lastEnd = runA.en;
 859                     } else {
 860                         AddRun(lastStart, lastEnd, tresh, tresh);
 861                         lastStart = runA.st;
 862                         lastEnd = runA.en;
 863                     }
 864                 } else {
 865                     lastStart = runA.st;
 866                     lastEnd = runA.en;
 867                 }
 868                 startExists = true;
 869
 870             } else {
 871
 872                 float cutPos = (runA.st * (tresh - runA.ven) + runA.en * (runA.vst - tresh)) / (runA.vst - runA.ven);
 873                 if ( startExists ) {
 874                     if ( lastEnd >= runA.st - 0.00001 ) {
 875                         AddRun(lastStart, cutPos, tresh, tresh);
 876                     } else {
 877                         AddRun(lastStart, lastEnd, tresh, tresh);
 878                         AddRun(runA.st, cutPos, tresh, tresh);
 879                     }
 880                 } else {
 881                     AddRun(runA.st, cutPos, tresh, tresh);
 882                 }
 883                 startExists = false;
 884             }
 885
 886         } else {
 887             if ( runA.ven >= tresh ) {
 888                 float cutPos = (runA.st * (runA.ven - tresh) + runA.en * (tresh - runA.vst)) / (runA.ven - runA.vst);
 889                 if ( startExists ) {
 890                     AddRun(lastStart, lastEnd, tresh, tresh);
 891                 }
 892                 startExists = true;
 893                 lastStart = cutPos;
 894                 lastEnd = runA.en;
 895             } else {
 896                 if ( startExists ) {
 897                     AddRun(lastStart, lastEnd, tresh, tresh);
 898                 }
 899                 startExists = false;
 900             }
 901         }
 902     }
 903
 904     if ( startExists ) {
 905         AddRun(lastStart, lastEnd, tresh, tresh);
 906     }
 907 }
 908
 909
 910 /*
 911   Local Variables:
 912   mode:c++
 913   c-file-style:"stroustrup"
 914   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
 915   indent-tabs-mode:nil
 916   fill-column:99
 917   End:
 918 */
 919 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :