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 |