Mercurial > hg > Database > jungle-sharp

comparison Main/jungle-main/data/treemap/TreeMapNode.cs @ 20:1f99e150f336

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