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#include "wm_occlusion_region.h"
16
17#include <map>
18#include <set>
19
20namespace OHOS::Rosen::WmOcclusion {
21static Rect _s_empty_rect_ { 0, 0, 0, 0 };
22static Rect _s_invalid_rect_ { 0, 0, -1, -1 };
23bool Region::_s_so_loaded_ = false;
24
25std::ostream& operator<<(std::ostream& os, const Rect& r)
26{
27    os << "{" << r.left_ << "," << r.top_ << "," << r.right_ << "," << r.bottom_ << "}";
28    return os;
29}
30
31void Node::Update(int updateStart, int updateEnd, Event::Type type)
32{
33    if (updateStart >= updateEnd) {
34        return;
35    }
36    if (updateStart == start_ && updateEnd == end_) {
37        if (type == Event::Type::CLOSE || type == Event::Type::OPEN) {
38            positive_count_ += type;
39        } else {
40            negative_count_ += type;
41        }
42    } else {
43        if (right_ == nullptr) {
44            right_ = new Node { mid_, end_ };
45        }
46        if (left_ == nullptr) {
47            left_ = new Node { start_, mid_ };
48        }
49
50        if (left_) {
51            left_->Update(updateStart, mid_ < updateEnd ? mid_ : updateEnd, type);
52        }
53        if (right_) {
54            right_->Update(mid_ > updateStart ? mid_ : updateStart, updateEnd, type);
55        }
56    }
57}
58
59bool EventSortByY(const Event& e1, const Event& e2)
60{
61    if (e1.y_ == e2.y_) {
62        return e1.type_ < e2.type_;
63    }
64    return e1.y_ < e2.y_;
65}
66
67void Node::GetOrRange(std::vector<Range>& res, bool isParentNodePos = false, bool isParentNodeNeg = false)
68{
69    bool isNeg = isParentNodeNeg || (negative_count_ > 0);
70    bool isPos = isParentNodePos || (positive_count_ > 0);
71
72    if (isNeg || isPos) {
73        PushRange(res);
74    } else {
75        if (left_ != nullptr) {
76            left_->GetOrRange(res, isPos, isNeg);
77        }
78        if (right_ != nullptr) {
79            right_->GetOrRange(res, isPos, isNeg);
80        }
81    }
82}
83
84void Node::GetAndRange(std::vector<Range>& res, bool isParentNodePos = false, bool isParentNodeNeg = false)
85{
86    bool isNeg = isParentNodeNeg || (negative_count_ > 0);
87    bool isPos = isParentNodePos || (positive_count_ > 0);
88
89    if (isNeg && isPos) {
90        PushRange(res);
91    } else {
92        if (left_ != nullptr) {
93            left_->GetAndRange(res, isPos, isNeg);
94        }
95        if (right_ != nullptr) {
96            right_->GetAndRange(res, isPos, isNeg);
97        }
98    }
99}
100
101void Node::GetSubRange(std::vector<Range>& res, bool isParentNodePos = false, bool isParentNodeNeg = false)
102{
103    bool isNeg = isParentNodeNeg || (negative_count_ > 0);
104    bool isPos = isParentNodePos || (positive_count_ > 0);
105
106    if (isPos && !isNeg && IsLeaf()) {
107        PushRange(res);
108    } else if (isNeg) {
109        return;
110    } else {
111        if (left_ != nullptr) {
112            left_->GetSubRange(res, isPos, isNeg);
113        }
114        if (right_ != nullptr) {
115            right_->GetSubRange(res, isPos, isNeg);
116        }
117    }
118}
119
120void Node::GetXOrRange(std::vector<Range>& res, bool isParentNodePos = false, bool isParentNodeNeg = false)
121{
122    bool isNeg = isParentNodeNeg || (negative_count_ > 0);
123    bool isPos = isParentNodePos || (positive_count_ > 0);
124
125    if (((isPos && !isNeg) || (!isPos && isNeg)) && IsLeaf()) {
126        PushRange(res);
127    } else if (isNeg && isPos) {
128        return;
129    } else {
130        if (left_ != nullptr) {
131            left_->GetXOrRange(res, isPos, isNeg);
132        }
133        if (right_ != nullptr) {
134            right_->GetXOrRange(res, isPos, isNeg);
135        }
136    }
137}
138
139void Region::getRange(std::vector<Range>& ranges, Node& node, Region::OP op)
140{
141    switch (op) {
142        case Region::OP::AND:
143            node.GetAndRange(ranges);
144            break;
145        case Region::OP::SUB:
146            node.GetSubRange(ranges);
147            break;
148        case Region::OP::OR:
149            node.GetOrRange(ranges);
150            break;
151        case Region::OP::XOR:
152            node.GetXOrRange(ranges);
153            break;
154        default:
155            break;
156    }
157    return;
158}
159
160void MakeEnumerate(std::set<int>& ys, std::map<int, int>& indexOf, std::vector<int>& indexAt)
161{
162    int index = 0;
163    auto it = ys.begin();
164    while (it != ys.end()) {
165        indexOf[*it] = index++;
166        indexAt.push_back(*it);
167        ++it;
168    }
169    return;
170}
171
172void Region::UpdateRects(Rects& r, std::vector<Range>& ranges, std::vector<int>& indexAt, Region& res)
173{
174    uint32_t i = 0;
175    uint32_t j = 0;
176    while (i < r.preRects.size() && j < ranges.size()) {
177        if (r.preRects[i].left_ == indexAt[ranges[j].start_] && r.preRects[i].right_ == indexAt[ranges[j].end_]) {
178            r.curRects.emplace_back(Rect { r.preRects[i].left_, r.preRects[i].top_, r.preRects[i].right_, r.curY });
179            j++;
180            i++;
181        } else if (r.preRects[i].right_ < indexAt[ranges[j].end_]) {
182            res.GetRegionRects().push_back(r.preRects[i]);
183            i++;
184        } else {
185            r.curRects.emplace_back(Rect { indexAt[ranges[j].start_], r.preY, indexAt[ranges[j].end_], r.curY });
186            j++;
187        }
188    }
189
190    for (; j < ranges.size(); j++) {
191        r.curRects.emplace_back(Rect { indexAt[ranges[j].start_], r.preY, indexAt[ranges[j].end_], r.curY });
192    }
193    for (; i < r.preRects.size(); i++) {
194        res.GetRegionRects().push_back(r.preRects[i]);
195    }
196    r.preRects.clear();
197    r.preRects.swap(r.curRects);
198    return;
199}
200
201void Region::MakeBound()
202{
203    if (rects_.size()) {
204        bound_ = rects_[0];
205        for (const auto& r : rects_) {
206            bound_.top_ = std::min(r.top_, bound_.top_);
207            bound_.left_ = std::min(r.left_, bound_.left_);
208            bound_.right_ = std::max(r.right_, bound_.right_);
209            bound_.bottom_ = std::max(r.bottom_, bound_.bottom_);
210        }
211    }
212}
213
214void Region::RegionOpLocal(Region& r1, Region& r2, Region& res, Region::OP op)
215{
216    r1.MakeBound();
217    r2.MakeBound();
218    res.GetRegionRects().clear();
219    std::set<int> xs;
220    std::vector<Event> events;
221
222    for (auto& rect : r1.GetRegionRects()) {
223        events.emplace_back(Event { rect.top_, Event::Type::OPEN, rect.left_, rect.right_ });
224        events.emplace_back(Event { rect.bottom_, Event::Type::CLOSE, rect.left_, rect.right_ });
225        xs.insert(rect.left_);
226        xs.insert(rect.right_);
227    }
228    for (auto& rect : r2.GetRegionRects()) {
229        events.emplace_back(Event { rect.top_, Event::Type::VOID_OPEN, rect.left_, rect.right_ });
230        events.emplace_back(Event { rect.bottom_, Event::Type::VOID_CLOSE, rect.left_, rect.right_ });
231        xs.insert(rect.left_);
232        xs.insert(rect.right_);
233    }
234
235    if (events.empty()) {
236        return;
237    }
238
239    std::vector<int> indexAt;
240    std::map<int, int> indexOf;
241    MakeEnumerate(xs, indexOf, indexAt);
242    sort(events.begin(), events.end(), EventSortByY);
243    size_t indexOfSize = indexOf.size() > 0 ? (indexOf.size() - 1) : 0;
244    Node rootNode { 0, static_cast<int>(indexOfSize) };
245
246    std::vector<Range> ranges;
247    Rects r;
248    r.curY = events[0].y_;
249    r.preY = events[0].y_;
250    for (auto& event : events) {
251        r.curY = event.y_;
252        ranges.clear();
253        getRange(ranges, rootNode, op);
254        if (r.curY > r.preY) {
255            UpdateRects(r, ranges, indexAt, res);
256        }
257        rootNode.Update(indexOf[event.left_], indexOf[event.right_], event.type_);
258        r.preY = r.curY;
259    }
260    copy(r.preRects.begin(), r.preRects.end(), back_inserter(res.GetRegionRects()));
261    res.MakeBound();
262}
263
264void Region::RegionOp(Region& r1, Region& r2, Region& res, Region::OP op)
265{
266    RegionOpLocal(r1, r2, res, op);
267}
268
269Region& Region::OperationSelf(Region& r, Region::OP op)
270{
271    Region r1(*this);
272    RegionOp(r1, r, *this, op);
273    return *this;
274}
275
276Region Region::Or(Region& r)
277{
278    Region res;
279    RegionOp(*this, r, res, Region::OP::OR);
280    return res;
281}
282
283Region Region::And(Region& r)
284{
285    Region res;
286    RegionOp(*this, r, res, Region::OP::AND);
287    return res;
288}
289
290Region Region::Sub(Region& r)
291{
292    Region res;
293    RegionOp(*this, r, res, Region::OP::SUB);
294    return res;
295}
296
297Region Region::Xor(Region& r)
298{
299    Region res;
300    RegionOp(*this, r, res, Region::OP::XOR);
301    return res;
302}
303
304Region& Region::OrSelf(Region& r)
305{
306    return OperationSelf(r, Region::OP::OR);
307}
308
309Region& Region::AndSelf(Region& r)
310{
311    return OperationSelf(r, Region::OP::AND);
312}
313
314Region& Region::SubSelf(Region& r)
315{
316    return OperationSelf(r, Region::OP::SUB);
317}
318
319Region& Region::XOrSelf(Region& r)
320{
321    return OperationSelf(r, Region::OP::XOR);
322}
323
324std::ostream& operator<<(std::ostream& os, const Region& r)
325{
326    os << "{";
327    os << r.GetSize() << ": ";
328    for (const Rect& regionRect : r.GetRegionRects()) {
329        os << regionRect;
330    }
331    os << "}" << std::endl;
332    return os;
333}
334} // namespace OHOS