Mercurial > hg > Database > jungle-sharp

comparison src/main/csharp/jp.ac.u-ryukyu.ie.cr/jungle-main/data/treemap/RedNode.cs @ 10:abe0c247f5a5

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add Network module. but, unComplete NetworkDefaultJungleTreeEditor.cs
author Kazuma Takeda <kazuma-arashi@hotmail.co.jp>
date Sun, 23 Oct 2016 07:40:50 +0900
parents
children
comparison
equal deleted inserted replaced
9:e6ad9016601c 10:abe0c247f5a5
1 using UnityEngine;
2 using System.Collections;
3 using System;
4 using System.Collections.Generic;
5
6 public class RedNode<K,V> : TreeMapNode<K,V>{
7
8 // Use this for initialization
9 public RedNode (K key, V value, TreeMapNode<K,V> left, TreeMapNode<K,V> right)
10 : base (key, value, left, right)
11 {
12 }
13
14 // Update is called once per frame
15 public override bool isNotEmpty ()
16 {
17 return true;
18 }
19
20 public override rebuildNode<K,V> deleteNode() {
21 TreeMapNode<K,V> emptyNode = new EmptyNode<K,V>(this.getKey());
22 return new rebuildNode<K,V>(false, emptyNode);
23 }
24
25 public override Rotate checkRotate(Rotate side) {
26 if (side == Rotate.L) {
27 if (left.isRed())
28 return Rotate.R;
29 else if (right.isRed())
30 return Rotate.LR;
31 return Rotate.N;
32 } else {
33 if (left.isRed())
34 return Rotate.RL;
35 else if (right.isRed())
36 return Rotate.L;
37 return Rotate.N;
38 }
39 }
40
41 public override rebuildNode<K,V> replaceNode(TreeMapNode<K, V> parent, Comparer<K> ctr) {
42 TreeMapNode<K, V> newNode;
43 if (!this.lefts().isNotEmpty() && !this.rights().isNotEmpty()) { //自身を削除する
44 return deleteNode();
45 } else if (this.lefts().isNotEmpty() && !this.rights().isNotEmpty()) { //左の部分木を昇格させる
46 newNode = lefts().createNode(lefts().getKey(), lefts().getValue(), lefts().lefts(), lefts().rights());
47 return new rebuildNode<K,V>(false, newNode);
48 } else if (!this.lefts().isNotEmpty() && this.rights().isNotEmpty()) { //右の部分木を昇格させる
49 newNode = rights().createNode(rights().getKey(), rights().getValue(), rights().lefts(), rights().rights());
50 return new rebuildNode<K,V>(false, newNode);
51 } else {//子ノードが左右にある場合
52 //左の部分木の最大の値を持つNodeと自身を置き換える
53 TreeMapNode<K, V> cur = this.lefts();
54
55 while (cur.rights().isNotEmpty()) {
56 cur = cur.rights();
57 }
58 if (this.lefts().rights().isNotEmpty()) {
59 rebuildNode<K, V> leftSubTreeNodeRebuildNode = this.lefts().deleteSubTreeMaxNode(null, ctr, Rotate.L);
60 if (leftSubTreeNodeRebuildNode.rebuilds()) {
61 TreeMapNode<K, V> node = leftSubTreeNodeRebuildNode.getNode();
62 TreeMapNode<K, V> newParent = createNode(cur.getKey(), cur.getValue(), node, this.rights());
63 return node.deleteBalance(newParent, ctr);
64 }
65 TreeMapNode<K, V> leftSubTreeNode = leftSubTreeNodeRebuildNode.getNode();
66 newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.rights());
67 return new rebuildNode<K,V>(false, newNode);
68 } else {
69 rebuildNode<K, V> leftSubTreeNodeRebuildNode = this.lefts().replaceNode(this, ctr);
70 if (leftSubTreeNodeRebuildNode.rebuilds()) {
71 TreeMapNode<K, V> node = leftSubTreeNodeRebuildNode.getNode();
72 TreeMapNode<K, V> newParent = createNode(this.lefts().getKey(), this.lefts().getValue(), node, this.rights());
73 return node.deleteBalance(newParent, ctr);
74 }
75 TreeMapNode<K, V> leftSubTreeNode = leftSubTreeNodeRebuildNode.getNode();
76 newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.rights());
77 return new rebuildNode<K,V>(false, newNode);
78 }
79
80 }
81 }
82
83 public override bool isRed() {
84 return true;
85 }
86
87 public override TreeMapNode<K, V> createNode(K key, V value, TreeMapNode<K, V> left, TreeMapNode<K, V> right) {
88 return new RedNode<K,V>(key, value, left, right);
89 }
90
91 public override TreeMapNode<K, V> insBalance() {
92 return this;
93 }
94
95 public override int checkDepth(int count, int minCount) { // test method
96 count++;
97 minCount = lefts().checkDepth(count, minCount);
98 minCount = rights().checkDepth(count, minCount);
99 return minCount;
100 }
101 }