You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@directory.apache.org by ka...@apache.org on 2009/08/29 14:19:42 UTC
svn commit: r809121 - in
/directory/apacheds/branches/apacheds-schema/core-avl: ./
src/main/java/org/apache/directory/server/core/avltree/
src/test/java/org/apache/directory/server/core/avltree/
Author: kayyagari
Date: Sat Aug 29 12:19:41 2009
New Revision: 809121
URL: http://svn.apache.org/viewvc?rev=809121&view=rev
Log:
o merged test cases according to the refactored AvlTree interface/impl
o added dependency on apacheds-xdbm-base
o added a cast in ArrayTreeMarshaller
Modified:
directory/apacheds/branches/apacheds-schema/core-avl/pom.xml
directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/ArrayMarshaller.java
directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlSingletonOrOrderedSetCursor.java
directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTree.java
directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeCursor.java
directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMapNoDupsWrapperCursor.java
directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMarshaller.java
directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/DefaultMarshaller.java
directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/KeyTupleAvlCursor.java
directory/apacheds/branches/apacheds-schema/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeCursorTest.java
directory/apacheds/branches/apacheds-schema/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMarshallerTest.java
directory/apacheds/branches/apacheds-schema/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreePerfTest.java
directory/apacheds/branches/apacheds-schema/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeTest.java
Modified: directory/apacheds/branches/apacheds-schema/core-avl/pom.xml
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-schema/core-avl/pom.xml?rev=809121&r1=809120&r2=809121&view=diff
==============================================================================
--- directory/apacheds/branches/apacheds-schema/core-avl/pom.xml (original)
+++ directory/apacheds/branches/apacheds-schema/core-avl/pom.xml Sat Aug 29 12:19:41 2009
@@ -38,6 +38,12 @@
<version>${org.apache.directory.shared.version}</version>
<artifactId>shared-cursor</artifactId>
</dependency>
+
+ <dependency>
+ <groupId>org.apache.directory.server</groupId>
+ <version>${pom.version}</version>
+ <artifactId>apacheds-xdbm-base</artifactId>
+ </dependency>
</dependencies>
</project>
Modified: directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/ArrayMarshaller.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/ArrayMarshaller.java?rev=809121&r1=809120&r2=809121&view=diff
==============================================================================
--- directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/ArrayMarshaller.java (original)
+++ directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/ArrayMarshaller.java Sat Aug 29 12:19:41 2009
@@ -79,7 +79,7 @@
public ArrayMarshaller( Comparator<E> comparator )
{
this.comparator = comparator;
- this.keyMarshaller = DefaultMarshaller.INSTANCE;
+ this.keyMarshaller = ( Marshaller<E> ) DefaultMarshaller.INSTANCE;
}
Modified: directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlSingletonOrOrderedSetCursor.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlSingletonOrOrderedSetCursor.java?rev=809121&r1=809120&r2=809121&view=diff
==============================================================================
--- directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlSingletonOrOrderedSetCursor.java (original)
+++ directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlSingletonOrOrderedSetCursor.java Sat Aug 29 12:19:41 2009
@@ -22,9 +22,9 @@
import java.util.Comparator;
-import org.apache.directory.server.core.cursor.InvalidCursorPositionException;
import org.apache.directory.server.xdbm.AbstractTupleCursor;
import org.apache.directory.server.xdbm.Tuple;
+import org.apache.directory.shared.ldap.cursor.InvalidCursorPositionException;
/**
Modified: directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTree.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTree.java?rev=809121&r1=809120&r2=809121&view=diff
==============================================================================
--- directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTree.java (original)
+++ directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTree.java Sat Aug 29 12:19:41 2009
@@ -20,52 +20,25 @@
package org.apache.directory.server.core.avltree;
-import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
/**
- * An AVL tree implementation
+ * The interface for an AVL Tree.
*
* @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
* @version $Rev$, $Date$
*/
-public class AvlTree<K>
+public interface AvlTree<K>
{
- /** the root of the tree */
- private LinkedAvlNode<K> root;
-
- /** The Comparator used for comparing the keys */
- private Comparator<K> comparator;
-
- /** node representing the start of the doubly linked list formed with the tree nodes */
- private LinkedAvlNode<K> first;
-
- /** node representing the end of the doubly linked list formed with the tree nodes */
- private LinkedAvlNode<K> last;
-
/**
- * Creates a new instance of AVLTree.
- *
- * @param comparator the comparator to be used for comparing keys
- */
- public AvlTree( Comparator<K> comparator)
- {
- this.comparator = comparator;
- }
-
-
- /**
* @return the comparator associated with this tree
*/
- public Comparator<K> getComparator()
- {
- return comparator;
- }
-
-
+ public abstract Comparator<K> getComparator();
+
+
/**
* Inserts a LinkedAvlNode with the given key.
*
@@ -73,608 +46,64 @@
* @return the replaced key if it already exists
* Note: Ignores if a node with the given key already exists.
*/
- public K insert( K key )
- {
- LinkedAvlNode<K> node, temp;
- LinkedAvlNode<K> parent = null;
- int c;
-
- if ( root == null )
- {
- root = new LinkedAvlNode<K>( key );
- first = root;
- last = root;
- return null;
- }
-
- 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; // key already exists
- }
-
- if( c < 0 )
- {
- temp.isLeft = true;
- temp = temp.getLeft();
- }
- else
- {
- temp.isLeft = false;
- temp = temp.getRight();
- }
- }
-
- if( ( c = comparator.compare( key, parent.getKey() ) ) < 0 )
- {
- parent.setLeft( node );
- }
- else
- {
- parent.setRight( node );
- }
-
- insertInList( node, parent, c );
-
- treePath.add( 0, node );
- balance(treePath);
-
- return null;
- }
-
-
- private void removeFromList(LinkedAvlNode<K> node)
- {
- if( node.next == null && node.previous == null ) // should happen in case of tree having single node
- {
- first = last = null;
- }
- else if( node.next == null ) // last node
- {
- node.previous.next = null;
- last = node.previous;
- }
- else if( node.previous == null ) // first node
- {
- node.next.previous = null;
- first = node.next;
- }
- else // somewhere in middle
- {
- node.previous.next = node.next;
- node.next.previous = node.previous;
- }
-
- }
-
-
- private void insertInList(LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode, int pos)
- {
-
- if( pos < 0 )
- {
- if( last == null )
- {
- last = parentNode;
- }
-
- if( parentNode.previous == null )
- {
- first = node;
- }
- else
- {
- parentNode.previous.next = node ;
- node.previous = parentNode.previous;
- }
-
- node.next = parentNode;
- parentNode.previous = node;
- }
- else if( pos > 0 )
- {
- if( parentNode.next == null )
- {
- last = node;
- }
- else
- {
- parentNode.next.previous = node;
- node.next = parentNode.next;
- }
- node.previous = parentNode;
- parentNode.next = node;
- }
-
- }
-
-
+ public abstract K insert( K key );
+
+
/**
* Removes the LinkedAvlNode present in the tree with the given key value
*
* @param key the value of the node to be removed
* @return the removed key, if any, or null if the key does not exist
*/
- public K remove( K key )
- {
- LinkedAvlNode<K> temp = null;
- LinkedAvlNode<K> y = null;
-
- List<LinkedAvlNode<K>> treePath = new ArrayList<LinkedAvlNode<K>>();
-
- treePath = find( key, root, treePath);
-
- if( treePath == null )
- {
- return null;
- }
-
- temp = treePath.remove( 0 );
-
- // remove from the doubly linked
- removeFromList(temp);
-
- if( temp.isLeaf() )
- {
- if( temp == root )
- {
- root = null;
- return key;
- }
-
- 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.remove( 0 ) );
- }
-
- leftTreePath.addAll( treePath );
- treePath = leftTreePath;
-
- y.right = temp.right; // assign the right here left will be assigned in replaceNode()
-
- 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.remove( 0 ) );
- }
-
- rightTreePath.addAll( treePath );
- treePath = rightTreePath;
-
- y.right = temp.right; // assign the right here left will be assigned in replaceNode()
-
- if( temp == root )
- {
- y.right = temp.right;
- root = y;
- }
- else
- {
- replaceNode( temp, y, treePath.get( 0 ) );
- }
- }
- }
-
- treePath.add( 0, y ); // y can be null but getBalance returns 0 so np
- balance( treePath );
-
- return key;
- }
-
-
- /**
- * 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 height 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;
-
- 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 );
- }
- }
- }
- }
-
+ public abstract K remove( K key );
+
/**
* Tests if the tree is logically empty.
*
* @return true if the tree is empty, false otherwise
*/
- public boolean isEmpty()
- {
- return root == null;
- }
+ public abstract boolean isEmpty();
+
-
/**
* returns the number of nodes present in this tree.
*
* @return the number of nodes present in this tree
*/
//NOTE: This method is internally used by AVLTreeMarshaller
- public int getSize()
- {
- if ( root == null )
- {
- return 0;
- }
-
- if( root.isLeaf() )
- {
- return 1;
- }
-
- LinkedAvlNode<K> x = first.next;
-
- while( x != null )
- {
- x.setIndex( x.previous.getIndex() + 1 );
- x = x.next;
- }
-
- return last.getIndex() + 1;
- }
-
-
- /**
- * Set the root of the tree.
- *
- * Note : this method is used by the deserialization method
- *
- * @param root the root of the tree
- */
- /* no protection */ void setRoot( LinkedAvlNode<K> root )
- {
- this.root = root;
- }
-
-
- /**
- * Set the first element of the tree
- *
- * Note : this method is used by the deserialization method
- *
- * @param first the first element to be added
- */
- /* no protection */ void setFirst( LinkedAvlNode<K> first )
- {
- this.first = first;
- }
-
-
- /**
- * Set the last element of the tree
- *
- * Note : this method is used by the deserialization method
- *
- * @param last the last element to be added
- */
- /* no protection */ void setLast( LinkedAvlNode<K> last )
- {
- this.last = last;
- }
+ public abstract int getSize();
/**
* @return the root element of this tree (ie, not the first, but the
* topmost element)
*/
- public LinkedAvlNode<K> getRoot()
- {
- return root;
- }
-
-
+ public abstract LinkedAvlNode<K> getRoot();
+
+
/**
* @return a list of the stored keys in this tree
*/
- public List<K> getKeys()
- {
- List<K> keys = new ArrayList<K>();
- LinkedAvlNode<K> node = first;
-
- while( node != null )
- {
- keys.add( node.key );
- node = node.next;
- }
-
- return keys;
- }
+ public abstract List<K> getKeys();
+
/**
* 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( null, getRoot().getRight(), getRoot() );
-
- visit( null, getRoot().getLeft(), getRoot() );
- }
-
+ public abstract void printTree();
- /**
- * @return The first element of this tree
- */
- public LinkedAvlNode<K> getFirst()
- {
- return first;
- }
-
/**
- * @return The last element in this tree
+ * @return The first element of this tree
*/
- public LinkedAvlNode<K> getLast()
- {
- return last;
- }
+ public abstract LinkedAvlNode<K> getFirst();
-
- /**
- * 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 == node )
- {
- parentNode.left = temp;
- }
- else if( parentNode.right == node )
- {
- 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 == node )
- {
- parentNode.left = temp;
- }
- else if( parentNode.right == node )
- {
- parentNode.right = temp;
- }
- }
- /*
- when the 'parentNode' param is null then the node under rotation is a child of ROOT.
- Most likely this condition executes when the root node is deleted and balancing is required.
- */
- else if( root != null )
- {
- if( root.left == node )
- {
- root.left = temp;
- }
- // no need to check for right node
- }
- }
-
/**
- * Detach a LinkedAvlNode from its parent
- *
- * @param node the LinkedAvlNode to be detached
- * @param parentNode the parent LinkedAvlNode of the node
+ * @return The last element in this tree
*/
- private void detachNodes(LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode)
- {
- if( parentNode != null )
- {
- if( node == parentNode.left )
- {
- parentNode.left = node.left;
- }
- else if( node == parentNode.right )
- {
- parentNode.right = node.left;
- }
- }
- }
-
-
- /**
- *
- * 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 )
- {
- replaceNode.left = deleteNode.left;
-
- 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;
- }
+ public abstract LinkedAvlNode<K> getLast();
/**
@@ -684,21 +113,7 @@
* @return the LinkedAvlNode<K> whose key is greater than the given key ,<br>
* null if there is no node with a higher key than the given key.
*/
- public LinkedAvlNode<K> findGreater( K key )
- {
- LinkedAvlNode<K> result = fetchNonNullNode( key, root, root);
-
- if( result == null )
- {
- return null;
- }
- else if( comparator.compare( key, result.key ) < 0 )
- {
- return result;
- }
-
- return result.next;
- }
+ public abstract LinkedAvlNode<K> findGreater( K key );
/**
@@ -708,21 +123,7 @@
* @return the LinkedAvlNode<K> whose key is greater than the given key ,<br>
* null if there is no node with a higher key than the given key.
*/
- public LinkedAvlNode<K> findGreaterOrEqual( K key )
- {
- LinkedAvlNode<K> result = fetchNonNullNode( key, root, root);
-
- if( result == null )
- {
- return null;
- }
- else if( comparator.compare( key, result.key ) <= 0 )
- {
- return result;
- }
-
- return result.next;
- }
+ public abstract LinkedAvlNode<K> findGreaterOrEqual( K key );
/**
@@ -732,21 +133,7 @@
* @return the LinkedAvlNode<K> whose key is lower than the given key ,<br>
* null if there is no node with a lower key than the given key.
*/
- public LinkedAvlNode<K> findLess( K key )
- {
- LinkedAvlNode<K> result = fetchNonNullNode( key, root, root);
-
- if( result == null )
- {
- return null;
- }
- else if( comparator.compare( key, result.key ) > 0 )
- {
- return result;
- }
-
- return result.previous;
- }
+ public abstract LinkedAvlNode<K> findLess( K key );
/**
@@ -756,52 +143,9 @@
* @return the LinkedAvlNode<K> whose key is lower than the given key ,<br>
* null if there is no node with a lower key than the given key.
*/
- public LinkedAvlNode<K> findLessOrEqual( K key )
- {
- LinkedAvlNode<K> result = fetchNonNullNode( key, root, root);
-
- if( result == null )
- {
- return null;
- }
- else if( comparator.compare( key, result.key ) >= 0 )
- {
- return result;
- }
-
- return result.previous;
- }
-
-
- /*
- * This method returns the last visited non-null node in case if the node with the given key
- * is not present. This method should not be used as general purpose lookup method.
- * This is written to assist the findGreater, findLess methods.
- */
- private LinkedAvlNode<K> fetchNonNullNode( K key, LinkedAvlNode<K> startNode, LinkedAvlNode<K> parent )
- {
-
- if( startNode == null )
- {
- return parent;
- }
-
- int c = comparator.compare( key, startNode.key );
-
- parent = startNode;
-
- if( c > 0 )
- {
- return fetchNonNullNode( key, startNode.right, parent );
- }
- else if( c < 0 )
- {
- return fetchNonNullNode( key, startNode.left, parent );
- }
-
- return startNode;
- }
-
+ public abstract LinkedAvlNode<K> findLessOrEqual( K key );
+
+
/**
*
* Find a LinkedAvlNode with the given key value in the tree.
@@ -809,211 +153,6 @@
* @param key the key to find
* @return the list of traversed LinkedAvlNode.
*/
- public LinkedAvlNode<K> find( K key )
- {
- return find( key, root);
- }
-
-
- private LinkedAvlNode<K> find( K key, LinkedAvlNode<K> startNode)
- {
- int c;
-
- if( startNode == null )
- {
- return null;
- }
-
- c = comparator.compare( key, startNode.key );
-
- if( c > 0 )
- {
- startNode.isLeft = false;
- return find( key, startNode.right );
- }
- else if( c < 0 )
- {
- startNode.isLeft = true;
- return find( key, startNode.left );
- }
-
- return startNode;
- }
-
-
- /**
- * 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 )
- {
- x.isLeft = false;
- y = x;
- x = x.right;
- }
-
- path = new ArrayList<LinkedAvlNode<K>>(2);
- path.add( x );
-
- if ( y != null )
- {
- path.add( y );
- }
-
- return path;
- }
+ public abstract LinkedAvlNode<K> find( K key );
-
- /**
- * 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 )
- {
- x.isLeft = true;
- 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 )
- {
- if( node == null)
- {
- return 0;
- }
-
- return node.getBalance();
- }
-
-
- /**
- * Checks that the tree is correct. It must be balanced, and the prev/next
- * chain must be equivalent to a depth-first descent on the tree
- *
- * @return true if the tree is balanced and correct
- */
- public boolean checkTree()
- {
- return true;
- }
-
-
- private void visit( StringBuilder sb, 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++ )
- {
- if ( sb != null )
- {
- sb.append( "| " );
- }
- else
- {
- System.out.print( "| " );
- }
- }
-
- String type = "";
-
- if( node == parentNode.left )
- {
- type = "L";
- }
- else if( node == parentNode.right )
- {
- type = "R";
- }
-
- if ( sb != null )
- {
- sb.append( "|--" ).append( node ).append( type ).append( '\n' );
- }
- else
- {
- System.out.println( "|--" + node + type );
- }
-
- if ( node.getRight() != null )
- {
- visit( sb, node.getRight(), node );
- }
-
- if( node.getLeft() != null )
- {
- visit( sb, node.getLeft(), node );
- }
- }
-
- public String toString()
- {
- if( isEmpty() )
- {
- return "[]";
- }
-
- getRoot().setDepth( 0 );
-
- StringBuilder sb = new StringBuilder();
-
- sb.append( getRoot() );
-
- visit( sb, getRoot().getRight(), getRoot() );
-
- visit( sb, getRoot().getLeft(), getRoot() );
-
- return sb.toString();
- }
-}
+}
\ No newline at end of file
Modified: directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeCursor.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeCursor.java?rev=809121&r1=809120&r2=809121&view=diff
==============================================================================
--- directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeCursor.java (original)
+++ directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeCursor.java Sat Aug 29 12:19:41 2009
@@ -19,12 +19,11 @@
*/
package org.apache.directory.server.core.avltree;
+
import org.apache.directory.shared.ldap.cursor.AbstractCursor;
import org.apache.directory.shared.ldap.cursor.InvalidCursorPositionException;
-
-
/**
* A Cursor for an AvlTree.
*
Modified: directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMapNoDupsWrapperCursor.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMapNoDupsWrapperCursor.java?rev=809121&r1=809120&r2=809121&view=diff
==============================================================================
--- directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMapNoDupsWrapperCursor.java (original)
+++ directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMapNoDupsWrapperCursor.java Sat Aug 29 12:19:41 2009
@@ -19,9 +19,9 @@
*/
package org.apache.directory.server.core.avltree;
-import org.apache.directory.server.core.cursor.InvalidCursorPositionException;
import org.apache.directory.server.xdbm.AbstractTupleCursor;
import org.apache.directory.server.xdbm.Tuple;
+import org.apache.directory.shared.ldap.cursor.InvalidCursorPositionException;
/**
Modified: directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMarshaller.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMarshaller.java?rev=809121&r1=809120&r2=809121&view=diff
==============================================================================
--- directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMarshaller.java (original)
+++ directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMarshaller.java Sat Aug 29 12:19:41 2009
@@ -27,12 +27,6 @@
import java.io.IOException;
import java.util.Comparator;
-import org.apache.directory.shared.ldap.util.StringTools;
-import org.slf4j.Logger;
-import org.slf4j.LoggerFactory;
-
-import sun.reflect.Reflection;
-
/**
* Class to serialize the AvlTree node data.
@@ -43,9 +37,6 @@
@SuppressWarnings("unchecked")
public class AvlTreeMarshaller<E> implements Marshaller<AvlTree<E>>
{
- /** static logger */
- private static final Logger LOG = LoggerFactory.getLogger( AvlTreeMarshaller.class );
-
/** used for serialized form of an empty AvlTree */
private static final byte[] EMPTY_TREE = new byte[1];
@@ -113,18 +104,6 @@
writeTree( tree.getRoot(), out );
out.flush();
data = byteStream.toByteArray();
-
- // Try to deserialize, just to see
- try
- {
- deserialize( data );
- }
- catch (NullPointerException npe )
- {
- System.out.println( "Bad serialization, tree : [" + StringTools.dumpBytes( data ) + "]");
- throw npe;
- }
-
out.close();
}
catch( IOException e )
@@ -185,59 +164,49 @@
*/
public AvlTree<E> deserialize( byte[] data ) throws IOException
{
- LOG.debug( "Deserializing the tree, called by {}", Reflection.getCallerClass( 2 ).getSimpleName() );
+ if ( data == null || data.length == 0 )
+ {
+ throw new IOException( "Null or empty data array is invalid." );
+ }
- try
+ if ( data.length == 1 && data[0] == 0 )
{
- 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 );
-
- byte startByte = din.readByte();
-
- if( startByte != 0 )
- {
- throw new IOException("wrong AvlTree serialized data format");
- }
-
- int size = din.readInt();
-
- LinkedAvlNode[] nodes = new LinkedAvlNode[ size ];
- LinkedAvlNode<E> root = readTree( din, null, nodes );
-
- 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;
+ return new AvlTreeImpl<E>( comparator );
}
- catch (NullPointerException npe )
+
+ ByteArrayInputStream bin = new ByteArrayInputStream( data );
+ DataInputStream din = new DataInputStream( bin );
+
+ byte startByte = din.readByte();
+
+ if( startByte != 0 )
{
- System.out.println( "Bad tree : [" + StringTools.dumpBytes( data ) + "]");
- throw npe;
+ throw new IOException("wrong AvlTree serialized data format");
}
+
+ int size = din.readInt();
+
+ LinkedAvlNode[] nodes = new LinkedAvlNode[ size ];
+ LinkedAvlNode<E> root = readTree( din, null, nodes );
+
+ AvlTreeImpl<E> tree = new AvlTreeImpl<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;
}
Modified: directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/DefaultMarshaller.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/DefaultMarshaller.java?rev=809121&r1=809120&r2=809121&view=diff
==============================================================================
--- directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/DefaultMarshaller.java (original)
+++ directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/DefaultMarshaller.java Sat Aug 29 12:19:41 2009
@@ -19,6 +19,7 @@
*/
package org.apache.directory.server.core.avltree;
+
import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.IOException;
@@ -26,15 +27,13 @@
import java.io.ObjectOutputStream;
-
-
/**
- * A marshaller which uses default Java Serialization.
+ * A Marshaller which uses default Java Serialization.
*
* @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
* @version $Rev$
*/
-public class DefaultMarshaller implements Marshaller
+public class DefaultMarshaller implements Marshaller<Object>
{
public static final DefaultMarshaller INSTANCE = new DefaultMarshaller();
Modified: directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/KeyTupleAvlCursor.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/KeyTupleAvlCursor.java?rev=809121&r1=809120&r2=809121&view=diff
==============================================================================
--- directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/KeyTupleAvlCursor.java (original)
+++ directory/apacheds/branches/apacheds-schema/core-avl/src/main/java/org/apache/directory/server/core/avltree/KeyTupleAvlCursor.java Sat Aug 29 12:19:41 2009
@@ -19,10 +19,9 @@
package org.apache.directory.server.core.avltree;
-import org.apache.directory.server.core.cursor.InvalidCursorPositionException;
-import org.apache.directory.server.xdbm.Tuple;
import org.apache.directory.server.xdbm.AbstractTupleCursor;
-import org.apache.directory.server.core.avltree.AvlTreeCursor;
+import org.apache.directory.server.xdbm.Tuple;
+import org.apache.directory.shared.ldap.cursor.InvalidCursorPositionException;
/**
Modified: directory/apacheds/branches/apacheds-schema/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeCursorTest.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-schema/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeCursorTest.java?rev=809121&r1=809120&r2=809121&view=diff
==============================================================================
--- directory/apacheds/branches/apacheds-schema/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeCursorTest.java (original)
+++ directory/apacheds/branches/apacheds-schema/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeCursorTest.java Sat Aug 29 12:19:41 2009
@@ -42,7 +42,7 @@
@Test
public void testEmptyCursor() throws Exception
{
- AvlTree<Integer> tree = new AvlTree<Integer>( new IntegerComparator() );
+ AvlTree<Integer> tree = new AvlTreeImpl<Integer>( new IntegerComparator() );
AvlTreeCursor<Integer> cursor = new AvlTreeCursor<Integer>( tree );
assertFalse( cursor.isClosed() );
@@ -91,7 +91,7 @@
@Test
public void testOneEntryCursor() throws Exception
{
- AvlTree<Integer> tree = new AvlTree<Integer>( new IntegerComparator() );
+ AvlTree<Integer> tree = new AvlTreeImpl<Integer>( new IntegerComparator() );
tree.insert( 7 );
AvlTreeCursor<Integer> cursor = new AvlTreeCursor<Integer>( tree );
@@ -155,7 +155,7 @@
@Test
public void testManyEntriesCursor() throws Exception
{
- AvlTree<Integer> tree = new AvlTree<Integer>( new IntegerComparator() );
+ AvlTree<Integer> tree = new AvlTreeImpl<Integer>( new IntegerComparator() );
tree.insert( 3 );
tree.insert( 7 );
tree.insert( 10 );
Modified: directory/apacheds/branches/apacheds-schema/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMarshallerTest.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-schema/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMarshallerTest.java?rev=809121&r1=809120&r2=809121&view=diff
==============================================================================
--- directory/apacheds/branches/apacheds-schema/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMarshallerTest.java (original)
+++ directory/apacheds/branches/apacheds-schema/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMarshallerTest.java Sat Aug 29 12:19:41 2009
@@ -110,7 +110,7 @@
};
- tree = new AvlTree<Integer>( comparator );
+ tree = new AvlTreeImpl<Integer>( comparator );
treeMarshaller = new AvlTreeMarshaller<Integer>( comparator, new IntegerKeyMarshaller() );
}
@@ -164,7 +164,7 @@
@Test
public void testMarshalEmptyTree() throws IOException
{
- byte[] bites = treeMarshaller.serialize( new AvlTree<Integer>( comparator ) );
+ byte[] bites = treeMarshaller.serialize( new AvlTreeImpl<Integer>( comparator ) );
AvlTree<Integer> tree = treeMarshaller.deserialize( bites );
assertNotNull( tree );
}
@@ -173,7 +173,7 @@
@Test
public void testRoundTripEmpty() throws IOException
{
- AvlTree<Integer> original = new AvlTree<Integer>( comparator );
+ AvlTree<Integer> original = new AvlTreeImpl<Integer>( comparator );
byte[] bites = treeMarshaller.serialize( original );
AvlTree<Integer> deserialized = treeMarshaller.deserialize( bites );
assertTrue( deserialized.isEmpty() );
@@ -183,7 +183,7 @@
@Test
public void testRoundTripOneEntry() throws IOException
{
- AvlTree<Integer> original = new AvlTree<Integer>( comparator );
+ AvlTree<Integer> original = new AvlTreeImpl<Integer>( comparator );
original.insert( 0 );
byte[] bites = treeMarshaller.serialize( original );
AvlTree<Integer> deserialized = treeMarshaller.deserialize( bites );
@@ -196,7 +196,7 @@
@Test
public void testRoundTripOneEntryFirstLast() throws IOException
{
- AvlTree<Integer> original = new AvlTree<Integer>( comparator );
+ AvlTree<Integer> original = new AvlTreeImpl<Integer>( comparator );
original.insert( 0 );
byte[] bites = treeMarshaller.serialize( original );
AvlTree<Integer> deserialized = treeMarshaller.deserialize( bites );
@@ -222,7 +222,7 @@
@Test
public void testRoundTripTwoEntries() throws IOException
{
- AvlTree<Integer> original = new AvlTree<Integer>( comparator );
+ AvlTree<Integer> original = new AvlTreeImpl<Integer>( comparator );
original.insert( 0 );
original.insert( 1 );
byte[] bites = treeMarshaller.serialize( original );
@@ -237,7 +237,7 @@
@Test
public void testRoundTripTwoEntriesFirstLast() throws IOException
{
- AvlTree<Integer> original = new AvlTree<Integer>( comparator );
+ AvlTree<Integer> original = new AvlTreeImpl<Integer>( comparator );
original.insert( 0 );
original.insert( 1 );
byte[] bites = treeMarshaller.serialize( original );
@@ -265,7 +265,7 @@
@Test
public void testRoundTripManyEntries() throws Exception
{
- AvlTree<Integer> original = new AvlTree<Integer>( comparator );
+ AvlTree<Integer> original = new AvlTreeImpl<Integer>( comparator );
for ( int ii = 0; ii < 100; ii++ )
{
original.insert( ii );
@@ -288,7 +288,7 @@
@Test
public void testRoundTripManyEntriesFirstLast() throws Exception
{
- AvlTree<Integer> original = new AvlTree<Integer>( comparator );
+ AvlTree<Integer> original = new AvlTreeImpl<Integer>( comparator );
for ( int ii = 0; ii < 100; ii++ )
{
original.insert( ii );
@@ -331,7 +331,7 @@
}
};
- AvlTree<Bar> original = new AvlTree<Bar>( barComparator );
+ AvlTree<Bar> original = new AvlTreeImpl<Bar>( barComparator );
for ( int ii = 0; ii < 100; ii++ )
{
Modified: directory/apacheds/branches/apacheds-schema/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreePerfTest.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-schema/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreePerfTest.java?rev=809121&r1=809120&r2=809121&view=diff
==============================================================================
--- directory/apacheds/branches/apacheds-schema/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreePerfTest.java (original)
+++ directory/apacheds/branches/apacheds-schema/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreePerfTest.java Sat Aug 29 12:19:41 2009
@@ -74,7 +74,7 @@
@Before
public void createTree()
{
- tree = new AvlTree<Integer>( new Comparator<Integer>()
+ tree = new AvlTreeImpl<Integer>( new Comparator<Integer>()
{
public int compare( Integer i1, Integer i2 )
Modified: directory/apacheds/branches/apacheds-schema/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeTest.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-schema/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeTest.java?rev=809121&r1=809120&r2=809121&view=diff
==============================================================================
--- directory/apacheds/branches/apacheds-schema/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeTest.java (original)
+++ directory/apacheds/branches/apacheds-schema/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeTest.java Sat Aug 29 12:19:41 2009
@@ -50,7 +50,7 @@
@Before
public void createTree()
{
- tree = new AvlTree<Integer>( new Comparator<Integer>()
+ tree = new AvlTreeImpl<Integer>( new Comparator<Integer>()
{
public int compare( Integer i1, Integer i2 )
@@ -294,7 +294,7 @@
assertNotNull( tree.find( 11 ) );
assertNull( tree.find( 0 ));
- tree.setRoot( null );
+ ( ( AvlTreeImpl ) tree ).setRoot( null );
assertNull( tree.find( 3 ));
}