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