1 files changed, 108 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..f0fb479
--- /dev/null
+++ b/src/livarot/sweep-event-queue.h
@@ -0,0 +1,108 @@
+// 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();
+
+    /**
+     * Number of events currently stored.
+     *
+     * @return The number of elements stored.
+     */
+    int size() const { return nbEvt; }
+
+    /** Look for the top most intersection in the heap
+     *
+     * @param iLeft Reference that function will set to the left node of top most intersection.
+     * @param iRight Reference that function will set to the right node of top most intersection.
+     * @param oPt Reference that function will set to the intersection point of top most intersection.
+     * @param itl Reference that function will set to time of top most intersection on the left edge.
+     * @param itr Reference that function will set to time of top most intersection on the right edge.
+     *
+     * @return True if an intersection event exists false otherwise.
+     */
+    bool peek(SweepTree * &iLeft, SweepTree * &iRight, Geom::Point &oPt, double &itl, double &itr);
+
+    /** Extract the top most intersection from the heap
+     *
+     * @param iLeft Reference that function will set to the left node of top most intersection.
+     * @param iRight Reference that function will set to the right node of top most intersection.
+     * @param oPt Reference that function will set to the point of top most intersection.
+     * @param itl Reference that function will set to time of top most intersection on the left edge.
+     * @param itr Reference that function will set to time of top most intersection on the right edge.
+     *
+     * @return True if an intersection event exists false otherwise.
+     */
+    bool extract(SweepTree * &iLeft, SweepTree * &iRight, Geom::Point &oPt, double &itl, double &itr);
+
+    /** Add an intersection in the binary heap
+     *
+     * @param iLeft Pointer to left node of intersection.
+     * @param iRight Pointer to right node of intersection.
+     * @param iPt Point of intersection.
+     * @param itl Time of intersection on the left edge.
+     * @param itr Time of intersection on the right edge.
+     */
+    SweepEvent *add(SweepTree *iLeft, SweepTree *iRight, Geom::Point &iPt, double itl, double itr);
+
+    /**
+     * Remove event from the event queue. Make sure to clear the evt pointers from the nodes
+     * involved.
+     *
+     * @param e The event to remove.
+     */
+    void remove(SweepEvent *e);
+
+    /**
+     * Relocate the event `e` to the location to.
+     *
+     * This will place all data of `e` in `to` and also update any
+     * evt pointers held by the intersection nodes.
+     *
+     * @param e The SweepEvent to relocate.
+     * @param to The index of the location where we want to relocate `e` to.
+     */
+    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 :