You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@directory.apache.org by el...@apache.org on 2009/07/10 10:19:39 UTC
svn commit: r792829 - in /directory/apacheds/trunk/core-avl/src:
main/java/org/apache/directory/server/core/avltree/ArrayTree.java
test/java/org/apache/directory/server/core/avltree/ArrayTreeTest.java
Author: elecharny
Date: Fri Jul 10 08:19:39 2009
New Revision: 792829
URL: http://svn.apache.org/viewvc?rev=792829&view=rev
Log:
The new ArrayTree implementation used to replace the AVL tree, with the associated tests.
Added:
directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/ArrayTree.java
directory/apacheds/trunk/core-avl/src/test/java/org/apache/directory/server/core/avltree/ArrayTreeTest.java
Added: directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/ArrayTree.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/ArrayTree.java?rev=792829&view=auto
==============================================================================
--- directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/ArrayTree.java (added)
+++ directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/ArrayTree.java Fri Jul 10 08:19:39 2009
@@ -0,0 +1,673 @@
+/*
+ * 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.Arrays;
+import java.util.Comparator;
+import java.util.List;
+
+
+/**
+ * A data structure simulating a tree (ie, a sorted list of elements) using an array.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $Rev$, $Date$
+ */
+public class ArrayTree<K>
+{
+ /** The Comparator used for comparing the keys */
+ private Comparator<K> comparator;
+
+ /** The array containing the data */
+ private K[] array;
+
+ /** The current number of elements in the array. May be lower than the array size */
+ private int size;
+
+ /** The extend size to use when increasing the array size */
+ private static final int INCREMENT = 16;
+
+ /** The current position in the array */
+ private int position;
+
+ /**
+ * Creates a new instance of AVLTree.
+ *
+ * @param comparator the comparator to be used for comparing keys
+ */
+ public ArrayTree( Comparator<K> comparator)
+ {
+ this.comparator = comparator;
+ array = (K[])new Object[INCREMENT];
+ size = 0;
+ position = 0;
+ }
+
+
+ /**
+ * @return the comparator associated with this tree
+ */
+ public Comparator<K> getComparator()
+ {
+ return comparator;
+ }
+
+
+ /**
+ * Inserts a key.
+ *
+ * @param key the item to be inserted
+ * @return the replaced key if it already exists
+ * Note: Ignores if the given key already exists.
+ */
+ public K insert( K key )
+ {
+ if ( size == array.length )
+ {
+ // The array is full, let's extend it
+ K[] newArray = (K[])new Object[size + INCREMENT];
+
+ System.arraycopy( array, 0, newArray, 0, size );
+ array = newArray;
+ }
+
+ array[size++] = key;
+ Arrays.sort( array, 0, size, comparator );
+
+ return key;
+ }
+
+
+ /**
+ * Reduce the array size if neede
+ */
+ private void reduceArray()
+ {
+ // We will reduce the array size when the number of elements
+ // in it is leaving twice the number of INCREMENT empty slots.
+ // We then remove INCREMENT slots
+ if ( ( array.length - size ) > (INCREMENT << 1) )
+ {
+ K[] newArray = (K[])new Object[array.length - INCREMENT];
+ System.arraycopy( array, 0, newArray, 0, array.length );
+ }
+ }
+
+
+ /**
+ * Removes a key present in the tree
+ *
+ * @param key the value to be removed
+ * @return the removed key, if any, or null if the key does not exist
+ */
+ public K remove( K key )
+ {
+ // Search for the key position in the tree
+ int pos = findPosition( key );
+
+ if ( pos != -1 )
+ {
+ // Found...
+ if ( pos != size - 1 )
+ {
+ // If the element is not the last one, we have to
+ // move the end of the array one step to the left
+ System.arraycopy( array, pos + 1, array, pos, size - pos - 1 );
+
+ reduceArray();
+ }
+
+ size --;
+
+ return key;
+ }
+ else
+ {
+ return null;
+ }
+ }
+
+
+ /**
+ * Tests if the tree is empty.
+ *
+ * @return true if the tree is empty, false otherwise
+ */
+ public boolean isEmpty()
+ {
+ return size == 0;
+ }
+
+
+ /**
+ * returns the number of nodes present in this tree.
+ *
+ * @return the number of nodes present in this tree
+ */
+ public int getSize()
+ {
+ return size;
+ }
+
+
+ /**
+ * @return a list of the stored keys in this tree
+ */
+ public List<K> getKeys()
+ {
+ List<K> list = new ArrayList<K>( size );
+
+ for ( int i = 0; i < size; i++ )
+ {
+ list.add( array[i] );
+ }
+
+ return list;
+ }
+
+ /**
+ * Prints the contents of AVL tree in pretty format
+ */
+ public void printTree()
+ {
+ if( isEmpty() )
+ {
+ System.out.println( "Tree is empty" );
+ return;
+ }
+
+ boolean isFirst = false;
+
+ for ( K key:array )
+ {
+ if ( isFirst )
+ {
+ isFirst = false;
+ }
+ else
+ {
+ System.out.print( ", " );
+ }
+
+ System.out.println( key );
+ }
+ }
+
+
+ /**
+ * Get the element at a given position
+ * @param position The position in the tree
+ * @return The found key, or null if the position is out of scope
+ */
+ public K get( int position )
+ {
+ if ( ( position < 0 ) || ( position >= size ) )
+ {
+ return null;
+ }
+
+ return array[position];
+ }
+
+
+ /**
+ * Get the element at the current position
+ * @return The found key, or null if the position is out of scope
+ */
+ public K get()
+ {
+ if ( ( position < 0 ) || ( position >= size ) )
+ {
+ return null;
+ }
+
+ return array[position];
+ }
+
+
+ /**
+ * Get the first element in the tree. It sets the current position to this
+ * element.
+ * @return The first element of this tree
+ */
+ public K getFirst()
+ {
+ position = 0;
+
+ if ( size != 0 )
+ {
+ return array[position];
+ }
+ else
+ {
+ return null;
+ }
+ }
+
+
+ /**
+ * Get the next element in the tree, from the current position. The position is
+ * changed accordingly
+ * @return The next element of this tree
+ */
+ public K getNext()
+ {
+ if ( ( position < 0 ) || ( position >= size - 1 ) )
+ {
+ return null;
+ }
+
+ position++;
+ return array[position];
+ }
+
+
+ /**
+ * Get the previous element in the tree, from the current position. The position is
+ * changed accordingly
+ * @return The previous element of this tree
+ */
+ public K getPrevious()
+ {
+ if ( ( position <= 0 ) || ( position > size - 1 ) )
+ {
+ return null;
+ }
+
+ position--;
+ return array[position];
+ }
+
+
+ /**
+ * Get the last element in the tree. It sets the current position to this
+ * element.
+ * @return The last element in this tree
+ */
+ public K getLast()
+ {
+ position = size - 1;
+
+ if ( size != 0 )
+ {
+ return array[position];
+ }
+ else
+ {
+ return null;
+ }
+ }
+
+ /**
+ * Finds a key higher than the given key. Sets the current position to this
+ * element.
+ *
+ * @param key the key to find
+ * @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 K findGreater( K key )
+ {
+ if ( size == 0 )
+ {
+ return null;
+ }
+
+ int current = size >> 1;
+ int end = size;
+ int start = 0;
+ int previousCurrent = -1;
+
+ while ( previousCurrent != current )
+ {
+ int res = comparator.compare( array[current], key ) ;
+
+ if ( res == 0 )
+ {
+ if ( current == size - 1 )
+ {
+ return null;
+ }
+ else
+ {
+ position = current + 1;
+ return array[position];
+ }
+ }
+ else if ( res < 0 )
+ {
+ start = current;
+ previousCurrent = current;
+ current = (start + end ) >> 1;
+ }
+ else
+ {
+ end = current;
+ previousCurrent = current;
+ current = (start + end ) >> 1 ;
+ }
+ }
+
+ // We haven't found the element, so take the next one
+ if ( current == size - 1 )
+ {
+ return null;
+ }
+ else
+ {
+ position = current + 1;
+ return array[position];
+ }
+ }
+
+
+ /**
+ * Finds a key higher than the given key.
+ *
+ * @param key the key
+ * @return the key chich is greater than the given key ,<br>
+ * null if there is no higher key than the given key.
+ */
+ public K findGreaterOrEqual( K key )
+ {
+ if ( size == 0 )
+ {
+ return null;
+ }
+
+ int current = size >> 1;
+ int end = size;
+ int start = 0;
+ int previousCurrent = -1;
+
+ while ( previousCurrent != current )
+ {
+ int res = comparator.compare( array[current], key ) ;
+
+ if ( res == 0 )
+ {
+ position = current;
+ return array[current];
+ }
+ else if ( res < 0 )
+ {
+ start = current;
+ previousCurrent = current;
+ current = (current + end ) >> 1;
+ }
+ else
+ {
+ end = current;
+ previousCurrent = current;
+ current = (current + start ) >> 1 ;
+ }
+ }
+
+ // We haven't found the element, so take the next one
+ if ( current == size - 1 )
+ {
+ return null;
+ }
+ else
+ {
+ position = current + 1;
+ return array[position];
+ }
+ }
+
+
+ /**
+ * Finds a key which is lower than the given key.
+ *
+ * @param key the key
+ * @return the key lower than the given key ,<br>
+ * null if there is no node with a lower key than the given key.
+ */
+ public K findLess( K key )
+ {
+ if ( size == 0 )
+ {
+ return null;
+ }
+
+ int current = size >> 1;
+ int end = size;
+ int start = 0;
+ int previousCurrent = -1;
+
+ while ( previousCurrent != current )
+ {
+ int res = comparator.compare( array[current], key ) ;
+
+ if ( res == 0 )
+ {
+ if ( current == 0 )
+ {
+ return null;
+ }
+ else
+ {
+ position = current - 1;
+ return array[position];
+ }
+ }
+ else if ( res < 0 )
+ {
+ start = current;
+ previousCurrent = current;
+ current = (current + end ) >> 1;
+ }
+ else
+ {
+ end = current;
+ previousCurrent = current;
+ current = (current + start ) >> 1 ;
+ }
+ }
+
+ // We haven't found the element, so take the previous one
+ if ( current == 0 )
+ {
+ return null;
+ }
+ else
+ {
+ position = current;
+ return array[current];
+ }
+ }
+
+
+ /**
+ * Finds a key chich is lower than the given key.
+ *
+ * @param key the key
+ * @return the key which is lower than the given key ,<br>
+ * null if there is no node with a lower key than the given key.
+ */
+ public K findLessOrEqual( K key )
+ {
+ if ( size == 0 )
+ {
+ return null;
+ }
+
+ int current = size >> 1;
+ int end = size;
+ int start = 0;
+ int previousCurrent = -1;
+
+ while ( previousCurrent != current )
+ {
+ int res = comparator.compare( array[current], key ) ;
+
+ if ( res == 0 )
+ {
+ position = current;
+ return array[current];
+ }
+ else if ( res < 0 )
+ {
+ start = current;
+ previousCurrent = current;
+ current = (current + end ) >> 1;
+ }
+ else
+ {
+ end = current;
+ previousCurrent = current;
+ current = (current + start ) >> 1 ;
+ }
+ }
+
+ // We haven't found the element, so take the previous one
+ if ( current == 0 )
+ {
+ return null;
+ }
+ else
+ {
+ position = current - 1;
+ return array[position];
+ }
+ }
+
+
+ /**
+ * Find
+ *
+ * @param key the key to find
+ * @return the list of traversed LinkedAvlNode.
+ */
+ public K find( K key )
+ {
+ if ( size == 0 )
+ {
+ position = 0;
+ return null;
+ }
+
+ int current = size >> 1;
+ int end = size;
+ int start = 0;
+ int previousCurrent = -1;
+
+ while ( previousCurrent != current )
+ {
+ int res = comparator.compare( array[current], key ) ;
+
+ if ( res == 0 )
+ {
+ position = current;
+ return key;
+ }
+ else if ( res < 0 )
+ {
+ start = current;
+ previousCurrent = current;
+ current = (current + end ) >> 1;
+ }
+ else
+ {
+ end = current;
+ previousCurrent = current;
+ current = (current + start ) >> 1 ;
+ }
+ }
+
+ position = 0;
+ return null;
+ }
+
+
+ private int findPosition( K key )
+ {
+ if ( size == 0 )
+ {
+ return -1;
+ }
+
+ int current = size >> 1;
+ int end = size;
+ int start = 0;
+ int previousCurrent = -1;
+
+ while ( previousCurrent != current )
+ {
+ int res = comparator.compare( array[current], key ) ;
+
+ if ( res == 0 )
+ {
+ position = current;
+ return current;
+ }
+ else if ( res < 0 )
+ {
+ start = current;
+ previousCurrent = current;
+ current = (current + end ) >> 1;
+ }
+ else
+ {
+ end = current;
+ previousCurrent = current;
+ current = (current + start ) >> 1 ;
+ }
+ }
+
+ return -1;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public String toString()
+ {
+ if( isEmpty() )
+ {
+ return "[]";
+ }
+
+ StringBuilder sb = new StringBuilder();
+
+ boolean isFirst = true;
+
+ for ( int i = 0; i < size; i ++ )
+ {
+ K key = array[i];
+
+ if ( isFirst )
+ {
+ isFirst = false;
+ }
+ else
+ {
+ sb.append( ", " );
+ }
+
+ sb.append( key );
+ }
+
+ return sb.toString();
+ }
+}
Added: directory/apacheds/trunk/core-avl/src/test/java/org/apache/directory/server/core/avltree/ArrayTreeTest.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/core-avl/src/test/java/org/apache/directory/server/core/avltree/ArrayTreeTest.java?rev=792829&view=auto
==============================================================================
--- directory/apacheds/trunk/core-avl/src/test/java/org/apache/directory/server/core/avltree/ArrayTreeTest.java (added)
+++ directory/apacheds/trunk/core-avl/src/test/java/org/apache/directory/server/core/avltree/ArrayTreeTest.java Fri Jul 10 08:19:39 2009
@@ -0,0 +1,522 @@
+/*
+ * 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.Comparator;
+import java.util.List;
+
+import org.junit.Before;
+import org.junit.Test;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+
+/**
+ * An AVL tree testcase.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $Rev$, $Date$
+ */
+public class ArrayTreeTest
+{
+
+ ArrayTree<Integer> tree;
+
+ private static final Logger LOG = LoggerFactory.getLogger( ArrayTreeTest.class );
+
+
+ @Before
+ public void createTree()
+ {
+ tree = new ArrayTree<Integer>( new Comparator<Integer>()
+ {
+
+ public int compare( Integer i1, Integer i2 )
+ {
+ return i1.compareTo( i2 );
+ }
+
+ } );
+ }
+
+
+ @Test
+ public void testEmpty()
+ {
+ assertTrue( tree.isEmpty() );
+ assertNull( tree.getFirst() );
+ assertNull( tree.getLast() );
+
+ tree.remove( 97 ); // remove a non-existing key
+ assertTrue( tree.isEmpty() );
+
+ if ( LOG.isDebugEnabled() )
+ {
+ tree.printTree();
+ }
+ }
+
+
+ @Test
+ public void testFirstAndLast()
+ {
+ tree.insert( 7 );
+ assertFalse( tree.isEmpty() );
+ assertNotNull( tree.getFirst() );
+ assertNotNull( tree.getLast() );
+
+ tree.insert( 10 );
+ assertEquals( 2, tree.getSize() );
+ assertNotNull( tree.getFirst() );
+ assertNotNull( tree.getLast() );
+ assertFalse( tree.getFirst().equals( tree.getLast() ) );
+ assertTrue( tree.getFirst().equals( 7 ) );
+ assertTrue( tree.getLast().equals( 10 ) );
+
+ tree.insert( 3 );
+ assertTrue( tree.getFirst().equals( 3 ) );
+ assertTrue( tree.getLast().equals( 10 ) );
+
+ tree.insert( 11 );
+ assertTrue( tree.getFirst().equals( 3 ) );
+ assertTrue( tree.getLast().equals( 11 ) );
+ }
+
+
+ @Test
+ public void testInsert()
+ {
+ assertTrue( tree.isEmpty() );
+
+ assertTrue( 3 == tree.insert( 3 ) );// should be ignored
+ assertTrue( 1 == tree.getSize() );
+
+ assertNotNull( tree.getFirst() );
+ assertNotNull( tree.getLast() );
+ assertTrue( tree.getFirst() == tree.getLast() );
+
+ tree.remove( 3 );
+
+ tree.insert( 37 );
+ tree.insert( 70 );
+ tree.insert( 12 );
+ assertTrue( 3 == tree.getSize() );
+
+ tree.insert( 90 );
+ tree.insert( 25 );
+ tree.insert( 99 );
+ tree.insert( 91 );
+ tree.insert( 24 );
+ tree.insert( 28 );
+ tree.insert( 26 );
+
+ if ( LOG.isDebugEnabled() )
+ {
+ tree.printTree();
+ }
+
+ tree.remove( 24 ); // this causes a single left rotation on node with key 12
+ if ( LOG.isDebugEnabled() )
+ {
+ tree.printTree();
+ }
+ assertTrue( tree.findGreater( 24 ) == 25 );
+ }
+
+
+ @Test
+ public void testSingleRightRotation()
+ {
+ // right rotation
+ tree.insert( 3 );
+ tree.insert( 2 );
+ tree.insert( 1 );
+
+ assertEquals( "1, 2, 3", tree.toString() );
+ }
+
+
+ @Test
+ public void testSingleLeftRotation()
+ {
+ // left rotation
+ tree.insert( 1 );
+ tree.insert( 2 );
+ tree.insert( 3 );
+
+ assertEquals( "1, 2, 3", tree.toString() );
+ }
+
+
+ @Test
+ public void testDoubleLeftRotation() // left-right totation
+ {
+ // double left rotation
+ tree.insert( 1 );
+ tree.insert( 3 );
+ tree.insert( 2 );
+
+ assertEquals( "1, 2, 3", tree.toString() );
+ }
+
+
+ @Test
+ public void testDoubleRightRotation() // right-left totation
+ {
+ // double left rotation
+ tree.insert( 3 );
+ tree.insert( 1 );
+ tree.insert( 2 );
+ assertEquals( "1, 2, 3", tree.toString() );
+ }
+
+
+ @Test
+ public void testLinks()
+ {
+ tree.insert( 37 );
+ tree.insert( 1 );
+ tree.insert( 2 );
+ tree.insert( 10 );
+ tree.insert( 11 );
+ tree.insert( 25 );
+ tree.insert( 5 );
+
+ assertTrue( 1 == tree.getFirst() );
+ assertTrue( 37 == tree.getLast() );
+ }
+
+
+ @Test
+ public void testRemove()
+ {
+ tree.insert( 3 );
+ tree.insert( 2 );
+ tree.insert( 1 );
+
+ LOG.debug( getLinkedText() );
+ tree.remove( 2 );
+ LOG.debug( getLinkedText() );
+ assertEquals( "1, 3", tree.toString() );
+
+ tree.remove( 1 );
+ assertEquals( "3", tree.toString() );
+ assertTrue( 3 == tree.getFirst() );
+
+ assertNull( tree.remove( 777 ) );// key not present
+ assertTrue( 3 == 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", tree.toString() );
+
+ tree.remove( 26 ); // remove a non-root non-leaf node in the left sub tree of root
+ assertEquals( "21, 27, 37, 38, 39, 43", tree.toString() );
+
+ tree.remove( 43 );
+ assertEquals( "21, 27, 37, 38, 39", tree.toString() );
+
+ tree.remove( 39 );
+ assertEquals( "21, 27, 37, 38", tree.toString() );
+
+ tree.remove( 38 ); // a double right rotation has to happen after this
+
+ assertEquals( "21, 27, 37", tree.toString() );
+
+ if ( LOG.isDebugEnabled() )
+ {
+ tree.printTree();
+ }
+ }
+
+
+ @Test
+ public void testLinkedNodes()
+ {
+ for ( int i = 0; i < 3; i++ )
+ {
+ tree.insert( i );
+ }
+
+ assertEquals( "[0]-->[1]-->[2]-->NULL", getLinkedText() );
+
+ tree.remove( 1 );
+ assertEquals( "[0]-->[2]-->NULL", getLinkedText() );
+
+ tree.insert( 4 );
+ tree.insert( 3 );
+
+ assertEquals( "[0]-->[2]-->[3]-->[4]-->NULL", getLinkedText() );
+
+ tree.remove( 0 );
+ assertEquals( "[2]-->[3]-->[4]-->NULL", getLinkedText() );
+
+ tree.remove( 3 );
+ assertEquals( "[2]-->[4]-->NULL", getLinkedText() );
+ }
+
+
+ @Test
+ public void testFind()
+ {
+ assertNull( tree.find( 3 ) );
+
+ tree.insert( 1 );
+ tree.insert( 70 );
+ tree.insert( 21 );
+ tree.insert( 12 );
+ tree.insert( 27 );
+ tree.insert( 11 );
+
+ assertNotNull( tree.find( 11 ) );
+ assertNull( tree.find( 0 ) );
+ }
+
+
+ @Test
+ public void testFindGreater()
+ {
+ assertNull( tree.findGreater( 1 ) );
+
+ tree.insert( 1 );
+ assertNull( tree.findGreater( 1 ) );
+
+ tree.insert( 0 );
+ tree.insert( 3 );
+ tree.insert( 7 );
+ tree.insert( 6 );
+ tree.insert( 2 );
+ tree.insert( 8 );
+
+ assertFalse( 1 == tree.findGreater( 1 ) );
+ assertTrue( 2 == tree.findGreater( 1 ) );
+ assertTrue( 6 == tree.findGreater( 4 ) );
+ assertNull( tree.findGreater( 8 ) );
+ }
+
+
+ @Test
+ public void testFindLess()
+ {
+ assertNull( tree.findLess( 1 ) );
+
+ tree.insert( 1 );
+ assertNull( tree.findLess( 1 ) );
+
+ tree.insert( 2 );
+ tree.insert( 7 );
+ tree.insert( 3 );
+ tree.insert( 6 );
+ tree.insert( 0 );
+ tree.insert( 37 );
+
+ assertFalse( 0 == tree.findLess( 5 ) );
+ assertTrue( 3 == tree.findLess( 5 ) );
+ assertTrue( 7 == tree.findLess( 8 ) );
+ assertNull( tree.findLess( 0 ) );
+ }
+
+
+ @Test
+ public void testFindMaxMin()
+ {
+ tree.insert( 72 );
+ tree.insert( 79 );
+
+ tree.remove( 72 );// should call findMax internally
+ assertTrue( 79 == tree.getFirst() );
+
+ tree.insert( 11 );
+ tree.remove( 79 ); // should call findMin internally
+ assertTrue( 11 == tree.getFirst() );
+ }
+
+
+ @Test
+ public void testGetKeys()
+ {
+ tree.insert( 72 );
+ tree.insert( 79 );
+ tree.insert( 1 );
+ tree.insert( 2 );
+ tree.insert( 3 );
+ tree.insert( 7 );
+ tree.insert( 34 );
+
+ assertTrue( 7 == tree.getKeys().size() );
+ }
+
+
+ @Test
+ public void testTreeRoationAtLeftChildAfterDeletingRoot()
+ {
+ int[] keys =
+ { 86, 110, 122, 2, 134, 26, 14, 182 }; // order is important to produce the expected tree
+ int[] expectedKeys =
+ { 2, 14, 26, 86, 122, 134, 182 };
+
+ for ( int key : keys )
+ {
+ tree.insert( key );
+ }
+
+ tree.remove( 110 );
+
+ for ( int key : expectedKeys )
+ {
+ assertNotNull( "Should find " + key, tree.find( key ) );
+ }
+ }
+
+
+ private String getLinkedText()
+ {
+ Integer first = tree.getFirst();
+ StringBuilder sb = new StringBuilder();
+
+ while ( first != null )
+ {
+ sb.append( "[" ).append( first ).append( "]-->" );
+
+ first = tree.findGreater( first );
+ }
+
+ sb.append( "NULL" );
+ return sb.toString();
+ }
+
+
+ private String getInorderForm()
+ {
+ StringBuilder sb = new StringBuilder();
+
+ return tree.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
+ }
+
+
+ @Test
+ public void testRemoveEmptyTree()
+ {
+ tree.remove( null );
+
+ assertEquals( 0, tree.getSize() );
+
+ tree.remove( 1 );
+
+ assertEquals( 0, tree.getSize() );
+ }
+
+
+ @Test
+ public void testRemoveOneNode()
+ {
+ tree.insert( 1 );
+ assertEquals( 1, tree.getSize() );
+
+ tree.remove( 1 );
+ assertEquals( 0, tree.getSize() );
+ }
+
+
+ @Test
+ public void testRemoveOneNodeWithRight()
+ {
+ tree.insert( 1 );
+ tree.insert( 2 );
+ assertEquals( 2, tree.getSize() );
+ assertEquals( "1, 2", tree.toString() );
+
+ tree.remove( 1 );
+ assertEquals( 1, tree.getSize() );
+ assertEquals( Integer.valueOf( 2 ), tree.getFirst() );
+ }
+
+
+ @Test
+ public void testNext()
+ {
+ tree.insert( 1 );
+ tree.insert( 70 );
+ tree.insert( 21 );
+ tree.insert( 12 );
+ tree.insert( 27 );
+ tree.insert( 11 );
+
+ assertEquals( Integer.valueOf( 1 ), tree.getFirst() );
+ assertEquals( Integer.valueOf( 11 ), tree.getNext() );
+ assertEquals( Integer.valueOf( 12 ), tree.getNext() );
+ assertEquals( Integer.valueOf( 21 ), tree.getNext() );
+ assertEquals( Integer.valueOf( 27 ), tree.getNext() );
+ assertEquals( Integer.valueOf( 70 ), tree.getNext() );
+ assertNull( tree.getNext() );
+ }
+
+
+ @Test
+ public void testPrevious()
+ {
+ tree.insert( 1 );
+ tree.insert( 70 );
+ tree.insert( 21 );
+ tree.insert( 12 );
+ tree.insert( 27 );
+ tree.insert( 11 );
+
+ assertEquals( Integer.valueOf( 70 ), tree.getLast() );
+ assertEquals( Integer.valueOf( 27 ), tree.getPrevious() );
+ assertEquals( Integer.valueOf( 21 ), tree.getPrevious() );
+ assertEquals( Integer.valueOf( 12 ), tree.getPrevious() );
+ assertEquals( Integer.valueOf( 11 ), tree.getPrevious() );
+ assertEquals( Integer.valueOf( 1 ), tree.getPrevious() );
+ assertNull( tree.getPrevious() );
+ }
+}