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