Adding upstream version 1.2.2.upstream/1.2.2upstream

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

1 files changed, 284 insertions, 0 deletions

diff --git a/src/livarot/sweep-event.cpp b/src/livarot/sweep-event.cpp
new file mode 100644
index 0000000..bb9e4e7
--- /dev/null
+++ b/src/livarot/sweep-event.cpp
@@ -0,0 +1,284 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/** @file
+ * TODO: insert short description here
+ *//*
+ * Authors: see git history
+ *
+ * Copyright (C) 2018 Authors
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+#include <glib.h>
+#include "livarot/sweep-event-queue.h"
+#include "livarot/sweep-tree.h"
+#include "livarot/sweep-event.h"
+#include "livarot/Shape.h"
+
+SweepEventQueue::SweepEventQueue(int s) : nbEvt(0), maxEvt(s)
+{
+    /* FIXME: use new[] for this, but this causes problems when delete[]
+    ** calls the SweepEvent destructors.
+    */
+    events = (SweepEvent *) g_malloc(maxEvt * sizeof(SweepEvent));
+    inds = new int[maxEvt];
+}
+
+SweepEventQueue::~SweepEventQueue()
+{
+    g_free(events);
+    delete []inds;
+}
+
+SweepEvent *SweepEventQueue::add(SweepTree *iLeft, SweepTree *iRight, Geom::Point &px, double itl, double itr)
+{
+    if (nbEvt > maxEvt) {
+	return nullptr;
+    }
+    
+    int const n = nbEvt++;
+    events[n].MakeNew (iLeft, iRight, px, itl, itr);
+
+    SweepTree *t[2] = { iLeft, iRight };
+    for (auto & i : t) {
+        Shape *s = i->src;
+	Shape::dg_arete const &e = s->getEdge(i->bord);
+	int const n = std::max(e.st, e.en);
+	s->pData[n].pending++;;
+    }
+
+    events[n].ind = n;
+    inds[n] = n;
+
+    int curInd = n;
+    while (curInd > 0) {
+	int const half = (curInd - 1) / 2;
+	int const no = inds[half];
+	if (px[1] < events[no].posx[1]
+	    || (px[1] == events[no].posx[1] && px[0] < events[no].posx[0]))
+	{
+	    events[n].ind = half;
+	    events[no].ind = curInd;
+	    inds[half] = n;
+	    inds[curInd] = no;
+	} else {
+	    break;
+	}
+	
+	curInd = half;
+    }
+  
+    return events + n;
+}
+
+
+
+bool SweepEventQueue::peek(SweepTree * &iLeft, SweepTree * &iRight, Geom::Point &px, double &itl, double &itr)
+{
+    if (nbEvt <= 0) {
+	return false;
+    }
+    
+    SweepEvent const &e = events[inds[0]];
+
+    iLeft = e.sweep[LEFT];
+    iRight = e.sweep[RIGHT];
+    px = e.posx;
+    itl = e.tl;
+    itr = e.tr;
+    
+    return true;
+}
+
+bool SweepEventQueue::extract(SweepTree * &iLeft, SweepTree * &iRight, Geom::Point &px, double &itl, double &itr)
+{
+    if (nbEvt <= 0) {
+	return false;
+    }
+
+    SweepEvent &e = events[inds[0]];
+    
+    iLeft = e.sweep[LEFT];
+    iRight = e.sweep[RIGHT];
+    px = e.posx;
+    itl = e.tl;
+    itr = e.tr;
+    remove(&e);
+    
+    return true;
+}
+
+
+void SweepEventQueue::remove(SweepEvent *e)
+{
+    if (nbEvt <= 1) {
+	e->MakeDelete ();
+	nbEvt = 0;
+	return;
+    }
+    
+    int const n = e->ind;
+    int to = inds[n];
+    e->MakeDelete();
+    relocate(&events[--nbEvt], to);
+
+    int const moveInd = nbEvt;
+    if (moveInd == n) {
+	return;
+    }
+    
+    to = inds[moveInd];
+
+    events[to].ind = n;
+    inds[n] = to;
+
+    int curInd = n;
+    Geom::Point const px = events[to].posx;
+    bool didClimb = false;
+    while (curInd > 0) {
+	int const half = (curInd - 1) / 2;
+	int const no = inds[half];
+	if (px[1] < events[no].posx[1]
+	    || (px[1] == events[no].posx[1] && px[0] < events[no].posx[0]))
+	{
+	  events[to].ind = half;
+	  events[no].ind = curInd;
+	  inds[half] = to;
+	  inds[curInd] = no;
+	  didClimb = true;
+	} else {
+	    break;
+	}
+	curInd = half;
+    }
+    
+    if (didClimb) {
+	return;
+    }
+    
+    while (2 * curInd + 1 < nbEvt) {
+	int const child1 = 2 * curInd + 1;
+	int const child2 = child1 + 1;
+	int const no1 = inds[child1];
+	int const no2 = inds[child2];
+	if (child2 < nbEvt) {
+	    if (px[1] > events[no1].posx[1]
+		|| (px[1] == events[no1].posx[1]
+		    && px[0] > events[no1].posx[0]))
+	    {
+		if (events[no2].posx[1] > events[no1].posx[1]
+		    || (events[no2].posx[1] == events[no1].posx[1]
+			&& events[no2].posx[0] > events[no1].posx[0]))
+		{
+		    events[to].ind = child1;
+		    events[no1].ind = curInd;
+		    inds[child1] = to;
+		    inds[curInd] = no1;
+		    curInd = child1;
+		} else {
+		    events[to].ind = child2;
+		    events[no2].ind = curInd;
+		    inds[child2] = to;
+		    inds[curInd] = no2;
+		    curInd = child2;
+		}
+	    } else {
+		if (px[1] > events[no2].posx[1]
+		    || (px[1] == events[no2].posx[1]
+			&& px[0] > events[no2].posx[0]))
+		{
+		    events[to].ind = child2;
+		    events[no2].ind = curInd;
+		    inds[child2] = to;
+		    inds[curInd] = no2;
+		    curInd = child2;
+		} else {
+		    break;
+		}
+	    }
+	} else {
+	    if (px[1] > events[no1].posx[1]
+		|| (px[1] == events[no1].posx[1]
+		    && px[0] > events[no1].posx[0]))
+	    {
+		events[to].ind = child1;
+		events[no1].ind = curInd;
+		inds[child1] = to;
+		inds[curInd] = no1;
+	    }
+	    
+	    break;
+	}
+    }
+}
+
+
+
+
+void SweepEventQueue::relocate(SweepEvent *e, int to)
+{
+    if (inds[e->ind] == to) {
+	return;			// j'y suis deja
+    }
+
+    events[to] = *e;
+
+    e->sweep[LEFT]->evt[RIGHT] = events + to;
+    e->sweep[RIGHT]->evt[LEFT] = events + to;
+    inds[e->ind] = to;
+}
+
+
+/*
+ * a simple binary heap
+ * it only contains intersection events
+ * the regular benley-ottman stuffs the segment ends in it too, but that not needed here since theses points
+ * are already sorted. and the binary heap is much faster with only intersections...
+ * the code sample on which this code is based comes from purists.org
+ */
+SweepEvent::SweepEvent()
+{
+    MakeNew (nullptr, nullptr, Geom::Point(0, 0), 0, 0);
+}
+
+SweepEvent::~SweepEvent()
+{
+    MakeDelete();
+}
+
+void SweepEvent::MakeNew(SweepTree *iLeft, SweepTree *iRight, Geom::Point const &px, double itl, double itr)
+{
+    ind = -1;
+    posx = px;
+    tl = itl;
+    tr = itr;
+    sweep[LEFT] = iLeft;
+    sweep[RIGHT] = iRight;
+    sweep[LEFT]->evt[RIGHT] = this;
+    sweep[RIGHT]->evt[LEFT] = this;
+}
+
+void SweepEvent::MakeDelete()
+{
+    for (int i = 0; i < 2; i++) {
+	if (sweep[i]) {
+	    Shape *s = sweep[i]->src;
+	    Shape::dg_arete const &e = s->getEdge(sweep[i]->bord);
+	    int const n = std::max(e.st, e.en);
+	    s->pData[n].pending--;
+	}
+
+	sweep[i]->evt[1 - i] = nullptr;
+	sweep[i] = nullptr;
+    }
+}
+
+
+/*
+  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 :