Home | History | Annotate | Download | only in Platform 
      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 <WebCore/IntRect.h>
     30 #include <wtf/Vector.h>
     31 
     32 #include <vector>
     33 
     34 namespace WebKit {
     35 
     36 class Region {
     37 public:
     38     Region();
     39     Region(const WebCore::IntRect&);
     40 
     41     WebCore::IntRect bounds() const { return m_bounds; }
     42     bool isEmpty() const { return m_bounds.isEmpty(); }
     43 
     44     Vector<WebCore::IntRect> rects() const;
     45 
     46     void unite(const Region&);
     47     void intersect(const Region&);
     48     void subtract(const Region&);
     49 
     50     void translate(const WebCore::IntSize&);
     51 
     52 #ifndef NDEBUG
     53     void dump() const;
     54 #endif
     55 
     56 private:
     57     struct Span {
     58         Span(int y, size_t segmentIndex)
     59             : y(y), segmentIndex(segmentIndex)
     60         {
     61         }
     62 
     63         int y;
     64         size_t segmentIndex;
     65     };
     66 
     67     class Shape {
     68     public:
     69         Shape();
     70         Shape(const WebCore::IntRect&);
     71 
     72         WebCore::IntRect bounds() const;
     73         bool isEmpty() const { return m_spans.isEmpty(); }
     74 
     75         typedef const Span* SpanIterator;
     76         SpanIterator spans_begin() const;
     77         SpanIterator spans_end() const;
     78 
     79         typedef const int* SegmentIterator;
     80         SegmentIterator segments_begin(SpanIterator) const;
     81         SegmentIterator segments_end(SpanIterator) const;
     82 
     83         static Shape unionShapes(const Shape& shape1, const Shape& shape2);
     84         static Shape intersectShapes(const Shape& shape1, const Shape& shape2);
     85         static Shape subtractShapes(const Shape& shape1, const Shape& shape2);
     86 
     87         void translate(const WebCore::IntSize&);
     88         void swap(Shape&);
     89 
     90 #ifndef NDEBUG
     91         void dump() const;
     92 #endif
     93 
     94     private:
     95         struct UnionOperation;
     96         struct IntersectOperation;
     97         struct SubtractOperation;
     98 
     99         template<typename Operation>
    100         static Shape shapeOperation(const Shape& shape1, const Shape& shape2);
    101 
    102         void appendSegment(int x);
    103         void appendSpan(int y);
    104         void appendSpan(int y, SegmentIterator begin, SegmentIterator end);
    105         void appendSpans(const Shape&, SpanIterator begin, SpanIterator end);
    106 
    107         bool canCoalesce(SegmentIterator begin, SegmentIterator end);
    108 
    109         // FIXME: These vectors should have inline sizes. Figure out a good optimal value.
    110         Vector<int> m_segments;
    111         Vector<Span> m_spans;
    112     };
    113 
    114     WebCore::IntRect m_bounds;
    115     Shape m_shape;
    116 };
    117 
    118 static inline Region intersect(const Region& a, const Region& b)
    119 {
    120     Region result(a);
    121     result.intersect(b);
    122 
    123     return result;
    124 }
    125 
    126 static inline Region subtract(const Region& a, const Region& b)
    127 {
    128     Region result(a);
    129     result.subtract(b);
    130 
    131     return result;
    132 }
    133 
    134 static inline Region translate(const Region& region, const WebCore::IntSize& offset)
    135 {
    136     Region result(region);
    137     result.translate(offset);
    138 
    139     return result;
    140 }
    141 
    142 } // namespace WebKit
    143 
    144 #endif // Region_h
    145