RegionHelper.h revision 836513bfbf166217d57d1ef212d9d700ed25620c 
1/*
2 * Copyright (C) 2009 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#ifndef ANDROID_UI_PRIVATE_REGION_HELPER_H
18#define ANDROID_UI_PRIVATE_REGION_HELPER_H
19
20#include <limits>
21#include <stdint.h>
22#include <sys/types.h>
23
24#include <limits>
25
26namespace android {
27// ----------------------------------------------------------------------------
28
29template<typename RECT>
30class region_operator
31{
32public:
33    typedef typename RECT::value_type TYPE;
34    static const TYPE max_value = std::numeric_limits<TYPE>::max();
35
36    /*
37     * Common boolean operations:
38     * value is computed as 0b101 op 0b110
39     *    other boolean operation are possible, simply compute
40     *    their corresponding value with the above formulae and use
41     *    it when instantiating a region_operator.
42     */
43    static const uint32_t LHS = 0x5;  // 0b101
44    static const uint32_t RHS = 0x6;  // 0b110
45    enum {
46        op_nand = LHS & ~RHS,
47        op_and  = LHS &  RHS,
48        op_or   = LHS |  RHS,
49        op_xor  = LHS ^  RHS
50    };
51
52    struct region {
53        RECT const* rects;
54        size_t count;
55        TYPE dx;
56        TYPE dy;
57        inline region(const region& rhs)
58            : rects(rhs.rects), count(rhs.count), dx(rhs.dx), dy(rhs.dy) { }
59        inline region(RECT const* _r, size_t _c)
60            : rects(_r), count(_c), dx(), dy() { }
61        inline region(RECT const* _r, size_t _c, TYPE _dx, TYPE _dy)
62            : rects(_r), count(_c), dx(_dx), dy(_dy) { }
63    };
64
65    class region_rasterizer {
66        friend class region_operator;
67        virtual void operator()(const RECT& rect) = 0;
68    public:
69        virtual ~region_rasterizer() { }
70    };
71
72    inline region_operator(uint32_t op, const region& lhs, const region& rhs)
73        : op_mask(op), spanner(lhs, rhs)
74    {
75    }
76
77    void operator()(region_rasterizer& rasterizer) {
78        RECT current(Rect::EMPTY_RECT);
79        do {
80            SpannerInner spannerInner(spanner.lhs, spanner.rhs);
81            int inside = spanner.next(current.top, current.bottom);
82            spannerInner.prepare(inside);
83            do {
84                TYPE left, right;
85                int inner_inside = spannerInner.next(current.left, current.right);
86                if ((op_mask >> inner_inside) & 1) {
87                    if (current.left < current.right &&
88                            current.top < current.bottom) {
89                        rasterizer(current);
90                    }
91                }
92            } while(!spannerInner.isDone());
93        } while(!spanner.isDone());
94    }
95
96private:
97    uint32_t op_mask;
98
99    class SpannerBase
100    {
101    public:
102        SpannerBase()
103            : lhs_head(max_value), lhs_tail(max_value),
104              rhs_head(max_value), rhs_tail(max_value) {
105        }
106
107        enum {
108            lhs_before_rhs   = 0,
109            lhs_after_rhs    = 1,
110            lhs_coincide_rhs = 2
111        };
112
113    protected:
114        TYPE lhs_head;
115        TYPE lhs_tail;
116        TYPE rhs_head;
117        TYPE rhs_tail;
118
119        inline int next(TYPE& head, TYPE& tail,
120                bool& more_lhs, bool& more_rhs)
121        {
122            int inside;
123            more_lhs = false;
124            more_rhs = false;
125            if (lhs_head < rhs_head) {
126                inside = lhs_before_rhs;
127                head = lhs_head;
128                if (lhs_tail <= rhs_head) {
129                    tail = lhs_tail;
130                    more_lhs = true;
131                } else {
132                    lhs_head = rhs_head;
133                    tail = rhs_head;
134                }
135            } else if (rhs_head < lhs_head) {
136                inside = lhs_after_rhs;
137                head = rhs_head;
138                if (rhs_tail <= lhs_head) {
139                    tail = rhs_tail;
140                    more_rhs = true;
141                } else {
142                    rhs_head = lhs_head;
143                    tail = lhs_head;
144                }
145            } else {
146                inside = lhs_coincide_rhs;
147                head = lhs_head;
148                if (lhs_tail <= rhs_tail) {
149                    tail = rhs_head = lhs_tail;
150                    more_lhs = true;
151                }
152                if (rhs_tail <= lhs_tail) {
153                    tail = lhs_head = rhs_tail;
154                    more_rhs = true;
155                }
156            }
157            return inside;
158        }
159    };
160
161    class Spanner : protected SpannerBase
162    {
163        friend class region_operator;
164        region lhs;
165        region rhs;
166
167    public:
168        inline Spanner(const region& _lhs, const region& _rhs)
169        : lhs(_lhs), rhs(_rhs)
170        {
171            if (lhs.count) {
172                SpannerBase::lhs_head = lhs.rects->top      + lhs.dy;
173                SpannerBase::lhs_tail = lhs.rects->bottom   + lhs.dy;
174            }
175            if (rhs.count) {
176                SpannerBase::rhs_head = rhs.rects->top      + rhs.dy;
177                SpannerBase::rhs_tail = rhs.rects->bottom   + rhs.dy;
178            }
179        }
180
181        inline bool isDone() const {
182            return !rhs.count && !lhs.count;
183        }
184
185        inline int next(TYPE& top, TYPE& bottom)
186        {
187            bool more_lhs = false;
188            bool more_rhs = false;
189            int inside = SpannerBase::next(top, bottom, more_lhs, more_rhs);
190            if (more_lhs) {
191                advance(lhs, SpannerBase::lhs_head, SpannerBase::lhs_tail);
192            }
193            if (more_rhs) {
194                advance(rhs, SpannerBase::rhs_head, SpannerBase::rhs_tail);
195            }
196            return inside;
197        }
198
199    private:
200        static inline
201        void advance(region& reg, TYPE& aTop, TYPE& aBottom) {
202            // got to next span
203            size_t count = reg.count;
204            RECT const * rects = reg.rects;
205            RECT const * const end = rects + count;
206            const int top = rects->top;
207            while (rects != end && rects->top == top) {
208                rects++;
209                count--;
210            }
211            if (rects != end) {
212                aTop    = rects->top    + reg.dy;
213                aBottom = rects->bottom + reg.dy;
214            } else {
215                aTop    = max_value;
216                aBottom = max_value;
217            }
218            reg.rects = rects;
219            reg.count = count;
220        }
221    };
222
223    class SpannerInner : protected SpannerBase
224    {
225        region lhs;
226        region rhs;
227
228    public:
229        inline SpannerInner(const region& _lhs, const region& _rhs)
230            : lhs(_lhs), rhs(_rhs)
231        {
232        }
233
234        inline void prepare(int inside) {
235            if (inside == SpannerBase::lhs_before_rhs) {
236                if (lhs.count) {
237                    SpannerBase::lhs_head = lhs.rects->left  + lhs.dx;
238                    SpannerBase::lhs_tail = lhs.rects->right + lhs.dx;
239                }
240                SpannerBase::rhs_head = max_value;
241                SpannerBase::rhs_tail = max_value;
242            } else if (inside == SpannerBase::lhs_after_rhs) {
243                SpannerBase::lhs_head = max_value;
244                SpannerBase::lhs_tail = max_value;
245                if (rhs.count) {
246                    SpannerBase::rhs_head = rhs.rects->left  + rhs.dx;
247                    SpannerBase::rhs_tail = rhs.rects->right + rhs.dx;
248                }
249            } else {
250                if (lhs.count) {
251                    SpannerBase::lhs_head = lhs.rects->left  + lhs.dx;
252                    SpannerBase::lhs_tail = lhs.rects->right + lhs.dx;
253                }
254                if (rhs.count) {
255                    SpannerBase::rhs_head = rhs.rects->left  + rhs.dx;
256                    SpannerBase::rhs_tail = rhs.rects->right + rhs.dx;
257                }
258            }
259        }
260
261        inline bool isDone() const {
262            return SpannerBase::lhs_head == max_value &&
263                   SpannerBase::rhs_head == max_value;
264        }
265
266        inline int next(TYPE& left, TYPE& right)
267        {
268            bool more_lhs = false;
269            bool more_rhs = false;
270            int inside = SpannerBase::next(left, right, more_lhs, more_rhs);
271            if (more_lhs) {
272                advance(lhs, SpannerBase::lhs_head, SpannerBase::lhs_tail);
273            }
274            if (more_rhs) {
275                advance(rhs, SpannerBase::rhs_head, SpannerBase::rhs_tail);
276            }
277            return inside;
278        }
279
280    private:
281        static inline
282        void advance(region& reg, TYPE& left, TYPE& right) {
283            if (reg.rects && reg.count) {
284                const int cur_span_top = reg.rects->top;
285                reg.rects++;
286                reg.count--;
287                if (!reg.count || reg.rects->top != cur_span_top) {
288                    left  = max_value;
289                    right = max_value;
290                } else {
291                    left  = reg.rects->left  + reg.dx;
292                    right = reg.rects->right + reg.dx;
293                }
294            }
295        }
296    };
297
298    Spanner spanner;
299};
300
301// ----------------------------------------------------------------------------
302};
303
304#endif /* ANDROID_UI_PRIVATE_REGION_HELPER_H */
305