directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From akaras...@apache.org
Subject svn commit: r633710 - 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 Tue, 04 Mar 2008 23:43:46 GMT
Author: akarasulu
Date: Tue Mar  4 15:43:32 2008
New Revision: 633710

URL: http://svn.apache.org/viewvc?rev=633710&view=rev
Log:
DIRSERVER-1142: applying patch from Kiran

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=633710&r1=633709&r2=633710&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 15:43:32 2008
@@ -598,18 +598,80 @@
         return null;
     }
     
-    
+    /**
+     * finds a LinkedAvlNode<K> whose key is higher than the given key.
+     *
+     * @param key the key
+     * @return the LinkedAvlNode<K> whose key is greater than the given key ,<br>
+     *         null if there is no node with a higher key than the given key.
+     */
     public LinkedAvlNode<K> findGreater( K key )
     {
-        throw new NotImplementedException();
+        LinkedAvlNode<K> result = fetchNonNullNode( key, root, root);
+
+        if( result == null )
+        {
+            return null;
+        }
+        else if( comparator.compare( key, result.key ) < 0 )
+        {
+            return result;
+        }
+        
+        return result.next;
     }
     
-    
+    /**
+     * finds a LinkedAvlNode<K> whose key is lower than the given key.
+     *
+     * @param key the key
+     * @return the LinkedAvlNode<K> whose key is lower than the given key ,<br>
+     *         null if there is no node with a lower key than the given key.
+     */
     public LinkedAvlNode<K> findLess( K key )
     {
-        throw new NotImplementedException();
+        LinkedAvlNode<K> result = fetchNonNullNode( key, root, root);
+
+        if( result == null )
+        {
+            return null;
+        }
+        else if( comparator.compare( key, result.key ) > 0 )
+        {
+            return result;
+        }
+        
+        return result.previous;
     }
     
+    /*
+     * This method returns the last visited non-null node in case if the node with the given
key
+     * is not present. This method should not be used as general purpose lookup method.
+     * This is written to assist the findGreater, findLess methods. 
+     */
+    private LinkedAvlNode<K> fetchNonNullNode( K key, LinkedAvlNode<K> startNode,
LinkedAvlNode<K> parent )
+    {
+        
+        if( startNode == null )
+        {
+            return parent;
+        }
+        
+        int c = comparator.compare( key, startNode.key );
+        
+        parent = startNode;
+
+        if( c > 0 )
+        {
+            return fetchNonNullNode( key, startNode.right, parent );
+        }
+        else if( c < 0 )
+        {
+            return fetchNonNullNode( key, startNode.left, parent );
+        }
+        
+        return startNode;
+    }
     
     /**
      * 

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=633710&r1=633709&r2=633710&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 Mar  4 15:43:32 2008
@@ -255,6 +255,48 @@
     }
     
     @Test
+    public void testFindGreater()
+    {
+        assertNull( tree.findGreater( 1 ) );
+        
+        tree.insert( 1 );
+        assertNull( tree.findGreater( 1 ) );
+        
+        tree.insert( 0 );
+        tree.insert( 3 );
+        tree.insert( 7 );
+        tree.insert( 6 );
+        tree.insert( 2 );
+        tree.insert( 8 );
+        
+        assertFalse( 1 == tree.findGreater( 1 ).key );
+        assertTrue( 2 == tree.findGreater( 1 ).key );
+        assertTrue( 6 == tree.findGreater( 4 ).key );
+        assertNull( tree.findGreater( 8 ) );
+    }
+    
+    @Test
+    public void testFindLess()
+    {
+        assertNull( tree.findLess( 1 ) );
+        
+        tree.insert( 1 );
+        assertNull( tree.findLess( 1 ) );
+
+        tree.insert( 2 );
+        tree.insert( 7 );
+        tree.insert( 3 );
+        tree.insert( 6 );
+        tree.insert( 0 );
+        tree.insert( 37 );
+        
+        assertFalse( 0 == tree.findLess( 5 ).key );
+        assertTrue( 3 == tree.findLess( 5 ).key );
+        assertTrue( 7 == tree.findLess( 8 ).key );
+        assertNull( tree.findLess( 0 ) );
+    }
+    
+    @Test
     public void testFindMaxMin()
     {
         tree.insert( 72 );



Mime
View raw message