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/18 02:38:46 UTC
svn commit: r795285 - in
/directory/apacheds/trunk/core-avl/src/test/java/org/apache/directory/server/core/avltree:
ArrayTreeCursorTest.java ArrayTreeTest.java
Author: elecharny
Date: Sat Jul 18 00:38:45 2009
New Revision: 795285
URL: http://svn.apache.org/viewvc?rev=795285&view=rev
Log:
Added the ArrayTree class and the associated cursor to replace the AvlTree
Added:
directory/apacheds/trunk/core-avl/src/test/java/org/apache/directory/server/core/avltree/ArrayTreeCursorTest.java
Modified:
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/ArrayTreeCursorTest.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/core-avl/src/test/java/org/apache/directory/server/core/avltree/ArrayTreeCursorTest.java?rev=795285&view=auto
==============================================================================
--- directory/apacheds/trunk/core-avl/src/test/java/org/apache/directory/server/core/avltree/ArrayTreeCursorTest.java (added)
+++ directory/apacheds/trunk/core-avl/src/test/java/org/apache/directory/server/core/avltree/ArrayTreeCursorTest.java Sat Jul 18 00:38:45 2009
@@ -0,0 +1,248 @@
+/*
+ * 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.Comparator;
+
+import org.apache.directory.shared.ldap.cursor.InvalidCursorPositionException;
+import org.junit.Test;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.fail;
+
+
+/**
+ * Tests the ArrayTreeCursor class.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $Rev$, $Date$
+ */
+public class ArrayTreeCursorTest
+{
+ @Test
+ public void testEmptyCursor() throws Exception
+ {
+ ArrayTree<Integer> tree = new ArrayTree<Integer>( new IntegerComparator() );
+ ArrayTreeCursor<Integer> cursor = new ArrayTreeCursor<Integer>( tree );
+
+ assertFalse( cursor.isClosed() );
+ assertFalse( cursor.available() );
+ assertTrue( cursor.isElementReused() );
+
+ try
+ {
+ cursor.get();
+ fail( "Should not get here" );
+ }
+ catch ( InvalidCursorPositionException e )
+ {
+ assertNotNull( e );
+ }
+
+ cursor.beforeFirst();
+ assertFalse( cursor.available() );
+
+ cursor.afterLast();
+ assertFalse( cursor.available() );
+
+ assertFalse( cursor.first() );
+ assertFalse( cursor.available() );
+
+ assertFalse( cursor.last() );
+ assertFalse( cursor.available() );
+
+ assertFalse( cursor.next() );
+ assertFalse( cursor.available() );
+
+ assertFalse( cursor.previous() );
+ assertFalse( cursor.available() );
+
+ cursor.before( 3 );
+ assertFalse( cursor.available() );
+
+ cursor.after( 3 );
+ assertFalse( cursor.available() );
+
+ cursor.close();
+ assertTrue( cursor.isClosed() );
+ }
+
+
+ @Test
+ public void testOneEntryCursor() throws Exception
+ {
+ ArrayTree<Integer> tree = new ArrayTree<Integer>( new IntegerComparator() );
+ tree.insert( 7 );
+ ArrayTreeCursor<Integer> cursor = new ArrayTreeCursor<Integer>( tree );
+
+ assertFalse( cursor.isClosed() );
+ assertFalse( cursor.available() );
+ assertTrue( cursor.isElementReused() );
+
+ try
+ {
+ cursor.get();
+ fail( "Should not get here" );
+ }
+ catch ( InvalidCursorPositionException e )
+ {
+ assertNotNull( e );
+ }
+
+ cursor.beforeFirst();
+ assertFalse( cursor.available() );
+ assertFalse( cursor.previous() );
+ assertTrue( cursor.next() );
+ assertTrue( cursor.available() );
+ assertEquals( 7, ( int ) cursor.get() );
+
+ cursor.afterLast();
+ assertFalse( cursor.next() );
+ assertFalse( cursor.available() );
+
+ assertTrue( cursor.first() );
+ assertTrue( cursor.available() );
+
+ assertTrue( cursor.last() );
+ assertTrue( cursor.available() );
+
+ assertFalse( cursor.next() );
+ assertFalse( cursor.available() );
+
+ assertTrue( cursor.previous() );
+ assertTrue( cursor.available() );
+
+ cursor.before( 3 );
+ assertFalse( cursor.available() );
+ assertTrue( cursor.next() );
+ assertTrue( cursor.available() );
+ assertEquals( 7, ( int ) cursor.get() );
+
+ cursor.after( 3 );
+ assertFalse( cursor.available() );
+ assertTrue( cursor.next() );
+ assertTrue( cursor.available() );
+ assertEquals( 7, ( int ) cursor.get() );
+
+ cursor.before( 7 );
+ assertFalse( cursor.available() );
+ assertTrue( cursor.next() );
+ assertTrue( cursor.available() );
+ assertEquals( 7, ( int ) cursor.get() );
+ }
+
+
+ @Test
+ public void testManyEntriesCursor() throws Exception
+ {
+ ArrayTree<Integer> tree = new ArrayTree<Integer>( new IntegerComparator() );
+ tree.insert( 3 );
+ tree.insert( 7 );
+ tree.insert( 10 );
+ tree.insert( 11 );
+ ArrayTreeCursor<Integer> cursor = new ArrayTreeCursor<Integer>( tree );
+
+ assertFalse( cursor.isClosed() );
+ assertFalse( cursor.available() );
+ assertTrue( cursor.isElementReused() );
+ assertEquals( 4, tree.size() );
+
+ try
+ {
+ cursor.get();
+ fail( "Should not get here" );
+ }
+ catch ( InvalidCursorPositionException e )
+ {
+ assertNotNull( e );
+ }
+
+ cursor.beforeFirst();
+ assertFalse( cursor.available() );
+ assertTrue( cursor.next() );
+ assertTrue( cursor.available() );
+ assertEquals( 3, ( int ) cursor.get() );
+ assertTrue( cursor.next() );
+ assertTrue( cursor.available() );
+ assertEquals( 7, ( int ) cursor.get() );
+ assertTrue( cursor.next() );
+ assertTrue( cursor.available() );
+ assertEquals( 10, ( int ) cursor.get() );
+ assertTrue( cursor.next() );
+ assertTrue( cursor.available() );
+ assertEquals( 11, ( int ) cursor.get() );
+ assertFalse( cursor.next() );
+ assertFalse( cursor.available() );
+
+
+ cursor.afterLast();
+ assertFalse( cursor.available() );
+ assertTrue( cursor.previous() );
+ assertTrue( cursor.available() );
+ assertEquals( 11, ( int ) cursor.get() );
+ assertTrue( cursor.previous() );
+ assertTrue( cursor.available() );
+ assertEquals( 10, ( int ) cursor.get() );
+ assertTrue( cursor.previous() );
+ assertTrue( cursor.available() );
+ assertEquals( 7, ( int ) cursor.get() );
+ assertTrue( cursor.previous() );
+ assertTrue( cursor.available() );
+ assertEquals( 3, ( int ) cursor.get() );
+ assertFalse( cursor.previous() );
+ assertFalse( cursor.available() );
+
+ assertTrue( cursor.first() );
+ assertTrue( cursor.available() );
+
+ assertTrue( cursor.last() );
+ assertTrue( cursor.available() );
+
+ assertFalse( cursor.next() );
+ assertFalse( cursor.available() );
+
+ assertTrue( cursor.previous() );
+ assertTrue( cursor.available() );
+
+ cursor.after( 5 );
+ assertTrue( cursor.next() );
+ assertTrue( cursor.available() );
+ assertEquals( 7, ( int ) cursor.get() );
+
+
+ cursor.before( 11 );
+ assertTrue( cursor.next() );
+ assertTrue( cursor.available() );
+ assertEquals( 11, ( int ) cursor.get() );
+
+ }
+
+
+ class IntegerComparator implements Comparator<Integer>
+ {
+ public int compare( Integer o1, Integer o2 )
+ {
+ return o1.compareTo( o2 );
+ }
+ }
+}
Modified: 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=795285&r1=795284&r2=795285&view=diff
==============================================================================
--- directory/apacheds/trunk/core-avl/src/test/java/org/apache/directory/server/core/avltree/ArrayTreeTest.java (original)
+++ directory/apacheds/trunk/core-avl/src/test/java/org/apache/directory/server/core/avltree/ArrayTreeTest.java Sat Jul 18 00:38:45 2009
@@ -25,9 +25,10 @@
import static org.junit.Assert.assertNotNull;
import static org.junit.Assert.assertNull;
import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.assertNotSame;
+import static org.junit.Assert.fail;
import java.util.Comparator;
-import java.util.List;
import org.junit.Before;
import org.junit.Test;
@@ -43,7 +44,26 @@
*/
public class ArrayTreeTest
{
-
+ private static final Integer MINUS_ONE = Integer.valueOf( -1 );
+ private static final Integer ZERO = Integer.valueOf( 0 );
+ private static final Integer ONE = Integer.valueOf( 1 );
+ private static final Integer TWO = Integer.valueOf( 2 );
+ private static final Integer THREE = Integer.valueOf( 3 );
+ private static final Integer FOUR = Integer.valueOf( 4 );
+ private static final Integer FIVE = Integer.valueOf( 5 );
+ private static final Integer SIX = Integer.valueOf( 6 );
+ private static final Integer SEVEN = Integer.valueOf( 7 );
+ private static final Integer EIGHT = Integer.valueOf( 8 );
+ private static final Integer NINE = Integer.valueOf( 9 );
+ private static final Integer TEN = Integer.valueOf( 10 );
+ private static final Integer ELEVEN = Integer.valueOf( 11 );
+ private static final Integer TWELVE = Integer.valueOf( 12 );
+ private static final Integer THIRTY_ONE = Integer.valueOf( 31 );
+ private static final Integer THIRTY_TWO = Integer.valueOf( 32 );
+ private static final Integer THIRTY_SEVEN = Integer.valueOf( 37 );
+ private static final Integer SEVENTY = Integer.valueOf( 70 );
+ private static final Integer SEVENTY_NINE = Integer.valueOf( 79 );
+
ArrayTree<Integer> tree;
private static final Logger LOG = LoggerFactory.getLogger( ArrayTreeTest.class );
@@ -54,9 +74,13 @@
{
tree = new ArrayTree<Integer>( new Comparator<Integer>()
{
-
public int compare( Integer i1, Integer i2 )
{
+ if ( i1 == null )
+ {
+ return (i2 == null ? 0 : -1);
+ }
+
return i1.compareTo( i2 );
}
@@ -90,64 +114,23 @@
assertNotNull( tree.getLast() );
tree.insert( 10 );
- assertEquals( 2, tree.getSize() );
+ assertEquals( 2, tree.size() );
assertNotNull( tree.getFirst() );
assertNotNull( tree.getLast() );
assertFalse( tree.getFirst().equals( tree.getLast() ) );
- assertTrue( tree.getFirst().equals( 7 ) );
- assertTrue( tree.getLast().equals( 10 ) );
+ assertEquals( SEVEN, tree.getFirst() );
+ assertEquals( TEN, tree.getLast() );
tree.insert( 3 );
- assertTrue( tree.getFirst().equals( 3 ) );
- assertTrue( tree.getLast().equals( 10 ) );
+ assertEquals( THREE, tree.getFirst() );
+ assertEquals( TEN, tree.getLast() );
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 );
+ assertEquals( THREE, tree.getFirst() );
+ assertEquals( ELEVEN, tree.getLast() );
}
-
-
+
+
@Test
public void testSingleRightRotation()
{
@@ -206,8 +189,8 @@
tree.insert( 25 );
tree.insert( 5 );
- assertTrue( 1 == tree.getFirst() );
- assertTrue( 37 == tree.getLast() );
+ assertEquals( ONE, tree.getFirst() );
+ assertEquals( THIRTY_SEVEN, tree.getLast() );
}
@@ -225,10 +208,10 @@
tree.remove( 1 );
assertEquals( "3", tree.toString() );
- assertTrue( 3 == tree.getFirst() );
+ assertEquals( THREE, tree.getFirst() );
assertNull( tree.remove( 777 ) );// key not present
- assertTrue( 3 == tree.remove( 3 ) );
+ assertEquals( THREE, tree.remove( 3 ) );
assertTrue( tree.isEmpty() );
tree.insert( 37 );
@@ -304,61 +287,17 @@
@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() );
+ assertEquals( SEVENTY_NINE, tree.getFirst() );
tree.insert( 11 );
tree.remove( 79 ); // should call findMin internally
- assertTrue( 11 == tree.getFirst() );
+ assertEquals( ELEVEN, tree.getFirst() );
}
@@ -373,7 +312,7 @@
tree.insert( 7 );
tree.insert( 34 );
- assertTrue( 7 == tree.getKeys().size() );
+ assertEquals( 7, tree.getKeys().size() );
}
@@ -416,107 +355,971 @@
}
- private String getInorderForm()
+ @Test
+ public void testRemoveOneNode()
+ {
+ tree.insert( 1 );
+ assertEquals( 1, tree.size() );
+
+ tree.remove( 1 );
+ assertEquals( 0, tree.size() );
+ }
+
+
+ @Test
+ public void testRemoveOneNodeWithRight()
+ {
+ tree.insert( 1 );
+ tree.insert( 2 );
+ assertEquals( 2, tree.size() );
+ assertEquals( "1, 2", tree.toString() );
+
+ tree.remove( 1 );
+ assertEquals( 1, tree.size() );
+ assertEquals( TWO, tree.getFirst() );
+ }
+
+
+ //-----------------------------------------------------------------------
+ // Test insert( K value )
+ //-----------------------------------------------------------------------
+ @Test
+ public void testInsertNullValue()
+ {
+ assertEquals( 0, tree.size() );
+ assertNull( tree.insert( null ) );
+ assertEquals( 0, tree.size() );
+ }
+
+
+ @Test
+ public void testInsertInEmptyTree()
+ {
+ assertEquals( 0, tree.size() );
+ assertNull( tree.insert( 0 ) );
+ assertEquals( 1, tree.size() );
+ assertEquals( ZERO, tree.get( 0 ) );
+ assertEquals( ZERO, tree.getFirst() );
+ assertEquals( ZERO, tree.getLast() );
+ }
+
+
+ @Test
+ public void testInsertInOnElementTreeAtTheBeginning()
+ {
+ // Initialize the array
+ assertNull( tree.insert( 5 ) );
+ assertEquals( 1, tree.size() );
+
+ Integer existing = tree.insert( ZERO );
+ assertNull( existing );
+ assertEquals( 2, tree.size() );
+ assertEquals( ZERO, tree.getFirst() );
+ assertEquals( FIVE, tree.getLast() );
+ assertEquals( "0, 5", tree.toString() );
+ }
+
+
+ @Test
+ public void testInsertInOnElementTreeAtTheEnd()
+ {
+ // Initialize the array
+ assertNull( tree.insert( 5 ) );
+ assertEquals( 1, tree.size() );
+
+ Integer existing = tree.insert( TEN );
+ assertNull( existing );
+ assertEquals( 2, tree.size() );
+ assertEquals( FIVE, tree.getFirst() );
+ assertEquals( TEN, tree.getLast() );
+ assertEquals( "5, 10", tree.toString() );
+ }
+
+
+ @Test
+ public void testInsertInOnElementTreeExistingElement()
+ {
+ // Initialize the array
+ assertNull( tree.insert( 5 ) );
+ assertEquals( 1, tree.size() );
+
+ Integer existing = tree.insert( FIVE );
+ assertEquals( 1, tree.size() );
+ assertEquals( FIVE, existing );
+ assertEquals( FIVE, tree.getFirst() );
+ assertEquals( FIVE, tree.getLast() );
+ assertEquals( "5", tree.toString() );
+ }
+
+
+ @Test
+ public void testInsertInEvenTreeAtTheBeginning()
+ {
+ // Initialize the array
+ assertNull( tree.insert( ZERO ) );
+ assertNull( tree.insert( TWO ) );
+ assertNull( tree.insert( FOUR ) );
+ assertNull( tree.insert( SIX ) );
+ assertNull( tree.insert( EIGHT ) );
+ assertNull( tree.insert( TEN ) );
+ assertEquals( 6, tree.size() );
+
+ Integer existing = tree.insert( MINUS_ONE );
+ assertNull( existing );
+ assertEquals( 7, tree.size() );
+ assertEquals( MINUS_ONE, tree.getFirst() );
+ assertEquals( TEN, tree.getLast() );
+ assertEquals( "-1, 0, 2, 4, 6, 8, 10", tree.toString() );
+ }
+
+
+ @Test
+ public void testInsertInEvenTreeAtTheEnd()
+ {
+ // Initialize the array
+ assertNull( tree.insert( ZERO ) );
+ assertNull( tree.insert( TWO ) );
+ assertNull( tree.insert( FOUR ) );
+ assertNull( tree.insert( SIX ) );
+ assertNull( tree.insert( EIGHT ) );
+ assertNull( tree.insert( TEN ) );
+ assertEquals( 6, tree.size() );
+
+ Integer existing = tree.insert( TWELVE );
+ assertNull( existing );
+ assertEquals( 7, tree.size() );
+ assertEquals( ZERO, tree.getFirst() );
+ assertEquals( TWELVE, tree.getLast() );
+ assertEquals( "0, 2, 4, 6, 8, 10, 12", tree.toString() );
+ }
+
+
+ @Test
+ public void testInsertInEvenTreeInTheMiddle()
+ {
+ // Initialize the array
+ assertNull( tree.insert( ZERO ) );
+ assertNull( tree.insert( TWO ) );
+ assertNull( tree.insert( FOUR ) );
+ assertNull( tree.insert( SIX ) );
+ assertNull( tree.insert( EIGHT ) );
+ assertNull( tree.insert( TEN ) );
+ assertEquals( 6, tree.size() );
+
+ // Insert 1
+ Integer existing = tree.insert( ONE );
+ assertNull( existing );
+ assertEquals( 7, tree.size() );
+ assertEquals( ZERO, tree.getFirst() );
+ assertEquals( TEN, tree.getLast() );
+ assertEquals( "0, 1, 2, 4, 6, 8, 10", tree.toString() );
+
+ // Insert 5
+ existing = tree.insert( FIVE );
+ assertNull( existing );
+ assertEquals( 8, tree.size() );
+ assertEquals( ZERO, tree.getFirst() );
+ assertEquals( TEN, tree.getLast() );
+ assertEquals( "0, 1, 2, 4, 5, 6, 8, 10", tree.toString() );
+
+ // Insert 9
+ existing = tree.insert( NINE );
+ assertNull( existing );
+ assertEquals( 9, tree.size() );
+ assertEquals( ZERO, tree.getFirst() );
+ assertEquals( TEN, tree.getLast() );
+ assertEquals( "0, 1, 2, 4, 5, 6, 8, 9, 10", tree.toString() );
+ }
+
+
+ @Test
+ public void testInsertInEvenTreeExistingEelemnt()
+ {
+ // Initialize the array
+ assertNull( tree.insert( ZERO ) );
+ assertNull( tree.insert( TWO ) );
+ assertNull( tree.insert( FOUR ) );
+ assertNull( tree.insert( SIX ) );
+ assertNull( tree.insert( EIGHT ) );
+ assertNull( tree.insert( TEN ) );
+ assertEquals( 6, tree.size() );
+
+ // Insert 0
+ Integer existing = tree.insert( ZERO );
+ assertEquals( ZERO, existing );
+ assertEquals( 6, tree.size() );
+ assertEquals( ZERO, tree.getFirst() );
+ assertEquals( TEN, tree.getLast() );
+ assertEquals( "0, 2, 4, 6, 8, 10", tree.toString() );
+
+ // Insert 6
+ existing = tree.insert( SIX );
+ assertEquals( SIX, existing );
+ assertEquals( 6, tree.size() );
+ assertEquals( ZERO, tree.getFirst() );
+ assertEquals( TEN, tree.getLast() );
+ assertEquals( "0, 2, 4, 6, 8, 10", tree.toString() );
+
+ // Insert 10
+ existing = tree.insert( TEN );
+ assertEquals( TEN, existing );
+ assertEquals( 6, tree.size() );
+ assertEquals( ZERO, tree.getFirst() );
+ assertEquals( TEN, tree.getLast() );
+ assertEquals( "0, 2, 4, 6, 8, 10", tree.toString() );
+ }
+
+
+ @Test
+ public void testInsertInFullTree()
{
StringBuilder sb = new StringBuilder();
+ boolean isFirst = true;
+
+ // Initialize the array
+ for ( int i = 0; i < 32; i++ )
+ {
+ tree.insert( i );
+
+ if ( isFirst )
+ {
+ isFirst = false;
+ }
+ else
+ {
+ sb.append( ", " );
+ }
+
+ sb.append( i );
+ }
+
+
+ assertEquals( 32, tree.size() );
+ assertEquals( sb.toString(), tree.toString() );
+
+ assertEquals( ZERO, tree.getFirst() );
+ assertEquals( THIRTY_ONE, tree.getLast() );
+
+ // Now insert at the beginning
+ tree.insert( MINUS_ONE );
+ assertEquals( 33, tree.size() );
+ assertEquals( MINUS_ONE, tree.getFirst() );
+ assertEquals( THIRTY_ONE, tree.getLast() );
+
+ // Insert at the end
+ tree.insert( THIRTY_TWO );
+ assertEquals( 34, tree.size() );
+ assertEquals( MINUS_ONE, tree.getFirst() );
+ assertEquals( THIRTY_TWO, tree.getLast() );
+ }
+
+
+ //-----------------------------------------------------------------------
+ // Test remove( K value )
+ //-----------------------------------------------------------------------
+ @Test
+ public void testRemoveEmptyTree()
+ {
+ assertNull( tree.remove( null ) );
- return tree.toString();
+ assertEquals( 0, tree.size() );
+
+ assertNull( tree.remove( ONE ) );
+
+ assertEquals( 0, tree.size() );
}
+
+ @Test
+ public void testRemoveFromOnElementTree()
+ {
+ // Initialize the array
+ assertNull( tree.insert( 5 ) );
+ assertEquals( 1, tree.size() );
+
+ Integer existing = tree.remove( FIVE );
+ assertEquals( FIVE, existing );
+ assertEquals( 0, tree.size() );
+ assertNull( tree.getFirst() );
+ assertNull( tree.getLast() );
+ assertEquals( "[]", tree.toString() );
+ }
- private void traverse( LinkedAvlNode<Integer> startNode, List<LinkedAvlNode<Integer>> path )
+
+ @Test
+ public void testRemovefromOnElementTreeNotExistingElement()
{
- //1. pre-order
+ // Initialize the array
+ assertNull( tree.insert( 5 ) );
+ assertEquals( 1, tree.size() );
+
+ assertNull( tree.remove( TEN ) );
+ assertEquals( 1, tree.size() );
+ assertEquals( FIVE, tree.getFirst() );
+ assertEquals( FIVE, tree.getLast() );
+ assertEquals( "5", tree.toString() );
+ }
+
- if ( startNode.left != null )
+ @Test
+ public void testRemoveFromFullTreeFromTheBeginning()
+ {
+ StringBuilder sb = new StringBuilder();
+ boolean isFirst = true;
+
+ // Initialize the array
+ for ( int i = 0; i < 32; i++ )
{
- traverse( startNode.left, path );
+ tree.insert( i );
+
+ if ( isFirst )
+ {
+ isFirst = false;
+ }
+ else
+ {
+ sb.append( ", " );
+ }
+
+ sb.append( i );
}
+
+
+ assertEquals( 32, tree.size() );
+ assertEquals( sb.toString(), tree.toString() );
+
+ int size = 32;
+
+ for ( int i = 0; i < 32; i++)
+ {
+ assertEquals( Integer.valueOf( i ), tree.remove( i ) );
+ assertEquals( size - i - 1, tree.size() );
+
+ if ( i < 31 )
+ {
+ assertEquals( Integer.valueOf( i + 1 ), tree.getFirst() );
+ assertEquals( THIRTY_ONE, tree.getLast() );
+ }
+ }
+
+ assertEquals( 0, tree.size() );
+ assertNull( tree.getFirst() );
+ assertNull( tree.getLast() );
+ }
- path.add( startNode ); //2. in-order NOTE: change this line's position to change the type of traversal
- if ( startNode.right != null )
+ @Test
+ public void testRemoveFromFullTreeFromTheEnd()
+ {
+ StringBuilder sb = new StringBuilder();
+ boolean isFirst = true;
+
+ // Initialize the array
+ for ( int i = 0; i < 32; i++ )
{
- traverse( startNode.right, path );
+ tree.insert( i );
+
+ if ( isFirst )
+ {
+ isFirst = false;
+ }
+ else
+ {
+ sb.append( ", " );
+ }
+
+ sb.append( i );
+ }
+
+
+ assertEquals( 32, tree.size() );
+ assertEquals( sb.toString(), tree.toString() );
+
+ int size = 32;
+
+ for ( int i = 0; i < 32; i++)
+ {
+ assertEquals( Integer.valueOf( i ), tree.remove( i ) );
+ assertEquals( size - i - 1, tree.size() );
+
+ if ( i < 31 )
+ {
+ assertEquals( Integer.valueOf( i + 1 ), tree.getFirst() );
+ assertEquals( THIRTY_ONE, tree.getLast() );
+ }
}
- //3. post-order
+
+ assertEquals( 0, tree.size() );
+ assertNull( tree.getFirst() );
+ assertNull( tree.getLast() );
}
+ //-----------------------------------------------------------------------
+ // Test isEmpty()
+ //-----------------------------------------------------------------------
@Test
- public void testRemoveEmptyTree()
+ public void testIsEmptyEmptyTree()
{
- tree.remove( null );
+ assertTrue( tree.isEmpty() );
+
+ tree.insert( ONE );
+
+ assertFalse( tree.isEmpty() );
+
+ tree.remove( ONE );
+
+ assertTrue( tree.isEmpty() );
+ }
- assertEquals( 0, tree.getSize() );
- tree.remove( 1 );
+ //-----------------------------------------------------------------------
+ // Test size()
+ //-----------------------------------------------------------------------
+ @Test
+ public void testSizeEmptyTree()
+ {
+ assertEquals( 0, tree.size() );
+
+ tree.insert( ONE );
+
+ assertEquals( 1, tree.size() );
+
+ tree.remove( ONE );
+
+ assertEquals( 0, tree.size() );
+ }
+
- assertEquals( 0, tree.getSize() );
+ //-----------------------------------------------------------------------
+ // Test find()
+ //-----------------------------------------------------------------------
+ @Test
+ public void testFindEmptyTree()
+ {
+ assertNull( tree.find( ONE ) );
}
@Test
- public void testRemoveOneNode()
+ public void testFindNullFromEmptyTree()
{
- tree.insert( 1 );
- assertEquals( 1, tree.getSize() );
+ assertNull( tree.find( null ) );
+ }
- tree.remove( 1 );
- assertEquals( 0, tree.getSize() );
+
+ @Test
+ public void testFindExistingElement()
+ {
+ tree.insert( ZERO );
+ tree.insert( TWO );
+ tree.insert( FOUR );
+ tree.insert( SIX );
+ tree.insert( EIGHT );
+
+ assertEquals( ZERO, tree.find( 0 ) );
+ assertEquals( TWO, tree.find( 2 ) );
+ assertEquals( FOUR, tree.find( 4 ) );
+ assertEquals( SIX, tree.find( 6 ) );
+ assertEquals( EIGHT, tree.find( 8 ) );
}
@Test
- public void testRemoveOneNodeWithRight()
+ public void testFindNonExistingElement()
{
- tree.insert( 1 );
- tree.insert( 2 );
- assertEquals( 2, tree.getSize() );
- assertEquals( "1, 2", tree.toString() );
+ tree.insert( ZERO );
+ tree.insert( TWO );
+ tree.insert( FOUR );
+ tree.insert( SIX );
+ tree.insert( EIGHT );
+
+ assertNull( tree.find( -1 ) );
+ assertNull( tree.find( 1 ) );
+ assertNull( tree.find( 3 ) );
+ assertNull( tree.find( 5 ) );
+ assertNull( tree.find( 7 ) );
+ assertNull( tree.find( 9 ) );
+ }
- tree.remove( 1 );
- assertEquals( 1, tree.getSize() );
- assertEquals( Integer.valueOf( 2 ), tree.getFirst() );
+
+ //-----------------------------------------------------------------------
+ // Test getFirst()
+ //-----------------------------------------------------------------------
+ @Test
+ public void testGetFirstEmptyTree()
+ {
+ assertNull( tree.getFirst() );
}
@Test
- public void testNext()
+ public void testGetFirst()
{
- tree.insert( 1 );
- tree.insert( 70 );
- tree.insert( 21 );
- tree.insert( 12 );
- tree.insert( 27 );
- tree.insert( 11 );
+ tree.insert( FIVE );
+ assertEquals( FIVE, tree.getFirst() );
+
+ tree.insert( TEN );
+ assertEquals( FIVE, tree.getFirst() );
+
+ tree.insert( ONE );
+ assertEquals( ONE, tree.getFirst() );
+
+ tree.insert( TWO );
+ assertEquals( ONE, tree.getFirst() );
+
+ tree.remove( ONE );
+ assertEquals( TWO, tree.getFirst() );
+ }
+
- 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 getLast()
+ //-----------------------------------------------------------------------
+ @Test
+ public void testGetLastEmptyTree()
+ {
+ assertNull( tree.getLast() );
}
@Test
- public void testPrevious()
+ public void testGetLast()
{
- tree.insert( 1 );
- tree.insert( 70 );
- tree.insert( 21 );
- tree.insert( 12 );
- tree.insert( 27 );
- tree.insert( 11 );
+ tree.insert( FIVE );
+ assertEquals( FIVE, tree.getLast() );
+
+ tree.insert( TEN );
+ assertEquals( TEN, tree.getLast() );
+
+ tree.insert( EIGHT );
+ assertEquals( TEN, tree.getLast() );
+
+ tree.insert( ELEVEN );
+ assertEquals( ELEVEN, tree.getLast() );
+
+ tree.remove( ELEVEN );
+ assertEquals( TEN, tree.getLast() );
+ }
+
+
+ //-----------------------------------------------------------------------
+ // Test findGreater()
+ //-----------------------------------------------------------------------
+ @Test
+ public void testFindGreaterEmptyTree()
+ {
+ assertNull( tree.findGreater( ONE ) );
+ }
+
+
+ @Test
+ public void testFindGreaterNullFromEmptyTree()
+ {
+ assertNull( tree.findGreater( null ) );
+ }
+
+
+ @Test
+ public void testFindGreaterFromOneElementTree()
+ {
+ tree.insert( TWO );
+
+ assertNull( tree.findGreater( null ) );
+ assertEquals( TWO, tree.findGreater( ONE ) );
+ assertNull( tree.findGreater( TWO ) );
+ assertNull( tree.findGreater( THREE ) );
+ }
+
+
+ @Test
+ public void testFindGreaterFromTwoElementsTree()
+ {
+ tree.insert( TWO );
+ tree.insert( FOUR );
+
+ assertNull( tree.findGreater( null ) );
+ assertEquals( TWO, tree.findGreater( ONE ) );
+ assertEquals( FOUR, tree.findGreater( TWO ) );
+ assertEquals( FOUR, tree.findGreater( THREE ) );
+ assertNull( tree.findGreater( FOUR ) );
+ assertNull( tree.findGreater( FIVE ) );
+ }
+
+
+ @Test
+ public void testFindGreater()
+ {
+ tree.insert( ZERO );
+ tree.insert( TWO );
+ tree.insert( FOUR );
+ tree.insert( SIX );
+ tree.insert( EIGHT );
+ tree.insert( TEN );
+
+ assertEquals( ZERO, tree.findGreater( MINUS_ONE ) );
+ assertNotSame( ONE, tree.findGreater( ONE ) );
+ assertEquals( TWO, tree.findGreater( ONE ) );
+ assertEquals( SIX, tree.findGreater( FIVE ) );
+ tree.remove( SIX );
+ assertEquals( EIGHT, tree.findGreater( FIVE ) );
+ assertNull( tree.findGreater( TEN ) );
+ }
+
+
+ //-----------------------------------------------------------------------
+ // Test findGreaterOrEqual()
+ //-----------------------------------------------------------------------
+ @Test
+ public void testFindGreaterOrEqualEmptyTree()
+ {
+ assertNull( tree.findGreaterOrEqual( ONE ) );
+ }
+
+
+ @Test
+ public void testFindGreaterOrEqualNullFromEmptyTree()
+ {
+ assertNull( tree.findGreaterOrEqual( null ) );
+ }
+
+
+
+
+ @Test
+ public void testFindGreaterOrEqualFromOneElementTree()
+ {
+ tree.insert( TWO );
+
+ assertNull( tree.findGreaterOrEqual( null ) );
+ assertEquals( TWO, tree.findGreaterOrEqual( ONE ) );
+ assertEquals( TWO, tree.findGreaterOrEqual( TWO ) );
+ assertNull( tree.findGreaterOrEqual( THREE ) );
+ }
+
+
+ @Test
+ public void testFindGreaterOrEqualFromTwoElementsTree()
+ {
+ tree.insert( TWO );
+ tree.insert( FOUR );
+
+ assertNull( tree.findGreaterOrEqual( null ) );
+ assertEquals( TWO, tree.findGreaterOrEqual( ONE ) );
+ assertEquals( TWO, tree.findGreaterOrEqual( TWO ) );
+ assertEquals( FOUR, tree.findGreaterOrEqual( THREE ) );
+ assertEquals( FOUR, tree.findGreaterOrEqual( FOUR ) );
+ assertNull( tree.findGreaterOrEqual( FIVE ) );
+ }
+
+
+ @Test
+ public void testFindGreaterOrEqual()
+ {
+ tree.insert( ZERO );
+ tree.insert( TWO );
+ tree.insert( FOUR );
+ tree.insert( SIX );
+ tree.insert( EIGHT );
+ tree.insert( TEN );
- 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() );
+ assertEquals( ZERO, tree.findGreater( MINUS_ONE ) );
+ assertNotSame( ONE, tree.findGreaterOrEqual( ONE ) );
+ assertEquals( TWO, tree.findGreaterOrEqual( ONE ) );
+ assertEquals( TWO, tree.findGreaterOrEqual( TWO ) );
+ assertEquals( SIX, tree.findGreaterOrEqual( FIVE ) );
+ tree.remove( SIX );
+ assertEquals( EIGHT, tree.findGreaterOrEqual( FIVE ) );
+ assertEquals( TEN, tree.findGreaterOrEqual( TEN ) );
+ assertNull( tree.findGreaterOrEqual( ELEVEN ) );
+ }
+
+
+ //-----------------------------------------------------------------------
+ // Test findLess()
+ //-----------------------------------------------------------------------
+ @Test
+ public void testFindLessEmptyTree()
+ {
+ assertNull( tree.findLess( ONE ) );
+ }
+
+
+ @Test
+ public void testFindLessNullFromEmptyTree()
+ {
+ assertNull( tree.findLess( null ) );
+ }
+
+
+ @Test
+ public void testFindLessFromOneElementTree()
+ {
+ tree.insert( TWO );
+
+ assertNull( tree.findLess( null ) );
+ assertNull( tree.findLess( ONE ) );
+ assertNull( tree.findLess( TWO ) );
+ assertEquals( TWO, tree.findLess( THREE ) );
+ }
+
+
+ @Test
+ public void testFindLessFromTwoElementsTree()
+ {
+ tree.insert( TWO );
+ tree.insert( FOUR );
+
+ assertNull( tree.findLess( null ) );
+ assertNull( tree.findLess( ONE ) );
+ assertNull( tree.findLess( TWO ) );
+ assertEquals( TWO, tree.findLess( THREE ) );
+ assertEquals( TWO, tree.findLess( FOUR ) );
+ assertEquals( FOUR, tree.findLess( FIVE ) );
+ }
+
+
+ @Test
+ public void testFindLess()
+ {
+ tree.insert( ZERO );
+ tree.insert( TWO );
+ tree.insert( FOUR );
+ tree.insert( SIX );
+ tree.insert( EIGHT );
+ tree.insert( TEN );
+
+ assertNull( tree.findLess( ZERO ) );
+ assertNotSame( ONE, tree.findLess( ONE ) );
+ assertEquals( ZERO, tree.findLess( ONE ) );
+ assertEquals( FOUR, tree.findLess( FIVE ) );
+ tree.remove( FOUR );
+ assertEquals( TWO, tree.findLess( FIVE ) );
+ assertEquals( EIGHT, tree.findLess( TEN ) );
+ assertEquals( TEN, tree.findLess( SEVENTY ) );
+ }
+
+
+ //-----------------------------------------------------------------------
+ // Test findLessOrEqual()
+ //-----------------------------------------------------------------------
+ @Test
+ public void testFindLessOrEqualEmptyTree()
+ {
+ assertNull( tree.findLessOrEqual( ONE ) );
+ }
+
+
+ @Test
+ public void testFindLessOrEqualNullFromEmptyTree()
+ {
+ assertNull( tree.findLessOrEqual( null ) );
+ }
+
+
+ @Test
+ public void testFindLessOrEqualFromOneElementTree()
+ {
+ tree.insert( TWO );
+
+ assertNull( tree.findLessOrEqual( null ) );
+ assertNull( tree.findLessOrEqual( ONE ) );
+ assertEquals( TWO, tree.findLessOrEqual( TWO ) );
+ assertEquals( TWO, tree.findLessOrEqual( THREE ) );
+ }
+
+
+ @Test
+ public void testFindLessOrEqualFromTwoElementsTree()
+ {
+ tree.insert( TWO );
+ tree.insert( FOUR );
+
+ assertNull( tree.findLessOrEqual( null ) );
+ assertNull( tree.findLessOrEqual( ONE ) );
+ assertEquals( TWO, tree.findLessOrEqual( TWO ) );
+ assertEquals( TWO, tree.findLessOrEqual( THREE ) );
+ assertEquals( FOUR, tree.findLessOrEqual( FOUR ) );
+ assertEquals( FOUR, tree.findLessOrEqual( FIVE ) );
+ }
+
+
+ @Test
+ public void testFindLessOrEqual()
+ {
+ tree.insert( ZERO );
+ tree.insert( TWO );
+ tree.insert( FOUR );
+ tree.insert( SIX );
+ tree.insert( EIGHT );
+ tree.insert( TEN );
+
+ assertNull( tree.findLessOrEqual( MINUS_ONE ) );
+ assertEquals( ZERO, tree.findLessOrEqual( ZERO ) );
+ assertEquals( ZERO, tree.findLessOrEqual( ONE ) );
+ assertEquals( TWO, tree.findLessOrEqual( THREE ) );
+ assertEquals( FOUR, tree.findLessOrEqual( FIVE ) );
+ tree.remove( FOUR );
+ assertEquals( TWO, tree.findLessOrEqual( FIVE ) );
+ assertEquals( EIGHT, tree.findLessOrEqual( NINE ) );
+ assertEquals( TEN, tree.findLessOrEqual( TEN ) );
+ assertEquals( TEN, tree.findLessOrEqual( ELEVEN ) );
+ }
+
+
+ //-----------------------------------------------------------------------
+ // Test get( int position )
+ //-----------------------------------------------------------------------
+ @Test
+ public void testGetEmptyTree()
+ {
+ try
+ {
+ assertNull( tree.get( 0 ) );
+ fail();
+ }
+ catch ( ArrayIndexOutOfBoundsException aioobe )
+ {
+ assertTrue( true );
+ }
+ }
+
+
+ @Test
+ public void testGetEmptyTreeAIOOBException()
+ {
+ try
+ {
+ tree.get( -1 );
+ fail();
+ }
+ catch ( ArrayIndexOutOfBoundsException aioobe )
+ {
+ assertTrue( true );
+ }
+
+ try
+ {
+ tree.get( 1 );
+ fail();
+ }
+ catch ( ArrayIndexOutOfBoundsException aioobe )
+ {
+ assertTrue( true );
+ }
+ }
+
+
+ //-----------------------------------------------------------------------
+ // Test getAfterPosition( K key )
+ //-----------------------------------------------------------------------
+ @Test
+ public void testGetAfterPositionEmptyTree()
+ {
+ assertEquals( -1, tree.getAfterPosition( ZERO ) );
+ }
+
+
+ @Test
+ public void testGetAfterPositionOneElementTree()
+ {
+ tree.insert( TWO );
+
+ assertEquals( -1, tree.getAfterPosition( null ) );
+ assertEquals( 0, tree.getAfterPosition( ZERO ) );
+ assertEquals( -1, tree.getAfterPosition( TWO ) );
+ assertEquals( -1, tree.getAfterPosition( FOUR ) );
+ }
+
+
+ @Test
+ public void testGetAfterPositionTwoElementsTree()
+ {
+ tree.insert( TWO );
+ tree.insert( FOUR );
+
+ assertEquals( -1, tree.getAfterPosition( null ) );
+ assertEquals( 0, tree.getAfterPosition( ZERO ) );
+ assertEquals( 1, tree.getAfterPosition( TWO ) );
+ assertEquals( 1, tree.getAfterPosition( THREE ) );
+ assertEquals( -1, tree.getAfterPosition( FOUR ) );
+ }
+
+
+ @Test
+ public void testGetAfterPositionNElementsTree()
+ {
+ tree.insert( TWO );
+ tree.insert( FOUR );
+ tree.insert( SIX );
+ tree.insert( EIGHT );
+
+ assertEquals( -1, tree.getAfterPosition( null ) );
+ assertEquals( 0, tree.getAfterPosition( ZERO ) );
+ assertEquals( 1, tree.getAfterPosition( TWO ) );
+ assertEquals( 1, tree.getAfterPosition( THREE ) );
+ assertEquals( 2, tree.getAfterPosition( FOUR ) );
+ assertEquals( 2, tree.getAfterPosition( FIVE ) );
+ assertEquals( 3, tree.getAfterPosition( SIX ) );
+ assertEquals( 3, tree.getAfterPosition( SEVEN ) );
+ assertEquals( -1, tree.getAfterPosition( EIGHT ) );
+ }
+
+
+ //-----------------------------------------------------------------------
+ // Test getBeforePosition( K key )
+ //-----------------------------------------------------------------------
+ @Test
+ public void testGetBeforePositionEmptyTree()
+ {
+ assertEquals( -1, tree.getBeforePosition( ZERO ) );
+ }
+
+
+ @Test
+ public void testGetBeforePositionOneElementTree()
+ {
+ tree.insert( TWO );
+
+ assertEquals( -1, tree.getBeforePosition( null ) );
+ assertEquals( -1, tree.getBeforePosition( ZERO ) );
+ assertEquals( -1, tree.getBeforePosition( TWO ) );
+ assertEquals( 0, tree.getBeforePosition( FOUR ) );
+ }
+
+
+ @Test
+ public void testGetBeforePositionTwoElementsTree()
+ {
+ tree.insert( TWO );
+ tree.insert( FOUR );
+
+ assertEquals( -1, tree.getBeforePosition( null ) );
+ assertEquals( -1, tree.getBeforePosition( ZERO ) );
+ assertEquals( -1, tree.getBeforePosition( TWO ) );
+ assertEquals( 0, tree.getBeforePosition( THREE ) );
+ assertEquals( 0, tree.getBeforePosition( FOUR ) );
+ assertEquals( 1, tree.getBeforePosition( FIVE ) );
+ }
+
+
+ @Test
+ public void testGetBeforePositionNElementsTree()
+ {
+ tree.insert( TWO );
+ tree.insert( FOUR );
+ tree.insert( SIX );
+ tree.insert( EIGHT );
+
+ assertEquals( -1, tree.getBeforePosition( null ) );
+ assertEquals( -1, tree.getBeforePosition( ZERO ) );
+ assertEquals( -1, tree.getBeforePosition( TWO ) );
+ assertEquals( 0, tree.getBeforePosition( THREE ) );
+ assertEquals( 0, tree.getBeforePosition( FOUR ) );
+ assertEquals( 1, tree.getBeforePosition( FIVE ) );
+ assertEquals( 1, tree.getBeforePosition( SIX ) );
+ assertEquals( 2, tree.getBeforePosition( SEVEN ) );
+ assertEquals( 2, tree.getBeforePosition( EIGHT ) );
+ assertEquals( 3, tree.getBeforePosition( NINE ) );
}
}