Adds an RTree data structure to gfx/geometry

ui/gfx/geometry/r_tree_unittest.cc

+// Copyright (c) 2014 The Chromium 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 <set>
+
+#include "testing/gtest/include/gtest/gtest.h"
+#include "ui/gfx/geometry/r_tree.h"
+#include "ui/gfx/geometry/rect.h"
+
+namespace gfx {

[piman, 2014/04/21 23:59:31]

I think we want to add several tests around all the heuristics wrt choosing
subtrees, or splitting nodes.
It's pretty subtle logic...

[luken, 2014/04/28 01:33:34]

Done.

+
+// Adds count squares stacked around the point (0,0) with key equal to width.
+void AddStackedSquares(RTree* rt, int count) {
+  for (int i = 1; i <= count; ++i) {
+    rt->Insert(Rect(0, 0, i, i), reinterpret_cast<void*>(i));
+    EXPECT_TRUE(rt->Validate());
+  }
+}
+
+// Given an unordered list of matching keys, verify that it contains all values
+// [1..length] for the length of that list.
+void VerifyAllKeys(const std::set<void*>& keys) {
+  // Verify that each key was uniquely identified.
+  int c = 1;
+  for (std::set<void*>::const_iterator it = keys.begin();
+       it != keys.end();
+       it++) {
+    // Verify that the keys are in values [1,count].
+    EXPECT_EQ(c, reinterpret_cast<int>((*it)));

[piman, 2014/04/21 23:59:31]

nit: extra () around *it

[luken, 2014/04/28 01:33:34]

Done.

+    ++c;
+  }
+}
+
+// An empty RTree should never return Query results, and RTrees should be empty
+// upon construction.
+TEST(RTreeTest, QueryEmptyTree) {
+  RTree rt(2, 10);
+  EXPECT_TRUE(rt.Validate());
+  std::set<void*> results;
+  Rect test_rect(25, 25);
+  rt.Query(test_rect, &results);
+  EXPECT_EQ(results.size(), 0U);
+  EXPECT_TRUE(rt.Validate());
+}
+
+// Clear should empty the tree, meaning that all queries should not return
+// results after.
+TEST(RTreeTest, ClearEmptiesTreeOfSingleNode) {
+  RTree rt(2, 5);
+  rt.Insert(Rect(0, 0, 100, 100), reinterpret_cast<void*>(1));
+  rt.Clear();
+  std::set<void*> results;
+  Rect test_rect(1, 1);
+  rt.Query(test_rect, &results);
+  EXPECT_EQ(results.size(), 0U);
+}
+
+// Even with a complex internal structure, clear should empty the tree, meaning
+// that all queries should not return results after.
+TEST(RTreeTest, ClearEmptiesTreeOfManyNodes) {
+  RTree rt(2, 5);
+  AddStackedSquares(&rt, 100);
+  rt.Clear();
+  EXPECT_TRUE(rt.Validate());
+  std::set<void*> results;
+  Rect test_rect(1, 1);
+  rt.Query(test_rect, &results);
+  EXPECT_EQ(results.size(), 0U);
+}
+
+// Duplicate inserts should overwrite previous inserts.
+TEST(RTreeTest, DuplicateInsertsOverwrite) {
+  RTree rt(2, 5);
+  // Add 100 stacked squares, but always with duplicate key of 1.
+  for (int i = 1; i <= 100; ++i) {
+    rt.Insert(Rect(0, 0, i, i), reinterpret_cast<void*>(1));
+    EXPECT_TRUE(rt.Validate());
+  }
+  std::set<void*> results;
+  Rect test_rect(1, 1);
+  rt.Query(test_rect, &results);
+  EXPECT_EQ(results.size(), 1U);
+  EXPECT_EQ(reinterpret_cast<int>(*(results.begin())), 1);
+}
+
+// Call Remove() once on something that's been inserted repeatedly.
+TEST(RTreeTest, DuplicateInsertRemove) {
+  RTree rt(3, 9);
+  AddStackedSquares(&rt, 25);
+  for (int i = 1; i <= 100; ++i) {
+    rt.Insert(Rect(0, 0, i, i), reinterpret_cast<void*>(26));
+    EXPECT_TRUE(rt.Validate());
+  }
+  rt.Remove(reinterpret_cast<void*>(26));
+  std::set<void*> results;
+  Rect test_rect(1, 1);
+  rt.Query(test_rect, &results);
+  EXPECT_EQ(results.size(), 25U);
+  VerifyAllKeys(results);
+}
+
+// Call Remove() repeatedly on something that's been inserted once.
+TEST(RTreeTest, InsertDuplicateRemove) {
+  RTree rt(7, 15);
+  AddStackedSquares(&rt, 101);
+  for (int i = 0; i < 100; ++i) {
+    rt.Remove(reinterpret_cast<void*>(101));
+    EXPECT_TRUE(rt.Validate());
+  }
+  std::set<void*> results;
+  Rect test_rect(1, 1);
+  rt.Query(test_rect, &results);
+  EXPECT_EQ(results.size(), 100U);
+  VerifyAllKeys(results);
+}
+
+// Stacked rects should meet all matching queries regardless of nesting.
+TEST(RTreeTest, QueryStackedSquaresNestedHit) {
+  RTree rt(2, 5);
+  AddStackedSquares(&rt, 100);
+  std::set<void*> results;
+  Rect test_rect(1, 1);
+  rt.Query(test_rect, &results);
+  EXPECT_EQ(results.size(), 100U);
+  VerifyAllKeys(results);
+}
+
+// Stacked rects should meet all matching queries when contained completely by
+// the query rectangle.
+TEST(RTreeTest, QueryStackedSquaresContainedHit) {
+  RTree rt(2, 10);
+  AddStackedSquares(&rt, 100);
+  std::set<void*> results;
+  Rect test_rect(0, 0, 100, 100);
+  rt.Query(test_rect, &results);
+  EXPECT_EQ(results.size(), 100U);
+  VerifyAllKeys(results);
+}
+
+// Stacked rects should miss a missing query when the query has no intersection
+// with the rects.
+TEST(RTreeTest, QueryStackedSquaresCompleteMiss) {
+  RTree rt(2, 7);
+  AddStackedSquares(&rt, 100);
+  std::set<void*> results;
+  Rect test_rect(150, 150, 100, 100);
+  rt.Query(test_rect, &results);
+  EXPECT_EQ(results.size(), 0U);
+}
+
+// Removing half the nodes after insertion should still result in a valid tree.
+TEST(RTreeTest, RemoveHalfStackedRects) {
+  RTree rt(2, 11);
+  AddStackedSquares(&rt, 200);
+  for (int i = 101; i <= 200; ++i) {
+    rt.Remove(reinterpret_cast<void*>(i));
+    EXPECT_TRUE(rt.Validate());
+  }
+  std::set<void*> results;
+  Rect test_rect(1, 1);
+  rt.Query(test_rect, &results);
+  EXPECT_EQ(results.size(), 100U);
+  VerifyAllKeys(results);
+  // Add the nodes back in.
+  for (int i = 101; i <= 200; ++i) {
+    rt.Insert(Rect(0, 0, i, i), reinterpret_cast<void*>(i));
+    EXPECT_TRUE(rt.Validate());
+  }
+  results.clear();
+  rt.Query(test_rect, &results);
+  EXPECT_EQ(results.size(), 200U);
+  VerifyAllKeys(results);
+}
+
+TEST(RTreeTest, InsertNegativeCoordsRect) {
+  RTree rt(5, 11);
+  for (int i = 1; i <= 100; ++i) {
+    rt.Insert(Rect(-i, -i, i, i), reinterpret_cast<void*>((i * 2) - 1));
+    EXPECT_TRUE(rt.Validate());
+    rt.Insert(Rect(0, 0, i, i), reinterpret_cast<void*>(i * 2));
+    EXPECT_TRUE(rt.Validate());
+  }
+  std::set<void*> results;
+  Rect test_rect(-1, -1, 2, 2);
+  rt.Query(test_rect, &results);
+  EXPECT_EQ(results.size(), 200U);
+  VerifyAllKeys(results);
+}
+
+TEST(RTreeTest, RemoveNegativeCoordsRect) {
+  RTree rt(7, 21);
+  // Add 100 positive stacked squares.
+  AddStackedSquares(&rt, 100);
+  // Now add 100 negative stacked squares.
+  for (int i = 101; i <= 200; ++i) {
+    rt.Insert(Rect(100 - i, 100 - i, i - 100, i - 100),
+              reinterpret_cast<void*>(301 - i));
+    EXPECT_TRUE(rt.Validate());
+  }
+  // Now remove half of the negative squares.
+  for (int i = 101; i <= 150; ++i) {
+    rt.Remove(reinterpret_cast<void*>(301 - i));
+    EXPECT_TRUE(rt.Validate());
+  }
+  // Queries should return 100 positive and 50 negative stacked squares.
+  std::set<void*> results;
+  Rect test_rect(-1, -1, 2, 2);
+  rt.Query(test_rect, &results);
+  EXPECT_EQ(results.size(), 150U);
+  VerifyAllKeys(results);
+}
+
+}  // namespace gfx