1 /* 2 * Copyright (C) 2012 Apple Inc. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 7 * 1. Redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer. 9 * 2. Redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution. 12 * 13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS'' 14 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, 15 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS 17 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 18 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 19 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 20 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 21 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 22 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF 23 * THE POSSIBILITY OF SUCH DAMAGE. 24 */ 25 26 #include "config.h" 27 28 #include "wtf/TreeNode.h" 29 30 #include "wtf/PassRefPtr.h" 31 #include "wtf/RefCounted.h" 32 #include "wtf/RefPtr.h" 33 #include <gtest/gtest.h> 34 35 namespace { 36 37 class TestTree : public RefCounted<TestTree>, public TreeNode<TestTree> { 38 public: 39 static PassRefPtr<TestTree> create() { return adoptRef(new TestTree()); } 40 }; 41 42 TEST(TreeNodeTest, AppendChild) 43 { 44 RefPtr<TestTree> root = TestTree::create(); 45 RefPtr<TestTree> firstChild = TestTree::create(); 46 RefPtr<TestTree> lastChild = TestTree::create(); 47 48 root->appendChild(firstChild.get()); 49 EXPECT_EQ(root->firstChild(), firstChild.get()); 50 EXPECT_EQ(root->lastChild(), firstChild.get()); 51 EXPECT_EQ(firstChild->parent(), root.get()); 52 53 root->appendChild(lastChild.get()); 54 EXPECT_EQ(root->firstChild(), firstChild.get()); 55 EXPECT_EQ(root->lastChild(), lastChild.get()); 56 EXPECT_EQ(lastChild->previous(), firstChild.get()); 57 EXPECT_EQ(firstChild->next(), lastChild.get()); 58 EXPECT_EQ(lastChild->parent(), root.get()); 59 } 60 61 TEST(TreeNodeTest, InsertBefore) 62 { 63 RefPtr<TestTree> root = TestTree::create(); 64 RefPtr<TestTree> firstChild = TestTree::create(); 65 RefPtr<TestTree> middleChild = TestTree::create(); 66 RefPtr<TestTree> lastChild = TestTree::create(); 67 68 // Inserting single node 69 root->insertBefore(lastChild.get(), 0); 70 EXPECT_EQ(lastChild->parent(), root.get()); 71 EXPECT_EQ(root->firstChild(), lastChild.get()); 72 EXPECT_EQ(root->lastChild(), lastChild.get()); 73 74 // Then prepend 75 root->insertBefore(firstChild.get(), lastChild.get()); 76 EXPECT_EQ(firstChild->parent(), root.get()); 77 EXPECT_EQ(root->firstChild(), firstChild.get()); 78 EXPECT_EQ(root->lastChild(), lastChild.get()); 79 EXPECT_EQ(firstChild->next(), lastChild.get()); 80 EXPECT_EQ(firstChild.get(), lastChild->previous()); 81 82 // Inserting in the middle 83 root->insertBefore(middleChild.get(), lastChild.get()); 84 EXPECT_EQ(middleChild->parent(), root.get()); 85 EXPECT_EQ(root->firstChild(), firstChild.get()); 86 EXPECT_EQ(root->lastChild(), lastChild.get()); 87 EXPECT_EQ(middleChild->previous(), firstChild.get()); 88 EXPECT_EQ(middleChild->next(), lastChild.get()); 89 EXPECT_EQ(firstChild->next(), middleChild.get()); 90 EXPECT_EQ(lastChild->previous(), middleChild.get()); 91 92 } 93 94 TEST(TreeNodeTest, RemoveSingle) 95 { 96 RefPtr<TestTree> root = TestTree::create(); 97 RefPtr<TestTree> child = TestTree::create(); 98 RefPtr<TestTree> nullNode; 99 100 root->appendChild(child.get()); 101 root->removeChild(child.get()); 102 EXPECT_EQ(child->next(), nullNode.get()); 103 EXPECT_EQ(child->previous(), nullNode.get()); 104 EXPECT_EQ(child->parent(), nullNode.get()); 105 EXPECT_EQ(root->firstChild(), nullNode.get()); 106 EXPECT_EQ(root->lastChild(), nullNode.get()); 107 } 108 109 class Trio { 110 public: 111 Trio() 112 : root(TestTree::create()) 113 , firstChild(TestTree::create()) 114 , middleChild(TestTree::create()) 115 , lastChild(TestTree::create()) 116 { 117 } 118 119 void appendChildren() 120 { 121 root->appendChild(firstChild.get()); 122 root->appendChild(middleChild.get()); 123 root->appendChild(lastChild.get()); 124 } 125 126 RefPtr<TestTree> root; 127 RefPtr<TestTree> firstChild; 128 RefPtr<TestTree> middleChild; 129 RefPtr<TestTree> lastChild; 130 }; 131 132 TEST(TreeNodeTest, RemoveMiddle) 133 { 134 Trio trio; 135 trio.appendChildren(); 136 137 trio.root->removeChild(trio.middleChild.get()); 138 EXPECT_TRUE(trio.middleChild->orphan()); 139 EXPECT_EQ(trio.firstChild->next(), trio.lastChild.get()); 140 EXPECT_EQ(trio.lastChild->previous(), trio.firstChild.get()); 141 EXPECT_EQ(trio.root->firstChild(), trio.firstChild.get()); 142 EXPECT_EQ(trio.root->lastChild(), trio.lastChild.get()); 143 } 144 145 TEST(TreeNodeTest, RemoveLast) 146 { 147 RefPtr<TestTree> nullNode; 148 Trio trio; 149 trio.appendChildren(); 150 151 trio.root->removeChild(trio.lastChild.get()); 152 EXPECT_TRUE(trio.lastChild->orphan()); 153 EXPECT_EQ(trio.middleChild->next(), nullNode.get()); 154 EXPECT_EQ(trio.root->firstChild(), trio.firstChild.get()); 155 EXPECT_EQ(trio.root->lastChild(), trio.middleChild.get()); 156 } 157 158 TEST(TreeNodeTest, RemoveFirst) 159 { 160 RefPtr<TestTree> nullNode; 161 Trio trio; 162 trio.appendChildren(); 163 164 trio.root->removeChild(trio.firstChild.get()); 165 EXPECT_TRUE(trio.firstChild->orphan()); 166 EXPECT_EQ(trio.middleChild->previous(), nullNode.get()); 167 EXPECT_EQ(trio.root->firstChild(), trio.middleChild.get()); 168 EXPECT_EQ(trio.root->lastChild(), trio.lastChild.get()); 169 } 170 171 TEST(TreeNodeTest, TakeChildrenFrom) 172 { 173 RefPtr<TestTree> newParent = TestTree::create(); 174 Trio trio; 175 trio.appendChildren(); 176 177 newParent->takeChildrenFrom(trio.root.get()); 178 179 EXPECT_FALSE(trio.root->hasChildren()); 180 EXPECT_TRUE(newParent->hasChildren()); 181 EXPECT_EQ(trio.firstChild.get(), newParent->firstChild()); 182 EXPECT_EQ(trio.middleChild.get(), newParent->firstChild()->next()); 183 EXPECT_EQ(trio.lastChild.get(), newParent->lastChild()); 184 } 185 186 class TrioWithGrandChild : public Trio { 187 public: 188 TrioWithGrandChild() 189 : grandChild(TestTree::create()) 190 { 191 } 192 193 void appendChildren() 194 { 195 Trio::appendChildren(); 196 middleChild->appendChild(grandChild.get()); 197 } 198 199 RefPtr<TestTree> grandChild; 200 }; 201 202 TEST(TreeNodeTest, TraverseNext) 203 { 204 TrioWithGrandChild trio; 205 trio.appendChildren(); 206 207 TestTree* order[] = { 208 trio.root.get(), trio.firstChild.get(), trio.middleChild.get(), 209 trio.grandChild.get(), trio.lastChild.get() 210 }; 211 212 unsigned orderIndex = 0; 213 for (TestTree* node = trio.root.get(); node; node = traverseNext(node), orderIndex++) 214 EXPECT_EQ(node, order[orderIndex]); 215 EXPECT_EQ(orderIndex, sizeof(order) / sizeof(TestTree*)); 216 } 217 218 TEST(TreeNodeTest, TraverseNextPostORder) 219 { 220 TrioWithGrandChild trio; 221 trio.appendChildren(); 222 223 224 TestTree* order[] = { 225 trio.firstChild.get(), 226 trio.grandChild.get(), trio.middleChild.get(), trio.lastChild.get(), trio.root.get() 227 }; 228 229 unsigned orderIndex = 0; 230 for (TestTree* node = traverseFirstPostOrder(trio.root.get()); node; node = traverseNextPostOrder(node), orderIndex++) 231 EXPECT_EQ(node, order[orderIndex]); 232 EXPECT_EQ(orderIndex, sizeof(order) / sizeof(TestTree*)); 233 234 } 235 236 237 } // namespace 238
