diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 18:24:48 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 18:24:48 +0000 |
commit | cca66b9ec4e494c1d919bff0f71a820d8afab1fa (patch) | |
tree | 146f39ded1c938019e1ed42d30923c2ac9e86789 /src/livarot/sweep-event-queue.h | |
parent | Initial commit. (diff) | |
download | inkscape-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 '')
-rw-r--r-- | src/livarot/sweep-event-queue.h | 60 |
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 : |