summaryrefslogtreecommitdiffstats
path: root/src/livarot/sweep-event-queue.h
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-07 18:24:48 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-07 18:24:48 +0000
commitcca66b9ec4e494c1d919bff0f71a820d8afab1fa (patch)
tree146f39ded1c938019e1ed42d30923c2ac9e86789 /src/livarot/sweep-event-queue.h
parentInitial commit. (diff)
downloadinkscape-cca66b9ec4e494c1d919bff0f71a820d8afab1fa.tar.xz
inkscape-cca66b9ec4e494c1d919bff0f71a820d8afab1fa.zip
Adding upstream version 1.2.2.upstream/1.2.2upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'src/livarot/sweep-event-queue.h')
-rw-r--r--src/livarot/sweep-event-queue.h60
1 files changed, 60 insertions, 0 deletions
diff --git a/src/livarot/sweep-event-queue.h b/src/livarot/sweep-event-queue.h
new file mode 100644
index 0000000..759727a
--- /dev/null
+++ b/src/livarot/sweep-event-queue.h
@@ -0,0 +1,60 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/** @file
+ * A container of intersection events.
+ *//*
+ * Authors: see git history
+ *
+ * Copyright (C) 2010 Authors
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+#ifndef SEEN_LIVAROT_SWEEP_EVENT_QUEUE_H
+#define SEEN_LIVAROT_SWEEP_EVENT_QUEUE_H
+
+#include <2geom/forward.h>
+class SweepEvent;
+class SweepTree;
+
+
+/**
+ * The structure to hold the intersections events encountered during the sweep. It's an array of
+ * SweepEvent (not allocated with "new SweepEvent[n]" but with a malloc). There's a list of
+ * indices because it's a binary heap: inds[i] tell that events[inds[i]] has position i in the
+ * heap. Each SweepEvent has a field to store its index in the heap, too.
+ */
+class SweepEventQueue
+{
+public:
+ SweepEventQueue(int s);
+ virtual ~SweepEventQueue();
+
+ int size() const { return nbEvt; }
+
+ /// Look for the topmost intersection in the heap
+ bool peek(SweepTree * &iLeft, SweepTree * &iRight, Geom::Point &oPt, double &itl, double &itr);
+ /// Extract the topmost intersection from the heap
+ bool extract(SweepTree * &iLeft, SweepTree * &iRight, Geom::Point &oPt, double &itl, double &itr);
+ /// Add one intersection in the binary heap
+ SweepEvent *add(SweepTree *iLeft, SweepTree *iRight, Geom::Point &iPt, double itl, double itr);
+
+ void remove(SweepEvent *e);
+ void relocate(SweepEvent *e, int to);
+
+private:
+ int nbEvt; ///< Number of events currently in the heap.
+ int maxEvt; ///< Allocated size of the heap.
+ int *inds; ///< Indices.
+ SweepEvent *events; ///< Sweep events.
+};
+
+#endif /* !SEEN_LIVAROT_SWEEP_EVENT_QUEUE_H */
+
+/*
+ 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 :