directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From akaras...@apache.org
Subject svn commit: r631460 - in /directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src: main/java/org/apache/directory/server/core/avltree/ test/java/org/apache/directory/server/core/avltree/
Date Wed, 27 Feb 2008 01:43:59 GMT
Author: akarasulu
Date: Tue Feb 26 17:43:57 2008
New Revision: 631460

URL: http://svn.apache.org/viewvc?rev=631460&view=rev
Log:
DIRSERVER-1138: Applying patches contributed by Kiran Ayagari for avl tree implementation

Modified:
    directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/avltree/AVLTree.java
    directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/avltree/LinkedAvlNode.java
    directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/core/avltree/AVLTreeTest.java

Modified: directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/avltree/AVLTree.java
URL: http://svn.apache.org/viewvc/directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/avltree/AVLTree.java?rev=631460&r1=631459&r2=631460&view=diff
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/avltree/AVLTree.java
(original)
+++ directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/avltree/AVLTree.java
Tue Feb 26 17:43:57 2008
@@ -24,7 +24,6 @@
 import java.util.Comparator;
 import java.util.List;
 
-
 /**
  * An AVL tree implementation
  *
@@ -40,6 +39,12 @@
 	/** The Comparator used for comparing the keys */
 	private Comparator<K> comparator;
 
+	/** node representing the start of the doubly linked list formed with the tree nodes */
+	private LinkedAvlNode<K> first;
+	
+	/** node representing the end of the doubly linked list formed with the tree nodes */
+    private LinkedAvlNode<K> last;
+    
 	/**
 	 * Creates a new instance of AVLTree.
 	 *
@@ -65,10 +70,12 @@
 	    if( root == null )
 	    {
 	      root = new LinkedAvlNode<K>( key );
+	      first = root;
 	      return;
 	    }
 	    
 	    node = new LinkedAvlNode<K>( key );
+	    
 	    temp = root;
 	    
 	    List<LinkedAvlNode<K>> treePath = new ArrayList<LinkedAvlNode<K>>();
@@ -103,11 +110,78 @@
 	    {
 	        parent.setRight( node );
 	    }
-	 
-	    treePath.add( 0, node );
+	    
+        insertInList( node, parent, c );
+        
+        treePath.add( 0, node );
 	    balance(treePath);
 	}
 	
+	private void removeFromList(LinkedAvlNode<K> node)
+	{
+        if( node.next == null && node.previous == null ) // should happen in case
of tree having single node
+        {
+            first = last = null;
+        }
+        else if( node.next == null ) // last node
+        {
+            node.previous.next = null;
+            last = node.previous;
+        }
+        else if( node.previous == null ) // first node
+        {
+            node.next.previous = null;
+            first = node.next;
+        }
+        else // somewhere in middle
+        {
+            node.previous.next = node.next;
+            node.next.previous = node.previous;
+        }
+        
+	}
+	
+	private void insertInList(LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode,
int pos)
+	{
+	 // add to the linked list
+
+        if( pos < 0 )
+        {
+            if( last == null )
+            {
+              last = parentNode;  
+            }
+            
+            if( parentNode.previous == null )
+            {
+                first = node;
+            }
+            else
+            {
+                parentNode.previous.next = node ;
+                node.previous = parentNode.previous;
+            }
+            
+            node.next = parentNode;
+            parentNode.previous = node;
+        }
+        else if( pos > 0 )
+        {
+            if( parentNode.next == null )
+            {
+                last = node;
+            }
+            else
+            {
+                parentNode.next.previous = node;
+                node.next = parentNode.next;
+            }
+            node.previous = parentNode;
+            parentNode.next = node;
+         }
+        
+        // end of adding to the linked list  
+	}
 	
 	/**
      * Removes the LinkedAvlNode present in the tree with the given key value
@@ -130,6 +204,9 @@
         }
         
         temp = treePath.remove( 0 );
+
+        // remove from the doubly linked
+        removeFromList(temp);        
         
         if( temp.isLeaf() )
         {
@@ -205,7 +282,8 @@
                 }
             }
         }
-        
+       
+       treePath.add( 0, y ); // y can be null but getBalance returns 0 so np
        balance( treePath );
     }
     
@@ -238,7 +316,9 @@
             if( node != root )
             {
                 if( treePath.indexOf( node ) < ( size - 1 ) )
+                {
                     parentNode = treePath.get( treePath.indexOf( node ) + 1 );
+                }
             }
 
 	        if( balFactor > 1 )
@@ -271,6 +351,20 @@
 	}
 	
 
+	
+	/**
+     * 
+     * Find a LinkedAvlNode with the given key value in the tree.
+     *
+     * @param key the key to find
+     * @return the list of traversed LinkedAvlNode.
+     */
+    public LinkedAvlNode<K> find( K key )
+    {
+        return find( key, root);
+    }
+    
+    
 	/**
      * Tests if the tree is logically empty.
      * 
@@ -281,7 +375,35 @@
       return root == null;   
     }
 
+    public int getSize()
+    {
+      if( root.isLeaf() )
+      {
+          return 1;
+      }
+      
+      return last.getIndex() + 1;
+    }
+    
     
+    public void setRoot( LinkedAvlNode<K> root )
+    {
+        this.root = root;
+    }
+
+    
+    
+    public void setFirst( LinkedAvlNode<K> first )
+    {
+        this.first = first;
+    }
+
+    public void setLast( LinkedAvlNode<K> last )
+    {
+        this.last = last;
+    }
+
+
     public LinkedAvlNode<K> getRoot()
     {
         return root;
@@ -311,7 +433,17 @@
 
     //-------------- private methods ----------
     
-	/**
+	public LinkedAvlNode<K> getFirst()
+    {
+        return first;
+    }
+
+    public LinkedAvlNode<K> getLast()
+    {
+        return last;
+    }
+
+    /**
 	 * Rotate the node left side once.
 	 *
 	 * @param node the LinkedAvlNode to be rotated
@@ -332,11 +464,11 @@
         }
         else if( parentNode != null )
         {
-            if( parentNode.left != null )
+            if( parentNode.left == node )
             {
                 parentNode.left = temp;
             }
-            else
+            else if( parentNode.right == node )
             {
                 parentNode.right = temp;
             }
@@ -365,11 +497,11 @@
         }
         else if( parentNode != null )
         {
-            if( parentNode.left != null )
+            if( parentNode.left == node )
             {
                 parentNode.left = temp;
             }
-            else
+            else if( parentNode.right == node )
             {
                 parentNode.right = temp;
             }
@@ -422,6 +554,28 @@
         }
     }
     
+    private LinkedAvlNode<K> find( K key, LinkedAvlNode<K> startNode)
+    {
+        int c;
+        
+        if( startNode == null )
+        {
+            return null;
+        }
+        
+        c = comparator.compare( key, startNode.key );
+        
+        if( c > 0 )
+        {
+            return find( key, startNode.right );
+        }
+        else if( c < 0 )
+        {
+            return find( key, startNode.left );
+        }
+        
+        return startNode;
+    }
     
     /**
      * 
@@ -539,6 +693,11 @@
      */
 	private int getBalance( LinkedAvlNode<K> node )
 	{
+	    if( node == null)
+	    {
+	        return 0;
+	    }
+	    
 	    int rh = ( node.right == null ? 0 : node.right.getHeight() );
 	    int lh = ( node.left == null ? 0 : node.left.getHeight() );
 	    

Modified: directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/avltree/LinkedAvlNode.java
URL: http://svn.apache.org/viewvc/directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/avltree/LinkedAvlNode.java?rev=631460&r1=631459&r2=631460&view=diff
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/avltree/LinkedAvlNode.java
(original)
+++ directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/avltree/LinkedAvlNode.java
Tue Feb 26 17:43:57 2008
@@ -64,6 +64,7 @@
 		return right;
 	}
 
+	
 	public T getKey() {
 		return key;
 	}
@@ -73,16 +74,30 @@
 		return ( right == null && left == null );
 	}
 	
+	
 	public int getDepth() {
 		return depth;
 	}
 
+	
 	public void setDepth( int depth ) {
 		this.depth = depth;
 	}
 
 	
-	public int getHeight()
+	public void setNext( LinkedAvlNode<T> next )
+    {
+        this.next = next;
+    }
+
+
+    public void setPrevious( LinkedAvlNode<T> previous )
+    {
+        this.previous = previous;
+    }
+
+
+    public int getHeight()
     {
 	    if(right == null && left == null)
 	    {
@@ -95,6 +110,15 @@
         return 1 + Math.max( lh, rh );
     }
 
+	public int getIndex()
+	{
+	    if( previous == null )
+	    {
+	        return 0;
+	    }
+	    
+	  return previous.getIndex() + 1;
+	}
 
     @Override
 	public String toString() {

Modified: directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/core/avltree/AVLTreeTest.java
URL: http://svn.apache.org/viewvc/directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/core/avltree/AVLTreeTest.java?rev=631460&r1=631459&r2=631460&view=diff
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/core/avltree/AVLTreeTest.java
(original)
+++ directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/core/avltree/AVLTreeTest.java
Tue Feb 26 17:43:57 2008
@@ -19,9 +19,13 @@
  */
 package org.apache.directory.server.core.avltree;
 
+import static junit.framework.Assert.assertEquals;
 import static org.junit.Assert.assertEquals;
-import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.assertNotSame;
 import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertNull;
 
 import java.util.ArrayList;
 import java.util.Comparator;
@@ -62,6 +66,8 @@
       
       tree.remove( 97 ); // remove a non-existing key
       assertTrue( tree.isEmpty() );
+      
+      tree.printTree();
     }
     
     
@@ -70,9 +76,36 @@
     {
         tree.insert( 3 );
         assertFalse( tree.isEmpty() );
+        assertTrue( 1 == tree.getSize() );
         
         tree.insert( 3 );// should be ignored
-        assertEquals( 1, tree.getRoot().getHeight() );
+        assertTrue( 1 == tree.getRoot().getHeight() );
+
+        assertNotNull( tree.getFirst() );
+        assertNull( tree.getLast() );
+        assertNotSame( tree.getFirst(), tree.getLast() );
+        
+        tree.remove( 3 );
+        
+        tree.insert( 37 );
+        tree.insert( 70 );
+        tree.insert( 12 );
+        
+        assertTrue( 3 == tree.getSize() );
+        
+        tree.insert( 90 );
+        tree.insert( 25 );
+        tree.insert( 99 );
+        tree.insert( 91 );
+        tree.insert( 24 );
+        tree.insert( 28 );
+        tree.insert( 26 );
+        
+        tree.printTree();
+        
+        tree.remove( 24 ); // this causes a single left rotation on node with key 12
+        tree.printTree();
+        assertTrue( tree.getRoot().getLeft().key == 26 );
     }
     
     
@@ -120,6 +153,20 @@
       assertEquals("1,2,3", getInorderForm());
     }
     
+    @Test
+    public void testLinks()
+    {
+        tree.insert( 37 );
+        tree.insert( 1 );
+        tree.insert( 2 );
+        tree.insert( 10 );
+        tree.insert( 11 );
+        tree.insert( 25 );
+        tree.insert( 5 );
+        
+        assertTrue( 1 == tree.getFirst().key );
+        assertTrue( 37 == tree.getLast().key );
+    }
     
     @Test
     public void testRemove()
@@ -128,12 +175,14 @@
         tree.insert( 2 );
         tree.insert( 1 );
         
+        System.out.println(getLinkedText());
         tree.remove( 2 );
+        System.out.println(getLinkedText());
         assertEquals("1,3", getInorderForm());
         
         tree.remove( 1 );
         assertEquals("3", getInorderForm());
-        assertEquals( 3, tree.getRoot().key );
+        assertTrue( 3 == tree.getRoot().key );
         
         tree.remove( 3 );
         assertTrue(tree.isEmpty());
@@ -155,16 +204,89 @@
         
         tree.remove( 39 );
         assertEquals( "21,27,37,38", getInorderForm() );
-        assertEquals( 37, tree.getRoot().key ); // check the root value
+        assertTrue( 37 == tree.getRoot().key ); // check the root value
         
         tree.remove( 38 ); // a double right rotation has to happen after this
-        assertEquals( 27, tree.getRoot().key ); // check the root value after double right
rotation
+        assertTrue( 27 == tree.getRoot().key ); // check the root value after double right
rotation
         assertEquals( "21,27,37", getInorderForm() );
         
         tree.printTree();
     }
 
-
+    @Test
+    public void testLinkedNodes()
+    {
+        for( int i=0; i< 3; i++)
+        {
+           tree.insert( i ); 
+        }
+        
+        assertEquals( "[0]-->[1]-->[2]-->NULL", getLinkedText());
+        
+        tree.remove( 1 );
+        assertEquals( "[0]-->[2]-->NULL", getLinkedText());
+        
+        tree.insert( 4 );
+        tree.insert( 3 );
+        
+        assertEquals( "[0]-->[2]-->[3]-->[4]-->NULL", getLinkedText());
+        
+        tree.remove( 0 );
+        assertEquals( "[2]-->[3]-->[4]-->NULL", getLinkedText());
+        
+        tree.remove( 3 );
+        assertEquals( "[2]-->[4]-->NULL", getLinkedText());
+    }
+    
+    
+    @Test
+    public void testFind()
+    {
+        tree.insert( 1 );
+        tree.insert( 70 );
+        tree.insert( 21 );
+        tree.insert( 12 );
+        tree.insert( 27 );
+        tree.insert( 11 );
+        
+        assertNotNull( tree.find( 11 ) );
+        assertNull( tree.find( 0 ));
+        
+        tree.setRoot( null );
+        assertNull( tree.find( 3 ));
+    }
+    
+    
+    @Test
+    public void testFindMaxMin()
+    {
+        tree.insert( 72 );
+        tree.insert( 79 );
+        
+        tree.remove( 72 );// should call findMax internally
+        assertTrue( 79 == tree.getRoot().key );
+        
+        tree.insert( 11 );
+        tree.remove( 79 ); // should call findMin internally
+        assertTrue( 11 == tree.getRoot().key );
+    }
+    
+    private String getLinkedText() 
+    {
+        LinkedAvlNode<Integer> first = tree.getFirst();
+        StringBuilder sb = new StringBuilder();
+        
+        while( first != null )
+        {
+            sb.append( first )
+              .append( "-->" );
+            
+            first = first.next;
+        }
+        sb.append( "NULL" );
+        return sb.toString();
+    }
+    
     private String getInorderForm()
     {
       StringBuilder sb = new StringBuilder();
@@ -198,7 +320,6 @@
       {
          traverse( startNode.right, path ); 
       }
-
       //3. post-order
     }
 }



Mime
View raw message