| OLD | NEW |
| 1 // Copyright 2014 The Chromium Authors. All rights reserved. | 1 // Copyright 2014 The Chromium Authors. All rights reserved. |
| 2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
| 4 | 4 |
| 5 #include "testing/gtest/include/gtest/gtest.h" | 5 #include "testing/gtest/include/gtest/gtest.h" |
| 6 #include "ui/gfx/geometry/r_tree.h" | 6 #include "ui/gfx/geometry/r_tree.h" |
| 7 #include "ui/gfx/geometry/r_tree_base.h" | 7 #include "ui/gfx/geometry/r_tree_base.h" |
| 8 #include "ui/gfx/geometry/rect.h" | 8 #include "ui/gfx/geometry/rect.h" |
| 9 | 9 |
| 10 namespace gfx { | 10 namespace gfx { |
| (...skipping 261 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 272 EXPECT_FALSE(NodeCompareHorizontal(&low, &shorter_tie)); | 272 EXPECT_FALSE(NodeCompareHorizontal(&low, &shorter_tie)); |
| 273 } | 273 } |
| 274 | 274 |
| 275 TEST_F(RTreeNodeTest, CompareCenterDistanceFromParent) { | 275 TEST_F(RTreeNodeTest, CompareCenterDistanceFromParent) { |
| 276 // Create a test node we can add children to, for distance comparisons. | 276 // Create a test node we can add children to, for distance comparisons. |
| 277 scoped_ptr<RTreeNode> parent(new RTreeNode); | 277 scoped_ptr<RTreeNode> parent(new RTreeNode); |
| 278 | 278 |
| 279 // Add three children, one each with centers at (0, 0), (10, 10), (-9, -9), | 279 // Add three children, one each with centers at (0, 0), (10, 10), (-9, -9), |
| 280 // around which a bounding box will be centered at (0, 0) | 280 // around which a bounding box will be centered at (0, 0) |
| 281 scoped_ptr<RTreeRecord> center_zero(new RTreeRecord(Rect(-1, -1, 2, 2), 1)); | 281 scoped_ptr<RTreeRecord> center_zero(new RTreeRecord(Rect(-1, -1, 2, 2), 1)); |
| 282 parent->AddChild(center_zero.PassAs<RTreeNodeBase>()); | 282 parent->AddChild(center_zero.Pass()); |
| 283 | 283 |
| 284 scoped_ptr<RTreeRecord> center_positive(new RTreeRecord(Rect(9, 9, 2, 2), 2)); | 284 scoped_ptr<RTreeRecord> center_positive(new RTreeRecord(Rect(9, 9, 2, 2), 2)); |
| 285 parent->AddChild(center_positive.PassAs<RTreeNodeBase>()); | 285 parent->AddChild(center_positive.Pass()); |
| 286 | 286 |
| 287 scoped_ptr<RTreeRecord> center_negative( | 287 scoped_ptr<RTreeRecord> center_negative( |
| 288 new RTreeRecord(Rect(-10, -10, 2, 2), 3)); | 288 new RTreeRecord(Rect(-10, -10, 2, 2), 3)); |
| 289 parent->AddChild(center_negative.PassAs<RTreeNodeBase>()); | 289 parent->AddChild(center_negative.Pass()); |
| 290 | 290 |
| 291 ValidateNode(parent.get(), 1U, 5U); | 291 ValidateNode(parent.get(), 1U, 5U); |
| 292 EXPECT_EQ(Rect(-10, -10, 21, 21), parent->rect()); | 292 EXPECT_EQ(Rect(-10, -10, 21, 21), parent->rect()); |
| 293 | 293 |
| 294 EXPECT_TRUE( | 294 EXPECT_TRUE( |
| 295 NodeCompareCenterDistanceFromParent(parent->child(0), parent->child(1))); | 295 NodeCompareCenterDistanceFromParent(parent->child(0), parent->child(1))); |
| 296 EXPECT_FALSE( | 296 EXPECT_FALSE( |
| 297 NodeCompareCenterDistanceFromParent(parent->child(1), parent->child(0))); | 297 NodeCompareCenterDistanceFromParent(parent->child(1), parent->child(0))); |
| 298 EXPECT_TRUE( | 298 EXPECT_TRUE( |
| 299 NodeCompareCenterDistanceFromParent(parent->child(0), parent->child(2))); | 299 NodeCompareCenterDistanceFromParent(parent->child(0), parent->child(2))); |
| (...skipping 204 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 504 TEST_F(RTreeNodeTest, DivideChildren) { | 504 TEST_F(RTreeNodeTest, DivideChildren) { |
| 505 // Create a test node to split. | 505 // Create a test node to split. |
| 506 scoped_ptr<RTreeNode> test_node(new RTreeNode); | 506 scoped_ptr<RTreeNode> test_node(new RTreeNode); |
| 507 std::vector<RTreeNodeBase*> sorted_children; | 507 std::vector<RTreeNodeBase*> sorted_children; |
| 508 RTreeRects low_bounds; | 508 RTreeRects low_bounds; |
| 509 RTreeRects high_bounds; | 509 RTreeRects high_bounds; |
| 510 // Insert 10 record nodes, also inserting them into our children array. | 510 // Insert 10 record nodes, also inserting them into our children array. |
| 511 for (int i = 1; i <= 10; ++i) { | 511 for (int i = 1; i <= 10; ++i) { |
| 512 scoped_ptr<RTreeRecord> record(new RTreeRecord(Rect(0, 0, i, i), i)); | 512 scoped_ptr<RTreeRecord> record(new RTreeRecord(Rect(0, 0, i, i), i)); |
| 513 sorted_children.push_back(record.get()); | 513 sorted_children.push_back(record.get()); |
| 514 test_node->AddChild(record.PassAs<RTreeNodeBase>()); | 514 test_node->AddChild(record.Pass()); |
| 515 low_bounds.push_back(Rect(0, 0, i, i)); | 515 low_bounds.push_back(Rect(0, 0, i, i)); |
| 516 high_bounds.push_back(Rect(0, 0, 10, 10)); | 516 high_bounds.push_back(Rect(0, 0, 10, 10)); |
| 517 } | 517 } |
| 518 // Split the children in half. | 518 // Split the children in half. |
| 519 scoped_ptr<RTreeNodeBase> split_node_base(NodeDivideChildren( | 519 scoped_ptr<RTreeNodeBase> split_node_base(NodeDivideChildren( |
| 520 test_node.get(), low_bounds, high_bounds, sorted_children, 5)); | 520 test_node.get(), low_bounds, high_bounds, sorted_children, 5)); |
| 521 RTreeNode* split_node = static_cast<RTreeNode*>(split_node_base.get()); | 521 RTreeNode* split_node = static_cast<RTreeNode*>(split_node_base.get()); |
| 522 // Both nodes should be valid. | 522 // Both nodes should be valid. |
| 523 ValidateNode(test_node.get(), 1U, 10U); | 523 ValidateNode(test_node.get(), 1U, 10U); |
| 524 ValidateNode(split_node, 1U, 10U); | 524 ValidateNode(split_node, 1U, 10U); |
| (...skipping 52 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 577 scoped_ptr<RTreeNode> root(NewNodeAtLevel(2)); | 577 scoped_ptr<RTreeNode> root(NewNodeAtLevel(2)); |
| 578 for (int i = 0; i < 2; ++i) { | 578 for (int i = 0; i < 2; ++i) { |
| 579 scoped_ptr<RTreeNode> level_1_child(NewNodeAtLevel(1)); | 579 scoped_ptr<RTreeNode> level_1_child(NewNodeAtLevel(1)); |
| 580 for (int j = 0; j < 2; ++j) { | 580 for (int j = 0; j < 2; ++j) { |
| 581 scoped_ptr<RTreeNode> level_0_child(new RTreeNode); | 581 scoped_ptr<RTreeNode> level_0_child(new RTreeNode); |
| 582 for (int k = 0; k < 2; ++k) { | 582 for (int k = 0; k < 2; ++k) { |
| 583 scoped_ptr<RTreeRecord> record( | 583 scoped_ptr<RTreeRecord> record( |
| 584 new RTreeRecord(Rect(0, 0, id, id), id)); | 584 new RTreeRecord(Rect(0, 0, id, id), id)); |
| 585 ++id; | 585 ++id; |
| 586 records.push_back(record.get()); | 586 records.push_back(record.get()); |
| 587 level_0_child->AddChild(record.PassAs<RTreeNodeBase>()); | 587 level_0_child->AddChild(record.Pass()); |
| 588 } | 588 } |
| 589 level_0_children.push_back(level_0_child.get()); | 589 level_0_children.push_back(level_0_child.get()); |
| 590 level_1_child->AddChild(level_0_child.PassAs<RTreeNodeBase>()); | 590 level_1_child->AddChild(level_0_child.Pass()); |
| 591 } | 591 } |
| 592 level_1_children.push_back(level_1_child.get()); | 592 level_1_children.push_back(level_1_child.get()); |
| 593 root->AddChild(level_1_child.PassAs<RTreeNodeBase>()); | 593 root->AddChild(level_1_child.Pass()); |
| 594 } | 594 } |
| 595 | 595 |
| 596 // This should now be a valid tree structure. | 596 // This should now be a valid tree structure. |
| 597 ValidateNode(root.get(), 2U, 2U); | 597 ValidateNode(root.get(), 2U, 2U); |
| 598 EXPECT_EQ(2U, level_1_children.size()); | 598 EXPECT_EQ(2U, level_1_children.size()); |
| 599 EXPECT_EQ(4U, level_0_children.size()); | 599 EXPECT_EQ(4U, level_0_children.size()); |
| 600 EXPECT_EQ(8U, records.size()); | 600 EXPECT_EQ(8U, records.size()); |
| 601 | 601 |
| 602 // Now remove all of the level 0 nodes so we get the record nodes as orphans. | 602 // Now remove all of the level 0 nodes so we get the record nodes as orphans. |
| 603 RTreeNodes orphans; | 603 RTreeNodes orphans; |
| (...skipping 48 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 652 scoped_ptr<RTreeNode> test_parent(NewNodeAtLevel(1)); | 652 scoped_ptr<RTreeNode> test_parent(NewNodeAtLevel(1)); |
| 653 // Construct 4 nodes with 1x2 rects spaced horizontally 1 pixel apart, or: | 653 // Construct 4 nodes with 1x2 rects spaced horizontally 1 pixel apart, or: |
| 654 // | 654 // |
| 655 // a b c d | 655 // a b c d |
| 656 // a b c d | 656 // a b c d |
| 657 // | 657 // |
| 658 for (int i = 0; i < 4; ++i) { | 658 for (int i = 0; i < 4; ++i) { |
| 659 scoped_ptr<RTreeNode> node(new RTreeNode); | 659 scoped_ptr<RTreeNode> node(new RTreeNode); |
| 660 scoped_ptr<RTreeRecord> record( | 660 scoped_ptr<RTreeRecord> record( |
| 661 new RTreeRecord(Rect(i * 2, 0, 1, 2), i + 1)); | 661 new RTreeRecord(Rect(i * 2, 0, 1, 2), i + 1)); |
| 662 node->AddChild(record.PassAs<RTreeNodeBase>()); | 662 node->AddChild(record.Pass()); |
| 663 test_parent->AddChild(node.PassAs<RTreeNodeBase>()); | 663 test_parent->AddChild(node.Pass()); |
| 664 } | 664 } |
| 665 | 665 |
| 666 ValidateNode(test_parent.get(), 1U, 5U); | 666 ValidateNode(test_parent.get(), 1U, 5U); |
| 667 | 667 |
| 668 // Test rect at (7, 0) should require minimum overlap on the part of the | 668 // Test rect at (7, 0) should require minimum overlap on the part of the |
| 669 // fourth rectangle to add: | 669 // fourth rectangle to add: |
| 670 // | 670 // |
| 671 // a b c dT | 671 // a b c dT |
| 672 // a b c d | 672 // a b c d |
| 673 // | 673 // |
| (...skipping 29 matching lines...) Expand all Loading... |
| 703 | 703 |
| 704 // Add a rectangle that overlaps completely with rectangle c, to test | 704 // Add a rectangle that overlaps completely with rectangle c, to test |
| 705 // when there is a tie between two completely contained rectangles: | 705 // when there is a tie between two completely contained rectangles: |
| 706 // | 706 // |
| 707 // a b Ted | 707 // a b Ted |
| 708 // a b eed | 708 // a b eed |
| 709 // | 709 // |
| 710 scoped_ptr<RTreeNode> record_parent(new RTreeNode); | 710 scoped_ptr<RTreeNode> record_parent(new RTreeNode); |
| 711 record_parent->AddChild( | 711 record_parent->AddChild( |
| 712 scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(4, 0, 2, 2), 9))); | 712 scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(4, 0, 2, 2), 9))); |
| 713 test_parent->AddChild(record_parent.PassAs<RTreeNodeBase>()); | 713 test_parent->AddChild(record_parent.Pass()); |
| 714 BuildExpandedRects(test_parent.get(), test_rect_inside, &expanded_rects); | 714 BuildExpandedRects(test_parent.get(), test_rect_inside, &expanded_rects); |
| 715 result = NodeLeastOverlapIncrease( | 715 result = NodeLeastOverlapIncrease( |
| 716 test_parent.get(), test_rect_inside, expanded_rects); | 716 test_parent.get(), test_rect_inside, expanded_rects); |
| 717 EXPECT_TRUE(result == NULL); | 717 EXPECT_TRUE(result == NULL); |
| 718 } | 718 } |
| 719 | 719 |
| 720 TEST_F(RTreeNodeTest, LeastAreaEnlargement) { | 720 TEST_F(RTreeNodeTest, LeastAreaEnlargement) { |
| 721 scoped_ptr<RTreeNode> test_parent(NewNodeAtLevel(1)); | 721 scoped_ptr<RTreeNode> test_parent(NewNodeAtLevel(1)); |
| 722 // Construct 4 nodes in a cross-hairs style configuration: | 722 // Construct 4 nodes in a cross-hairs style configuration: |
| 723 // | 723 // |
| 724 // a | 724 // a |
| 725 // b c | 725 // b c |
| 726 // d | 726 // d |
| 727 // | 727 // |
| 728 scoped_ptr<RTreeNode> node(new RTreeNode); | 728 scoped_ptr<RTreeNode> node(new RTreeNode); |
| 729 node->AddChild( | 729 node->AddChild( |
| 730 scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(1, 0, 1, 1), 1))); | 730 scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(1, 0, 1, 1), 1))); |
| 731 test_parent->AddChild(node.PassAs<RTreeNodeBase>()); | 731 test_parent->AddChild(node.Pass()); |
| 732 node.reset(new RTreeNode); | 732 node.reset(new RTreeNode); |
| 733 node->AddChild( | 733 node->AddChild( |
| 734 scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 1, 1, 1), 2))); | 734 scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 1, 1, 1), 2))); |
| 735 test_parent->AddChild(node.PassAs<RTreeNodeBase>()); | 735 test_parent->AddChild(node.Pass()); |
| 736 node.reset(new RTreeNode); | 736 node.reset(new RTreeNode); |
| 737 node->AddChild( | 737 node->AddChild( |
| 738 scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(2, 1, 1, 1), 3))); | 738 scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(2, 1, 1, 1), 3))); |
| 739 test_parent->AddChild(node.PassAs<RTreeNodeBase>()); | 739 test_parent->AddChild(node.Pass()); |
| 740 node.reset(new RTreeNode); | 740 node.reset(new RTreeNode); |
| 741 node->AddChild( | 741 node->AddChild( |
| 742 scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(1, 2, 1, 1), 4))); | 742 scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(1, 2, 1, 1), 4))); |
| 743 test_parent->AddChild(node.PassAs<RTreeNodeBase>()); | 743 test_parent->AddChild(node.Pass()); |
| 744 | 744 |
| 745 ValidateNode(test_parent.get(), 1U, 5U); | 745 ValidateNode(test_parent.get(), 1U, 5U); |
| 746 | 746 |
| 747 // Test rect at (1, 3) should require minimum area to add to Node d: | 747 // Test rect at (1, 3) should require minimum area to add to Node d: |
| 748 // | 748 // |
| 749 // a | 749 // a |
| 750 // b c | 750 // b c |
| 751 // d | 751 // d |
| 752 // T | 752 // T |
| 753 // | 753 // |
| (...skipping 18 matching lines...) Expand all Loading... |
| 772 | 772 |
| 773 // Add e at (0, 1) to overlap b and c, to test tie-breaking: | 773 // Add e at (0, 1) to overlap b and c, to test tie-breaking: |
| 774 // | 774 // |
| 775 // a | 775 // a |
| 776 // eee | 776 // eee |
| 777 // d | 777 // d |
| 778 // | 778 // |
| 779 node.reset(new RTreeNode); | 779 node.reset(new RTreeNode); |
| 780 node->AddChild( | 780 node->AddChild( |
| 781 scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 1, 3, 1), 7))); | 781 scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 1, 3, 1), 7))); |
| 782 test_parent->AddChild(node.PassAs<RTreeNodeBase>()); | 782 test_parent->AddChild(node.Pass()); |
| 783 | 783 |
| 784 ValidateNode(test_parent.get(), 1U, 5U); | 784 ValidateNode(test_parent.get(), 1U, 5U); |
| 785 | 785 |
| 786 // Test rect at (3, 1) should tie between c and e, but c has smaller area so | 786 // Test rect at (3, 1) should tie between c and e, but c has smaller area so |
| 787 // the algorithm should select c: | 787 // the algorithm should select c: |
| 788 // | 788 // |
| 789 // | 789 // |
| 790 // a | 790 // a |
| 791 // eeeT | 791 // eeeT |
| 792 // d | 792 // d |
| (...skipping 223 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1016 AddStackedSquares(&rt, 100); | 1016 AddStackedSquares(&rt, 100); |
| 1017 ValidateRTree(&rt); | 1017 ValidateRTree(&rt); |
| 1018 | 1018 |
| 1019 for (int i = 1; i <= 100; ++i) { | 1019 for (int i = 1; i <= 100; ++i) { |
| 1020 rt.Insert(Rect(0, 0, 0, 0), i); | 1020 rt.Insert(Rect(0, 0, 0, 0), i); |
| 1021 ValidateRTree(&rt); | 1021 ValidateRTree(&rt); |
| 1022 } | 1022 } |
| 1023 } | 1023 } |
| 1024 | 1024 |
| 1025 } // namespace gfx | 1025 } // namespace gfx |
| OLD | NEW |