Mercurial > hg > Members > shoshi > jungle > jungle-core
changeset 200:07475e00049d
merge TreeMao
line wrap: on
line diff
--- a/build.gradle Wed May 06 18:40:15 2015 +0900 +++ b/build.gradle Sat May 16 16:22:36 2015 +0900 @@ -16,7 +16,7 @@ compile "org.apache.maven.surefire:surefire-junit4:2.13" compile "com.google.guava:guava:12.0" compile fileTree(dir: 'lib', include: '*.jar') - testCompile "junit:junit:4.7" + compile "junit:junit:4.7" } jar {
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/DefaultJungleTree.java Wed May 06 18:40:15 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/DefaultJungleTree.java Sat May 16 16:22:36 2015 +0900 @@ -1,7 +1,7 @@ package jp.ac.u_ryukyu.ie.cr.shoshi.jungle; import fj.data.List; -import jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap.TreeMap; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.persistent.ChangeListWriter; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.NodePath; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.TreeContext;
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/JungleTree.java Wed May 06 18:40:15 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/JungleTree.java Sat May 16 16:22:36 2015 +0900 @@ -2,7 +2,7 @@ import fj.data.List; -import jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap.TreeMap; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.NodePath; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.traverser.InterfaceTraverser;
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/store/TreeContext.java Wed May 06 18:40:15 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/store/TreeContext.java Sat May 16 16:22:36 2015 +0900 @@ -2,7 +2,7 @@ import fj.data.List; -import jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap.TreeMap; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.persistent.ChangeList; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.operations.TreeOperation;
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/store/impl/TreeNodeAttributes.java Wed May 06 18:40:15 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/store/impl/TreeNodeAttributes.java Sat May 16 16:22:36 2015 +0900 @@ -3,7 +3,7 @@ import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.core.Attributes; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.util.Either; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.util.Error; -import jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap.TreeMap; import java.nio.ByteBuffer; import java.util.Iterator;
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/DefaultTreeContext.java Wed May 06 18:40:15 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/DefaultTreeContext.java Sat May 16 16:22:36 2015 +0900 @@ -1,7 +1,7 @@ package jp.ac.u_ryukyu.ie.cr.shoshi.jungle.transaction; import fj.data.List; -import jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap.TreeMap; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.persistent.ChangeList; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.TreeContext; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode;
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/DefaultTreeNode.java Wed May 06 18:40:15 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/DefaultTreeNode.java Sat May 16 16:22:36 2015 +0900 @@ -5,7 +5,7 @@ import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNodeChildren; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.util.Either; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.util.Error; -import jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap.TreeMap; import java.nio.ByteBuffer; import java.rmi.dgc.VMID;
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/DefaultTreeNodeAttribute.java Wed May 06 18:40:15 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/DefaultTreeNodeAttribute.java Sat May 16 16:22:36 2015 +0900 @@ -7,7 +7,7 @@ import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.util.DefaultEither; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.util.Either; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.util.Error; -import jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap.TreeMap; import java.nio.ByteBuffer; import java.util.Iterator;
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/DefaultTreeNodeChildren.java Wed May 06 18:40:15 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/DefaultTreeNodeChildren.java Sat May 16 16:22:36 2015 +0900 @@ -8,7 +8,7 @@ import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.util.DefaultEither; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.util.Either; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.util.Error; -import jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap.TreeMap; import java.nio.ByteBuffer; import java.util.Iterator;
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/traverser/InterfaceTraverser.java Wed May 06 18:40:15 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/traverser/InterfaceTraverser.java Sat May 16 16:22:36 2015 +0900 @@ -4,7 +4,7 @@ import java.util.Optional; import fj.data.List; -import jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap.TreeMap; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.NulIterator; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode; import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.query.PathNodeIterator;
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/TreeMap/BlackNode.java Sat May 16 16:22:36 2015 +0900 @@ -0,0 +1,137 @@ +package jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap; + +import org.junit.Test; + +import static jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap.Rotate.*; + + +public class BlackNode<K, V> extends Node<K, V> { + + + public BlackNode(K key, V value, Node<K, V> left, Node<K, V> right) { + super(key, value, left, right); + } + + + @Override + public Node deleteNode() throws RotateParent { + EmptyNode<K, V> emptyNode = new EmptyNode<K, V>(key); + throw new RotateParent(emptyNode); + } + + @Override + @Test + protected int checkDepth(int count, int minCount) { // test method + count++; + minCount = left().checkDepth(count, minCount); + minCount = right().checkDepth(count, minCount); + count--; + return minCount; + } + + + @Override + protected boolean isNotEmpty() { + return true; + } + + @Override + public Node<K, V> createNode(K key, V value, Node<K, V> left, Node<K, V> right) { + return new BlackNode<K, V>(key, value, left, right); + } + + + @Override + Node insBalance() { + Rotate spin = left.checkRotate(L); + + if (spin == R) { + Node<K, V> leftChild = new BlackNode<K, V>(left.left().getKey(), left.left().getValue(), left.left().left(), left.left().right()); + Node<K, V> rightChild = new BlackNode<K, V>(getKey(), getValue(), left.right(), right); + return new RedNode<K, V>(left.getKey(), left.getValue(), leftChild, rightChild); + + } else if (spin == LR) { + Node<K, V> leftChild = new BlackNode<K, V>(left.getKey(), left.getValue(), left.left(), left.right().left()); + Node<K, V> rightChild = new BlackNode<K, V>(getKey(), getValue(), left.right().right(), right); + return new RedNode<K, V>(left.right().getKey(), left.right().getValue(), leftChild, rightChild); + + } + + spin = right.checkRotate(R); + if (spin == L) { + Node<K, V> leftChild = new BlackNode<K, V>(getKey(), getValue(), left, right.left()); + Node<K, V> rightChild = new BlackNode<K, V>(right.right().getKey(), (V) right.right().getValue(), right.right().left(), right.right().right()); + return new RedNode<K, V>(right.getKey(), right.getValue(), leftChild, rightChild); + + } else if (spin == RL) { + Node leftChild = new BlackNode(getKey(), getValue(), left, right.left().left()); + Node rightChild = new BlackNode(right.getKey(), right.getValue(), right.left().right(), right.right()); + return new RedNode(right.left().getKey(), right.left().getValue(), leftChild, rightChild); + + } + + return this; + } + + + @Override + Rotate checkRotate(Rotate side) { + return N; + } + + @Override + boolean isRed() { + return false; + } + + + /** + * @param parent + * @return + */ + @Override + public Node replaceNode(Node<K, V> parent) throws RotateParent { + Node<K, V> newNode = null; + if (!this.left().isNotEmpty() && !this.right().isNotEmpty()) { //自身を削除する + return deleteNode();//黒が1つ減るので木のバランスを取る + } else if (this.left().isNotEmpty() && !this.right().isNotEmpty()) { //左の部分木を昇格させる + newNode = createNode(left().getKey(), left().getValue(), left().left(), left().right()); + if (!this.left().isRed()) //昇格させる木のrootが黒だったらバランスを取る + throw new RotateParent(newNode); + return newNode; + } else if (!this.left().isNotEmpty() && this.right().isNotEmpty()) { //右の部分木を昇格させる + newNode = createNode(right().getKey(), right().getValue(), right().left(), right().right()); + if (!this.right().isRed()) //昇格させる木のrootが黒だったらバランスを取る + throw new RotateParent(newNode); + return newNode; + } else {//子ノードが左右にある場合 二回目はここには入らない + //左の部分木の最大の値を持つNodeと自身を置き換える + Node<K, V> cur = this.left(); + while (cur.right().isNotEmpty()) { //左の部分期の最大値を持つNodeを取得する + cur = cur.right(); + } + if (this.left().right().isNotEmpty()) { //左の部分木が右の子を持っているか + try { + Node leftSubTreeNode = this.left().deleteSubTreeMaxNode(null, Rotate.L);//最大値を削除した左の部分木を返す。rootはthisと同じ。 + Node<K, V> newParent = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.right()); //rootをcurと入れ替えることでNodeの削除は完了する + return newParent; + } catch (RotateParent e) { + Node leftSubTreeNode = e.getParent(); + Node<K, V> newParent = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.right()); + return leftSubTreeNode.deleteBalance(newParent); + } + } else { + Node leftSubTreeNode = null; + try { + leftSubTreeNode = this.left().replaceNode(this);//右の子がいなかった場合、左の子を昇格させるだけで良い。 + Node newParent = createNode(this.left().getKey(), this.left().getValue(), leftSubTreeNode, this.right()); + return newParent; + } catch (RotateParent e) { + Node node = e.getParent(); + Node newParent = createNode(this.left().getKey(), this.left().getValue(), leftSubTreeNode, this.right()); + return node.deleteBalance(newParent); + } + } + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/TreeMap/EmptyNode.java Sat May 16 16:22:36 2015 +0900 @@ -0,0 +1,84 @@ +package jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap; + +import org.junit.Assert; +import org.junit.Test; + +import static jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap.Rotate.N; + +/** + * Created by e115731 on 15/03/25. + */ +public class EmptyNode<K, V> extends Node<K, V> { + + public EmptyNode() { + super(null, null); + } + + public EmptyNode(K key) { //keyは削除時の回転処理に使用する + super(key, null); + } + + @Override // 回転処理時にEmptyNodeの子を見ることがあるのでleft rightでEmptyNodeを返すようにする + public Node<K, V> left() { + return new EmptyNode<>(); + } + + @Override + public Node<K, V> right() { + return new EmptyNode<>(); + } + + + @Override + protected boolean isNotEmpty() { + return false; + } + + + @Override + public Node<K, V> createNode(K key, V value, Node<K, V> left, Node<K, V> right) { + return new RedNode<K, V>(key, value, new EmptyNode<K, V>(), new EmptyNode<K, V>()); + } + + + public Node<K, V> put(K k, V value) { + return new RedNode(k, value, new EmptyNode<K, V>(), new EmptyNode<K, V>()); + } + + @Override + public Node replaceNode(Node<K, V> parent) { // not use method + return this; + } + + @Override + protected Node deleteNode() { //not use method + return this; + } + + @Override + Node insBalance() { + return this; + } + + @Override + Rotate checkRotate(Rotate side) { + return N; + } + + @Override + boolean isRed() { + return false; + } + + @Override + @Test + protected int checkDepth(int count,int minCount) { // test method + if (count < minCount | minCount == 0) + minCount = count; + System.out.println("depth = " + count); + + Assert.assertTrue(count <= 2 * minCount); + return minCount; + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/TreeMap/Node.java Sat May 16 16:22:36 2015 +0900 @@ -0,0 +1,295 @@ +package jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap; + +import org.junit.Test; + +import java.util.Optional; + + +/** + * Created by e115731 on 15/03/23. + */ +public abstract class Node<K, V> { + + protected K key; + protected V value; + protected Node<K, V> right; + protected Node<K, V> left; + + public Node(K key, V value) { + this.key = key; + this.value = value; + } + + public Node(K key, V value, Node<K, V> left, Node<K, V> right) { + this.key = key; + this.value = value; + this.right = right; + this.left = left; + } + + public Node<K, V> left() { + return left; + } + + public int compare(Comparable<? super K> compareKey) { + return compareKey.compareTo(getKey()); + + } + + public Optional<V> get(K key) { + Node<K, V> cur = this; + Comparable<? super K> k = (Comparable<? super K>) key; + while (cur.isNotEmpty()) { + int result = cur.compare(k); + if (result > 0) + cur = cur.right(); + else if (result < 0) + cur = cur.left(); + else if (result == 0) + return Optional.ofNullable(cur.getValue()); + } + return Optional.ofNullable(null); + } + + + public Node<K, V> right() { + return right; + } + + public K getKey() { + return key; + } + + public V getValue() { + return value; + } + + + public Node<K, V> put(Comparable<? super K> k, V value) { + if (!isNotEmpty()) { + return createNode((K)k, value, left, right); + } + int result = compare(k); + if (result > 0) { + Node<K, V> node = right.put(k, value); + node = createNode(key, this.value, left, node); + return node.insBalance(); + } else if (result < 0) { + Node node = left.put(k, value); + return createNode(key, this.value, node, right).insBalance(); + } + return createNode(key, value, left, right); // equals + + } + + public Node<K, V> delete(Comparable<? super K> key, Node<K, V> parent, Rotate side) throws RotateParent { + if (this.isNotEmpty()) { + int result = compare(key); + + try { + Node<K, V> node = null; + if (result > 0) { + node = right.delete(key, this, Rotate.R); + if (node == null) + return null; + if (parent == null) + return node; + } else if (result < 0) { + node = left.delete(key, this, Rotate.L); + if (node == null) + return null; + if (parent == null) + return node; + } else if (result == 0) { + node = replaceNode(parent); + if (parent == null)// equals + return node; + if (side == Rotate.R) + return parent.createNode(parent.getKey(), parent.getValue(), parent.left(), node); + else + return parent.createNode(parent.getKey(), parent.getValue(), node, parent.right()); + } + if (side == Rotate.L) + return parent.createNode(parent.getKey(), parent.getValue(), node, parent.right()); + else + return parent.createNode(parent.getKey(), parent.getValue(), parent.left(), node); + } catch (RotateParent e) { + Node node = e.getParent(); + if (parent != null) + return node.deleteBalance(parent); + return node; + } + } + return null; // no key + } + + + public Node<K, V> deleteSubTreeMaxNode(Node<K, V> parent, Rotate side) throws RotateParent { + Node<K, V> node; + try { + if (right().isNotEmpty()) {//最大値のノードが取得できるまで潜る + node = right().deleteSubTreeMaxNode(this, Rotate.R); + } else { + node = this.replaceNode(parent); + } + } catch (RotateParent e) { + node = e.getParent(); + if (parent == null) + throw e; + return node.deleteBalance(parent); + } + if (parent == null) + return node; + if (side == Rotate.R) + return parent.createNode(parent.getKey(), parent.getValue(), parent.left(), node); + else + return parent.createNode(parent.getKey(), parent.getValue(), node, parent.right()); + + } + + public Node deleteBalance(Node<K, V> parent) throws RotateParent { + if (!isRed()) { + if (0 > compare((Comparable<? super K>) parent.getKey())) { //自身がどちらの子かを調べる + boolean rightChild = parent.left().right().isRed(); + boolean leftChild = parent.left().left().isRed(); + + if (!parent.isRed()) { //親が黒 + if (!parent.left().isRed()) { //左の子が黒 + if (!rightChild && !leftChild) + throw new RotateParent(rebuildThree(parent, Rotate.R)); + if (rightChild) + return rebuildfive(parent, Rotate.R); + else if (leftChild) + return rebuildsix(parent, Rotate.R); + } else { //左の子が赤 + return rebuildTwo(parent, Rotate.R); + } + } else { //親が赤 + if (!rightChild && !leftChild) + return rebuildFour(parent, Rotate.R); + if (rightChild) + return rebuildfive(parent, Rotate.R); + else if (leftChild) + return rebuildsix(parent, Rotate.R); + } + } else { + boolean rightChild = parent.right().right().isRed(); + boolean leftChild = parent.right().left().isRed(); + + if (!parent.isRed()) { //親が黒 + if (!parent.right().isRed()) { //左の子が黒 + if (!rightChild && !leftChild) + throw new RotateParent(rebuildThree(parent, Rotate.L)); + if (rightChild) + return rebuildsix(parent, Rotate.L); + else if (leftChild) + return rebuildfive(parent, Rotate.L); + } else { //左の子が赤 + return rebuildTwo(parent, Rotate.L); + } + } else { //親が赤 + if (!rightChild && !leftChild) + return rebuildFour(parent, Rotate.L); + if (rightChild) + return rebuildsix(parent, Rotate.L); + else if (leftChild) + return rebuildfive(parent, Rotate.L); + } + } + } + if (0 > (compare((Comparable<? super K>) parent.getKey()))) + return parent.createNode(parent.getKey(), parent.getValue(), parent.left(), this); + else + return parent.createNode(parent.getKey(), parent.getValue(), this, parent.right()); + } + + protected Node<K, V> rebuildTwo(Node<K, V> parent, Rotate side) throws RotateParent { // case2 + if (side == Rotate.L) { // rotate Left + Node<K, V> node = parent.right(); + Node<K, V> leftSubTreeRoot = node.createNode(parent.getKey(), parent.getValue(), this, node.left()); // check + Node<K, V> leftNode = this.deleteBalance(leftSubTreeRoot); + Node<K, V> rightNode = node.right(); + return parent.createNode(node.getKey(), node.getValue(), leftNode, rightNode); + } else { // rotate Right + Node<K, V> node = parent.left(); + Node<K, V> rightSubTreeRoot = node.createNode(parent.getKey(), parent.getValue(), node.right(), this); + Node<K, V> rightNode = this.deleteBalance(rightSubTreeRoot); + Node<K, V> leftNode = node.left(); + return parent.createNode(node.getKey(), node.getValue(), leftNode, rightNode); + } + } + + protected Node rebuildThree(Node<K, V> parent, Rotate side) { // case3 再帰 + if (side == Rotate.L) { + Node<K, V> rightNode; + if (parent.right().isNotEmpty()) + rightNode = new RedNode<K, V>(parent.right().getKey(), parent.right().getValue(), parent.right().left(), parent.right().right()); // check + else + rightNode = new EmptyNode<>(); + return parent.createNode(parent.getKey(), parent.getValue(), this, rightNode); + } else { + Node<K, V> leftNode; + if (parent.left().isNotEmpty()) + leftNode = new RedNode<K, V>(parent.left().getKey(), parent.left().getValue(), parent.left().left(), parent.left().right()); // check + else + leftNode = new EmptyNode<>(); + return parent.createNode(parent.getKey(), parent.getValue(), leftNode, this); + } + } + + protected Node rebuildFour(Node<K, V> parent, Rotate side) { //case 4 + if (side == Rotate.R) { + Node<K, V> leftNode = new RedNode<K, V>(parent.left().getKey(), parent.left().getValue(), parent.left().left(), parent.left().right()); + return new BlackNode<K, V>(parent.getKey(), parent.getValue(), leftNode, this); + } else { + Node<K, V> rightNode = new RedNode<K, V>(parent.right().getKey(), parent.right().getValue(), parent.right().left(), parent.right().right()); + return new BlackNode<K, V>(parent.getKey(), parent.getValue(), this, rightNode); + } + } + + protected Node rebuildfive(Node<K, V> parent, Rotate side) { //case5 + if (side == Rotate.R) { // rotate Left + Node<K, V> leftChild = new RedNode<K, V>(parent.left().getKey(), parent.left().getValue(), parent.left().left(), parent.left().right().left()); + Node<K, V> rightChild = parent.left().right().right(); + Node<K, V> leftSubTreeRoot = new BlackNode<K, V>(parent.left().right().getKey(), parent.left().right().getValue(), leftChild, rightChild); + Node<K, V> newParent = parent.createNode(parent.getKey(), parent.getValue(), leftSubTreeRoot, this); + return this.rebuildsix(newParent, Rotate.R); + } else { // rotate Right 修正済み + Node<K, V> leftChild = parent.right().left().left(); + Node<K, V> rightChild = new RedNode<K, V>(parent.right().getKey(), parent.right().getValue(), parent.right().left().right(), parent.right().right()); + Node<K, V> rightSubTreeRoot = new BlackNode<K, V>(parent.right().left().getKey(), parent.right().left().getValue(), leftChild, rightChild); + Node<K, V> newParent = parent.createNode(parent.getKey(), parent.getValue(), this, rightSubTreeRoot); + return this.rebuildsix(newParent, Rotate.L); + } + } + + protected Node rebuildsix(Node<K, V> parent, Rotate side) { //case6 + if (side == Rotate.L) { // rotate Left + Node<K, V> leftChild = parent.right().createNode(parent.getKey(), parent.getValue(), this, parent.right().left()); //check + Node<K, V> rightChild = new BlackNode<K, V>(parent.right().right().getKey(), parent.right().right().getValue(), parent.right().right().left(), parent.right().right().right()); + return parent.createNode(parent.right().getKey(), parent.right().getValue(), leftChild, rightChild); + } else { // rotate Right + Node<K, V> leftChild = new BlackNode<K, V>(parent.left().left().getKey(), parent.left().left().getValue(), parent.left().left().left(), parent.left().left().right()); + Node<K, V> rightChild = parent.left().createNode(parent.getKey(), parent.getValue(), parent.left().right(), this); + return parent.createNode(parent.left().getKey(), parent.left().getValue(), leftChild, rightChild); + } + } + + + protected abstract boolean isNotEmpty(); + + public abstract Node<K, V> createNode(K key, V value, Node<K, V> left, Node<K, V> right); + + abstract Node<K, V> insBalance(); + + abstract Rotate checkRotate(Rotate side); + + abstract boolean isRed(); + + public abstract Node replaceNode(Node<K, V> parent) throws RotateParent; + + protected abstract Node deleteNode() throws RotateParent; + + @Test + protected abstract int checkDepth (int count , int minCount); // test method +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/TreeMap/RedNode.java Sat May 16 16:22:36 2015 +0900 @@ -0,0 +1,115 @@ +package jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap; + +import org.junit.Test; + +import static jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap.Rotate.*; + +/** + * Created by e115731 on 15/03/25. + */ +public class RedNode<K, V> extends Node<K, V> { + + + public RedNode(K key, V value, Node<K, V> left, Node<K, V> right) { + super(key, value, left, right); + } + + + @Override + protected boolean isNotEmpty() { + return true; + } + + @Override + public Node<K, V> createNode(K key, V value, Node<K, V> left, Node<K, V> right) { + return new RedNode<K, V>(key, value, left, right); + } + + @Override + protected Node<K, V> insBalance() { + return this; + } + + @Override + protected Node deleteNode() throws RotateParent { + EmptyNode emptyNode = new EmptyNode(this.getKey()); + return emptyNode; + } + + @Override + Rotate checkRotate(Rotate side) { + if (side == L) { + if (left.isRed()) + return R; + else if (right.isRed()) + return LR; + return N; + } else { + if (left.isRed()) + return RL; + else if (right.isRed()) + return L; + return N; + } + } + + @Override + boolean isRed() { + return true; + } + + @Override + public Node replaceNode(Node<K, V> parent) throws RotateParent { + Node<K, V> newNode = null; + if (!this.left().isNotEmpty() && !this.right().isNotEmpty()) { //自身を削除する + return deleteNode(); + } else if (this.left().isNotEmpty() && !this.right().isNotEmpty()) { //左の部分木を昇格させる + newNode = left().createNode(left().getKey(), left().getValue(), left().left(), left().right()); + return newNode; + } else if (!this.left().isNotEmpty() && this.right().isNotEmpty()) { //右の部分木を昇格させる + newNode = right().createNode(right().getKey(), right().getValue(), right().left(), right().right()); + return newNode; + } else {//子ノードが左右にある場合 + //左の部分木の最大の値を持つNodeと自身を置き換える + Node<K, V> cur = this.left(); + + while (cur.right().isNotEmpty()) { + cur = cur.right(); + } + Node leftSubTreeNode = null; + if (this.left().right().isNotEmpty()) { + try { + leftSubTreeNode = this.left().deleteSubTreeMaxNode(null,Rotate.L); + newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.right()); + return newNode; + } catch (RotateParent e) { + leftSubTreeNode = e.getParent(); + Node<K, V> newParent = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.right()); + return leftSubTreeNode.deleteBalance(newParent); + } + } else { + try { + leftSubTreeNode = this.left().replaceNode(this); + newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.right()); + return newNode; + } catch (RotateParent e) { + Node node = e.getParent(); + Node newParent = createNode(this.left().getKey(), this.left().getValue(), leftSubTreeNode, this.right()); + return node.deleteBalance(newParent); + } + } + + } + } + + + @Override + @Test + protected int checkDepth(int count,int minCount) { // test method + count ++; + minCount = left().checkDepth(count, minCount); + minCount = right().checkDepth(count, minCount); + count --; + return minCount; + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/TreeMap/Rotate.java Sat May 16 16:22:36 2015 +0900 @@ -0,0 +1,8 @@ +package jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap; + +/** + * Created by e115731 on 15/03/23. + */ +public enum Rotate { + R, L, RL, LR, N; +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/TreeMap/RotateParent.java Sat May 16 16:22:36 2015 +0900 @@ -0,0 +1,15 @@ +package jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap; + +/** + * Created by e115731 on 15/04/17. + */ +public class RotateParent extends Exception { + Node parent ; + public RotateParent(Node node) { + this.parent = node; + } + + public Node getParent(){ + return parent; + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/TreeMap/TreeMap.java Sat May 16 16:22:36 2015 +0900 @@ -0,0 +1,114 @@ +package jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap; + + +import org.junit.Test; + +import java.util.Iterator; +import java.util.Optional; +import java.util.Stack; + + +/** + * Created by e115731 on 15/03/23. + */ +public class TreeMap<K, V> { + final Node<K, V> root; + final int size; + + public TreeMap() { + this.root = new EmptyNode(); + this.size = 0; + } + + + public Node getRoot() { + return root; + } + + public TreeMap(Node<K, V> root, int size) { + this.root = root; + this.size = size; + } + + public Optional<V> get(final K key) { + return root.get(key); + } + + public TreeMap put(K key, V value) { + + if (key == null || value == null) // null check + throw new NullPointerException(); + + if (isEmpty()) { + Node<K, V> newRoot = new BlackNode(key, value, new EmptyNode(), new EmptyNode()); + return new TreeMap<K, V>(newRoot, size + 1); + } + + Node<K, V> newEntry = root.put((Comparable<? super K>) key, value); + Node<K, V> newRoot = new BlackNode(newEntry.getKey(), newEntry.getValue(), newEntry.left(), newEntry.right()); + return new TreeMap(newRoot, 0); + } + + + public boolean isEmpty() { + return !root.isNotEmpty(); + } + + + public TreeMap<K, V> delete(K key) { + Node node = null; + try { + node = root.delete((Comparable<? super K>) key, null, Rotate.N); + } catch (RotateParent rotateParent) { + } + if (node == null) + return this; // not key + if (!node.isNotEmpty()) + return new TreeMap(new EmptyNode<>(), 0); + Node newRoot = new BlackNode(node.getKey(), node.getValue(), node.left(), node.right()); + return new TreeMap(newRoot, 0); + } + + public Iterator<K> keys() { + return new Iterator<K>() { + Stack<Node> nodeStack = new Stack(); + Node currentNode = root; + + @Override + public boolean hasNext() { + return currentNode != null; + } + + @Override + public K next() { + K key = (K) currentNode.getKey(); + + if (currentNode.left().isNotEmpty()) { + nodeStack.push(currentNode); + currentNode = currentNode.left(); + return key; + } else if (currentNode.right().isNotEmpty()) { + currentNode = currentNode.right(); + return key; + } else if (nodeStack.isEmpty()) { + currentNode = null; + return key; + } + + do { + currentNode = nodeStack.pop().right(); + if (currentNode.isNotEmpty()) + return key; + + } while (!nodeStack.isEmpty()); + return key; + } + }; + } + + @Test + public void checkDepth() { + root.checkDepth(0, 0); + System.out.println("-----------------------------------"); + } +}
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/IndexCreater.java Wed May 06 18:40:15 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/IndexCreater.java Sat May 16 16:22:36 2015 +0900 @@ -3,7 +3,7 @@ import fj.data.List; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNodeChildren; -import jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap.TreeMap; import java.util.Iterator; import java.util.Optional;
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/ParentIndex.java Wed May 06 18:40:15 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/ParentIndex.java Sat May 16 16:22:36 2015 +0900 @@ -2,7 +2,7 @@ import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNodeChildren; -import jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap.TreeMap; import java.util.Iterator;
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/test/TatsukiTreeMapGetThread.java Wed May 06 18:40:15 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/test/TatsukiTreeMapGetThread.java Sat May 16 16:22:36 2015 +0900 @@ -1,6 +1,6 @@ package jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.test; -import jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap.TreeMap; import java.util.Optional;
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/test/TreeMapBenchMark.java Wed May 06 18:40:15 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/test/TreeMapBenchMark.java Sat May 16 16:22:36 2015 +0900 @@ -36,7 +36,7 @@ readThread[count] = new UtilTreeMapGetThread(map); } } else if (args[0].equals("tatsuki")) { - jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.TreeMap map = new jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.TreeMap(); + jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap.TreeMap map = new jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap.TreeMap(); for (long count = 0; count < 1000; count++) { map = map.put(count, String.valueOf(count)); }
--- a/src/test/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/impl/clonable/DefaultTreeNodeAttributesTest.java Wed May 06 18:40:15 2015 +0900 +++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/impl/clonable/DefaultTreeNodeAttributesTest.java Sat May 16 16:22:36 2015 +0900 @@ -6,7 +6,7 @@ import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.core.AttributesTest; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.transaction.DefaultTreeNode; -import jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap.TreeMap; import junit.framework.TestCase; import junit.framework.TestSuite;
--- a/src/test/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/impl/node/DefaultAttributesTest.java Wed May 06 18:40:15 2015 +0900 +++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/impl/node/DefaultAttributesTest.java Sat May 16 16:22:36 2015 +0900 @@ -6,7 +6,7 @@ import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNodeAttributes; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.transaction.DefaultTreeNode; -import jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap.TreeMap; import org.junit.Assert; import java.nio.ByteBuffer;
--- a/src/test/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/impl/node/DefaultChildrenTest.java Wed May 06 18:40:15 2015 +0900 +++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/impl/node/DefaultChildrenTest.java Sat May 16 16:22:36 2015 +0900 @@ -5,7 +5,7 @@ import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.transaction.DefaultTreeNode; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.transaction.DefaultTreeNodeChildren; -import jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap.TreeMap; import org.junit.Assert; import java.nio.ByteBuffer;
--- a/src/test/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/impl/node/DefaultNodeTest.java Wed May 06 18:40:15 2015 +0900 +++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/impl/node/DefaultNodeTest.java Sat May 16 16:22:36 2015 +0900 @@ -3,7 +3,7 @@ import fj.data.List; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.transaction.DefaultTreeNode; -import jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap.TreeMap; import junit.framework.TestCase; import junit.framework.TestSuite;
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/treemap/TreeMapDelete.java Sat May 16 16:22:36 2015 +0900 @@ -0,0 +1,36 @@ +package jp.ac.u_ryukyu.ie.cr.tatsuki.treemap; + +import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap.RotateParent; +import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap.TreeMap; +import org.junit.Test; + +import java.util.ArrayList; +import java.util.Collections; + +/** + * Created by e115731 on 15/04/04. + */ +public class TreeMapDelete { + + @Test + public void TreeMapDeleteTest() throws RotateParent { + TreeMap<Integer, Integer> map = new TreeMap(); + for (int count = 1; count < 1000; count++) { + map = map.put(count, count); + map.checkDepth(); + } + + ArrayList<Integer> list = new ArrayList(); + for (int i = 1; i < 1000; i++) { + list.add(i); + } + Collections.shuffle(list); + for (Integer num : list) { + System.out.println(num); + TreeMap newMap = map.delete(num); + map = newMap; + map.checkDepth(); + } + System.out.println("end"); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/treemap/TreeMapTest.java Sat May 16 16:22:36 2015 +0900 @@ -0,0 +1,48 @@ +package jp.ac.u_ryukyu.ie.cr.tatsuki.treemap; + +import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap.TreeMap; + +import java.util.Optional; + +/** + * Created by e115731 on 15/03/24. + */ +public class TreeMapTest { + public static void main(String args[]) { + TreeMap<Integer, Integer> map = new TreeMap(); + TreeMap<Integer, Integer> map1 = map.put(0,0); + TreeMap<Integer, Integer> map2 = map1.put(1,1); + TreeMap<Integer, Integer> map3 = map2.put(2,2); + TreeMap<Integer, Integer> map4 = map3.put(3,3); + TreeMap<Integer, Integer> map5 = map4.put(4,4); + for (int count = 100; count > 0; count--) { + map = map.put(count, count); + map.checkDepth(); + System.out.println("-------------------------------------------"); + } + + for (int count = 100; count > -10; count--) { + + Optional<Integer> op = map.get(count); + if (op.isPresent()) + System.out.println(op.get()); + } + + System.out.println("end"); + } +} + + + + + + + + + + + + + + +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/treemap/TreeNodeIteratorTest.java Sat May 16 16:22:36 2015 +0900 @@ -0,0 +1,30 @@ +package jp.ac.u_ryukyu.ie.cr.tatsuki.treemap; + +import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap.TreeMap; +import junit.framework.Assert; +import org.junit.Test; + +import java.util.Iterator; + +/** + * Created by e115731 on 15/05/06. + */ +public class TreeNodeIteratorTest { + @Test + public void getKeyTest() { + TreeMap<Integer, Integer> map = new TreeMap(); + for (int attributeMaxCount = 10; attributeMaxCount < 1000; attributeMaxCount = attributeMaxCount + 10) { + for (int count = 0; count < attributeMaxCount; count++) { //insertData + map = map.put(count, count); + } + Iterator<Integer> it = map.keys(); + int iteratorCount = 0; + while (it.hasNext()) { // count return iterator Attribute Count + iteratorCount++; + System.out.println(it.next()); + } + Assert.assertTrue(iteratorCount == attributeMaxCount); // check + } + + } +}