Mercurial > hg > Members > tatsuki > TreeMap

changeset 24:77681539d7c1 default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add get keys , keys return TreeMap key Iterator
author tatsuki
date Wed, 06 May 2015 06:16:05 +0900
parents 60f35f5c6982
children
files TreeMap.iml src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Color.java src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/DeleteRebuildFlag.java src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Entry.java src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Node.java src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/TreeMap.java src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Tuple.java src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/test/TreeMapDelete.java src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/test/TreeNodeIteratorTest.java
diffstat 9 files changed, 109 insertions(+), 111 deletions(-) [+]
line wrap: on
line diff
--- /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 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<module external.linked.project.id="TreeMap" external.linked.project.path="$MODULE_DIR$" external.root.project.path="$MODULE_DIR$" external.system.id="GRADLE" external.system.module.group="" external.system.module.version="1.0" type="JAVA_MODULE" version="4">
+  <component name="NewModuleRootManager" inherit-compiler-output="false">
+    <output url="file://$MODULE_DIR$/build/classes/main" />
+    <output-test url="file://$MODULE_DIR$/build/classes/test" />
+    <exclude-output />
+    <content url="file://$MODULE_DIR$">
+      <sourceFolder url="file://$MODULE_DIR$/src/main/java" isTestSource="false" />
+      <sourceFolder url="file://$MODULE_DIR$/src/test/java" isTestSource="true" />
+      <sourceFolder url="file://$MODULE_DIR$/src/main/resources" type="java-resource" />
+      <sourceFolder url="file://$MODULE_DIR$/src/test/resources" type="java-test-resource" />
+      <excludeFolder url="file://$MODULE_DIR$/.gradle" />
+      <excludeFolder url="file://$MODULE_DIR$/build" />
+    </content>
+    <orderEntry type="inheritedJdk" />
+    <orderEntry type="sourceFolder" forTests="false" />
+    <orderEntry type="library" exported="" name="Gradle: junit:junit:4.7" level="project" />
+    <orderEntry type="library" exported="" name="Gradle: org.apache.maven.surefire:surefire-junit4:2.13" level="project" />
+    <orderEntry type="library" exported="" name="Gradle: org.apache.maven.surefire:surefire-api:2.13" level="project" />
+  </component>
+</module>
\ No newline at end of file
--- 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;
-}
--- 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
-}
--- 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<K, V> {
-    private K key;
-    private V value;
-    private Entry<K, V> right;
-    private Entry<K, V> 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<K, V> left, Entry<K, V> 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;
-    }
-
-}
--- 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<K, V> right;
     protected Node<K, V> 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());
 
     }
 
--- 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<V> get(final K key) {return root.get(key);}
+    public Optional<V> get(final K key) {
+        return root.get(key);
+    }
 
     public TreeMap put(K key, V value) {
 
@@ -40,7 +44,7 @@
             return new TreeMap<K, V>(newRoot, size + 1);
         }
 
-        Node<K, V> newEntry = root.put((Comparable<? super K>)key, value);
+        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);
     }
@@ -51,19 +55,60 @@
     }
 
 
-    public TreeMap<K,V> delete(K key) throws RotateParent {
-       Node node = root.delete((Comparable<? super K>)key, null,Rotate.N);
+    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);
+            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);
+    public void checkDepth() {
+        root.checkDepth(0, 0);
         System.out.println("-----------------------------------");
     }
 }
--- 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;
-    }
-
-
-}
--- 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<Integer, Integer> 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<Integer> list = new ArrayList();
-        for (int i = 1; i < 3000; i++) {
+        for (int i = 1; i < 1000; i++) {
             list.add(i);
         }
         Collections.shuffle(list);
--- /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<Integer, Integer> map = new TreeMap();
+        for (int attributeMaxCount = 10; attributeMaxCount < 1000; attributeMaxCount = attributeMaxCount + 10) {
+            for (int count = 0; count < attributeMaxCount; count++) { //insertData
+                map = map.put(count, count);
+            }
+            Iterator<Integer> it = map.keys();
+            int iteratorCount = 0;
+            while (it.hasNext()) { // count return iterator Attribute Count
+                iteratorCount++;
+                System.out.println(it.next());
+            }
+            Assert.assertTrue(iteratorCount == attributeMaxCount); // check
+        }
+
+    }
+}