# HG changeset patch
# User tatsuki
# Date 1430860565 -32400
# Node ID 77681539d7c1bde23d86efefe246135a09c6bf1f
# Parent 60f35f5c6982693895823b5451a19310c7851dcb
add get keys , keys return TreeMap key Iterator
diff -r 60f35f5c6982 -r 77681539d7c1 TreeMap.iml
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/TreeMap.iml Wed May 06 06:16:05 2015 +0900
@@ -0,0 +1,21 @@
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
\ No newline at end of file
diff -r 60f35f5c6982 -r 77681539d7c1 src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Color.java
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Color.java Wed Apr 29 16:55:23 2015 +0900
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,9 +0,0 @@
-package jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap;
-
-/**
- * Created by e115731 on 15/03/23.
- */
-public class Color {
- public static final boolean RED = false;
- public static final boolean BLACK = true;
-}
diff -r 60f35f5c6982 -r 77681539d7c1 src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/DeleteRebuildFlag.java
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/DeleteRebuildFlag.java Wed Apr 29 16:55:23 2015 +0900
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,8 +0,0 @@
-package jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap;
-
-/**
- * Created by e115731 on 15/04/05.
- */
-public enum DeleteRebuildFlag {
- one,two,three,four,five,six,allBlack
-}
diff -r 60f35f5c6982 -r 77681539d7c1 src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Entry.java
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Entry.java Wed Apr 29 16:55:23 2015 +0900
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,55 +0,0 @@
-package jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap;
-
-/**
- * Created by e115731 on 15/03/23.
- */
-public class Entry {
- private K key;
- private V value;
- private Entry right;
- private Entry left;
- private boolean color = Color.RED;
-
- public Entry(boolean color,K key, V value) {
- this.key = key;
- this.value = value;
- this.right = null;
- this.left = null;
- }
-
- public Entry(Entry e) {
- this.key = (K) e.getKey();
- this.value = (V) e.getValue();
- this.right = e.right();
- this.left = e.left;
- }
-
- public Entry(boolean color,K key, V value, Entry left, Entry right) {
- this.key = key;
- this.value = value;
- this.right = right;
- this.left = left;
- this.color = color;
- }
-
- public Entry left() {
- return left;
- }
-
- public Entry right() {
- return right;
- }
-
- public K getKey() {
- return key;
- }
-
- public V getValue() {
- return value;
- }
-
- public boolean getColor() {
- return color;
- }
-
-}
diff -r 60f35f5c6982 -r 77681539d7c1 src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Node.java
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Node.java Wed Apr 29 16:55:23 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Node.java Wed May 06 06:16:05 2015 +0900
@@ -14,7 +14,6 @@
protected V value;
protected Node right;
protected Node left;
- protected boolean rebuildFlag = false;
public Node(K key, V value) {
this.key = key;
@@ -32,8 +31,8 @@
return left;
}
- public int compare(Comparable super K> parentKey) {
- return parentKey.compareTo(getKey());
+ public int compare(Comparable super K> compareKey) {
+ return compareKey.compareTo(getKey());
}
diff -r 60f35f5c6982 -r 77681539d7c1 src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/TreeMap.java
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/TreeMap.java Wed Apr 29 16:55:23 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/TreeMap.java Wed May 06 06:16:05 2015 +0900
@@ -3,7 +3,9 @@
import org.junit.Test;
+import java.util.Iterator;
import java.util.Optional;
+import java.util.Stack;
/**
@@ -28,7 +30,9 @@
this.size = size;
}
- public Optional get(final K key) {return root.get(key);}
+ public Optional get(final K key) {
+ return root.get(key);
+ }
public TreeMap put(K key, V value) {
@@ -40,7 +44,7 @@
return new TreeMap(newRoot, size + 1);
}
- Node newEntry = root.put((Comparable super K>)key, value);
+ Node newEntry = root.put((Comparable super K>) key, value);
Node newRoot = new BlackNode(newEntry.getKey(), newEntry.getValue(), newEntry.left(), newEntry.right());
return new TreeMap(newRoot, 0);
}
@@ -51,19 +55,60 @@
}
- public TreeMap delete(K key) throws RotateParent {
- Node node = root.delete((Comparable super K>)key, null,Rotate.N);
+ public TreeMap 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);
+ 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 keys() {
+ return new Iterator() {
+ Stack 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);
+ public void checkDepth() {
+ root.checkDepth(0, 0);
System.out.println("-----------------------------------");
}
}
diff -r 60f35f5c6982 -r 77681539d7c1 src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Tuple.java
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Tuple.java Wed Apr 29 16:55:23 2015 +0900
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,25 +0,0 @@
-package jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap;
-
-/**
- * Created by e115731 on 15/04/18.
- */
-public class Tuple {
-
- Node node;
- boolean rebuildFlag;
-
- public Tuple(Node node, boolean rebuildFlag){
- this.node = node;
- this.rebuildFlag = rebuildFlag;
- }
-
- public Node getNode(){
- return node;
- }
-
- public boolean getRebuildFlag(){
- return rebuildFlag;
- }
-
-
-}
diff -r 60f35f5c6982 -r 77681539d7c1 src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/test/TreeMapDelete.java
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/test/TreeMapDelete.java Wed Apr 29 16:55:23 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/test/TreeMapDelete.java Wed May 06 06:16:05 2015 +0900
@@ -15,13 +15,13 @@
@Test
public static void main(String args[]) throws RotateParent {
TreeMap map = new TreeMap();
- for (int count = 1; count < 3000; count++) {
+ for (int count = 1; count < 1000; count++) {
map = map.put(count, count);
map.checkDepth();
}
ArrayList list = new ArrayList();
- for (int i = 1; i < 3000; i++) {
+ for (int i = 1; i < 1000; i++) {
list.add(i);
}
Collections.shuffle(list);
diff -r 60f35f5c6982 -r 77681539d7c1 src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/test/TreeNodeIteratorTest.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/test/TreeNodeIteratorTest.java Wed May 06 06:16:05 2015 +0900
@@ -0,0 +1,30 @@
+package jp.ac.u_ryukyu.ie.cr.tatsuki.test;
+
+import jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.TreeMap;
+import junit.framework.Assert;
+import org.junit.Test;
+
+import java.util.Iterator;
+
+/**
+ * Created by e115731 on 15/05/06.
+ */
+public class TreeNodeIteratorTest {
+ @Test
+ public void getKeyTest() {
+ TreeMap map = new TreeMap();
+ for (int attributeMaxCount = 10; attributeMaxCount < 1000; attributeMaxCount = attributeMaxCount + 10) {
+ for (int count = 0; count < attributeMaxCount; count++) { //insertData
+ map = map.put(count, count);
+ }
+ Iterator it = map.keys();
+ int iteratorCount = 0;
+ while (it.hasNext()) { // count return iterator Attribute Count
+ iteratorCount++;
+ System.out.println(it.next());
+ }
+ Assert.assertTrue(iteratorCount == attributeMaxCount); // check
+ }
+
+ }
+}