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 32namespace WebCore { 33 34class Region { 35 WTF_MAKE_FAST_ALLOCATED; 36 37public: 38 Region(); 39 Region(const IntRect&); 40 41 IntRect bounds() const { return m_bounds; } 42 bool isEmpty() const { return m_bounds.isEmpty(); } 43 bool isRect() const { return m_shape.isRect(); } 44 45 Vector<IntRect> rects() const; 46 47 void unite(const Region&); 48 void intersect(const Region&); 49 void subtract(const Region&); 50 51 void translate(const IntSize&); 52 53 // Returns true if the query region is a subset of this region. 54 bool contains(const Region&) const; 55 56 bool contains(const IntPoint&) const; 57 58 // Returns true if the query region intersects any part of this region. 59 bool intersects(const Region&) const; 60 61 unsigned totalArea() const; 62 63 unsigned gridSize() const { return m_shape.gridSize(); } 64 65#ifndef NDEBUG 66 void dump() const; 67#endif 68 69 bool isValid() const { return m_shape.isValid(); } 70 71 // This is internal to Region, but exposed just for encoding. 72 // FIXME: figure out a better way to encode WebCore classes. 73 struct Span { 74 Span() 75 : y(0) 76 , segmentIndex(0) 77 { 78 } 79 80 Span(int y, size_t segmentIndex) 81 : y(y) 82 , segmentIndex(segmentIndex) 83 { 84 } 85 86 int y; 87 size_t segmentIndex; 88 }; 89 90 // For encoding/decoding only. 91 const Vector<int, 32>& shapeSegments() const { return m_shape.segments(); } 92 const Vector<Span, 16>& shapeSpans() const { return m_shape.spans(); } 93 94 void setShapeSegments(const Vector<int>& segments) { m_shape.setSegments(segments); } 95 void setShapeSpans(const Vector<Span>& spans) { m_shape.setSpans(spans); } 96 void updateBoundsFromShape(); 97 98private: 99 100 class Shape { 101 public: 102 Shape(); 103 Shape(const IntRect&); 104 105 IntRect bounds() const; 106 bool isEmpty() const { return m_spans.isEmpty(); } 107 bool isRect() const { return m_spans.size() <= 2 && m_segments.size() <= 2; } 108 unsigned gridSize() const { return m_spans.size() * m_segments.size(); } 109 110 typedef const Span* SpanIterator; 111 SpanIterator spans_begin() const; 112 SpanIterator spans_end() const; 113 114 typedef const int* SegmentIterator; 115 SegmentIterator segments_begin(SpanIterator) const; 116 SegmentIterator segments_end(SpanIterator) const; 117 118 static Shape unionShapes(const Shape& shape1, const Shape& shape2); 119 static Shape intersectShapes(const Shape& shape1, const Shape& shape2); 120 static Shape subtractShapes(const Shape& shape1, const Shape& shape2); 121 122 void translate(const IntSize&); 123 void swap(Shape&); 124 125 struct CompareContainsOperation; 126 struct CompareIntersectsOperation; 127 128 template<typename CompareOperation> 129 static bool compareShapes(const Shape& shape1, const Shape& shape2); 130 131 bool isValid() const; 132 133 // For encoding/decoding only. 134 const Vector<int, 32>& segments() const { return m_segments; } 135 const Vector<Span, 16>& spans() const { return m_spans; } 136 137 void setSegments(const Vector<int>& segments) { m_segments = segments; } 138 void setSpans(const Vector<Span>& spans) { m_spans = spans; } 139 140#ifndef NDEBUG 141 void dump() const; 142#endif 143 144 private: 145 struct UnionOperation; 146 struct IntersectOperation; 147 struct SubtractOperation; 148 149 template<typename Operation> 150 static Shape shapeOperation(const Shape& shape1, const Shape& shape2); 151 152 void appendSegment(int x); 153 void appendSpan(int y); 154 void appendSpan(int y, SegmentIterator begin, SegmentIterator end); 155 void appendSpans(const Shape&, SpanIterator begin, SpanIterator end); 156 157 bool canCoalesce(SegmentIterator begin, SegmentIterator end); 158 159 Vector<int, 32> m_segments; 160 Vector<Span, 16> m_spans; 161 162 friend bool operator==(const Shape&, const Shape&); 163 }; 164 165 IntRect m_bounds; 166 Shape m_shape; 167 168 friend bool operator==(const Region&, const Region&); 169 friend bool operator==(const Shape&, const Shape&); 170 friend bool operator==(const Span&, const Span&); 171}; 172 173static inline Region intersect(const Region& a, const Region& b) 174{ 175 Region result(a); 176 result.intersect(b); 177 178 return result; 179} 180 181static inline Region subtract(const Region& a, const Region& b) 182{ 183 Region result(a); 184 result.subtract(b); 185 186 return result; 187} 188 189static inline Region translate(const Region& region, const IntSize& offset) 190{ 191 Region result(region); 192 result.translate(offset); 193 194 return result; 195} 196 197inline bool operator==(const Region& a, const Region& b) 198{ 199 return a.m_bounds == b.m_bounds && a.m_shape == b.m_shape; 200} 201 202inline bool operator==(const Region::Shape& a, const Region::Shape& b) 203{ 204 return a.m_spans == b.m_spans && a.m_segments == b.m_segments; 205} 206 207inline bool operator==(const Region::Span& a, const Region::Span& b) 208{ 209 return a.y == b.y && a.segmentIndex == b.segmentIndex; 210} 211 212} // namespace WebCore 213 214#endif // Region_h 215