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 41 WebCore::IntRect bounds() const { return m_bounds; } 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 { 58 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; 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 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 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 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