directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From akaras...@apache.org
Subject svn commit: r636594 - in /directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src: main/java/org/apache/directory/server/core/avltree/ test/java/org/apache/directory/server/core/avltree/
Date Thu, 13 Mar 2008 01:05:39 GMT
Author: akarasulu
Date: Wed Mar 12 18:05:37 2008
New Revision: 636594

URL: http://svn.apache.org/viewvc?rev=636594&view=rev
Log:
fixing couple problems with avl tree and marshaller but some still do exist ...

 o marshaller did not properly handle basis case of empty tree
 o marshaller not extensively tested and avl tree size is lost
 o problems with accounting of tree size exist with all operations
 o wrote some tests to show these problems: the tests will fail until a fix


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/main/java/org/apache/directory/server/core/avltree/AvlTreeMarshaller.java
    directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMarshallerTest.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=636594&r1=636593&r2=636594&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 18:05:37 2008
@@ -47,8 +47,9 @@
 
     /** holds the number of nodes present in the tree */
     private int size;
-    
-	/**
+
+
+    /**
 	 * Creates a new instance of AVLTree.
 	 *
 	 * @param comparator the comparator to be used for comparing keys
@@ -79,11 +80,11 @@
 	    
 	    if( root == null )
 	    {
-	      root = new LinkedAvlNode<K>( key );
-	      first = root;
-	      last = root;
-	      size = 1;
-	      return null;
+	        root = new LinkedAvlNode<K>( key );
+	        first = root;
+	        last = root;
+	        size = 1;
+	        return null;
 	    }
 	    
 	    node = new LinkedAvlNode<K>( key );
@@ -106,13 +107,13 @@
 	        
 	        if( c < 0 )
 	        {
-	          temp.isLeft = true;
-	          temp = temp.getLeft();  
+	            temp.isLeft = true;
+	            temp = temp.getLeft();
 	        }
 	        else
 	        {
-	          temp.isLeft = false;
-	          temp = temp.getRight();
+	            temp.isLeft = false;
+	            temp = temp.getRight();
 	        }
 	    }
 	    

Modified: directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMarshaller.java
URL: http://svn.apache.org/viewvc/directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMarshaller.java?rev=636594&r1=636593&r2=636594&view=diff
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMarshaller.java
(original)
+++ directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMarshaller.java
Wed Mar 12 18:05:37 2008
@@ -37,6 +37,9 @@
 @SuppressWarnings("unchecked")
 public class AvlTreeMarshaller<E> implements Marshaller<AvlTree<E>>
 {
+    /** used for serialized form of an empty AvlTree */
+    private static final byte[] EMPTY_TREE = new byte[1];
+
     /** marshaller to be used for marshalling the keys */
     private Marshaller<E> keyMarshaller;
     
@@ -67,7 +70,7 @@
     {
         if( tree.isEmpty() )
         {
-            return null;
+            return EMPTY_TREE;
         }
 
         LinkedAvlNode<E> x = tree.getFirst().next;
@@ -146,8 +149,18 @@
      * 
      * @param data byte array to be converted into AVLTree  
      */
-    public AvlTree<E> deserialize( byte[] data )
+    public AvlTree<E> deserialize( byte[] data ) throws IOException
     {
+        if ( data == null || data.length == 0 )
+        {
+            throw new IOException( "Null or empty data array is invalid." );
+        }
+
+        if ( data.length == 1 && data[0] == 0 )
+        {
+            return new AvlTree<E>( comparator );
+        }
+
         ByteArrayInputStream bin = new ByteArrayInputStream( data );
         DataInputStream din = new DataInputStream( bin );
         
@@ -181,7 +194,7 @@
                 nodes[ i ].setNext( nodes[ i + 1] );
                 nodes[ i + 1].setPrevious( nodes[ i ] );
             }
-            
+
             return tree;
         }
         catch( Exception ioe )
@@ -194,8 +207,9 @@
 
     
     /**
-     * Reads the data from given InputStream and creates the LinkedAvlNodes to form the tree
-     * node = [size] [data-length] [data] [index] [child-marker] [node] [child-marker] [node]
+     * Reads the data from given InputStream and creates the LinkedAvlNodes to
+     * form the tree node = [size] [data-length] [data] [index] [child-marker]
+     * [node] [child-marker] [node].
      *
      * @param in the input stream to deserialize from
      * @param node the node to deserialize
@@ -204,32 +218,33 @@
      */
     public LinkedAvlNode<E> readTree( DataInputStream in, LinkedAvlNode<E> node
) throws IOException
     {
-      int dLen = in.readInt();
+        int dLen = in.readInt();
       
-      byte[] data = new byte[ dLen ];
+        byte[] data = new byte[ dLen ];
+
         //noinspection ResultOfMethodCallIgnored
         in.read( data );
 
-      E key = keyMarshaller.deserialize( data );
-      node = new LinkedAvlNode( key );
+        E key = keyMarshaller.deserialize( data );
+        node = new LinkedAvlNode( key );
       
-      int index = in.readInt();
-      nodes[ index ] = node;
+        int index = in.readInt();
+        nodes[ index ] = node;
       
-      int childMarker = in.readInt();
+        int childMarker = in.readInt();
       
-      if( childMarker == 2)
-      {
-          node.setLeft( readTree( in, node.getLeft() ) );
-      }
+        if( childMarker == 2)
+        {
+            node.setLeft( readTree( in, node.getLeft() ) );
+        }
       
-      childMarker = in.readInt();
+        childMarker = in.readInt();
       
-      if( childMarker == 4 )
-      {
-          node.setRight( readTree( in, node.getRight() ) );
-      }
+        if( childMarker == 4 )
+        {
+            node.setRight( readTree( in, node.getRight() ) );
+        }
       
-      return node;
+        return node;
     }
 }

Modified: directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMarshallerTest.java
URL: http://svn.apache.org/viewvc/directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMarshallerTest.java?rev=636594&r1=636593&r2=636594&view=diff
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMarshallerTest.java
(original)
+++ directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMarshallerTest.java
Wed Mar 12 18:05:37 2008
@@ -22,6 +22,8 @@
 
 import static org.junit.Assert.assertNotNull;
 import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertEquals;
 
 import java.io.File;
 import java.io.FileInputStream;
@@ -42,7 +44,6 @@
  */
 public class AvlTreeMarshallerTest
 {
-
     AvlTree<Integer> tree;
     Comparator<Integer> comparator;
     AvlTreeMarshaller<Integer> treeMarshaller;
@@ -56,23 +57,91 @@
     {
         comparator = new Comparator<Integer>() 
         {
-
-          public int compare( Integer i1, Integer i2 )
-          {
-              return i1.compareTo( i2 );
-          }
-        
+            public int compare( Integer i1, Integer i2 )
+            {
+                return i1.compareTo( i2 );
+            }
         };
         
       
-      tree = new AvlTree<Integer>( comparator );  
-      treeMarshaller = new AvlTreeMarshaller<Integer>( comparator, new IntegerKeyMarshaller()
);
+        tree = new AvlTree<Integer>( comparator );
+        treeMarshaller = new AvlTreeMarshaller<Integer>( comparator, new IntegerKeyMarshaller()
);
     }
-    
+
+
     @Test
-    public void testMarshal() throws FileNotFoundException, IOException
+    public void testMarshalEmptyTree() throws IOException
+    {
+        byte[] bites = treeMarshaller.serialize( new AvlTree<Integer>( comparator )
);
+        AvlTree<Integer> tree = treeMarshaller.deserialize( bites );
+        assertNotNull( tree );
+    }
+
+
+    @Test
+    public void testRoundTripEmpty() throws IOException
+    {
+        AvlTree<Integer> original = new AvlTree<Integer>( comparator );
+        byte[] bites = treeMarshaller.serialize( original );
+        AvlTree<Integer> deserialized = treeMarshaller.deserialize( bites );
+        assertTrue( deserialized.isEmpty() );
+    }
+
+
+    @Test
+    public void testRoundTripOneEntry() throws IOException
+    {
+        AvlTree<Integer> original = new AvlTree<Integer>( comparator );
+        original.insert( 0 );
+        byte[] bites = treeMarshaller.serialize( original );
+        AvlTree<Integer> deserialized = treeMarshaller.deserialize( bites );
+        assertFalse( deserialized.isEmpty() );
+        assertEquals( 1, deserialized.getSize() );
+        assertEquals( 0, ( int ) deserialized.getFirst().getKey() );
+    }
+
+
+    @Test
+    public void testRoundTripTwoEntries() throws IOException
+    {
+        AvlTree<Integer> original = new AvlTree<Integer>( comparator );
+        original.insert( 0 );
+        original.insert( 1 );
+        byte[] bites = treeMarshaller.serialize( original );
+        AvlTree<Integer> deserialized = treeMarshaller.deserialize( bites );
+        assertFalse( deserialized.isEmpty() );
+        assertEquals( 2, deserialized.getSize() );
+        assertEquals( 0, ( int ) deserialized.getFirst().getKey() );
+        assertEquals( 1, ( int ) deserialized.getFirst().next.getKey() );
+    }
+
+
+    @Test
+    public void testRoundTripManyEntries() throws Exception
+    {
+        AvlTree<Integer> original = new AvlTree<Integer>( comparator );
+        for ( int ii = 0; ii < 100; ii++ )
+        {
+            original.insert( ii );
+        }
+        byte[] bites = treeMarshaller.serialize( original );
+        AvlTree<Integer> deserialized = treeMarshaller.deserialize( bites );
+        assertFalse( deserialized.isEmpty() );
+        assertEquals( 100, deserialized.getSize() );
+
+        AvlTreeCursor<Integer> cursor = new AvlTreeCursor<Integer>( deserialized
);
+        cursor.first();
+        for ( int ii = 0; ii < 100; ii++ )
+        {
+            assertEquals( ii, ( int ) cursor.get() );
+            cursor.next();
+        }
+    }
+
+
+    @Test
+    public void testMarshal() throws IOException
     {
-        
         tree.insert( 37 );
         tree.insert( 7 );
         tree.insert( 25 );
@@ -127,5 +196,4 @@
         assertNotNull(unmarshalledTree.getFirst());
         assertNotNull(unmarshalledTree.getLast());
     }
-
-}
+}
\ No newline at end of file



Mime
View raw message