15c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* 25c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Copyright (C) 2010, 2011 Apple Inc. All rights reserved. 35c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 45c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Redistribution and use in source and binary forms, with or without 55c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * modification, are permitted provided that the following conditions 65c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * are met: 75c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 1. Redistributions of source code must retain the above copyright 85c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * notice, this list of conditions and the following disclaimer. 95c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 2. Redistributions in binary form must reproduce the above copyright 105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * notice, this list of conditions and the following disclaimer in the 115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * documentation and/or other materials provided with the distribution. 125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS'' 145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, 155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS 175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF 235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * THE POSSIBILITY OF SUCH DAMAGE. 245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef Region_h 275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define Region_h 285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 291e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)#include "platform/PlatformExport.h" 301e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)#include "platform/geometry/IntRect.h" 317757ec2eadfa2dd8ac2aeed0a4399e9b07ec38cbBen Murdoch#include "wtf/Vector.h" 325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 33c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)namespace blink { 345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 351e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)class PLATFORM_EXPORT Region { 365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)public: 375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Region(); 385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Region(const IntRect&); 395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) IntRect bounds() const { return m_bounds; } 415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool isEmpty() const { return m_bounds.isEmpty(); } 425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool isRect() const { return m_shape.isRect(); } 435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Vector<IntRect> rects() const; 455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void unite(const Region&); 475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void intersect(const Region&); 485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void subtract(const Region&); 495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void translate(const IntSize&); 515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Returns true if the query region is a subset of this region. 535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool contains(const Region&) const; 545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool contains(const IntPoint&) const; 565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Returns true if the query region intersects any part of this region. 585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool intersects(const Region&) const; 595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) unsigned totalArea() const; 615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef NDEBUG 635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void dump() const; 645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)private: 675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct Span { 685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Span(int y, size_t segmentIndex) 695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : y(y), segmentIndex(segmentIndex) 705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int y; 745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) size_t segmentIndex; 755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) class Shape { 785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) public: 795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Shape(); 805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Shape(const IntRect&); 815d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) Shape(size_t segmentsCapacity, size_t spansCapacity); 825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) IntRect bounds() const; 845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool isEmpty() const { return m_spans.isEmpty(); } 855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool isRect() const { return m_spans.size() <= 2 && m_segments.size() <= 2; } 865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef const Span* SpanIterator; 881e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) SpanIterator spansBegin() const; 891e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) SpanIterator spansEnd() const; 905d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) size_t spansSize() const { return m_spans.size(); } 9102772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef const int* SegmentIterator; 931e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) SegmentIterator segmentsBegin(SpanIterator) const; 941e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) SegmentIterator segmentsEnd(SpanIterator) const; 955d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) size_t segmentsSize() const { return m_segments.size(); } 965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static Shape unionShapes(const Shape& shape1, const Shape& shape2); 985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static Shape intersectShapes(const Shape& shape1, const Shape& shape2); 995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static Shape subtractShapes(const Shape& shape1, const Shape& shape2); 1005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void translate(const IntSize&); 1025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void swap(Shape&); 1035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct CompareContainsOperation; 1055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct CompareIntersectsOperation; 1065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename CompareOperation> 1085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static bool compareShapes(const Shape& shape1, const Shape& shape2); 1095d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) void trimCapacities(); 1105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef NDEBUG 1125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void dump() const; 1135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 1145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) private: 1165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct UnionOperation; 1175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct IntersectOperation; 1185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct SubtractOperation; 11902772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 1205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename Operation> 1215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static Shape shapeOperation(const Shape& shape1, const Shape& shape2); 1225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void appendSegment(int x); 1245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void appendSpan(int y); 1255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void appendSpan(int y, SegmentIterator begin, SegmentIterator end); 1265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void appendSpans(const Shape&, SpanIterator begin, SpanIterator end); 1275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool canCoalesce(SegmentIterator begin, SegmentIterator end); 1295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Vector<int, 32> m_segments; 1315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Vector<Span, 16> m_spans; 1325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) friend bool operator==(const Shape&, const Shape&); 1345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 1355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) IntRect m_bounds; 1375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Shape m_shape; 1385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) friend bool operator==(const Region&, const Region&); 1405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) friend bool operator==(const Shape&, const Shape&); 1415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) friend bool operator==(const Span&, const Span&); 1425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 1435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)static inline Region intersect(const Region& a, const Region& b) 1455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 1465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Region result(a); 1475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) result.intersect(b); 1485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return result; 1505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 15102772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 1525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)static inline Region subtract(const Region& a, const Region& b) 1535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 1545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Region result(a); 1555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) result.subtract(b); 1565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return result; 1585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)static inline Region translate(const Region& region, const IntSize& offset) 1615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 1625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Region result(region); 1635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) result.translate(offset); 1645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return result; 1665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)inline bool operator==(const Region& a, const Region& b) 1695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 1705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return a.m_bounds == b.m_bounds && a.m_shape == b.m_shape; 1715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)inline bool operator==(const Region::Shape& a, const Region::Shape& b) 1745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 1755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return a.m_spans == b.m_spans && a.m_segments == b.m_segments; 1765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)inline bool operator==(const Region::Span& a, const Region::Span& b) 1795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 1805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return a.y == b.y && a.segmentIndex == b.segmentIndex; 1815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 183c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)} // namespace blink 1845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif // Region_h 186