1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
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 :
|
