1 | /* |
2 | * Copyright (C) 2010, 2011 Apple Inc. All rights reserved. |
3 | * |
4 | * Redistribution and use in source and binary forms, with or without |
5 | * modification, are permitted provided that the following conditions |
6 | * are met: |
7 | * 1. Redistributions of source code must retain the above copyright |
8 | * notice, this list of conditions and the following disclaimer. |
9 | * 2. Redistributions in binary form must reproduce the above copyright |
10 | * notice, this list of conditions and the following disclaimer in the |
11 | * documentation and/or other materials provided with the distribution. |
12 | * |
13 | * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS'' |
14 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, |
15 | * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
16 | * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS |
17 | * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
18 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
19 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
20 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
21 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
22 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF |
23 | * THE POSSIBILITY OF SUCH DAMAGE. |
24 | */ |
25 | |
26 | #ifndef Region_h |
27 | #define Region_h |
28 | |
29 | #include "IntRect.h" |
30 | #include <wtf/Optional.h> |
31 | #include <wtf/PointerComparison.h> |
32 | #include <wtf/Vector.h> |
33 | |
34 | namespace WebCore { |
35 | |
36 | class Region { |
37 | WTF_MAKE_FAST_ALLOCATED; |
38 | |
39 | public: |
40 | WEBCORE_EXPORT Region(); |
41 | WEBCORE_EXPORT Region(const IntRect&); |
42 | |
43 | WEBCORE_EXPORT Region(const Region&); |
44 | WEBCORE_EXPORT Region(Region&&); |
45 | |
46 | WEBCORE_EXPORT ~Region(); |
47 | |
48 | WEBCORE_EXPORT Region& operator=(const Region&); |
49 | WEBCORE_EXPORT Region& operator=(Region&&); |
50 | |
51 | IntRect bounds() const { return m_bounds; } |
52 | bool isEmpty() const { return m_bounds.isEmpty(); } |
53 | bool isRect() const { return !m_shape; } |
54 | |
55 | WEBCORE_EXPORT Vector<IntRect, 1> rects() const; |
56 | |
57 | WEBCORE_EXPORT void unite(const Region&); |
58 | WEBCORE_EXPORT void intersect(const Region&); |
59 | WEBCORE_EXPORT void subtract(const Region&); |
60 | |
61 | WEBCORE_EXPORT void translate(const IntSize&); |
62 | |
63 | // Returns true if the query region is a subset of this region. |
64 | WEBCORE_EXPORT bool contains(const Region&) const; |
65 | |
66 | WEBCORE_EXPORT bool contains(const IntPoint&) const; |
67 | |
68 | // Returns true if the query region intersects any part of this region. |
69 | WEBCORE_EXPORT bool intersects(const Region&) const; |
70 | |
71 | WEBCORE_EXPORT uint64_t totalArea() const; |
72 | |
73 | unsigned gridSize() const { return m_shape ? m_shape->gridSize() : 0; } |
74 | |
75 | #ifndef NDEBUG |
76 | void dump() const; |
77 | #endif |
78 | |
79 | template<class Encoder> void encode(Encoder&) const; |
80 | template<class Decoder> static Optional<Region> decode(Decoder&); |
81 | // FIXME: Remove legacy decode. |
82 | template<class Decoder> static bool decode(Decoder&, Region&); |
83 | |
84 | private: |
85 | struct Span { |
86 | int y { 0 }; |
87 | size_t segmentIndex { 0 }; |
88 | |
89 | template<class Encoder> void encode(Encoder&) const; |
90 | template<class Decoder> static Optional<Span> decode(Decoder&); |
91 | }; |
92 | |
93 | class Shape { |
94 | public: |
95 | Shape() = default; |
96 | Shape(const IntRect&); |
97 | |
98 | IntRect bounds() const; |
99 | bool isEmpty() const { return m_spans.isEmpty(); } |
100 | bool isRect() const { return m_spans.size() <= 2 && m_segments.size() <= 2; } |
101 | unsigned gridSize() const { return m_spans.size() * m_segments.size(); } |
102 | |
103 | typedef const Span* SpanIterator; |
104 | SpanIterator spans_begin() const; |
105 | SpanIterator spans_end() const; |
106 | |
107 | typedef const int* SegmentIterator; |
108 | SegmentIterator segments_begin(SpanIterator) const; |
109 | SegmentIterator segments_end(SpanIterator) const; |
110 | |
111 | static Shape unionShapes(const Shape& shape1, const Shape& shape2); |
112 | static Shape intersectShapes(const Shape& shape1, const Shape& shape2); |
113 | static Shape subtractShapes(const Shape& shape1, const Shape& shape2); |
114 | |
115 | WEBCORE_EXPORT void translate(const IntSize&); |
116 | |
117 | struct CompareContainsOperation; |
118 | struct CompareIntersectsOperation; |
119 | |
120 | template<typename CompareOperation> |
121 | static bool compareShapes(const Shape& shape1, const Shape& shape2); |
122 | |
123 | template<class Encoder> void encode(Encoder&) const; |
124 | template<class Decoder> static Optional<Shape> decode(Decoder&); |
125 | |
126 | #ifndef NDEBUG |
127 | void dump() const; |
128 | #endif |
129 | |
130 | private: |
131 | struct UnionOperation; |
132 | struct IntersectOperation; |
133 | struct SubtractOperation; |
134 | |
135 | template<typename Operation> |
136 | static Shape shapeOperation(const Shape& shape1, const Shape& shape2); |
137 | |
138 | void appendSegment(int x); |
139 | void appendSpan(int y); |
140 | void appendSpan(int y, SegmentIterator begin, SegmentIterator end); |
141 | void appendSpans(const Shape&, SpanIterator begin, SpanIterator end); |
142 | |
143 | bool canCoalesce(SegmentIterator begin, SegmentIterator end); |
144 | |
145 | Vector<int, 32> m_segments; |
146 | Vector<Span, 16> m_spans; |
147 | |
148 | friend bool operator==(const Shape&, const Shape&); |
149 | }; |
150 | |
151 | std::unique_ptr<Shape> copyShape() const { return m_shape ? std::make_unique<Shape>(*m_shape) : nullptr; } |
152 | void setShape(Shape&&); |
153 | |
154 | IntRect m_bounds; |
155 | std::unique_ptr<Shape> m_shape; |
156 | |
157 | friend bool operator==(const Region&, const Region&); |
158 | friend bool operator==(const Shape&, const Shape&); |
159 | friend bool operator==(const Span&, const Span&); |
160 | friend bool operator!=(const Span&, const Span&); |
161 | }; |
162 | |
163 | static inline Region intersect(const Region& a, const Region& b) |
164 | { |
165 | Region result(a); |
166 | result.intersect(b); |
167 | |
168 | return result; |
169 | } |
170 | |
171 | static inline Region subtract(const Region& a, const Region& b) |
172 | { |
173 | Region result(a); |
174 | result.subtract(b); |
175 | |
176 | return result; |
177 | } |
178 | |
179 | static inline Region translate(const Region& region, const IntSize& offset) |
180 | { |
181 | Region result(region); |
182 | result.translate(offset); |
183 | |
184 | return result; |
185 | } |
186 | |
187 | inline bool operator==(const Region& a, const Region& b) |
188 | { |
189 | return a.m_bounds == b.m_bounds && arePointingToEqualData(a.m_shape, b.m_shape); |
190 | } |
191 | inline bool operator!=(const Region& a, const Region& b) |
192 | { |
193 | return !(a == b); |
194 | } |
195 | |
196 | inline bool operator==(const Region::Shape& a, const Region::Shape& b) |
197 | { |
198 | return a.m_spans == b.m_spans && a.m_segments == b.m_segments; |
199 | } |
200 | |
201 | inline bool operator==(const Region::Span& a, const Region::Span& b) |
202 | { |
203 | return a.y == b.y && a.segmentIndex == b.segmentIndex; |
204 | } |
205 | |
206 | inline bool operator!=(const Region::Span& a, const Region::Span& b) |
207 | { |
208 | return !(a == b); |
209 | } |
210 | |
211 | WEBCORE_EXPORT WTF::TextStream& operator<<(WTF::TextStream&, const Region&); |
212 | |
213 | template<class Encoder> |
214 | void Region::Span::encode(Encoder& encoder) const |
215 | { |
216 | encoder << y << static_cast<uint64_t>(segmentIndex); |
217 | } |
218 | |
219 | template<class Decoder> |
220 | Optional<Region::Span> Region::Span::decode(Decoder& decoder) |
221 | { |
222 | Optional<int> y; |
223 | decoder >> y; |
224 | if (!y) |
225 | return { }; |
226 | |
227 | Optional<uint64_t> segmentIndex; |
228 | decoder >> segmentIndex; |
229 | if (!segmentIndex) |
230 | return { }; |
231 | |
232 | return { { *y, static_cast<size_t>(*segmentIndex) } }; |
233 | } |
234 | |
235 | template<class Encoder> |
236 | void Region::Shape::encode(Encoder& encoder) const |
237 | { |
238 | encoder << m_segments; |
239 | encoder << m_spans; |
240 | } |
241 | |
242 | template<class Decoder> |
243 | Optional<Region::Shape> Region::Shape::decode(Decoder& decoder) |
244 | { |
245 | Optional<Vector<int>> segments; |
246 | decoder >> segments; |
247 | if (!segments) |
248 | return WTF::nullopt; |
249 | |
250 | Optional<Vector<Region::Span>> spans; |
251 | decoder >> spans; |
252 | if (!spans) |
253 | return WTF::nullopt; |
254 | |
255 | Shape shape; |
256 | shape.m_segments = WTFMove(*segments); |
257 | shape.m_spans = WTFMove(*spans); |
258 | |
259 | return { shape }; |
260 | } |
261 | |
262 | template<class Encoder> |
263 | void Region::encode(Encoder& encoder) const |
264 | { |
265 | encoder << m_bounds; |
266 | bool hasShape = !!m_shape; |
267 | encoder << hasShape; |
268 | if (hasShape) |
269 | encoder << *m_shape; |
270 | } |
271 | |
272 | template<class Decoder> |
273 | Optional<Region> Region::decode(Decoder& decoder) |
274 | { |
275 | Optional<IntRect> bounds; |
276 | decoder >> bounds; |
277 | if (!bounds) |
278 | return WTF::nullopt; |
279 | |
280 | Optional<bool> hasShape; |
281 | decoder >> hasShape; |
282 | if (!hasShape) |
283 | return WTF::nullopt; |
284 | |
285 | Region region = { *bounds }; |
286 | |
287 | if (*hasShape) { |
288 | Optional<Shape> shape; |
289 | decoder >> shape; |
290 | if (!shape) |
291 | return WTF::nullopt; |
292 | region.m_shape = std::make_unique<Shape>(WTFMove(*shape)); |
293 | } |
294 | |
295 | return { region }; |
296 | } |
297 | |
298 | template<class Decoder> |
299 | bool Region::decode(Decoder& decoder, Region& region) |
300 | { |
301 | Optional<Region> decodedRegion; |
302 | decoder >> decodedRegion; |
303 | if (!decodedRegion) |
304 | return false; |
305 | region = WTFMove(*decodedRegion); |
306 | return true; |
307 | } |
308 | |
309 | } // namespace WebCore |
310 | |
311 | #endif // Region_h |
312 | |