directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From akaras...@apache.org
Subject svn commit: r620690 - in /directory/sandbox/akarasulu/bigbang/apacheds/core-splay/src: main/java/org/apache/directory/server/core/splay/SplayTree.java test/java/org/apache/directory/server/core/splay/SplayTreeTest.java
Date Tue, 12 Feb 2008 02:32:14 GMT
Author: akarasulu
Date: Mon Feb 11 18:32:13 2008
New Revision: 620690

URL: http://svn.apache.org/viewvc?rev=620690&view=rev
Log:
DIRSERVER-1131: Applying patch from Kiran on splay tree work

Added:
    directory/sandbox/akarasulu/bigbang/apacheds/core-splay/src/test/java/org/apache/directory/server/core/splay/SplayTreeTest.java
Modified:
    directory/sandbox/akarasulu/bigbang/apacheds/core-splay/src/main/java/org/apache/directory/server/core/splay/SplayTree.java

Modified: directory/sandbox/akarasulu/bigbang/apacheds/core-splay/src/main/java/org/apache/directory/server/core/splay/SplayTree.java
URL: http://svn.apache.org/viewvc/directory/sandbox/akarasulu/bigbang/apacheds/core-splay/src/main/java/org/apache/directory/server/core/splay/SplayTree.java?rev=620690&r1=620689&r2=620690&view=diff
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/core-splay/src/main/java/org/apache/directory/server/core/splay/SplayTree.java
(original)
+++ directory/sandbox/akarasulu/bigbang/apacheds/core-splay/src/main/java/org/apache/directory/server/core/splay/SplayTree.java
Mon Feb 11 18:32:13 2008
@@ -39,7 +39,8 @@
     private LinkedBinaryNode<K> root;
     private Comparator<K> keyComparator;
 
-
+    private LinkedBinaryNode<K> first, last;
+    
     public SplayTree( Comparator<K> keyComparator )
     {
         this.keyComparator = keyComparator;
@@ -59,6 +60,7 @@
         if ( root == null )
         {
             root = new LinkedBinaryNode<K>( key );
+            first = root;
             return;
         }
         splay( key );
@@ -68,6 +70,20 @@
             return;
         }
         n = new LinkedBinaryNode<K>( key );
+        
+        if( last == null )
+        {
+          first.next = n;
+	      n.previous = first;
+        }
+        else
+        {
+        	last.next = n;
+        	n.previous = last;
+        }
+        
+        last = n;
+        
         if ( c < 0 )
         {
             n.left = root.left;
@@ -91,8 +107,13 @@
      */
     public void remove( K key )
     {
-        LinkedBinaryNode<K> x;
+        LinkedBinaryNode<K> temp = null;
+        LinkedBinaryNode<K> deleteNode;
+        
         splay( key );
+
+        deleteNode = root; // splay makes the node with key 'key' as root 
+
         if ( keyComparator.compare( key, root.key ) != 0 )
         {
             //            throw new ItemNotFoundException(x.toString());
@@ -105,10 +126,49 @@
         }
         else
         {
-            x = root.right;
+            temp = root.right;
             root = root.left;
             splay( key );
-            root.right = x;
+            root.right = temp;
+        }
+        
+        if( deleteNode == first )
+        {
+        	temp = first.next;
+        	
+        	if( temp != null )
+        	{
+        		first = temp;
+        	}
+        	else
+        	{
+        		first = last = null;
+        	}
+        	
+        }
+        else if( deleteNode == last )
+        {
+        	temp = last.previous;
+       		temp.next = null;
+       		
+        	last = temp;
+        }
+        else
+        {
+            temp = first.next;
+            
+            while( temp != null )
+            {
+                if( temp == deleteNode )
+                {
+                  temp.previous.next = temp.next;
+                  temp.next.previous = temp.previous;
+                  temp = null;
+                  break;
+                }
+                
+                temp = temp.next;
+            }
         }
     }
 
@@ -171,6 +231,18 @@
     public boolean isEmpty()
     {
         return root == null;
+    }
+
+
+    public LinkedBinaryNode<K> getFirst()
+    {
+        return first;
+    }
+
+
+    public LinkedBinaryNode<K> getLast()
+    {
+        return last;
     }
 
 

Added: directory/sandbox/akarasulu/bigbang/apacheds/core-splay/src/test/java/org/apache/directory/server/core/splay/SplayTreeTest.java
URL: http://svn.apache.org/viewvc/directory/sandbox/akarasulu/bigbang/apacheds/core-splay/src/test/java/org/apache/directory/server/core/splay/SplayTreeTest.java?rev=620690&view=auto
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/core-splay/src/test/java/org/apache/directory/server/core/splay/SplayTreeTest.java
(added)
+++ directory/sandbox/akarasulu/bigbang/apacheds/core-splay/src/test/java/org/apache/directory/server/core/splay/SplayTreeTest.java
Mon Feb 11 18:32:13 2008
@@ -0,0 +1,92 @@
+/*
+ *   Licensed to the Apache Software Foundation (ASF) under one
+ *   or more contributor license agreements.  See the NOTICE file
+ *   distributed with this work for additional information
+ *   regarding copyright ownership.  The ASF licenses this file
+ *   to you under the Apache License, Version 2.0 (the
+ *   "License"); you may not use this file except in compliance
+ *   with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *   Unless required by applicable law or agreed to in writing,
+ *   software distributed under the License is distributed on an
+ *   "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *   KIND, either express or implied.  See the License for the
+ *   specific language governing permissions and limitations
+ *   under the License.
+ *
+ */
+package org.apache.directory.server.core.splay;
+
+import static junit.framework.Assert.assertEquals;
+
+import java.util.Comparator;
+
+import org.junit.Before;
+import org.junit.Test;
+
+/**
+ * Tests the linking of <code>LinkedBinaryNode</code>s present in the splay tree.
+ * 
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $Rev$, $Date$
+ */
+public class SplayTreeTest
+{
+   SplayTree<Integer> tree; 
+    
+   @Before
+   public void createTree()
+   {
+       tree = new SplayTree<Integer>( new Comparator<Integer>()
+        {
+
+            public int compare( Integer i1, Integer i2 )
+            {
+                return i1.compareTo( i2 );
+            }
+        });
+   }
+   
+   @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]-->[4]-->[3]-->NULL", getLinkedText());
+       
+       tree.remove( 0 );
+       assertEquals( "[2]-->[4]-->[3]-->NULL", getLinkedText());
+       
+       tree.remove( 3 );
+       assertEquals( "[2]-->[4]-->NULL", getLinkedText());
+   }
+   
+   private String getLinkedText() 
+   {
+       LinkedBinaryNode<Integer> first = tree.getFirst();
+       StringBuilder sb = new StringBuilder();
+       
+       while( first != null )
+       {
+           sb.append( first )
+             .append( "-->" );
+           
+           first = first.next;
+       }
+       sb.append( "NULL" );
+       return sb.toString();
+   }
+}



Mime
View raw message