2fecfe4161aa0f3c3ef8d3f21bb5519139e78c6e
[WebKit-https.git] / Source / WebCore / platform / graphics / Region.h
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/Vector.h>
31
32 namespace WebCore {
33
34 class Region {
35 public:
36     Region();
37     Region(const IntRect&);
38
39     IntRect bounds() const { return m_bounds; }
40     bool isEmpty() const { return m_bounds.isEmpty(); }
41
42     Vector<IntRect> rects() const;
43
44     void unite(const Region&);
45     void intersect(const Region&);
46     void subtract(const Region&);
47
48     void translate(const IntSize&);
49
50     // Returns true if the query region is a subset of this region.
51     bool contains(const Region&) const;
52
53     bool contains(const IntPoint&) const;
54
55     unsigned totalArea() const;
56
57 #ifndef NDEBUG
58     void dump() const;
59 #endif
60
61 private:
62     struct Span {
63         Span(int y, size_t segmentIndex)
64             : y(y), segmentIndex(segmentIndex)
65         {
66         }
67
68         int y;
69         size_t segmentIndex;
70     };
71
72     class Shape {
73     public:
74         Shape();
75         Shape(const IntRect&);
76
77         IntRect bounds() const;
78         bool isEmpty() const { return m_spans.isEmpty(); }
79
80         typedef const Span* SpanIterator;
81         SpanIterator spans_begin() const;
82         SpanIterator spans_end() const;
83         
84         typedef const int* SegmentIterator;
85         SegmentIterator segments_begin(SpanIterator) const;
86         SegmentIterator segments_end(SpanIterator) const;
87
88         static Shape unionShapes(const Shape& shape1, const Shape& shape2);
89         static Shape intersectShapes(const Shape& shape1, const Shape& shape2);
90         static Shape subtractShapes(const Shape& shape1, const Shape& shape2);
91
92         void translate(const IntSize&);
93         void swap(Shape&);
94
95 #ifndef NDEBUG
96         void dump() const;
97 #endif
98
99     private:
100         struct UnionOperation;
101         struct IntersectOperation;
102         struct SubtractOperation;
103         
104         template<typename Operation>
105         static Shape shapeOperation(const Shape& shape1, const Shape& shape2);
106
107         void appendSegment(int x);
108         void appendSpan(int y);
109         void appendSpan(int y, SegmentIterator begin, SegmentIterator end);
110         void appendSpans(const Shape&, SpanIterator begin, SpanIterator end);
111
112         bool canCoalesce(SegmentIterator begin, SegmentIterator end);
113
114         Vector<int, 32> m_segments;
115         Vector<Span, 16> m_spans;
116
117         friend bool operator==(const Shape&, const Shape&);
118     };
119
120     IntRect m_bounds;
121     Shape m_shape;
122
123     friend bool operator==(const Region&, const Region&);
124     friend bool operator==(const Shape&, const Shape&);
125     friend bool operator==(const Span&, const Span&);
126 };
127
128 static inline Region intersect(const Region& a, const Region& b)
129 {
130     Region result(a);
131     result.intersect(b);
132
133     return result;
134 }
135     
136 static inline Region subtract(const Region& a, const Region& b)
137 {
138     Region result(a);
139     result.subtract(b);
140
141     return result;
142 }
143
144 static inline Region translate(const Region& region, const IntSize& offset)
145 {
146     Region result(region);
147     result.translate(offset);
148
149     return result;
150 }
151
152 inline bool operator==(const Region& a, const Region& b)
153 {
154     return a.m_bounds == b.m_bounds && a.m_shape == b.m_shape;
155 }
156
157 inline bool operator==(const Region::Shape& a, const Region::Shape& b)
158 {
159     return a.m_spans == b.m_spans && a.m_segments == b.m_segments;
160 }
161
162 inline bool operator==(const Region::Span& a, const Region::Span& b)
163 {
164     return a.y == b.y && a.segmentIndex == b.segmentIndex;
165 }
166
167 } // namespace WebCore
168
169 #endif // Region_h