1/*
2 * Copyright (C) 2013 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#define LOG_TAG "RegionTest"
18
19#include <stdlib.h>
20#include <ui/Region.h>
21#include <ui/Rect.h>
22#include <gtest/gtest.h>
23
24namespace android {
25
26class RegionTest : public testing::Test {
27protected:
28    void checkVertTJunction(const Rect* lhs, const Rect* rhs) {
29        EXPECT_FALSE((rhs->right > lhs->left && rhs->right < lhs->right) ||
30                (rhs->left > lhs->left && rhs->left < lhs->right));
31    }
32
33    void verifyNoTJunctions(const Region& r) {
34        for (const Rect* current = r.begin(); current < r.end(); current++) {
35            for (const Rect* other = current - 1; other >= r.begin(); other--) {
36                if (other->bottom < current->top) break;
37                if (other->bottom != current->top) continue;
38                checkVertTJunction(current, other);
39            }
40            for (const Rect* other = current + 1; other < r.end(); other++) {
41                if (other->top > current->bottom) break;
42                if (other->top != current->bottom) continue;
43                checkVertTJunction(current, other);
44            }
45        }
46    }
47
48    void checkTJunctionFreeFromRegion(const Region& original, int expectedCount = -1) {
49        Region modified = Region::createTJunctionFreeRegion(original);
50        verifyNoTJunctions(modified);
51        if (expectedCount != -1) {
52            EXPECT_EQ(modified.end() - modified.begin(), expectedCount);
53        }
54        EXPECT_TRUE((original ^ modified).isEmpty());
55    }
56};
57
58TEST_F(RegionTest, MinimalDivision_TJunction) {
59    Region r;
60     // | x |
61     // |xxx|
62    r.clear();
63    r.orSelf(Rect(1, 0, 2, 1));
64    r.orSelf(Rect(0, 1, 3, 2));
65    checkTJunctionFreeFromRegion(r, 4);
66
67     // | x |
68     // |   |
69     // |xxx|
70    r.clear();
71    r.orSelf(Rect(1, 0, 2, 1));
72    r.orSelf(Rect(0, 2, 3, 3));
73    checkTJunctionFreeFromRegion(r, 2);
74}
75
76TEST_F(RegionTest, Trivial_TJunction) {
77    Region r;
78    checkTJunctionFreeFromRegion(r);
79
80    r.orSelf(Rect(100, 100, 500, 500));
81    checkTJunctionFreeFromRegion(r);
82}
83
84TEST_F(RegionTest, Simple_TJunction) {
85    Region r;
86     // | x  |
87     // |xxxx|
88     // |xxxx|
89     // |xxxx|
90    r.clear();
91    r.orSelf(Rect(1, 0, 2, 1));
92    r.orSelf(Rect(0, 1, 3, 3));
93    checkTJunctionFreeFromRegion(r);
94
95     // | x |
96     // |xx |
97     // |xxx|
98    r.clear();
99    r.orSelf(Rect(2,0,4,2));
100    r.orSelf(Rect(0,2,4,4));
101    r.orSelf(Rect(0,4,6,6));
102    checkTJunctionFreeFromRegion(r);
103
104     // |x x|
105     // |xxx|
106     // |x x|
107    r.clear();
108    r.orSelf(Rect(0,0,2,6));
109    r.orSelf(Rect(4,0,6,6));
110    r.orSelf(Rect(0,2,6,4));
111    checkTJunctionFreeFromRegion(r);
112
113     // |xxx|
114     // | x |
115     // | x |
116    r.clear();
117    r.orSelf(Rect(0,0,6,2));
118    r.orSelf(Rect(2,2,4,6));
119    checkTJunctionFreeFromRegion(r);
120}
121
122TEST_F(RegionTest, Bigger_TJunction) {
123    Region r;
124     // |xxxx   |
125     // | xxxx  |
126     // |  xxxx |
127     // |   xxxx|
128    for (int i = 0; i < 4; i++) {
129        r.orSelf(Rect(i,i,i+4,i+1));
130    }
131    checkTJunctionFreeFromRegion(r, 16);
132}
133
134#define ITER_MAX 1000
135#define X_MAX 8
136#define Y_MAX 8
137
138TEST_F(RegionTest, Random_TJunction) {
139    Region r;
140    srandom(12345);
141
142    for (int iter = 0; iter < ITER_MAX; iter++) {
143        r.clear();
144        for (int i = 0; i < X_MAX; i++) {
145            for (int j = 0; j < Y_MAX; j++) {
146                if (random() % 2) {
147                    r.orSelf(Rect(i, j, i + 1, j + 1));
148                }
149            }
150        }
151        checkTJunctionFreeFromRegion(r);
152    }
153}
154
155}; // namespace android
156
157