display_list/geometry/dl_rtree_unittests.cc - mirrors/engine - Git at Google

 // Copyright 2013 The Flutter Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.

 #include "flutter/display_list/geometry/dl_rtree.h"
 #include "gtest/gtest.h"

 #include "third_party/skia/include/core/SkRect.h"

 namespace flutter {
 namespace testing {

 #ifndef NDEBUG
 TEST(DisplayListRTree, NullRectListNonZeroCount) {
   EXPECT_DEATH_IF_SUPPORTED(new DlRTree(nullptr, 1), "rects != nullptr");
 }

 TEST(DisplayListRTree, NegativeCount) {
   EXPECT_DEATH_IF_SUPPORTED(new DlRTree(nullptr, -1), "N >= 0");
 }

 TEST(DisplayListRTree, NullSearchResultVector) {
   DlRTree tree(nullptr, 0);
   EXPECT_DEATH_IF_SUPPORTED(tree.search(SkRect::MakeLTRB(0, 0, 1, 1), nullptr),
                             "results != nullptr");
 }
 #endif

 TEST(DisplayListRTree, NullRectListZeroCount) {
   DlRTree tree(nullptr, 0);
   EXPECT_EQ(tree.leaf_count(), 0);
   EXPECT_EQ(tree.node_count(), 0);
   std::vector<int> results;
   auto huge = SkRect::MakeLTRB(-1e6, -1e6, 1e6, 1e6);
   tree.search(huge, &results);
   EXPECT_EQ(results.size(), 0u);
   auto list = tree.searchAndConsolidateRects(huge);
   EXPECT_EQ(list.size(), 0u);
 }

 TEST(DisplayListRTree, ManySizes) {
   // A diagonal of non-overlapping 10x10 rectangles spaced 20
   // pixels apart.
   // Rect 1 goes from  0 to 10
   // Rect 2 goes from 20 to 30
   // etc. in both dimensions
   const int kMaxN = 250;
   SkRect rects[kMaxN + 1];
   int ids[kMaxN + 1];
   for (int i = 0; i <= kMaxN; i++) {
     rects[i].setXYWH(i * 20, i * 20, 10, 10);
     ids[i] = i + 42;
   }
   std::vector<int> results;
   for (int N = 0; N <= kMaxN; N++) {
     DlRTree tree(rects, N, ids);
     auto desc = "node count = " + std::to_string(N);
     EXPECT_EQ(tree.leaf_count(), N) << desc;
     EXPECT_GE(tree.node_count(), N) << desc;
     EXPECT_EQ(tree.id(-1), -1) << desc;
     EXPECT_EQ(tree.bounds(-1), SkRect::MakeEmpty()) << desc;
     EXPECT_EQ(tree.id(N), -1) << desc;
     EXPECT_EQ(tree.bounds(N), SkRect::MakeEmpty()) << desc;
     results.clear();
     tree.search(SkRect::MakeEmpty(), &results);
     EXPECT_EQ(results.size(), 0u) << desc;
     results.clear();
     tree.search(SkRect::MakeLTRB(2, 2, 8, 8), &results);
     if (N == 0) {
       EXPECT_EQ(results.size(), 0u) << desc;
     } else {
       EXPECT_EQ(results.size(), 1u) << desc;
       EXPECT_EQ(results[0], 0) << desc;
       EXPECT_EQ(tree.id(results[0]), ids[0]) << desc;
       EXPECT_EQ(tree.bounds(results[0]), rects[0]) << desc;
       for (int i = 1; i < N; i++) {
         results.clear();
         auto query = SkRect::MakeXYWH(i * 20 + 2, i * 20 + 2, 6, 6);
         tree.search(query, &results);
         EXPECT_EQ(results.size(), 1u) << desc;
         EXPECT_EQ(results[0], i) << desc;
         EXPECT_EQ(tree.id(results[0]), ids[i]) << desc;
         EXPECT_EQ(tree.bounds(results[0]), rects[i]) << desc;
         auto list = tree.searchAndConsolidateRects(query);
         EXPECT_EQ(list.size(), 1u);
         EXPECT_EQ(list.front(), rects[i]);
       }
     }
   }
 }

 TEST(DisplayListRTree, HugeSize) {
   // A diagonal of non-overlapping 10x10 rectangles spaced 20
   // pixels apart.
   // Rect 1 goes from  0 to 10
   // Rect 2 goes from 20 to 30
   // etc. in both dimensions
   const int N = 10000;
   SkRect rects[N];
   int ids[N];
   for (int i = 0; i < N; i++) {
     rects[i].setXYWH(i * 20, i * 20, 10, 10);
     ids[i] = i + 42;
   }
   DlRTree tree(rects, N, ids);
   EXPECT_EQ(tree.leaf_count(), N);
   EXPECT_GE(tree.node_count(), N);
   EXPECT_EQ(tree.id(-1), -1);
   EXPECT_EQ(tree.bounds(-1), SkRect::MakeEmpty());
   EXPECT_EQ(tree.id(N), -1);
   EXPECT_EQ(tree.bounds(N), SkRect::MakeEmpty());
   std::vector<int> results;
   tree.search(SkRect::MakeEmpty(), &results);
   EXPECT_EQ(results.size(), 0u);
   for (int i = 0; i < N; i++) {
     results.clear();
     tree.search(SkRect::MakeXYWH(i * 20 + 2, i * 20 + 2, 6, 6), &results);
     EXPECT_EQ(results.size(), 1u);
     EXPECT_EQ(results[0], i);
     EXPECT_EQ(tree.id(results[0]), ids[i]);
     EXPECT_EQ(tree.bounds(results[0]), rects[i]);
   }
 }

 TEST(DisplayListRTree, Grid) {
   // Non-overlapping 10 x 10 rectangles starting at 5, 5 with
   // 10 pixels between them.
   // Rect 1 goes from  5 to 15
   // Rect 2 goes from 25 to 35
   // etc. in both dimensions
   const int ROWS = 10;
   const int COLS = 10;
   const int N = ROWS * COLS;
   SkRect rects[N];
   int ids[N];
   for (int r = 0; r < ROWS; r++) {
     int y = r * 20 + 5;
     for (int c = 0; c < COLS; c++) {
       int x = c * 20 + 5;
       int i = r * COLS + c;
       rects[i] = SkRect::MakeXYWH(x, y, 10, 10);
       ids[i] = i + 42;
     }
   }
   DlRTree tree(rects, N, ids);
   EXPECT_EQ(tree.leaf_count(), N);
   EXPECT_GE(tree.node_count(), N);
   EXPECT_EQ(tree.id(-1), -1);
   EXPECT_EQ(tree.bounds(-1), SkRect::MakeEmpty());
   EXPECT_EQ(tree.id(N), -1);
   EXPECT_EQ(tree.bounds(N), SkRect::MakeEmpty());
   std::vector<int> results;
   tree.search(SkRect::MakeEmpty(), &results);
   EXPECT_EQ(results.size(), 0u);
   // Testing eqch rect for a single hit
   for (int r = 0; r < ROWS; r++) {
     int y = r * 20 + 5;
     for (int c = 0; c < COLS; c++) {
       int x = c * 20 + 5;
       int i = r * COLS + c;
       auto desc =
           "row " + std::to_string(r + 1) + ", col " + std::to_string(c + 1);
       results.clear();
       auto query = SkRect::MakeXYWH(x + 2, y + 2, 6, 6);
       tree.search(query, &results);
       EXPECT_EQ(results.size(), 1u) << desc;
       EXPECT_EQ(results[0], i) << desc;
       EXPECT_EQ(tree.id(results[0]), ids[i]) << desc;
       EXPECT_EQ(tree.bounds(results[0]), rects[i]) << desc;
       auto list = tree.searchAndConsolidateRects(query);
       EXPECT_EQ(list.size(), 1u);
       EXPECT_EQ(list.front(), rects[i]);
     }
   }
   // Testing inside each gap for no hits
   for (int r = 1; r < ROWS; r++) {
     int y = r * 20 + 5;
     for (int c = 1; c < COLS; c++) {
       int x = c * 20 + 5;
       auto desc =
           "row " + std::to_string(r + 1) + ", col " + std::to_string(c + 1);
       results.clear();
       auto query = SkRect::MakeXYWH(x - 8, y - 8, 6, 6);
       tree.search(query, &results);
       EXPECT_EQ(results.size(), 0u) << desc;
       auto list = tree.searchAndConsolidateRects(query);
       EXPECT_EQ(list.size(), 0u) << desc;
     }
   }
   // Spanning each gap for a quad of hits
   for (int r = 1; r < ROWS; r++) {
     int y = r * 20 + 5;
     for (int c = 1; c < COLS; c++) {
       int x = c * 20 + 5;
       // We will hit this rect and the ones above/left of us
       int i = r * COLS + c;
       auto desc =
           "row " + std::to_string(r + 1) + ", col " + std::to_string(c + 1);
       results.clear();
       auto query = SkRect::MakeXYWH(x - 11, y - 11, 12, 12);
       tree.search(query, &results);
       EXPECT_EQ(results.size(), 4u) << desc;

       // First rect is above and to the left
       EXPECT_EQ(results[0], i - COLS - 1) << desc;
       EXPECT_EQ(tree.id(results[0]), ids[i - COLS - 1]) << desc;
       EXPECT_EQ(tree.bounds(results[0]), rects[i - COLS - 1]) << desc;

       // Second rect is above
       EXPECT_EQ(results[1], i - COLS) << desc;
       EXPECT_EQ(tree.id(results[1]), ids[i - COLS]) << desc;
       EXPECT_EQ(tree.bounds(results[1]), rects[i - COLS]) << desc;

       // Third rect is left
       EXPECT_EQ(results[2], i - 1) << desc;
       EXPECT_EQ(tree.id(results[2]), ids[i - 1]) << desc;
       EXPECT_EQ(tree.bounds(results[2]), rects[i - 1]) << desc;

       // Fourth rect is us
       EXPECT_EQ(results[3], i) << desc;
       EXPECT_EQ(tree.id(results[3]), ids[i]) << desc;
       EXPECT_EQ(tree.bounds(results[3]), rects[i]) << desc;

       auto list = tree.searchAndConsolidateRects(query);
       EXPECT_EQ(list.size(), 4u);
       list.remove(rects[i - COLS - 1]);
       list.remove(rects[i - COLS]);
       list.remove(rects[i - 1]);
       list.remove(rects[i]);
       EXPECT_EQ(list.size(), 0u);
     }
   }
 }

 TEST(DisplayListRTree, OverlappingRects) {
   // Rectangles are centered at coordinates 15, 35, and 55 and are 15 wide
   // This gives them 10 pixels of overlap with the rectangles on either
   // side of them and the 10 pixels around their center coordinate are
   // exclusive to themselves.
   // So, horizontally and vertically, they cover the following ranges:
   // First  row/col:  0 to 30
   // Second row/col: 20 to 50
   // Third  row/col: 40 to 70
   // Coords  0 to 20 are only the first row/col
   // Coords 20 to 30 are both first and second row/col
   // Coords 30 to 40 are only the second row/col
   // Coords 40 to 50 are both second and third row/col
   // Coords 50 to 70 are only the third row/col
   //
   // In either dimension:
   // 0------------------20--------30--------40--------50------------------70
   // |         rect1               |
   //                     |  1 & 2  |
   //                     |            rect2            |
   //                                         |  2 & 3  |
   //                                         |                rect3        |
   SkRect rects[9];
   for (int r = 0; r < 3; r++) {
     int y = 15 + 20 * r;
     for (int c = 0; c < 3; c++) {
       int x = 15 + 20 * c;
       rects[r * 3 + c].setLTRB(x - 15, y - 15, x + 15, y + 15);
     }
   }
   DlRTree tree(rects, 9);
   // Tiny rects only intersecting a single source rect
   for (int r = 0; r < 3; r++) {
     int y = 15 + 20 * r;
     for (int c = 0; c < 3; c++) {
       int x = 15 + 20 * c;
       auto query = SkRect::MakeLTRB(x - 1, y - 1, x + 1, y + 1);
       auto list = tree.searchAndConsolidateRects(query);
       EXPECT_EQ(list.size(), 1u);
       EXPECT_EQ(list.front(), rects[r * 3 + c]);
     }
   }
   // Wide rects intersecting 3 source rects horizontally
   for (int r = 0; r < 3; r++) {
     int c = 1;
     int y = 15 + 20 * r;
     int x = 15 + 20 * c;
     auto query = SkRect::MakeLTRB(x - 6, y - 1, x + 6, y + 1);
     auto list = tree.searchAndConsolidateRects(query);
     EXPECT_EQ(list.size(), 1u);
     EXPECT_EQ(list.front(), SkRect::MakeLTRB(x - 35, y - 15, x + 35, y + 15));
   }
   // Tall rects intersecting 3 source rects vertically
   for (int c = 0; c < 3; c++) {
     int r = 1;
     int x = 15 + 20 * c;
     int y = 15 + 20 * r;
     auto query = SkRect::MakeLTRB(x - 1, y - 6, x + 1, y + 6);
     auto list = tree.searchAndConsolidateRects(query);
     EXPECT_EQ(list.size(), 1u);
     EXPECT_EQ(list.front(), SkRect::MakeLTRB(x - 15, y - 35, x + 15, y + 35));
   }
   // Finally intersecting all 9 rects
   auto query = SkRect::MakeLTRB(35 - 6, 35 - 6, 35 + 6, 35 + 6);
   auto list = tree.searchAndConsolidateRects(query);
   EXPECT_EQ(list.size(), 1u);
   EXPECT_EQ(list.front(), SkRect::MakeLTRB(0, 0, 70, 70));
 }

 TEST(DisplayListRTree, Region) {
   SkRect rect[9];
   for (int i = 0; i < 9; i++) {
     rect[i] = SkRect::MakeXYWH(i * 10, i * 10, 20, 20);
   }
   DlRTree rtree(rect, 9);
   const auto& region = rtree.region();
   auto rects = region.getRects(true);
   std::vector<SkIRect> expected_rects{
       SkIRect::MakeLTRB(0, 0, 20, 10),    SkIRect::MakeLTRB(0, 10, 30, 20),
       SkIRect::MakeLTRB(10, 20, 40, 30),  SkIRect::MakeLTRB(20, 30, 50, 40),
       SkIRect::MakeLTRB(30, 40, 60, 50),  SkIRect::MakeLTRB(40, 50, 70, 60),
       SkIRect::MakeLTRB(50, 60, 80, 70),  SkIRect::MakeLTRB(60, 70, 90, 80),
       SkIRect::MakeLTRB(70, 80, 100, 90), SkIRect::MakeLTRB(80, 90, 100, 100),
   };
   EXPECT_EQ(rects.size(), expected_rects.size());
 }

 }  // namespace testing
 }  // namespace flutter
	// Copyright 2013 The Flutter Authors. All rights reserved.
	// Use of this source code is governed by a BSD-style license that can be
	// found in the LICENSE file.

	#include "flutter/display_list/geometry/dl_rtree.h"
	#include "gtest/gtest.h"

	#include "third_party/skia/include/core/SkRect.h"

	namespace flutter {
	namespace testing {

	#ifndef NDEBUG
	TEST(DisplayListRTree, NullRectListNonZeroCount) {
	EXPECT_DEATH_IF_SUPPORTED(new DlRTree(nullptr, 1), "rects != nullptr");
	}

	TEST(DisplayListRTree, NegativeCount) {
	EXPECT_DEATH_IF_SUPPORTED(new DlRTree(nullptr, -1), "N >= 0");
	}

	TEST(DisplayListRTree, NullSearchResultVector) {
	DlRTree tree(nullptr, 0);
	EXPECT_DEATH_IF_SUPPORTED(tree.search(SkRect::MakeLTRB(0, 0, 1, 1), nullptr),
	"results != nullptr");
	}
	#endif

	TEST(DisplayListRTree, NullRectListZeroCount) {
	DlRTree tree(nullptr, 0);
	EXPECT_EQ(tree.leaf_count(), 0);
	EXPECT_EQ(tree.node_count(), 0);
	std::vector<int> results;
	auto huge = SkRect::MakeLTRB(-1e6, -1e6, 1e6, 1e6);
	tree.search(huge, &results);
	EXPECT_EQ(results.size(), 0u);
	auto list = tree.searchAndConsolidateRects(huge);
	EXPECT_EQ(list.size(), 0u);
	}

	TEST(DisplayListRTree, ManySizes) {
	// A diagonal of non-overlapping 10x10 rectangles spaced 20
	// pixels apart.
	// Rect 1 goes from 0 to 10
	// Rect 2 goes from 20 to 30
	// etc. in both dimensions
	const int kMaxN = 250;
	SkRect rects[kMaxN + 1];
	int ids[kMaxN + 1];
	for (int i = 0; i <= kMaxN; i++) {
	rects[i].setXYWH(i * 20, i * 20, 10, 10);
	ids[i] = i + 42;
	}
	std::vector<int> results;
	for (int N = 0; N <= kMaxN; N++) {
	DlRTree tree(rects, N, ids);
	auto desc = "node count = " + std::to_string(N);
	EXPECT_EQ(tree.leaf_count(), N) << desc;
	EXPECT_GE(tree.node_count(), N) << desc;
	EXPECT_EQ(tree.id(-1), -1) << desc;
	EXPECT_EQ(tree.bounds(-1), SkRect::MakeEmpty()) << desc;
	EXPECT_EQ(tree.id(N), -1) << desc;
	EXPECT_EQ(tree.bounds(N), SkRect::MakeEmpty()) << desc;
	results.clear();
	tree.search(SkRect::MakeEmpty(), &results);
	EXPECT_EQ(results.size(), 0u) << desc;
	results.clear();
	tree.search(SkRect::MakeLTRB(2, 2, 8, 8), &results);
	if (N == 0) {
	EXPECT_EQ(results.size(), 0u) << desc;
	} else {
	EXPECT_EQ(results.size(), 1u) << desc;
	EXPECT_EQ(results[0], 0) << desc;
	EXPECT_EQ(tree.id(results[0]), ids[0]) << desc;
	EXPECT_EQ(tree.bounds(results[0]), rects[0]) << desc;
	for (int i = 1; i < N; i++) {
	results.clear();
	auto query = SkRect::MakeXYWH(i * 20 + 2, i * 20 + 2, 6, 6);
	tree.search(query, &results);
	EXPECT_EQ(results.size(), 1u) << desc;
	EXPECT_EQ(results[0], i) << desc;
	EXPECT_EQ(tree.id(results[0]), ids[i]) << desc;
	EXPECT_EQ(tree.bounds(results[0]), rects[i]) << desc;
	auto list = tree.searchAndConsolidateRects(query);
	EXPECT_EQ(list.size(), 1u);
	EXPECT_EQ(list.front(), rects[i]);
	}
	}
	}
	}

	TEST(DisplayListRTree, HugeSize) {
	// A diagonal of non-overlapping 10x10 rectangles spaced 20
	// pixels apart.
	// Rect 1 goes from 0 to 10
	// Rect 2 goes from 20 to 30
	// etc. in both dimensions
	const int N = 10000;
	SkRect rects[N];
	int ids[N];
	for (int i = 0; i < N; i++) {
	rects[i].setXYWH(i * 20, i * 20, 10, 10);
	ids[i] = i + 42;
	}
	DlRTree tree(rects, N, ids);
	EXPECT_EQ(tree.leaf_count(), N);
	EXPECT_GE(tree.node_count(), N);
	EXPECT_EQ(tree.id(-1), -1);
	EXPECT_EQ(tree.bounds(-1), SkRect::MakeEmpty());
	EXPECT_EQ(tree.id(N), -1);
	EXPECT_EQ(tree.bounds(N), SkRect::MakeEmpty());
	std::vector<int> results;
	tree.search(SkRect::MakeEmpty(), &results);
	EXPECT_EQ(results.size(), 0u);
	for (int i = 0; i < N; i++) {
	results.clear();
	tree.search(SkRect::MakeXYWH(i * 20 + 2, i * 20 + 2, 6, 6), &results);
	EXPECT_EQ(results.size(), 1u);
	EXPECT_EQ(results[0], i);
	EXPECT_EQ(tree.id(results[0]), ids[i]);
	EXPECT_EQ(tree.bounds(results[0]), rects[i]);
	}
	}

	TEST(DisplayListRTree, Grid) {
	// Non-overlapping 10 x 10 rectangles starting at 5, 5 with
	// 10 pixels between them.
	// Rect 1 goes from 5 to 15
	// Rect 2 goes from 25 to 35
	// etc. in both dimensions
	const int ROWS = 10;
	const int COLS = 10;
	const int N = ROWS * COLS;
	SkRect rects[N];
	int ids[N];
	for (int r = 0; r < ROWS; r++) {
	int y = r * 20 + 5;
	for (int c = 0; c < COLS; c++) {
	int x = c * 20 + 5;
	int i = r * COLS + c;
	rects[i] = SkRect::MakeXYWH(x, y, 10, 10);
	ids[i] = i + 42;
	}
	}
	DlRTree tree(rects, N, ids);
	EXPECT_EQ(tree.leaf_count(), N);
	EXPECT_GE(tree.node_count(), N);
	EXPECT_EQ(tree.id(-1), -1);
	EXPECT_EQ(tree.bounds(-1), SkRect::MakeEmpty());
	EXPECT_EQ(tree.id(N), -1);
	EXPECT_EQ(tree.bounds(N), SkRect::MakeEmpty());
	std::vector<int> results;
	tree.search(SkRect::MakeEmpty(), &results);
	EXPECT_EQ(results.size(), 0u);
	// Testing eqch rect for a single hit
	for (int r = 0; r < ROWS; r++) {
	int y = r * 20 + 5;
	for (int c = 0; c < COLS; c++) {
	int x = c * 20 + 5;
	int i = r * COLS + c;
	auto desc =
	"row " + std::to_string(r + 1) + ", col " + std::to_string(c + 1);
	results.clear();
	auto query = SkRect::MakeXYWH(x + 2, y + 2, 6, 6);
	tree.search(query, &results);
	EXPECT_EQ(results.size(), 1u) << desc;
	EXPECT_EQ(results[0], i) << desc;
	EXPECT_EQ(tree.id(results[0]), ids[i]) << desc;
	EXPECT_EQ(tree.bounds(results[0]), rects[i]) << desc;
	auto list = tree.searchAndConsolidateRects(query);
	EXPECT_EQ(list.size(), 1u);
	EXPECT_EQ(list.front(), rects[i]);
	}
	}
	// Testing inside each gap for no hits
	for (int r = 1; r < ROWS; r++) {
	int y = r * 20 + 5;
	for (int c = 1; c < COLS; c++) {
	int x = c * 20 + 5;
	auto desc =
	"row " + std::to_string(r + 1) + ", col " + std::to_string(c + 1);
	results.clear();
	auto query = SkRect::MakeXYWH(x - 8, y - 8, 6, 6);
	tree.search(query, &results);
	EXPECT_EQ(results.size(), 0u) << desc;
	auto list = tree.searchAndConsolidateRects(query);
	EXPECT_EQ(list.size(), 0u) << desc;
	}
	}
	// Spanning each gap for a quad of hits
	for (int r = 1; r < ROWS; r++) {
	int y = r * 20 + 5;
	for (int c = 1; c < COLS; c++) {
	int x = c * 20 + 5;
	// We will hit this rect and the ones above/left of us
	int i = r * COLS + c;
	auto desc =
	"row " + std::to_string(r + 1) + ", col " + std::to_string(c + 1);
	results.clear();
	auto query = SkRect::MakeXYWH(x - 11, y - 11, 12, 12);
	tree.search(query, &results);
	EXPECT_EQ(results.size(), 4u) << desc;

	// First rect is above and to the left
	EXPECT_EQ(results[0], i - COLS - 1) << desc;
	EXPECT_EQ(tree.id(results[0]), ids[i - COLS - 1]) << desc;
	EXPECT_EQ(tree.bounds(results[0]), rects[i - COLS - 1]) << desc;

	// Second rect is above
	EXPECT_EQ(results[1], i - COLS) << desc;
	EXPECT_EQ(tree.id(results[1]), ids[i - COLS]) << desc;
	EXPECT_EQ(tree.bounds(results[1]), rects[i - COLS]) << desc;

	// Third rect is left
	EXPECT_EQ(results[2], i - 1) << desc;
	EXPECT_EQ(tree.id(results[2]), ids[i - 1]) << desc;
	EXPECT_EQ(tree.bounds(results[2]), rects[i - 1]) << desc;

	// Fourth rect is us
	EXPECT_EQ(results[3], i) << desc;
	EXPECT_EQ(tree.id(results[3]), ids[i]) << desc;
	EXPECT_EQ(tree.bounds(results[3]), rects[i]) << desc;

	auto list = tree.searchAndConsolidateRects(query);
	EXPECT_EQ(list.size(), 4u);
	list.remove(rects[i - COLS - 1]);
	list.remove(rects[i - COLS]);
	list.remove(rects[i - 1]);
	list.remove(rects[i]);
	EXPECT_EQ(list.size(), 0u);
	}
	}
	}

	TEST(DisplayListRTree, OverlappingRects) {
	// Rectangles are centered at coordinates 15, 35, and 55 and are 15 wide
	// This gives them 10 pixels of overlap with the rectangles on either
	// side of them and the 10 pixels around their center coordinate are
	// exclusive to themselves.
	// So, horizontally and vertically, they cover the following ranges:
	// First row/col: 0 to 30
	// Second row/col: 20 to 50
	// Third row/col: 40 to 70
	// Coords 0 to 20 are only the first row/col
	// Coords 20 to 30 are both first and second row/col
	// Coords 30 to 40 are only the second row/col
	// Coords 40 to 50 are both second and third row/col
	// Coords 50 to 70 are only the third row/col
	//
	// In either dimension:
	// 0------------------20--------30--------40--------50------------------70
	// \| rect1 \|
	// \| 1 & 2 \|
	// \| rect2 \|
	// \| 2 & 3 \|
	// \| rect3 \|
	SkRect rects[9];
	for (int r = 0; r < 3; r++) {
	int y = 15 + 20 * r;
	for (int c = 0; c < 3; c++) {
	int x = 15 + 20 * c;
	rects[r * 3 + c].setLTRB(x - 15, y - 15, x + 15, y + 15);
	}
	}
	DlRTree tree(rects, 9);
	// Tiny rects only intersecting a single source rect
	for (int r = 0; r < 3; r++) {
	int y = 15 + 20 * r;
	for (int c = 0; c < 3; c++) {
	int x = 15 + 20 * c;
	auto query = SkRect::MakeLTRB(x - 1, y - 1, x + 1, y + 1);
	auto list = tree.searchAndConsolidateRects(query);
	EXPECT_EQ(list.size(), 1u);
	EXPECT_EQ(list.front(), rects[r * 3 + c]);
	}
	}
	// Wide rects intersecting 3 source rects horizontally
	for (int r = 0; r < 3; r++) {
	int c = 1;
	int y = 15 + 20 * r;
	int x = 15 + 20 * c;
	auto query = SkRect::MakeLTRB(x - 6, y - 1, x + 6, y + 1);
	auto list = tree.searchAndConsolidateRects(query);
	EXPECT_EQ(list.size(), 1u);
	EXPECT_EQ(list.front(), SkRect::MakeLTRB(x - 35, y - 15, x + 35, y + 15));
	}
	// Tall rects intersecting 3 source rects vertically
	for (int c = 0; c < 3; c++) {
	int r = 1;
	int x = 15 + 20 * c;
	int y = 15 + 20 * r;
	auto query = SkRect::MakeLTRB(x - 1, y - 6, x + 1, y + 6);
	auto list = tree.searchAndConsolidateRects(query);
	EXPECT_EQ(list.size(), 1u);
	EXPECT_EQ(list.front(), SkRect::MakeLTRB(x - 15, y - 35, x + 15, y + 35));
	}
	// Finally intersecting all 9 rects
	auto query = SkRect::MakeLTRB(35 - 6, 35 - 6, 35 + 6, 35 + 6);
	auto list = tree.searchAndConsolidateRects(query);
	EXPECT_EQ(list.size(), 1u);
	EXPECT_EQ(list.front(), SkRect::MakeLTRB(0, 0, 70, 70));
	}

	TEST(DisplayListRTree, Region) {
	SkRect rect[9];
	for (int i = 0; i < 9; i++) {
	rect[i] = SkRect::MakeXYWH(i * 10, i * 10, 20, 20);
	}
	DlRTree rtree(rect, 9);
	const auto& region = rtree.region();
	auto rects = region.getRects(true);
	std::vector<SkIRect> expected_rects{
	SkIRect::MakeLTRB(0, 0, 20, 10), SkIRect::MakeLTRB(0, 10, 30, 20),
	SkIRect::MakeLTRB(10, 20, 40, 30), SkIRect::MakeLTRB(20, 30, 50, 40),
	SkIRect::MakeLTRB(30, 40, 60, 50), SkIRect::MakeLTRB(40, 50, 70, 60),
	SkIRect::MakeLTRB(50, 60, 80, 70), SkIRect::MakeLTRB(60, 70, 90, 80),
	SkIRect::MakeLTRB(70, 80, 100, 90), SkIRect::MakeLTRB(80, 90, 100, 100),
	};
	EXPECT_EQ(rects.size(), expected_rects.size());
	}

	} // namespace testing
	} // namespace flutter