Adding upstream version 1.0.2.upstream/1.0.2upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 916 insertions, 0 deletions

diff --git a/src/livarot/float-line.cpp b/src/livarot/float-line.cpp
new file mode 100644
index 0000000..9a19729
--- /dev/null
+++ b/src/livarot/float-line.cpp
@@ -0,0 +1,916 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/** @file
+ * Implementation of coverage with floating-point values.
+ *//*
+ * Authors:
+ * see git history
+ * Fred
+ *
+ * Copyright (C) 2018 Authors
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+
+#ifdef faster_flatten
+# include <cmath>  // std::abs(float)
+#endif
+#include <cstdio>
+#include "livarot/float-line.h"
+#include "livarot/int-line.h"
+#include <cstdio>
+
+FloatLigne::FloatLigne()
+{
+    s_first = s_last = -1;
+}
+
+
+FloatLigne::~FloatLigne()
+= default;
+
+/// Reset the line to  empty (boundaries and runs).
+void FloatLigne::Reset()
+{
+    bords.clear();
+    runs.clear();
+    s_first = s_last = -1;
+}
+
+/**
+ * Add a coverage portion.
+ *
+ * \param guess Position from where we should try to insert the first 
+ * boundary, or -1 if we don't have a clue.
+ */
+int FloatLigne::AddBord(float spos, float sval, float epos, float eval, int guess)
+{
+//  if ( showCopy ) printf("b= %f %f -> %f %f \n",spos,sval,epos,eval);
+    if ( spos >= epos ) {
+        return -1;
+    }
+
+    float pente = (eval - sval) / (epos - spos);
+    
+#ifdef faster_flatten
+    if ( std::abs(epos - spos) < 0.001 || std::abs(pente) > 1000 ) {
+        return -1;
+        epos = spos;
+        pente = 0;
+    }
+#endif
+  
+    if ( guess >= int(bords.size()) ) {
+        guess = -1;
+    }
+    
+    // add the left boundary
+    float_ligne_bord b;
+    int n = bords.size();
+    b.pos = spos;
+    b.val = sval;
+    b.start = true;
+    b.other = n + 1;
+    b.pente = pente;
+    b.s_prev = b.s_next = -1;
+    bords.push_back(b);
+
+    // insert it in the doubly-linked list
+    InsertBord(n, spos, guess);
+    
+    // add the right boundary
+    n = bords.size();
+    b.pos = epos;
+    b.val = eval;
+    b.start = false;
+    b.other = n-1;
+    b.pente = pente;
+    b.s_prev = b.s_next = -1;
+    bords.push_back(b);
+    
+    // insert it in the doubly-linked list, knowing that boundary at index n-1 is not too far before me
+    InsertBord(n, epos, n - 1);
+  	
+    return n;
+}
+
+/**
+ * Add a coverage portion.
+ *
+ * \param guess Position from where we should try to insert the first 
+ * boundary, or -1 if we don't have a clue.
+ */
+int FloatLigne::AddBord(float spos, float sval, float epos, float eval, float pente, int guess)
+{
+//  if ( showCopy ) printf("b= %f %f -> %f %f \n",spos,sval,epos,eval);
+    if ( spos >= epos ) {
+        return -1;
+    }
+
+#ifdef faster_flatten
+    if ( std::abs(epos - spos) < 0.001 || std::abs(pente) > 1000 ) {
+        return -1;
+        epos = spos;
+        pente = 0;
+    }
+#endif
+    
+    if ( guess >= int(bords.size()) ) {
+        guess=-1;
+    }
+
+    float_ligne_bord b;
+    int n = bords.size();
+    b.pos = spos;
+    b.val = sval;
+    b.start = true;
+    b.other = n + 1;
+    b.pente = pente;
+    b.s_prev = b.s_next = -1;
+    bords.push_back(b);
+
+    n = bords.size();
+    b.pos = epos;
+    b.val = eval;
+    b.start = false;
+    b.other = n - 1;
+    b.pente = pente;
+    b.s_prev = b.s_next = -1;
+    bords.push_back(b);
+
+    InsertBord(n - 1, spos, guess);
+    InsertBord(n, epos, n - 1);
+/*	if ( bords[n-1].s_next < 0 ) {
+		bords[n].s_next=-1;
+		s_last=n;
+
+		bords[n].s_prev=n-1;
+		bords[n-1].s_next=n;
+	} else if ( bords[bords[n-1].s_next].pos >= epos ) {
+		bords[n].s_next=bords[n-1].s_next;
+		bords[bords[n].s_next].s_prev=n;
+		
+		bords[n].s_prev=n-1;
+		bords[n-1].s_next=n;
+	} else {
+		int c=bords[bords[n-1].s_next].s_next;
+		while ( c >= 0 && bords[c].pos < epos ) c=bords[c].s_next;
+		if ( c < 0 ) {
+			bords[n].s_prev=s_last;
+			bords[s_last].s_next=n;
+			s_last=n;
+		} else {
+			bords[n].s_prev=bords[c].s_prev;
+			bords[bords[n].s_prev].s_next=n;
+
+			bords[n].s_next=c;
+			bords[c].s_prev=n;
+		}
+
+	}*/
+    return n;
+}
+
+/**
+ * Add a coverage portion.
+ *
+ * \param guess Position from where we should try to insert the last
+ * boundary, or -1 if we don't have a clue.
+ */
+int FloatLigne::AddBordR(float spos, float sval, float epos, float eval, float pente, int guess)
+{
+//  if ( showCopy ) printf("br= %f %f -> %f %f \n",spos,sval,epos,eval);
+//	return AddBord(spos,sval,epos,eval,pente,guess);
+    if ( spos >= epos ){
+        return -1;
+    }
+    
+#ifdef faster_flatten
+    if ( std::abs(epos - spos) < 0.001 || std::abs(pente) > 1000 ) {
+        return -1;
+        epos = spos;
+        pente = 0;
+    }
+#endif
+
+    if ( guess >= int(bords.size()) ) {
+        guess=-1;
+    }
+
+    float_ligne_bord b;
+    int n = bords.size();
+    b.pos = spos;
+    b.val = sval;
+    b.start = true;
+    b.other = n + 1;
+    b.pente = pente;
+    b.s_prev = b.s_next = -1;
+    bords.push_back(b);
+    
+    n = bords.size();
+    b.pos = epos;
+    b.val = eval;
+    b.start = false;
+    b.other = n - 1;
+    b.pente = pente;
+    b.s_prev = b.s_next = -1;
+    bords.push_back(b);
+    
+    InsertBord(n, epos, guess);
+    InsertBord(n - 1, spos, n);
+    
+/*	if ( bords[n].s_prev < 0 ) {
+		bords[n-1].s_prev=-1;
+		s_first=n-1;
+
+		bords[n-1].s_next=n;
+		bords[n].s_prev=n-1;
+	} else if ( bords[bords[n].s_prev].pos <= spos ) {
+		bords[n-1].s_prev=bords[n].s_prev;
+		bords[bords[n-1].s_prev].s_next=n-1;
+
+		bords[n-1].s_next=n;
+		bords[n].s_prev=n-1;
+	} else {
+		int c=bords[bords[n].s_prev].s_prev;
+		while ( c >= 0 && bords[c].pos > spos ) c=bords[c].s_prev;
+		if ( c < 0 ) {
+			bords[n-1].s_next=s_first;
+			bords[s_first].s_prev=n-1;
+			s_first=n-1;
+		} else {
+			bords[n-1].s_next=bords[c].s_next;
+			bords[bords[n-1].s_next].s_prev=n-1;
+
+			bords[n-1].s_prev=c;
+			bords[c].s_next=n-1;
+		}
+		
+                }*/
+    return n - 1;
+}
+
+/**
+ * Add a coverage portion by appending boundaries at the end of the list.
+ *
+ * This works because we know they are on the right.
+ */
+int FloatLigne::AppendBord(float spos, float sval, float epos, float eval, float pente)
+{
+//  if ( showCopy ) printf("b= %f %f -> %f %f \n",spos,sval,epos,eval);
+//	return AddBord(spos,sval,epos,eval,pente,s_last);
+    if ( spos >= epos ) {
+        return -1;
+    }
+    
+#ifdef faster_flatten
+    if ( std::abs(epos - spos) < 0.001 || std::abs(pente) > 1000 ) {
+        return -1;
+        epos = spos;
+        pente = 0;
+    }
+#endif
+    
+    int n = bords.size();
+    float_ligne_bord b;
+    b.pos = spos;
+    b.val = sval;
+    b.start = true;
+    b.other = n + 1;
+    b.pente = pente;
+    b.s_prev = s_last;
+    b.s_next = n + 1;
+    bords.push_back(b);
+ 
+    if ( s_last >=  0 ) {
+        bords[s_last].s_next = n;
+    }
+    
+    if ( s_first < 0 ) {
+        s_first = n;
+    }
+
+    n = bords.size();
+    b.pos = epos;
+    b.val = eval;
+    b.start = false;
+    b.other = n - 1;
+    b.pente = pente;
+    b.s_prev = n - 1;
+    b.s_next = -1;
+    bords.push_back(b);
+
+    s_last = n;
+
+    return n;
+}
+
+
+
+// insertion in a boubly-linked list. nothing interesting here
+void FloatLigne::InsertBord(int no, float /*p*/, int guess)
+{
+// TODO check if ignoring p is bad
+    if ( no < 0 || no >= int(bords.size()) ) {
+        return;
+    }
+    
+    if ( s_first < 0 ) {
+        s_first = s_last = no;
+        bords[no].s_prev = -1;
+        bords[no].s_next = -1;
+        return;
+    }
+    
+    if ( guess < 0 || guess >= int(bords.size()) ) {
+        int c = s_first;
+        while ( c >= 0 && c < int(bords.size()) && CmpBord(bords[c], bords[no]) < 0 ) {
+            c = bords[c].s_next;
+        }
+        
+        if ( c < 0 || c >= int(bords.size()) ) {
+            bords[no].s_prev = s_last;
+            bords[s_last].s_next = no;
+            s_last = no;
+        } else {
+            bords[no].s_prev = bords[c].s_prev;
+            if ( bords[no].s_prev >= 0 ) {
+                bords[bords[no].s_prev].s_next = no;
+            } else {
+                s_first = no;
+            }
+            bords[no].s_next = c;
+            bords[c].s_prev = no;
+        }
+    } else {
+        int c = guess;
+        int stTst = CmpBord(bords[c], bords[no]);
+
+        if ( stTst == 0 ) {
+
+            bords[no].s_prev = bords[c].s_prev;
+            if ( bords[no].s_prev >= 0 ) {
+                bords[bords[no].s_prev].s_next = no;
+            } else {
+                s_first = no;
+            }
+            bords[no].s_next = c;
+            bords[c].s_prev = no;
+            
+        } else if ( stTst > 0 ) {
+            
+            while ( c >= 0 && c < int(bords.size()) && CmpBord(bords[c], bords[no]) > 0 ) {
+                c = bords[c].s_prev;
+            }
+            
+            if ( c < 0 || c >= int(bords.size()) ) {
+                bords[no].s_next = s_first;
+                bords[s_first].s_prev =no; // s_first != -1
+                s_first = no; 
+            } else {
+                bords[no].s_next = bords[c].s_next;
+                if ( bords[no].s_next >= 0 ) {
+                    bords[bords[no].s_next].s_prev = no;
+                } else {
+                    s_last = no;
+                }
+                bords[no].s_prev = c;
+                bords[c].s_next = no;
+            }
+            
+        } else {
+
+            while ( c >= 0 && c < int(bords.size()) && CmpBord(bords[c],bords[no]) < 0 ) {
+                c = bords[c].s_next;
+            }
+            
+            if ( c < 0 || c >= int(bords.size()) ) {
+                bords[no].s_prev = s_last;
+                bords[s_last].s_next = no;
+                s_last = no;
+            } else {
+                bords[no].s_prev = bords[c].s_prev;
+                if ( bords[no].s_prev >= 0 ) {
+                    bords[bords[no].s_prev].s_next = no;
+                } else {
+                    s_first = no;
+                }
+                bords[no].s_next = c;
+                bords[c].s_prev = no;
+            }
+        }
+    }
+}
+
+/**
+ * Computes the sum of the coverages of the runs currently being scanned, 
+ * of which there are "pending".
+ */
+float FloatLigne::RemainingValAt(float at, int pending)
+{
+    float sum = 0;
+/*	int     no=firstAc;
+	while ( no >= 0 && no < bords.size() ) {
+		int   nn=bords[no].other;
+		sum+=bords[nn].val+(at-bords[nn].pos)*bords[nn].pente;
+//				sum+=((at-bords[nn].pos)*bords[no].val+(bords[no].pos-at)*bords[nn].val)/(bords[no].pos-bords[nn].pos);
+//		sum+=ValAt(at,bords[nn].pos,bords[no].pos,bords[nn].val,bords[no].val);
+		no=bords[no].next;
+	}*/
+  // for each portion being scanned, compute coverage at position "at" and sum.
+  // we could simply compute the sum of portion coverages as a "f(x)=ux+y" and evaluate it at "x=at",
+  // but there are numerical problems with this approach, and it produces ugly lines of incorrectly 
+  // computed alpha values, so i reverted to this "safe but slow" version
+    
+    for (int i=0; i < pending; i++) {
+        int const nn = bords[i].pend_ind;
+        sum += bords[nn].val + (at - bords[nn].pos) * bords[nn].pente;
+    }
+    
+    return sum;
+}
+
+
+/**
+ * Extract a set of non-overlapping runs from the boundaries.
+ *
+ * We scan the boundaries left to right, maintaining a set of coverage 
+ * portions currently being scanned. For each such portion, the function 
+ * will add the index of its first boundary in an array; but instead of 
+ * allocating another array, it uses a field in float_ligne_bord: pend_ind.
+ * The outcome is that an array of float_ligne_run is produced.
+ */
+void FloatLigne::Flatten()
+{
+    if ( int(bords.size()) <= 1 ) {
+        Reset();
+        return;
+    }
+    
+    runs.clear();
+
+//	qsort(bords,bords.size(),sizeof(float_ligne_bord),FloatLigne::CmpBord);
+//	SortBords(0,bords.size()-1);
+  
+    float totPente = 0;
+    float totStart = 0;
+    float totX = bords[0].pos;
+    
+    bool startExists = false;
+    float lastStart = 0;
+    float lastVal = 0;
+    int pending = 0;
+    
+//	for (int i=0;i<bords.size();) {
+    // read the list from left to right, adding a run for each boundary crossed, minus runs with alpha=0
+    for (int i=/*0*/s_first; i>=0 && i < int(bords.size()) ;) {
+        
+        float cur = bords[i].pos;  // position of the current boundary (there may be several boundaries at this position)
+        float leftV = 0;  // deltas in coverage value at this position
+        float rightV = 0;
+        float leftP = 0; // deltas in coverage increase per unit length at this position
+        float rightP = 0;
+        
+        // more precisely, leftV is the sum of decreases of coverage value,
+        // while rightV is the sum of increases, so that leftV+rightV is the delta.
+        // idem for leftP and rightP
+    
+        // start by scanning all boundaries that end a portion at this position
+        while ( i >= 0 && i < int(bords.size()) && bords[i].pos == cur && bords[i].start == false ) {
+            leftV += bords[i].val;
+            leftP += bords[i].pente;
+            
+#ifndef faster_flatten
+            // we need to remove the boundary that started this coverage portion for the pending list
+            if ( bords[i].other >= 0 && bords[i].other < int(bords.size()) ) {
+                // so we use the pend_inv "array"
+                int const k = bords[bords[i].other].pend_inv;
+                if ( k >= 0 && k < pending ) {
+                    // and update the pend_ind array and its inverse pend_inv
+                    bords[k].pend_ind = bords[pending - 1].pend_ind;
+                    bords[bords[k].pend_ind].pend_inv = k;
+                }
+            }
+#endif
+            
+            // one less portion pending
+            pending--;
+            // and we move to the next boundary in the doubly linked list
+            i=bords[i].s_next;
+            //i++;
+        }
+        
+        // then scan all boundaries that start a portion at this position
+        while ( i >= 0 && i < int(bords.size()) && bords[i].pos == cur && bords[i].start ) {
+            rightV += bords[i].val;
+            rightP += bords[i].pente;
+#ifndef faster_flatten
+            bords[pending].pend_ind=i;
+            bords[i].pend_inv=pending;
+#endif
+            pending++;
+            i = bords[i].s_next;
+            //i++;
+        }
+
+        // coverage value at end of the run will be "start coverage"+"delta per unit length"*"length"
+        totStart = totStart + totPente * (cur - totX);
+    
+        if ( startExists ) {
+            // add that run
+            AddRun(lastStart, cur, lastVal, totStart, totPente);
+        }
+        // update "delta coverage per unit length"
+        totPente += rightP - leftP;
+        // not really needed here
+        totStart += rightV - leftV;
+        // update position
+        totX = cur;
+        if ( pending > 0 ) {
+            startExists = true;
+            
+#ifndef faster_flatten
+            // to avoid accumulation of numerical errors, we compute an accurate coverage for this position "cur"
+            totStart = RemainingValAt(cur, pending);
+#endif
+            lastVal = totStart;
+            lastStart = cur;
+        } else {
+            startExists = false;
+            totStart = 0;
+            totPente = 0;
+        }
+    }
+}
+
+
+/// Debug dump of the instance.
+void FloatLigne::Affiche()
+{
+    printf("%lu : \n", (long unsigned int) bords.size());
+    for (auto & bord : bords) {
+        printf("(%f %f %f %i) ",bord.pos,bord.val,bord.pente,(bord.start?1:0)); // localization ok
+    }
+    
+    printf("\n");
+    printf("%lu : \n", (long unsigned int) runs.size());
+    
+    for (auto & run : runs) {
+        printf("(%f %f -> %f %f / %f)",
+               run.st, run.vst, run.en, run.ven, run.pente); // localization ok
+    }
+    
+    printf("\n");
+}
+
+
+int FloatLigne::AddRun(float st, float en, float vst, float ven)
+{
+    return AddRun(st, en, vst, ven, (ven - vst) / (en - st));
+}
+
+
+int FloatLigne::AddRun(float st, float en, float vst, float ven, float pente)
+{
+    if ( st >= en ) {
+        return -1;
+    }
+
+    int const n = runs.size();
+    float_ligne_run r;
+    r.st = st;
+    r.en = en;
+    r.vst = vst;
+    r.ven = ven;
+    r.pente = pente;
+    runs.push_back(r);
+    
+    return n;
+}
+
+void FloatLigne::Copy(FloatLigne *a)
+{
+    if ( a->runs.empty() ) {
+        Reset();
+        return;
+    }
+    
+    bords.clear();
+    runs = a->runs;
+}
+
+void FloatLigne::Copy(IntLigne *a)
+{
+    if ( a->nbRun ) {
+        Reset();
+        return;
+    }
+    
+    bords.clear();
+    runs.resize(a->nbRun);
+    
+    for (int i = 0; i < int(runs.size()); i++) {
+        runs[i].st = a->runs[i].st;
+        runs[i].en = a->runs[i].en;
+        runs[i].vst = a->runs[i].vst;
+        runs[i].ven = a->runs[i].ven;
+    }
+}
+
+/// Cuts the parts having less than tresh coverage.
+void FloatLigne::Min(FloatLigne *a, float tresh, bool addIt)
+{
+    Reset();
+    if ( a->runs.empty() ) {
+        return;
+    }
+
+    bool startExists = false;
+    float lastStart=0;
+    float lastEnd = 0;
+    
+    for (auto runA : a->runs) {
+        if ( runA.vst <= tresh ) {
+            if ( runA.ven <= tresh ) {
+                if ( startExists ) {
+                    if ( lastEnd >= runA.st - 0.00001 ) {
+                        lastEnd = runA.en;
+                    } else {
+                        if ( addIt ) {
+                            AddRun(lastStart, lastEnd, tresh, tresh);
+                        }
+                        lastStart = runA.st;
+                        lastEnd = runA.en;
+                    }
+                } else {
+                    lastStart = runA.st;
+                    lastEnd = runA.en;
+                }
+                startExists = true;
+            } else {
+                float cutPos = (runA.st * (tresh - runA.ven) + runA.en * (runA.vst - tresh)) / (runA.vst - runA.ven);
+                if ( startExists ) {
+                    if ( lastEnd >= runA.st - 0.00001 ) {
+                        if ( addIt ) {
+                            AddRun(lastStart, cutPos, tresh, tresh);
+                        }
+                        AddRun(cutPos,runA.en, tresh, runA.ven);
+                    } else {
+                        if ( addIt ) {
+                            AddRun(lastStart, lastEnd, tresh, tresh);
+                        }
+                        if ( addIt ) {
+                            AddRun(runA.st, cutPos, tresh, tresh);
+                        }
+                        AddRun(cutPos, runA.en, tresh, runA.ven);
+                    }
+                } else {
+                    if ( addIt ) {
+                        AddRun(runA.st, cutPos, tresh, tresh);
+                    }
+                    AddRun(cutPos, runA.en, tresh, runA.ven);
+                }
+                startExists = false;
+            }
+            
+        } else {
+            
+            if ( runA.ven <= tresh ) {
+                float cutPos = (runA.st * (runA.ven - tresh) + runA.en * (tresh - runA.vst)) / (runA.ven - runA.vst);
+                if ( startExists ) {
+                    if ( addIt ) {
+                        AddRun(lastStart, lastEnd, tresh, tresh);
+                    }
+                }
+                AddRun(runA.st, cutPos, runA.vst, tresh);
+                startExists = true;
+                lastStart = cutPos;
+                lastEnd = runA.en;
+            } else {
+                if ( startExists ) {
+                    if ( addIt ) {
+                        AddRun(lastStart, lastEnd, tresh, tresh);
+                    }
+                }
+                startExists = false;
+                AddRun(runA.st, runA.en, runA.vst, runA.ven);
+            }
+        }
+    }
+    
+    if ( startExists ) {
+        if ( addIt ) {
+            AddRun(lastStart, lastEnd, tresh, tresh);
+        }
+    }
+}
+
+/** 
+ * Cuts the coverage a in 2 parts.
+ *
+ * over will receive the parts where coverage > tresh, while the present
+ * FloatLigne will receive the parts where coverage <= tresh.
+ */
+void FloatLigne::Split(FloatLigne *a, float tresh, FloatLigne *over)
+{
+    Reset();
+    if ( a->runs.empty() ) {
+        return;
+    }
+
+    for (auto runA : a->runs) {
+        if ( runA.vst >= tresh ) {
+            if ( runA.ven >= tresh ) {
+                if ( over ) {
+                    over->AddRun(runA.st, runA.en, runA.vst, runA.ven);
+                }
+            } else {
+                float cutPos = (runA.st * (tresh - runA.ven) + runA.en * (runA.vst - tresh)) / (runA.vst - runA.ven);
+                if ( over ) {
+                    over->AddRun(runA.st, cutPos, runA.vst, tresh);
+                }
+                AddRun(cutPos, runA.en, tresh, runA.ven);
+            }
+        } else {
+            if ( runA.ven >= tresh ) {
+                float cutPos = (runA.st * (runA.ven - tresh) + runA.en * (tresh-runA.vst)) / (runA.ven - runA.vst);
+                AddRun(runA.st, cutPos, runA.vst, tresh);
+                if ( over ) {
+                    over->AddRun(cutPos, runA.en, tresh, runA.ven);
+                }
+            } else {
+                AddRun(runA.st, runA.en, runA.vst, runA.ven);
+            }
+        }
+    }
+}
+
+/** 
+ * Clips the coverage runs to tresh.
+ *
+ * If addIt is false, it only leaves the parts that are not entirely under 
+ * tresh. If addIt is true, it's the coverage clamped to tresh.
+ */
+void FloatLigne::Max(FloatLigne *a, float tresh, bool addIt)
+{
+    Reset();
+    if ( a->runs.empty() <= 0 ) {
+        return;
+    }
+
+    bool startExists = false;
+    float lastStart = 0;
+    float lastEnd = 0;
+    for (auto runA : a->runs) {
+        if ( runA.vst >= tresh ) {
+            if ( runA.ven >= tresh ) {
+                if ( startExists ) {
+                    if ( lastEnd >= runA.st-0.00001 ) {
+                        lastEnd = runA.en;
+                    } else {
+                        if ( addIt ) {
+                            AddRun(lastStart,lastEnd,tresh,tresh);
+                        }
+                        lastStart = runA.st;
+                        lastEnd = runA.en;
+                    }
+                } else {
+                    lastStart = runA.st;
+                    lastEnd = runA.en;
+                }
+                startExists = true;
+            } else {
+                float cutPos = (runA.st * (tresh - runA.ven) + runA.en * (runA.vst - tresh)) / (runA.vst - runA.ven);
+                if ( startExists ) {
+                    if ( lastEnd >= runA.st-0.00001 ) {
+                        if ( addIt ) {
+                            AddRun(lastStart, cutPos, tresh, tresh);
+                        }
+                        AddRun(cutPos, runA.en, tresh, runA.ven);
+                    } else {
+                        if ( addIt ) {
+                            AddRun(lastStart, lastEnd, tresh, tresh);
+                        }
+                        if ( addIt ) {
+                            AddRun(runA.st, cutPos, tresh, tresh);
+                        }
+                        AddRun(cutPos, runA.en, tresh, runA.ven);
+                    }
+                } else {
+                    if ( addIt ) {
+                        AddRun(runA.st, cutPos, tresh, tresh);
+                    }
+                    AddRun(cutPos, runA.en, tresh, runA.ven);
+                }
+                startExists = false;
+            }
+            
+        } else {
+            
+            if ( runA.ven >= tresh ) {
+                float cutPos = (runA.st * (runA.ven - tresh) + runA.en * (tresh - runA.vst)) / (runA.ven - runA.vst);
+                if ( startExists ) {
+                    if ( addIt ) {
+                        AddRun(lastStart,lastEnd,tresh,tresh);
+                    }
+                }
+                AddRun(runA.st, cutPos, runA.vst, tresh);
+                startExists = true;
+                lastStart = cutPos;
+                lastEnd = runA.en;
+            } else {
+                if ( startExists ) {
+                    if ( addIt ) {
+                        AddRun(lastStart,lastEnd,tresh,tresh);
+                    }
+                }
+                startExists = false;
+                AddRun(runA.st, runA.en, runA.vst, runA.ven);
+            }
+        }
+    }
+    
+    if ( startExists ) {
+        if ( addIt ) {
+            AddRun(lastStart, lastEnd, tresh, tresh);
+        }
+    }
+}
+
+/// Extract the parts where coverage > tresh.
+void FloatLigne::Over(FloatLigne *a, float tresh)
+{
+    Reset();
+    if ( a->runs.empty() ) {
+        return;
+    }
+
+    bool startExists = false;
+    float lastStart = 0;
+    float lastEnd = 0;
+    
+    for (auto runA : a->runs) {
+        if ( runA.vst >= tresh ) {
+            if ( runA.ven >= tresh ) {
+                if ( startExists ) {
+                    if ( lastEnd >= runA.st - 0.00001 ) {
+                        lastEnd = runA.en;
+                    } else {
+                        AddRun(lastStart, lastEnd, tresh, tresh);
+                        lastStart = runA.st;
+                        lastEnd = runA.en;
+                    }
+                } else {
+                    lastStart = runA.st;
+                    lastEnd = runA.en;
+                }
+                startExists = true;
+                
+            } else {
+                
+                float cutPos = (runA.st * (tresh - runA.ven) + runA.en * (runA.vst - tresh)) / (runA.vst - runA.ven);
+                if ( startExists ) {
+                    if ( lastEnd >= runA.st - 0.00001 ) {
+                        AddRun(lastStart, cutPos, tresh, tresh);
+                    } else {
+                        AddRun(lastStart, lastEnd, tresh, tresh);
+                        AddRun(runA.st, cutPos, tresh, tresh);
+                    }
+                } else {
+                    AddRun(runA.st, cutPos, tresh, tresh);
+                }
+                startExists = false;
+            }
+            
+        } else {
+            if ( runA.ven >= tresh ) {
+                float cutPos = (runA.st * (runA.ven - tresh) + runA.en * (tresh - runA.vst)) / (runA.ven - runA.vst);
+                if ( startExists ) {
+                    AddRun(lastStart, lastEnd, tresh, tresh);
+                }
+                startExists = true;
+                lastStart = cutPos;
+                lastEnd = runA.en;
+            } else {
+                if ( startExists ) {
+                    AddRun(lastStart, lastEnd, tresh, tresh);
+                }
+                startExists = false;
+            }
+        }
+    }
+    
+    if ( startExists ) {
+        AddRun(lastStart, lastEnd, tresh, tresh);
+    }
+}
+
+
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :