include/private/ui/RegionHelper.h

/*
 * Copyright (C) 2009 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#ifndef ANDROID_UI_PRIVATE_REGION_HELPER_H
#define ANDROID_UI_PRIVATE_REGION_HELPER_H

#include <stdint.h>
#include <sys/types.h>

namespace android {
// ----------------------------------------------------------------------------

template<typename RECT>
class region_operator
{
public:
    typedef typename RECT::value_type TYPE;    
    static const TYPE max_value = 0x7FFFFFF;

    /* 
     * Common boolean operations:
     * value is computed as 0b101 op 0b110
     *    other boolean operation are possible, simply compute
     *    their corresponding value with the above formulae and use
     *    it when instantiating a region_operator.
     */
    static const uint32_t LHS = 0x5;  // 0b101
    static const uint32_t RHS = 0x6;  // 0b110
    enum {
        op_nand = LHS & ~RHS,
        op_and  = LHS &  RHS,
        op_or   = LHS |  RHS,
        op_xor  = LHS ^  RHS
    };

    struct region {
        RECT const* rects;
        size_t count;
        TYPE dx;
        TYPE dy;
        inline region(const region& rhs) 
            : rects(rhs.rects), count(rhs.count), dx(rhs.dx), dy(rhs.dy) { }
        inline region(RECT const* r, size_t c) 
            : rects(r), count(c), dx(), dy() { }
        inline region(RECT const* r, size_t c, TYPE dx, TYPE dy) 
            : rects(r), count(c), dx(dx), dy(dy) { }
    };

    class region_rasterizer {
        friend class region_operator;
        virtual void operator()(const RECT& rect) = 0;
    public:
        virtual ~region_rasterizer() { };
    };
    
    inline region_operator(int op, const region& lhs, const region& rhs) 
        : op_mask(op), spanner(lhs, rhs) 
    {
    }

    void operator()(region_rasterizer& rasterizer) {
        RECT current(Rect::EMPTY_RECT);
        do {
            SpannerInner spannerInner(spanner.lhs, spanner.rhs);
            int inside = spanner.next(current.top, current.bottom);
            spannerInner.prepare(inside);
            do {
                TYPE left, right;
                int inside = spannerInner.next(current.left, current.right);
                if ((op_mask >> inside) & 1) {
                    if (current.left < current.right && 
                            current.top < current.bottom) {
                        rasterizer(current);
                    }
                }
            } while(!spannerInner.isDone());
        } while(!spanner.isDone());
    }

private:    
    uint32_t op_mask;

    class SpannerBase
    {
    public:
        SpannerBase()
            : lhs_head(max_value), lhs_tail(max_value),
              rhs_head(max_value), rhs_tail(max_value) {
        }

        enum {
            lhs_before_rhs   = 0,
            lhs_after_rhs    = 1,
            lhs_coincide_rhs = 2
        };

    protected:
        TYPE lhs_head;
        TYPE lhs_tail;
        TYPE rhs_head;
        TYPE rhs_tail;

        inline int next(TYPE& head, TYPE& tail,
                bool& more_lhs, bool& more_rhs) 
        {
            int inside;
            more_lhs = false;
            more_rhs = false;
            if (lhs_head < rhs_head) {
                inside = lhs_before_rhs;
                head = lhs_head;
                if (lhs_tail <= rhs_head) {
                    tail = lhs_tail;
                    more_lhs = true;
                } else {
                    lhs_head = rhs_head;
                    tail = rhs_head;
                }
            } else if (rhs_head < lhs_head) {
                inside = lhs_after_rhs;
                head = rhs_head;
                if (rhs_tail <= lhs_head) {
                    tail = rhs_tail;
                    more_rhs = true;
                } else {
                    rhs_head = lhs_head;
                    tail = lhs_head;
                }
            } else {
                inside = lhs_coincide_rhs;
                head = lhs_head;
                if (lhs_tail <= rhs_tail) {
                    tail = rhs_head = lhs_tail;
                    more_lhs = true;
                }
                if (rhs_tail <= lhs_tail) {
                    tail = lhs_head = rhs_tail;
                    more_rhs = true;
                }
            }
            return inside;
        }
    };

    class Spanner : protected SpannerBase 
    {
        friend class region_operator;
        region lhs;
        region rhs;

    public:
        inline Spanner(const region& lhs, const region& rhs)
        : lhs(lhs), rhs(rhs)
        {
            if (lhs.count) {
                SpannerBase::lhs_head = lhs.rects->top      + lhs.dy;
                SpannerBase::lhs_tail = lhs.rects->bottom   + lhs.dy;
            }
            if (rhs.count) {
                SpannerBase::rhs_head = rhs.rects->top      + rhs.dy;
                SpannerBase::rhs_tail = rhs.rects->bottom   + rhs.dy;
            }
        }

        inline bool isDone() const {
            return !rhs.count && !lhs.count;
        }

        inline int next(TYPE& top, TYPE& bottom) 
        {
            bool more_lhs = false;
            bool more_rhs = false;
            int inside = SpannerBase::next(top, bottom, more_lhs, more_rhs);
            if (more_lhs) {
                advance(lhs, SpannerBase::lhs_head, SpannerBase::lhs_tail);
            }
            if (more_rhs) {
                advance(rhs, SpannerBase::rhs_head, SpannerBase::rhs_tail);
            }
            return inside;
        }

    private:
        static inline 
        void advance(region& reg, TYPE& aTop, TYPE& aBottom) {
            // got to next span
            size_t count = reg.count;
            RECT const * rects = reg.rects;
            RECT const * const end = rects + count;
            const int top = rects->top;
            while (rects != end && rects->top == top) {
                rects++;
                count--;
            }
            if (rects != end) {
                aTop    = rects->top    + reg.dy;
                aBottom = rects->bottom + reg.dy;
            } else {
                aTop    = max_value;
                aBottom = max_value;
            }
            reg.rects = rects;
            reg.count = count;
        }
    };

    class SpannerInner : protected SpannerBase 
    {
        region lhs;
        region rhs;
        
    public:
        inline SpannerInner(const region& lhs, const region& rhs)
            : lhs(lhs), rhs(rhs) 
        {
        }

        inline void prepare(int inside) {
            if (inside == SpannerBase::lhs_before_rhs) {
                if (lhs.count) {
                    SpannerBase::lhs_head = lhs.rects->left  + lhs.dx;
                    SpannerBase::lhs_tail = lhs.rects->right + lhs.dx;
                }
                SpannerBase::rhs_head = max_value;
                SpannerBase::rhs_tail = max_value;
            } else if (inside == SpannerBase::lhs_after_rhs) {
                SpannerBase::lhs_head = max_value;
                SpannerBase::lhs_tail = max_value;
                if (rhs.count) {
                    SpannerBase::rhs_head = rhs.rects->left  + rhs.dx;
                    SpannerBase::rhs_tail = rhs.rects->right + rhs.dx;
                }
            } else {
                if (lhs.count) {
                    SpannerBase::lhs_head = lhs.rects->left  + lhs.dx;
                    SpannerBase::lhs_tail = lhs.rects->right + lhs.dx;
                }
                if (rhs.count) {
                    SpannerBase::rhs_head = rhs.rects->left  + rhs.dx;
                    SpannerBase::rhs_tail = rhs.rects->right + rhs.dx;
                }
            }
        }

        inline bool isDone() const {
            return SpannerBase::lhs_head == max_value && 
                   SpannerBase::rhs_head == max_value;
        }

        inline int next(TYPE& left, TYPE& right) 
        {
            bool more_lhs = false;
            bool more_rhs = false;
            int inside = SpannerBase::next(left, right, more_lhs, more_rhs);
            if (more_lhs) {
                advance(lhs, SpannerBase::lhs_head, SpannerBase::lhs_tail);
            }
            if (more_rhs) {
                advance(rhs, SpannerBase::rhs_head, SpannerBase::rhs_tail);
            }
            return inside;
        }

    private:
        static inline 
        void advance(region& reg, TYPE& left, TYPE& right) {
            if (reg.rects && reg.count) {
                const int cur_span_top = reg.rects->top;
                reg.rects++;
                reg.count--;
                if (!reg.count || reg.rects->top != cur_span_top) {
                    left  = max_value;
                    right = max_value;
                } else {
                    left  = reg.rects->left  + reg.dx;
                    right = reg.rects->right + reg.dx;
                }
            }
        }
    };

    Spanner spanner;
};

// ----------------------------------------------------------------------------
};

#endif /* ANDROID_UI_PRIVATE_REGION_HELPER_H */