sead
Loading...
Searching...
No Matches
seadTreeMapImpl.hpp
Go to the documentation of this file.
1#pragma once
2
3namespace sead {
4
5template <typename Key>
6TreeMapNode<Key>*
7TreeMapImpl<Key>::insert(Node* h, Node* node)
8{
9 if (h == nullptr)
10 {
11 node->mColor_ = Node::cRed_;
12 node->mLeft_ = nullptr;
13 node->mRight_ = nullptr;
14 return node;
15 }
16
17 s32 cmp = node->mKey_.compare(h->mKey_);
18 if (cmp < 0)
19 h->mLeft_ = insert(h->mLeft_, node);
20 else if (cmp > 0)
21 h->mRight_ = insert(h->mRight_, node);
22 else
23 {
24 if (h != node)
25 {
26 node->mRight_ = h->mRight_;
27 node->mLeft_ = h->mLeft_;
28 node->mColor_ = h->mColor_;
29 h->erase_();
30 }
31 h = node;
32 }
33
34 if (isRed(h->mRight_) && !isRed(h->mLeft_))
35 h = rotateLeft(h);
36
37 if (isRed(h->mLeft_) && isRed(h->mLeft_->mLeft_))
38 h = rotateRight(h);
39
40 if (isRed(h->mLeft_) && isRed(h->mRight_))
41 flipColors(h);
42
43 return h;
44}
45
46template <typename Key>
47TreeMapNode<Key>*
48TreeMapImpl<Key>::erase(Node* h, const Key& key)
49{
50 if (key.compare(h->mKey_) < 0)
51 {
52 if (!isRed(h->mLeft_) && !isRed(h->mLeft_->mLeft_))
53 h = moveRedLeft(h);
54
55 h->mLeft_ = erase(h->mLeft_, key);
56 }
57 else
58 {
59 if (isRed(h->mLeft_))
60 h = rotateRight(h);
61
62 if (key.compare(h->mKey_) == 0 && h->mRight_ == nullptr)
63 {
64 h->erase_();
65 return nullptr;
66 }
67
68 if (!isRed(h->mRight_) && !isRed(h->mRight_->mLeft_))
69 h = moveRedRight(h);
70
71 if (key.compare(h->mKey_) == 0)
72 {
73 Node* node = find(h->mRight_, min(h->mRight_)->mKey_);
74 node->mRight_ = eraseMin(h->mRight_);
75 node->mLeft_ = h->mLeft_;
76 node->mColor_ = h->mColor_;
77 h->erase_();
78 h = node;
79 }
80 else
81 {
82 h->mRight_ = erase(h->mRight_, key);
83 }
84 }
85
86 return fixUp(h);
87}
88
89template <typename Key>
90TreeMapNode<Key>*
91TreeMapImpl<Key>::find(Node* node, const Key& key) const
92{
93 while (node != nullptr)
94 {
95 s32 cmp = key.compare(node->mKey_);
96 if (cmp < 0)
97 node = node->mLeft_;
98 else if (cmp > 0)
99 node = node->mRight_;
100 else
101 return node;
102 }
103 return nullptr;
104}
105
106template <typename Key>
107inline TreeMapNode<Key>*
108TreeMapImpl<Key>::min(Node* h)
109{
110 while (h->mLeft_ != nullptr)
111 h = h->mLeft_;
112
113 return h;
114}
115
116template <typename Key>
117inline TreeMapNode<Key>*
118TreeMapImpl<Key>::eraseMin(Node* h)
119{
120 if (h->mLeft_ == nullptr)
121 return nullptr;
122
123 if (!isRed(h->mLeft_) && !isRed(h->mLeft_->mLeft_))
124 h = moveRedLeft(h);
125
126 h->mLeft_ = eraseMin(h->mLeft_);
127
128 return fixUp(h);
129}
130
131template <typename Key>
132inline TreeMapNode<Key>*
133TreeMapImpl<Key>::moveRedLeft(Node* h)
134{
135 flipColors(h);
136 if (isRed(h->mRight_->mLeft_))
137 {
138 h->mRight_ = rotateRight(h->mRight_);
139 h = rotateLeft(h);
140 flipColors(h);
141 }
142 return h;
143}
144
145template <typename Key>
146inline TreeMapNode<Key>*
147TreeMapImpl<Key>::moveRedRight(Node* h)
148{
149 flipColors(h);
150 if (isRed(h->mLeft_->mLeft_))
151 {
152 h = rotateRight(h);
153 flipColors(h);
154 }
155 return h;
156}
157
158template <typename Key>
159inline TreeMapNode<Key>*
160TreeMapImpl<Key>::fixUp(Node* h)
161{
162 if (isRed(h->mRight_))
163 h = rotateLeft(h);
164
165 if (isRed(h->mLeft_) && isRed(h->mLeft_->mLeft_))
166 h = rotateRight(h);
167
168 if (isRed(h->mLeft_) && isRed(h->mRight_))
169 flipColors(h);
170
171 return h;
172}
173
174template <typename Key>
175inline TreeMapNode<Key>*
176TreeMapImpl<Key>::rotateLeft(Node* h)
177{
178 Node* n = h->mRight_;
179 h->mRight_ = n->mLeft_;
180 n->mLeft_ = h;
181 n->mColor_ = h->mColor_;
182 h->mColor_ = Node::cRed_;
183 return n;
184}
185
186template <typename Key>
187inline TreeMapNode<Key>*
188TreeMapImpl<Key>::rotateRight(Node* h)
189{
190 Node* n = h->mLeft_;
191 h->mLeft_ = n->mRight_;
192 n->mRight_ = h;
193 n->mColor_ = h->mColor_;
194 h->mColor_ = Node::cRed_;
195 return n;
196}
197
198template <typename Key>
199inline void
206
207template <typename Key>
208inline bool
209TreeMapImpl<Key>::isRed(Node* h)
210{
211 if (h == nullptr)
212 return false;
213
214 return h->mColor_ == Node::cRed_;
215}
216
217} // namespace sead
sead
Definition seadAssert.h:44