directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From akaras...@apache.org
Subject svn commit: r631459 - 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 Wed, 27 Feb 2008 01:41:19 GMT
Author: akarasulu
Date: Tue Feb 26 17:41:18 2008
New Revision: 631459

URL: http://svn.apache.org/viewvc?rev=631459&view=rev
Log:
DIRSERVER-1138: committing files contributed from Kiran Ayagari

Added:
    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/main/java/org/apache/directory/server/core/avltree/Marshaller.java
    directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMarshallerTest.java
    directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/core/avltree/IntegerKeyMarshaller.java

Added: 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=631459&view=auto
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMarshaller.java
(added)
+++ directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMarshaller.java
Tue Feb 26 17:41:18 2008
@@ -0,0 +1,216 @@
+/*
+ *   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.avltree.marshaller;
+
+import java.io.ByteArrayInputStream;
+import java.io.ByteArrayOutputStream;
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.util.Comparator;
+
+import org.apache.directory.server.core.avltree.AVLTree;
+import org.apache.directory.server.core.avltree.LinkedAvlNode;
+
+/**
+ * 
+ * Class to serialize the AvlTree node data.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $Rev$, $Date$
+ */
+@SuppressWarnings("unchecked")
+public class AvlTreeMarshaller<E> implements Marshaller<AVLTree<E>>
+{
+
+    /** marshaller to be used for marshalling the keys */
+    private Marshaller<E> keyMarshaller;
+    
+    /** key Comparator for the AvlTree */
+    private Comparator<E> comparator;
+    
+    private LinkedAvlNode[] nodes;
+    
+
+    /**
+     * 
+     * Creates a new instance of AvlTreeMarshaller.
+     *
+     * @param comparator Comparator to be used for key comparision
+     * @param keyMarshaller marshaller for keys
+     */
+    public AvlTreeMarshaller(Comparator<E> comparator, Marshaller keyMarshaller)
+    {
+        this.comparator = comparator;
+        this.keyMarshaller = keyMarshaller;
+    }
+    
+    /**
+     * Marshals the given tree to bytes
+     * @param tree the tree to be marshalled
+     */
+    public byte[] marshal( AVLTree<E> tree )
+    {
+        if( tree.isEmpty() )
+        {
+            return null;
+        }
+
+        ByteArrayOutputStream byteStream = new ByteArrayOutputStream();
+        DataOutputStream out = new DataOutputStream( byteStream );
+        byte[] data = null;
+        
+        try
+        {
+            out.writeInt( tree.getSize() );
+            writeTree( tree.getRoot(), out );
+            out.flush();
+            data = byteStream.toByteArray();
+            out.close();
+        }
+        catch( IOException e )
+        {
+            e.printStackTrace();
+        }
+        
+        return data;
+    }
+
+    /**
+     * writes the content of the AVLTree to an output stream.
+     * The current format is 
+     *  
+     *   node = [size] [data-length] [data] [index] [child-marker] [node] [child-marker]
[node]
+     *
+     * @param node the node to be marshalled to bytes
+     * @param out OutputStream
+     * @throws IOException
+     */
+    private void writeTree( LinkedAvlNode<E> node, DataOutputStream out ) throws IOException
+    {
+        byte[] data = keyMarshaller.marshal( node.getKey() );
+        
+        out.writeInt( data.length ); // data-length
+        out.write( data ); // data
+        out.writeInt( node.getIndex() ); // index
+        
+        if( node.getLeft() != null )
+        {
+            out.writeInt( 2 ); // left
+            writeTree( node.getLeft(), out );
+        }
+        else
+        {
+            out.writeInt( 0 );   
+        }
+        
+        if( node.getRight() != null )
+        {
+            out.writeInt( 4 ); // right
+            writeTree( node.getRight(), out );
+        }
+        else
+        {
+            out.writeInt( 0 );   
+        }
+        
+    }
+
+    
+    /**
+     * Creates an AVLTree from given bytes of data.
+     * 
+     * @param data byte array to be converted into AVLTree  
+     */
+    public AVLTree<E> unMarshal( byte[] data )
+    {
+        ByteArrayInputStream bin = new ByteArrayInputStream( data );
+        DataInputStream din = new DataInputStream( bin );
+        
+        try
+        {
+            int size = din.readInt();
+            
+            nodes = new LinkedAvlNode[ size ];
+            LinkedAvlNode<E> root = readTree( din, null );
+            
+            AVLTree<E> tree = new AVLTree<E>( comparator );
+            
+            tree.setRoot( root );
+            
+            tree.setFirst( nodes[0] );
+            
+            if( nodes.length > 1 )
+            {
+                tree.setLast( nodes[ nodes.length - 1 ] );
+            }
+            
+            for( int i = 0; i < nodes.length - 1; i++ )
+            {
+                nodes[ i ].setNext( nodes[ i + 1] );
+                nodes[ i + 1].setPrevious( nodes[ i ] );
+            }
+            
+            return tree;
+        }
+        catch( Exception ioe )
+        {
+            ioe.printStackTrace();
+        }
+        
+        return null;
+    }
+
+    
+    /**
+     * 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]
+     * 
+     */
+    public LinkedAvlNode<E> readTree( DataInputStream in, LinkedAvlNode<E> node
) throws IOException
+    {
+      int dLen = in.readInt();
+      
+      byte[] data = new byte[ dLen ];
+      in.read( data );
+
+      E key = keyMarshaller.unMarshal( data );
+      node = new LinkedAvlNode( key );
+      
+      int index = in.readInt();
+      nodes[ index ] = node;
+      
+      int childMarker = in.readInt();
+      
+      if( childMarker == 2)
+      {
+          node.setLeft( readTree( in, node.getLeft() ) );
+      }
+      
+      childMarker = in.readInt();
+      
+      if( childMarker == 4 )
+      {
+          node.setRight( readTree( in, node.getRight() ) );
+      }
+      
+      return node;
+    }
+}

Added: directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/avltree/Marshaller.java
URL: http://svn.apache.org/viewvc/directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/avltree/Marshaller.java?rev=631459&view=auto
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/avltree/Marshaller.java
(added)
+++ directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/avltree/Marshaller.java
Tue Feb 26 17:41:18 2008
@@ -0,0 +1,33 @@
+/*
+ *   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.avltree.marshaller;
+
+/**
+ * 
+ * An interface to marshall/unmarshal the AVLTree keys.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $Rev$, $Date$
+ */
+public interface Marshaller<E>
+{
+    byte[] marshal(E e);
+    E unMarshal(byte[] data);
+}

Added: 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=631459&view=auto
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMarshallerTest.java
(added)
+++ directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMarshallerTest.java
Tue Feb 26 17:41:18 2008
@@ -0,0 +1,131 @@
+/*
+ *   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.avltree.marshaller;
+
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertTrue;
+
+import java.io.File;
+import java.io.FileInputStream;
+import java.io.FileNotFoundException;
+import java.io.FileOutputStream;
+import java.io.IOException;
+import java.util.Comparator;
+
+import org.apache.directory.server.core.avltree.AVLTree;
+import org.junit.Before;
+import org.junit.Test;
+
+/**
+ * TestCase for AvlTreeMarshaller.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $Rev$, $Date$
+ */
+public class AvlTreeMarshallerTest
+{
+
+    AVLTree<Integer> tree;
+    Comparator<Integer> comparator;
+    AvlTreeMarshaller<Integer> treeMarshaller;
+    
+    static AVLTree<Integer> savedTree;
+    
+    File treeFile = new File( System.getProperty( "java.io.tmpdir" ) + File.separator + "avl.tree");
+    
+    @Before
+    public void createTree()
+    {
+        comparator = new Comparator<Integer>() 
+        {
+
+          public int compare( Integer i1, Integer i2 )
+          {
+              return i1.compareTo( i2 );
+          }
+        
+        };
+        
+      
+      tree = new AVLTree<Integer>( comparator );  
+      treeMarshaller = new AvlTreeMarshaller<Integer>( comparator, new IntegerKeyMarshaller()
);
+    }
+    
+    @Test
+    public void testMarshal() throws FileNotFoundException, IOException
+    {
+        
+        tree.insert( 37 );
+        tree.insert( 7 );
+        tree.insert( 25 );
+        tree.insert( 8 );
+        tree.insert( 9 );
+
+        FileOutputStream fout = new FileOutputStream( treeFile );
+        fout.write( treeMarshaller.marshal( tree ) );
+        fout.close();
+        
+        savedTree = tree; // to reference in other tests
+        
+        System.out.println("saved tree\n--------");
+        tree.printTree();
+        
+        assertTrue( true );
+    }
+
+
+    @Test
+    public void testUnMarshal() throws FileNotFoundException, IOException
+    {
+        FileInputStream fin = new FileInputStream(treeFile);
+        
+        byte[] data = new byte[ ( int )treeFile.length() ];
+        fin.read( data );
+        
+        AVLTree<Integer> unmarshalledTree = treeMarshaller.unMarshal( data );
+        
+        System.out.println("\nunmarshalled tree\n---------------");
+        unmarshalledTree.printTree();
+        
+        assertTrue( savedTree.getRoot().getKey() == unmarshalledTree.getRoot().getKey() );
+
+        unmarshalledTree.insert( 6 ); // will change the root as part of balancing
+        
+        assertFalse( savedTree.getRoot().getKey() == unmarshalledTree.getRoot().getKey()
);
+        assertTrue( 8 == unmarshalledTree.getRoot().getKey() ); // new root
+        
+        assertTrue( 37 == unmarshalledTree.getLast().getKey() );
+        unmarshalledTree.insert( 99 );
+        assertTrue( 99 == unmarshalledTree.getLast().getKey() );
+
+        assertTrue( 6 == unmarshalledTree.getFirst().getKey() );
+        
+        unmarshalledTree.insert( 0 );
+        assertTrue( 0 == unmarshalledTree.getFirst().getKey() );
+        
+        System.out.println("\nmodified tree after unmarshalling\n---------------");
+        unmarshalledTree.printTree();
+        
+        assertNotNull(unmarshalledTree.getFirst());
+        assertNotNull(unmarshalledTree.getLast());
+    }
+
+}

Added: directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/core/avltree/IntegerKeyMarshaller.java
URL: http://svn.apache.org/viewvc/directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/core/avltree/IntegerKeyMarshaller.java?rev=631459&view=auto
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/core/avltree/IntegerKeyMarshaller.java
(added)
+++ directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/core/avltree/IntegerKeyMarshaller.java
Tue Feb 26 17:41:18 2008
@@ -0,0 +1,35 @@
+
+package org.apache.directory.server.core.avltree.marshaller;
+
+public class IntegerKeyMarshaller implements Marshaller<Integer>
+{
+
+    public byte[] marshal( Integer i )
+    {
+        int y = i.intValue();
+        byte[] data = new byte[4];
+        data[0] = (byte)((y & 0xFF) >>> 24);
+        data[1] = (byte)((y & 0xFF) >>> 16);
+        data[2] = (byte)((y & 0xFF) >>> 8);
+        data[3] = (byte)(y & 0xFF);
+        
+        return data;
+    }
+
+
+    public Integer unMarshal( byte[] data )
+    {
+        if( data == null || data.length == 0)
+        {
+            return null;
+        }
+       
+        int y =  ( ( data[0] & 0xFF ) << 24 ) 
+                  | (( data[1] & 0xFF ) << 16 )
+                  | ( ( data[2] & 0xFF ) << 8 )
+                  | ( data[3] & 0xFF );
+        
+        return y;
+    }
+
+}



Mime
View raw message