1 // Copyright 2023 Google LLC
2 // Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
3
4 #include "modules/bentleyottmann/include/EventQueue.h"
5 #include "tests/Test.h"
6
7 namespace bentleyottmann {
8 class EventQueueTestingPeer {
9 public:
NextEvent(EventQueue * eq)10 static Event NextEvent(EventQueue* eq) {
11 SkASSERT(eq->hasMoreEvents());
12
13 auto firstElement = eq->fQueue.begin();
14
15 // Extract event at the beginning of the queue.
16 Event event = *firstElement;
17
18 // Remove the beginning element from the queue.
19 eq->fQueue.erase(firstElement);
20
21 return event;
22 }
23 };
24 } // namespace bentleyottmann
25
26 using namespace bentleyottmann;
27
DEF_TEST(BO_EventQueueOrdering,reporter)28 DEF_TEST(BO_EventQueueOrdering, reporter) {
29 { // Check that event types are ordered correctly.
30 EventQueue::Queue q;
31
32 // Insert the events in reverse order.
33 Point eventPoint = {100, 100};
34 Segment s = {{100, 100}, {200, 200}};
35 q.insert(Event{eventPoint, Upper{s}});
36 Segment s0 = {{50, 50}, {150, 150}},
37 s1 = {{150, 50}, {50, 150}};
38 q.insert(Event{eventPoint, Cross{s0, s1}});
39 q.insert(Event{eventPoint, Lower{}});
40
41 // Make sure that the events are in the right order.
42 auto cursor = q.begin();
43 REPORTER_ASSERT(reporter, std::holds_alternative<Lower>(cursor->type));
44 ++cursor;
45 REPORTER_ASSERT(reporter, std::holds_alternative<Cross>(cursor->type));
46 ++cursor;
47 REPORTER_ASSERT(reporter, std::holds_alternative<Upper>(cursor->type));
48 }
49 }
50
DEF_TEST(BO_EventQueueBasic,reporter)51 DEF_TEST(BO_EventQueueBasic, reporter) {
52 {
53 EventQueue::Queue q;
54 EventQueue eq{std::move(q)};
55 REPORTER_ASSERT(reporter, !eq.hasMoreEvents());
56 }
57 {
58 EventQueue::Queue q;
59 Point eventPoint = {100, 100};
60 q.insert({eventPoint, Lower{} });
61 EventQueue eq{std::move(q)};
62 {
63 REPORTER_ASSERT(reporter, eq.hasMoreEvents());
64 Event e = EventQueueTestingPeer::NextEvent(&eq);
65 REPORTER_ASSERT(reporter, e.where == eventPoint);
66 REPORTER_ASSERT(reporter, !eq.hasMoreEvents());
67 }
68 }
69 { // Check that Lower events are de-duplicated.
70 EventQueue::Queue q;
71 Point eventPoint = {100, 100};
72 q.insert({eventPoint, Lower{}});
73 q.insert({eventPoint, Lower{}});
74 EventQueue eq{std::move(q)};
75 {
76 // There should be only one lower because of queue de-duplication
77 REPORTER_ASSERT(reporter, eq.hasMoreEvents());
78 auto [p, _] = EventQueueTestingPeer::NextEvent(&eq);
79 REPORTER_ASSERT(reporter, p == eventPoint);
80 REPORTER_ASSERT(reporter, !eq.hasMoreEvents());
81 }
82 }
83 { // Check that Lower distinct Lower events are distinct.
84 EventQueue::Queue q;
85 Point eventPoint1 = {100, 100};
86 Point eventPoint2 = {100, 101};
87
88 q.insert({eventPoint1, Lower{}});
89 q.insert({eventPoint2, Lower{}});
90 EventQueue eq{std::move(q)};
91 {
92 // There should be only one lower because of queue de-duplication
93 REPORTER_ASSERT(reporter, eq.hasMoreEvents());
94 auto [p, _] = EventQueueTestingPeer::NextEvent(&eq);
95 REPORTER_ASSERT(reporter, p == eventPoint1);
96 }
97 {
98 // There should be only one lower because of queue de-duplication
99 REPORTER_ASSERT(reporter, eq.hasMoreEvents());
100 auto [p, _] = EventQueueTestingPeer::NextEvent(&eq);
101 REPORTER_ASSERT(reporter, p == eventPoint2);
102 REPORTER_ASSERT(reporter, !eq.hasMoreEvents());
103 }
104 }
105 { // Check that non-Lower events are separate.
106 EventQueue::Queue q;
107 Segment s0 {{0, 0}, {100, 100}};
108 Segment s1 {{0, 0}, {-100, 100}};
109 q.insert({Point{0, 0}, Upper{s0}});
110 q.insert({Point{0, 0}, Upper{s1}});
111 EventQueue eq{std::move(q)};
112 {
113 REPORTER_ASSERT(reporter, eq.hasMoreEvents());
114 Event e = EventQueueTestingPeer::NextEvent(&eq);
115 Point upperPt = Point{0, 0};
116 REPORTER_ASSERT(reporter, e.where == upperPt);
117 REPORTER_ASSERT(reporter, e.type.index() == 2);
118 Upper upper = std::get<Upper>(e.type);
119 REPORTER_ASSERT(reporter, !(upper < Upper{s1}) && !(Upper{s1} < upper));
120 Event e2 = EventQueueTestingPeer::NextEvent(&eq);
121 REPORTER_ASSERT(reporter, e2.where == upperPt);
122 REPORTER_ASSERT(reporter, e2.type.index() == 2);
123 Upper upper2 = std::get<Upper>(e2.type);
124 REPORTER_ASSERT(reporter, !(upper2 < Upper{s0}) && !(Upper{s0} < upper2));
125 REPORTER_ASSERT(reporter, !eq.hasMoreEvents());
126 }
127 }
128 }
129
130 enum HasDeletions {
131 kHasDeletions, // The handleDeletions call should be called.
132 kHasNoDeletions // The handleDeletions call should not be called.
133 };
134
135 struct TestEventHandler : public SweepLineInterface {
TestEventHandlerTestEventHandler136 TestEventHandler(skiatest::Reporter*r,
137 Point eventPoint,
138 SkSpan<const Segment> deletions,
139 SkSpan<const Segment> insertions,
140 SkSpan<const Crossing> crossings,
141 HasDeletions hasDeletions = kHasDeletions)
142 : fR(r)
143 , fCandidateEventPoint{eventPoint}
144 , fDeletions{deletions.begin(), deletions.end()}
145 , fInsertions{insertions.begin(), insertions.end()}
146 , fCrossings{crossings.begin(), crossings.end()}
147 , fHasDeletions{hasDeletions} {}
148
handleDeletionsTestEventHandler149 void handleDeletions(Point eventPoint,
150 const DeletionSegmentSet& removing) override {
151 if (fHasDeletions == kHasNoDeletions) {
152 REPORTER_ASSERT(fR, false, "There should be no deletions.");
153 return;
154 }
155
156 REPORTER_ASSERT(fR, eventPoint == fCandidateEventPoint);
157
158 REPORTER_ASSERT(fR, removing.size() == fDeletions.size());
159
160 for (const Segment& s : fDeletions) {
161 REPORTER_ASSERT(fR, removing.find(s) != removing.end());
162 }
163 }
164
165 void
handleInsertionsAndCheckForNewCrossingsTestEventHandler166 handleInsertionsAndCheckForNewCrossings(Point eventPoint,
167 const InsertionSegmentSet& inserting,
168 EventQueueInterface* queue) override {
169 REPORTER_ASSERT(fR, eventPoint == fCandidateEventPoint);
170
171 REPORTER_ASSERT(fR, inserting.size() == fInsertions.size());
172
173 for (const Segment& s : fInsertions) {
174 REPORTER_ASSERT(fR, inserting.find(s) != inserting.end());
175 }
176
177 for (const Crossing& crossing : fCrossings) {
178 auto [s0, s1, pt] = crossing;
179 queue->addCrossing(pt, s0, s1);
180 }
181 }
182
183 skiatest::Reporter* const fR;
184 const Point fCandidateEventPoint;
185 std::vector<Segment> fDeletions;
186 std::vector<Segment> fInsertions;
187 std::vector<Crossing> fCrossings;
188 const HasDeletions fHasDeletions;
189 };
190
DEF_TEST(BO_EventQueueHandlerInterface,reporter)191 DEF_TEST(BO_EventQueueHandlerInterface, reporter) {
192 { // Check that a Lower event is added while processing the Upper event.
193 EventQueue::Queue q;
194 static constexpr Point eventPoint = {100, 100};
195 static constexpr Point endPoint = {200, 200};
196 static constexpr Segment s = {eventPoint, endPoint};
197 q.insert(Event{eventPoint, Upper{s}});
198 EventQueue eq{std::move(q)};
199
200 REPORTER_ASSERT(reporter, eq.hasMoreEvents());
201
202
203 TestEventHandler eh1{reporter, eventPoint, {}, {s}, {}, kHasNoDeletions};
204 eq.handleNextEventPoint(&eh1);
205
206 TestEventHandler eh2{reporter, endPoint, {}, {}, {}};
207 eq.handleNextEventPoint(&eh2);
208
209 REPORTER_ASSERT(reporter, !eq.hasMoreEvents());
210 }
211
212 { // Check an entire crossing event.
213 EventQueue::Queue q;
214 static constexpr Point b0 = {100, 100};
215 static constexpr Point e0 = {200, 200};
216 static constexpr Segment s0 = {b0, e0};
217 static constexpr Point b1 = {200, 100};
218 static constexpr Point e1 = {100, 200};
219 static constexpr Segment s1 = {b1, e1};
220 static constexpr Point crossingPoint = {150, 150};
221
222 // Load crossing segments into the queue
223 q.insert(Event{b0, Upper{s0}});
224 q.insert(Event{b1, Upper{s1}});
225 EventQueue eq{std::move(q)};
226
227 REPORTER_ASSERT(reporter, eq.hasMoreEvents());
228
229 TestEventHandler eh1{reporter, b0, {}, {s0}, {}, kHasNoDeletions};
230 eq.handleNextEventPoint(&eh1);
231
232 TestEventHandler eh2{reporter, b1, {}, {s1}, {{s0, s1, crossingPoint}}, kHasNoDeletions};
233 eq.handleNextEventPoint(&eh2);
234
235 TestEventHandler eh3{reporter, crossingPoint, {s0, s1}, {s0, s1}, {}};
236 eq.handleNextEventPoint(&eh3);
237
238 TestEventHandler eh4{reporter, e1, {}, {}, {}};
239 eq.handleNextEventPoint(&eh4);
240
241 TestEventHandler eh5{reporter, e0, {}, {}, {}};
242 eq.handleNextEventPoint(&eh5);
243
244 REPORTER_ASSERT(reporter, !eq.hasMoreEvents());
245 }
246 }
247
248