1 #ifndef SEEN_LIVAROT_SWEEP_EVENT_QUEUE_H
2 #define SEEN_LIVAROT_SWEEP_EVENT_QUEUE_H
3 /** \file
4 * A container of intersection events.
5 */
7 #include <libnr/nr-forward.h>
8 class SweepEvent;
9 class SweepTree;
12 /**
13 * The structure to hold the intersections events encountered during the sweep. It's an array of
14 * SweepEvent (not allocated with "new SweepEvent[n]" but with a malloc). There's a list of
15 * indices because it's a binary heap: inds[i] tell that events[inds[i]] has position i in the
16 * heap. Each SweepEvent has a field to store its index in the heap, too.
17 */
18 class SweepEventQueue
19 {
20 public:
21 SweepEventQueue(int s);
22 ~SweepEventQueue();
24 int size() const { return nbEvt; }
26 /// Look for the topmost intersection in the heap
27 bool peek(SweepTree * &iLeft, SweepTree * &iRight, NR::Point &oPt, double &itl, double &itr);
28 /// Extract the topmost intersection from the heap
29 bool extract(SweepTree * &iLeft, SweepTree * &iRight, NR::Point &oPt, double &itl, double &itr);
30 /// Add one intersection in the binary heap
31 SweepEvent *add(SweepTree *iLeft, SweepTree *iRight, NR::Point &iPt, double itl, double itr);
33 void remove(SweepEvent *e);
34 void relocate(SweepEvent *e, int to);
36 private:
37 int nbEvt; ///< Number of events currently in the heap.
38 int maxEvt; ///< Allocated size of the heap.
39 int *inds; ///< Indices.
40 SweepEvent *events; ///< Sweep events.
41 };
43 #endif /* !SEEN_LIVAROT_SWEEP_EVENT_QUEUE_H */
45 /*
46 Local Variables:
47 mode:c++
48 c-file-style:"stroustrup"
49 c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
50 indent-tabs-mode:nil
51 fill-column:99
52 End:
53 */
54 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :