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 33namespace WebCore { 34 35class PLATFORM_EXPORT Region { 36public: 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 66private: 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 82 IntRect bounds() const; 83 bool isEmpty() const { return m_spans.isEmpty(); } 84 bool isRect() const { return m_spans.size() <= 2 && m_segments.size() <= 2; } 85 86 typedef const Span* SpanIterator; 87 SpanIterator spansBegin() const; 88 SpanIterator spansEnd() const; 89 90 typedef const int* SegmentIterator; 91 SegmentIterator segmentsBegin(SpanIterator) const; 92 SegmentIterator segmentsEnd(SpanIterator) const; 93 94 static Shape unionShapes(const Shape& shape1, const Shape& shape2); 95 static Shape intersectShapes(const Shape& shape1, const Shape& shape2); 96 static Shape subtractShapes(const Shape& shape1, const Shape& shape2); 97 98 void translate(const IntSize&); 99 void swap(Shape&); 100 101 struct CompareContainsOperation; 102 struct CompareIntersectsOperation; 103 104 template<typename CompareOperation> 105 static bool compareShapes(const Shape& shape1, const Shape& shape2); 106 107#ifndef NDEBUG 108 void dump() const; 109#endif 110 111 private: 112 struct UnionOperation; 113 struct IntersectOperation; 114 struct SubtractOperation; 115 116 template<typename Operation> 117 static Shape shapeOperation(const Shape& shape1, const Shape& shape2); 118 119 void appendSegment(int x); 120 void appendSpan(int y); 121 void appendSpan(int y, SegmentIterator begin, SegmentIterator end); 122 void appendSpans(const Shape&, SpanIterator begin, SpanIterator end); 123 124 bool canCoalesce(SegmentIterator begin, SegmentIterator end); 125 126 Vector<int, 32> m_segments; 127 Vector<Span, 16> m_spans; 128 129 friend bool operator==(const Shape&, const Shape&); 130 }; 131 132 IntRect m_bounds; 133 Shape m_shape; 134 135 friend bool operator==(const Region&, const Region&); 136 friend bool operator==(const Shape&, const Shape&); 137 friend bool operator==(const Span&, const Span&); 138}; 139 140static inline Region intersect(const Region& a, const Region& b) 141{ 142 Region result(a); 143 result.intersect(b); 144 145 return result; 146} 147 148static inline Region subtract(const Region& a, const Region& b) 149{ 150 Region result(a); 151 result.subtract(b); 152 153 return result; 154} 155 156static inline Region translate(const Region& region, const IntSize& offset) 157{ 158 Region result(region); 159 result.translate(offset); 160 161 return result; 162} 163 164inline bool operator==(const Region& a, const Region& b) 165{ 166 return a.m_bounds == b.m_bounds && a.m_shape == b.m_shape; 167} 168 169inline bool operator==(const Region::Shape& a, const Region::Shape& b) 170{ 171 return a.m_spans == b.m_spans && a.m_segments == b.m_segments; 172} 173 174inline bool operator==(const Region::Span& a, const Region::Span& b) 175{ 176 return a.y == b.y && a.segmentIndex == b.segmentIndex; 177} 178 179} // namespace WebCore 180 181#endif // Region_h 182