Mercurial > hg > Database > jungle-sharp

comparison src/main/csharp/jp.ac.u-ryukyu.ie.cr/jungle/data/treemap/TreeMapNode.cs @ 0:dec15de2c6ff

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
first commit
author Kazuma
date Tue, 21 Jun 2016 17:11:12 +0900
parents
children 5c58219da97e
comparison
equal deleted inserted replaced
-1:000000000000 0:dec15de2c6ff
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 }