Return-Path: Delivered-To: apmail-directory-commits-archive@www.apache.org Received: (qmail 197 invoked from network); 25 May 2008 11:29:17 -0000 Received: from hermes.apache.org (HELO mail.apache.org) (140.211.11.2) by minotaur.apache.org with SMTP; 25 May 2008 11:29:17 -0000 Received: (qmail 87749 invoked by uid 500); 25 May 2008 11:29:19 -0000 Delivered-To: apmail-directory-commits-archive@directory.apache.org Received: (qmail 87702 invoked by uid 500); 25 May 2008 11:29:18 -0000 Mailing-List: contact commits-help@directory.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@directory.apache.org Delivered-To: mailing list commits@directory.apache.org Received: (qmail 87693 invoked by uid 99); 25 May 2008 11:29:18 -0000 Received: from athena.apache.org (HELO athena.apache.org) (140.211.11.136) by apache.org (qpsmtpd/0.29) with ESMTP; Sun, 25 May 2008 04:29:18 -0700 X-ASF-Spam-Status: No, hits=-2000.0 required=10.0 tests=ALL_TRUSTED X-Spam-Check-By: apache.org Received: from [140.211.11.4] (HELO eris.apache.org) (140.211.11.4) by apache.org (qpsmtpd/0.29) with ESMTP; Sun, 25 May 2008 11:28:39 +0000 Received: by eris.apache.org (Postfix, from userid 65534) id 3561323889F1; Sun, 25 May 2008 04:28:56 -0700 (PDT) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit 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 -0000 To: commits@directory.apache.org From: kayyagari@apache.org X-Mailer: svnmailer-1.0.8 Message-Id: <20080525112856.3561323889F1@eris.apache.org> X-Virus-Checked: Checked by ClamAV on apache.org 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() {