You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@directory.apache.org by ak...@apache.org on 2008/03/04 15:32:26 UTC
svn commit: r633486 - 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/AVLTreePerfTest.java
Author: akarasulu
Date: Tue Mar 4 06:32:23 2008
New Revision: 633486
URL: http://svn.apache.org/viewvc?rev=633486&view=rev
Log:
minor formatting
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/AVLTreePerfTest.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=633486&r1=633485&r2=633486&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 Mar 4 06:32:23 2008
@@ -33,7 +33,6 @@
*/
public class AVLTree<K>
{
-
/** the root of the tree */
private LinkedAvlNode<K> root;
@@ -45,6 +44,7 @@
/** node representing the end of the doubly linked list formed with the tree nodes */
private LinkedAvlNode<K> last;
+
/**
* Creates a new instance of AVLTree.
@@ -56,6 +56,7 @@
this.comparator = comparator;
}
+
/**
* Inserts a LinkedAvlNode with the given key
*
@@ -120,6 +121,7 @@
balance(treePath);
}
+
private void removeFromList(LinkedAvlNode<K> node)
{
if( node.next == null && node.previous == null ) // should happen in case of tree having single node
@@ -144,6 +146,7 @@
}
+
private void insertInList(LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode, int pos)
{
@@ -184,6 +187,7 @@
}
+
/**
* Removes the LinkedAvlNode present in the tree with the given key value
*
@@ -193,7 +197,6 @@
{
LinkedAvlNode<K> temp = null;
LinkedAvlNode<K> y = null;
- LinkedAvlNode<K> x = null;
List<LinkedAvlNode<K>> treePath = new ArrayList<LinkedAvlNode<K>>();
@@ -293,9 +296,10 @@
* Balances the tree by visiting the nodes present in the List of nodes present in the
* treePath parameter.<br><br>
*
- * This really does the balancing if the hight of the tree is greater than 2 and the<br>
+ * This really does the balancing if the height of the tree is greater than 2 and the<br>
* balance factor is greater than +1 or less than -1.<br><br>
- * For an excellent info please read the <a href="http://en.wikipedia.org/wiki/Avl_tree">Wikipedia article on AVL tree</a>.
+ * For an excellent info please read the
+ * <a href="http://en.wikipedia.org/wiki/Avl_tree">Wikipedia article on AVL tree</a>.
*
* @param treePath the traversed list of LinkedAvlNodes after performing an insert/delete operation.
*/
@@ -357,6 +361,7 @@
return root == null;
}
+
/**
* returns the number of nodes present in this tree.
*
@@ -409,8 +414,8 @@
/**
* Prints the contents of AVL tree in pretty format
*/
- public void printTree() {
-
+ public void printTree()
+ {
if( isEmpty() )
{
System.out.println( "Tree is empty" );
@@ -429,16 +434,19 @@
//-------------- private methods ----------
+
public LinkedAvlNode<K> getFirst()
{
return first;
}
+
public LinkedAvlNode<K> getLast()
{
return last;
}
+
/**
* Rotate the node left side once.
*
@@ -601,6 +609,7 @@
return find( key, root);
}
+
private LinkedAvlNode<K> find( K key, LinkedAvlNode<K> startNode)
{
int c;
@@ -625,6 +634,7 @@
return startNode;
}
+
/**
* Find the LinkedAvlNode having the max key value in the tree starting from the startNode.
Modified: directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/core/avltree/AVLTreePerfTest.java
URL: http://svn.apache.org/viewvc/directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/core/avltree/AVLTreePerfTest.java?rev=633486&r1=633485&r2=633486&view=diff
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/core/avltree/AVLTreePerfTest.java (original)
+++ directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/core/avltree/AVLTreePerfTest.java Tue Mar 4 06:32:23 2008
@@ -63,6 +63,7 @@
};
AvlTreeMarshaller<Integer> treeMarshaller = new AvlTreeMarshaller<Integer>( comparator, new IntegerKeyMarshaller() );
+
@Before
public void createTree()
@@ -82,6 +83,7 @@
start = end = 0;
}
+
@Test
public void testRBTreeInsertPerf()
{
@@ -98,6 +100,7 @@
}
+
@Test
public void testRBTreeLookupPerf()
{
@@ -119,6 +122,7 @@
System.out.println( "total time took to read an item from set " + getTime( start, end ) ) ;
}
+
@Test
public void testRemoveFromRBTree()
{
@@ -157,6 +161,7 @@
System.out.println("total time for inserting " + numKeys + " items into the AVLTree-->" + getTime(start, end));
}
+
@Test
public void testAVLTreeLookupPerf()
{
@@ -179,6 +184,7 @@
System.out.println("total time took to read an item from tree " + getTime( start, end ) ) ;
}
+
@Test
public void testAVLTreeRemovePerf()
{
@@ -225,7 +231,9 @@
System.out.println( "total time taken for serializing HashSet ->" + getTime( start, end ) );
}
- @Test
+
+ @SuppressWarnings("unchecked")
+ @Test
public void testRBTreeDeserializationPerf() throws Exception
{
// read test
@@ -234,12 +242,13 @@
start = System.nanoTime();
- set = (HashSet) objIn.readObject();
+ set = ( HashSet ) objIn.readObject();
end = System.nanoTime();
System.out.println("total time taken for reconstructing a serialized HashSet ->" + getTime( start, end ) );
}
+
@Test
public void testAVLTreeSerializationPerf() throws Exception