41TEST(DisplayListRTree, ManySizes) {
47 const int kMaxN = 250;
50 for (
int i = 0; i <= kMaxN; i++) {
51 rects[i].
setXYWH(i * 20, i * 20, 10, 10);
54 std::vector<int> results;
55 for (
int N = 0;
N <= kMaxN;
N++) {
57 auto desc =
"node count = " + std::to_string(
N);
60 EXPECT_EQ(tree.
id(-1), -1) << desc;
62 EXPECT_EQ(tree.
id(
N), -1) << desc;
66 EXPECT_EQ(results.size(), 0u) << desc;
70 EXPECT_EQ(results.size(), 0u) << desc;
72 EXPECT_EQ(results.size(), 1u) << desc;
73 EXPECT_EQ(results[0], 0) << desc;
74 EXPECT_EQ(tree.
id(results[0]), ids[0]) << desc;
75 EXPECT_EQ(tree.
bounds(results[0]), rects[0]) << desc;
76 for (
int i = 1; i <
N; i++) {
79 tree.
search(query, &results);
80 EXPECT_EQ(results.size(), 1u) << desc;
81 EXPECT_EQ(results[0], i) << desc;
82 EXPECT_EQ(tree.
id(results[0]), ids[i]) << desc;
83 EXPECT_EQ(tree.
bounds(results[0]), rects[i]) << desc;
85 EXPECT_EQ(list.size(), 1u);
86 EXPECT_EQ(list.front(), rects[i]);
92TEST(DisplayListRTree, HugeSize) {
101 for (
int i = 0; i <
N; i++) {
102 rects[i].
setXYWH(i * 20, i * 20, 10, 10);
108 EXPECT_EQ(tree.
id(-1), -1);
110 EXPECT_EQ(tree.
id(
N), -1);
112 std::vector<int> results;
114 EXPECT_EQ(results.size(), 0u);
115 for (
int i = 0; i <
N; i++) {
118 EXPECT_EQ(results.size(), 1u);
119 EXPECT_EQ(results[0], i);
120 EXPECT_EQ(tree.
id(results[0]), ids[i]);
121 EXPECT_EQ(tree.
bounds(results[0]), rects[i]);
133 const int N = ROWS * COLS;
136 for (
int r = 0; r < ROWS; r++) {
138 for (
int c = 0; c < COLS; c++) {
140 int i = r * COLS + c;
148 EXPECT_EQ(tree.
id(-1), -1);
150 EXPECT_EQ(tree.
id(
N), -1);
152 std::vector<int> results;
154 EXPECT_EQ(results.size(), 0u);
156 for (
int r = 0; r < ROWS; r++) {
158 for (
int c = 0; c < COLS; c++) {
160 int i = r * COLS + c;
162 "row " + std::to_string(r + 1) +
", col " + std::to_string(c + 1);
165 tree.
search(query, &results);
166 EXPECT_EQ(results.size(), 1u) << desc;
167 EXPECT_EQ(results[0], i) << desc;
168 EXPECT_EQ(tree.
id(results[0]), ids[i]) << desc;
169 EXPECT_EQ(tree.
bounds(results[0]), rects[i]) << desc;
171 EXPECT_EQ(list.size(), 1u);
172 EXPECT_EQ(list.front(), rects[i]);
176 for (
int r = 1; r < ROWS; r++) {
178 for (
int c = 1; c < COLS; c++) {
181 "row " + std::to_string(r + 1) +
", col " + std::to_string(c + 1);
184 tree.
search(query, &results);
185 EXPECT_EQ(results.size(), 0u) << desc;
187 EXPECT_EQ(list.size(), 0u) << desc;
191 for (
int r = 1; r < ROWS; r++) {
193 for (
int c = 1; c < COLS; c++) {
196 int i = r * COLS + c;
198 "row " + std::to_string(r + 1) +
", col " + std::to_string(c + 1);
201 tree.
search(query, &results);
202 EXPECT_EQ(results.size(), 4u) << desc;
205 EXPECT_EQ(results[0], i - COLS - 1) << desc;
206 EXPECT_EQ(tree.
id(results[0]), ids[i - COLS - 1]) << desc;
207 EXPECT_EQ(tree.
bounds(results[0]), rects[i - COLS - 1]) << desc;
210 EXPECT_EQ(results[1], i - COLS) << desc;
211 EXPECT_EQ(tree.
id(results[1]), ids[i - COLS]) << desc;
212 EXPECT_EQ(tree.
bounds(results[1]), rects[i - COLS]) << desc;
215 EXPECT_EQ(results[2], i - 1) << desc;
216 EXPECT_EQ(tree.
id(results[2]), ids[i - 1]) << desc;
217 EXPECT_EQ(tree.
bounds(results[2]), rects[i - 1]) << desc;
220 EXPECT_EQ(results[3], i) << desc;
221 EXPECT_EQ(tree.
id(results[3]), ids[i]) << desc;
222 EXPECT_EQ(tree.
bounds(results[3]), rects[i]) << desc;
225 EXPECT_EQ(list.size(), 4u);
226 list.remove(rects[i - COLS - 1]);
227 list.remove(rects[i - COLS]);
228 list.remove(rects[i - 1]);
229 list.remove(rects[i]);
230 EXPECT_EQ(list.size(), 0u);
235TEST(DisplayListRTree, OverlappingRects) {
258 for (
int r = 0; r < 3; r++) {
260 for (
int c = 0; c < 3; c++) {
262 rects[r * 3 + c].
setLTRB(
x - 15,
y - 15,
x + 15,
y + 15);
267 for (
int r = 0; r < 3; r++) {
269 for (
int c = 0; c < 3; c++) {
273 EXPECT_EQ(list.size(), 1u);
274 EXPECT_EQ(list.front(), rects[r * 3 + c]);
278 for (
int r = 0; r < 3; r++) {
284 EXPECT_EQ(list.size(), 1u);
288 for (
int c = 0; c < 3; c++) {
294 EXPECT_EQ(list.size(), 1u);
300 EXPECT_EQ(list.size(), 1u);