directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From kayyag...@apache.org
Subject svn commit: r761375 - in /directory/apacheds/branches/ldif-partition/core-avl/src: main/java/org/apache/directory/server/core/avltree/AvlTreeMapImpl.java test/java/org/apache/directory/server/core/avltree/AvlTreeMapTest.java
Date Thu, 02 Apr 2009 18:50:40 GMT
Author: kayyagari
Date: Thu Apr  2 18:50:39 2009
New Revision: 761375

URL: http://svn.apache.org/viewvc?rev=761375&view=rev
Log:
o fixed the remove(K,V) operation
o implemented remove(K) operation
o moved the logic to do a balance after delete from remove(K,V) to a new method balanceNodesAfterRemove()
o renamed the node 'temp' to be deleted to 'delNode'
o added few more test cases

Modified:
    directory/apacheds/branches/ldif-partition/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMapImpl.java
    directory/apacheds/branches/ldif-partition/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMapTest.java

Modified: directory/apacheds/branches/ldif-partition/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMapImpl.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/ldif-partition/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMapImpl.java?rev=761375&r1=761374&r2=761375&view=diff
==============================================================================
--- directory/apacheds/branches/ldif-partition/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMapImpl.java
(original)
+++ directory/apacheds/branches/ldif-partition/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMapImpl.java
Thu Apr  2 18:50:39 2009
@@ -261,9 +261,41 @@
     }
     
     
+    /**
+     * removes a node associated with a key
+     * The entire node will be removed irrespective of whether duplicate keys
+     * are enabled or not
+     */
     public SingletonOrOrderedSet<V> remove( K key )
     {
-        throw new NotImplementedException();
+        if( key == null )
+        {
+            throw new IllegalArgumentException( "key cannot be null" );
+        }
+        
+        LinkedAvlMapNode<K,V> temp = null;
+        
+        List<LinkedAvlMapNode<K,V>> treePath = new ArrayList<LinkedAvlMapNode<K,V>>();
+        
+        treePath = find( key, root, treePath);
+        
+        if( treePath == null )
+        {
+            return null;
+        }
+        
+        temp = treePath.remove( 0 );
+       
+        if( temp.isLeaf() && ( temp == root ) )
+        {
+            root = null;
+        }
+        else
+        {
+            balanceNodesAfterRemove( treePath, temp );
+        }
+        
+       return temp.value;
     }
     
     
@@ -272,8 +304,12 @@
      */
     public V remove( K key, V value )
     {
+        if( key == null || value == null )
+        {
+            throw new IllegalArgumentException( "key or value cannot be null" );
+        }
+        
         LinkedAvlMapNode<K,V> temp = null;
-        LinkedAvlMapNode<K,V> y = null;
         
         List<LinkedAvlMapNode<K,V>> treePath = new ArrayList<LinkedAvlMapNode<K,V>>();
         
@@ -287,7 +323,7 @@
         temp = treePath.remove( 0 );
 
         // check if the value matches
-        if( value != null )
+        if( allowDuplicates )
         {
             if( temp.value.isOrderedSet() )
             {
@@ -302,7 +338,7 @@
                 // further down in this function
                 if( ( removedVal != null ) && ! dupsTree.isEmpty() )
                 {
-                    return value;//no need to balance
+                    return removedVal;//no need to balance
                 }
             }
             else
@@ -313,33 +349,61 @@
                 }
             }
         }
-        
-        // remove from the doubly linked
-        removeFromList( temp );        
-        
-        if( temp.isLeaf() )
+
+        if( temp.isLeaf() && ( temp == root ) )
         {
-            if( temp == root )
+            if( allowDuplicates )
             {
-              root = null;
-              return key;
+                if( temp.value.isSingleton() || temp.value.getOrderedSet().isEmpty() )
+                {
+                    root = null;
+                }
+            }
+            else // if dups are not allowed set root to null
+            {
+                root = null;
             }
             
+            return value;
+        }
+
+       balanceNodesAfterRemove( treePath, temp );
+        
+       return value;
+    }
+
+    
+    /**
+     * changes the order of nodes after a delete operation and then 
+     * balances the tree
+     *
+     * @param treePath the path traversed to find the node temp 
+     * @param delNode the node to be deleted
+     */
+    private void balanceNodesAfterRemove( List<LinkedAvlMapNode<K,V>> treePath,
LinkedAvlMapNode<K,V> delNode )
+    {
+        LinkedAvlMapNode<K,V> y = null;
+        
+        // remove from the doubly linked
+        removeFromList( delNode );        
+
+        if( delNode.isLeaf() )
+        {
             if( !treePath.isEmpty() )
             {
-                detachNodes( temp, treePath.get( 0 ) );
+                detachNodes( delNode, treePath.get( 0 ) );
             }
         }
         else
         {
-            if( temp.left != null )
+            if( delNode.left != null )
             {
-                List<LinkedAvlMapNode<K,V>> leftTreePath = findMax( temp.left
);
+                List<LinkedAvlMapNode<K,V>> leftTreePath = findMax( delNode.left
);
                 y = leftTreePath.remove( 0 );
                 
                 if( leftTreePath.isEmpty() ) // y is the left child of root and y is a leaf
                 {
-                    detachNodes( y, temp );
+                    detachNodes( y, delNode );
                 }
                 else
                 {
@@ -349,26 +413,26 @@
                 leftTreePath.addAll( treePath );
                 treePath = leftTreePath;
                 
-                y.right = temp.right; // assign the right here left will be assigned in replaceNode()
+                y.right = delNode.right; // assign the right here left will be assigned in
replaceNode()
 
-                if( temp == root )
+                if( delNode == root )
                 {
-                    y.left = temp.left;
+                    y.left = delNode.left;
                     root = y;
                 }
                 else
                 {
-                    replaceNode( temp, y, treePath.get( 0 ) );
+                    replaceNode( delNode, y, treePath.get( 0 ) );
                 }
             }
-            else if( temp.right != null )
+            else if( delNode.right != null )
             {
-                List<LinkedAvlMapNode<K,V>> rightTreePath = findMin( temp.right
);
+                List<LinkedAvlMapNode<K,V>> rightTreePath = findMin( delNode.right
);
                 y = rightTreePath.remove( 0 );
                 
                 if( rightTreePath.isEmpty() )
                 {
-                    detachNodes( y, temp ); // y is the right child of root and y is a leaf
+                    detachNodes( y, delNode ); // y is the right child of root and y is a
leaf
                 }
                 else
                 {
@@ -378,24 +442,22 @@
                 rightTreePath.addAll( treePath );
                 treePath = rightTreePath;
                 
-                y.right = temp.right; // assign the right here left will be assigned in replaceNode()
+                y.right = delNode.right; // assign the right here left will be assigned in
replaceNode()
                 
-                if( temp == root )
+                if( delNode == root )
                 {
-                    y.right = temp.right;
+                    y.right = delNode.right;
                     root = y;
                 }
                 else
                 {
-                    replaceNode( temp, y, treePath.get( 0 ) );
+                    replaceNode( delNode, y, treePath.get( 0 ) );
                 }
             }
         }
        
        treePath.add( 0, y ); // y can be null but getBalance returns 0 so np
        balance( treePath );
-       
-       return key;
     }
     
     

Modified: directory/apacheds/branches/ldif-partition/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMapTest.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/ldif-partition/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMapTest.java?rev=761375&r1=761374&r2=761375&view=diff
==============================================================================
--- directory/apacheds/branches/ldif-partition/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMapTest.java
(original)
+++ directory/apacheds/branches/ldif-partition/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMapTest.java
Thu Apr  2 18:50:39 2009
@@ -93,7 +93,7 @@
         assertNotNull( tree.getFirst() );
         assertNotNull( tree.getLast() );
         assertTrue( tree.getFirst().getKey().equals( 7 ) );
-        assertTrue( tree.getFirst().getValue().equals( 1 ) );
+        assertTrue( tree.getFirst().getValue().getSingleton().equals( 1 ) );
         
         tree.insert( 10, 2 );
         assertEquals( 2, tree.getSize() );
@@ -132,8 +132,8 @@
     {
         assertNull( tree.insert( 3, 1 ) );
         assertFalse( tree.isEmpty() );
-
-        assertTrue( 3 == tree.insert( 3, 1 ) );// should be ignored
+        
+        assertTrue( 1 == tree.insert( 3, 1 ) );
         assertTrue( 1 == tree.getSize() );
 
         assertNotNull( tree.getFirst() );
@@ -183,7 +183,7 @@
             tree.printTree();
         }
         
-        assertTrue( 3 == tree.insert( 3, 1 ) );// should be ignored
+        assertTrue( 1 == tree.insert( 3, 1 ) );// should be ignored
         assertTrue( 1 == tree.getSize() );
         
         LinkedAvlMapNode node = tree.find( 3 );
@@ -191,7 +191,7 @@
      
         assertTrue( node.value.getOrderedSet().getClass() ==  AvlTreeImpl.class );
         
-        AvlTree dupsTree = ( AvlTree ) node.value;
+        AvlTree dupsTree = ( ( SingletonOrOrderedSet ) node.value ).getOrderedSet();
         assertEquals( 3, dupsTree.getSize() );
     }
     
@@ -211,7 +211,7 @@
         assertTrue( 3 == tree.getRoot().key );
         
         assertNull( tree.remove( 777, 0 ) );// key not present
-        assertTrue( 3 == tree.remove( 3, null ) );
+        assertTrue( 3 == tree.remove( 3, 3 ) );
         assertTrue(tree.isEmpty());
         
         tree.insert( 37, 37 );
@@ -266,7 +266,7 @@
         assertEquals("1,3", getInorderForm());
         assertEquals( 2, tree.getSize() );
         
-        tree.remove( 3, null );
+        tree.remove( 3, 3 );
         assertEquals("1", getInorderForm());
         assertEquals( 1, tree.getSize() );
         
@@ -285,6 +285,80 @@
     }
     
     
+    /**
+     * checks the root node value(s) when duplicates are allowed and
+     * only single node(size one) is present 
+     */
+    @Test
+    public void testRemoveDuplictesOnRoot()
+    {
+        assertTrue( tree.isDupsAllowed() );
+        tree.insert( 3, 4 );
+        tree.insert( 3, 5 );
+        
+        assertEquals( 1, tree.getSize() );
+        
+        assertTrue( 4 == tree.remove( 3, 4 ) );
+        assertNotNull( tree.getRoot() ); // still root should be not null
+        assertEquals( 1, tree.getSize() );
+        
+        assertTrue( 5 == tree.remove( 3, 5 ) );
+        assertNull( tree.getRoot() );
+        
+        tree.insert( 1, 1 );
+        tree.insert( 1, 2 );
+        tree.insert( 1, 3 );
+        assertNotNull( tree.getRoot() );
+        assertEquals( 1, tree.getSize() );
+        
+        tree.remove( 1 );
+        assertNull( tree.getRoot() );
+    }
+    
+    
+    @Test
+    public void testRemoveWithoutDupKeys()
+    {
+        tree = new AvlTreeMapImpl<Integer, Integer>( comparator, comparator, false
);
+        assertFalse( tree.isDupsAllowed() );
+        
+        tree.insert( 3, 4 );
+        assertTrue( 4 == tree.insert( 3, 5 ) );
+        assertEquals( 1, tree.getSize() );
+        
+        assertNotNull( tree.remove( 3, 5 ) );
+        assertNull( tree.getRoot() );
+    }
+    
+    
+    @Test
+    public void testRemoveWithKeyOnly()
+    {
+        assertTrue( tree.isDupsAllowed() );
+        tree.insert( 3, 1 );
+        tree.insert( 3, 2 );
+        tree.insert( 4, 4 );
+        
+        SingletonOrOrderedSet<Integer> set = tree.remove( 3 );
+        assertNotNull( set );
+        assertNull( tree.find( 3 ) );
+        
+        AvlTree<Integer> valueTree = set.getOrderedSet();
+        assertNotNull( valueTree );
+        assertTrue( 2 == valueTree.getSize() );
+        assertNotNull( valueTree.find( 1 ) );
+        assertNotNull( valueTree.find( 2 ) );
+        
+        tree = new AvlTreeMapImpl<Integer, Integer>( comparator, comparator, false
);
+        tree.insert( 7, 4 );
+        
+        set = tree.remove( 7 );
+        assertNotNull( set );
+        assertNull( tree.find( 7 ) );
+        assertTrue( 4 == set.getSingleton() );
+    }
+
+    
     @Test
     public void testSingleRightRotation()
     {



Mime
View raw message