Source/WebCore/platform/graphics/Region.h

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