Mercurial > hg > Database > jungle-sharp

changeset 1:5c58219da97e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fix code TreeMap
author Kazuma
date Fri, 01 Jul 2016 11:41:41 +0900
parents dec15de2c6ff
children a3af05a061b4
files src/main/csharp/jp.ac.u-ryukyu.ie.cr/jungle/data/treemap/BlackNode.cs src/main/csharp/jp.ac.u-ryukyu.ie.cr/jungle/data/treemap/EmptyNode.cs src/main/csharp/jp.ac.u-ryukyu.ie.cr/jungle/data/treemap/RedNode.cs src/main/csharp/jp.ac.u-ryukyu.ie.cr/jungle/data/treemap/Rotate.cs src/main/csharp/jp.ac.u-ryukyu.ie.cr/jungle/data/treemap/TreeMap.cs src/main/csharp/jp.ac.u-ryukyu.ie.cr/jungle/data/treemap/TreeMapNode.cs src/test/csharp/jp.ac.u-ryukyu.ie.cr/data/treemap/TreeMapDelete.cs
diffstat 7 files changed, 179 insertions(+), 201 deletions(-) [+]
line wrap: on
line diff
--- a/src/main/csharp/jp.ac.u-ryukyu.ie.cr/jungle/data/treemap/BlackNode.cs	Tue Jun 21 17:11:12 2016 +0900
+++ b/src/main/csharp/jp.ac.u-ryukyu.ie.cr/jungle/data/treemap/BlackNode.cs	Fri Jul 01 11:41:41 2016 +0900
@@ -1,4 +1,5 @@
 using UnityEngine;
+using System.Collections.Generic;
 using System.Collections;
 using System;
 
@@ -77,7 +78,7 @@
 		return false;
 	}
 
-	public override rebuildNode<K,V> replaceNode (TreeMapNode<K, V> parent, Comparer ctr)
+	public override rebuildNode<K,V> replaceNode (TreeMapNode<K, V> parent, Comparer<K> ctr)
 	{
 		TreeMapNode<K, V> newNode;
 		if (!this.lefts ().isNotEmpty () && !this.rights ().isNotEmpty ()) { //自身を削除する
@@ -122,4 +123,4 @@
 			}
 		}
 	}
-}
+}
\ No newline at end of file
--- a/src/main/csharp/jp.ac.u-ryukyu.ie.cr/jungle/data/treemap/EmptyNode.cs	Tue Jun 21 17:11:12 2016 +0900
+++ b/src/main/csharp/jp.ac.u-ryukyu.ie.cr/jungle/data/treemap/EmptyNode.cs	Fri Jul 01 11:41:41 2016 +0900
@@ -1,9 +1,10 @@
 using UnityEngine;
 using System.Collections;
+using System.Collections.Generic;
 using System;
 
 public class EmptyNode<K,V> : TreeMapNode<K,V>{
-	static V values;
+	//static V values;
 	// Use this for initialization
 	public EmptyNode ()
 		: base (default(K),default(V))
@@ -11,15 +12,15 @@
 	}
 
 	public EmptyNode (K key)
-		: base (key,values)
+		: base (key,default(V))
 	{
 	}
 
-	public TreeMapNode<K,V> left(){
+	public override TreeMapNode<K,V> lefts(){
 		return new EmptyNode<K,V>();
 	}
 
-	public TreeMapNode<K,V> right(){
+	public override TreeMapNode<K,V> rights(){
 		return new EmptyNode<K,V>();
 	}
 
@@ -36,7 +37,7 @@
 	}
 
 	//I don't know only Comparator method.
-	public override rebuildNode<K, V> replaceNode(TreeMapNode<K, V> parent, Comparer ctr) { // not use method
+	public override rebuildNode<K, V> replaceNode(TreeMapNode<K, V> parent, Comparer<K> ctr) { // not use method
 		return new rebuildNode<K,V>(false, this);
 	}
 
@@ -57,11 +58,11 @@
 	}
 
 	public override int checkDepth(int count, int minCount) { // test method
-		if (count < minCount | minCount == 0)
+		if (count < minCount || minCount == 0) {
 			minCount = count;
-		Debug.Log("depth = " + count);
-		//c# is there assert??
-		//Assert.assertTrue(count <= 2 * minCount);
+		}
+			//c# is there assert??
+			//Assert.assertTrue(count <= 2 * minCount);
 		return minCount;
 	}
 
--- a/src/main/csharp/jp.ac.u-ryukyu.ie.cr/jungle/data/treemap/RedNode.cs	Tue Jun 21 17:11:12 2016 +0900
+++ b/src/main/csharp/jp.ac.u-ryukyu.ie.cr/jungle/data/treemap/RedNode.cs	Fri Jul 01 11:41:41 2016 +0900
@@ -1,100 +1,101 @@
-using UnityEngine;
-using System.Collections;
-using System;
-
-public class RedNode<K,V> : TreeMapNode<K,V>{
-
-	// Use this for initialization
-	public RedNode (K key, V value, TreeMapNode<K,V> left, TreeMapNode<K,V> right)
-		: base (key, value, left, right)
-	{
-	}
-	
-	// Update is called once per frame
-	public override bool isNotEmpty ()
-	{
-		return true;
-	}
-
-	public override rebuildNode<K,V> deleteNode() {
-		TreeMapNode<K,V> emptyNode = new EmptyNode<K,V>(this.getKey());
-		return new rebuildNode<K,V>(false, emptyNode);
-	}
-
-	public override Rotate checkRotate(Rotate side) {
-		if (side == Rotate.L) {
-			if (left.isRed())
-				return Rotate.R;
-			else if (right.isRed())
-				return Rotate.LR;
-			return Rotate.N;
-		} else {
-			if (left.isRed())
-				return Rotate.RL;
-			else if (right.isRed())
-				return Rotate.L;
-			return Rotate.N;
-		}
-	}
-
-	public override rebuildNode<K,V> replaceNode(TreeMapNode<K, V> parent, Comparer ctr) {
-		TreeMapNode<K, V> newNode;
-		if (!this.lefts().isNotEmpty() && !this.rights().isNotEmpty()) { //自身を削除する
-			return deleteNode();
-		} else if (this.lefts().isNotEmpty() && !this.rights().isNotEmpty()) { //左の部分木を昇格させる
-			newNode = lefts().createNode(lefts().getKey(), lefts().getValue(), lefts().lefts(), lefts().rights());
-			return new rebuildNode<K,V>(false, newNode);
-		} else if (!this.lefts().isNotEmpty() && this.rights().isNotEmpty()) { //右の部分木を昇格させる
-			newNode = rights().createNode(rights().getKey(), rights().getValue(), rights().lefts(), rights().rights());
-			return new rebuildNode<K,V>(false, newNode);
-		} else {//子ノードが左右にある場合
-			//左の部分木の最大の値を持つNodeと自身を置き換える
-			TreeMapNode<K, V> cur = this.lefts();
-			
-			while (cur.rights().isNotEmpty()) {
-				cur = cur.rights();
-			}
-			if (this.lefts().rights().isNotEmpty()) {
-				rebuildNode<K, V> leftSubTreeNodeRebuildNode = this.lefts().deleteSubTreeMaxNode(null, ctr, Rotate.L);
-				if (leftSubTreeNodeRebuildNode.rebuilds()) {
-					TreeMapNode<K, V> node = leftSubTreeNodeRebuildNode.getNode();
-					TreeMapNode<K, V> newParent = createNode(cur.getKey(), cur.getValue(), node, this.rights());
-					return node.deleteBalance(newParent, ctr);
-				}
-				TreeMapNode<K, V> leftSubTreeNode = leftSubTreeNodeRebuildNode.getNode();
-				newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.rights());
-				return new rebuildNode<K,V>(false, newNode);
-			} else {
-				rebuildNode<K, V> leftSubTreeNodeRebuildNode = this.lefts().replaceNode(this, ctr);
-				if (leftSubTreeNodeRebuildNode.rebuilds()) {
-					TreeMapNode<K, V> node = leftSubTreeNodeRebuildNode.getNode();
-					TreeMapNode<K, V> newParent = createNode(this.lefts().getKey(), this.lefts().getValue(), node, this.rights());
-					return node.deleteBalance(newParent, ctr);
-				}
-				TreeMapNode<K, V> leftSubTreeNode = leftSubTreeNodeRebuildNode.getNode();
-				newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.rights());
-				return new rebuildNode<K,V>(false, newNode);
-			}
-			
-		}
-	}
-
-	public override bool isRed() {
-		return true;
-	}
-
-	public override TreeMapNode<K, V> createNode(K key, V value, TreeMapNode<K, V> left, TreeMapNode<K, V> right) {
-		return new RedNode<K,V>(key, value, left, right);
-	}
-
-	public override TreeMapNode<K, V> insBalance() {
-		return this;
-	}
-
-	public override int checkDepth(int count, int minCount) { // test method
-		count++;
-		minCount = lefts().checkDepth(count, minCount);
-		minCount = rights().checkDepth(count, minCount);
-		return minCount;
-	}
-}
+using UnityEngine;
+using System.Collections;
+using System;
+using System.Collections.Generic;
+
+public class RedNode<K,V> : TreeMapNode<K,V>{
+
+	// Use this for initialization
+	public RedNode (K key, V value, TreeMapNode<K,V> left, TreeMapNode<K,V> right)
+		: base (key, value, left, right)
+	{
+	}
+	
+	// Update is called once per frame
+	public override bool isNotEmpty ()
+	{
+		return true;
+	}
+
+	public override rebuildNode<K,V> deleteNode() {
+		TreeMapNode<K,V> emptyNode = new EmptyNode<K,V>(this.getKey());
+		return new rebuildNode<K,V>(false, emptyNode);
+	}
+
+	public override Rotate checkRotate(Rotate side) {
+		if (side == Rotate.L) {
+			if (left.isRed())
+				return Rotate.R;
+			else if (right.isRed())
+				return Rotate.LR;
+			return Rotate.N;
+		} else {
+			if (left.isRed())
+				return Rotate.RL;
+			else if (right.isRed())
+				return Rotate.L;
+			return Rotate.N;
+		}
+	}
+
+	public override rebuildNode<K,V> replaceNode(TreeMapNode<K, V> parent, Comparer<K> ctr) {
+		TreeMapNode<K, V> newNode;
+		if (!this.lefts().isNotEmpty() && !this.rights().isNotEmpty()) { //自身を削除する
+			return deleteNode();
+		} else if (this.lefts().isNotEmpty() && !this.rights().isNotEmpty()) { //左の部分木を昇格させる
+			newNode = lefts().createNode(lefts().getKey(), lefts().getValue(), lefts().lefts(), lefts().rights());
+			return new rebuildNode<K,V>(false, newNode);
+		} else if (!this.lefts().isNotEmpty() && this.rights().isNotEmpty()) { //右の部分木を昇格させる
+			newNode = rights().createNode(rights().getKey(), rights().getValue(), rights().lefts(), rights().rights());
+			return new rebuildNode<K,V>(false, newNode);
+		} else {//子ノードが左右にある場合
+			//左の部分木の最大の値を持つNodeと自身を置き換える
+			TreeMapNode<K, V> cur = this.lefts();
+			
+			while (cur.rights().isNotEmpty()) {
+				cur = cur.rights();
+			}
+			if (this.lefts().rights().isNotEmpty()) {
+				rebuildNode<K, V> leftSubTreeNodeRebuildNode = this.lefts().deleteSubTreeMaxNode(null, ctr, Rotate.L);
+				if (leftSubTreeNodeRebuildNode.rebuilds()) {
+					TreeMapNode<K, V> node = leftSubTreeNodeRebuildNode.getNode();
+					TreeMapNode<K, V> newParent = createNode(cur.getKey(), cur.getValue(), node, this.rights());
+					return node.deleteBalance(newParent, ctr);
+				}
+				TreeMapNode<K, V> leftSubTreeNode = leftSubTreeNodeRebuildNode.getNode();
+				newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.rights());
+				return new rebuildNode<K,V>(false, newNode);
+			} else {
+				rebuildNode<K, V> leftSubTreeNodeRebuildNode = this.lefts().replaceNode(this, ctr);
+				if (leftSubTreeNodeRebuildNode.rebuilds()) {
+					TreeMapNode<K, V> node = leftSubTreeNodeRebuildNode.getNode();
+					TreeMapNode<K, V> newParent = createNode(this.lefts().getKey(), this.lefts().getValue(), node, this.rights());
+					return node.deleteBalance(newParent, ctr);
+				}
+				TreeMapNode<K, V> leftSubTreeNode = leftSubTreeNodeRebuildNode.getNode();
+				newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.rights());
+				return new rebuildNode<K,V>(false, newNode);
+			}
+			
+		}
+	}
+
+	public override bool isRed() {
+		return true;
+	}
+
+	public override TreeMapNode<K, V> createNode(K key, V value, TreeMapNode<K, V> left, TreeMapNode<K, V> right) {
+		return new RedNode<K,V>(key, value, left, right);
+	}
+
+	public override TreeMapNode<K, V> insBalance() {
+		return this;
+	}
+
+	public override int checkDepth(int count, int minCount) { // test method
+		count++;
+		minCount = lefts().checkDepth(count, minCount);
+		minCount = rights().checkDepth(count, minCount);
+		return minCount;
+	}
+}
--- a/src/main/csharp/jp.ac.u-ryukyu.ie.cr/jungle/data/treemap/Rotate.cs	Tue Jun 21 17:11:12 2016 +0900
+++ b/src/main/csharp/jp.ac.u-ryukyu.ie.cr/jungle/data/treemap/Rotate.cs	Fri Jul 01 11:41:41 2016 +0900
@@ -1,7 +1,7 @@
-using UnityEngine;
-using System.Collections;
-
-public enum Rotate{
-	R,L,RL,LR,N
-}
-
+using UnityEngine;
+using System.Collections;
+
+public enum Rotate{
+	R,L,RL,LR,N
+}
+
--- a/src/main/csharp/jp.ac.u-ryukyu.ie.cr/jungle/data/treemap/TreeMap.cs	Tue Jun 21 17:11:12 2016 +0900
+++ b/src/main/csharp/jp.ac.u-ryukyu.ie.cr/jungle/data/treemap/TreeMap.cs	Fri Jul 01 11:41:41 2016 +0900
@@ -5,7 +5,7 @@
 
 public class TreeMap<K, V> {
 	TreeMapNode<K, V> root;
-	Comparer comparator;
+	Comparer<K> comparator;
 
 
 	public TreeMap(IComparer icompere) {
@@ -14,7 +14,7 @@
 
 	public TreeMap() {
 		this.root = new EmptyNode<K, V> ();
-		this.comparator =  Comparer.Default;
+		this.comparator =  Comparer<K>.Default;
 	}
 
 	public TreeMap(TreeMapNode<K, V> root) {
@@ -22,7 +22,7 @@
 		//this.comparator = comparator;
 	}
 
-	public TreeMap(TreeMapNode<K, V> root, Comparer comparator) {
+	public TreeMap(TreeMapNode<K, V> root, Comparer<K> comparator) {
 		this.root = root;
 		this.comparator = comparator;
 	}
@@ -50,28 +50,11 @@
 		return !root.isNotEmpty ();
 	}
 
-	public TreeMap<K, V> delete(K key, Comparer ctr) {
-		if (key == null) {
-			return this;
-		}
-		rebuildNode<K, V> rootRebuildNode = this.root.delete (key, null, ctr, Rotate.N);
-		if (!rootRebuildNode.notEmpty ()) {
-			// key does not found, do nothing 
-			return this;
-		}
-		TreeMapNode<K, V> root = rootRebuildNode.getNode ();
-		if (!root.isNotEmpty ()) {
-			return new TreeMap<K, V> (new EmptyNode<K, V> (), this.comparator);
-		}
-		TreeMapNode<K, V> newRoot = new BlackNode<K, V> (root.getKey (), root.getValue (), root.lefts (), root.rights ());
-		return new TreeMap<K, V>(newRoot, this.comparator);
-	}
-
 	public TreeMap<K, V> delete(K key) {
 		if (key == null) {
 			return this;
 		}
-		rebuildNode<K, V> rootRebuildNode = root.delete (key, null, comparator, Rotate.N);
+		rebuildNode<K, V> rootRebuildNode = root.delete (key, null, this.comparator, Rotate.N);
 		if (!rootRebuildNode.notEmpty ()) {
 			return this;
 		}
--- a/src/main/csharp/jp.ac.u-ryukyu.ie.cr/jungle/data/treemap/TreeMapNode.cs	Tue Jun 21 17:11:12 2016 +0900
+++ b/src/main/csharp/jp.ac.u-ryukyu.ie.cr/jungle/data/treemap/TreeMapNode.cs	Fri Jul 01 11:41:41 2016 +0900
@@ -1,21 +1,17 @@
 using System.Collections;
 using System;
 using UnityEngine;
+using System.Collections.Generic;
 
 
 public abstract class  TreeMapNode<K,V>
 {
-// K,Vがnullableではないので受け付けない
-	// ジェネリックの扱いがJavaとちがうー＞特にnullの扱いが面倒。
-	protected  K key;
-	protected  V value;
-	protected TreeMapNode<K,V> right;
-	protected TreeMapNode<K,V> left;
 
-	void Start(){
-		key = default(K);
-		value = default(V);
-	}
+	public  K key = default(K);
+	public  V value = default(V);
+	public TreeMapNode<K,V> right;
+	public TreeMapNode<K,V> left;
+
 
 	//  Use this for initialization
 	public TreeMapNode (K key, V value)
@@ -32,24 +28,24 @@
 		this.left = left;
 	}
 
-	public TreeMapNode<K,V> lefts ()
+	public virtual TreeMapNode<K,V> lefts ()
 	{
 		return left;
 	}
 		
 
-	public int compare(K compareKey, Comparer ctr)  {
-		return ctr.Compare(compareKey, this.getKey());
+	public int compare(K compareKey, Comparer<K> ctr)  {
+		int val = (int) ctr.Compare (compareKey, this.getKey ());
+		return val;
 	}
     
-	public V get (K key, Comparer ctr)
+	public V get (K key, Comparer<K> ctr)
  	{
  		TreeMapNode<K,V> cur = this;
 		int result = cur.compare (key, ctr);
 		while (cur.isNotEmpty ()) {
 			if (result > 0) {
 				cur = cur.rights ();
-				Debug.Log (cur);
 			} else if (result < 0) {
 				cur = cur.lefts ();
 			} else if (result == 0) {
@@ -63,7 +59,7 @@
 
 
 
-	public TreeMapNode<K,V> rights () {
+	public virtual TreeMapNode<K,V> rights () {
 		return right;
 	}
 
@@ -76,34 +72,34 @@
 	}
 
 	// may be to use Comparer??
-	public TreeMapNode<K,V> put (K k, V v,Comparer ctr) {
+	public TreeMapNode<K,V> put (K k, V v,Comparer<K> ctr) {
 
 		if (!isNotEmpty ()) {
-			return createNode (k, value, left, right);
+			return createNode (k, v, left, right);
 		}
 
-		int result = compare (k,ctr);
+		int result = compare (k, ctr);
 		if (result > 0) {
-			TreeMapNode<K,V> node = right.put (k, value,ctr);
+			TreeMapNode<K,V> node = right.put (k, v, ctr);
 			node = createNode (key, this.value, left, node);
 			return node.insBalance ();
 		} else if (result < 0) {
-			TreeMapNode<K,V> node = left.put (k, value,ctr);
+			TreeMapNode<K,V> node = left.put (k, v,ctr);
 			return createNode (key, this.value, node, right).insBalance ();
 		}
-		return createNode (key, value, left, right);
+		return createNode (key, v, left, right);
 	}
 		
-	public rebuildNode<K,V> delete (K key, TreeMapNode<K,V> parent, Comparer ctr, Rotate side)
+	public rebuildNode<K,V> delete (K key, TreeMapNode<K,V> parent, Comparer<K> ctr, Rotate side)
 	{
 		if (this.isNotEmpty ()) {
-			rebuildNode<K,V> rebuildNode;
+			rebuildNode<K,V> rebuildNode = null;
 			int result = compare(key, ctr);
 			if (result > 0) {
 				rebuildNode = right.delete (key, this, ctr, Rotate.R);
 			} else if (result < 0) {
 				rebuildNode = left.delete (key, this, ctr, Rotate.L);
-			} else {
+			} else if (result == 0){
 				rebuildNode = replaceNode (parent, ctr);
 			}
 			if (parent == null) {
@@ -125,7 +121,7 @@
 		return null;
 	}
 
-	public rebuildNode<K,V> deleteSubTreeMaxNode (TreeMapNode<K, V> parent, Comparer ctr, Rotate side)
+	public rebuildNode<K,V> deleteSubTreeMaxNode (TreeMapNode<K, V> parent, Comparer<K> ctr, Rotate side)
 	{
 		rebuildNode<K,V> rebuildNode;
 		TreeMapNode<K, V> node;
@@ -149,7 +145,7 @@
 	}
 
 
-	public rebuildNode<K, V> deleteBalance (TreeMapNode<K, V> parent, Comparer ctr)
+	public rebuildNode<K, V> deleteBalance (TreeMapNode<K, V> parent, Comparer<K> ctr)
 	{
 		TreeMapNode<K, V> newNode = null;
 		if (!isRed ()) {
@@ -232,7 +228,7 @@
 		}
 	}
 
-	protected TreeMapNode<K, V> rebuildTwo (TreeMapNode<K, V> parent, Comparer ctr, Rotate side)
+	protected TreeMapNode<K, V> rebuildTwo (TreeMapNode<K, V> parent, Comparer<K> ctr, Rotate side)
 	{ //  case2
 		if (side == Rotate.L) { //  rotate Left
 			TreeMapNode<K, V> node = parent.rights ();
@@ -329,7 +325,7 @@
 
 	public abstract bool isRed ();
 
-	public abstract rebuildNode<K,V> replaceNode (TreeMapNode<K,V> parent, Comparer ctr);
+	public abstract rebuildNode<K,V> replaceNode (TreeMapNode<K,V> parent, Comparer<K> ctr);
 
 	public abstract rebuildNode<K,V> deleteNode ();
 
--- a/src/test/csharp/jp.ac.u-ryukyu.ie.cr/data/treemap/TreeMapDelete.cs	Tue Jun 21 17:11:12 2016 +0900
+++ b/src/test/csharp/jp.ac.u-ryukyu.ie.cr/data/treemap/TreeMapDelete.cs	Fri Jul 01 11:41:41 2016 +0900
@@ -1,33 +1,29 @@
-using UnityEngine;
-using System.Collections;
-
-public class TreeMapDelete : MonoBehaviour {
-
-	// Use this for initialization
-	void Start () {
-		TreeMap<int,int> map = new TreeMap<int, int> ();
-		for (int count = 1; count < 5; count++) {
-			map = map.put (count, count);
-			map.checkDepth ();
-		}
-
-		ArrayList list = new ArrayList ();
-		for (int i = 1; i < 5; i++) {
-			list.Add (i);
-		}
-
-		for (int i = 1; i < 5; i++) {
-			int ran = Random.Range (1, 6);
-			object obj = list [i];
-            list [i] = list [ran];
-			list [ran] = obj;
-		}
-
-		foreach(int num in list){
-			Debug.Log (num);
-			map = map.delete(num);
-			map.checkDepth();
-		}
-		Debug.Log ("end");
-	}
-}
+using UnityEngine;
+using System.Collections;
+
+public class TreeMapDelete : MonoBehaviour {
+
+	// Use this for initialization
+	void Start () {
+		TreeMap<int,int> map = new TreeMap<int, int> ();
+		for (int count = 1; count < 6; count++) {
+			Debug.Log (count);
+			map = map.put (count, count);
+			int val = map.get(count);
+			Debug.Log ("value : " + val);
+			map.checkDepth ();
+		}
+
+		// ただ消すための数字をここに入れているだけ
+		List<int> list = new List<int>(5);
+		for (int i = 1; i < 5; i++) {
+			list.Add (i);
+		}
+
+		foreach(int num in list){
+			map = map.delete(num);
+			map.checkDepth();
+		}
+		Debug.Log ("end");
+	}
+}