|
0
|
1 using System.Collections;
|
|
|
2 using System;
|
|
|
3 using UnityEngine;
|
|
|
4
|
|
|
5
|
|
|
6 public abstract class TreeMapNode<K,V>
|
|
|
7 {
|
|
|
8 // K,Vがnullableではないので受け付けない
|
|
|
9 // ジェネリックの扱いがJavaとちがうー＞特にnullの扱いが面倒。
|
|
|
10 protected K key;
|
|
|
11 protected V value;
|
|
|
12 protected TreeMapNode<K,V> right;
|
|
|
13 protected TreeMapNode<K,V> left;
|
|
|
14
|
|
|
15 void Start(){
|
|
|
16 key = default(K);
|
|
|
17 value = default(V);
|
|
|
18 }
|
|
|
19
|
|
|
20 // Use this for initialization
|
|
|
21 public TreeMapNode (K key, V value)
|
|
|
22 {
|
|
|
23 this.key = key;
|
|
|
24 this.value = value;
|
|
|
25 }
|
|
|
26
|
|
|
27 public TreeMapNode (K key, V value, TreeMapNode<K,V> left, TreeMapNode<K,V> right)
|
|
|
28 {
|
|
|
29 this.key = key;
|
|
|
30 this.value = value;
|
|
|
31 this.right = right;
|
|
|
32 this.left = left;
|
|
|
33 }
|
|
|
34
|
|
|
35 public TreeMapNode<K,V> lefts ()
|
|
|
36 {
|
|
|
37 return left;
|
|
|
38 }
|
|
|
39
|
|
|
40
|
|
|
41 public int compare(K compareKey, Comparer ctr) {
|
|
|
42 return ctr.Compare(compareKey, this.getKey());
|
|
|
43 }
|
|
|
44
|
|
|
45 public V get (K key, Comparer ctr)
|
|
|
46 {
|
|
|
47 TreeMapNode<K,V> cur = this;
|
|
|
48 int result = cur.compare (key, ctr);
|
|
|
49 while (cur.isNotEmpty ()) {
|
|
|
50 if (result > 0) {
|
|
|
51 cur = cur.rights ();
|
|
|
52 Debug.Log (cur);
|
|
|
53 } else if (result < 0) {
|
|
|
54 cur = cur.lefts ();
|
|
|
55 } else if (result == 0) {
|
|
|
56 if (cur != null) {
|
|
|
57 return cur.getValue ();
|
|
|
58 }
|
|
|
59 }
|
|
|
60 }
|
|
|
61 return default(V); // Optional<V>.ofNullable (null);
|
|
|
62 }
|
|
|
63
|
|
|
64
|
|
|
65
|
|
|
66 public TreeMapNode<K,V> rights () {
|
|
|
67 return right;
|
|
|
68 }
|
|
|
69
|
|
|
70 public K getKey () {
|
|
|
71 return key;
|
|
|
72 }
|
|
|
73
|
|
|
74 public V getValue () {
|
|
|
75 return value;
|
|
|
76 }
|
|
|
77
|
|
|
78 // may be to use Comparer??
|
|
|
79 public TreeMapNode<K,V> put (K k, V v,Comparer ctr) {
|
|
|
80
|
|
|
81 if (!isNotEmpty ()) {
|
|
|
82 return createNode (k, value, left, right);
|
|
|
83 }
|
|
|
84
|
|
|
85 int result = compare (k,ctr);
|
|
|
86 if (result > 0) {
|
|
|
87 TreeMapNode<K,V> node = right.put (k, value,ctr);
|
|
|
88 node = createNode (key, this.value, left, node);
|
|
|
89 return node.insBalance ();
|
|
|
90 } else if (result < 0) {
|
|
|
91 TreeMapNode<K,V> node = left.put (k, value,ctr);
|
|
|
92 return createNode (key, this.value, node, right).insBalance ();
|
|
|
93 }
|
|
|
94 return createNode (key, value, left, right);
|
|
|
95 }
|
|
|
96
|
|
|
97 public rebuildNode<K,V> delete (K key, TreeMapNode<K,V> parent, Comparer ctr, Rotate side)
|
|
|
98 {
|
|
|
99 if (this.isNotEmpty ()) {
|
|
|
100 rebuildNode<K,V> rebuildNode;
|
|
|
101 int result = compare(key, ctr);
|
|
|
102 if (result > 0) {
|
|
|
103 rebuildNode = right.delete (key, this, ctr, Rotate.R);
|
|
|
104 } else if (result < 0) {
|
|
|
105 rebuildNode = left.delete (key, this, ctr, Rotate.L);
|
|
|
106 } else {
|
|
|
107 rebuildNode = replaceNode (parent, ctr);
|
|
|
108 }
|
|
|
109 if (parent == null) {
|
|
|
110 return rebuildNode;
|
|
|
111 }
|
|
|
112 TreeMapNode<K,V> node = rebuildNode.getNode ();
|
|
|
113 if (rebuildNode.rebuilds ()) {
|
|
|
114 // ここのエラーは後で
|
|
|
115 return node.deleteBalance (parent, ctr);
|
|
|
116 }
|
|
|
117 TreeMapNode<K,V> newParent;
|
|
|
118 if (side == Rotate.L) {
|
|
|
119 newParent = parent.createNode (parent.getKey (), parent.getValue (), node, parent.rights ());
|
|
|
120 } else {
|
|
|
121 newParent = parent.createNode (parent.getKey (), parent.getValue (), parent.lefts (), node);
|
|
|
122 }
|
|
|
123 return new rebuildNode<K,V> (false, newParent);
|
|
|
124 }
|
|
|
125 return null;
|
|
|
126 }
|
|
|
127
|
|
|
128 public rebuildNode<K,V> deleteSubTreeMaxNode (TreeMapNode<K, V> parent, Comparer ctr, Rotate side)
|
|
|
129 {
|
|
|
130 rebuildNode<K,V> rebuildNode;
|
|
|
131 TreeMapNode<K, V> node;
|
|
|
132 if (rights ().isNotEmpty ()) {// 最大値のノードが取得できるまで潜る
|
|
|
133 rebuildNode = rights ().deleteSubTreeMaxNode (this, ctr, Rotate.R);
|
|
|
134 } else {
|
|
|
135 rebuildNode = this.replaceNode (parent, ctr);
|
|
|
136 }
|
|
|
137 if (parent == null)
|
|
|
138 return rebuildNode;
|
|
|
139
|
|
|
140 if (rebuildNode.rebuilds ()) {
|
|
|
141 node = rebuildNode.getNode ();
|
|
|
142 return node.deleteBalance (parent, ctr);
|
|
|
143 }
|
|
|
144 if (side == Rotate.R)
|
|
|
145 node = parent.createNode (parent.getKey (), parent.getValue (), parent.lefts (), rebuildNode.getNode ());
|
|
|
146 else
|
|
|
147 node = parent.createNode (parent.getKey (), parent.getValue (), rebuildNode.getNode (), parent.rights ());
|
|
|
148 return new rebuildNode<K,V> (false, node);
|
|
|
149 }
|
|
|
150
|
|
|
151
|
|
|
152 public rebuildNode<K, V> deleteBalance (TreeMapNode<K, V> parent, Comparer ctr)
|
|
|
153 {
|
|
|
154 TreeMapNode<K, V> newNode = null;
|
|
|
155 if (!isRed ()) {
|
|
|
156 if (0 > compare (parent.getKey (), ctr)) {
|
|
|
157 bool rightChild = parent.lefts ().rights ().isRed ();
|
|
|
158 bool leftChild = parent.lefts ().lefts ().isRed ();
|
|
|
159
|
|
|
160 if (!parent.isRed ()) {
|
|
|
161 if (!parent.lefts ().isRed ()) {
|
|
|
162 if (!rightChild && !leftChild) {
|
|
|
163 newNode = rebuildThree (parent, Rotate.R);
|
|
|
164 return new rebuildNode<K,V> (true, newNode);
|
|
|
165 }
|
|
|
166 if (rightChild) {
|
|
|
167 newNode = rebuildfive (parent, Rotate.R);
|
|
|
168 return new rebuildNode<K,V> (false, newNode);
|
|
|
169 } else {
|
|
|
170 newNode = rebuildsix (parent, Rotate.R);
|
|
|
171 return new rebuildNode<K,V> (false, newNode);
|
|
|
172 }
|
|
|
173 } else { // 左の子が赤
|
|
|
174 newNode = rebuildTwo (parent, ctr, Rotate.R);
|
|
|
175 return new rebuildNode<K,V> (false, newNode);
|
|
|
176 }
|
|
|
177 } else { // 親が赤
|
|
|
178 if (!rightChild && !leftChild) {
|
|
|
179 newNode = rebuildFour (parent, Rotate.R);
|
|
|
180 return new rebuildNode<K,V> (false, newNode);
|
|
|
181 }
|
|
|
182 if (rightChild) {
|
|
|
183 newNode = rebuildfive (parent, Rotate.R);
|
|
|
184 return new rebuildNode<K,V> (false, newNode);
|
|
|
185 } else {
|
|
|
186 newNode = rebuildsix (parent, Rotate.R);
|
|
|
187 return new rebuildNode<K,V> (false, newNode);
|
|
|
188 }
|
|
|
189 }
|
|
|
190 } else {
|
|
|
191 bool rightChild = parent.rights ().rights ().isRed ();
|
|
|
192 bool leftChild = parent.rights ().lefts ().isRed ();
|
|
|
193
|
|
|
194 if (!parent.isRed ()) { // 親が黒
|
|
|
195 if (!parent.rights ().isRed ()) { // 左の子が黒
|
|
|
196 if (!rightChild && !leftChild) {
|
|
|
197 newNode = rebuildThree (parent, Rotate.L);
|
|
|
198 return new rebuildNode<K,V> (true, newNode);
|
|
|
199 }
|
|
|
200 if (rightChild) {
|
|
|
201 newNode = rebuildsix (parent, Rotate.L);
|
|
|
202 return new rebuildNode<K,V> (false, newNode);
|
|
|
203 } else {
|
|
|
204 newNode = rebuildfive (parent, Rotate.L);
|
|
|
205 return new rebuildNode<K,V> (false, newNode);
|
|
|
206 }
|
|
|
207 } else { // 左の子が赤
|
|
|
208 newNode = rebuildTwo (parent, ctr, Rotate.L);
|
|
|
209 return new rebuildNode<K,V> (false, newNode);
|
|
|
210 }
|
|
|
211 } else { // 親が赤
|
|
|
212 if (!rightChild && !leftChild) {
|
|
|
213 newNode = rebuildFour (parent, Rotate.L);
|
|
|
214 return new rebuildNode<K,V> (false, newNode);
|
|
|
215 }
|
|
|
216 if (rightChild) {
|
|
|
217 newNode = rebuildsix (parent, Rotate.L);
|
|
|
218 return new rebuildNode<K,V> (false, newNode);
|
|
|
219 } else {
|
|
|
220 newNode = rebuildfive (parent, Rotate.L);
|
|
|
221 return new rebuildNode<K,V> (false, newNode);
|
|
|
222 }
|
|
|
223 }
|
|
|
224 }
|
|
|
225 }
|
|
|
226 if (0 > (compare (parent.getKey (), ctr))) {
|
|
|
227 newNode = parent.createNode (parent.getKey (), parent.getValue (), parent.lefts (), this);
|
|
|
228 return new rebuildNode<K,V> (false, newNode);
|
|
|
229 } else {
|
|
|
230 newNode = parent.createNode (parent.getKey (), parent.getValue (), this, parent.rights ());
|
|
|
231 return new rebuildNode<K,V> (false, newNode);
|
|
|
232 }
|
|
|
233 }
|
|
|
234
|
|
|
235 protected TreeMapNode<K, V> rebuildTwo (TreeMapNode<K, V> parent, Comparer ctr, Rotate side)
|
|
|
236 { // case2
|
|
|
237 if (side == Rotate.L) { // rotate Left
|
|
|
238 TreeMapNode<K, V> node = parent.rights ();
|
|
|
239 TreeMapNode<K, V> leftSubTreeRoot = node.createNode (parent.getKey (), parent.getValue (), this, node.lefts ()); // check
|
|
|
240 rebuildNode<K, V> rebuildNode = new rebuildNode<K,V> (false, leftSubTreeRoot);
|
|
|
241 rebuildNode<K, V> leftNodeRebuildNode = this.deleteBalance (rebuildNode.getNode (), ctr);
|
|
|
242 TreeMapNode<K, V> rightNode = node.rights ();
|
|
|
243 return parent.createNode (node.getKey (), node.getValue (), leftNodeRebuildNode.getNode (), rightNode);
|
|
|
244 } else { // rotate Right
|
|
|
245 TreeMapNode<K, V> node = parent.lefts ();
|
|
|
246 TreeMapNode<K, V> rightSubTreeRoot = node.createNode (parent.getKey (), parent.getValue (), node.rights (), this);
|
|
|
247 rebuildNode<K, V> rightSubTreeRebuildNode = new rebuildNode<K,V> (false, rightSubTreeRoot);
|
|
|
248 rebuildNode<K, V> rightNodeRebuildNode = this.deleteBalance (rightSubTreeRebuildNode.getNode (), ctr);
|
|
|
249 TreeMapNode<K, V> leftNode = node.lefts ();
|
|
|
250 return parent.createNode (node.getKey (), node.getValue (), leftNode, rightNodeRebuildNode.getNode ());
|
|
|
251 }
|
|
|
252 }
|
|
|
253
|
|
|
254 protected TreeMapNode<K, V> rebuildThree (TreeMapNode<K, V> parent, Rotate side)
|
|
|
255 { // case3 再帰
|
|
|
256 if (side == Rotate.L) {
|
|
|
257 TreeMapNode<K, V> rightNode;
|
|
|
258 if (parent.rights ().isNotEmpty ())
|
|
|
259 rightNode = new RedNode<K,V> (parent.rights ().getKey (), parent.rights ().getValue (), parent.rights ().lefts (), parent.rights ().rights ()); // check
|
|
|
260 else
|
|
|
261 rightNode = new EmptyNode<K,V> ();
|
|
|
262 return parent.createNode (parent.getKey (), parent.getValue (), this, rightNode);
|
|
|
263 } else {
|
|
|
264 TreeMapNode<K, V> leftNode;
|
|
|
265 if (parent.lefts ().isNotEmpty ())
|
|
|
266 leftNode = new RedNode<K,V> (parent.lefts ().getKey (), parent.lefts ().getValue (), parent.lefts ().lefts (), parent.lefts ().rights ()); // check
|
|
|
267 else
|
|
|
268 leftNode = new EmptyNode<K,V> ();
|
|
|
269 return parent.createNode (parent.getKey (), parent.getValue (), leftNode, this);
|
|
|
270 }
|
|
|
271 }
|
|
|
272
|
|
|
273 protected TreeMapNode<K, V> rebuildFour (TreeMapNode<K, V> parent, Rotate side)
|
|
|
274 { // case 4
|
|
|
275 if (side == Rotate.R) {
|
|
|
276 TreeMapNode<K, V> leftNode = new RedNode<K,V> (parent.lefts ().getKey (), parent.lefts ().getValue (), parent.lefts ().lefts (), parent.lefts ().rights ());
|
|
|
277 return new BlackNode<K,V> (parent.getKey (), parent.getValue (), leftNode, this);
|
|
|
278 } else {
|
|
|
279 TreeMapNode<K, V> rightNode = new RedNode<K,V> (parent.rights ().getKey (), parent.rights ().getValue (), parent.rights ().lefts (), parent.rights ().rights ());
|
|
|
280 return new BlackNode<K,V> (parent.getKey (), parent.getValue (), this, rightNode);
|
|
|
281 }
|
|
|
282 }
|
|
|
283
|
|
|
284 protected TreeMapNode<K, V> rebuildfive (TreeMapNode<K, V> parent, Rotate side)
|
|
|
285 { // case5
|
|
|
286 if (side == Rotate.R) { // rotate Left
|
|
|
287 TreeMapNode<K, V> leftChild = new RedNode<K,V> (parent.lefts ().getKey (), parent.lefts ().getValue (), parent.lefts ().lefts (), parent.lefts ().rights ().lefts ());
|
|
|
288 TreeMapNode<K, V> rightChild = parent.lefts ().rights ().rights ();
|
|
|
289 TreeMapNode<K, V> leftSubTreeRoot = new BlackNode<K,V> (parent.lefts ().rights ().getKey (), parent.lefts ().rights ().getValue (), leftChild, rightChild);
|
|
|
290 TreeMapNode<K, V> newParent = parent.createNode (parent.getKey (), parent.getValue (), leftSubTreeRoot, this);
|
|
|
291 return this.rebuildsix (newParent, Rotate.R);
|
|
|
292 } else { // rotate Right 修正済み
|
|
|
293 TreeMapNode<K, V> leftChild = parent.rights ().lefts ().lefts ();
|
|
|
294 TreeMapNode<K, V> rightChild = new RedNode<K,V> (parent.rights ().getKey (), parent.rights ().getValue (), parent.rights ().lefts ().rights (), parent.rights ().rights ());
|
|
|
295 TreeMapNode<K, V> rightSubTreeRoot = new BlackNode<K,V> (parent.rights ().lefts ().getKey (), parent.rights ().lefts ().getValue (), leftChild, rightChild);
|
|
|
296 TreeMapNode<K, V> newParent = parent.createNode (parent.getKey (), parent.getValue (), this, rightSubTreeRoot);
|
|
|
297 return this.rebuildsix (newParent, Rotate.L);
|
|
|
298 }
|
|
|
299 }
|
|
|
300
|
|
|
301 protected TreeMapNode<K, V> rebuildsix (TreeMapNode<K, V> parent, Rotate side)
|
|
|
302 { // case6
|
|
|
303 if (side == Rotate.L) { // rotate Left
|
|
|
304 TreeMapNode<K, V> leftChild = parent.rights ().createNode (parent.getKey (), parent.getValue (), this, parent.rights ().lefts ()); // check
|
|
|
305 TreeMapNode<K, V> rightChild = new BlackNode<K,V> (parent.rights ().rights ().getKey (), parent.rights ().rights ().getValue (), parent.rights ().rights ().lefts (), parent.rights ().rights ().rights ());
|
|
|
306 return parent.createNode (parent.rights ().getKey (), parent.rights ().getValue (), leftChild, rightChild);
|
|
|
307 } else { // rotate Right
|
|
|
308 TreeMapNode<K, V> leftChild = new BlackNode<K,V> (parent.lefts ().lefts ().getKey (), parent.lefts ().lefts ().getValue (), parent.lefts ().lefts ().lefts (), parent.lefts ().lefts ().rights ());
|
|
|
309 TreeMapNode<K, V> rightChild = parent.lefts ().createNode (parent.getKey (), parent.getValue (), parent.lefts ().rights (), this);
|
|
|
310 return parent.createNode (parent.lefts ().getKey (), parent.lefts ().getValue (), leftChild, rightChild);
|
|
|
311 }
|
|
|
312 }
|
|
|
313
|
|
|
314
|
|
|
315
|
|
|
316
|
|
|
317
|
|
|
318
|
|
|
319
|
|
|
320
|
|
|
321 public abstract bool isNotEmpty ();
|
|
|
322
|
|
|
323 public abstract TreeMapNode<K,V> createNode (K key, V value, TreeMapNode<K,V> left, TreeMapNode<K,V> right);
|
|
|
324
|
|
|
325 public abstract TreeMapNode<K,V> insBalance ();
|
|
|
326
|
|
|
327
|
|
|
328 public abstract Rotate checkRotate (Rotate side);
|
|
|
329
|
|
|
330 public abstract bool isRed ();
|
|
|
331
|
|
|
332 public abstract rebuildNode<K,V> replaceNode (TreeMapNode<K,V> parent, Comparer ctr);
|
|
|
333
|
|
|
334 public abstract rebuildNode<K,V> deleteNode ();
|
|
|
335
|
|
|
336 // test method
|
|
|
337 public abstract int checkDepth (int count, int minCount);
|
|
|
338 }
|
