You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@directory.apache.org by ka...@apache.org on 2008/03/12 20:23:55 UTC
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
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