directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From kayyag...@apache.org
Subject svn commit: r659962 - in /directory/apacheds/branches/bigbang/core-avl/src: main/java/org/apache/directory/server/core/avltree/AvlTree.java test/java/org/apache/directory/server/core/avltree/AvlTreeTest.java
Date Sun, 25 May 2008 11:28:55 GMT
Author: kayyagari
Date: Sun May 25 04:28:55 2008
New Revision: 659962

URL: http://svn.apache.org/viewvc?rev=659962&view=rev
Log:
AvlTree - fixed another issue with preserving child nodes while deleting non-leaf node
AvlTreeTest - added a test case for the above fix

Modified:
    directory/apacheds/branches/bigbang/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTree.java
    directory/apacheds/branches/bigbang/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeTest.java

Modified: directory/apacheds/branches/bigbang/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTree.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/bigbang/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTree.java?rev=659962&r1=659961&r2=659962&view=diff
==============================================================================
--- directory/apacheds/branches/bigbang/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTree.java
(original)
+++ directory/apacheds/branches/bigbang/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTree.java
Sun May 25 04:28:55 2008
@@ -248,13 +248,13 @@
                 }
                 else
                 {
-                    detachNodes( y, leftTreePath.get( 0 ) );
+                    detachNodes( y, leftTreePath.remove( 0 ) );
                 }
                 
                 leftTreePath.addAll( treePath );
                 treePath = leftTreePath;
                 
-                y.right = temp.right;
+                y.right = temp.right; // assign the right here left will be assigned in replaceNode()
 
                 if( temp == root )
                 {
@@ -277,13 +277,13 @@
                 }
                 else
                 {
-                    detachNodes( y, rightTreePath.get( 0 ) );
+                    detachNodes( y, rightTreePath.remove( 0 ) );
                 }
                 
                 rightTreePath.addAll( treePath );
                 treePath = rightTreePath;
                 
-                y.right = temp.right;
+                y.right = temp.right; // assign the right here left will be assigned in replaceNode()
                 
                 if( temp == root )
                 {
@@ -549,6 +549,7 @@
         {
             if( root.left == node )
             {
+                System.out.println("IT IS ROOT");
                 root.left = temp;
             }
             // no need to check for right node
@@ -590,6 +591,8 @@
     {
         if( parentNode != null )
         {
+            replaceNode.left = deleteNode.left;
+            
             if( deleteNode == parentNode.left )
             {
                 parentNode.left = replaceNode;

Modified: directory/apacheds/branches/bigbang/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeTest.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/bigbang/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeTest.java?rev=659962&r1=659961&r2=659962&view=diff
==============================================================================
--- directory/apacheds/branches/bigbang/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeTest.java
(original)
+++ directory/apacheds/branches/bigbang/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeTest.java
Sun May 25 04:28:55 2008
@@ -388,6 +388,22 @@
         assertEquals( 26, ( int ) tree.find( 14 ).right.key );
     }
 
+
+    @Test
+    public void testRemoveInRightSubtree()
+    {
+        int[] keys = { 8, 4, 13, 6, 15, 7, 10, 5, 14, 2, 11, 3, 9, 1 }; // order is important
to produce the expected tree
+        
+        for( int key:keys )
+        {
+            tree.insert( key );
+        }
+
+        tree.remove( 13 );
+
+        assertEquals( 11, ( int ) tree.find( 8 ).right.key );
+    }
+
     
     private String getLinkedText() 
     {



Mime
View raw message