directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From kayyag...@apache.org
Subject svn commit: r659876 - 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 Sat, 24 May 2008 21:20:11 GMT
Author: kayyagari
Date: Sat May 24 14:20:11 2008
New Revision: 659876

URL: http://svn.apache.org/viewvc?rev=659876&view=rev
Log:
AvlTree - fixed an issue with tree rotation after deleting root node 
          fixed another issue with detaching nodes after deleting root node
AvlTreeTest -added test cases for testing above fixes

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=659876&r1=659875&r2=659876&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
Sat May 24 14:20:11 2008
@@ -541,6 +541,18 @@
                 parentNode.right = temp;
             }
         }
+        /*
+         when the 'parentNode' param is null then the node under rotation is a child of ROOT.
+         Most likely this condition executes when the root node is deleted and balancing
is required.
+         */
+        else if( root != null )
+        {
+            if( root.left == node )
+            {
+                root.left = temp;
+            }
+            // no need to check for right node
+        }
 	}
 		
 
@@ -560,7 +572,7 @@
 	        }
 	        else if( node == parentNode.right )
 	        {
-	            parentNode.right = null;
+	            parentNode.right = node.left;
 	        }
 	    }
 	}

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=659876&r1=659875&r2=659876&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
Sat May 24 14:20:11 2008
@@ -353,6 +353,41 @@
         assertTrue( 7 == tree.getKeys().size() );
     }
     
+    @Test
+    public void testTreeRoationAtLeftChildAfterDeletingRoot()
+    {
+        int[] keys = { 86, 110, 122, 2, 134, 26, 14, 182 }; // order is important to produce
the expected tree
+        int[] expectedKeys = { 2, 14, 26, 86, 122, 134, 182 };
+        
+        for( int key:keys )
+        {
+            tree.insert( key );
+        }
+        
+        tree.remove( 110 );
+
+        for ( int key : expectedKeys )
+        {
+            assertNotNull( "Should find " + key, tree.find( key ) );
+        }
+    }
+    
+
+    @Test
+    public void testDetachNodesAtLeftChildAfterDeletingRoot()
+    {
+        int[] keys = { 110, 122, 2, 134, 86, 14, 26, 182 }; // order is important to produce
the expected tree
+        
+        for( int key:keys )
+        {
+            tree.insert( key );
+        }
+
+        tree.remove( 110 );
+        
+        assertEquals( 26, ( int ) tree.find( 14 ).right.key );
+    }
+
     
     private String getLinkedText() 
     {



Mime
View raw message