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(WTF, TreeNodeAppendChild) 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 ASSERT_EQ(root->firstChild(), firstChild.get()); 50 ASSERT_EQ(root->lastChild(), firstChild.get()); 51 ASSERT_EQ(firstChild->parent(), root.get()); 52 53 root->appendChild(lastChild.get()); 54 ASSERT_EQ(root->firstChild(), firstChild.get()); 55 ASSERT_EQ(root->lastChild(), lastChild.get()); 56 ASSERT_EQ(lastChild->previous(), firstChild.get()); 57 ASSERT_EQ(firstChild->next(), lastChild.get()); 58 ASSERT_EQ(lastChild->parent(), root.get()); 59 } 60 61 TEST(WTF, TreeNodeInsertBefore) 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 ASSERT_EQ(lastChild->parent(), root.get()); 71 ASSERT_EQ(root->firstChild(), lastChild.get()); 72 ASSERT_EQ(root->lastChild(), lastChild.get()); 73 74 // Then prepend 75 root->insertBefore(firstChild.get(), lastChild.get()); 76 ASSERT_EQ(firstChild->parent(), root.get()); 77 ASSERT_EQ(root->firstChild(), firstChild.get()); 78 ASSERT_EQ(root->lastChild(), lastChild.get()); 79 ASSERT_EQ(firstChild->next(), lastChild.get()); 80 ASSERT_EQ(firstChild.get(), lastChild->previous()); 81 82 // Inserting in the middle 83 root->insertBefore(middleChild.get(), lastChild.get()); 84 ASSERT_EQ(middleChild->parent(), root.get()); 85 ASSERT_EQ(root->firstChild(), firstChild.get()); 86 ASSERT_EQ(root->lastChild(), lastChild.get()); 87 ASSERT_EQ(middleChild->previous(), firstChild.get()); 88 ASSERT_EQ(middleChild->next(), lastChild.get()); 89 ASSERT_EQ(firstChild->next(), middleChild.get()); 90 ASSERT_EQ(lastChild->previous(), middleChild.get()); 91 92 } 93 94 TEST(WTF, TreeNodeRemoveSingle) 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 ASSERT_EQ(child->next(), nullNode.get()); 103 ASSERT_EQ(child->previous(), nullNode.get()); 104 ASSERT_EQ(child->parent(), nullNode.get()); 105 ASSERT_EQ(root->firstChild(), nullNode.get()); 106 ASSERT_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(WTF, TreeNodeRemoveMiddle) 133 { 134 Trio trio; 135 trio.appendChildren(); 136 137 trio.root->removeChild(trio.middleChild.get()); 138 ASSERT_TRUE(trio.middleChild->orphan()); 139 ASSERT_EQ(trio.firstChild->next(), trio.lastChild.get()); 140 ASSERT_EQ(trio.lastChild->previous(), trio.firstChild.get()); 141 ASSERT_EQ(trio.root->firstChild(), trio.firstChild.get()); 142 ASSERT_EQ(trio.root->lastChild(), trio.lastChild.get()); 143 } 144 145 TEST(WTF, TreeNodeRemoveLast) 146 { 147 RefPtr<TestTree> nullNode; 148 Trio trio; 149 trio.appendChildren(); 150 151 trio.root->removeChild(trio.lastChild.get()); 152 ASSERT_TRUE(trio.lastChild->orphan()); 153 ASSERT_EQ(trio.middleChild->next(), nullNode.get()); 154 ASSERT_EQ(trio.root->firstChild(), trio.firstChild.get()); 155 ASSERT_EQ(trio.root->lastChild(), trio.middleChild.get()); 156 } 157 158 TEST(WTF, TreeNodeRemoveFirst) 159 { 160 RefPtr<TestTree> nullNode; 161 Trio trio; 162 trio.appendChildren(); 163 164 trio.root->removeChild(trio.firstChild.get()); 165 ASSERT_TRUE(trio.firstChild->orphan()); 166 ASSERT_EQ(trio.middleChild->previous(), nullNode.get()); 167 ASSERT_EQ(trio.root->firstChild(), trio.middleChild.get()); 168 ASSERT_EQ(trio.root->lastChild(), trio.lastChild.get()); 169 } 170 171 class TrioWithGrandChild : public Trio { 172 public: 173 TrioWithGrandChild() 174 : grandChild(TestTree::create()) 175 { 176 } 177 178 void appendChildren() 179 { 180 Trio::appendChildren(); 181 middleChild->appendChild(grandChild.get()); 182 } 183 184 RefPtr<TestTree> grandChild; 185 }; 186 187 TEST(WTF, TreeNodeTraverseNext) 188 { 189 TrioWithGrandChild trio; 190 trio.appendChildren(); 191 192 TestTree* order[] = { 193 trio.root.get(), trio.firstChild.get(), trio.middleChild.get(), 194 trio.grandChild.get(), trio.lastChild.get() 195 }; 196 197 unsigned orderIndex = 0; 198 for (TestTree* node = trio.root.get(); node; node = traverseNext(node), orderIndex++) 199 ASSERT_EQ(node, order[orderIndex]); 200 ASSERT_EQ(orderIndex, sizeof(order) / sizeof(TestTree*)); 201 } 202 203 TEST(WTF, TreeNodeTraverseNextPostORder) 204 { 205 TrioWithGrandChild trio; 206 trio.appendChildren(); 207 208 209 TestTree* order[] = { 210 trio.firstChild.get(), 211 trio.grandChild.get(), trio.middleChild.get(), trio.lastChild.get(), trio.root.get() 212 }; 213 214 unsigned orderIndex = 0; 215 for (TestTree* node = traverseFirstPostOrder(trio.root.get()); node; node = traverseNextPostOrder(node), orderIndex++) 216 ASSERT_EQ(node, order[orderIndex]); 217 ASSERT_EQ(orderIndex, sizeof(order) / sizeof(TestTree*)); 218 219 } 220 221 222 } // namespace 223
