Mercurial > hg > Members > shoshi > jungle > jungle-core
changeset 202:f6cebe3f4505
add nondestructiveList
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/list/DefaultNode.java Mon May 18 14:26:38 2015 +0900 @@ -0,0 +1,68 @@ +package jp.ac.u_ryukyu.ie.cr.list; + +/** + * Created by e115731 on 15/05/16. + */ +public class DefaultNode<T> implements Node<T> { + private final T attribute; + private final int num; + private final Node next; + + public DefaultNode(T attribute, int num, Node next) { + this.attribute = attribute; + this.num = num; + this.next = next; + } + + public int getNum() { + return num; + } + + public Node getNext() { + return next; + } + + public T getAttribute() { + return attribute; + } + + public Node<T> add(int num, T attribute) { + if (this.num == num) { + Node<T> newNode = new DefaultNode(attribute, num, this.next); + return new DefaultNode<T>(this.attribute, this.num + 1, newNode); + } + + Node<T> newNode = next.add(num, attribute); + if (newNode == null) + return null; + + return new DefaultNode(this.attribute, this.num + 1, newNode); + } + + @Override + public Node<T> delete(int deleteNum) { + if (this.num - 1 == deleteNum) { + return new DefaultNode(this.attribute, deleteNum, this.next.getNext()); + } + + Node<T> newNode = next.delete(deleteNum); + if (newNode == null) + return null; + + return new DefaultNode(this.attribute, this.num - 1, newNode); + } + + @Override + public Node<T> replaceNode(int num, T attribute) { + if (this.num - 1 == num) { + Node<T> newNode = new DefaultNode(attribute, num, this.next.getNext()); + return new DefaultNode(this.attribute, num + 1, newNode); + } + + Node<T> newNode = next.replaceNode(num, attribute); + if (newNode == null) + return null; + + return new DefaultNode(this.attribute, this.num, newNode); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/list/List.java Mon May 18 14:26:38 2015 +0900 @@ -0,0 +1,84 @@ +package jp.ac.u_ryukyu.ie.cr.list; + +import java.util.Iterator; + +/** + * Created by e115731 on 15/05/16. + */ +public class List<T> { + final Node<T> head; + final int listLength; + + public List() { + this.head = new headNode(null); + this.listLength = 0; + } + + + private List(Node<T> head) { + this.head = head; + this.listLength = head.getNext().getNum(); + } + + public List<T> addLast(T attribute) { + Node newNode = new DefaultNode(attribute, listLength + 1, head.getNext()); + Node newHead = new headNode(newNode); + return new List(newHead); + } + + public T index(int num) { + Node<T> currentNode = head.getNext(); + while (currentNode.getNum() != -1) { + if (currentNode.getNum() == num) + return currentNode.getAttribute(); + currentNode = currentNode.getNext(); + } + return null; + } + + public Iterator<T> iterator() { + return new Iterator<T>() { + Node<T> currentNode = head.getNext(); + + @Override + public boolean hasNext() { + return currentNode.getNum() != -1; + } + + @Override + public T next() { + T attribute = currentNode.getAttribute(); + currentNode = currentNode.getNext(); + return attribute; + } + }; + } + + public List<T> add(int num, T attribute) { + Node<T> newNode = head.getNext().add(num, attribute); + if (newNode == null) + return this; + Node<T> newHead = new headNode<>(newNode); + return new List<T>(newHead); + } + + public List<T> delete(int num) { + Node<T> newNode = head.getNext().delete(num); + if (newNode == null) + return this; + Node<T> newHead = new headNode<>(newNode); + return new List<T>(newHead); + } + + public List<T> replace(int num, T attribute) { + Node<T> newNode = head.getNext().replaceNode(num,attribute); + if (newNode == null) + return this; + Node<T> newHead = new headNode<>(newNode); + return new List<T>(newHead); + } + + public int lengh() { + return listLength; + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/list/Node.java Mon May 18 14:26:38 2015 +0900 @@ -0,0 +1,18 @@ +package jp.ac.u_ryukyu.ie.cr.list; + +/** + * Created by e115731 on 15/05/18. + */ +public interface Node<T> { + public int getNum(); + + public Node getNext(); + + public T getAttribute(); + + public Node<T> add(int num, T attribute); + + public Node<T> delete(int num); + + Node<T> replaceNode(int num, T attribute); +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/list/headNode.java Mon May 18 14:26:38 2015 +0900 @@ -0,0 +1,39 @@ +package jp.ac.u_ryukyu.ie.cr.list; + +/** + * Created by e115731 on 15/05/18. + */ +public class headNode<T> implements Node<T> { + private final Node next; + + public headNode(Node next) { + this.next = next; + } + + public int getNum() { + return -1; + } + + public Node getNext() { + if (next == null) + return this; + return next; + } + + public T getAttribute() { + return null; + } + + public Node<T> add(int num, T attribute) { + return null; + } + + public Node<T> delete(int num) { + return null; + } + + @Override + public Node<T> replaceNode(int num, T attribute) { + return null; + } +}
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/DefaultJungleTree.java Sat May 16 16:28:43 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/DefaultJungleTree.java Mon May 18 14:26:38 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.jungle.TreeMap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.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 Sat May 16 16:28:43 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/JungleTree.java Mon May 18 14:26:38 2015 +0900 @@ -2,7 +2,7 @@ import fj.data.List; -import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.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 Sat May 16 16:28:43 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/store/TreeContext.java Mon May 18 14:26:38 2015 +0900 @@ -2,7 +2,7 @@ import fj.data.List; -import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.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 Sat May 16 16:28:43 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/store/impl/TreeNodeAttributes.java Mon May 18 14:26:38 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.jungle.TreeMap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.treemap.TreeMap; import java.nio.ByteBuffer; import java.util.Iterator;
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/store/impl/TreeNodeChildren.java Sat May 16 16:28:43 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/store/impl/TreeNodeChildren.java Mon May 18 14:26:38 2015 +0900 @@ -12,5 +12,4 @@ public Either<Error,TreeNode> addNewChildAt(int pos,TreeNode newChild); public Either<Error,TreeNode> replaceNode(int pos,TreeNode replacement); public List<TreeNode> getChildrenAsRawList(); - public Either<Error,TreeNode> addExistTreeNodeToChildren(TreeNode node, int pos); } \ No newline at end of file
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/DefaultTreeContext.java Sat May 16 16:28:43 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/DefaultTreeContext.java Mon May 18 14:26:38 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.jungle.TreeMap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.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 Sat May 16 16:28:43 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/DefaultTreeNode.java Mon May 18 14:26:38 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.jungle.TreeMap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.treemap.TreeMap; import java.nio.ByteBuffer; import java.rmi.dgc.VMID; @@ -48,7 +48,7 @@ @Override public Either<Error, TreeNode> appendRootNode() { TreeNodeChildren newRootChildren = new DefaultTreeNodeChildren(NIL_LIST, new TreeMap()); - Either<Error, TreeNode> either = newRootChildren.addExistTreeNodeToChildren(this, 0); + Either<Error, TreeNode> either = newRootChildren.addNewChildAt(0,this); return either; }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/DefaultTreeNodeAttribute.java Sat May 16 16:28:43 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/DefaultTreeNodeAttribute.java Mon May 18 14:26:38 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.jungle.TreeMap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.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 Sat May 16 16:28:43 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/DefaultTreeNodeChildren.java Mon May 18 14:26:38 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.jungle.TreeMap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.treemap.TreeMap; import java.nio.ByteBuffer; import java.util.Iterator; @@ -131,17 +131,4 @@ return DefaultEither.newB(newNode); } - @Override - public Either<Error, TreeNode> addExistTreeNodeToChildren(TreeNode node, int pos) { - - if(!boundaryCheck(pos) || pos < 0){ - return DefaultEither.newA(NodeEditorError.INDEX_OUT_OF_BOUNDS); - } - - P2<List<TreeNode>,List<TreeNode>> split = children.splitAt(pos); - List<TreeNode> newChildren = split._1().snoc(node).append(split._2()); - TreeNode newNode = new DefaultTreeNode(newChildren,attrs); - return DefaultEither.newB(newNode); - } - }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/traverser/InterfaceTraverser.java Sat May 16 16:28:43 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/traverser/InterfaceTraverser.java Mon May 18 14:26:38 2015 +0900 @@ -4,7 +4,7 @@ import java.util.Optional; import fj.data.List; -import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.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;
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/TreeMap/BlackNode.java Sat May 16 16:28:43 2015 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,137 +0,0 @@ -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); - } - } - } - } -}
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/TreeMap/EmptyNode.java Sat May 16 16:28:43 2015 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,84 +0,0 @@ -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; - } - -}
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/TreeMap/Node.java Sat May 16 16:28:43 2015 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,295 +0,0 @@ -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 -}
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/TreeMap/RedNode.java Sat May 16 16:28:43 2015 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,115 +0,0 @@ -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; - } -}
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/TreeMap/Rotate.java Sat May 16 16:28:43 2015 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,8 +0,0 @@ -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; -}
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/TreeMap/RotateParent.java Sat May 16 16:28:43 2015 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,15 +0,0 @@ -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; - } -}
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/TreeMap/TreeMap.java Sat May 16 16:28:43 2015 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,114 +0,0 @@ -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 Sat May 16 16:28:43 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/IndexCreater.java Mon May 18 14:26:38 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.jungle.TreeMap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.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 Sat May 16 16:28:43 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/ParentIndex.java Mon May 18 14:26:38 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.jungle.TreeMap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.treemap.TreeMap; import java.util.Iterator;
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/test/TatsukiTreeMapGetThread.java Sat May 16 16:28:43 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/test/TatsukiTreeMapGetThread.java Mon May 18 14:26:38 2015 +0900 @@ -1,6 +1,6 @@ package jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.test; -import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.treemap.TreeMap; import java.util.Optional;
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/test/TreeMapBenchMark.java Sat May 16 16:28:43 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/test/TreeMapBenchMark.java Mon May 18 14:26:38 2015 +0900 @@ -1,5 +1,7 @@ package jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.test; +import jp.ac.u_ryukyu.ie.cr.treemap.TreeMap; + import java.io.*; /** @@ -36,7 +38,7 @@ readThread[count] = new UtilTreeMapGetThread(map); } } else if (args[0].equals("tatsuki")) { - jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap.TreeMap map = new jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap.TreeMap(); + TreeMap map = new TreeMap(); for (long count = 0; count < 1000; count++) { map = map.put(count, String.valueOf(count)); }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/treemap/BlackNode.java Mon May 18 14:26:38 2015 +0900 @@ -0,0 +1,135 @@ +package jp.ac.u_ryukyu.ie.cr.treemap; + +import org.junit.Test; + + +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(Rotate.L); + + if (spin == Rotate.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 == Rotate.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(Rotate.R); + if (spin == Rotate.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 == Rotate.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 Rotate.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/treemap/EmptyNode.java Mon May 18 14:26:38 2015 +0900 @@ -0,0 +1,82 @@ +package jp.ac.u_ryukyu.ie.cr.treemap; + +import org.junit.Assert; +import org.junit.Test; + +/** + * 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 Rotate.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/treemap/Node.java Mon May 18 14:26:38 2015 +0900 @@ -0,0 +1,295 @@ +package jp.ac.u_ryukyu.ie.cr.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/treemap/RedNode.java Mon May 18 14:26:38 2015 +0900 @@ -0,0 +1,113 @@ +package jp.ac.u_ryukyu.ie.cr.treemap; + +import org.junit.Test; + +/** + * 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 == 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; + } + } + + @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/treemap/Rotate.java Mon May 18 14:26:38 2015 +0900 @@ -0,0 +1,8 @@ +package jp.ac.u_ryukyu.ie.cr.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/treemap/RotateParent.java Mon May 18 14:26:38 2015 +0900 @@ -0,0 +1,15 @@ +package jp.ac.u_ryukyu.ie.cr.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/treemap/TreeMap.java Mon May 18 14:26:38 2015 +0900 @@ -0,0 +1,114 @@ +package jp.ac.u_ryukyu.ie.cr.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/test/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/impl/clonable/DefaultTreeNodeAttributesTest.java Sat May 16 16:28:43 2015 +0900 +++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/impl/clonable/DefaultTreeNodeAttributesTest.java Mon May 18 14:26:38 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.jungle.TreeMap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.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 Sat May 16 16:28:43 2015 +0900 +++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/impl/node/DefaultAttributesTest.java Mon May 18 14:26:38 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.jungle.TreeMap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.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 Sat May 16 16:28:43 2015 +0900 +++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/impl/node/DefaultChildrenTest.java Mon May 18 14:26:38 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.jungle.TreeMap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.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 Sat May 16 16:28:43 2015 +0900 +++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/impl/node/DefaultNodeTest.java Mon May 18 14:26:38 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.jungle.TreeMap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.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/list/deleteTest.java Mon May 18 14:26:38 2015 +0900 @@ -0,0 +1,23 @@ +package jp.ac.u_ryukyu.ie.cr.tatsuki.list; + +import jp.ac.u_ryukyu.ie.cr.list.List; +import junit.framework.Assert; +import org.junit.Test; + +/** + * Created by e115731 on 15/05/18. + */ +public class deleteTest { + @Test + public void deleteTest() { + List<Integer> list = new List<Integer>(); + + for (int count = 1; count <= 10; count++) { + list = list.addLast(count); + } + + List<Integer> newList = list.delete(5); + Assert.assertEquals(newList.lengh(),9); + Assert.assertEquals(list.lengh(),10); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/list/listAdd.java Mon May 18 14:26:38 2015 +0900 @@ -0,0 +1,38 @@ +package jp.ac.u_ryukyu.ie.cr.tatsuki.list; + +import jp.ac.u_ryukyu.ie.cr.list.List; +import junit.framework.Assert; +import org.junit.Test; + +/** + * Created by e115731 on 15/05/17. + */ +public class listAdd { + + @Test + public void listAddTest() { + List<Integer> list = new List<Integer>(); + + for (int count = 1; count <= 10; count++) { + list = list.addLast(count); + } + Assert.assertEquals(list.lengh(), 10); + int num = list.index(5); + Assert.assertEquals(num, 5); + + List<Integer> newList = list.add(5, 1000); + num = newList.index(5); + Assert.assertEquals(num, 1000); + num = list.index(5); + Assert.assertEquals(num, 5); + + list = list.add(1000, 1001); + num = list.index(5); + Assert.assertEquals(num, 5); + + Integer aaa = list.index(11); + System.out.println("aaa"); + } + + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/list/listIterator.java Mon May 18 14:26:38 2015 +0900 @@ -0,0 +1,26 @@ +package jp.ac.u_ryukyu.ie.cr.tatsuki.list; + +import jp.ac.u_ryukyu.ie.cr.list.List; +import junit.framework.Assert; +import org.junit.Test; + +import java.util.Iterator; + +/** + * Created by e115731 on 15/05/17. + */ +public class listIterator { + @Test + public void listIteratorTest() { + List<Integer> list = new List<Integer>(); + for (int count = 1; count <= 100; count++) { + list = list.addLast(count); + } + Iterator<Integer> iterator = list.iterator(); + for (int count = 100; count > 0; count--) { + Assert.assertTrue(iterator.hasNext()); + int attribute = iterator.next(); + Assert.assertEquals(attribute, count); + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/list/replaceTest.java Mon May 18 14:26:38 2015 +0900 @@ -0,0 +1,25 @@ +package jp.ac.u_ryukyu.ie.cr.tatsuki.list; + +import jp.ac.u_ryukyu.ie.cr.list.List; +import junit.framework.Assert; +import org.junit.Test; + +/** + * Created by e115731 on 15/05/18. + */ +public class replaceTest { + @Test + public void replaceTest() { + List<Integer> list = new List<Integer>(); + for (int count = 1; count <= 10; count++) { + list = list.addLast(count); + } + List<Integer> newList = list.replace(5, 15); + Assert.assertEquals(list.lengh(), 10); + int attribute = list.index(5); + Assert.assertEquals(attribute, 5); + attribute = newList.index(5); + Assert.assertEquals(newList.lengh(), 10); + Assert.assertEquals(attribute, 15); + } +}
--- a/src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/treemap/TreeMapDelete.java Sat May 16 16:28:43 2015 +0900 +++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/treemap/TreeMapDelete.java Mon May 18 14:26:38 2015 +0900 @@ -1,7 +1,7 @@ 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 jp.ac.u_ryukyu.ie.cr.treemap.RotateParent; +import jp.ac.u_ryukyu.ie.cr.treemap.TreeMap; import org.junit.Test; import java.util.ArrayList;
--- a/src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/treemap/TreeMapTest.java Sat May 16 16:28:43 2015 +0900 +++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/treemap/TreeMapTest.java Mon May 18 14:26:38 2015 +0900 @@ -1,6 +1,6 @@ package jp.ac.u_ryukyu.ie.cr.tatsuki.treemap; -import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.treemap.TreeMap; import java.util.Optional;
--- a/src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/treemap/TreeNodeIteratorTest.java Sat May 16 16:28:43 2015 +0900 +++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/treemap/TreeNodeIteratorTest.java Mon May 18 14:26:38 2015 +0900 @@ -1,6 +1,6 @@ package jp.ac.u_ryukyu.ie.cr.tatsuki.treemap; -import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.TreeMap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.treemap.TreeMap; import junit.framework.Assert; import org.junit.Test;