1#include <basis/seadRawPrint.h>
2#include <container/seadTreeNode.h>
3
4namespace sead
5{
6TreeNode::TreeNode()
7{
8 clearLinks();
9}
10
11void TreeNode::clearChildLinksRecursively_()
12{
13 TreeNode* node = this->mChild;
14 while (node != NULL)
15 {
16 TreeNode* next = node->mNext;
17 node->clearChildLinksRecursively_();
18 node->clearLinks();
19 node = next;
20 }
21}
22
23void TreeNode::clearLinks()
24{
25 mPrev = NULL;
26 mParent = NULL;
27 mNext = NULL;
28 mChild = NULL;
29}
30
31s32 TreeNode::countChildren() const
32{
33 s32 count = 0;
34 TreeNode* node = mChild;
35 while (node)
36 {
37 ++count;
38 node = node->mNext;
39 }
40 return count;
41}
42
43void TreeNode::detachAll()
44{
45 detachSubTree();
46 clearChildLinksRecursively_();
47 clearLinks();
48}
49
50void TreeNode::detachSubTree()
51{
52 if (mParent && mParent->mChild == this)
53 {
54 mParent->mChild = mNext;
55 if (mNext)
56 {
57 mNext->mPrev = mPrev;
58 mNext = nullptr;
59 }
60 }
61 else
62 {
63 if (mPrev)
64 mPrev->mNext = mNext;
65 if (mNext)
66 {
67 mNext->mPrev = mPrev;
68 mNext = nullptr;
69 }
70 else if (mParent)
71 {
72 mParent->mChild->mPrev = mPrev;
73 }
74 }
75 mPrev = nullptr;
76 mParent = nullptr;
77}
78
79TreeNode* TreeNode::findRoot()
80{
81 if (!mParent)
82 return this;
83
84 TreeNode* p = mParent;
85 TreeNode* root;
86 do
87 {
88 root = p;
89 SEAD_ASSERT(p != this);
90 p = p->mParent;
91 } while (p);
92 return root;
93}
94
95const TreeNode* TreeNode::findRoot() const
96{
97 if (!mParent)
98 return this;
99
100 TreeNode* p = mParent;
101 TreeNode* root;
102 do
103 {
104 root = p;
105 SEAD_ASSERT(p != this);
106 p = p->mParent;
107 } while (p);
108 return root;
109}
110
111void TreeNode::insertAfterSelf(TreeNode* node)
112{
113 node->detachSubTree();
114
115 TreeNode* next = mNext;
116 mNext = node;
117 node->mPrev = this;
118 node->mNext = next;
119 if (next)
120 next->mPrev = node;
121 else if (mParent)
122 mParent->mChild->mPrev = node;
123 node->mParent = mParent;
124}
125
126void TreeNode::insertBeforeSelf(TreeNode* node)
127{
128 node->detachSubTree();
129
130 TreeNode* prev = mPrev;
131 mPrev = node;
132 node->mPrev = prev;
133 node->mNext = this;
134 if (mParent && mParent->mChild == this)
135 mParent->mChild = node;
136 else if (prev)
137 prev->mNext = node;
138 node->mParent = mParent;
139}
140
141void TreeNode::pushBackChild(TreeNode* node)
142{
143 node->detachSubTree();
144
145 if (mChild)
146 {
147 TreeNode* n = mChild->mPrev;
148 SEAD_ASSERT(n);
149 n->mNext = node;
150 node->mPrev = n;
151 node->mParent = n->mParent;
152 mChild->mPrev = node;
153 }
154 else
155 {
156 mChild = node;
157 node->mParent = this;
158 node->mPrev = node;
159 }
160}
161
162void TreeNode::pushBackSibling(TreeNode* node)
163{
164 node->detachSubTree();
165
166 TreeNode* m;
167 if (mParent && mParent->mChild)
168 {
169 m = mParent->mChild->mPrev;
170 mParent->mChild->mPrev = node;
171 }
172 else
173 {
174 m = this;
175 while (m->mNext)
176 m = m->mNext;
177 }
178 m->mNext = node;
179 node->mPrev = m;
180 node->mParent = m->mParent;
181}
182
183void TreeNode::pushFrontChild(TreeNode* node)
184{
185 node->detachSubTree();
186 if (mChild)
187 {
188 node->mNext = mChild;
189 node->mPrev = mChild->mPrev;
190 mChild->mPrev = node;
191 mChild = node;
192 node->mParent = this;
193 }
194 else
195 {
196 mChild = node;
197 node->mParent = this;
198 node->mPrev = node;
199 }
200}
201} // namespace sead
202