directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From elecha...@apache.org
Subject 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
Date Fri, 10 Jul 2009 08:19:39 GMT
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() );
+    }
+}



Mime
View raw message