1 // SPDX-License-Identifier: GPL-2.0-or-later 2 /** @file 3 * A container of intersection events. 4 *//* 5 * Authors: see git history 6 * 7 * Copyright (C) 2010 Authors 8 * Released under GNU GPL v2+, read the file 'COPYING' for more information. 9 */ 10 #ifndef SEEN_LIVAROT_SWEEP_EVENT_QUEUE_H 11 #define SEEN_LIVAROT_SWEEP_EVENT_QUEUE_H 12 13 #include <2geom/forward.h> 14 class SweepEvent; 15 class SweepTree; 16 17 18 /** 19 * The structure to hold the intersections events encountered during the sweep. It's an array of 20 * SweepEvent (not allocated with "new SweepEvent[n]" but with a malloc). There's a list of 21 * indices because it's a binary heap: inds[i] tell that events[inds[i]] has position i in the 22 * heap. Each SweepEvent has a field to store its index in the heap, too. 23 */ 24 class SweepEventQueue 25 { 26 public: 27 SweepEventQueue(int s); 28 virtual ~SweepEventQueue(); 29 size()30 int size() const { return nbEvt; } 31 32 /// Look for the topmost intersection in the heap 33 bool peek(SweepTree * &iLeft, SweepTree * &iRight, Geom::Point &oPt, double &itl, double &itr); 34 /// Extract the topmost intersection from the heap 35 bool extract(SweepTree * &iLeft, SweepTree * &iRight, Geom::Point &oPt, double &itl, double &itr); 36 /// Add one intersection in the binary heap 37 SweepEvent *add(SweepTree *iLeft, SweepTree *iRight, Geom::Point &iPt, double itl, double itr); 38 39 void remove(SweepEvent *e); 40 void relocate(SweepEvent *e, int to); 41 42 private: 43 int nbEvt; ///< Number of events currently in the heap. 44 int maxEvt; ///< Allocated size of the heap. 45 int *inds; ///< Indices. 46 SweepEvent *events; ///< Sweep events. 47 }; 48 49 #endif /* !SEEN_LIVAROT_SWEEP_EVENT_QUEUE_H */ 50 51 /* 52 Local Variables: 53 mode:c++ 54 c-file-style:"stroustrup" 55 c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) 56 indent-tabs-mode:nil 57 fill-column:99 58 End: 59 */ 60 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 : 61