| OLD | NEW |
| 1 /* | 1 /* |
| 2 * Copyright (C) 2012 Apple Inc. All rights reserved. | 2 * Copyright (C) 2012 Apple Inc. All rights reserved. |
| 3 * | 3 * |
| 4 * Redistribution and use in source and binary forms, with or without | 4 * Redistribution and use in source and binary forms, with or without |
| 5 * modification, are permitted provided that the following conditions | 5 * modification, are permitted provided that the following conditions |
| 6 * are met: | 6 * are met: |
| 7 * 1. Redistributions of source code must retain the above copyright | 7 * 1. Redistributions of source code must retain the above copyright |
| 8 * notice, this list of conditions and the following disclaimer. | 8 * notice, this list of conditions and the following disclaimer. |
| 9 * 2. Redistributions in binary form must reproduce the above copyright | 9 * 2. Redistributions in binary form must reproduce the above copyright |
| 10 * notice, this list of conditions and the following disclaimer in the | 10 * notice, this list of conditions and the following disclaimer in the |
| (...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 46 RefPtr<TestTree> lastChild = TestTree::create(); | 46 RefPtr<TestTree> lastChild = TestTree::create(); |
| 47 | 47 |
| 48 root->appendChild(firstChild.get()); | 48 root->appendChild(firstChild.get()); |
| 49 ASSERT_EQ(root->firstChild(), firstChild.get()); | 49 ASSERT_EQ(root->firstChild(), firstChild.get()); |
| 50 ASSERT_EQ(root->lastChild(), firstChild.get()); | 50 ASSERT_EQ(root->lastChild(), firstChild.get()); |
| 51 ASSERT_EQ(firstChild->parent(), root.get()); | 51 ASSERT_EQ(firstChild->parent(), root.get()); |
| 52 | 52 |
| 53 root->appendChild(lastChild.get()); | 53 root->appendChild(lastChild.get()); |
| 54 ASSERT_EQ(root->firstChild(), firstChild.get()); | 54 ASSERT_EQ(root->firstChild(), firstChild.get()); |
| 55 ASSERT_EQ(root->lastChild(), lastChild.get()); | 55 ASSERT_EQ(root->lastChild(), lastChild.get()); |
| 56 ASSERT_EQ(lastChild->previousSibling(), firstChild.get()); | 56 ASSERT_EQ(lastChild->previous(), firstChild.get()); |
| 57 ASSERT_EQ(firstChild->nextSibling(), lastChild.get()); | 57 ASSERT_EQ(firstChild->next(), lastChild.get()); |
| 58 ASSERT_EQ(lastChild->parent(), root.get()); | 58 ASSERT_EQ(lastChild->parent(), root.get()); |
| 59 } | 59 } |
| 60 | 60 |
| 61 TEST(WTF, TreeNodeInsertBefore) | 61 TEST(WTF, TreeNodeInsertBefore) |
| 62 { | 62 { |
| 63 RefPtr<TestTree> root = TestTree::create(); | 63 RefPtr<TestTree> root = TestTree::create(); |
| 64 RefPtr<TestTree> firstChild = TestTree::create(); | 64 RefPtr<TestTree> firstChild = TestTree::create(); |
| 65 RefPtr<TestTree> middleChild = TestTree::create(); | 65 RefPtr<TestTree> middleChild = TestTree::create(); |
| 66 RefPtr<TestTree> lastChild = TestTree::create(); | 66 RefPtr<TestTree> lastChild = TestTree::create(); |
| 67 | 67 |
| 68 // Inserting single node | 68 // Inserting single node |
| 69 root->insertBefore(lastChild.get(), 0); | 69 root->insertBefore(lastChild.get(), 0); |
| 70 ASSERT_EQ(lastChild->parent(), root.get()); | 70 ASSERT_EQ(lastChild->parent(), root.get()); |
| 71 ASSERT_EQ(root->firstChild(), lastChild.get()); | 71 ASSERT_EQ(root->firstChild(), lastChild.get()); |
| 72 ASSERT_EQ(root->lastChild(), lastChild.get()); | 72 ASSERT_EQ(root->lastChild(), lastChild.get()); |
| 73 | 73 |
| 74 // Then prepend | 74 // Then prepend |
| 75 root->insertBefore(firstChild.get(), lastChild.get()); | 75 root->insertBefore(firstChild.get(), lastChild.get()); |
| 76 ASSERT_EQ(firstChild->parent(), root.get()); | 76 ASSERT_EQ(firstChild->parent(), root.get()); |
| 77 ASSERT_EQ(root->firstChild(), firstChild.get()); | 77 ASSERT_EQ(root->firstChild(), firstChild.get()); |
| 78 ASSERT_EQ(root->lastChild(), lastChild.get()); | 78 ASSERT_EQ(root->lastChild(), lastChild.get()); |
| 79 ASSERT_EQ(firstChild->nextSibling(), lastChild.get()); | 79 ASSERT_EQ(firstChild->next(), lastChild.get()); |
| 80 ASSERT_EQ(firstChild.get(), lastChild->previousSibling()); | 80 ASSERT_EQ(firstChild.get(), lastChild->previous()); |
| 81 | 81 |
| 82 // Inserting in the middle | 82 // Inserting in the middle |
| 83 root->insertBefore(middleChild.get(), lastChild.get()); | 83 root->insertBefore(middleChild.get(), lastChild.get()); |
| 84 ASSERT_EQ(middleChild->parent(), root.get()); | 84 ASSERT_EQ(middleChild->parent(), root.get()); |
| 85 ASSERT_EQ(root->firstChild(), firstChild.get()); | 85 ASSERT_EQ(root->firstChild(), firstChild.get()); |
| 86 ASSERT_EQ(root->lastChild(), lastChild.get()); | 86 ASSERT_EQ(root->lastChild(), lastChild.get()); |
| 87 ASSERT_EQ(middleChild->previousSibling(), firstChild.get()); | 87 ASSERT_EQ(middleChild->previous(), firstChild.get()); |
| 88 ASSERT_EQ(middleChild->nextSibling(), lastChild.get()); | 88 ASSERT_EQ(middleChild->next(), lastChild.get()); |
| 89 ASSERT_EQ(firstChild->nextSibling(), middleChild.get()); | 89 ASSERT_EQ(firstChild->next(), middleChild.get()); |
| 90 ASSERT_EQ(lastChild->previousSibling(), middleChild.get()); | 90 ASSERT_EQ(lastChild->previous(), middleChild.get()); |
| 91 | 91 |
| 92 } | 92 } |
| 93 | 93 |
| 94 TEST(WTF, TreeNodeRemoveSingle) | 94 TEST(WTF, TreeNodeRemoveSingle) |
| 95 { | 95 { |
| 96 RefPtr<TestTree> root = TestTree::create(); | 96 RefPtr<TestTree> root = TestTree::create(); |
| 97 RefPtr<TestTree> child = TestTree::create(); | 97 RefPtr<TestTree> child = TestTree::create(); |
| 98 RefPtr<TestTree> nullNode; | 98 RefPtr<TestTree> nullNode; |
| 99 | 99 |
| 100 root->appendChild(child.get()); | 100 root->appendChild(child.get()); |
| 101 root->removeChild(child.get()); | 101 root->removeChild(child.get()); |
| 102 ASSERT_EQ(child->nextSibling(), nullNode.get()); | 102 ASSERT_EQ(child->next(), nullNode.get()); |
| 103 ASSERT_EQ(child->previousSibling(), nullNode.get()); | 103 ASSERT_EQ(child->previous(), nullNode.get()); |
| 104 ASSERT_EQ(child->parent(), nullNode.get()); | 104 ASSERT_EQ(child->parent(), nullNode.get()); |
| 105 ASSERT_EQ(root->firstChild(), nullNode.get()); | 105 ASSERT_EQ(root->firstChild(), nullNode.get()); |
| 106 ASSERT_EQ(root->lastChild(), nullNode.get()); | 106 ASSERT_EQ(root->lastChild(), nullNode.get()); |
| 107 } | 107 } |
| 108 | 108 |
| 109 class Trio { | 109 class Trio { |
| 110 public: | 110 public: |
| 111 Trio() | 111 Trio() |
| 112 : root(TestTree::create()) | 112 : root(TestTree::create()) |
| 113 , firstChild(TestTree::create()) | 113 , firstChild(TestTree::create()) |
| (...skipping 15 matching lines...) Expand all Loading... |
| 129 RefPtr<TestTree> lastChild; | 129 RefPtr<TestTree> lastChild; |
| 130 }; | 130 }; |
| 131 | 131 |
| 132 TEST(WTF, TreeNodeRemoveMiddle) | 132 TEST(WTF, TreeNodeRemoveMiddle) |
| 133 { | 133 { |
| 134 Trio trio; | 134 Trio trio; |
| 135 trio.appendChildren(); | 135 trio.appendChildren(); |
| 136 | 136 |
| 137 trio.root->removeChild(trio.middleChild.get()); | 137 trio.root->removeChild(trio.middleChild.get()); |
| 138 ASSERT_TRUE(trio.middleChild->orphan()); | 138 ASSERT_TRUE(trio.middleChild->orphan()); |
| 139 ASSERT_EQ(trio.firstChild->nextSibling(), trio.lastChild.get()); | 139 ASSERT_EQ(trio.firstChild->next(), trio.lastChild.get()); |
| 140 ASSERT_EQ(trio.lastChild->previousSibling(), trio.firstChild.get()); | 140 ASSERT_EQ(trio.lastChild->previous(), trio.firstChild.get()); |
| 141 ASSERT_EQ(trio.root->firstChild(), trio.firstChild.get()); | 141 ASSERT_EQ(trio.root->firstChild(), trio.firstChild.get()); |
| 142 ASSERT_EQ(trio.root->lastChild(), trio.lastChild.get()); | 142 ASSERT_EQ(trio.root->lastChild(), trio.lastChild.get()); |
| 143 } | 143 } |
| 144 | 144 |
| 145 TEST(WTF, TreeNodeRemoveLast) | 145 TEST(WTF, TreeNodeRemoveLast) |
| 146 { | 146 { |
| 147 RefPtr<TestTree> nullNode; | 147 RefPtr<TestTree> nullNode; |
| 148 Trio trio; | 148 Trio trio; |
| 149 trio.appendChildren(); | 149 trio.appendChildren(); |
| 150 | 150 |
| 151 trio.root->removeChild(trio.lastChild.get()); | 151 trio.root->removeChild(trio.lastChild.get()); |
| 152 ASSERT_TRUE(trio.lastChild->orphan()); | 152 ASSERT_TRUE(trio.lastChild->orphan()); |
| 153 ASSERT_EQ(trio.middleChild->nextSibling(), nullNode.get()); | 153 ASSERT_EQ(trio.middleChild->next(), nullNode.get()); |
| 154 ASSERT_EQ(trio.root->firstChild(), trio.firstChild.get()); | 154 ASSERT_EQ(trio.root->firstChild(), trio.firstChild.get()); |
| 155 ASSERT_EQ(trio.root->lastChild(), trio.middleChild.get()); | 155 ASSERT_EQ(trio.root->lastChild(), trio.middleChild.get()); |
| 156 } | 156 } |
| 157 | 157 |
| 158 TEST(WTF, TreeNodeRemoveFirst) | 158 TEST(WTF, TreeNodeRemoveFirst) |
| 159 { | 159 { |
| 160 RefPtr<TestTree> nullNode; | 160 RefPtr<TestTree> nullNode; |
| 161 Trio trio; | 161 Trio trio; |
| 162 trio.appendChildren(); | 162 trio.appendChildren(); |
| 163 | 163 |
| 164 trio.root->removeChild(trio.firstChild.get()); | 164 trio.root->removeChild(trio.firstChild.get()); |
| 165 ASSERT_TRUE(trio.firstChild->orphan()); | 165 ASSERT_TRUE(trio.firstChild->orphan()); |
| 166 ASSERT_EQ(trio.middleChild->previousSibling(), nullNode.get()); | 166 ASSERT_EQ(trio.middleChild->previous(), nullNode.get()); |
| 167 ASSERT_EQ(trio.root->firstChild(), trio.middleChild.get()); | 167 ASSERT_EQ(trio.root->firstChild(), trio.middleChild.get()); |
| 168 ASSERT_EQ(trio.root->lastChild(), trio.lastChild.get()); | 168 ASSERT_EQ(trio.root->lastChild(), trio.lastChild.get()); |
| 169 } | 169 } |
| 170 | 170 |
| 171 class TrioWithGrandChild : public Trio { | 171 class TrioWithGrandChild : public Trio { |
| 172 public: | 172 public: |
| 173 TrioWithGrandChild() | 173 TrioWithGrandChild() |
| 174 : grandChild(TestTree::create()) | 174 : grandChild(TestTree::create()) |
| 175 { | 175 { |
| 176 } | 176 } |
| (...skipping 11 matching lines...) Expand all Loading... |
| 188 { | 188 { |
| 189 TrioWithGrandChild trio; | 189 TrioWithGrandChild trio; |
| 190 trio.appendChildren(); | 190 trio.appendChildren(); |
| 191 | 191 |
| 192 TestTree* order[] = { | 192 TestTree* order[] = { |
| 193 trio.root.get(), trio.firstChild.get(), trio.middleChild.get(), | 193 trio.root.get(), trio.firstChild.get(), trio.middleChild.get(), |
| 194 trio.grandChild.get(), trio.lastChild.get() | 194 trio.grandChild.get(), trio.lastChild.get() |
| 195 }; | 195 }; |
| 196 | 196 |
| 197 unsigned orderIndex = 0; | 197 unsigned orderIndex = 0; |
| 198 for (TestTree* node = trio.root.get(); node; node = traverseNext<TestTree>(*
node), orderIndex++) | 198 for (TestTree* node = trio.root.get(); node; node = traverseNext(node), orde
rIndex++) |
| 199 ASSERT_EQ(node, order[orderIndex]); | 199 ASSERT_EQ(node, order[orderIndex]); |
| 200 ASSERT_EQ(orderIndex, sizeof(order) / sizeof(TestTree*)); | 200 ASSERT_EQ(orderIndex, sizeof(order) / sizeof(TestTree*)); |
| 201 } | 201 } |
| 202 | 202 |
| 203 TEST(WTF, TreeNodeTraverseNextPostORder) | 203 TEST(WTF, TreeNodeTraverseNextPostORder) |
| 204 { | 204 { |
| 205 TrioWithGrandChild trio; | 205 TrioWithGrandChild trio; |
| 206 trio.appendChildren(); | 206 trio.appendChildren(); |
| 207 | 207 |
| 208 | 208 |
| 209 TestTree* order[] = { | 209 TestTree* order[] = { |
| 210 trio.firstChild.get(), | 210 trio.firstChild.get(), |
| 211 trio.grandChild.get(), trio.middleChild.get(), trio.lastChild.get(), tri
o.root.get() | 211 trio.grandChild.get(), trio.middleChild.get(), trio.lastChild.get(), tri
o.root.get() |
| 212 }; | 212 }; |
| 213 | 213 |
| 214 unsigned orderIndex = 0; | 214 unsigned orderIndex = 0; |
| 215 for (TestTree* node = traverseFirstPostOrder<TestTree>(*trio.root.get()); no
de; node = traverseNextPostOrder<TestTree>(*node), orderIndex++) | 215 for (TestTree* node = traverseFirstPostOrder(trio.root.get()); node; node =
traverseNextPostOrder(node), orderIndex++) |
| 216 ASSERT_EQ(node, order[orderIndex]); | 216 ASSERT_EQ(node, order[orderIndex]); |
| 217 ASSERT_EQ(orderIndex, sizeof(order) / sizeof(TestTree*)); | 217 ASSERT_EQ(orderIndex, sizeof(order) / sizeof(TestTree*)); |
| 218 | 218 |
| 219 } | 219 } |
| 220 | 220 |
| 221 | 221 |
| 222 } // namespace | 222 } // namespace |
| OLD | NEW |