third_party/WebKit/Source/wtf/TreeNodeTest.cpp

   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 #include "wtf/TreeNode.h"
  28
  29 #include "wtf/PassRefPtr.h"
  30 #include "wtf/RefCounted.h"
  31 #include "wtf/RefPtr.h"
  32 #include <gtest/gtest.h>
  33
  34 namespace WTF {
  35
  36 class TestTree : public RefCounted<TestTree>, public TreeNode<TestTree> {
  37 public:
  38     static PassRefPtr<TestTree> create() { return adoptRef(new TestTree()); }
  39 };
  40
  41 TEST(TreeNodeTest, AppendChild)
  42 {
  43     RefPtr<TestTree> root = TestTree::create();
  44     RefPtr<TestTree> firstChild = TestTree::create();
  45     RefPtr<TestTree> lastChild = TestTree::create();
  46
  47     root->appendChild(firstChild.get());
  48     EXPECT_EQ(root->firstChild(), firstChild.get());
  49     EXPECT_EQ(root->lastChild(), firstChild.get());
  50     EXPECT_EQ(firstChild->parent(), root.get());
  51
  52     root->appendChild(lastChild.get());
  53     EXPECT_EQ(root->firstChild(), firstChild.get());
  54     EXPECT_EQ(root->lastChild(), lastChild.get());
  55     EXPECT_EQ(lastChild->previous(), firstChild.get());
  56     EXPECT_EQ(firstChild->next(), lastChild.get());
  57     EXPECT_EQ(lastChild->parent(), root.get());
  58 }
  59
  60 TEST(TreeNodeTest, InsertBefore)
  61 {
  62     RefPtr<TestTree> root = TestTree::create();
  63     RefPtr<TestTree> firstChild = TestTree::create();
  64     RefPtr<TestTree> middleChild = TestTree::create();
  65     RefPtr<TestTree> lastChild = TestTree::create();
  66
  67     // Inserting single node
  68     root->insertBefore(lastChild.get(), 0);
  69     EXPECT_EQ(lastChild->parent(), root.get());
  70     EXPECT_EQ(root->firstChild(), lastChild.get());
  71     EXPECT_EQ(root->lastChild(), lastChild.get());
  72
  73     // Then prepend
  74     root->insertBefore(firstChild.get(), lastChild.get());
  75     EXPECT_EQ(firstChild->parent(), root.get());
  76     EXPECT_EQ(root->firstChild(), firstChild.get());
  77     EXPECT_EQ(root->lastChild(), lastChild.get());
  78     EXPECT_EQ(firstChild->next(), lastChild.get());
  79     EXPECT_EQ(firstChild.get(), lastChild->previous());
  80
  81     // Inserting in the middle
  82     root->insertBefore(middleChild.get(), lastChild.get());
  83     EXPECT_EQ(middleChild->parent(), root.get());
  84     EXPECT_EQ(root->firstChild(), firstChild.get());
  85     EXPECT_EQ(root->lastChild(), lastChild.get());
  86     EXPECT_EQ(middleChild->previous(), firstChild.get());
  87     EXPECT_EQ(middleChild->next(), lastChild.get());
  88     EXPECT_EQ(firstChild->next(), middleChild.get());
  89     EXPECT_EQ(lastChild->previous(), middleChild.get());
  90
  91 }
  92
  93 TEST(TreeNodeTest, RemoveSingle)
  94 {
  95     RefPtr<TestTree> root = TestTree::create();
  96     RefPtr<TestTree> child = TestTree::create();
  97     RefPtr<TestTree> nullNode;
  98
  99     root->appendChild(child.get());
 100     root->removeChild(child.get());
 101     EXPECT_EQ(child->next(), nullNode.get());
 102     EXPECT_EQ(child->previous(), nullNode.get());
 103     EXPECT_EQ(child->parent(), nullNode.get());
 104     EXPECT_EQ(root->firstChild(), nullNode.get());
 105     EXPECT_EQ(root->lastChild(), nullNode.get());
 106 }
 107
 108 class Trio {
 109 public:
 110     Trio()
 111         : root(TestTree::create())
 112         , firstChild(TestTree::create())
 113         , middleChild(TestTree::create())
 114         , lastChild(TestTree::create())
 115     {
 116     }
 117
 118     void appendChildren()
 119     {
 120         root->appendChild(firstChild.get());
 121         root->appendChild(middleChild.get());
 122         root->appendChild(lastChild.get());
 123     }
 124
 125     RefPtr<TestTree> root;
 126     RefPtr<TestTree> firstChild;
 127     RefPtr<TestTree> middleChild;
 128     RefPtr<TestTree> lastChild;
 129 };
 130
 131 TEST(TreeNodeTest, RemoveMiddle)
 132 {
 133     Trio trio;
 134     trio.appendChildren();
 135
 136     trio.root->removeChild(trio.middleChild.get());
 137     EXPECT_TRUE(trio.middleChild->orphan());
 138     EXPECT_EQ(trio.firstChild->next(), trio.lastChild.get());
 139     EXPECT_EQ(trio.lastChild->previous(), trio.firstChild.get());
 140     EXPECT_EQ(trio.root->firstChild(), trio.firstChild.get());
 141     EXPECT_EQ(trio.root->lastChild(), trio.lastChild.get());
 142 }
 143
 144 TEST(TreeNodeTest, RemoveLast)
 145 {
 146     RefPtr<TestTree> nullNode;
 147     Trio trio;
 148     trio.appendChildren();
 149
 150     trio.root->removeChild(trio.lastChild.get());
 151     EXPECT_TRUE(trio.lastChild->orphan());
 152     EXPECT_EQ(trio.middleChild->next(), nullNode.get());
 153     EXPECT_EQ(trio.root->firstChild(), trio.firstChild.get());
 154     EXPECT_EQ(trio.root->lastChild(), trio.middleChild.get());
 155 }
 156
 157 TEST(TreeNodeTest, RemoveFirst)
 158 {
 159     RefPtr<TestTree> nullNode;
 160     Trio trio;
 161     trio.appendChildren();
 162
 163     trio.root->removeChild(trio.firstChild.get());
 164     EXPECT_TRUE(trio.firstChild->orphan());
 165     EXPECT_EQ(trio.middleChild->previous(), nullNode.get());
 166     EXPECT_EQ(trio.root->firstChild(), trio.middleChild.get());
 167     EXPECT_EQ(trio.root->lastChild(), trio.lastChild.get());
 168 }
 169
 170 TEST(TreeNodeTest, TakeChildrenFrom)
 171 {
 172     RefPtr<TestTree> newParent = TestTree::create();
 173     Trio trio;
 174     trio.appendChildren();
 175
 176     newParent->takeChildrenFrom(trio.root.get());
 177
 178     EXPECT_FALSE(trio.root->hasChildren());
 179     EXPECT_TRUE(newParent->hasChildren());
 180     EXPECT_EQ(trio.firstChild.get(), newParent->firstChild());
 181     EXPECT_EQ(trio.middleChild.get(), newParent->firstChild()->next());
 182     EXPECT_EQ(trio.lastChild.get(), newParent->lastChild());
 183 }
 184
 185 class TrioWithGrandChild : public Trio {
 186 public:
 187     TrioWithGrandChild()
 188         : grandChild(TestTree::create())
 189     {
 190     }
 191
 192     void appendChildren()
 193     {
 194         Trio::appendChildren();
 195         middleChild->appendChild(grandChild.get());
 196     }
 197
 198     RefPtr<TestTree> grandChild;
 199 };
 200
 201 TEST(TreeNodeTest, TraverseNext)
 202 {
 203     TrioWithGrandChild trio;
 204     trio.appendChildren();
 205
 206     TestTree* order[] = {
 207         trio.root.get(), trio.firstChild.get(), trio.middleChild.get(),
 208         trio.grandChild.get(), trio.lastChild.get()
 209     };
 210
 211     unsigned orderIndex = 0;
 212     for (TestTree* node = trio.root.get(); node; node = traverseNext(node), orderIndex++)
 213         EXPECT_EQ(node, order[orderIndex]);
 214     EXPECT_EQ(orderIndex, sizeof(order) / sizeof(TestTree*));
 215 }
 216
 217 TEST(TreeNodeTest, TraverseNextPostORder)
 218 {
 219     TrioWithGrandChild trio;
 220     trio.appendChildren();
 221
 222
 223     TestTree* order[] = {
 224         trio.firstChild.get(),
 225         trio.grandChild.get(), trio.middleChild.get(), trio.lastChild.get(), trio.root.get()
 226     };
 227
 228     unsigned orderIndex = 0;
 229     for (TestTree* node = traverseFirstPostOrder(trio.root.get()); node; node = traverseNextPostOrder(node), orderIndex++)
 230         EXPECT_EQ(node, order[orderIndex]);
 231     EXPECT_EQ(orderIndex, sizeof(order) / sizeof(TestTree*));
 232
 233 }
 234
 235 } // namespace WTF