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(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
61TEST(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
94TEST(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
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(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
145TEST(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
158TEST(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
171class TrioWithGrandChild : public Trio {
172public:
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
187TEST(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
203TEST(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