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/03/31 10:27:23 UTC
svn commit: r760365 - in
/directory/apacheds/branches/ldif-partition/core-avl/src:
main/java/org/apache/directory/server/core/avltree/
test/java/org/apache/directory/server/core/avltree/
Author: kayyagari
Date: Tue Mar 31 08:27:22 2009
New Revision: 760365
URL: http://svn.apache.org/viewvc?rev=760365&view=rev
Log:
initial drop of AvlTreeMap implementation
Added:
directory/apacheds/branches/ldif-partition/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMap.java
directory/apacheds/branches/ldif-partition/core-avl/src/main/java/org/apache/directory/server/core/avltree/LinkedAvlMapNode.java
directory/apacheds/branches/ldif-partition/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMapTest.java
Added: directory/apacheds/branches/ldif-partition/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMap.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/ldif-partition/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMap.java?rev=760365&view=auto
==============================================================================
--- directory/apacheds/branches/ldif-partition/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMap.java (added)
+++ directory/apacheds/branches/ldif-partition/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMap.java Tue Mar 31 08:27:22 2009
@@ -0,0 +1,1080 @@
+/*
+ * 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 with support to store both key and value.
+ * This implementation also supports duplicate keys. The values of a same key
+ * will be stored in a AvlTree.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $Rev$, $Date$
+ */
+public class AvlTreeMap<K,V>
+{
+ /** the root of the tree */
+ private LinkedAvlMapNode<K,V> root;
+
+ /** The Comparator used for comparing the keys */
+ private Comparator<K> keyComparator;
+
+ /** The Comparator used for comparing the values */
+ private Comparator<V> valueComparator;
+
+ /** node representing the start of the doubly linked list formed with the tree nodes */
+ private LinkedAvlMapNode<K,V> first;
+
+ /** node representing the end of the doubly linked list formed with the tree nodes */
+ private LinkedAvlMapNode<K,V> last;
+
+
+ /**
+ * Creates a new instance of AVLTree.
+ *
+ * @param comparator1 the comparator to be used for comparing keys
+ */
+ public AvlTreeMap( Comparator<K> keyComparator, Comparator<V> valueComparator )
+ {
+ this.keyComparator = keyComparator;
+ this.valueComparator = valueComparator;
+ }
+
+
+ /**
+ * @return the key comparator associated with this tree
+ */
+ public Comparator<K> getKeyComparator()
+ {
+ return keyComparator;
+ }
+
+
+ /**
+ * @return the value comparator associated with this tree
+ */
+ public Comparator<V> getValueComparator()
+ {
+ return valueComparator;
+ }
+
+
+ /**
+ * Inserts a LinkedAvlMapNode with the given key and value.
+ *
+ * @param key the item to be inserted
+ * @return the replaced key if it already exists
+ * Note: Ignores if a node with the given key already exists.
+ */
+ public K insert( K key, V value )
+ {
+ LinkedAvlMapNode<K,V> node, temp;
+ LinkedAvlMapNode<K,V> parent = null;
+ int c;
+
+ if ( root == null )
+ {
+ root = new LinkedAvlMapNode<K,V>( key, value );
+ first = root;
+ last = root;
+ return null;
+ }
+
+ node = new LinkedAvlMapNode<K,V>( key, value );
+
+ temp = root;
+
+ List<LinkedAvlMapNode<K,V>> treePath = new ArrayList<LinkedAvlMapNode<K,V>>();
+
+ while( temp != null )
+ {
+ treePath.add(0, temp ); // last node first, for the sake of balance factor computation
+ parent = temp;
+
+ c = keyComparator.compare( key, temp.getKey() );
+
+ if( c == 0 )
+ {
+ return insertDupKey( key, value, temp ); // key already exists add another value
+ }
+
+ if( c < 0 )
+ {
+ temp.isLeft = true;
+ temp = temp.getLeft();
+ }
+ else
+ {
+ temp.isLeft = false;
+ temp = temp.getRight();
+ }
+ }
+
+ if( ( c = keyComparator.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 K insertDupKey( K key, V value, LinkedAvlMapNode existingNode )
+ {
+ AvlTree<V> dupsTree = null;
+
+ if( existingNode.value instanceof AvlTree )
+ {
+ dupsTree = ( AvlTree<V> ) existingNode.value;
+ }
+ else
+ {
+ dupsTree = new AvlTree<V>( valueComparator );
+ dupsTree.insert( ( V ) existingNode.value );
+ existingNode.value = dupsTree;
+ }
+
+ // check if value already exists
+ if( dupsTree.find( value ) != null )
+ {
+ return key;
+ }
+
+ // insert value into duplicate key holder
+ dupsTree.insert( value );
+
+ return null;
+ }
+
+
+ private void removeFromList(LinkedAvlMapNode<K,V> 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(LinkedAvlMapNode<K,V> node, LinkedAvlMapNode<K,V> 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;
+ }
+
+ }
+
+
+ /**
+ * Removes the LinkedAvlMapNode present in the tree with the given key and value
+ *
+ * @param key the key of the node to be removed
+ * @param value the value of the node, if null the entire node will be removed
+ * including any values having the same key
+ * @return the removed key, if any, or null if the key does not exist
+ */
+ public K remove( K key, V value )
+ {
+ LinkedAvlMapNode<K,V> temp = null;
+ LinkedAvlMapNode<K,V> y = null;
+
+ List<LinkedAvlMapNode<K,V>> treePath = new ArrayList<LinkedAvlMapNode<K,V>>();
+
+ treePath = find( key, root, treePath);
+
+ if( treePath == null )
+ {
+ return null;
+ }
+
+ temp = treePath.remove( 0 );
+
+ // check if the value matches
+ if( value != null )
+ {
+ if( temp.value instanceof AvlTree )
+ {
+ AvlTree<V> dupsTree = ( AvlTree<V> ) temp.value;
+ V removedVal = dupsTree.remove( value );
+
+ // if the removal is successful and the tree is not empty
+ // we don't need to balance the tree, cause just one value
+ // of the same key was removed
+ // if the tree is empty because of the removal, the entire
+ // node will be removed which might require balancing, so we continue
+ // further down in this function
+ if( ( removedVal != null ) && ! dupsTree.isEmpty() )
+ {
+ return key;//no need to balance
+ }
+ }
+ else
+ {
+ if( valueComparator.compare( temp.value, value ) != 0 )
+ {
+ return null;// no need to balance
+ }
+ }
+ }
+
+ // 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<LinkedAvlMapNode<K,V>> 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<LinkedAvlMapNode<K,V>> 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<LinkedAvlMapNode<K,V>> treePath )
+ {
+ LinkedAvlMapNode<K,V> parentNode = null;
+
+ int size = treePath.size();
+
+ for( LinkedAvlMapNode<K,V> 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;
+ }
+
+
+ /**
+ * 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;
+ }
+
+ LinkedAvlMapNode<K,V> 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( LinkedAvlMapNode<K,V> 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( LinkedAvlMapNode<K,V> 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( LinkedAvlMapNode<K,V> last )
+ {
+ this.last = last;
+ }
+
+
+ /**
+ * @return the root element of this tree (ie, not the first, but the
+ * topmost element)
+ */
+ public LinkedAvlMapNode<K,V> getRoot()
+ {
+ return root;
+ }
+
+
+ /**
+ * @return a list of the stored keys in this tree
+ */
+ public List<K> getKeys()
+ {
+ List<K> keys = new ArrayList<K>();
+ LinkedAvlMapNode<K,V> node = first;
+
+ while( node != null )
+ {
+ keys.add( node.key );
+ node = node.next;
+ }
+
+ return keys;
+ }
+
+ /**
+ * 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() );
+ }
+
+
+ /**
+ * @return The first element of this tree
+ */
+ public LinkedAvlMapNode<K,V> getFirst()
+ {
+ return first;
+ }
+
+
+ /**
+ * @return The last element in this tree
+ */
+ public LinkedAvlMapNode<K,V> getLast()
+ {
+ return last;
+ }
+
+
+ /**
+ * Rotate the node left side once.
+ *
+ * @param node the LinkedAvlNode to be rotated
+ * @param parentNode parent LinkedAvlNode of node
+ */
+ private void rotateSingleLeft(LinkedAvlMapNode<K,V> node, LinkedAvlMapNode<K,V> parentNode)
+ {
+ LinkedAvlMapNode<K,V> 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(LinkedAvlMapNode<K,V> node, LinkedAvlMapNode<K,V> parentNode)
+ {
+ LinkedAvlMapNode<K,V> 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
+ */
+ private void detachNodes(LinkedAvlMapNode<K,V> node, LinkedAvlMapNode<K,V> 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(LinkedAvlMapNode<K,V> deleteNode, LinkedAvlMapNode<K,V> replaceNode, LinkedAvlMapNode<K,V> 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<LinkedAvlMapNode<K,V>> find( K key, LinkedAvlMapNode<K,V> startNode, List<LinkedAvlMapNode<K,V>> path )
+ {
+ int c;
+
+ if( startNode == null )
+ {
+ return null;
+ }
+
+ path.add( 0, startNode );
+ c = keyComparator.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;
+ }
+
+
+ /**
+ * Finds a LinkedAvlMapNode<K,V> whose key is higher than the given key.
+ *
+ * @param key the key
+ * @return the LinkedAvlMapNode<K,V> whose key is greater than the given key ,<br>
+ * null if there is no node with a higher key than the given key.
+ */
+ public LinkedAvlMapNode<K,V> findGreater( K key )
+ {
+ LinkedAvlMapNode<K,V> result = fetchNonNullNode( key, root, root);
+
+ if( result == null )
+ {
+ return null;
+ }
+ else if( keyComparator.compare( key, result.key ) < 0 )
+ {
+ return result;
+ }
+
+ return result.next;
+ }
+
+
+ /**
+ * Finds a LinkedAvlMapNode<K,V> whose key is higher than the given key.
+ *
+ * @param key the key
+ * @return the LinkedAvlMapNode<K,V> whose key is greater than the given key ,<br>
+ * null if there is no node with a higher key than the given key.
+ */
+ public LinkedAvlMapNode<K,V> findGreaterOrEqual( K key )
+ {
+ LinkedAvlMapNode<K,V> result = fetchNonNullNode( key, root, root);
+
+ if( result == null )
+ {
+ return null;
+ }
+ else if( keyComparator.compare( key, result.key ) <= 0 )
+ {
+ return result;
+ }
+
+ return result.next;
+ }
+
+
+ /**
+ * Finds a LinkedAvlMapNode<K,V> whose key is lower than the given key.
+ *
+ * @param key the key
+ * @return the LinkedAvlMapNode<K,V> whose key is lower than the given key ,<br>
+ * null if there is no node with a lower key than the given key.
+ */
+ public LinkedAvlMapNode<K,V> findLess( K key )
+ {
+ LinkedAvlMapNode<K,V> result = fetchNonNullNode( key, root, root);
+
+ if( result == null )
+ {
+ return null;
+ }
+ else if( keyComparator.compare( key, result.key ) > 0 )
+ {
+ return result;
+ }
+
+ return result.previous;
+ }
+
+
+ /**
+ * Finds a LinkedAvlMapNode<K,V> whose key is lower than the given key.
+ *
+ * @param key the key
+ * @return the LinkedAvlMapNode<K,V> whose key is lower than the given key ,<br>
+ * null if there is no node with a lower key than the given key.
+ */
+ public LinkedAvlMapNode<K,V> findLessOrEqual( K key )
+ {
+ LinkedAvlMapNode<K,V> result = fetchNonNullNode( key, root, root);
+
+ if( result == null )
+ {
+ return null;
+ }
+ else if( keyComparator.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 LinkedAvlMapNode<K,V> fetchNonNullNode( K key, LinkedAvlMapNode<K,V> startNode, LinkedAvlMapNode<K,V> parent )
+ {
+
+ if( startNode == null )
+ {
+ return parent;
+ }
+
+ int c = keyComparator.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;
+ }
+
+ /**
+ *
+ * Find a LinkedAvlNode with the given key value in the tree.
+ *
+ * @param key the key to find
+ * @return the list of traversed LinkedAvlNode.
+ */
+ public LinkedAvlMapNode<K,V> find( K key )
+ {
+ return find( key, root);
+ }
+
+
+ public LinkedAvlMapNode<K,V> find( K key, V value )
+ {
+ if( key == null || value == null )
+ {
+ return null;
+ }
+
+ LinkedAvlMapNode<K,V> node = find( key, root);
+
+ if( node == null )
+ {
+ return null;
+ }
+
+ if( node.value instanceof AvlTree )
+ {
+ AvlTree<V> dupsTree = ( AvlTree<V> ) node.value;
+
+ if( dupsTree.find( value ) == null )
+ {
+ return null;
+ }
+ }
+ else
+ {
+ if( valueComparator.compare( node.value, value ) != 0 )
+ {
+ return null;
+ }
+ }
+
+ return node;
+ }
+
+
+ private LinkedAvlMapNode<K,V> find( K key, LinkedAvlMapNode<K,V> startNode)
+ {
+ int c;
+
+ if( startNode == null )
+ {
+ return null;
+ }
+
+ c = keyComparator.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<LinkedAvlMapNode<K,V>> findMax( LinkedAvlMapNode<K,V> startNode )
+ {
+ LinkedAvlMapNode<K,V> x = startNode;
+ LinkedAvlMapNode<K,V> y = null;
+ List<LinkedAvlMapNode<K,V>> path;
+
+ if( x == null )
+ {
+ return null;
+ }
+
+ while( x.right != null )
+ {
+ x.isLeft = false;
+ y = x;
+ x = x.right;
+ }
+
+ path = new ArrayList<LinkedAvlMapNode<K,V>>(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<LinkedAvlMapNode<K,V>> findMin( LinkedAvlMapNode<K,V> startNode )
+ {
+ LinkedAvlMapNode<K,V> x = startNode;
+ LinkedAvlMapNode<K,V> y = null;
+ List<LinkedAvlMapNode<K,V>> path;
+
+ if( x == null )
+ {
+ return null;
+ }
+
+ while( x.left != null )
+ {
+ x.isLeft = true;
+ y = x;
+ x = x.left;
+ }
+
+ path = new ArrayList<LinkedAvlMapNode<K,V>>(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( LinkedAvlMapNode<K,V> node )
+ {
+ if( node == null)
+ {
+ return 0;
+ }
+
+ return node.getBalance();
+ }
+
+
+ private void visit( LinkedAvlMapNode<K,V> node, LinkedAvlMapNode<K,V> 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/apacheds/branches/ldif-partition/core-avl/src/main/java/org/apache/directory/server/core/avltree/LinkedAvlMapNode.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/ldif-partition/core-avl/src/main/java/org/apache/directory/server/core/avltree/LinkedAvlMapNode.java?rev=760365&view=auto
==============================================================================
--- directory/apacheds/branches/ldif-partition/core-avl/src/main/java/org/apache/directory/server/core/avltree/LinkedAvlMapNode.java (added)
+++ directory/apacheds/branches/ldif-partition/core-avl/src/main/java/org/apache/directory/server/core/avltree/LinkedAvlMapNode.java Tue Mar 31 08:27:22 2009
@@ -0,0 +1,209 @@
+/*
+ * 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 with support to store value along with a key.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $Rev$, $Date$
+ */
+public class LinkedAvlMapNode<K, V>
+{
+ /** The key stored in the node */
+ K key;
+
+ /** the value stored in the node */
+ V value;
+
+ /** The left child */
+ LinkedAvlMapNode<K, V> left;
+
+ /** The right child */
+ LinkedAvlMapNode<K, V> right;
+
+ /** The next node, superior to the current node */
+ LinkedAvlMapNode<K, V> next;
+
+ /** The previous node, inferior to the current node */
+ LinkedAvlMapNode<K, V> previous;
+
+ transient int depth;
+ transient int index;
+
+ boolean isLeft;
+ transient int height = 1;
+
+
+ /**
+ * Creates a new instance of LinkedAvlNode, containing a given value.
+ *
+ * @param theKey the stored value on the topmost node
+ */
+ public LinkedAvlMapNode( K theKey, V theValue )
+ {
+ key = theKey;
+ value = theValue;
+ left = null;
+ right = null;
+ }
+
+
+ public void setLeft( LinkedAvlMapNode<K, V> left )
+ {
+ this.left = left;
+ }
+
+
+ public void setRight( LinkedAvlMapNode<K, V> right )
+ {
+ this.right = right;
+ }
+
+
+ public LinkedAvlMapNode<K, V> getNext()
+ {
+ return next;
+ }
+
+
+ public LinkedAvlMapNode<K, V> getPrevious()
+ {
+ return previous;
+ }
+
+
+ public LinkedAvlMapNode<K, V> getLeft()
+ {
+ return left;
+ }
+
+
+ public LinkedAvlMapNode<K, V> getRight()
+ {
+ return right;
+ }
+
+
+ public K getKey()
+ {
+ return key;
+ }
+
+
+ public V getValue()
+ {
+ return value;
+ }
+
+
+ public boolean isLeaf()
+ {
+ return ( right == null && left == null );
+ }
+
+
+ public int getDepth()
+ {
+ return depth;
+ }
+
+
+ public void setDepth( int depth )
+ {
+ this.depth = depth;
+ }
+
+
+ public int getHeight()
+ {
+ return height;
+ }
+
+
+ public void setNext( LinkedAvlMapNode<K, V> next )
+ {
+ this.next = next;
+ }
+
+
+ public void setPrevious( LinkedAvlMapNode<K, V> previous )
+ {
+ this.previous = previous;
+ }
+
+
+ public int computeHeight()
+ {
+
+ if ( right == null && left == null )
+ {
+ height = 1;
+ return height;
+ }
+
+ int lh, rh;
+
+ if ( isLeft )
+ {
+ lh = ( left == null ? -1 : left.computeHeight() );
+ rh = ( right == null ? -1 : right.getHeight() );
+ }
+ else
+ {
+ rh = ( right == null ? -1 : right.computeHeight() );
+ lh = ( left == null ? -1 : left.getHeight() );
+ }
+
+ height = 1 + Math.max( lh, rh );
+
+ return height;
+ }
+
+
+ public int getBalance()
+ {
+ int lh = ( left == null ? 0 : left.computeHeight() );
+ int rh = ( right == null ? 0 : right.computeHeight() );
+
+ return ( rh - lh );
+ }
+
+
+ public int getIndex()
+ {
+ return index;
+ }
+
+
+ public void setIndex( int index )
+ {
+ this.index = index;
+ }
+
+
+ @Override
+ public String toString()
+ {
+ return "[" + key + ", [" + value + "]" + "]";
+ }
+
+}
Added: directory/apacheds/branches/ldif-partition/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMapTest.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/ldif-partition/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMapTest.java?rev=760365&view=auto
==============================================================================
--- directory/apacheds/branches/ldif-partition/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMapTest.java (added)
+++ directory/apacheds/branches/ldif-partition/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMapTest.java Tue Mar 31 08:27:22 2009
@@ -0,0 +1,321 @@
+/*
+ * 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 junit.framework.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertNull;
+import static org.junit.Assert.assertTrue;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.List;
+
+import org.junit.Before;
+import org.junit.Test;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+
+/**
+ * An AVLTreeMap testcase.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $Rev$, $Date$
+ */
+public class AvlTreeMapTest
+{
+
+ AvlTreeMap<Integer, Integer> tree;
+
+ private static final Logger LOG = LoggerFactory.getLogger( AvlTreeTest.class );
+
+
+ @Before
+ public void createTree()
+ {
+ Comparator<Integer> comparator = new Comparator<Integer>()
+ {
+
+ public int compare( Integer i1, Integer i2 )
+ {
+ return i1.compareTo( i2 );
+ }
+
+ };
+
+ tree = new AvlTreeMap<Integer, Integer>( comparator, comparator );
+ }
+
+
+ @Test
+ public void testEmpty()
+ {
+ assertTrue( tree.isEmpty() );
+ assertNull( tree.getFirst() );
+ assertNull( tree.getLast() );
+
+ tree.remove( 97, 0 ); // remove a non-existing key
+ assertTrue( tree.isEmpty() );
+
+ if ( LOG.isDebugEnabled() )
+ {
+ tree.printTree();
+ }
+ }
+
+
+ @Test
+ public void testFirstAndLast()
+ {
+ tree.insert( 7, 1 );
+ assertFalse( tree.isEmpty() );
+ assertNotNull( tree.getFirst() );
+ assertNotNull( tree.getLast() );
+ assertTrue( tree.getFirst().getKey().equals( 7 ) );
+ assertTrue( tree.getFirst().getValue().equals( 1 ) );
+
+ tree.insert( 10, 2 );
+ assertEquals( 2, tree.getSize() );
+ assertNotNull( tree.getFirst() );
+ assertNotNull( tree.getLast() );
+ assertFalse( tree.getFirst().equals( tree.getLast() ) );
+ assertTrue( tree.getFirst().getKey().equals( 7 ) );
+ assertTrue( tree.getLast().getKey().equals( 10 ) );
+
+ tree.insert( 3, 0 );
+ assertTrue( tree.getFirst().getKey().equals( 3 ) );
+ assertTrue( tree.getLast().getKey().equals( 10 ) );
+
+ tree.insert( 11, 1 );
+ assertTrue( tree.getFirst().getKey().equals( 3 ) );
+ assertTrue( tree.getLast().getKey().equals( 11 ) );
+ }
+
+
+ @Test
+ public void testInsert()
+ {
+ assertNull( tree.insert( 3, 1 ) );
+ assertFalse( tree.isEmpty() );
+
+ assertTrue( 3 == tree.insert( 3, 1 ) );// should be ignored
+ assertTrue( 1 == tree.getSize() );
+
+ assertNotNull( tree.getFirst() );
+ assertNotNull( tree.getLast() );
+ assertTrue( tree.getFirst() == tree.getLast() );
+
+ tree.remove( 3, 1 );
+
+ tree.insert( 37, 2 );
+ tree.insert( 70, 1 );
+ tree.insert( 12, 0 );
+ assertTrue( 3 == tree.getSize() );
+
+ tree.insert( 90, 3 );
+ tree.insert( 25, 0 );
+ tree.insert( 99, 7 );
+ tree.insert( 91, 5 );
+ tree.insert( 24, 3 );
+ tree.insert( 28, 4 );
+ tree.insert( 26, 5 );
+
+ if ( LOG.isDebugEnabled() )
+ {
+ tree.printTree();
+ }
+
+ tree.remove( 24, 3 ); // this causes a single left rotation on node with key 12
+ if ( LOG.isDebugEnabled() )
+ {
+ tree.printTree();
+ }
+ assertTrue( tree.getRoot().getLeft().key == 26 );
+ }
+
+
+ @Test
+ public void testDuplicateKeyInsert()
+ {
+ assertNull( tree.insert( 3, 1 ) );
+ assertNull( tree.insert( 3, 2 ) ); // duplicate key
+ assertNull( tree.insert( 3, 3 ) );
+ assertFalse( tree.isEmpty() );
+
+ if( LOG.isDebugEnabled() )
+ {
+ tree.printTree();
+ }
+
+ assertTrue( 3 == tree.insert( 3, 1 ) );// should be ignored
+ assertTrue( 1 == tree.getSize() );
+
+ LinkedAvlMapNode node = tree.find( 3 );
+ assertNotNull( node );
+
+ assertTrue( node.value.getClass() == AvlTree.class );
+
+ AvlTree dupsTree = ( AvlTree ) node.value;
+ assertEquals( 3, dupsTree.getSize() );
+ }
+
+
+ @Test
+ public void testRemove()
+ {
+ tree.insert( 3, 3 );
+ tree.insert( 2, 2 );
+ tree.insert( 1, 1 );
+
+ tree.remove( 2, 2 );
+ assertEquals("1,3", getInorderForm());
+
+ tree.remove( 1, 1 );
+ assertEquals("3", getInorderForm());
+ assertTrue( 3 == tree.getRoot().key );
+
+ assertNull( tree.remove( 777, 0 ) );// key not present
+ assertTrue( 3 == tree.remove( 3, null ) );
+ assertTrue(tree.isEmpty());
+
+ tree.insert( 37, 37 );
+ tree.insert( 39, 39 );
+ tree.insert( 27, 27 );
+ tree.insert( 38, 38 );
+ tree.insert( 21, 21 );
+ tree.insert( 26, 26 );
+ tree.insert( 43, 43 );
+ assertEquals( "21,26,27,37,38,39,43", getInorderForm() );
+
+ tree.remove( 26, 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, 43 );
+ assertEquals( "21,27,37,38,39", getInorderForm() );
+
+ tree.remove( 39, 39 );
+ assertEquals( "21,27,37,38", getInorderForm() );
+
+ assertTrue( 37 == tree.getRoot().key ); // check the root value
+
+ tree.remove( 38, 38 ); // a double right rotation has to happen after this
+ assertTrue( 27 == tree.getRoot().key ); // check the root value after double right rotation
+ assertEquals( "21,27,37", getInorderForm() );
+
+ if( LOG.isDebugEnabled() )
+ {
+ tree.printTree();
+ }
+ }
+
+
+ @Test
+ public void testRemoveWithDuplicateKeys()
+ {
+ tree.insert( 1, 1 );
+
+ // insert deuplicates
+ tree.insert( 3, 3 );
+ tree.insert( 3, 2 );
+ tree.insert( 3, 1 );
+
+ tree.insert( 2, 3 );
+
+ tree.remove( 2, 3 );
+ assertEquals("1,3", getInorderForm());
+ assertEquals( 2, tree.getSize() );
+
+ tree.remove( 3, 3 );
+ // removing a duplicate key,value shouldn't change the size
+ assertEquals("1,3", getInorderForm());
+ assertEquals( 2, tree.getSize() );
+
+ tree.remove( 3, null );
+ assertEquals("1", getInorderForm());
+ assertEquals( 1, tree.getSize() );
+
+ // add some more
+ tree.insert( 3, 3 );
+ tree.insert( 3, 4 );
+ assertEquals( 2, tree.getSize() );
+
+ tree.remove( 3, 3 );
+ assertEquals("1,3", getInorderForm());
+ assertEquals( 2, tree.getSize() );
+
+ tree.remove( 3, 4 ); // is the last value in the dupsTree should remove the whole
+ // node with key 3
+ assertEquals( 1, tree.getSize() );
+ }
+
+
+ @Test
+ public void testSingleRightRotation()
+ {
+ // right rotation
+ tree.insert( 3, 3 );
+ tree.insert( 2, 2 );
+ tree.insert( 1, 1 );
+
+ assertEquals( "1,2,3", getInorderForm() );
+ }
+
+
+ private String getInorderForm()
+ {
+ StringBuilder sb = new StringBuilder();
+ List<LinkedAvlMapNode<Integer,Integer>> path = new ArrayList<LinkedAvlMapNode<Integer,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( LinkedAvlMapNode<Integer,Integer> startNode, List<LinkedAvlMapNode<Integer,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
+ }
+
+}