directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From kayyag...@apache.org
Subject svn commit: r636469 - in /directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src: main/java/org/apache/directory/server/core/avltree/AvlTree.java test/java/org/apache/directory/server/core/avltree/AvlTreeTest.java
Date Wed, 12 Mar 2008 19:23:55 GMT
Author: kayyagari
Date: Wed Mar 12 12:23:53 2008
New Revision: 636469

URL: http://svn.apache.org/viewvc?rev=636469&view=rev
Log:
added a size variable to hold the number of nodes present in the tree instead f calculating
every time

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/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=636469&r1=636468&r2=636469&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
Wed Mar 12 12:23:53 2008
@@ -45,6 +45,8 @@
 	/** node representing the end of the doubly linked list formed with the tree nodes */
     private LinkedAvlNode<K> last;
 
+    /** holds the number of nodes present in the tree */
+    private int size;
     
 	/**
 	 * Creates a new instance of AVLTree.
@@ -80,6 +82,7 @@
 	      root = new LinkedAvlNode<K>( key );
 	      first = root;
 	      last = root;
+	      size = 1;
 	      return null;
 	    }
 	    
@@ -127,6 +130,8 @@
         treePath.add( 0, node );
 	    balance(treePath);
 	    
+	    size++;
+	    
 	    return null;
 	}
 	
@@ -226,6 +231,7 @@
             if( temp == root )
             {
               root = null;
+              size = 0;
               return key;
             }
             
@@ -299,6 +305,8 @@
        treePath.add( 0, y ); // y can be null but getBalance returns 0 so np
        balance( treePath );
        
+       size--;
+       
        return key;
     }
     
@@ -381,25 +389,7 @@
     //NOTE: This method is internally used by AVLTreeMarshaller
     public int getSize()
     {
-        if ( root == null )
-        {
-            return 0;
-        }
-        
-        if( root.isLeaf() )
-        {
-            return 1;
-        }
-      
-        LinkedAvlNode<K> x = first.next;
-      
-        while( x != null )
-        {
-            x.setIndex( x.previous.getIndex() + 1 );  
-            x = x.next;
-        }
-      
-        return last.getIndex() + 1;
+        return size;
     }
     
     

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=636469&r1=636468&r2=636469&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
Wed Mar 12 12:23:53 2008
@@ -388,6 +388,32 @@
       return sb.toString();
     }
     
+    @Test
+    public void testSize()
+    {
+        assertTrue( 0 == tree.getSize() );
+        
+        tree.insert( 3 );
+        assertTrue( 1 == tree.getSize() );
+        
+        tree.remove( 3 );
+        assertTrue( 0 == tree.getSize() );
+        
+        tree.insert( 0 );
+        tree.insert( 7 );
+        tree.insert( 3 );
+        assertTrue( 3 == tree.getSize() );
+        
+        tree.remove( 0 );
+        assertTrue( 2 == tree.getSize() );
+        
+        tree.remove( 7 );
+        tree.remove( 3 );
+        
+        assertTrue( 0 == tree.getSize() );
+    }
+    
+    
     private void traverse( LinkedAvlNode<Integer> startNode, List<LinkedAvlNode<Integer>>
path )
     {
       //1. pre-order



Mime
View raw message