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
24 namespace android {
25
26 class RegionTest : public testing::Test {
27 protected:
checkVertTJunction(const Rect * lhs,const Rect * rhs)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
verifyNoTJunctions(const Region & r)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
checkTJunctionFreeFromRegion(const Region & original,int expectedCount=-1)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
TEST_F(RegionTest,MinimalDivision_TJunction)58 TEST_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
TEST_F(RegionTest,Trivial_TJunction)76 TEST_F(RegionTest, Trivial_TJunction) {
77 Region r;
78 checkTJunctionFreeFromRegion(r);
79
80 r.orSelf(Rect(100, 100, 500, 500));
81 checkTJunctionFreeFromRegion(r);
82 }
83
TEST_F(RegionTest,Simple_TJunction)84 TEST_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
TEST_F(RegionTest,Bigger_TJunction)122 TEST_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
TEST_F(RegionTest,Random_TJunction)138 TEST_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