myers::EventQueue Class Reference

Public Member Functions
Event	operator[] (size_t i) const
Iterator	begin () const
Iterator	end () const
size_t	size () const
bool	empty () const

Static Public Member Functions
static EventQueue	Make (const SkSpan< const Segment > segments)

Detailed Description

Definition at line 232 of file Myers.cpp.

Member Function Documentation

begin()

Iterator myers::EventQueue::begin ( ) const

inline

Definition at line 390 of file Myers.cpp.

                           {
        return Iterator{*this, 0};
    }

empty()

bool myers::EventQueue::empty ( ) const

inline

Definition at line 402 of file Myers.cpp.

                       {
        return fEvents.empty();
    }

end()

Iterator myers::EventQueue::end ( ) const

inline

Definition at line 394 of file Myers.cpp.

                         {
        return Iterator{*this, fEvents.size()};
    }

Make()

static EventQueue myers::EventQueue::Make ( const SkSpan< const Segment >  segments )

inlinestatic

Definition at line 273 of file Myers.cpp.

                                                                 {
        SkASSERT(!segments.empty());
        SkASSERT(segments.size() < INT32_MAX);
 
        enum EventType {
            kBegin = 0,
            kHorizontal = 1,
            kEnd = 2
        };
 
        // A vector of SetupTuple when ordered will produce the events, and all the different
        // sets of segments (beginning, etc.).
        struct SetupTuple {
            // The main ordering of events.
            int32_t yOrdering;
 
            // Group together like event types together.
            EventType type;
 
            // Break ties if yOrdering is the same.
            int32_t xTieBreaker;
 
            // We want to sort the segments, but they are not part of the key.
            Segment originalSegment;
 
            bool operator==(const SetupTuple& r) const {
                return
                    std::tie(this->yOrdering, this->type, this->xTieBreaker, this->originalSegment)
                        == std::tie(r.yOrdering, r.type, r.xTieBreaker, r.originalSegment);
            }
        };
 
        std::vector<SetupTuple> eventOrdering;
        for (const auto& s : segments) {
 
            // Exclude zero length segments.
            if (s.upper() == s.lower()) {
                continue;
            }
 
            if (s.isHorizontal()) {
                // Tag for the horizontal set.
                eventOrdering.push_back(SetupTuple{s.upper().y, kHorizontal, -s.upper().x, s});
            } else {
                // Tag for the beginning and ending sets.
                eventOrdering.push_back(SetupTuple{s.upper().y, kBegin, -s.upper().x, s});
                eventOrdering.push_back(SetupTuple{s.lower().y, kEnd, -s.lower().x, s});
            }
        }
 
        // Order the tuples by y, then by set type, then by x value.
        auto eventLess = [](const SetupTuple& l, const SetupTuple& r) {
            return std::tie(l.yOrdering, l.type, l.xTieBreaker) <
                   std::tie(r.yOrdering, r.type, r.xTieBreaker);
        };
 
        // Sort the events.
        std::sort(eventOrdering.begin(), eventOrdering.end(), eventLess);
 
        // Remove duplicate segments.
        auto eraseFrom = std::unique(eventOrdering.begin(), eventOrdering.end());
        eventOrdering.erase(eraseFrom, eventOrdering.end());
 
        std::vector<CompactEvent> events;
        std::vector<Segment> segmentStorage;
        segmentStorage.reserve(eventOrdering.size());
 
        int32_t currentY = eventOrdering.front().yOrdering;
        int32_t start = 0,
                endOfBegin = 0,
                endOfHorizontal = 0,
                endOfEnd = 0;
        for (const auto& [y, type, _, s] : eventOrdering) {
            // If this is a new y then create the compact event.
            if (currentY != y) {
                events.push_back(CompactEvent{currentY,
                                              start,
                                              endOfBegin,
                                              endOfHorizontal,
                                              endOfEnd});
                start = endOfBegin = endOfHorizontal = endOfEnd = segmentStorage.size();
                currentY = y;
            }
 
            segmentStorage.push_back(s);
 
            // Increment the various set indices.
            const size_t segmentCount = segmentStorage.size();
            switch (type) {
                case kBegin: endOfBegin = segmentCount;
                    [[fallthrough]];
                case kHorizontal: endOfHorizontal = segmentCount;
                    [[fallthrough]];
                case kEnd: endOfEnd = segmentCount;
            }
        }
 
        // Store the last event.
        events.push_back(CompactEvent{currentY,
                                      start,
                                      endOfBegin,
                                      endOfHorizontal,
                                      endOfEnd});
 
        return EventQueue{std::move(events), std::move(segmentStorage)};
    }

operator[]()

Event myers::EventQueue::operator[] ( size_t  i ) const

inline

Definition at line 380 of file Myers.cpp.

                                     {
        SkASSERT(i < fEvents.size());
        auto& [y, start, endOfBegin, endOfHorizontal, endOfEnd] = fEvents[i];
        SkSpan<const Segment> begin{&fSegmentStorage[start], endOfBegin - start};
        SkSpan<const Segment>
            horizontal{&fSegmentStorage[endOfBegin], endOfHorizontal - endOfBegin};
        SkSpan<const Segment> end{&fSegmentStorage[endOfHorizontal], endOfEnd - endOfHorizontal};
        return Event{y, begin, horizontal, end};
    }

size()

size_t myers::EventQueue::size ( ) const

inline

Definition at line 398 of file Myers.cpp.

                        {
        return fEvents.size();
    }

---

The documentation for this class was generated from the following file:

• third_party/skia/modules/bentleyottmann/src/Myers.cpp