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
35namespace {
36
37class TestTree : public RefCounted<TestTree>, public TreeNode<TestTree> {
38public:
39    static PassRefPtr<TestTree> create() { return adoptRef(new TestTree()); }
40};
41
42TEST(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
61TEST(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
94TEST(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
109class Trio {
110public:
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
132TEST(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
145TEST(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
158TEST(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
171TEST(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
186class TrioWithGrandChild : public Trio {
187public:
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
202TEST(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
218TEST(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