1/*
2 * Copyright (c) 2022 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 *     http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15#ifndef OHOS_ROSEN_WM_OCCLUSION_REGION_H
16#define OHOS_ROSEN_WM_OCCLUSION_REGION_H
17
18#include <refbase.h>
19#include <algorithm>
20#include <iostream>
21#include <vector>
22#include <string>
23
24namespace OHOS::Rosen::WmOcclusion {
25class Rect {
26public:
27    int left_ = 0;
28    int top_ = 0;
29    int right_ = 0;
30    int bottom_ = 0;
31    static Rect _s_empty_rect_;
32    static Rect _s_invalid_rect_;
33
34    Rect() : left_(0), top_(0), right_(0), bottom_(0) {}
35    Rect(int l, int t, int r, int b) : left_(l), top_(t), right_(r), bottom_(b) {}
36
37    std::string GetRectInfo() const
38    {
39        return std::string("[" +
40            std::to_string(left_) + ", " +
41            std::to_string(top_) + ", " +
42            std::to_string(right_ - left_) + ", " +
43            std::to_string(bottom_ - top_) + "]");
44    }
45
46    bool IsEmpty() const
47    {
48        return left_ >= right_ || top_ >= bottom_;
49    }
50};
51
52std::ostream& operator<<(std::ostream& os, const Rect& r);
53
54/*
55    Event: Used for record a rect edge in/out event
56    y_: rect edge Y value
57    type: OPEN/CLOSE: lhs rect in/out; VOID_OPEN/VOID_CLOSE: rhs rect in/out
58*/
59class Event {
60public:
61    // Use different value to differentiate lhs and rhs ranges.
62    enum Type { OPEN = 1, CLOSE = -1, VOID_OPEN = 2, VOID_CLOSE = -2 };
63    int y_ = 0;
64    Type type_ = Type::OPEN;
65    int left_ = 0;
66    int right_ = 0;
67
68    Event(int y, Type type, int l, int r) : y_(y), type_(type), left_(l), right_(r) {}
69};
70
71bool EventSortByY(const Event& e1, const Event& e2);
72
73class Range {
74public:
75    int start_ = 0;
76    int end_ = 0;
77    Range(int start, int end) : start_(start), end_(end) {}
78    bool operator==(const Range& r)
79    {
80        return start_ == r.start_ && end_ == r.end_;
81    }
82};
83
84class Node {
85public:
86    int start_ = 0;
87    int end_ = 0;
88    int mid_ = 0;
89    Node* left_ = nullptr;
90    Node* right_ = nullptr;
91    int positive_count_ = 0; // used for counting current lhs ranges
92    int negative_count_ = 0; // used for counting current rhs ranges
93
94    Node(int s, int e) : start_(s), end_(e), mid_((s + e) >> 1) {}
95    ~Node()
96    {
97        if (right_ != nullptr) {
98            delete right_;
99            right_ = nullptr;
100        }
101        if (left_ != nullptr) {
102            delete left_;
103            left_ = nullptr;
104        }
105    }
106
107    inline bool IsLeaf()
108    {
109        return left_ == nullptr && right_ == nullptr;
110    }
111
112    // push current node [start, end] into range result, merge last range if possible
113    inline void PushRange(std::vector<Range>& res)
114    {
115        if (res.size() > 0 && start_ == res[res.size() - 1].end_) {
116            // merge range with previous range if their end and start share same point
117            res[res.size() - 1].end_ = end_;
118        } else {
119            res.emplace_back(Range { start_, end_ });
120        }
121    }
122
123    // update segment tree
124    void Update(int updateStart, int updateEnd, Event::Type type);
125    // get ranges where positive_count_ or negtive_count_ is positive
126    void GetOrRange(std::vector<Range>& res, bool isParentNodePos, bool isParentNodeNeg);
127    // get ranges where positive_count_ and negtive_count_ are both positive
128    void GetAndRange(std::vector<Range>& res, bool isParentNodePos, bool isParentNodeNeg);
129    // get ranges where positive_count_ is positive and negtive_count_ not
130    void GetSubRange(std::vector<Range>& res, bool isParentNodePos, bool isParentNodeNeg);
131    // get ranges where either positive_count_ and negtive_count_ are both positive
132    void GetXOrRange(std::vector<Range>& res, bool isParentNodePos, bool isParentNodeNeg);
133};
134
135class Region {
136public:
137    enum OP {
138        // bit index 0: lhs
139        // bit index 1: lhs & rhs
140        // bit index 2: rhs
141        AND = 2, // 010
142        OR  = 7, // 111
143        XOR = 5, // 101
144        SUB = 1  // 001
145    };
146
147    Region() = default;
148    explicit Region(Rect& rect)
149    {
150        rects_.push_back(rect);
151        bound_ = Rect { rect };
152    }
153
154    Region(const Region& region) : rects_(region.rects_), bound_(region.bound_) {}
155    Region& operator=(const Region& region)
156    {
157        rects_ = region.rects_;
158        bound_ = region.bound_;
159        return *this;
160    }
161    ~Region() {}
162
163    std::vector<Rect>& GetRegionRects()
164    {
165        return rects_;
166    }
167
168    std::vector<Rect> GetRegionRects() const
169    {
170        return rects_;
171    }
172
173    bool IsEmpty() const
174    {
175        return rects_.size() == 0;
176    }
177
178    int GetSize() const
179    {
180        return rects_.size();
181    }
182
183    Rect& GetBoundRef()
184    {
185        return bound_;
186    }
187
188    Rect GetBound() const
189    {
190        return bound_;
191    }
192
193    std::string GetRegionInfo() const
194    {
195        std::string info = "{ Region Size " + std::to_string(rects_.size()) + ": ";
196        for (auto& rect : rects_) {
197            info.append(rect.GetRectInfo());
198        }
199        info.append(" }");
200        return info;
201    }
202
203    inline size_t Size() const
204    {
205        return rects_.size();
206    }
207
208    inline std::vector<Rect>::const_iterator CBegin() const
209    {
210        return rects_.cbegin();
211    }
212
213    inline std::vector<Rect>::iterator Begin()
214    {
215        return rects_.begin();
216    }
217
218    inline std::vector<Rect>::const_iterator CEnd() const
219    {
220        return rects_.cend();
221    }
222
223    inline std::vector<Rect>::const_iterator End()
224    {
225        return rects_.end();
226    }
227
228    /* core Region logic operation function, the return region's rects is guaranteed no-intersection
229        (rect in rects_ do not intersect with each other)
230    */
231    void RegionOp(Region& r1, Region& r2, Region& res, Region::OP op);
232    void RegionOpLocal(Region& r1, Region& r2, Region& res, Region::OP op);
233    // bound of all region rects
234    void MakeBound();
235
236    // return merge region
237    Region Or(Region& r);
238    // return intersection region
239    Region And(Region& r);
240    // return region belongs to Region(lhs) but not Region(rhs)
241    Region Sub(Region& r);
242    // return merge region subtract intersection region
243    Region Xor(Region& r);
244
245    Region& OperationSelf(Region& r, Region::OP op);
246    // replace region with or result
247    Region& OrSelf(Region& r);
248    // replace region with and result
249    Region& AndSelf(Region& r);
250    // replace region with sub result
251    Region& SubSelf(Region& r);
252    // replace region with xor result
253    Region& XOrSelf(Region& r);
254
255private:
256    class Rects {
257    public:
258        int preY = 0;
259        int curY = 0;
260        std::vector<Rect> preRects;
261        std::vector<Rect> curRects;
262    };
263    // update tmp rects and region according to current ranges
264    void UpdateRects(Rects& r, std::vector<Range>& ranges, std::vector<int>& indexAt, Region& res);
265    // get ranges from segmentTree node according to logical operation type
266    void getRange(std::vector<Range>& ranges, Node& node, OP op);
267
268private:
269    std::vector<Rect> rects_;
270    Rect bound_;
271    static bool _s_so_loaded_;
272};
273std::ostream& operator<<(std::ostream& os, const Region& r);
274} // namespace OHOS::Rosen::Occlusion
275#endif // OHOS_ROSEN_WM_OCCLUSION_REGION_H