directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From akaras...@apache.org
Subject svn commit: r629205 - in /directory/sandbox/akarasulu/bigbang/apacheds: ./ core-avl/ core-avl/src/ core-avl/src/main/ core-avl/src/main/java/ core-avl/src/main/java/org/ core-avl/src/main/java/org/apache/ core-avl/src/main/java/org/apache/directory/ co...
Date Tue, 19 Feb 2008 19:44:50 GMT
Author: akarasulu
Date: Tue Feb 19 11:44:43 2008
New Revision: 629205

URL: http://svn.apache.org/viewvc?rev=629205&view=rev
Log:
DIRSERVER-1138: committing patches from Kiran for new in memory threaded AVL tree implementation

Added:
    directory/sandbox/akarasulu/bigbang/apacheds/core-avl/   (with props)
    directory/sandbox/akarasulu/bigbang/apacheds/core-avl/pom.xml
    directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/
    directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/
    directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/
    directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/
    directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/
    directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/
    directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/
    directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/
    directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/avltree/
    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/LinkedAvlNode.java
    directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/
    directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/
    directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/
    directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/
    directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/
    directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/
    directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/core/
    directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/core/avltree/
    directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/core/avltree/AVLTreeTest.java
Modified:
    directory/sandbox/akarasulu/bigbang/apacheds/pom.xml

Propchange: directory/sandbox/akarasulu/bigbang/apacheds/core-avl/
------------------------------------------------------------------------------
--- svn:ignore (added)
+++ svn:ignore Tue Feb 19 11:44:43 2008
@@ -0,0 +1,17 @@
+target
+.clover
+.wtpmodules
+.settings
+.deployables
+apache.org
+.metadata
+*.md5
+*.log
+*.iml
+*.ipr
+*.iws
+.project
+.classpath
+nbproject
+schema
+

Added: directory/sandbox/akarasulu/bigbang/apacheds/core-avl/pom.xml
URL: http://svn.apache.org/viewvc/directory/sandbox/akarasulu/bigbang/apacheds/core-avl/pom.xml?rev=629205&view=auto
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/core-avl/pom.xml (added)
+++ directory/sandbox/akarasulu/bigbang/apacheds/core-avl/pom.xml Tue Feb 19 11:44:43 2008
@@ -0,0 +1,44 @@
+<?xml version="1.0" encoding="ISO-8859-1"?>
+<!--
+    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.
+-->
+<!-- $Rev:  $ $Date:  $ -->
+<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
+  <modelVersion>4.0.0</modelVersion>
+  <parent>
+    <groupId>org.apache.directory.server</groupId>
+    <artifactId>apacheds-parent</artifactId>
+    <version>1.5.2-SNAPSHOT</version>
+  </parent>
+  <artifactId>apacheds-core-avl</artifactId>
+  <name>ApacheDS Core AVL</name>
+
+  <description>
+    A linked in memory AVL tree implementation with Cursor.
+  </description>
+
+  <packaging>jar</packaging>
+
+  <dependencies>
+    <dependency>
+      <groupId>${pom.groupId}</groupId>
+      <version>${pom.version}</version>
+      <artifactId>apacheds-core-cursor</artifactId>
+    </dependency>
+  </dependencies>
+  
+</project>
+

Added: 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=629205&view=auto
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/avltree/AVLTree.java
(added)
+++ directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/avltree/AVLTree.java
Tue Feb 19 11:44:43 2008
@@ -0,0 +1,588 @@
+/*
+ *   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;
+
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.List;
+
+
+/**
+ * An AVL tree implementation
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $Rev$, $Date$
+ */
+public class AVLTree<K>
+{
+
+    /** the root of the tree */
+	private LinkedAvlNode<K> root;
+
+	/** The Comparator used for comparing the keys */
+	private Comparator<K> comparator;
+
+	/**
+	 * Creates a new instance of AVLTree.
+	 *
+	 * @param comparator the comparator to be used for comparing keys
+	 */
+	public AVLTree( Comparator<K> comparator)
+	{
+	    this.comparator = comparator;
+	}
+	
+	/**
+	 * Inserts a LinkedAvlNode with the given key
+	 *
+	 * @param key the item to be inserted.<br> 
+	 * Note: Ignores if a node with the given key already exists.
+	 */
+	public void insert( K key )
+	{
+	    LinkedAvlNode<K> node, temp;
+	    LinkedAvlNode<K> parent = null;
+	    int c;
+	    
+	    if( root == null )
+	    {
+	      root = new LinkedAvlNode<K>( key );
+	      return;
+	    }
+	    
+	    node = new LinkedAvlNode<K>( key );
+	    temp = root;
+	    
+	    List<LinkedAvlNode<K>> treePath = new ArrayList<LinkedAvlNode<K>>();
+
+	    while( temp != null )
+	    {
+	        treePath.add(0, temp ); // last node first, for the sake of balance factor computation
+	        parent = temp;
+	        
+	        c = comparator.compare( key, temp.getKey() );
+	        
+	        if( c == 0 )
+	        {
+	            return; // key already exists
+	        }
+	        
+	        if( c < 0 )
+	        {
+	          temp = temp.getLeft();  
+	        }
+	        else
+	        {
+	          temp = temp.getRight();
+	        }
+	    }
+	    
+	    if( ( c = comparator.compare( key, parent.getKey() ) ) < 0 )
+	    {
+	        parent.setLeft( node );
+	    }
+	    else
+	    {
+	        parent.setRight( node );
+	    }
+	 
+	    treePath.add( 0, node );
+	    balance(treePath);
+	}
+	
+	
+	/**
+     * Removes the LinkedAvlNode present in the tree with the given key value
+     *
+     * @param key the value of the node to be removed
+     */
+    public void remove( K key )
+    {
+        LinkedAvlNode<K> temp = null;
+        LinkedAvlNode<K> y = null;
+        LinkedAvlNode<K> x = null;
+        
+        List<LinkedAvlNode<K>> treePath = new ArrayList<LinkedAvlNode<K>>();
+        
+        treePath = find( key, root, treePath);
+        
+        if( treePath == null )
+        {
+            return;
+        }
+        
+        temp = treePath.remove( 0 );
+        
+        if( temp.isLeaf() )
+        {
+            if( temp == root )
+            {
+              root = null;
+              return;
+            }
+            
+            if( !treePath.isEmpty() )
+            {
+                detachNodes( temp, treePath.get( 0 ) );
+            }
+        }
+        else
+        {
+            if( temp.left != null )
+            {
+                List<LinkedAvlNode<K>> leftTreePath = findMax( temp.left );
+                y = leftTreePath.remove( 0 );
+                
+                if( leftTreePath.isEmpty() ) // y is the left child of root and y is a leaf
+                {
+                    detachNodes( y, temp );
+                }
+                else
+                {
+                    detachNodes( y, leftTreePath.get( 0 ) );
+                }
+                
+                leftTreePath.addAll( treePath );
+                treePath = leftTreePath;
+                
+                y.right = temp.right;
+
+                if( temp == root )
+                {
+                    y.left = temp.left;
+                    root = y;
+                }
+                else
+                {
+                    replaceNode( temp, y, treePath.get( 0 ) );
+                }
+            }
+            else if( temp.right != null )
+            {
+                List<LinkedAvlNode<K>> rightTreePath = findMin( temp.right );
+                y = rightTreePath.remove( 0 );
+                
+                if( rightTreePath.isEmpty() )
+                {
+                    detachNodes( y, temp ); // y is the right child of root and y is a leaf
+                }
+                else
+                {
+                    detachNodes( y, rightTreePath.get( 0 ) );
+                }
+                
+                rightTreePath.addAll( treePath );
+                treePath = rightTreePath;
+                
+                y.right = temp.right;
+                
+                if( temp == root )
+                {
+                    y.right = temp.right;
+                    root = y;
+                }
+                else
+                {
+                    replaceNode( temp, y, treePath.get( 0 ) );
+                }
+            }
+        }
+        
+       balance( treePath );
+    }
+    
+    
+	/**
+	 * Balances the tree by visiting the nodes present in the List of nodes present in the
+	 * treePath parameter.<br><br>
+	 *
+	 * This really does the balancing if the hight of the tree is greater than 2 and the<br>

+	 * balance factor is greater than +1 or less than -1.<br><br>
+	 * For an excellent info please read the <a href="http://en.wikipedia.org/wiki/Avl_tree">Wikipedia
article on AVL tree</a>.
+	 * 
+	 * @param treePath the traversed list of LinkedAvlNodes after performing an insert/delete
operation.
+	 */
+	private void balance( List<LinkedAvlNode<K>> treePath )
+	{
+	    LinkedAvlNode<K> parentNode = null;
+	    
+	    if(root.getHeight() <= 2)
+	    {
+	        return;
+	    }
+	    
+	    int size = treePath.size();
+	    
+	    for( LinkedAvlNode<K> node: treePath )
+	    {
+	        int balFactor = getBalance( node );
+
+            if( node != root )
+            {
+                if( treePath.indexOf( node ) < ( size - 1 ) )
+                    parentNode = treePath.get( treePath.indexOf( node ) + 1 );
+            }
+
+	        if( balFactor > 1 )
+	        {
+	            if( getBalance( node.right ) <= -1)
+	            {
+	                //------rotate double-left--------
+	                rotateSingleRight( node.right, node );
+	                rotateSingleLeft( node, parentNode );
+	            }
+	            else // rotate single-left
+	            {
+	               rotateSingleLeft( node, parentNode );
+	            }
+	        }
+	        else if( balFactor < -1 )
+	        {
+	            if( getBalance( node.left ) >= 1)
+	            {
+	               //------rotate double-right--------
+	               rotateSingleLeft( node.left, node ); 
+	               rotateSingleRight( node, parentNode );
+	            }
+	            else
+	            {
+	                rotateSingleRight( node, parentNode );
+	            }
+	        }
+	    }
+	}
+	
+
+	/**
+     * Tests if the tree is logically empty.
+     * 
+     * @return true if the tree is empty, false otherwise
+     */
+    public boolean isEmpty()
+    {
+      return root == null;   
+    }
+
+    
+    public LinkedAvlNode<K> getRoot()
+    {
+        return root;
+    }
+    
+
+    /**
+     * Prints the contents of AVL tree in pretty format
+     */
+    public void printTree() {
+        
+        if( isEmpty() )
+        {
+            System.out.println( "Tree is empty" );
+            return;
+        }
+        
+        getRoot().setDepth( 0 );
+
+        System.out.println( getRoot() );
+        
+        visit( getRoot().getRight(), getRoot() );
+        
+        visit( getRoot().getLeft(), getRoot() );
+    }
+    
+
+    //-------------- private methods ----------
+    
+	/**
+	 * Rotate the node left side once.
+	 *
+	 * @param node the LinkedAvlNode to be rotated
+	 * @param parentNode parent LinkedAvlNode of node
+	 */
+	private void rotateSingleLeft(LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode)
+	{
+	    LinkedAvlNode<K> temp;
+	    //------rotate single-left--------
+        
+        temp = node.right;
+        node.right = temp.left;
+        temp.left = node;
+        
+        if( node == root )
+        {
+          root = temp;  
+        }
+        else if( parentNode != null )
+        {
+            if( parentNode.left != null )
+            {
+                parentNode.left = temp;
+            }
+            else
+            {
+                parentNode.right = temp;
+            }
+        }
+	}
+	
+	
+	/**
+     * Rotate the node right side once.
+     *
+     * @param node the LinkedAvlNode to be rotated
+     * @param parentNode parent LinkedAvlNode of node
+     */
+	private void rotateSingleRight(LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode)
+	{
+	    LinkedAvlNode<K> temp;
+        //------rotate single-right--------
+        
+        temp = node.left;
+        node.left = temp.right;
+        temp.right = node;
+       
+        if( node == root )
+        {
+          root = temp;  
+        }
+        else if( parentNode != null )
+        {
+            if( parentNode.left != null )
+            {
+                parentNode.left = temp;
+            }
+            else
+            {
+                parentNode.right = temp;
+            }
+        }
+	}
+		
+
+	/**
+	 * Detach a LinkedAvlNode from its parent
+	 *
+	 * @param node the LinkedAvlNode to be detached
+	 * @param parentNode the parent LinkedAvlNode of the node
+	 */
+	private void detachNodes(LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode)
+	{
+	    if( parentNode != null )
+	    {
+	        if( node == parentNode.left )
+	        {
+	            parentNode.left = null;
+	        }
+	        else if( node == parentNode.right )
+	        {
+	            parentNode.right = null;
+	        }
+	    }
+	}
+
+
+	/**
+	 * 
+	 * Replace a LinkedAvlNode to be removed with a new existing LinkedAvlNode 
+	 *
+	 * @param deleteNode the LinkedAvlNode to be deleted
+	 * @param replaceNode the LinkedAvlNode to replace the deleteNode
+	 * @param parentNode the parent LinkedAvlNode of deleteNode
+	 */
+    private void replaceNode(LinkedAvlNode<K> deleteNode, LinkedAvlNode<K> replaceNode,
LinkedAvlNode<K> parentNode)
+    {
+        if( parentNode != null )
+        {
+            if( deleteNode == parentNode.left )
+            {
+                parentNode.left = replaceNode;
+            }
+            else if( deleteNode == parentNode.right )
+            {
+                parentNode.right = replaceNode;
+            }
+        }
+    }
+    
+    
+    /**
+     * 
+     * Find a LinkedAvlNode with the given key value in the tree starting from the startNode.
+     *
+     * @param key the key to find
+     * @param startNode starting node of a subtree/tree
+     * @param path the list to be filled with traversed nodes
+     * @return the list of traversed LinkedAvlNodes.
+     */
+    private List<LinkedAvlNode<K>> find( K key, LinkedAvlNode<K> startNode,
List<LinkedAvlNode<K>> path )
+    {
+        int c;
+        
+        if( startNode == null )
+        {
+            return null;
+        }
+        
+        path.add( 0, startNode );
+        c = comparator.compare( key, startNode.key );
+        
+        if( c == 0 )
+        {
+            return path;
+        }
+        else if( c > 0 )
+        {
+            return find( key, startNode.right, path );
+        }
+        else if( c < 0 )
+        {
+            return find( key, startNode.left, path );
+        }
+        
+        return null;
+    }
+	
+    
+    /**
+     * Find the LinkedAvlNode having the max key value in the tree starting from the startNode.
+     *
+     * @param startNode starting node of a subtree/tree
+     * @return the list of traversed LinkedAvlNodes.
+     */
+	private List<LinkedAvlNode<K>> findMax( LinkedAvlNode<K> startNode )
+	{
+	    LinkedAvlNode<K> x = startNode;
+	    LinkedAvlNode<K> y = null;
+	    List<LinkedAvlNode<K>> path;
+	    
+	    if( x == null )
+	    {
+	        return null;
+	    }
+	    
+	    while( x.right != null )
+	    {
+	        y = x;
+	        x = x.right;
+	    }
+	    
+	    path = new ArrayList<LinkedAvlNode<K>>(2);
+	    path.add( x );
+	    
+	    if ( y != null )
+	    {
+	      path.add( y );  
+	    }
+	    
+	    return path;
+	}
+
+	
+	/**
+     * Find the LinkedAvlNode having the min key value in the tree starting from the startNode.
+     *
+     * @param startNode starting node of a subtree/tree
+     * @return the list of traversed LinkedAvlNodes.
+     */
+    private List<LinkedAvlNode<K>> findMin( LinkedAvlNode<K> startNode
)
+    {
+        LinkedAvlNode<K> x = startNode;
+        LinkedAvlNode<K> y = null;
+        List<LinkedAvlNode<K>> path;
+       
+        if( x == null )
+        {
+            return null;
+        }
+       
+        while( x.left != null )
+        {
+            y = x;
+            x = x.left;
+        }
+        
+        path = new ArrayList<LinkedAvlNode<K>>(2);
+        path.add( x );
+        
+        if ( y != null )
+        {
+          path.add( y );  
+        }
+        
+        return path;
+    }
+   
+    
+    /**
+     * Get balance-factor of the given LinkedAvlNode.
+     *
+     * @param node a LinkedAvlNode 
+     * @return balance-factor of the node
+     */
+	private int getBalance( LinkedAvlNode<K> node )
+	{
+	    int rh = ( node.right == null ? 0 : node.right.getHeight() );
+	    int lh = ( node.left == null ? 0 : node.left.getHeight() );
+	    
+	    return ( rh - lh );
+	}
+	
+    
+    private void visit( LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode )

+    {
+        if( node == null )
+        {
+            return;
+        }
+        
+        if( !node.isLeaf() )
+        {
+            node.setDepth( parentNode.getDepth() + 1 );
+        }
+        
+        for( int i=0; i < parentNode.getDepth(); i++ )
+        {
+            System.out.print( "|  " );
+        }
+
+        String type = "";
+        if( node == parentNode.left )
+        {
+            type = "L";
+        }
+        else if( node == parentNode.right )
+        {
+            type = "R";
+        }
+        
+        System.out.println( "|--" + node + type );
+        
+        if ( node.getRight() != null )
+        {
+            visit( node.getRight(), node );
+        }
+        
+        if( node.getLeft() != null )
+        {
+            visit( node.getLeft(), node );
+        }
+    }
+}

Added: directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/avltree/LinkedAvlNode.java
URL: http://svn.apache.org/viewvc/directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/avltree/LinkedAvlNode.java?rev=629205&view=auto
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/avltree/LinkedAvlNode.java
(added)
+++ directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/avltree/LinkedAvlNode.java
Tue Feb 19 11:44:43 2008
@@ -0,0 +1,105 @@
+/*
+ *   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;
+
+
+/**
+ * A linked AVL tree node.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $Rev$, $Date$
+ */
+public class LinkedAvlNode<T> 
+{
+    T key; // The data in the node
+    LinkedAvlNode<T> left; // Left child
+    LinkedAvlNode<T> right; // Right child
+    LinkedAvlNode<T> next;
+    LinkedAvlNode<T> previous;
+    
+    transient int depth;
+    
+    public LinkedAvlNode( T theKey )
+    {
+        key = theKey;
+        left = right = null;
+    }
+
+
+	public void setLeft( LinkedAvlNode<T> left )
+    {
+        this.left = left;
+    }
+
+
+    public void setRight( LinkedAvlNode<T> right )
+    {
+        this.right = right;
+    }
+
+
+    public LinkedAvlNode<T> getLeft() {
+		return left;
+	}
+
+
+	public LinkedAvlNode<T> getRight() {
+		return right;
+	}
+
+	public T getKey() {
+		return key;
+	}
+
+	public boolean isLeaf()
+	{
+		return ( right == null && left == null );
+	}
+	
+	public int getDepth() {
+		return depth;
+	}
+
+	public void setDepth( int depth ) {
+		this.depth = depth;
+	}
+
+	
+	public int getHeight()
+    {
+	    if(right == null && left == null)
+	    {
+	        return 1;
+	    }
+	    
+	    int lh = ( left == null ? -1 : left.getHeight() );
+	    int rh = ( right == null ? -1 : right.getHeight() );
+	    
+        return 1 + Math.max( lh, rh );
+    }
+
+
+    @Override
+	public String toString() {
+	    return "[" + key + "]";
+	}
+    
+    
+}

Added: 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=629205&view=auto
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/core/avltree/AVLTreeTest.java
(added)
+++ directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/core/avltree/AVLTreeTest.java
Tue Feb 19 11:44:43 2008
@@ -0,0 +1,204 @@
+/*
+ *   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;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.assertFalse;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.List;
+
+import org.junit.Before;
+import org.junit.Test;
+
+/**
+ * An AVL tree testcase.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $Rev$, $Date$
+ */
+public class AVLTreeTest
+{
+
+    AVLTree<Integer> tree;
+    
+    @Before
+    public void createTree()
+    {
+      tree = new AVLTree<Integer>( new Comparator<Integer>() 
+          {
+
+            public int compare( Integer i1, Integer i2 )
+            {
+                return i1.compareTo( i2 );
+            }
+          
+          });  
+    }
+    
+    @Test
+    public void testEmpty()
+    {
+      assertTrue( tree.isEmpty() );
+      
+      tree.remove( 97 ); // remove a non-existing key
+      assertTrue( tree.isEmpty() );
+    }
+    
+    
+    @Test
+    public void testInsert()
+    {
+        tree.insert( 3 );
+        assertFalse( tree.isEmpty() );
+        
+        tree.insert( 3 );// should be ignored
+        assertEquals( 1, tree.getRoot().getHeight() );
+    }
+    
+    
+    @Test
+    public void testSingleRightRotation()
+    {
+     // right rotation
+      tree.insert( 3 );
+      tree.insert( 2 );
+      tree.insert( 1 );
+      
+      assertEquals("1,2,3", getInorderForm());
+    }
+
+    @Test
+    public void testSingleLeftRotation()
+    {
+     // left rotation
+      tree.insert( 1 );
+      tree.insert( 2 );
+      tree.insert( 3 );
+      
+      assertEquals("1,2,3", getInorderForm());
+    }
+
+    
+    @Test
+    public void testDoubleLeftRotation() // left-right totation
+    {
+     // double left rotation
+      tree.insert( 1 );
+      tree.insert( 3 );
+      tree.insert( 2 );
+      
+      assertEquals("1,2,3", getInorderForm());
+    }
+    
+    @Test
+    public void testDoubleRightRotation() // right-left totation
+    {
+     // double left rotation
+      tree.insert( 3 );
+      tree.insert( 1 );
+      tree.insert( 2 );
+      assertEquals("1,2,3", getInorderForm());
+    }
+    
+    
+    @Test
+    public void testRemove()
+    {
+        tree.insert( 3 );
+        tree.insert( 2 );
+        tree.insert( 1 );
+        
+        tree.remove( 2 );
+        assertEquals("1,3", getInorderForm());
+        
+        tree.remove( 1 );
+        assertEquals("3", getInorderForm());
+        assertEquals( 3, tree.getRoot().key );
+        
+        tree.remove( 3 );
+        assertTrue(tree.isEmpty());
+        
+        tree.insert( 37 );
+        tree.insert( 39 );
+        tree.insert( 27 );
+        tree.insert( 38 );
+        tree.insert( 21 );
+        tree.insert( 26 );
+        tree.insert( 43 );
+        assertEquals( "21,26,27,37,38,39,43", getInorderForm() );
+
+        tree.remove( 26 ); // remove a non-root non-leaf node in the left sub tree of root
+        assertEquals( "21,27,37,38,39,43", getInorderForm() );
+        
+        tree.remove( 43 );
+        assertEquals( "21,27,37,38,39", getInorderForm() );
+        
+        tree.remove( 39 );
+        assertEquals( "21,27,37,38", getInorderForm() );
+        assertEquals( 37, tree.getRoot().key ); // check the root value
+        
+        tree.remove( 38 ); // a double right rotation has to happen after this
+        assertEquals( 27, tree.getRoot().key ); // check the root value after double right
rotation
+        assertEquals( "21,27,37", getInorderForm() );
+        
+        tree.printTree();
+    }
+
+
+    private String getInorderForm()
+    {
+      StringBuilder sb = new StringBuilder();
+      List<LinkedAvlNode<Integer>> path = new ArrayList<LinkedAvlNode<Integer>>();
+      
+      traverse( tree.getRoot(), path );
+      int i;
+      for( i=0; i < path.size() -1; i++ )
+      {
+          sb.append( path.get( i ).key )
+            .append( ',' );
+      }
+      
+      sb.append( path.get( i ).key );
+      
+      return sb.toString();
+    }
+    
+    private void traverse( LinkedAvlNode<Integer> startNode, List<LinkedAvlNode<Integer>>
path )
+    {
+      //1. pre-order
+        
+      if( startNode.left != null )
+      {
+          traverse( startNode.left, path );
+      }
+      
+      path.add( startNode ); //2. in-order NOTE: change this line's position to change the
type of traversal
+
+      if( startNode.right != null )
+      {
+         traverse( startNode.right, path ); 
+      }
+
+      //3. post-order
+    }
+}

Modified: directory/sandbox/akarasulu/bigbang/apacheds/pom.xml
URL: http://svn.apache.org/viewvc/directory/sandbox/akarasulu/bigbang/apacheds/pom.xml?rev=629205&r1=629204&r2=629205&view=diff
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/pom.xml (original)
+++ directory/sandbox/akarasulu/bigbang/apacheds/pom.xml Tue Feb 19 11:44:43 2008
@@ -336,6 +336,7 @@
     <module>core-entry</module>
     <module>core-cursor</module>
     <module>core-splay</module>
+    <module>core-avl</module>
     <module>protocol-shared</module>
     <module>protocol-ntp</module>
     <module>protocol-ldap</module>
@@ -567,6 +568,7 @@
         <module>core-unit</module>
         <module>core-entry</module>
         <module>core-splay</module>
+        <module>core-avl</module>
         <module>protocol-shared</module>
         <module>protocol-ntp</module>
         <module>protocol-ldap</module>



Mime
View raw message