13e010f3138593cc6953039ee0e3db8ee31881296Chris Craik/* 23e010f3138593cc6953039ee0e3db8ee31881296Chris Craik * Copyright (C) 2013 The Android Open Source Project 33e010f3138593cc6953039ee0e3db8ee31881296Chris Craik * 43e010f3138593cc6953039ee0e3db8ee31881296Chris Craik * Licensed under the Apache License, Version 2.0 (the "License"); 53e010f3138593cc6953039ee0e3db8ee31881296Chris Craik * you may not use this file except in compliance with the License. 63e010f3138593cc6953039ee0e3db8ee31881296Chris Craik * You may obtain a copy of the License at 73e010f3138593cc6953039ee0e3db8ee31881296Chris Craik * 83e010f3138593cc6953039ee0e3db8ee31881296Chris Craik * http://www.apache.org/licenses/LICENSE-2.0 93e010f3138593cc6953039ee0e3db8ee31881296Chris Craik * 103e010f3138593cc6953039ee0e3db8ee31881296Chris Craik * Unless required by applicable law or agreed to in writing, software 113e010f3138593cc6953039ee0e3db8ee31881296Chris Craik * distributed under the License is distributed on an "AS IS" BASIS, 123e010f3138593cc6953039ee0e3db8ee31881296Chris Craik * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 133e010f3138593cc6953039ee0e3db8ee31881296Chris Craik * See the License for the specific language governing permissions and 143e010f3138593cc6953039ee0e3db8ee31881296Chris Craik * limitations under the License. 153e010f3138593cc6953039ee0e3db8ee31881296Chris Craik */ 163e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 173e010f3138593cc6953039ee0e3db8ee31881296Chris Craik#define LOG_TAG "RegionTest" 183e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 193e010f3138593cc6953039ee0e3db8ee31881296Chris Craik#include <stdlib.h> 203e010f3138593cc6953039ee0e3db8ee31881296Chris Craik#include <ui/Region.h> 213e010f3138593cc6953039ee0e3db8ee31881296Chris Craik#include <ui/Rect.h> 223e010f3138593cc6953039ee0e3db8ee31881296Chris Craik#include <gtest/gtest.h> 233e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 243e010f3138593cc6953039ee0e3db8ee31881296Chris Craiknamespace android { 253e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 263e010f3138593cc6953039ee0e3db8ee31881296Chris Craikclass RegionTest : public testing::Test { 273e010f3138593cc6953039ee0e3db8ee31881296Chris Craikprotected: 283e010f3138593cc6953039ee0e3db8ee31881296Chris Craik void checkVertTJunction(const Rect* lhs, const Rect* rhs) { 293e010f3138593cc6953039ee0e3db8ee31881296Chris Craik EXPECT_FALSE((rhs->right > lhs->left && rhs->right < lhs->right) || 303e010f3138593cc6953039ee0e3db8ee31881296Chris Craik (rhs->left > lhs->left && rhs->left < lhs->right)); 313e010f3138593cc6953039ee0e3db8ee31881296Chris Craik } 323e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 333e010f3138593cc6953039ee0e3db8ee31881296Chris Craik void verifyNoTJunctions(const Region& r) { 343e010f3138593cc6953039ee0e3db8ee31881296Chris Craik for (const Rect* current = r.begin(); current < r.end(); current++) { 353e010f3138593cc6953039ee0e3db8ee31881296Chris Craik for (const Rect* other = current - 1; other >= r.begin(); other--) { 363e010f3138593cc6953039ee0e3db8ee31881296Chris Craik if (other->bottom < current->top) break; 373e010f3138593cc6953039ee0e3db8ee31881296Chris Craik if (other->bottom != current->top) continue; 383e010f3138593cc6953039ee0e3db8ee31881296Chris Craik checkVertTJunction(current, other); 393e010f3138593cc6953039ee0e3db8ee31881296Chris Craik } 403e010f3138593cc6953039ee0e3db8ee31881296Chris Craik for (const Rect* other = current + 1; other < r.end(); other++) { 413e010f3138593cc6953039ee0e3db8ee31881296Chris Craik if (other->top > current->bottom) break; 423e010f3138593cc6953039ee0e3db8ee31881296Chris Craik if (other->top != current->bottom) continue; 433e010f3138593cc6953039ee0e3db8ee31881296Chris Craik checkVertTJunction(current, other); 443e010f3138593cc6953039ee0e3db8ee31881296Chris Craik } 453e010f3138593cc6953039ee0e3db8ee31881296Chris Craik } 463e010f3138593cc6953039ee0e3db8ee31881296Chris Craik } 473e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 483e010f3138593cc6953039ee0e3db8ee31881296Chris Craik void checkTJunctionFreeFromRegion(const Region& original, int expectedCount = -1) { 493e010f3138593cc6953039ee0e3db8ee31881296Chris Craik Region modified = Region::createTJunctionFreeRegion(original); 503e010f3138593cc6953039ee0e3db8ee31881296Chris Craik verifyNoTJunctions(modified); 513e010f3138593cc6953039ee0e3db8ee31881296Chris Craik if (expectedCount != -1) { 523e010f3138593cc6953039ee0e3db8ee31881296Chris Craik EXPECT_EQ(modified.end() - modified.begin(), expectedCount); 533e010f3138593cc6953039ee0e3db8ee31881296Chris Craik } 543e010f3138593cc6953039ee0e3db8ee31881296Chris Craik EXPECT_TRUE((original ^ modified).isEmpty()); 553e010f3138593cc6953039ee0e3db8ee31881296Chris Craik } 563e010f3138593cc6953039ee0e3db8ee31881296Chris Craik}; 573e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 583e010f3138593cc6953039ee0e3db8ee31881296Chris CraikTEST_F(RegionTest, MinimalDivision_TJunction) { 593e010f3138593cc6953039ee0e3db8ee31881296Chris Craik Region r; 603e010f3138593cc6953039ee0e3db8ee31881296Chris Craik // | x | 613e010f3138593cc6953039ee0e3db8ee31881296Chris Craik // |xxx| 623e010f3138593cc6953039ee0e3db8ee31881296Chris Craik r.clear(); 633e010f3138593cc6953039ee0e3db8ee31881296Chris Craik r.orSelf(Rect(1, 0, 2, 1)); 643e010f3138593cc6953039ee0e3db8ee31881296Chris Craik r.orSelf(Rect(0, 1, 3, 2)); 653e010f3138593cc6953039ee0e3db8ee31881296Chris Craik checkTJunctionFreeFromRegion(r, 4); 663e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 673e010f3138593cc6953039ee0e3db8ee31881296Chris Craik // | x | 683e010f3138593cc6953039ee0e3db8ee31881296Chris Craik // | | 693e010f3138593cc6953039ee0e3db8ee31881296Chris Craik // |xxx| 703e010f3138593cc6953039ee0e3db8ee31881296Chris Craik r.clear(); 713e010f3138593cc6953039ee0e3db8ee31881296Chris Craik r.orSelf(Rect(1, 0, 2, 1)); 723e010f3138593cc6953039ee0e3db8ee31881296Chris Craik r.orSelf(Rect(0, 2, 3, 3)); 733e010f3138593cc6953039ee0e3db8ee31881296Chris Craik checkTJunctionFreeFromRegion(r, 2); 743e010f3138593cc6953039ee0e3db8ee31881296Chris Craik} 753e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 763e010f3138593cc6953039ee0e3db8ee31881296Chris CraikTEST_F(RegionTest, Trivial_TJunction) { 773e010f3138593cc6953039ee0e3db8ee31881296Chris Craik Region r; 783e010f3138593cc6953039ee0e3db8ee31881296Chris Craik checkTJunctionFreeFromRegion(r); 793e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 803e010f3138593cc6953039ee0e3db8ee31881296Chris Craik r.orSelf(Rect(100, 100, 500, 500)); 813e010f3138593cc6953039ee0e3db8ee31881296Chris Craik checkTJunctionFreeFromRegion(r); 823e010f3138593cc6953039ee0e3db8ee31881296Chris Craik} 833e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 843e010f3138593cc6953039ee0e3db8ee31881296Chris CraikTEST_F(RegionTest, Simple_TJunction) { 853e010f3138593cc6953039ee0e3db8ee31881296Chris Craik Region r; 863e010f3138593cc6953039ee0e3db8ee31881296Chris Craik // | x | 873e010f3138593cc6953039ee0e3db8ee31881296Chris Craik // |xxxx| 883e010f3138593cc6953039ee0e3db8ee31881296Chris Craik // |xxxx| 893e010f3138593cc6953039ee0e3db8ee31881296Chris Craik // |xxxx| 903e010f3138593cc6953039ee0e3db8ee31881296Chris Craik r.clear(); 913e010f3138593cc6953039ee0e3db8ee31881296Chris Craik r.orSelf(Rect(1, 0, 2, 1)); 923e010f3138593cc6953039ee0e3db8ee31881296Chris Craik r.orSelf(Rect(0, 1, 3, 3)); 933e010f3138593cc6953039ee0e3db8ee31881296Chris Craik checkTJunctionFreeFromRegion(r); 943e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 953e010f3138593cc6953039ee0e3db8ee31881296Chris Craik // | x | 963e010f3138593cc6953039ee0e3db8ee31881296Chris Craik // |xx | 973e010f3138593cc6953039ee0e3db8ee31881296Chris Craik // |xxx| 983e010f3138593cc6953039ee0e3db8ee31881296Chris Craik r.clear(); 993e010f3138593cc6953039ee0e3db8ee31881296Chris Craik r.orSelf(Rect(2,0,4,2)); 1003e010f3138593cc6953039ee0e3db8ee31881296Chris Craik r.orSelf(Rect(0,2,4,4)); 1013e010f3138593cc6953039ee0e3db8ee31881296Chris Craik r.orSelf(Rect(0,4,6,6)); 1023e010f3138593cc6953039ee0e3db8ee31881296Chris Craik checkTJunctionFreeFromRegion(r); 1033e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 1043e010f3138593cc6953039ee0e3db8ee31881296Chris Craik // |x x| 1053e010f3138593cc6953039ee0e3db8ee31881296Chris Craik // |xxx| 1063e010f3138593cc6953039ee0e3db8ee31881296Chris Craik // |x x| 1073e010f3138593cc6953039ee0e3db8ee31881296Chris Craik r.clear(); 1083e010f3138593cc6953039ee0e3db8ee31881296Chris Craik r.orSelf(Rect(0,0,2,6)); 1093e010f3138593cc6953039ee0e3db8ee31881296Chris Craik r.orSelf(Rect(4,0,6,6)); 1103e010f3138593cc6953039ee0e3db8ee31881296Chris Craik r.orSelf(Rect(0,2,6,4)); 1113e010f3138593cc6953039ee0e3db8ee31881296Chris Craik checkTJunctionFreeFromRegion(r); 1123e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 1133e010f3138593cc6953039ee0e3db8ee31881296Chris Craik // |xxx| 1143e010f3138593cc6953039ee0e3db8ee31881296Chris Craik // | x | 1153e010f3138593cc6953039ee0e3db8ee31881296Chris Craik // | x | 1163e010f3138593cc6953039ee0e3db8ee31881296Chris Craik r.clear(); 1173e010f3138593cc6953039ee0e3db8ee31881296Chris Craik r.orSelf(Rect(0,0,6,2)); 1183e010f3138593cc6953039ee0e3db8ee31881296Chris Craik r.orSelf(Rect(2,2,4,6)); 1193e010f3138593cc6953039ee0e3db8ee31881296Chris Craik checkTJunctionFreeFromRegion(r); 1203e010f3138593cc6953039ee0e3db8ee31881296Chris Craik} 1213e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 1223e010f3138593cc6953039ee0e3db8ee31881296Chris CraikTEST_F(RegionTest, Bigger_TJunction) { 1233e010f3138593cc6953039ee0e3db8ee31881296Chris Craik Region r; 1243e010f3138593cc6953039ee0e3db8ee31881296Chris Craik // |xxxx | 1253e010f3138593cc6953039ee0e3db8ee31881296Chris Craik // | xxxx | 1263e010f3138593cc6953039ee0e3db8ee31881296Chris Craik // | xxxx | 1273e010f3138593cc6953039ee0e3db8ee31881296Chris Craik // | xxxx| 1283e010f3138593cc6953039ee0e3db8ee31881296Chris Craik for (int i = 0; i < 4; i++) { 1293e010f3138593cc6953039ee0e3db8ee31881296Chris Craik r.orSelf(Rect(i,i,i+4,i+1)); 1303e010f3138593cc6953039ee0e3db8ee31881296Chris Craik } 1313e010f3138593cc6953039ee0e3db8ee31881296Chris Craik checkTJunctionFreeFromRegion(r, 16); 1323e010f3138593cc6953039ee0e3db8ee31881296Chris Craik} 1333e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 1343e010f3138593cc6953039ee0e3db8ee31881296Chris Craik#define ITER_MAX 1000 1353e010f3138593cc6953039ee0e3db8ee31881296Chris Craik#define X_MAX 8 1363e010f3138593cc6953039ee0e3db8ee31881296Chris Craik#define Y_MAX 8 1373e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 1383e010f3138593cc6953039ee0e3db8ee31881296Chris CraikTEST_F(RegionTest, Random_TJunction) { 1393e010f3138593cc6953039ee0e3db8ee31881296Chris Craik Region r; 1403e010f3138593cc6953039ee0e3db8ee31881296Chris Craik srandom(12345); 1413e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 1423e010f3138593cc6953039ee0e3db8ee31881296Chris Craik for (int iter = 0; iter < ITER_MAX; iter++) { 1433e010f3138593cc6953039ee0e3db8ee31881296Chris Craik r.clear(); 1443e010f3138593cc6953039ee0e3db8ee31881296Chris Craik for (int i = 0; i < X_MAX; i++) { 1453e010f3138593cc6953039ee0e3db8ee31881296Chris Craik for (int j = 0; j < Y_MAX; j++) { 1463e010f3138593cc6953039ee0e3db8ee31881296Chris Craik if (random() % 2) { 1473e010f3138593cc6953039ee0e3db8ee31881296Chris Craik r.orSelf(Rect(i, j, i + 1, j + 1)); 1483e010f3138593cc6953039ee0e3db8ee31881296Chris Craik } 1493e010f3138593cc6953039ee0e3db8ee31881296Chris Craik } 1503e010f3138593cc6953039ee0e3db8ee31881296Chris Craik } 1513e010f3138593cc6953039ee0e3db8ee31881296Chris Craik checkTJunctionFreeFromRegion(r); 1523e010f3138593cc6953039ee0e3db8ee31881296Chris Craik } 1533e010f3138593cc6953039ee0e3db8ee31881296Chris Craik} 1543e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 1553e010f3138593cc6953039ee0e3db8ee31881296Chris Craik}; // namespace android 1563e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 157