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/13 02:05:39 UTC
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/
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