1 // SPDX-License-Identifier: GPL-2.0-or-later
2 /** @file
3 * Implementation of coverage with floating-point values.
4 *//*
5 * Authors:
6 * see git history
7 * Fred
8 *
9 * Copyright (C) 2018 Authors
10 * Released under GNU GPL v2+, read the file 'COPYING' for more information.
11 */
12
13 #ifdef faster_flatten
14 # include <cmath> // std::abs(float)
15 #endif
16 #include <cstdio>
17 #include "livarot/float-line.h"
18 #include "livarot/int-line.h"
19 #include <cstdio>
20
FloatLigne()21 FloatLigne::FloatLigne()
22 {
23 s_first = s_last = -1;
24 }
25
26
27 FloatLigne::~FloatLigne()
28 = default;
29
30 /// Reset the line to empty (boundaries and runs).
Reset()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 */
AddBord(float spos,float sval,float epos,float eval,int guess)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 */
AddBord(float spos,float sval,float epos,float eval,float pente,int guess)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 */
AddBordR(float spos,float sval,float epos,float eval,float pente,int guess)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 */
AppendBord(float spos,float sval,float epos,float eval,float pente)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
InsertBord(int no,float,int guess)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 */
RemainingValAt(float at,int pending)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 */
Flatten()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 ) {
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.
Affiche()546 void FloatLigne::Affiche()
547 {
548 printf("%lu : \n", (long unsigned int) bords.size());
549 for (auto & bord : bords) {
550 printf("(%f %f %f %i) ",bord.pos,bord.val,bord.pente,(bord.start?1:0)); // localization ok
551 }
552
553 printf("\n");
554 printf("%lu : \n", (long unsigned int) runs.size());
555
556 for (auto & run : runs) {
557 printf("(%f %f -> %f %f / %f)",
558 run.st, run.vst, run.en, run.ven, run.pente); // localization ok
559 }
560
561 printf("\n");
562 }
563
564
AddRun(float st,float en,float vst,float ven)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
AddRun(float st,float en,float vst,float ven,float pente)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
Copy(FloatLigne * a)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
Copy(IntLigne * a)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.
Min(FloatLigne * a,float tresh,bool addIt)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 (auto runA : a->runs) {
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 */
Split(FloatLigne * a,float tresh,FloatLigne * over)712 void FloatLigne::Split(FloatLigne *a, float tresh, FloatLigne *over)
713 {
714 Reset();
715 if ( a->runs.empty() ) {
716 return;
717 }
718
719 for (auto runA : a->runs) {
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 is false, it only leaves the parts that are not entirely under
750 * tresh. If addIt is true, it's the coverage clamped to tresh.
751 */
Max(FloatLigne * a,float tresh,bool addIt)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 (auto runA : a->runs) {
763 if ( runA.vst >= tresh ) {
764 if ( runA.ven >= tresh ) {
765 if ( startExists ) {
766 if ( lastEnd >= runA.st-0.00001 ) {
767 lastEnd = runA.en;
768 } else {
769 if ( addIt ) {
770 AddRun(lastStart,lastEnd,tresh,tresh);
771 }
772 lastStart = runA.st;
773 lastEnd = runA.en;
774 }
775 } else {
776 lastStart = runA.st;
777 lastEnd = runA.en;
778 }
779 startExists = true;
780 } else {
781 float cutPos = (runA.st * (tresh - runA.ven) + runA.en * (runA.vst - tresh)) / (runA.vst - runA.ven);
782 if ( startExists ) {
783 if ( lastEnd >= runA.st-0.00001 ) {
784 if ( addIt ) {
785 AddRun(lastStart, cutPos, tresh, tresh);
786 }
787 AddRun(cutPos, runA.en, tresh, runA.ven);
788 } else {
789 if ( addIt ) {
790 AddRun(lastStart, lastEnd, tresh, tresh);
791 }
792 if ( addIt ) {
793 AddRun(runA.st, cutPos, tresh, tresh);
794 }
795 AddRun(cutPos, runA.en, tresh, runA.ven);
796 }
797 } else {
798 if ( addIt ) {
799 AddRun(runA.st, cutPos, tresh, tresh);
800 }
801 AddRun(cutPos, runA.en, tresh, runA.ven);
802 }
803 startExists = false;
804 }
805
806 } else {
807
808 if ( runA.ven >= tresh ) {
809 float cutPos = (runA.st * (runA.ven - tresh) + runA.en * (tresh - runA.vst)) / (runA.ven - runA.vst);
810 if ( startExists ) {
811 if ( addIt ) {
812 AddRun(lastStart,lastEnd,tresh,tresh);
813 }
814 }
815 AddRun(runA.st, cutPos, runA.vst, tresh);
816 startExists = true;
817 lastStart = cutPos;
818 lastEnd = runA.en;
819 } else {
820 if ( startExists ) {
821 if ( addIt ) {
822 AddRun(lastStart,lastEnd,tresh,tresh);
823 }
824 }
825 startExists = false;
826 AddRun(runA.st, runA.en, runA.vst, runA.ven);
827 }
828 }
829 }
830
831 if ( startExists ) {
832 if ( addIt ) {
833 AddRun(lastStart, lastEnd, tresh, tresh);
834 }
835 }
836 }
837
838 /// Extract the parts where coverage > tresh.
Over(FloatLigne * a,float tresh)839 void FloatLigne::Over(FloatLigne *a, float tresh)
840 {
841 Reset();
842 if ( a->runs.empty() ) {
843 return;
844 }
845
846 bool startExists = false;
847 float lastStart = 0;
848 float lastEnd = 0;
849
850 for (auto runA : a->runs) {
851 if ( runA.vst >= tresh ) {
852 if ( runA.ven >= tresh ) {
853 if ( startExists ) {
854 if ( lastEnd >= runA.st - 0.00001 ) {
855 lastEnd = runA.en;
856 } else {
857 AddRun(lastStart, lastEnd, tresh, tresh);
858 lastStart = runA.st;
859 lastEnd = runA.en;
860 }
861 } else {
862 lastStart = runA.st;
863 lastEnd = runA.en;
864 }
865 startExists = true;
866
867 } else {
868
869 float cutPos = (runA.st * (tresh - runA.ven) + runA.en * (runA.vst - tresh)) / (runA.vst - runA.ven);
870 if ( startExists ) {
871 if ( lastEnd >= runA.st - 0.00001 ) {
872 AddRun(lastStart, cutPos, tresh, tresh);
873 } else {
874 AddRun(lastStart, lastEnd, tresh, tresh);
875 AddRun(runA.st, cutPos, tresh, tresh);
876 }
877 } else {
878 AddRun(runA.st, cutPos, tresh, tresh);
879 }
880 startExists = false;
881 }
882
883 } else {
884 if ( runA.ven >= tresh ) {
885 float cutPos = (runA.st * (runA.ven - tresh) + runA.en * (tresh - runA.vst)) / (runA.ven - runA.vst);
886 if ( startExists ) {
887 AddRun(lastStart, lastEnd, tresh, tresh);
888 }
889 startExists = true;
890 lastStart = cutPos;
891 lastEnd = runA.en;
892 } else {
893 if ( startExists ) {
894 AddRun(lastStart, lastEnd, tresh, tresh);
895 }
896 startExists = false;
897 }
898 }
899 }
900
901 if ( startExists ) {
902 AddRun(lastStart, lastEnd, tresh, tresh);
903 }
904 }
905
906
907 /*
908 Local Variables:
909 mode:c++
910 c-file-style:"stroustrup"
911 c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
912 indent-tabs-mode:nil
913 fill-column:99
914 End:
915 */
916 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :
917