1/*
2 * Copyright (C) 2013 Google 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 are
6 * met:
7 *
8 *     * Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 *     * Redistributions in binary form must reproduce the above
11 * copyright notice, this list of conditions and the following disclaimer
12 * in the documentation and/or other materials provided with the
13 * distribution.
14 *     * Neither the name of Google Inc. nor the names of its
15 * contributors may be used to endorse or promote products derived from
16 * this software without specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 */
30
31#ifndef TreeNode_h
32#define TreeNode_h
33
34#include "wtf/Assertions.h"
35
36namespace WTF {
37
38//
39// TreeNode is generic, ContainerNode-like linked tree data structure.
40// There are a few notable difference between TreeNode and Node:
41//
42//  * Each TreeNode node is NOT ref counted. The user have to retain its lifetime somehow.
43//    FIXME: lifetime management could be parameterized so that ref counted implementations can be used.
44//  * It ASSERT()s invalid input. The callers have to ensure that given parameter is sound.
45//  * There is no branch-leaf difference. Every node can be a parent of other node.
46//
47template <class T>
48class TreeNode {
49public:
50    typedef T NodeType;
51
52    TreeNode()
53        : m_next(0)
54        , m_previous(0)
55        , m_parent(0)
56        , m_firstChild(0)
57        , m_lastChild(0)
58    {
59    }
60
61    NodeType* next() const { return m_next; }
62    NodeType* previous() const { return m_previous; }
63    NodeType* parent() const { return m_parent; }
64    NodeType* firstChild() const { return m_firstChild; }
65    NodeType* lastChild() const { return m_lastChild; }
66    NodeType* here() const { return static_cast<NodeType*>(const_cast<TreeNode*>(this)); }
67
68    bool orphan() const { return !m_parent && !m_next && !m_previous && !m_firstChild && !m_lastChild; }
69    bool hasChildren() const { return m_firstChild; }
70
71    void insertBefore(NodeType* newChild, NodeType* refChild)
72    {
73        ASSERT(!newChild->parent());
74        ASSERT(!newChild->next());
75        ASSERT(!newChild->previous());
76
77        ASSERT(!refChild || this == refChild->parent());
78
79        if (!refChild) {
80            appendChild(newChild);
81            return;
82        }
83
84        NodeType* newPrevious = refChild->previous();
85        newChild->m_parent = here();
86        newChild->m_next = refChild;
87        newChild->m_previous = newPrevious;
88        refChild->m_previous = newChild;
89        if (newPrevious)
90            newPrevious->m_next = newChild;
91        else
92            m_firstChild = newChild;
93    }
94
95    void appendChild(NodeType* child)
96    {
97        ASSERT(!child->parent());
98        ASSERT(!child->next());
99        ASSERT(!child->previous());
100
101        child->m_parent = here();
102
103        if (!m_lastChild) {
104            ASSERT(!m_firstChild);
105            m_lastChild = m_firstChild = child;
106            return;
107        }
108
109        ASSERT(!m_lastChild->m_next);
110        NodeType* oldLast = m_lastChild;
111        m_lastChild = child;
112
113        child->m_previous = oldLast;
114        oldLast->m_next = child;
115    }
116
117    NodeType* removeChild(NodeType* child)
118    {
119        ASSERT(child->parent() == this);
120
121        if (m_firstChild == child)
122            m_firstChild = child->next();
123        if (m_lastChild == child)
124            m_lastChild = child->previous();
125
126        NodeType* oldNext = child->next();
127        NodeType* oldPrevious = child->previous();
128        child->m_parent = child->m_next = child->m_previous = 0;
129
130        if (oldNext)
131            oldNext->m_previous = oldPrevious;
132        if (oldPrevious)
133            oldPrevious->m_next = oldNext;
134
135        return child;
136    }
137
138private:
139    NodeType* m_next;
140    NodeType* m_previous;
141    NodeType* m_parent;
142    NodeType* m_firstChild;
143    NodeType* m_lastChild;
144};
145
146template<class T>
147inline typename TreeNode<T>::NodeType* traverseNext(const TreeNode<T>* current, const TreeNode<T>* stayWithin = 0)
148{
149    if (typename TreeNode<T>::NodeType* next = current->firstChild())
150        return next;
151    if (current == stayWithin)
152        return 0;
153    if (typename TreeNode<T>::NodeType* next = current->next())
154        return next;
155    for (typename TreeNode<T>::NodeType* parent = current->parent(); parent; parent = parent->parent()) {
156        if (parent == stayWithin)
157            return 0;
158        if (typename TreeNode<T>::NodeType* next = parent->next())
159            return next;
160    }
161
162    return 0;
163}
164
165template<class T>
166inline typename TreeNode<T>::NodeType* traverseFirstPostOrder(const TreeNode<T>* current)
167{
168    typename TreeNode<T>::NodeType* first = current->here();
169    while (first->firstChild())
170        first = first->firstChild();
171    return first;
172}
173
174template<class T>
175inline typename TreeNode<T>::NodeType* traverseNextPostOrder(const TreeNode<T>* current, const TreeNode<T>* stayWithin = 0)
176{
177    if (current == stayWithin)
178        return 0;
179
180    typename TreeNode<T>::NodeType* next = current->next();
181    if (!next)
182        return current->parent();
183    while (next->firstChild())
184        next = next->firstChild();
185    return next;
186}
187
188}
189
190using WTF::TreeNode;
191using WTF::traverseNext;
192using WTF::traverseNextPostOrder;
193
194#endif
195