Re: Another bug in TreeMap

[Eric Blake]

Yes, it is a bug. I posted the following patch (since I was responsible
for this bug in the first place, several months ago):

2002-05-02  Eric Blake  <address@hidden>

        * java/util/TreeMap.java (remove): Fix improper return value.
        * THANKYOU: Add Xuan Baldauf for spotting this.

Index: java/util/TreeMap.java
===================================================================
RCS file: /cvsroot/classpath/classpath/java/util/TreeMap.java,v
retrieving revision 1.19
diff -u -r1.19 TreeMap.java
--- java/util/TreeMap.java      20 Feb 2002 23:56:46 -0000      1.19
+++ java/util/TreeMap.java      3 May 2002 04:17:37 -0000
@@ -623,8 +623,10 @@
     Node n = getNode(key);
     if (n == nil)
       return null;
+    // Note: removeNode can alter the contents of n, so save value now.
+    Object result = n.value;
     removeNode(n);
-    return n.value;
+    return result;
   }

   /**
@@ -1768,7 +1770,7 @@
             SubMap.this.clear();
           }
         };
-      return this.keys;
+      return this.values;
     }
   } // class SubMap
 } // class TreeMap

By the way, Brian, you forgot to commit TreeMap, so I did it for you.

Brian Jones wrote:
> 
> Xuan Baldauf <address@hidden> writes:
> 
> >
> > In case the node to be removed has two children, within
> > removeNode(), new keys and values will be swapped into the
> > node the which is about to be removed. After removeNode()
> > finished, remove() returns the value variable of that node.
> > Because it was changed previously within removeNode(), the
> > wrong value (from the swapped in node rather than from the
> > original node) is returned. This is a bug.
> 
> I'm pretty sure that without dusting off my data structures book I
> couldn't patch this properly.  I'm unsure what the point is of setting
> the key/value of node in the else statement with that "node" being
> deleted from the tree.

The swap of the node contents saves effort over the additional pointer
manipulation that is otherwise required, at the expense of modifying the
node so that it is no longer valid in remove().  In short, the code
deletes a leaf node, after moving its contents to the original node, so
that the net result is deleting the contents of the original node.

-- 
This signature intentionally left boring.

Eric Blake             address@hidden
  BYU student, free software programmer