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 #ifndef EventQueue_DEFINED 5 #define EventQueue_DEFINED 6 7 #include "include/core/SkSpan.h" 8 #include "modules/bentleyottmann/include/EventQueueInterface.h" 9 #include "modules/bentleyottmann/include/Point.h" 10 #include "modules/bentleyottmann/include/Segment.h" 11 12 #include <optional> 13 #include <set> 14 #include <tuple> 15 #include <variant> 16 #include <vector> 17 18 namespace bentleyottmann { 19 20 struct Lower { 21 // All Lowers are equal. 22 friend bool operator< (const Lower&, const Lower&) { 23 return false; 24 } 25 }; 26 27 struct Upper { 28 Segment s; 29 30 // Arbitrary comparison for queue uniqueness. 31 friend bool operator< (const Upper& u0, const Upper& u1) { 32 return std::tie(u0.s.p0, u0.s.p1) < std::tie(u1.s.p0, u1.s.p1); 33 } 34 }; 35 36 struct Cross { 37 Segment s0; 38 Segment s1; 39 40 // Arbitrary comparison for queue uniqueness. 41 friend bool operator< (const Cross& c0, const Cross& c1) { 42 return std::tie(c0.s0.p0, c0.s0.p1, c0.s1.p0, c0.s1.p1) < 43 std::tie(c1.s0.p0, c1.s0.p1, c1.s1.p0, c1.s1.p1); 44 } 45 }; 46 47 using EventType = std::variant<Lower, Cross, Upper>; 48 49 struct Event { 50 Point where; 51 EventType type; 52 53 friend bool operator< (const Event& e0, const Event& e1) { 54 return std::tie(e0.where, e0.type) < std::tie(e1.where, e1.type); 55 } 56 }; 57 58 class EventQueue : public EventQueueInterface { 59 public: 60 // Queue ordered by Event where the point is the most important followed by type and then 61 // contents of the event. The ordering of the contents of the event is arbitrary but need to 62 // enforce uniqueness of the events in the queue. 63 using Queue = std::set<Event>; 64 65 static std::optional<EventQueue> Make(SkSpan<const Segment> segments); 66 67 EventQueue(Queue&& queue); 68 EventQueue() = default; 69 70 void addCrossing(Point crossingPoint, const Segment& s0, const Segment& s1) override; 71 72 bool hasMoreEvents() const; 73 void handleNextEventPoint(SweepLineInterface* handler); 74 std::vector<Crossing> crossings(); 75 76 private: 77 friend class EventQueueTestingPeer; 78 Point fLastEventPoint = Point::Smallest(); 79 80 void add(const Event& e); 81 82 DeletionSegmentSet fDeletionSet; 83 InsertionSegmentSet fInsertionSet; 84 Queue fQueue; 85 std::vector<Crossing> fCrossings; 86 }; 87 } // namespace bentleyottmann 88 #endif // EventQueue_DEFINED 89