Author: [email protected]
Date: Fri May 15 14:55:56 2009
New Revision: 5400
Modified:
trunk/user/super/com/google/gwt/emul/java/util/TreeMap.java
trunk/user/test/com/google/gwt/emultest/java/util/TreeMapStringStringTest.java
Log:
Fix for issue 3423: TreeMap.remove(..) should not modify the contents of
the entry being removed. Now, the web mode behavior matches the hosted mode
behavior.
Patch by: amitmanjhi
Review by: jat
Modified: trunk/user/super/com/google/gwt/emul/java/util/TreeMap.java
==============================================================================
--- trunk/user/super/com/google/gwt/emul/java/util/TreeMap.java (original)
+++ trunk/user/super/com/google/gwt/emul/java/util/TreeMap.java Fri May 15
14:55:56 2009
@@ -960,8 +960,23 @@
state.found = true;
state.value = found.value;
}
- found.key = node.key;
- found.value = node.value;
+ /**
+ * put the "node" values in "found" (the node with key K) and
cut "node"
+ * out. However, we do not want to corrupt "found" -- issue 3423. So
+ * create a new node "newNode" to replace the "found" node.
+ *
+ * TODO: (jat's suggestion) Consider using rebalance to move the
deleted
+ * node to a leaf to avoid the extra traversal in replaceNode.
+ */
+ if (node != found) {
+ Node<K, V> newNode = new Node<K, V>(node.key, node.value);
+ replaceNode(head, found, newNode);
+ if (parent == found) {
+ parent = newNode;
+ }
+ }
+
+ // cut "node" out
parent.child[parent.child[RIGHT] == node ? RIGHT : LEFT] =
node.child[node.child[LEFT] == null
? RIGHT : LEFT];
size--;
@@ -975,6 +990,28 @@
}
/**
+ * replace 'node' with 'newNode' in the tree rooted at 'head'. Could have
+ * avoided this traversal if each node maintained a parent pointer.
+ */
+ private void replaceNode(Node<K, V> head, Node<K, V> node, Node<K, V>
newNode) {
+ Node<K, V> parent = head;
+ int direction = (parent.key == null || cmp.compare(node.key,
parent.key) > 0)
+ ? RIGHT : LEFT; // parent.key == null handles the fake root node
+ while (parent.child[direction] != node) {
+ parent = parent.child[direction];
+ assert parent != null;
+ direction = cmp.compare(node.key, parent.key) > 0 ? RIGHT : LEFT;
+ }
+ // replace node with newNode
+ parent.child[direction] = newNode;
+ newNode.isRed = node.isRed;
+ newNode.child[LEFT] = node.child[LEFT];
+ newNode.child[RIGHT] = node.child[RIGHT];
+ node.child[LEFT] = null;
+ node.child[RIGHT] = null;
+ }
+
+ /**
* Perform a double rotation, first rotating the child which will become
the
* root in the opposite direction, then rotating the root in the
specified
* direction.
@@ -1019,4 +1056,5 @@
save.isRed = false;
return save;
}
+
}
Modified:
trunk/user/test/com/google/gwt/emultest/java/util/TreeMapStringStringTest.java
==============================================================================
---
trunk/user/test/com/google/gwt/emultest/java/util/TreeMapStringStringTest.java
(original)
+++
trunk/user/test/com/google/gwt/emultest/java/util/TreeMapStringStringTest.java
Fri May 15 14:55:56 2009
@@ -21,6 +21,7 @@
import java.util.Set;
import java.util.SortedMap;
import java.util.TreeMap;
+import java.util.Map.Entry;
/**
* Tests <code>TreeMap</code> with Strings and the natural comparator.
@@ -120,6 +121,23 @@
assertEquals("lastKey", "dd", subMap.lastKey());
}
+ // checks for compatibility with real Jre's EntrySet.remove(): issue 3423
+ public void testTreeMapEntrySetRemove() {
+ Map<String, String> treeMap = new TreeMap<String, String>();
+ treeMap.put("foo", "fooValue");
+ treeMap.put("bar", "barValue");
+
+ Iterator<Entry<String, String>> entryIterator =
+treeMap.entrySet().iterator();
+ Entry<String, String> entry = entryIterator.next();
+ assertEquals("entry: " + entry, "bar", entry.getKey());
+
+ entry = entryIterator.next();
+ assertEquals("before remove(): " + entry, "foo", entry.getKey());
+ entryIterator.remove();
+ assertEquals("after remove(): " + entry, "foo", entry.getKey());
+ }
+
// checks for compatibility with real Jre's Entry.toString(): issue 3422
public void testTreeMapEntryToString() {
Map<String, String> treeMap = new TreeMap<String, String>();
@@ -127,6 +145,19 @@
assertEquals("bar=barValue",
treeMap.entrySet().iterator().next().toString());
+ }
+
+ public void testTreeMapRemove() {
+ Map<String, String> treeMap = new TreeMap<String, String>();
+ treeMap.put("foo", "fooValue");
+ treeMap.put("bar", "barValue");
+
+ Iterator<Entry<String, String>> entryIterator =
treeMap.entrySet().iterator();
+ entryIterator.next();
+ Entry<String, String> secondEntry = entryIterator.next();
+ assertEquals("before removeKey: ", "foo", secondEntry.getKey());
+ treeMap.remove("foo");
+ assertEquals("after removeKey: ", "foo", secondEntry.getKey());
}
@Override
--~--~---------~--~----~------------~-------~--~----~
http://groups.google.com/group/Google-Web-Toolkit-Contributors
-~----------~----~----~----~------~----~------~--~---
