Mercurial > hg > Members > shoshi > jungle > jungle-core
changeset 215:1b3661be3119
change TreeMap compare
& InterFace.find
use Index find
line wrap: on
line diff
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/DefaultJungle.java Wed Aug 05 00:36:57 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/DefaultJungle.java Tue Aug 11 08:16:07 2015 +0900 @@ -58,7 +58,7 @@ ChangeList list = new ChangeList() { @Override public Iterator<TreeOperation> iterator() { - List<TreeOperation> nil = new List(); + List<TreeOperation> nil = new List<>(); return nil.iterator(); }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/BlackNode.java Wed Aug 05 00:36:57 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/BlackNode.java Tue Aug 11 08:16:07 2015 +0900 @@ -2,6 +2,8 @@ import org.junit.Test; +import java.util.Comparator; + public class BlackNode<K, V> extends Node<K, V> { @@ -12,8 +14,8 @@ @Override - public Node deleteNode() throws RotateParent { - EmptyNode<K, V> emptyNode = new EmptyNode<K, V>(key); + public Node<K, V> deleteNode() throws RotateParent { + EmptyNode<K, V> emptyNode = new EmptyNode<>(key); throw new RotateParent(emptyNode); } @@ -23,7 +25,6 @@ count++; minCount = left().checkDepth(count, minCount); minCount = right().checkDepth(count, minCount); - count--; return minCount; } @@ -35,36 +36,36 @@ @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); + return new BlackNode<>(key, value, left, right); } @Override - Node insBalance() { + Node<K, V> 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); + Node<K, V> leftChild = new BlackNode<>(left.left().getKey(), left.left().getValue(), left.left().left(), left.left().right()); + Node<K, V> rightChild = new BlackNode<>(getKey(), getValue(), left.right(), right); + return new RedNode<>(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); + Node<K, V> leftChild = new BlackNode<>(left.getKey(), left.getValue(), left.left(), left.right().left()); + Node<K, V> rightChild = new BlackNode<>(getKey(), getValue(), left.right().right(), right); + return new RedNode<>(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); + Node<K, V> leftChild = new BlackNode<>(getKey(), getValue(), left, right.left()); + Node<K, V> rightChild = new BlackNode<>(right.right().getKey(), right.right().getValue(), right.right().left(), right.right().right()); + return new RedNode<>(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); + Node<K, V> leftChild = new BlackNode<>(getKey(), getValue(), left, right.left().left()); + Node<K, V> rightChild = new BlackNode<>(right.getKey(), right.getValue(), right.left().right(), right.right()); + return new RedNode<>(right.left().getKey(), right.left().getValue(), leftChild, rightChild); } @@ -83,13 +84,9 @@ } - /** - * @param parent - * @return - */ @Override - public Node replaceNode(Node<K, V> parent) throws RotateParent { - Node<K, V> newNode = null; + public Node<K, V> replaceNode(Node<K, V> parent, Comparator ctr) throws RotateParent { + Node<K, V> newNode; if (!this.left().isNotEmpty() && !this.right().isNotEmpty()) { //自身を削除する return deleteNode();//黒が1つ減るので木のバランスを取る } else if (this.left().isNotEmpty() && !this.right().isNotEmpty()) { //左の部分木を昇格させる @@ -110,24 +107,22 @@ } 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; + Node<K, V> leftSubTreeNode = this.left().deleteSubTreeMaxNode(null, ctr, Rotate.L);//最大値を削除した左の部分木を返す。rootはthisと同じ。 + return createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.right()); //rootをcurと入れ替えることでNodeの削除は完了する } catch (RotateParent e) { - Node leftSubTreeNode = e.getParent(); + Node<K, V> leftSubTreeNode = e.getParent(); Node<K, V> newParent = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.right()); - return leftSubTreeNode.deleteBalance(newParent); + return leftSubTreeNode.deleteBalance(newParent, ctr); } } else { - Node leftSubTreeNode = null; + Node<K, V> leftSubTreeNode = null; try { - leftSubTreeNode = this.left().replaceNode(this);//右の子がいなかった場合、左の子を昇格させるだけで良い。 - Node newParent = createNode(this.left().getKey(), this.left().getValue(), leftSubTreeNode, this.right()); - return newParent; + leftSubTreeNode = this.left().replaceNode(this, ctr);//右の子がいなかった場合、左の子を昇格させるだけで良い。 + return createNode(this.left().getKey(), this.left().getValue(), leftSubTreeNode, this.right()); } catch (RotateParent e) { - Node node = e.getParent(); - Node newParent = createNode(this.left().getKey(), this.left().getValue(), leftSubTreeNode, this.right()); - return node.deleteBalance(newParent); + Node<K, V> node = e.getParent(); + Node<K, V> newParent = createNode(this.left().getKey(), this.left().getValue(), node, this.right()); + return node.deleteBalance(newParent, ctr); } } }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/DefaultComparator.java Tue Aug 11 08:16:07 2015 +0900 @@ -0,0 +1,13 @@ +package jp.ac.u_ryukyu.ie.cr.jungle.data.treemap; + +import java.util.Comparator; + +/** + * Created by e115731 on 15/08/10. + */ +public class DefaultComparator<K> implements Comparator<K>{ + @Override + public int compare(K key, K compareKey) { + return ((Comparable<? super K>)key).compareTo(compareKey); + } +}
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/EmptyNode.java Wed Aug 05 00:36:57 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/EmptyNode.java Tue Aug 11 08:16:07 2015 +0900 @@ -3,9 +3,9 @@ import org.junit.Assert; import org.junit.Test; -/** - * Created by e115731 on 15/03/25. - */ +import java.util.Comparator; + + public class EmptyNode<K, V> extends Node<K, V> { public EmptyNode() { @@ -35,26 +35,26 @@ @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>()); + return new RedNode<>(key, value, new EmptyNode<>(), new EmptyNode<>()); } public Node<K, V> put(K k, V value) { - return new RedNode(k, value, new EmptyNode<K, V>(), new EmptyNode<K, V>()); + return new RedNode<>(k, value, new EmptyNode<>(), new EmptyNode<>()); } @Override - public Node replaceNode(Node<K, V> parent) { // not use method + public Node<K, V> replaceNode(Node<K, V> parent, Comparator ctr) { // not use method return this; } @Override - protected Node deleteNode() { //not use method + protected Node<K,V> deleteNode() { //not use method return this; } @Override - Node insBalance() { + Node<K, V> insBalance() { return this; } @@ -70,12 +70,12 @@ @Override @Test - protected int checkDepth(int count,int minCount) { // test method + 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); + Assert.assertTrue(count <= 2 * minCount); return minCount; }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/Node.java Wed Aug 05 00:36:57 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/Node.java Tue Aug 11 08:16:07 2015 +0900 @@ -2,10 +2,11 @@ import org.junit.Test; +import java.util.Comparator; import java.util.Optional; -public abstract class Node<K, V> { +public abstract class Node<K, V> { protected K key; protected V value; @@ -28,16 +29,15 @@ return left; } - public int compare(Comparable<? super K> compareKey) { - return compareKey.compareTo(getKey()); - + @SuppressWarnings("unchecked") + public int compare(K compareKey, Comparator ctr) { + return ctr.compare(compareKey, this.getKey()); } - public Optional<V> get(K key) { + public Optional<V> get(K key, Comparator ctr) { Node<K, V> cur = this; - Comparable<? super K> k = (Comparable<? super K>) key; while (cur.isNotEmpty()) { - int result = cur.compare(k); + int result = cur.compare(key, ctr); if (result > 0) cur = cur.right(); else if (result < 0) @@ -62,43 +62,43 @@ } - public Node<K, V> put(Comparable<? super K> k, V value) { + public Node<K, V> put(K k, V value, Comparator ctr) { if (!isNotEmpty()) { - return createNode((K)k, value, left, right); + return createNode(k, value, left, right); } - int result = compare(k); + int result = compare(k, ctr); if (result > 0) { - Node<K, V> node = right.put(k, value); + Node<K, V> node = right.put(k, value, ctr); node = createNode(key, this.value, left, node); return node.insBalance(); } else if (result < 0) { - Node node = left.put(k, value); + Node<K, V> node = left.put(k, value, ctr); 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 { + public Node<K, V> delete(K key, Node<K, V> parent, Comparator ctr, Rotate side) throws RotateParent { if (this.isNotEmpty()) { - int result = compare(key); + int result = compare(key, ctr); try { Node<K, V> node = null; if (result > 0) { - node = right.delete(key, this, Rotate.R); + node = right.delete(key, this, ctr, Rotate.R); if (node == null) return null; if (parent == null) return node; } else if (result < 0) { - node = left.delete(key, this, Rotate.L); + node = left.delete(key, this, ctr, Rotate.L); if (node == null) return null; if (parent == null) return node; } else if (result == 0) { - node = replaceNode(parent); + node = replaceNode(parent, ctr); if (parent == null)// equals return node; if (side == Rotate.R) @@ -111,9 +111,9 @@ else return parent.createNode(parent.getKey(), parent.getValue(), parent.left(), node); } catch (RotateParent e) { - Node node = e.getParent(); + Node<K, V> node = e.getParent(); if (parent != null) - return node.deleteBalance(parent); + return node.deleteBalance(parent, ctr); return node; } } @@ -121,19 +121,19 @@ } - public Node<K, V> deleteSubTreeMaxNode(Node<K, V> parent, Rotate side) throws RotateParent { + public Node<K, V> deleteSubTreeMaxNode(Node<K, V> parent, Comparator ctr, Rotate side) throws RotateParent { Node<K, V> node; try { if (right().isNotEmpty()) {//最大値のノードが取得できるまで潜る - node = right().deleteSubTreeMaxNode(this, Rotate.R); + node = right().deleteSubTreeMaxNode(this, ctr, Rotate.R); } else { - node = this.replaceNode(parent); + node = this.replaceNode(parent, ctr); } } catch (RotateParent e) { node = e.getParent(); if (parent == null) throw e; - return node.deleteBalance(parent); + return node.deleteBalance(parent, ctr); } if (parent == null) return node; @@ -144,9 +144,9 @@ } - public Node deleteBalance(Node<K, V> parent) throws RotateParent { + public Node<K, V> deleteBalance(Node<K, V> parent, Comparator ctr) throws RotateParent { if (!isRed()) { - if (0 > compare((Comparable<? super K>) parent.getKey())) { //自身がどちらの子かを調べる + if (0 > compare(parent.getKey(), ctr)) { //自身がどちらの子かを調べる boolean rightChild = parent.left().right().isRed(); boolean leftChild = parent.left().left().isRed(); @@ -156,17 +156,17 @@ throw new RotateParent(rebuildThree(parent, Rotate.R)); if (rightChild) return rebuildfive(parent, Rotate.R); - else if (leftChild) + else return rebuildsix(parent, Rotate.R); } else { //左の子が赤 - return rebuildTwo(parent, Rotate.R); + return rebuildTwo(parent, ctr, Rotate.R); } } else { //親が赤 if (!rightChild && !leftChild) return rebuildFour(parent, Rotate.R); if (rightChild) return rebuildfive(parent, Rotate.R); - else if (leftChild) + else return rebuildsix(parent, Rotate.R); } } else { @@ -179,44 +179,44 @@ throw new RotateParent(rebuildThree(parent, Rotate.L)); if (rightChild) return rebuildsix(parent, Rotate.L); - else if (leftChild) + else return rebuildfive(parent, Rotate.L); } else { //左の子が赤 - return rebuildTwo(parent, Rotate.L); + return rebuildTwo(parent, ctr, Rotate.L); } } else { //親が赤 if (!rightChild && !leftChild) return rebuildFour(parent, Rotate.L); if (rightChild) return rebuildsix(parent, Rotate.L); - else if (leftChild) + else return rebuildfive(parent, Rotate.L); } } } - if (0 > (compare((Comparable<? super K>) parent.getKey()))) + if (0 > (compare(parent.getKey(), ctr))) 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 + protected Node<K, V> rebuildTwo(Node<K, V> parent, Comparator ctr, 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> leftNode = this.deleteBalance(leftSubTreeRoot, ctr); 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> rightNode = this.deleteBalance(rightSubTreeRoot, ctr); 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 再帰 + protected Node<K, V> rebuildThree(Node<K, V> parent, Rotate side) { // case3 再帰 if (side == Rotate.L) { Node<K, V> rightNode; if (parent.right().isNotEmpty()) @@ -234,7 +234,7 @@ } } - protected Node rebuildFour(Node<K, V> parent, Rotate side) { //case 4 + protected Node<K, V> rebuildFour(Node<K, V> parent, Rotate side) { //case 4 if (side == Rotate.R) { Node<K, V> leftNode = new RedNode<>(parent.left().getKey(), parent.left().getValue(), parent.left().left(), parent.left().right()); return new BlackNode<>(parent.getKey(), parent.getValue(), leftNode, this); @@ -244,7 +244,7 @@ } } - protected Node rebuildfive(Node<K, V> parent, Rotate side) { //case5 + protected Node<K, V> rebuildfive(Node<K, V> parent, Rotate side) { //case5 if (side == Rotate.R) { // rotate Left Node<K, V> leftChild = new RedNode<>(parent.left().getKey(), parent.left().getValue(), parent.left().left(), parent.left().right().left()); Node<K, V> rightChild = parent.left().right().right(); @@ -260,7 +260,7 @@ } } - protected Node rebuildsix(Node<K, V> parent, Rotate side) { //case6 + protected Node<K, V> 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<>(parent.right().right().getKey(), parent.right().right().getValue(), parent.right().right().left(), parent.right().right().right()); @@ -283,11 +283,11 @@ abstract boolean isRed(); - public abstract Node replaceNode(Node<K, V> parent) throws RotateParent; + public abstract Node<K, V> replaceNode(Node<K, V> parent, Comparator ctr) throws RotateParent; protected abstract Node deleteNode() throws RotateParent; @Test // test method - protected abstract int checkDepth (int count , int minCount); + protected abstract int checkDepth(int count, int minCount); }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/RedNode.java Wed Aug 05 00:36:57 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/RedNode.java Tue Aug 11 08:16:07 2015 +0900 @@ -2,9 +2,9 @@ import org.junit.Test; -/** - * Created by e115731 on 15/03/25. - */ +import java.util.Comparator; + + public class RedNode<K, V> extends Node<K, V> { @@ -20,7 +20,7 @@ @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); + return new RedNode<>(key, value, left, right); } @Override @@ -29,9 +29,8 @@ } @Override - protected Node deleteNode() throws RotateParent { - EmptyNode emptyNode = new EmptyNode(this.getKey()); - return emptyNode; + protected Node<K, V> deleteNode() throws RotateParent { + return new EmptyNode<>(this.getKey()); } @Override @@ -57,8 +56,8 @@ } @Override - public Node replaceNode(Node<K, V> parent) throws RotateParent { - Node<K, V> newNode = null; + public Node<K, V> replaceNode(Node<K, V> parent, Comparator ctr) throws RotateParent { + Node<K, V> newNode; if (!this.left().isNotEmpty() && !this.right().isNotEmpty()) { //自身を削除する return deleteNode(); } else if (this.left().isNotEmpty() && !this.right().isNotEmpty()) { //左の部分木を昇格させる @@ -74,26 +73,26 @@ while (cur.right().isNotEmpty()) { cur = cur.right(); } - Node leftSubTreeNode = null; + Node<K, V> leftSubTreeNode; if (this.left().right().isNotEmpty()) { try { - leftSubTreeNode = this.left().deleteSubTreeMaxNode(null,Rotate.L); + leftSubTreeNode = this.left().deleteSubTreeMaxNode(null, ctr, 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); + return leftSubTreeNode.deleteBalance(newParent, ctr); } } else { try { - leftSubTreeNode = this.left().replaceNode(this); + leftSubTreeNode = this.left().replaceNode(this, ctr); 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); + Node<K, V> node = e.getParent(); + Node<K, V> newParent = createNode(this.left().getKey(), this.left().getValue(), node, this.right()); + return node.deleteBalance(newParent, ctr); } } @@ -103,11 +102,10 @@ @Override @Test - protected int checkDepth(int count,int minCount) { // test method - count ++; + 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/jungle/data/treemap/Rotate.java Wed Aug 05 00:36:57 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/Rotate.java Tue Aug 11 08:16:07 2015 +0900 @@ -1,8 +1,5 @@ package jp.ac.u_ryukyu.ie.cr.jungle.data.treemap; -/** - * Created by e115731 on 15/03/23. - */ public enum Rotate { - R, L, RL, LR, N; + R, L, RL, LR, N }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/RotateParent.java Wed Aug 05 00:36:57 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/RotateParent.java Tue Aug 11 08:16:07 2015 +0900 @@ -1,15 +1,13 @@ package jp.ac.u_ryukyu.ie.cr.jungle.data.treemap; -/** - * Created by e115731 on 15/04/17. - */ public class RotateParent extends Exception { - Node parent ; + + Node parent; public RotateParent(Node node) { this.parent = node; } - public Node getParent(){ + public Node getParent() { return parent; } }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/TreeMap.java Wed Aug 05 00:36:57 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/TreeMap.java Tue Aug 11 08:16:07 2015 +0900 @@ -3,48 +3,52 @@ import org.junit.Test; +import java.util.Comparator; import java.util.Iterator; import java.util.Optional; import java.util.Stack; - public class TreeMap<K, V> { final Node<K, V> root; - final int size; + Comparator comparator; public TreeMap() { this.root = new EmptyNode<>(); - this.size = 0; + this.comparator = new DefaultComparator<K>(); } + public TreeMap(Comparator comparator) { + this.root = new EmptyNode<>(); + this.comparator = comparator; + } + + public TreeMap(Node<K, V> root, Comparator comparator) { + this.root = root; + this.comparator = comparator; + } 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, comparator); } - public Optional<V> get(final K key) { - return root.get(key); - } - - public TreeMap put(K key, V value) { + public TreeMap<K, V> 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); + return new TreeMap<>(newRoot, this.comparator); } - Node<K, V> newEntry = root.put((Comparable<? super K>) key, value); + Node<K, V> newEntry = root.put(key, value, comparator); Node<K, V> newRoot = new BlackNode<>(newEntry.getKey(), newEntry.getValue(), newEntry.left(), newEntry.right()); - return new TreeMap<>(newRoot, 0); + return new TreeMap<>(newRoot, this.comparator); } @@ -54,23 +58,24 @@ public TreeMap<K, V> delete(K key) { - Node node = null; + Node<K, V> node = null; try { - node = root.delete((Comparable<? super K>) key, null, Rotate.N); + node = root.delete(key, null, comparator, Rotate.N); } catch (RotateParent rotateParent) { + System.out.println("no call this scope"); } 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); + return new TreeMap<>(new EmptyNode<>(), this.comparator); + Node<K, V> newRoot = new BlackNode<>(node.getKey(), node.getValue(), node.left(), node.right()); + return new TreeMap<>(newRoot, this.comparator); } public Iterator<K> keys() { return new Iterator<K>() { - Stack<Node> nodeStack = new Stack<>(); - Node currentNode = root; + Stack<Node<K, V>> nodeStack = new Stack<>(); + Node<K, V> currentNode = root; @Override public boolean hasNext() { @@ -79,13 +84,13 @@ @Override public K next() { - K key = (K) currentNode.getKey(); + K key = currentNode.getKey(); if (currentNode.left().isNotEmpty()) { nodeStack.push(currentNode); currentNode = currentNode.left(); return key; - } else if (currentNode.right().isNotEmpty()) { + } else if (currentNode.right().isNotEmpty()) { currentNode = currentNode.right(); return key; } else if (nodeStack.isEmpty()) {
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/query/PathNodeIterator.java Wed Aug 05 00:36:57 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/query/PathNodeIterator.java Tue Aug 11 08:16:07 2015 +0900 @@ -12,8 +12,8 @@ TreeNode node; int childNumber; private TreeNodeChildren children; - private Stack<TreeNode> nodeStack = new Stack<TreeNode>(); - private Stack<Integer> searchStack = new Stack<Integer>(); + private Stack<TreeNode> nodeStack = new Stack<>(); + private Stack<Integer> searchStack = new Stack<>(); /* * get queryIndexCondition from query
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/store/impl/logger/DefaultTreeOperationLog.java Wed Aug 05 00:36:57 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/store/impl/logger/DefaultTreeOperationLog.java Tue Aug 11 08:16:07 2015 +0900 @@ -36,7 +36,7 @@ public TreeOperationLog add(NodePath _p, NodeOperation _op) { TreeOperation op = new DefaultTreeOperation(_p,_op); - List<TreeOperation> newList = new List(op); + List<TreeOperation> newList = new List<>(op); Iterable<TreeOperation> concat = Iterables.concat(list,newList); return new DefaultTreeOperationLog(concat,size + 1);
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/store/index/ParentIndex.java Wed Aug 05 00:36:57 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/store/index/ParentIndex.java Tue Aug 11 08:16:07 2015 +0900 @@ -11,7 +11,7 @@ private TreeMap<TreeNode, TreeNode> parentIndex; public ParentIndex() { - parentIndex = new TreeMap(); + parentIndex = new TreeMap<>(); } public boolean isEmpty(){
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/test/AbstractTreeMapThread.java Wed Aug 05 00:36:57 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/test/AbstractTreeMapThread.java Tue Aug 11 08:16:07 2015 +0900 @@ -1,8 +1,5 @@ package jp.ac.u_ryukyu.ie.cr.jungle.test; -/** - * Created by e115731 on 15/03/17. - */ public abstract class AbstractTreeMapThread extends Thread{ public abstract void set(boolean flag); public abstract long getFindCount();
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/test/DataBaseBenchMark.java Wed Aug 05 00:36:57 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/test/DataBaseBenchMark.java Tue Aug 11 08:16:07 2015 +0900 @@ -19,11 +19,7 @@ import javax.xml.parsers.ParserConfigurationException; import java.io.*; import java.nio.ByteBuffer; -import java.util.Random; -/** - * Created by e115731 on 15/03/20. - */ public class DataBaseBenchMark { public static void main(String[] args) throws InterruptedException, IOException, ParserConfigurationException, SAXException { @@ -53,13 +49,12 @@ coll.insertOne(new Document("key",String.valueOf(i))); } coll.createIndex(new Document("key", 1)); - //coll.dropIndex(new Document("key", 1)); for (final Document index : coll.listIndexes()) { System.out.println(index.toJson()); } File file = new File("./time/" + args[0] + args[1] + "Time"); PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(file))); - DataBaseBenchMarkThread readThread[] = null; + DataBaseBenchMarkThread readThread[]; for (int THREAD_COUNT = 1; THREAD_COUNT <= cpuNum; THREAD_COUNT++) { readThread = new DataBaseBenchMarkThread[THREAD_COUNT]; for (int count = 0; THREAD_COUNT > count; count++) { @@ -87,10 +82,10 @@ } private static void jungleBench(String[] args, int cpuNum) throws IOException, InterruptedException { - JungleTree tree = createJungleTree(cpuNum); + JungleTree tree = createJungleTree(); File file = new File("./time/" + args[0] + args[0] + "Time"); PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(file))); - DataBaseBenchMarkThread readThread[] = null; + DataBaseBenchMarkThread readThread[]; for (int THREAD_COUNT = 1; THREAD_COUNT <= cpuNum; THREAD_COUNT++) { readThread = new DataBaseBenchMarkThread[THREAD_COUNT]; @@ -107,7 +102,7 @@ } System.out.println("StartThread"); Thread.sleep(1000); - if (args[1].equals("write")) { + if (writeThread != null) { writeThread.set(false); writeThread.get(); } @@ -126,9 +121,8 @@ pw.close(); } - private static JungleTree createJungleTree(int cpuNum) { + private static JungleTree createJungleTree() { Jungle jungle = new DefaultJungle(null, "hoge", new DefaultTreeEditor(new DefaultTraverser())); - JungleTree trees[] = new JungleTree[cpuNum]; JungleTree tree = jungle.createNewTree("tree"); JungleTreeEditor editor = tree.getTreeEditor(); editor = editor.putAttribute(new DefaultNodePath(), "key", ByteBuffer.wrap(String.valueOf(0).getBytes())).b(); @@ -137,7 +131,6 @@ System.out.println("success faild"); System.exit(1); } - trees[0] = tree; return tree; } @@ -145,7 +138,6 @@ public static JungleTreeEditor createTree(int deep, NodePath path, JungleTreeEditor editor) { - Random rnd = new Random(); String value1 = String.valueOf(nodeNum); nodeNum++; String value2 = String.valueOf(nodeNum);
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/test/DataBaseBenchMarkThread.java Wed Aug 05 00:36:57 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/test/DataBaseBenchMarkThread.java Tue Aug 11 08:16:07 2015 +0900 @@ -1,8 +1,6 @@ package jp.ac.u_ryukyu.ie.cr.jungle.test; -/** - * Created by e115731 on 15/03/17. - */ + public abstract class DataBaseBenchMarkThread extends Thread{ public abstract long getFindCount(); public abstract void set(boolean flag);
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/test/JungleWriteThread.java Wed Aug 05 00:36:57 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/test/JungleWriteThread.java Tue Aug 11 08:16:07 2015 +0900 @@ -6,9 +6,7 @@ import java.nio.ByteBuffer; -/** - * Created by e115731 on 15/04/18. - */ + public class JungleWriteThread extends Thread { JungleTree tree; @@ -27,8 +25,6 @@ System.out.println("writeCount = " + writeCount); } - ; - @Override public void run() { while (loop) {
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/test/TatsukiTreeMapGetThread.java Wed Aug 05 00:36:57 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/test/TatsukiTreeMapGetThread.java Tue Aug 11 08:16:07 2015 +0900 @@ -5,15 +5,12 @@ import java.util.Optional; -/** - * Created by e115731 on 15/03/17. - */ public class TatsukiTreeMapGetThread extends AbstractTreeMapThread { TreeMap<Long, String> map; private long findCount; boolean loop = true; - public TatsukiTreeMapGetThread(TreeMap map) { + public TatsukiTreeMapGetThread(TreeMap<Long,String> map) { this.map = map; }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/test/TreeMapBenchMark.java Wed Aug 05 00:36:57 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/test/TreeMapBenchMark.java Tue Aug 11 08:16:07 2015 +0900 @@ -22,33 +22,38 @@ PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(file))); - AbstractTreeMapThread readThread[] = null; + AbstractTreeMapThread readThread[]; for (int THREAD_COUNT = 1; THREAD_COUNT <= cpuNum; THREAD_COUNT++) { readThread = new AbstractTreeMapThread[THREAD_COUNT]; - if (args[0].equals("util")) { - java.util.TreeMap map = new java.util.TreeMap(); - for (long count = 0; count < 1000; count++) { - map.put(count, String.valueOf(count)); - } + switch (args[0]) { + case "util": { + java.util.TreeMap<Long, String> map = new java.util.TreeMap<>(); + for (long count = 0; count < 1000; count++) { + map.put(count, String.valueOf(count)); + } - for (int count = 0; THREAD_COUNT > count; count++) { - readThread[count] = new UtilTreeMapGetThread(map); + for (int count = 0; THREAD_COUNT > count; count++) { + readThread[count] = new UtilTreeMapGetThread(map); + } + break; } - } else if (args[0].equals("tatsuki")) { - TreeMap map = new TreeMap(); - for (long count = 0; count < 1000; count++) { - map = map.put(count, String.valueOf(count)); - } + case "tatsuki": { + TreeMap<Long,String> map = new TreeMap<>(); + for (long count = 0; count < 1000; count++) { + map = map.put(count, String.valueOf(count)); + } - for (int count = 0; THREAD_COUNT > count; count++) { - readThread[count] = new TatsukiTreeMapGetThread(map); + for (int count = 0; THREAD_COUNT > count; count++) { + readThread[count] = new TatsukiTreeMapGetThread(map); + } + break; } - } else { - System.out.println("not allow args"); - System.exit(0); + default: + System.out.println("not allow args"); + System.exit(0); } for (int count = 0; THREAD_COUNT > count; count++) {
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/test/UtilTreeMapGetThread.java Wed Aug 05 00:36:57 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/test/UtilTreeMapGetThread.java Tue Aug 11 08:16:07 2015 +0900 @@ -2,15 +2,13 @@ import java.util.TreeMap; -/** - * Created by e115731 on 15/04/18. - */ + public class UtilTreeMapGetThread extends AbstractTreeMapThread { TreeMap<Long, String> map; private long findCount; boolean loop = true; - public UtilTreeMapGetThread(TreeMap map) { + public UtilTreeMapGetThread(TreeMap<Long, String> map) { this.map = map; } @@ -28,7 +26,7 @@ @Override public void run() { while (loop) { - for (long count = 0 ; count < 1000; count++) { + for (long count = 0; count < 1000; count++) { String value = map.get(count); if (value == null) System.out.println("error");
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/test/findMongoAttributeThread.java Wed Aug 05 00:36:57 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/test/findMongoAttributeThread.java Tue Aug 11 08:16:07 2015 +0900 @@ -5,9 +5,7 @@ import com.mongodb.client.MongoCursor; import org.bson.Document; -/** - * Created by e115731 on 15/04/30. - */ + public class findMongoAttributeThread extends DataBaseBenchMarkThread { private long findCount; boolean loop = true;
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/test/findTreeAttributeThread.java Wed Aug 05 00:36:57 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/test/findTreeAttributeThread.java Tue Aug 11 08:16:07 2015 +0900 @@ -5,9 +5,7 @@ import jp.ac.u_ryukyu.ie.cr.jungle.traverser.InterfaceTraverser; import java.util.Iterator; -/** - * Created by e115731 on 15/03/20. - */ + public class findTreeAttributeThread extends DataBaseBenchMarkThread { JungleTree tree;
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/DefaultJungleTreeEditor.java Wed Aug 05 00:36:57 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/DefaultJungleTreeEditor.java Tue Aug 11 08:16:07 2015 +0900 @@ -1,30 +1,25 @@ package jp.ac.u_ryukyu.ie.cr.jungle.transaction; -import java.nio.ByteBuffer; - import jp.ac.u_ryukyu.ie.cr.jungle.JungleTreeEditor; import jp.ac.u_ryukyu.ie.cr.jungle.store.NodePath; import jp.ac.u_ryukyu.ie.cr.jungle.store.TreeEditor; import jp.ac.u_ryukyu.ie.cr.jungle.store.impl.DefaultNodePath; -import jp.ac.u_ryukyu.ie.cr.jungle.store.impl.logger.TreeOperationLog; -import jp.ac.u_ryukyu.ie.cr.jungle.store.operations.DefaultTreeOperation; -import jp.ac.u_ryukyu.ie.cr.jungle.store.operations.NodeOperation; -import jp.ac.u_ryukyu.ie.cr.jungle.store.trasnformer.AppendChildAt; -import jp.ac.u_ryukyu.ie.cr.jungle.store.trasnformer.PutAttribute; -import jp.ac.u_ryukyu.ie.cr.jungle.util.Error; import jp.ac.u_ryukyu.ie.cr.jungle.store.impl.TreeNode; import jp.ac.u_ryukyu.ie.cr.jungle.store.impl.logger.DefaultTreeOperationLog; import jp.ac.u_ryukyu.ie.cr.jungle.store.impl.logger.LoggingNode; import jp.ac.u_ryukyu.ie.cr.jungle.store.impl.logger.OperationLog; +import jp.ac.u_ryukyu.ie.cr.jungle.store.impl.logger.TreeOperationLog; +import jp.ac.u_ryukyu.ie.cr.jungle.store.operations.DefaultTreeOperation; +import jp.ac.u_ryukyu.ie.cr.jungle.store.operations.NodeOperation; import jp.ac.u_ryukyu.ie.cr.jungle.store.operations.TreeOperation; -import jp.ac.u_ryukyu.ie.cr.jungle.store.trasnformer.replaceRootNodeAt; -import jp.ac.u_ryukyu.ie.cr.jungle.store.trasnformer.DeleteAttribute; -import jp.ac.u_ryukyu.ie.cr.jungle.store.trasnformer.DeleteChildAt; -import jp.ac.u_ryukyu.ie.cr.jungle.store.trasnformer.NodeEditor; +import jp.ac.u_ryukyu.ie.cr.jungle.store.trasnformer.*; import jp.ac.u_ryukyu.ie.cr.jungle.util.DefaultEither; import jp.ac.u_ryukyu.ie.cr.jungle.util.Either; +import jp.ac.u_ryukyu.ie.cr.jungle.util.Error; import jp.ac.u_ryukyu.ie.cr.jungle.util.IterableConverter; +import java.nio.ByteBuffer; + public class DefaultJungleTreeEditor implements JungleTreeEditor { private final TransactionManager txManager; @@ -66,7 +61,7 @@ } }; - Iterable<TreeOperation> iterable = new IterableConverter<TreeOperation,NodeOperation>(newLog,converter); + Iterable<TreeOperation> iterable = new IterableConverter<>(newLog,converter); DefaultTreeOperationLog treeOperationLog = new DefaultTreeOperationLog(iterable,newLog.length()); TreeOperationLog newTreeOpLog = log.append(treeOperationLog);
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/DefaultTreeNode.java Wed Aug 05 00:36:57 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/DefaultTreeNode.java Tue Aug 11 08:16:07 2015 +0900 @@ -16,10 +16,10 @@ private TreeMap<String, ByteBuffer> attrs; final String nodeId = new VMID().toString(); - private static final List<TreeNode> NIL_LIST = new List(); + private static final List<TreeNode> NIL_LIST = new List<>(); public DefaultTreeNode() { - this(NIL_LIST, new TreeMap()); + this(NIL_LIST, new TreeMap<>()); } public DefaultTreeNode(List<TreeNode> _children, TreeMap<String, ByteBuffer> _attrs) { @@ -48,7 +48,7 @@ @Override public Either<Error, TreeNode> appendRootNode() { - TreeNodeChildren newRootChildren = new DefaultTreeNodeChildren(NIL_LIST, new TreeMap()); + TreeNodeChildren newRootChildren = new DefaultTreeNodeChildren(NIL_LIST, new TreeMap<>()); Either<jp.ac.u_ryukyu.ie.cr.jungle.util.Error, TreeNode> either = newRootChildren.addNewChildAt(0,this); return either; }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/traverser/InterfaceTraverser.java Wed Aug 05 00:36:57 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/traverser/InterfaceTraverser.java Tue Aug 11 08:16:07 2015 +0900 @@ -193,60 +193,58 @@ // }; // } // } + private TreeNode nextmatch(TreeNode node, Query query) { + if (query.condition(node)) + return node; + return null; + } + + public Iterator<TreeNode> find(final Query query, final String key, String searchValue) { - Iterator<TreeNode> nodeIterator = get(key, searchValue); - if (nodeIterator != null && useIndex) { - return nodeIterator; + Iterator<TreeNode> nodeIterator; + if (key != null && searchValue != null && useIndex) { + nodeIterator = get(key, searchValue); + ; } else { + nodeIterator = new PathNodeIterator(root); + } - final PathNodeIterator itNode = new PathNodeIterator(root); - return new Iterator<TreeNode>() { + TreeNode firstMatchNode = null; + for (; nodeIterator.hasNext(); ) { + firstMatchNode = nextmatch(nodeIterator.next(), query); + if (firstMatchNode != null) + break; + } - private TreeNode matchNode = nextmatch(itNode); + final TreeNode finalFirstMatchNode = firstMatchNode; - private TreeNode nextmatch(PathNodeIterator itNode) { + return new Iterator<TreeNode>() { + + TreeNode matchNode = finalFirstMatchNode; - for (; itNode.hasNext(); ) { - TreeNode targetNode = itNode.next(); - String value = targetNode.getAttributes().getString(key); - if (useIndex) { - if (value != null) - ; - // index = index.set(key, value, targetNode); - } - if (parentUpdateFlag) - ; - // parentIndex = parentIndex.set(targetNode); - if (query.condition(targetNode)) - return targetNode; - } - if (useIndex || parentUpdateFlag) - commit(); - return null; + @Override + public boolean hasNext() { + if (matchNode == null) { + return false; } + return true; + } - @Override - public boolean hasNext() { - if (matchNode == null) { - return false; - } - return true; + @Override + public TreeNode next() { + TreeNode currentPair = matchNode; + for (; nodeIterator.hasNext(); ) { + matchNode = nextmatch(nodeIterator.next(), query); } + return currentPair; + } - @Override - public TreeNode next() { - TreeNode currentPair = matchNode; - matchNode = nextmatch(itNode); - return currentPair; - } + @Override + public void remove() { + } - @Override - public void remove() { - } - - }; - } + }; } // public Iterator<TreeNode> findAll(final Query query, final String key) {
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/jungle/traverse/InterfaceTraverserTest.java Tue Aug 11 08:16:07 2015 +0900 @@ -0,0 +1,128 @@ +package jp.ac.u_ryukyu.ie.cr.jungle.traverse; + +import jp.ac.u_ryukyu.ie.cr.jungle.DefaultJungle; +import jp.ac.u_ryukyu.ie.cr.jungle.Jungle; +import jp.ac.u_ryukyu.ie.cr.jungle.JungleTree; +import jp.ac.u_ryukyu.ie.cr.jungle.JungleTreeEditor; +import jp.ac.u_ryukyu.ie.cr.jungle.persistent.NullJournal; +import jp.ac.u_ryukyu.ie.cr.jungle.store.NodePath; +import jp.ac.u_ryukyu.ie.cr.jungle.store.impl.DefaultNodePath; +import jp.ac.u_ryukyu.ie.cr.jungle.store.impl.DefaultTreeEditor; +import jp.ac.u_ryukyu.ie.cr.jungle.store.impl.TreeNode; +import jp.ac.u_ryukyu.ie.cr.jungle.transaction.DefaultTreeNode; +import jp.ac.u_ryukyu.ie.cr.jungle.traverser.DefaultTraverser; +import jp.ac.u_ryukyu.ie.cr.jungle.traverser.InterfaceTraverser; +import jp.ac.u_ryukyu.ie.cr.jungle.util.Either; +import jp.ac.u_ryukyu.ie.cr.jungle.util.Error; +import junit.framework.Assert; +import org.junit.Test; + +import java.nio.ByteBuffer; +import java.util.Iterator; + +/** + * Created by e115731 on 15/08/11. + */ +public class InterfaceTraverserTest { + @Test + public void InterfaseTraverserTest() { + Jungle jungle = new DefaultJungle(new NullJournal(), "hoge", new DefaultTreeEditor(new DefaultTraverser())); + jungle.createNewTree("TestTree"); + JungleTree tree = jungle.getTreeByName("TestTree"); + JungleTreeEditor editor = tree.getTreeEditor(); + editor = createTree(editor, 0, 3, new DefaultNodePath()); + Either<Error, JungleTreeEditor> either = editor.success(); + if (either.isA()) + Assert.fail(); + InterfaceTraverser traverser = tree.getTraverser(true); + + { + Iterator<TreeNode> iterator = traverser.find((TreeNode node) -> { // no index find + String value = node.getAttributes().getString(key); + if (value == null) + return false; + if (value.equals("<1,1,-1>")) + return true; + return false; + }, null, null); + + Assert.assertTrue(iterator.hasNext()); + TreeNode node = iterator.next(); + String value = node.getAttributes().getString("KEY"); + Assert.assertEquals("<1,1,-1>", value); + } + + { + Iterator<TreeNode> iterator = traverser.find((TreeNode node) -> { // no index find + String value = node.getAttributes().getString(key); + if (value == null) + return false; + if (value.equals("no exist value")) + return true; + return false; + }, null, null); + + Assert.assertFalse(iterator.hasNext()); + } + + { + Iterator<TreeNode> iterator = traverser.find((TreeNode node) -> { // use index find + String value = node.getAttributes().getString(key); + if (value == null) + return false; + if (value.equals("<1,1,-1>")) + return true; + return false; + }, indexKey, "<1,1,-1>+ index"); + + Assert.assertTrue(iterator.hasNext()); + TreeNode node = iterator.next(); + String value = node.getAttributes().getString("KEY"); + Assert.assertEquals("<1,1,-1>", value); + } + + { + Iterator<TreeNode> iterator = traverser.find((TreeNode node) -> { // use index find + String value = node.getAttributes().getString(key); + if (value == null) + return false; + if (value.equals("<1,1,-1>")) + return true; + return false; + }, indexKey, "no exist index value"); + + Assert.assertFalse(iterator.hasNext()); + } + } + + public static String key = "KEY"; + public static String indexKey = "INDEXKEY"; + public static DefaultTreeNode factory = new DefaultTreeNode(); + + public JungleTreeEditor createTree(JungleTreeEditor editor, int _curY, int _maxHeight, NodePath path) { + + if (_curY == _maxHeight) { + return editor; + } + for (int i = 0; i < 3; i++) { + + Either<Error, JungleTreeEditor> either = editor.addNewChildAt(path, i); + if (either.isA()) + Assert.fail(); + editor = either.b(); + String value = path.add(i).toString(); + either = editor.putAttribute(path.add(i), key, ByteBuffer.wrap(value.getBytes())); + if (either.isA()) + Assert.fail(); + editor = either.b(); + String value2 = value + "+ index"; + either = editor.putAttribute(path.add(i), indexKey, ByteBuffer.wrap(value2.getBytes())); + if (either.isA()) + Assert.fail(); + editor = either.b(); + editor = createTree(editor, _curY + 1, _maxHeight, path.add(i)); + } + return editor; + } + +}
--- a/src/test/java/jp/ac/u_ryukyu/ie/cr/jungle/traverse/TraverserTest.java Wed Aug 05 00:36:57 2015 +0900 +++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/jungle/traverse/TraverserTest.java Tue Aug 11 08:16:07 2015 +0900 @@ -21,7 +21,7 @@ { int maxHeight = 3; - TreeNode root = createTree(0,0,maxHeight,new DefaultNodePath()); + TreeNode root = createTree(0,maxHeight,new DefaultNodePath()); Traverser traverser = new DefaultTraverser(); List<DefaultNodePath> paths = generatePathPattern(new DefaultNodePath(),0,maxHeight); @@ -70,10 +70,9 @@ } public static String key = "KEY"; - public static ByteBuffer value = ByteBuffer.wrap(key.getBytes()); public static DefaultTreeNode factory = new DefaultTreeNode(); - public TreeNode createTree(int _curX,int _curY,int _maxHeight,NodePath _address) + public TreeNode createTree(int _curY,int _maxHeight,NodePath _address) { TreeNode parent = factory.createNewNode(); Either<Error,TreeNode> either = parent.getAttributes().put(key,ByteBuffer.wrap(_address.toString().getBytes())); @@ -87,7 +86,7 @@ } for(int i = 0;i < _curY + 1;i ++){ - TreeNode ch = createTree(i,_curY + 1,_maxHeight,_address.add(i)); + TreeNode ch = createTree(_curY + 1,_maxHeight,_address.add(i)); either = parent.getChildren().addNewChildAt(i,ch); if(either.isA()){ Assert.fail();
--- a/src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/treemap/TreeMapDelete.java Wed Aug 05 00:36:57 2015 +0900 +++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/treemap/TreeMapDelete.java Tue Aug 11 08:16:07 2015 +0900 @@ -7,29 +7,25 @@ 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(); + TreeMap<Integer, Integer> map = new TreeMap<>(); for (int count = 1; count < 1000; count++) { map = map.put(count, count); - // map.checkDepth(); + map.checkDepth(); } - ArrayList<Integer> list = new ArrayList(); + 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(); + map = map.delete(num); + map.checkDepth(); } System.out.println("end"); }
--- a/src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/treemap/TreeMapTest.java Wed Aug 05 00:36:57 2015 +0900 +++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/treemap/TreeMapTest.java Tue Aug 11 08:16:07 2015 +0900 @@ -1,21 +1,16 @@ package jp.ac.u_ryukyu.ie.cr.tatsuki.treemap; import jp.ac.u_ryukyu.ie.cr.jungle.data.treemap.TreeMap; +import org.junit.Test; 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--) { + + @Test + public void TreeMapTest() { + TreeMap<Integer, Integer> map = new TreeMap<>(); + for (int count = 100; count > -10; count--) { map = map.put(count, count); map.checkDepth(); System.out.println("-------------------------------------------");