Mercurial > hg > Database > jungle-sharp
view src/main/csharp/jp.ac.u-ryukyu.ie.cr/jungle/data/treemap/TreeMapNode.cs @ 2:a3af05a061b4
fix , but not work.
author | Kazuma |
---|---|
date | Fri, 01 Jul 2016 19:28:57 +0900 |
parents | 5c58219da97e |
children | 224f0f8b4f40 |
line wrap: on
line source
using System.Collections; using System; using UnityEngine; using System.Collections.Generic; public abstract class TreeMapNode<K,V> { protected K key = default(K); protected V value = default(V); public TreeMapNode<K,V> right; public TreeMapNode<K,V> left; // Use this for initialization public TreeMapNode (K key, V value) { this.key = key; this.value = value; } public TreeMapNode (K key, V value, TreeMapNode<K,V> left, TreeMapNode<K,V> right) { this.key = key; this.value = value; this.right = right; this.left = left; } public virtual TreeMapNode<K,V> lefts () { return left; } public int compare(K compareKey, Comparer<K> ctr) { int val = (int) ctr.Compare (compareKey, this.getKey ()); return val; } public V get (K key, Comparer<K> ctr) { TreeMapNode<K,V> cur = this; while (cur.isNotEmpty ()) { // getでEmpty nodeを返している ? compareでKeyが0になっている int result = cur.compare (key, ctr); if (result > 0) { cur = cur.rights (); } else if (result < 0) { cur = cur.lefts (); } else if (result == 0) { if (cur != null) { return cur.getValue (); } } } return default(V); } public virtual TreeMapNode<K,V> rights () { return right; } public K getKey () { return key; } public V getValue () { return value; } // may be to use Comparer?? public TreeMapNode<K,V> put (K k, V v,Comparer<K> ctr) { if (!isNotEmpty ()) { return createNode (k, v, left, right); } int result = compare (k, ctr); if (result > 0) { 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, v,ctr); return createNode (key, this.value, node, right).insBalance (); } return createNode (key, v, left, right); } public rebuildNode<K,V> delete (K key, TreeMapNode<K,V> parent, Comparer<K> ctr, Rotate side) { if (this.isNotEmpty ()) { 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 if (result == 0){ rebuildNode = replaceNode (parent, ctr); } if (parent == null) { return rebuildNode; } TreeMapNode<K,V> node = rebuildNode.getNode (); if (rebuildNode.rebuilds ()) { // ここのエラーは後で return node.deleteBalance (parent, ctr); } TreeMapNode<K,V> newParent; if (side == Rotate.L) { newParent = parent.createNode (parent.getKey (), parent.getValue (), node, parent.rights ()); } else { newParent = parent.createNode (parent.getKey (), parent.getValue (), parent.lefts (), node); } return new rebuildNode<K,V> (false, newParent); } return null; } public rebuildNode<K,V> deleteSubTreeMaxNode (TreeMapNode<K, V> parent, Comparer<K> ctr, Rotate side) { rebuildNode<K,V> rebuildNode; TreeMapNode<K, V> node; if (rights ().isNotEmpty ()) {// 最大値のノードが取得できるまで潜る rebuildNode = rights ().deleteSubTreeMaxNode (this, ctr, Rotate.R); } else { rebuildNode = this.replaceNode (parent, ctr); } if (parent == null) return rebuildNode; if (rebuildNode.rebuilds ()) { node = rebuildNode.getNode (); return node.deleteBalance (parent, ctr); } if (side == Rotate.R) node = parent.createNode (parent.getKey (), parent.getValue (), parent.lefts (), rebuildNode.getNode ()); else node = parent.createNode (parent.getKey (), parent.getValue (), rebuildNode.getNode (), parent.rights ()); return new rebuildNode<K,V> (false, node); } public rebuildNode<K, V> deleteBalance (TreeMapNode<K, V> parent, Comparer<K> ctr) { TreeMapNode<K, V> newNode = null; if (!isRed ()) { if (0 > compare (parent.getKey (), ctr)) { bool rightChild = parent.lefts ().rights ().isRed (); bool leftChild = parent.lefts ().lefts ().isRed (); if (!parent.isRed ()) { if (!parent.lefts ().isRed ()) { if (!rightChild && !leftChild) { newNode = rebuildThree (parent, Rotate.R); return new rebuildNode<K,V> (true, newNode); } if (rightChild) { newNode = rebuildfive (parent, Rotate.R); return new rebuildNode<K,V> (false, newNode); } else { newNode = rebuildsix (parent, Rotate.R); return new rebuildNode<K,V> (false, newNode); } } else { // 左の子が赤 newNode = rebuildTwo (parent, ctr, Rotate.R); return new rebuildNode<K,V> (false, newNode); } } else { // 親が赤 if (!rightChild && !leftChild) { newNode = rebuildFour (parent, Rotate.R); return new rebuildNode<K,V> (false, newNode); } if (rightChild) { newNode = rebuildfive (parent, Rotate.R); return new rebuildNode<K,V> (false, newNode); } else { newNode = rebuildsix (parent, Rotate.R); return new rebuildNode<K,V> (false, newNode); } } } else { bool rightChild = parent.rights ().rights ().isRed (); bool leftChild = parent.rights ().lefts ().isRed (); if (!parent.isRed ()) { // 親が黒 if (!parent.rights ().isRed ()) { // 左の子が黒 if (!rightChild && !leftChild) { newNode = rebuildThree (parent, Rotate.L); return new rebuildNode<K,V> (true, newNode); } if (rightChild) { newNode = rebuildsix (parent, Rotate.L); return new rebuildNode<K,V> (false, newNode); } else { newNode = rebuildfive (parent, Rotate.L); return new rebuildNode<K,V> (false, newNode); } } else { // 左の子が赤 newNode = rebuildTwo (parent, ctr, Rotate.L); return new rebuildNode<K,V> (false, newNode); } } else { // 親が赤 if (!rightChild && !leftChild) { newNode = rebuildFour (parent, Rotate.L); return new rebuildNode<K,V> (false, newNode); } if (rightChild) { newNode = rebuildsix (parent, Rotate.L); return new rebuildNode<K,V> (false, newNode); } else { newNode = rebuildfive (parent, Rotate.L); return new rebuildNode<K,V> (false, newNode); } } } } if (0 > (compare (parent.getKey (), ctr))) { newNode = parent.createNode (parent.getKey (), parent.getValue (), parent.lefts (), this); return new rebuildNode<K,V> (false, newNode); } else { newNode = parent.createNode (parent.getKey (), parent.getValue (), this, parent.rights ()); return new rebuildNode<K,V> (false, newNode); } } 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 (); TreeMapNode<K, V> leftSubTreeRoot = node.createNode (parent.getKey (), parent.getValue (), this, node.lefts ()); // check rebuildNode<K, V> rebuildNode = new rebuildNode<K,V> (false, leftSubTreeRoot); rebuildNode<K, V> leftNodeRebuildNode = this.deleteBalance (rebuildNode.getNode (), ctr); TreeMapNode<K, V> rightNode = node.rights (); return parent.createNode (node.getKey (), node.getValue (), leftNodeRebuildNode.getNode (), rightNode); } else { // rotate Right TreeMapNode<K, V> node = parent.lefts (); TreeMapNode<K, V> rightSubTreeRoot = node.createNode (parent.getKey (), parent.getValue (), node.rights (), this); rebuildNode<K, V> rightSubTreeRebuildNode = new rebuildNode<K,V> (false, rightSubTreeRoot); rebuildNode<K, V> rightNodeRebuildNode = this.deleteBalance (rightSubTreeRebuildNode.getNode (), ctr); TreeMapNode<K, V> leftNode = node.lefts (); return parent.createNode (node.getKey (), node.getValue (), leftNode, rightNodeRebuildNode.getNode ()); } } protected TreeMapNode<K, V> rebuildThree (TreeMapNode<K, V> parent, Rotate side) { // case3 再帰 if (side == Rotate.L) { TreeMapNode<K, V> rightNode; if (parent.rights ().isNotEmpty ()) rightNode = new RedNode<K,V> (parent.rights ().getKey (), parent.rights ().getValue (), parent.rights ().lefts (), parent.rights ().rights ()); // check else rightNode = new EmptyNode<K,V> (); return parent.createNode (parent.getKey (), parent.getValue (), this, rightNode); } else { TreeMapNode<K, V> leftNode; if (parent.lefts ().isNotEmpty ()) leftNode = new RedNode<K,V> (parent.lefts ().getKey (), parent.lefts ().getValue (), parent.lefts ().lefts (), parent.lefts ().rights ()); // check else leftNode = new EmptyNode<K,V> (); return parent.createNode (parent.getKey (), parent.getValue (), leftNode, this); } } protected TreeMapNode<K, V> rebuildFour (TreeMapNode<K, V> parent, Rotate side) { // case 4 if (side == Rotate.R) { TreeMapNode<K, V> leftNode = new RedNode<K,V> (parent.lefts ().getKey (), parent.lefts ().getValue (), parent.lefts ().lefts (), parent.lefts ().rights ()); return new BlackNode<K,V> (parent.getKey (), parent.getValue (), leftNode, this); } else { TreeMapNode<K, V> rightNode = new RedNode<K,V> (parent.rights ().getKey (), parent.rights ().getValue (), parent.rights ().lefts (), parent.rights ().rights ()); return new BlackNode<K,V> (parent.getKey (), parent.getValue (), this, rightNode); } } protected TreeMapNode<K, V> rebuildfive (TreeMapNode<K, V> parent, Rotate side) { // case5 if (side == Rotate.R) { // rotate Left TreeMapNode<K, V> leftChild = new RedNode<K,V> (parent.lefts ().getKey (), parent.lefts ().getValue (), parent.lefts ().lefts (), parent.lefts ().rights ().lefts ()); TreeMapNode<K, V> rightChild = parent.lefts ().rights ().rights (); TreeMapNode<K, V> leftSubTreeRoot = new BlackNode<K,V> (parent.lefts ().rights ().getKey (), parent.lefts ().rights ().getValue (), leftChild, rightChild); TreeMapNode<K, V> newParent = parent.createNode (parent.getKey (), parent.getValue (), leftSubTreeRoot, this); return this.rebuildsix (newParent, Rotate.R); } else { // rotate Right 修正済み TreeMapNode<K, V> leftChild = parent.rights ().lefts ().lefts (); TreeMapNode<K, V> rightChild = new RedNode<K,V> (parent.rights ().getKey (), parent.rights ().getValue (), parent.rights ().lefts ().rights (), parent.rights ().rights ()); TreeMapNode<K, V> rightSubTreeRoot = new BlackNode<K,V> (parent.rights ().lefts ().getKey (), parent.rights ().lefts ().getValue (), leftChild, rightChild); TreeMapNode<K, V> newParent = parent.createNode (parent.getKey (), parent.getValue (), this, rightSubTreeRoot); return this.rebuildsix (newParent, Rotate.L); } } protected TreeMapNode<K, V> rebuildsix (TreeMapNode<K, V> parent, Rotate side) { // case6 if (side == Rotate.L) { // rotate Left TreeMapNode<K, V> leftChild = parent.rights ().createNode (parent.getKey (), parent.getValue (), this, parent.rights ().lefts ()); // check TreeMapNode<K, V> rightChild = new BlackNode<K,V> (parent.rights ().rights ().getKey (), parent.rights ().rights ().getValue (), parent.rights ().rights ().lefts (), parent.rights ().rights ().rights ()); return parent.createNode (parent.rights ().getKey (), parent.rights ().getValue (), leftChild, rightChild); } else { // rotate Right TreeMapNode<K, V> leftChild = new BlackNode<K,V> (parent.lefts ().lefts ().getKey (), parent.lefts ().lefts ().getValue (), parent.lefts ().lefts ().lefts (), parent.lefts ().lefts ().rights ()); TreeMapNode<K, V> rightChild = parent.lefts ().createNode (parent.getKey (), parent.getValue (), parent.lefts ().rights (), this); return parent.createNode (parent.lefts ().getKey (), parent.lefts ().getValue (), leftChild, rightChild); } } public abstract bool isNotEmpty (); public abstract TreeMapNode<K,V> createNode (K key, V value, TreeMapNode<K,V> left, TreeMapNode<K,V> right); public abstract TreeMapNode<K,V> insBalance (); public abstract Rotate checkRotate (Rotate side); public abstract bool isRed (); public abstract rebuildNode<K,V> replaceNode (TreeMapNode<K,V> parent, Comparer<K> ctr); public abstract rebuildNode<K,V> deleteNode (); // test method public abstract int checkDepth (int count, int minCount); }