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 <WebCore/IntRect.h>
30 #include <wtf/Vector.h>
31
32 #include <vector>
33
34 namespace WebKit {
35
36 class Region {
37 public:
38 Region();
39 Region(const WebCore::IntRect&);
40
bounds()41 WebCore::IntRect bounds() const { return m_bounds; }
isEmpty()42 bool isEmpty() const { return m_bounds.isEmpty(); }
43
44 Vector<WebCore::IntRect> rects() const;
45
46 void unite(const Region&);
47 void intersect(const Region&);
48 void subtract(const Region&);
49
50 void translate(const WebCore::IntSize&);
51
52 #ifndef NDEBUG
53 void dump() const;
54 #endif
55
56 private:
57 struct Span {
SpanSpan58 Span(int y, size_t segmentIndex)
59 : y(y), segmentIndex(segmentIndex)
60 {
61 }
62
63 int y;
64 size_t segmentIndex;
65 };
66
67 class Shape {
68 public:
69 Shape();
70 Shape(const WebCore::IntRect&);
71
72 WebCore::IntRect bounds() const;
isEmpty()73 bool isEmpty() const { return m_spans.isEmpty(); }
74
75 typedef const Span* SpanIterator;
76 SpanIterator spans_begin() const;
77 SpanIterator spans_end() const;
78
79 typedef const int* SegmentIterator;
80 SegmentIterator segments_begin(SpanIterator) const;
81 SegmentIterator segments_end(SpanIterator) const;
82
83 static Shape unionShapes(const Shape& shape1, const Shape& shape2);
84 static Shape intersectShapes(const Shape& shape1, const Shape& shape2);
85 static Shape subtractShapes(const Shape& shape1, const Shape& shape2);
86
87 void translate(const WebCore::IntSize&);
88 void swap(Shape&);
89
90 #ifndef NDEBUG
91 void dump() const;
92 #endif
93
94 private:
95 struct UnionOperation;
96 struct IntersectOperation;
97 struct SubtractOperation;
98
99 template<typename Operation>
100 static Shape shapeOperation(const Shape& shape1, const Shape& shape2);
101
102 void appendSegment(int x);
103 void appendSpan(int y);
104 void appendSpan(int y, SegmentIterator begin, SegmentIterator end);
105 void appendSpans(const Shape&, SpanIterator begin, SpanIterator end);
106
107 bool canCoalesce(SegmentIterator begin, SegmentIterator end);
108
109 // FIXME: These vectors should have inline sizes. Figure out a good optimal value.
110 Vector<int> m_segments;
111 Vector<Span> m_spans;
112 };
113
114 WebCore::IntRect m_bounds;
115 Shape m_shape;
116 };
117
intersect(const Region & a,const Region & b)118 static inline Region intersect(const Region& a, const Region& b)
119 {
120 Region result(a);
121 result.intersect(b);
122
123 return result;
124 }
125
subtract(const Region & a,const Region & b)126 static inline Region subtract(const Region& a, const Region& b)
127 {
128 Region result(a);
129 result.subtract(b);
130
131 return result;
132 }
133
translate(const Region & region,const WebCore::IntSize & offset)134 static inline Region translate(const Region& region, const WebCore::IntSize& offset)
135 {
136 Region result(region);
137 result.translate(offset);
138
139 return result;
140 }
141
142 } // namespace WebKit
143
144 #endif // Region_h
145