Modified: directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/SingletonOrOrderedSet.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/SingletonOrOrderedSet.java?rev=1235258&r1=1235257&r2=1235258&view=diff
==============================================================================
--- directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/SingletonOrOrderedSet.java (original)
+++ directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/SingletonOrOrderedSet.java Tue Jan 24 14:10:56 2012
@@ -19,6 +19,7 @@
*/
package org.apache.directory.server.core.avltree;
+
import org.apache.directory.server.i18n.I18n;
@@ -31,8 +32,8 @@ public class SingletonOrOrderedSet<V>
{
private V singleton;
private AvlTree<V> orderedSet;
-
-
+
+
/**
* Creates a new instance of SingletonOrOrderedSet with a singleton value.
*
@@ -44,11 +45,11 @@ public class SingletonOrOrderedSet<V>
{
throw new IllegalArgumentException( I18n.err( I18n.ERR_447 ) );
}
-
+
this.singleton = singleton;
}
-
-
+
+
/**
* Creates a new instance of SingletonOrOrderedSet with a set of ordered
* values.
@@ -61,10 +62,10 @@ public class SingletonOrOrderedSet<V>
{
throw new IllegalArgumentException( I18n.err( I18n.ERR_448 ) );
}
-
+
this.orderedSet = orderedSet;
}
-
+
/**
* Gets whether or not the stored value is a singleton.
@@ -75,8 +76,8 @@ public class SingletonOrOrderedSet<V>
{
return singleton != null;
}
-
-
+
+
/**
* Gets whether or not the stored value is an ordered set.
*
@@ -86,7 +87,7 @@ public class SingletonOrOrderedSet<V>
{
return orderedSet != null;
}
-
+
/**
* Gets the singleton value.
@@ -100,11 +101,11 @@ public class SingletonOrOrderedSet<V>
{
return singleton;
}
-
+
throw new RuntimeException( I18n.err( I18n.ERR_449 ) );
}
-
-
+
+
/**
* Sets the singleton if in singleton mode.
*
@@ -117,18 +118,18 @@ public class SingletonOrOrderedSet<V>
{
throw new IllegalArgumentException( I18n.err( I18n.ERR_447 ) );
}
-
+
if ( this.orderedSet != null )
{
throw new RuntimeException( I18n.err( I18n.ERR_450 ) );
}
-
+
V retval = this.singleton;
this.singleton = singleton;
return retval;
}
-
-
+
+
/**
* Switches from orderedSet mode to singleton mode, while returning the
* ordered set of values before removing them forever.
@@ -143,19 +144,19 @@ public class SingletonOrOrderedSet<V>
{
throw new IllegalArgumentException( I18n.err( I18n.ERR_447 ) );
}
-
+
if ( this.singleton != null )
{
throw new RuntimeException( I18n.err( I18n.ERR_451 ) );
}
-
+
AvlTree<V> retval = this.orderedSet;
this.orderedSet = null;
this.singleton = singleton;
return retval;
}
-
-
+
+
/**
* Gets the ordered set.
*
@@ -168,11 +169,11 @@ public class SingletonOrOrderedSet<V>
{
return orderedSet;
}
-
+
throw new RuntimeException( I18n.err( I18n.ERR_452 ) );
}
-
-
+
+
/**
* Sets the set of ordered values.
*
@@ -186,18 +187,18 @@ public class SingletonOrOrderedSet<V>
{
throw new IllegalArgumentException( I18n.err( I18n.ERR_448 ) );
}
-
+
if ( this.singleton != null )
{
throw new RuntimeException( I18n.err( I18n.ERR_453 ) );
}
-
+
AvlTree<V> retval = this.orderedSet;
this.orderedSet = orderedSet;
return retval;
}
-
-
+
+
/**
* Switches from orderedSet mode to singleton mode, while returning the
* singleton value before removing it forever.
@@ -212,12 +213,12 @@ public class SingletonOrOrderedSet<V>
{
throw new IllegalArgumentException( I18n.err( I18n.ERR_448 ) );
}
-
+
if ( this.orderedSet != null )
{
throw new RuntimeException( I18n.err( I18n.ERR_454 ) );
}
-
+
V retval = this.singleton;
this.orderedSet = orderedSet;
this.singleton = null;
Modified: directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/avl/AvlTreeSet.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/avl/AvlTreeSet.java?rev=1235258&r1=1235257&r2=1235258&view=diff
==============================================================================
--- directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/avl/AvlTreeSet.java (original)
+++ directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/avl/AvlTreeSet.java Tue Jan 24 14:10:56 2012
@@ -19,286 +19,390 @@
*/
package org.apache.directory.server.core.avltree.avl;
+
import java.util.Iterator;
import java.util.Stack;
+
/**
* AVL Tree Set
*
* @author Vladimir Lysyy (http://bobah.net)
*
*/
-public class AvlTreeSet<T extends Comparable<T>> implements Iterable<T> {
+public class AvlTreeSet<T extends Comparable<T>> implements Iterable<T>
+{
- private AvlNode<T> tree;
- private int size = 0;
+ private AvlNode<T> tree;
+ private int size = 0;
- final boolean useFreeList;
+ final boolean useFreeList;
- public AvlTreeSet() {
- this(false);
- }
-
- public AvlTreeSet(boolean useFreeList) {
- this.useFreeList = useFreeList;
- }
-
- public final int height() {
- return (tree == null) ? 0 : tree.height + 1;
- }
-
- public final int size() {
- return size;
- }
-
- public final Iterator<T> iterator() {
- return new AvlTreeIterator<T>(tree);
- }
-
- public final boolean insert(T value) {
- // empty tree case
- if (tree == null) {
- tree = new_node(null, value);
- ++size;
- return true;
- }
-
- AvlNode<T> node = tree;
-
- // find the place and insert the value
- int cmp = value.compareTo(node.value);
- for (; cmp != 0; cmp = value.compareTo(node.value)) {
- if (cmp < 0) {
- if (node.left == null) { node.left = new_node(node, value); break; }
- else node = node.left;
- }
- else if (cmp > 0) {
- if (node.right == null) { node.right = new_node(node, value); break; }
- else node = node.right;
- }
- else assert false : "should never happen";
- }
-
- // node with _value_ already exists
- if (cmp == 0) return false;
- rebalance_up(node);
- ++ size;
-
- return true;
- }
-
- Stack<AvlNode<T>> free_list = new Stack<AvlNode<T>>();
- private final AvlNode<T> new_node(AvlNode<T> parent, T value) {
- if (!useFreeList || free_list.isEmpty()) return new AvlNode<T>(parent, value);
- else {
- AvlNode<T> node = free_list.pop();
- return node.reset(parent, value);
- }
- }
-
- private final void recycle_node(AvlNode<T> node) {
- if (!useFreeList) return;
-
- // keep free list size not bigger than tree size
- while (free_list.size() > size) free_list.pop();
- if (free_list.size() == size) return;
-
- free_list.push(node);
- }
-
- private void rebalance_up(AvlNode<T> node) {
- while (node != null) {
- int height_before = node.height;
- update_height(node);
-
- // rebalance
- if (node.balance == -2) node = big_right_rotation(node);
- else if (node.balance == 2) node = big_left_rotation(node);
-
- if (node.parent == null) tree = node;
-
- // if parent node is not affected
- if (height_before == node.height) break;
-
- node = node.parent;
- }
- }
-
- public final boolean remove(T value) {
- AvlNode<T> node = tree;
- if (node == null) return false;
-
- // find the node to be removed
- for (int cmp = value.compareTo(node.value); cmp != 0; cmp = value.compareTo(node.value)) {
- node = (cmp < 0) ? node.left : node.right;
- if (node == null) return false;
- }
-
- // find a replacement node (if needed)
- final int LEFT = -1;
- final int RIGHT = 1;
- final int NONE = 0;
- int replaceFrom = NONE;
- if (node.left != null && node.right == null) {
- replaceFrom = LEFT;
- }
- else if (node.right != null && node.left == null) {
- replaceFrom = RIGHT;
- }
- else if (node.right != null && node.left != null) {
- if (node.balance < 0) {
- replaceFrom = LEFT;
- }
- else if (node.balance > 0) {
- replaceFrom = RIGHT;
- }
- else {
- replaceFrom = LEFT; // TODO: asymmetry
- }
- }
- else { // node is itself a leaf, replacement is not needed
- if (node.parent == null) { // the tree root, single node in the tree
- tree = null; --size;
- recycle_node(node);
- return true;
- }
- else { // non-root leaf node
- // detach from parent
- if (node.parent.left == node) node.parent.left = null;
- else node.parent.right = null;
- AvlNode<T> dead = node;
- node = node.parent; // update heights/rebalance from node's parents up (the bottom of this method)
- recycle_node(dead);
- replaceFrom = NONE;
- }
+ public AvlTreeSet()
+ {
+ this( false );
+ }
+
+
+ public AvlTreeSet( boolean useFreeList )
+ {
+ this.useFreeList = useFreeList;
+ }
+
+
+ public final int height()
+ {
+ return ( tree == null ) ? 0 : tree.height + 1;
+ }
+
+
+ public final int size()
+ {
+ return size;
+ }
+
+
+ public final Iterator<T> iterator()
+ {
+ return new AvlTreeIterator<T>( tree );
}
- if (replaceFrom != NONE) {
- AvlNode<T> leaf = null;
- if (replaceFrom == LEFT) {
- leaf = node.left;
- while (leaf.left != null || leaf.right != null) {
- if (leaf.right != null) leaf = leaf.right;
- else leaf = small_right_rotation(leaf); // the rotation should ensure (leaf.right != null) on the next iteration
+
+ public final boolean insert( T value )
+ {
+ // empty tree case
+ if ( tree == null )
+ {
+ tree = new_node( null, value );
+ ++size;
+ return true;
}
- }
- else if (replaceFrom == RIGHT) {
- leaf = node.right;
- while (leaf.right != null || leaf.left != null) {
- if (leaf.left != null) leaf = leaf.left;
- else leaf = small_left_rotation(leaf); // the rotation should ensure (leaf.left != null) on the next iteration
+
+ AvlNode<T> node = tree;
+
+ // find the place and insert the value
+ int cmp = value.compareTo( node.value );
+ for ( ; cmp != 0; cmp = value.compareTo( node.value ) )
+ {
+ if ( cmp < 0 )
+ {
+ if ( node.left == null )
+ {
+ node.left = new_node( node, value );
+ break;
+ }
+ else
+ node = node.left;
+ }
+ else if ( cmp > 0 )
+ {
+ if ( node.right == null )
+ {
+ node.right = new_node( node, value );
+ break;
+ }
+ else
+ node = node.right;
+ }
+ else
+ assert false : "should never happen";
}
- }
- else assert false : "should never happen";
- assert leaf != null : "replacement leaf should always exist at this point";
+ // node with _value_ already exists
+ if ( cmp == 0 )
+ return false;
+ rebalance_up( node );
+ ++size;
+
+ return true;
+ }
- // detach leaf from its parent
- if (leaf.parent.left == leaf) leaf.parent.left = null;
- else if (leaf.parent.right == leaf) leaf.parent.right = null;
- else assert false : "broken parent/child reference in the tree";
+ Stack<AvlNode<T>> free_list = new Stack<AvlNode<T>>();
- node.value = leaf.value; // replace node value with leaf's value
- node = leaf.parent; // change recursion point down so that below down-up update picks up
- // everything from leaf's parent up
- recycle_node(leaf);
+ private final AvlNode<T> new_node( AvlNode<T> parent, T value )
+ {
+ if ( !useFreeList || free_list.isEmpty() )
+ return new AvlNode<T>( parent, value );
+ else
+ {
+ AvlNode<T> node = free_list.pop();
+ return node.reset( parent, value );
+ }
}
- rebalance_up(node);
- -- size;
+ private final void recycle_node( AvlNode<T> node )
+ {
+ if ( !useFreeList )
+ return;
+
+ // keep free list size not bigger than tree size
+ while ( free_list.size() > size )
+ free_list.pop();
+ if ( free_list.size() == size )
+ return;
+
+ free_list.push( node );
+ }
+
- return true;
- }
+ private void rebalance_up( AvlNode<T> node )
+ {
+ while ( node != null )
+ {
+ int height_before = node.height;
+ update_height( node );
+
+ // rebalance
+ if ( node.balance == -2 )
+ node = big_right_rotation( node );
+ else if ( node.balance == 2 )
+ node = big_left_rotation( node );
+
+ if ( node.parent == null )
+ tree = node;
+
+ // if parent node is not affected
+ if ( height_before == node.height )
+ break;
- public final boolean contains(T value) {
- AvlNode<T> node = tree;
- while (node != null) {
- int cmp = value.compareTo(node.value);
- if (cmp < 0) node = node.left;
- else if (cmp > 0) node = node.right;
- else return true;
+ node = node.parent;
+ }
}
- return false;
- }
- private static final <T extends Comparable<T>> void update_height(AvlNode<T> node) {
- int left_height = (node.left == null) ? -1 : node.left.height;
- int right_height = (node.right == null) ? -1 : node.right.height;
- node.height = 1 + (right_height > left_height ? right_height : left_height);
- node.balance = right_height - left_height;
- }
+ public final boolean remove( T value )
+ {
+ AvlNode<T> node = tree;
+ if ( node == null )
+ return false;
+
+ // find the node to be removed
+ for ( int cmp = value.compareTo( node.value ); cmp != 0; cmp = value.compareTo( node.value ) )
+ {
+ node = ( cmp < 0 ) ? node.left : node.right;
+ if ( node == null )
+ return false;
+ }
- private static final <T extends Comparable<T>> AvlNode<T> small_left_rotation(AvlNode<T> node) {
- assert node.balance > 0 : "null right child in small_left";
+ // find a replacement node (if needed)
+ final int LEFT = -1;
+ final int RIGHT = 1;
+ final int NONE = 0;
+ int replaceFrom = NONE;
+ if ( node.left != null && node.right == null )
+ {
+ replaceFrom = LEFT;
+ }
+ else if ( node.right != null && node.left == null )
+ {
+ replaceFrom = RIGHT;
+ }
+ else if ( node.right != null && node.left != null )
+ {
+ if ( node.balance < 0 )
+ {
+ replaceFrom = LEFT;
+ }
+ else if ( node.balance > 0 )
+ {
+ replaceFrom = RIGHT;
+ }
+ else
+ {
+ replaceFrom = LEFT; // TODO: asymmetry
+ }
+ }
+ else
+ { // node is itself a leaf, replacement is not needed
+ if ( node.parent == null )
+ { // the tree root, single node in the tree
+ tree = null;
+ --size;
+ recycle_node( node );
+ return true;
+ }
+ else
+ { // non-root leaf node
+ // detach from parent
+ if ( node.parent.left == node )
+ node.parent.left = null;
+ else
+ node.parent.right = null;
+
+ AvlNode<T> dead = node;
+ node = node.parent; // update heights/rebalance from node's parents up (the bottom of this method)
+ recycle_node( dead );
+ replaceFrom = NONE;
+ }
+ }
+
+ if ( replaceFrom != NONE )
+ {
+ AvlNode<T> leaf = null;
+ if ( replaceFrom == LEFT )
+ {
+ leaf = node.left;
+ while ( leaf.left != null || leaf.right != null )
+ {
+ if ( leaf.right != null )
+ leaf = leaf.right;
+ else
+ leaf = small_right_rotation( leaf ); // the rotation should ensure (leaf.right != null) on the next iteration
+ }
+ }
+ else if ( replaceFrom == RIGHT )
+ {
+ leaf = node.right;
+ while ( leaf.right != null || leaf.left != null )
+ {
+ if ( leaf.left != null )
+ leaf = leaf.left;
+ else
+ leaf = small_left_rotation( leaf ); // the rotation should ensure (leaf.left != null) on the next iteration
+ }
+ }
+ else
+ assert false : "should never happen";
+
+ assert leaf != null : "replacement leaf should always exist at this point";
+
+ // detach leaf from its parent
+ if ( leaf.parent.left == leaf )
+ leaf.parent.left = null;
+ else if ( leaf.parent.right == leaf )
+ leaf.parent.right = null;
+ else
+ assert false : "broken parent/child reference in the tree";
+
+ node.value = leaf.value; // replace node value with leaf's value
+ node = leaf.parent; // change recursion point down so that below down-up update picks up
+ // everything from leaf's parent up
+
+ recycle_node( leaf );
+ }
+
+ rebalance_up( node );
+
+ --size;
- // update child references
- AvlNode<T> right = node.right;
- node.right = right.left;
- right.left = node;
+ return true;
+ }
- // update parent references
- if (node.right != null) node.right.parent = node;
- right.parent = node.parent;
- if (right.parent != null) {
- if (right.parent.left == node) node.parent.left = right;
- else node.parent.right = right;
+ public final boolean contains( T value )
+ {
+ AvlNode<T> node = tree;
+ while ( node != null )
+ {
+ int cmp = value.compareTo( node.value );
+ if ( cmp < 0 )
+ node = node.left;
+ else if ( cmp > 0 )
+ node = node.right;
+ else
+ return true;
+ }
+ return false;
+
}
- node.parent = right;
- update_height(node);
- update_height(right);
+ private static final <T extends Comparable<T>> void update_height( AvlNode<T> node )
+ {
+ int left_height = ( node.left == null ) ? -1 : node.left.height;
+ int right_height = ( node.right == null ) ? -1 : node.right.height;
+ node.height = 1 + ( right_height > left_height ? right_height : left_height );
+ node.balance = right_height - left_height;
+ }
+
- return right;
- }
+ private static final <T extends Comparable<T>> AvlNode<T> small_left_rotation( AvlNode<T> node )
+ {
+ assert node.balance > 0 : "null right child in small_left";
- private static final <T extends Comparable<T>> AvlNode<T> small_right_rotation(AvlNode<T> node) {
- assert node.balance < 0 : "null left child in small_right";
+ // update child references
+ AvlNode<T> right = node.right;
+ node.right = right.left;
+ right.left = node;
- // update child references
- AvlNode<T> left = node.left;
- node.left = left.right;
- left.right = node;
+ // update parent references
+ if ( node.right != null )
+ node.right.parent = node;
+ right.parent = node.parent;
- // update parent references
- if (node.left != null) node.left.parent = node;
- left.parent = node.parent;
+ if ( right.parent != null )
+ {
+ if ( right.parent.left == node )
+ node.parent.left = right;
+ else
+ node.parent.right = right;
+ }
- if (left.parent != null) {
- if (left.parent.left == node) node.parent.left = left;
- else node.parent.right = left;
+ node.parent = right;
+
+ update_height( node );
+ update_height( right );
+
+ return right;
}
- node.parent = left;
- update_height(node);
- update_height(left);
+ private static final <T extends Comparable<T>> AvlNode<T> small_right_rotation( AvlNode<T> node )
+ {
+ assert node.balance < 0 : "null left child in small_right";
- return left;
- }
+ // update child references
+ AvlNode<T> left = node.left;
+ node.left = left.right;
+ left.right = node;
- private static final <T extends Comparable<T>> AvlNode<T> big_left_rotation(AvlNode<T> node) {
- assert node.right != null : "null right child in big_left";
+ // update parent references
+ if ( node.left != null )
+ node.left.parent = node;
+ left.parent = node.parent;
- if (node.right.balance < 0) node.right = small_right_rotation(node.right);
+ if ( left.parent != null )
+ {
+ if ( left.parent.left == node )
+ node.parent.left = left;
+ else
+ node.parent.right = left;
+ }
- update_height(node);
+ node.parent = left;
- return small_left_rotation(node);
- }
+ update_height( node );
+ update_height( left );
- private static final <T extends Comparable<T>> AvlNode<T> big_right_rotation(AvlNode<T> node) {
- assert node.left != null : "null right child in big_right";
+ return left;
+ }
- if (node.left.balance > 0) node.left = small_left_rotation(node.left);
- update_height(node);
+ private static final <T extends Comparable<T>> AvlNode<T> big_left_rotation( AvlNode<T> node )
+ {
+ assert node.right != null : "null right child in big_left";
- return small_right_rotation(node);
- }
+ if ( node.right.balance < 0 )
+ node.right = small_right_rotation( node.right );
+
+ update_height( node );
+
+ return small_left_rotation( node );
+ }
+
+
+ private static final <T extends Comparable<T>> AvlNode<T> big_right_rotation( AvlNode<T> node )
+ {
+ assert node.left != null : "null right child in big_right";
+
+ if ( node.left.balance > 0 )
+ node.left = small_left_rotation( node.left );
+
+ update_height( node );
+
+ return small_right_rotation( node );
+ }
}
Modified: 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=1235258&r1=1235257&r2=1235258&view=diff
==============================================================================
--- directory/apacheds/trunk/core-avl/src/test/java/org/apache/directory/server/core/avltree/ArrayTreeCursorTest.java (original)
+++ directory/apacheds/trunk/core-avl/src/test/java/org/apache/directory/server/core/avltree/ArrayTreeCursorTest.java Tue Jan 24 14:10:56 2012
@@ -50,10 +50,10 @@ public class ArrayTreeCursorTest
{
ArrayTree<Integer> tree = new ArrayTree<Integer>( new IntegerComparator() );
ArrayTreeCursor<Integer> cursor = new ArrayTreeCursor<Integer>( tree );
-
+
assertFalse( cursor.isClosed() );
assertFalse( cursor.available() );
-
+
try
{
cursor.get();
@@ -63,76 +63,76 @@ public class ArrayTreeCursorTest
{
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() );
-
+
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() );
@@ -186,8 +186,8 @@ public class ArrayTreeCursorTest
assertTrue( cursor.available() );
assertEquals( 7, ( int ) cursor.get() );
}
-
-
+
+
@Test
public void testManyEntriesCursor() throws Exception
{
@@ -197,11 +197,11 @@ public class ArrayTreeCursorTest
tree.insert( 10 );
tree.insert( 11 );
ArrayTreeCursor<Integer> cursor = new ArrayTreeCursor<Integer>( tree );
-
+
assertFalse( cursor.isClosed() );
assertFalse( cursor.available() );
assertEquals( 4, tree.size() );
-
+
try
{
cursor.get();
@@ -211,7 +211,7 @@ public class ArrayTreeCursorTest
{
assertNotNull( e );
}
-
+
cursor.beforeFirst();
assertFalse( cursor.available() );
assertTrue( cursor.next() );
@@ -228,8 +228,7 @@ public class ArrayTreeCursorTest
assertEquals( 11, ( int ) cursor.get() );
assertFalse( cursor.next() );
assertFalse( cursor.available() );
-
-
+
cursor.afterLast();
assertFalse( cursor.available() );
assertTrue( cursor.previous() );
@@ -246,19 +245,19 @@ public class ArrayTreeCursorTest
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() );
-
+
// position before first object
cursor.after( 2 );
assertTrue( cursor.next() );
@@ -385,8 +384,7 @@ public class ArrayTreeCursorTest
assertFalse( cursor.previous() );
assertFalse( cursor.available() );
}
-
-
+
class IntegerComparator implements Comparator<Integer>
{
public int compare( Integer o1, Integer 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=1235258&r1=1235257&r2=1235258&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 Tue Jan 24 14:10:56 2012
@@ -47,26 +47,26 @@ import org.slf4j.LoggerFactory;
@Concurrency()
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 );
-
+ 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 );
+
private static final Logger LOG = LoggerFactory.getLogger( ArrayTreeTest.class );
@@ -79,9 +79,9 @@ public class ArrayTreeTest
{
if ( i1 == null )
{
- return (i2 == null ? 0 : -1);
+ return ( i2 == null ? 0 : -1 );
}
-
+
return i1.compareTo( i2 );
}
@@ -133,8 +133,8 @@ public class ArrayTreeTest
assertEquals( THREE, tree.getFirst() );
assertEquals( ELEVEN, tree.getLast() );
}
-
-
+
+
@Test
public void testSingleRightRotation()
{
@@ -364,7 +364,7 @@ public class ArrayTreeTest
first = tree.findGreater( first );
}
-
+
sb.append( "NULL" );
return sb.toString();
}
@@ -409,7 +409,7 @@ public class ArrayTreeTest
assertEquals( 0, tree.size() );
}
-
+
@Test
public void testInsertInEmptyTree()
{
@@ -417,12 +417,12 @@ public class ArrayTreeTest
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() );
+ assertEquals( ZERO, tree.get( 0 ) );
+ assertEquals( ZERO, tree.getFirst() );
+ assertEquals( ZERO, tree.getLast() );
}
-
+
@Test
public void testInsertInOnElementTreeAtTheBeginning()
{
@@ -430,7 +430,7 @@ public class ArrayTreeTest
// Initialize the array
assertNull( tree.insert( 5 ) );
assertEquals( 1, tree.size() );
-
+
Integer existing = tree.insert( ZERO );
assertNull( existing );
assertEquals( 2, tree.size() );
@@ -439,7 +439,7 @@ public class ArrayTreeTest
assertEquals( "0, 5", tree.toString() );
}
-
+
@Test
public void testInsertInOnElementTreeAtTheEnd()
{
@@ -447,7 +447,7 @@ public class ArrayTreeTest
// Initialize the array
assertNull( tree.insert( 5 ) );
assertEquals( 1, tree.size() );
-
+
Integer existing = tree.insert( TEN );
assertNull( existing );
assertEquals( 2, tree.size() );
@@ -456,7 +456,7 @@ public class ArrayTreeTest
assertEquals( "5, 10", tree.toString() );
}
-
+
@Test
public void testInsertInOnElementTreeExistingElement()
{
@@ -464,7 +464,7 @@ public class ArrayTreeTest
// Initialize the array
assertNull( tree.insert( 5 ) );
assertEquals( 1, tree.size() );
-
+
Integer existing = tree.insert( FIVE );
assertEquals( 1, tree.size() );
assertEquals( FIVE, existing );
@@ -473,7 +473,7 @@ public class ArrayTreeTest
assertEquals( "5", tree.toString() );
}
-
+
@Test
public void testInsertInEvenTreeAtTheBeginning()
{
@@ -486,7 +486,7 @@ public class ArrayTreeTest
assertNull( tree.insert( EIGHT ) );
assertNull( tree.insert( TEN ) );
assertEquals( 6, tree.size() );
-
+
Integer existing = tree.insert( MINUS_ONE );
assertNull( existing );
assertEquals( 7, tree.size() );
@@ -495,7 +495,7 @@ public class ArrayTreeTest
assertEquals( "-1, 0, 2, 4, 6, 8, 10", tree.toString() );
}
-
+
@Test
public void testInsertInEvenTreeAtTheEnd()
{
@@ -508,7 +508,7 @@ public class ArrayTreeTest
assertNull( tree.insert( EIGHT ) );
assertNull( tree.insert( TEN ) );
assertEquals( 6, tree.size() );
-
+
Integer existing = tree.insert( TWELVE );
assertNull( existing );
assertEquals( 7, tree.size() );
@@ -517,7 +517,7 @@ public class ArrayTreeTest
assertEquals( "0, 2, 4, 6, 8, 10, 12", tree.toString() );
}
-
+
@Test
public void testInsertInEvenTreeInTheMiddle()
{
@@ -530,7 +530,7 @@ public class ArrayTreeTest
assertNull( tree.insert( EIGHT ) );
assertNull( tree.insert( TEN ) );
assertEquals( 6, tree.size() );
-
+
// Insert 1
Integer existing = tree.insert( ONE );
assertNull( existing );
@@ -538,7 +538,7 @@ public class ArrayTreeTest
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 );
@@ -546,7 +546,7 @@ public class ArrayTreeTest
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 );
@@ -556,7 +556,7 @@ public class ArrayTreeTest
assertEquals( "0, 1, 2, 4, 5, 6, 8, 9, 10", tree.toString() );
}
-
+
@Test
public void testInsertInEvenTreeExistingEelemnt()
{
@@ -569,7 +569,7 @@ public class ArrayTreeTest
assertNull( tree.insert( EIGHT ) );
assertNull( tree.insert( TEN ) );
assertEquals( 6, tree.size() );
-
+
// Insert 0
Integer existing = tree.insert( ZERO );
assertEquals( ZERO, existing );
@@ -577,7 +577,7 @@ public class ArrayTreeTest
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 );
@@ -585,7 +585,7 @@ public class ArrayTreeTest
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 );
@@ -602,12 +602,12 @@ public class ArrayTreeTest
ArrayTree<Integer> tree = createTree();
StringBuilder sb = new StringBuilder();
boolean isFirst = true;
-
+
// Initialize the array
for ( int i = 0; i < 32; i++ )
{
tree.insert( i );
-
+
if ( isFirst )
{
isFirst = false;
@@ -619,20 +619,19 @@ public class ArrayTreeTest
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() );
@@ -640,15 +639,15 @@ public class ArrayTreeTest
assertEquals( THIRTY_TWO, tree.getLast() );
}
-
+
//-----------------------------------------------------------------------
// Test remove( K value )
//-----------------------------------------------------------------------
@Test
public void testRemoveEmptyTree()
{
- ArrayTree<Integer> tree = createTree();
- assertNull( tree.remove( null ) );
+ ArrayTree<Integer> tree = createTree();
+ assertNull( tree.remove( null ) );
assertEquals( 0, tree.size() );
@@ -657,7 +656,7 @@ public class ArrayTreeTest
assertEquals( 0, tree.size() );
}
-
+
@Test
public void testRemoveFromOnElementTree()
{
@@ -665,7 +664,7 @@ public class ArrayTreeTest
// Initialize the array
assertNull( tree.insert( 5 ) );
assertEquals( 1, tree.size() );
-
+
Integer existing = tree.remove( FIVE );
assertEquals( FIVE, existing );
assertEquals( 0, tree.size() );
@@ -674,7 +673,7 @@ public class ArrayTreeTest
assertEquals( "[]", tree.toString() );
}
-
+
@Test
public void testRemovefromOnElementTreeNotExistingElement()
{
@@ -682,7 +681,7 @@ public class ArrayTreeTest
// Initialize the array
assertNull( tree.insert( 5 ) );
assertEquals( 1, tree.size() );
-
+
assertNull( tree.remove( TEN ) );
assertEquals( 1, tree.size() );
assertEquals( FIVE, tree.getFirst() );
@@ -697,12 +696,12 @@ public class ArrayTreeTest
ArrayTree<Integer> tree = createTree();
StringBuilder sb = new StringBuilder();
boolean isFirst = true;
-
+
// Initialize the array
for ( int i = 0; i < 32; i++ )
{
tree.insert( i );
-
+
if ( isFirst )
{
isFirst = false;
@@ -714,25 +713,24 @@ public class ArrayTreeTest
sb.append( i );
}
-
-
+
assertEquals( 32, tree.size() );
assertEquals( sb.toString(), tree.toString() );
-
+
int size = 32;
- for ( int i = 0; i < 32; i++)
+ for ( int i = 0; i < 32; i++ )
{
- assertEquals( Integer.valueOf( i ), tree.remove( 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() );
@@ -745,12 +743,12 @@ public class ArrayTreeTest
ArrayTree<Integer> tree = createTree();
StringBuilder sb = new StringBuilder();
boolean isFirst = true;
-
+
// Initialize the array
for ( int i = 0; i < 32; i++ )
{
tree.insert( i );
-
+
if ( isFirst )
{
isFirst = false;
@@ -762,25 +760,24 @@ public class ArrayTreeTest
sb.append( i );
}
-
-
+
assertEquals( 32, tree.size() );
assertEquals( sb.toString(), tree.toString() );
-
+
int size = 32;
- for ( int i = 0; i < 32; i++)
+ for ( int i = 0; i < 32; i++ )
{
- assertEquals( Integer.valueOf( i ), tree.remove( 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() );
@@ -795,13 +792,13 @@ public class ArrayTreeTest
{
ArrayTree<Integer> tree = createTree();
assertTrue( tree.isEmpty() );
-
+
tree.insert( ONE );
-
+
assertFalse( tree.isEmpty() );
-
+
tree.remove( ONE );
-
+
assertTrue( tree.isEmpty() );
}
@@ -814,13 +811,13 @@ public class ArrayTreeTest
{
ArrayTree<Integer> tree = createTree();
assertEquals( 0, tree.size() );
-
+
tree.insert( ONE );
-
+
assertEquals( 1, tree.size() );
-
+
tree.remove( ONE );
-
+
assertEquals( 0, tree.size() );
}
@@ -853,7 +850,7 @@ public class ArrayTreeTest
tree.insert( FOUR );
tree.insert( SIX );
tree.insert( EIGHT );
-
+
assertEquals( ZERO, tree.find( 0 ) );
assertEquals( TWO, tree.find( 2 ) );
assertEquals( FOUR, tree.find( 4 ) );
@@ -871,7 +868,7 @@ public class ArrayTreeTest
tree.insert( FOUR );
tree.insert( SIX );
tree.insert( EIGHT );
-
+
assertNull( tree.find( -1 ) );
assertNull( tree.find( 1 ) );
assertNull( tree.find( 3 ) );
@@ -898,16 +895,16 @@ public class ArrayTreeTest
ArrayTree<Integer> tree = createTree();
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() );
}
@@ -930,21 +927,21 @@ public class ArrayTreeTest
ArrayTree<Integer> tree = createTree();
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()
//-----------------------------------------------------------------------
@@ -963,13 +960,13 @@ public class ArrayTreeTest
assertNull( tree.findGreater( null ) );
}
-
+
@Test
public void testFindGreaterFromOneElementTree()
{
ArrayTree<Integer> tree = createTree();
tree.insert( TWO );
-
+
assertNull( tree.findGreater( null ) );
assertEquals( TWO, tree.findGreater( ONE ) );
assertNull( tree.findGreater( TWO ) );
@@ -983,7 +980,7 @@ public class ArrayTreeTest
ArrayTree<Integer> tree = createTree();
tree.insert( TWO );
tree.insert( FOUR );
-
+
assertNull( tree.findGreater( null ) );
assertEquals( TWO, tree.findGreater( ONE ) );
assertEquals( FOUR, tree.findGreater( TWO ) );
@@ -991,8 +988,8 @@ public class ArrayTreeTest
assertNull( tree.findGreater( FOUR ) );
assertNull( tree.findGreater( FIVE ) );
}
-
-
+
+
@Test
public void testFindGreater()
{
@@ -1003,7 +1000,7 @@ public class ArrayTreeTest
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 ) );
@@ -1012,8 +1009,8 @@ public class ArrayTreeTest
assertEquals( EIGHT, tree.findGreater( FIVE ) );
assertNull( tree.findGreater( TEN ) );
}
-
-
+
+
//-----------------------------------------------------------------------
// Test findGreaterOrEqual()
//-----------------------------------------------------------------------
@@ -1031,16 +1028,14 @@ public class ArrayTreeTest
ArrayTree<Integer> tree = createTree();
assertNull( tree.findGreaterOrEqual( null ) );
}
-
-
-
+
@Test
public void testFindGreaterOrEqualFromOneElementTree()
{
ArrayTree<Integer> tree = createTree();
tree.insert( TWO );
-
+
assertNull( tree.findGreaterOrEqual( null ) );
assertEquals( TWO, tree.findGreaterOrEqual( ONE ) );
assertEquals( TWO, tree.findGreaterOrEqual( TWO ) );
@@ -1054,7 +1049,7 @@ public class ArrayTreeTest
ArrayTree<Integer> tree = createTree();
tree.insert( TWO );
tree.insert( FOUR );
-
+
assertNull( tree.findGreaterOrEqual( null ) );
assertEquals( TWO, tree.findGreaterOrEqual( ONE ) );
assertEquals( TWO, tree.findGreaterOrEqual( TWO ) );
@@ -1062,8 +1057,8 @@ public class ArrayTreeTest
assertEquals( FOUR, tree.findGreaterOrEqual( FOUR ) );
assertNull( tree.findGreaterOrEqual( FIVE ) );
}
-
-
+
+
@Test
public void testFindGreaterOrEqual()
{
@@ -1085,8 +1080,8 @@ public class ArrayTreeTest
assertEquals( TEN, tree.findGreaterOrEqual( TEN ) );
assertNull( tree.findGreaterOrEqual( ELEVEN ) );
}
-
-
+
+
//-----------------------------------------------------------------------
// Test findLess()
//-----------------------------------------------------------------------
@@ -1111,7 +1106,7 @@ public class ArrayTreeTest
{
ArrayTree<Integer> tree = createTree();
tree.insert( TWO );
-
+
assertNull( tree.findLess( null ) );
assertNull( tree.findLess( ONE ) );
assertNull( tree.findLess( TWO ) );
@@ -1125,7 +1120,7 @@ public class ArrayTreeTest
ArrayTree<Integer> tree = createTree();
tree.insert( TWO );
tree.insert( FOUR );
-
+
assertNull( tree.findLess( null ) );
assertNull( tree.findLess( ONE ) );
assertNull( tree.findLess( TWO ) );
@@ -1133,8 +1128,8 @@ public class ArrayTreeTest
assertEquals( TWO, tree.findLess( FOUR ) );
assertEquals( FOUR, tree.findLess( FIVE ) );
}
-
-
+
+
@Test
public void testFindLess()
{
@@ -1145,7 +1140,7 @@ public class ArrayTreeTest
tree.insert( SIX );
tree.insert( EIGHT );
tree.insert( TEN );
-
+
assertNull( tree.findLess( ZERO ) );
assertNotSame( ONE, tree.findLess( ONE ) );
assertEquals( ZERO, tree.findLess( ONE ) );
@@ -1155,8 +1150,8 @@ public class ArrayTreeTest
assertEquals( EIGHT, tree.findLess( TEN ) );
assertEquals( TEN, tree.findLess( SEVENTY ) );
}
-
-
+
+
//-----------------------------------------------------------------------
// Test findLessOrEqual()
//-----------------------------------------------------------------------
@@ -1181,7 +1176,7 @@ public class ArrayTreeTest
{
ArrayTree<Integer> tree = createTree();
tree.insert( TWO );
-
+
assertNull( tree.findLessOrEqual( null ) );
assertNull( tree.findLessOrEqual( ONE ) );
assertEquals( TWO, tree.findLessOrEqual( TWO ) );
@@ -1195,7 +1190,7 @@ public class ArrayTreeTest
ArrayTree<Integer> tree = createTree();
tree.insert( TWO );
tree.insert( FOUR );
-
+
assertNull( tree.findLessOrEqual( null ) );
assertNull( tree.findLessOrEqual( ONE ) );
assertEquals( TWO, tree.findLessOrEqual( TWO ) );
@@ -1203,8 +1198,8 @@ public class ArrayTreeTest
assertEquals( FOUR, tree.findLessOrEqual( FOUR ) );
assertEquals( FOUR, tree.findLessOrEqual( FIVE ) );
}
-
-
+
+
@Test
public void testFindLessOrEqual()
{
@@ -1228,7 +1223,7 @@ public class ArrayTreeTest
assertEquals( TEN, tree.findLessOrEqual( ELEVEN ) );
}
-
+
//-----------------------------------------------------------------------
// Test get( int position )
//-----------------------------------------------------------------------
@@ -1273,7 +1268,7 @@ public class ArrayTreeTest
}
}
-
+
//-----------------------------------------------------------------------
// Test getAfterPosition( K key )
//-----------------------------------------------------------------------
@@ -1284,27 +1279,27 @@ public class ArrayTreeTest
assertEquals( -1, tree.getAfterPosition( ZERO ) );
}
-
+
@Test
public void testGetAfterPositionOneElementTree()
{
ArrayTree<Integer> tree = createTree();
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()
{
ArrayTree<Integer> tree = createTree();
tree.insert( TWO );
tree.insert( FOUR );
-
+
assertEquals( -1, tree.getAfterPosition( null ) );
assertEquals( 0, tree.getAfterPosition( ZERO ) );
assertEquals( 1, tree.getAfterPosition( TWO ) );
@@ -1312,7 +1307,7 @@ public class ArrayTreeTest
assertEquals( -1, tree.getAfterPosition( FOUR ) );
}
-
+
@Test
public void testGetAfterPositionNElementsTree()
{
@@ -1321,7 +1316,7 @@ public class ArrayTreeTest
tree.insert( FOUR );
tree.insert( SIX );
tree.insert( EIGHT );
-
+
assertEquals( -1, tree.getAfterPosition( null ) );
assertEquals( 0, tree.getAfterPosition( ZERO ) );
assertEquals( 1, tree.getAfterPosition( TWO ) );
@@ -1333,7 +1328,7 @@ public class ArrayTreeTest
assertEquals( -1, tree.getAfterPosition( EIGHT ) );
}
-
+
//-----------------------------------------------------------------------
// Test getBeforePosition( K key )
//-----------------------------------------------------------------------
@@ -1344,27 +1339,27 @@ public class ArrayTreeTest
assertEquals( -1, tree.getBeforePosition( ZERO ) );
}
-
+
@Test
public void testGetBeforePositionOneElementTree()
{
ArrayTree<Integer> tree = createTree();
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()
{
ArrayTree<Integer> tree = createTree();
tree.insert( TWO );
tree.insert( FOUR );
-
+
assertEquals( -1, tree.getBeforePosition( null ) );
assertEquals( -1, tree.getBeforePosition( ZERO ) );
assertEquals( -1, tree.getBeforePosition( TWO ) );
@@ -1373,7 +1368,7 @@ public class ArrayTreeTest
assertEquals( 1, tree.getBeforePosition( FIVE ) );
}
-
+
@Test
public void testGetBeforePositionNElementsTree()
{
@@ -1382,7 +1377,7 @@ public class ArrayTreeTest
tree.insert( FOUR );
tree.insert( SIX );
tree.insert( EIGHT );
-
+
assertEquals( -1, tree.getBeforePosition( null ) );
assertEquals( -1, tree.getBeforePosition( ZERO ) );
assertEquals( -1, tree.getBeforePosition( TWO ) );
Modified: directory/apacheds/trunk/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeCursorTest.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeCursorTest.java?rev=1235258&r1=1235257&r2=1235258&view=diff
==============================================================================
--- directory/apacheds/trunk/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeCursorTest.java (original)
+++ directory/apacheds/trunk/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeCursorTest.java Tue Jan 24 14:10:56 2012
@@ -50,10 +50,10 @@ public class AvlTreeCursorTest
{
AvlTree<Integer> tree = new AvlTreeImpl<Integer>( new IntegerComparator() );
AvlTreeCursor<Integer> cursor = new AvlTreeCursor<Integer>( tree );
-
+
assertFalse( cursor.isClosed() );
assertFalse( cursor.available() );
-
+
try
{
cursor.get();
@@ -63,46 +63,46 @@ public class AvlTreeCursorTest
{
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
{
AvlTree<Integer> tree = new AvlTreeImpl<Integer>( new IntegerComparator() );
tree.insert( 7 );
AvlTreeCursor<Integer> cursor = new AvlTreeCursor<Integer>( tree );
-
+
assertFalse( cursor.isClosed() );
assertFalse( cursor.available() );
-
+
try
{
cursor.get();
@@ -112,27 +112,27 @@ public class AvlTreeCursorTest
{
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() );
@@ -186,8 +186,8 @@ public class AvlTreeCursorTest
assertTrue( cursor.available() );
assertEquals( 7, ( int ) cursor.get() );
}
-
-
+
+
@Test
public void testManyEntriesCursor() throws Exception
{
@@ -197,11 +197,11 @@ public class AvlTreeCursorTest
tree.insert( 10 );
tree.insert( 11 );
AvlTreeCursor<Integer> cursor = new AvlTreeCursor<Integer>( tree );
-
+
assertFalse( cursor.isClosed() );
assertFalse( cursor.available() );
assertEquals( 4, tree.getSize() );
-
+
try
{
cursor.get();
@@ -211,7 +211,7 @@ public class AvlTreeCursorTest
{
assertNotNull( e );
}
-
+
cursor.beforeFirst();
assertFalse( cursor.available() );
assertTrue( cursor.next() );
@@ -228,8 +228,7 @@ public class AvlTreeCursorTest
assertEquals( 11, ( int ) cursor.get() );
assertFalse( cursor.next() );
assertFalse( cursor.available() );
-
-
+
cursor.afterLast();
assertFalse( cursor.available() );
assertTrue( cursor.previous() );
@@ -246,16 +245,16 @@ public class AvlTreeCursorTest
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() );
@@ -385,8 +384,7 @@ public class AvlTreeCursorTest
assertFalse( cursor.previous() );
assertFalse( cursor.available() );
}
-
-
+
class IntegerComparator implements Comparator<Integer>
{
public int compare( Integer o1, Integer o2 )
Modified: directory/apacheds/trunk/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMapNoDupsCursorTest.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMapNoDupsCursorTest.java?rev=1235258&r1=1235257&r2=1235258&view=diff
==============================================================================
--- directory/apacheds/trunk/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMapNoDupsCursorTest.java (original)
+++ directory/apacheds/trunk/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMapNoDupsCursorTest.java Tue Jan 24 14:10:56 2012
@@ -162,7 +162,7 @@ public class AvlTreeMapNoDupsCursorTest
cursor.before( new Tuple<Integer, SingletonOrOrderedSet<Integer>>( 3, null ) );
assertFalse( cursor.previous() );
assertFalse( cursor.available() );
-
+
cursor.after( new Tuple<Integer, SingletonOrOrderedSet<Integer>>( 3, null ) );
assertFalse( cursor.available() );
assertTrue( cursor.next() );
@@ -180,27 +180,27 @@ public class AvlTreeMapNoDupsCursorTest
assertTrue( cursor.available() );
assertEquals( 7, ( int ) cursor.get().getKey() );
assertEquals( 7, ( int ) cursor.get().getValue().getSingleton() );
-
+
cursor.before( new Tuple<Integer, SingletonOrOrderedSet<Integer>>( 7, null ) );
assertFalse( cursor.previous() );
assertFalse( cursor.available() );
-
+
cursor.after( new Tuple<Integer, SingletonOrOrderedSet<Integer>>( 7, null ) );
assertFalse( cursor.available() );
assertFalse( cursor.next() );
assertFalse( cursor.available() );
-
+
cursor.after( new Tuple<Integer, SingletonOrOrderedSet<Integer>>( 7, null ) );
assertTrue( cursor.previous() );
assertTrue( cursor.available() );
assertEquals( 7, ( int ) cursor.get().getKey() );
assertEquals( 7, ( int ) cursor.get().getValue().getSingleton() );
-
+
cursor.before( new Tuple<Integer, SingletonOrOrderedSet<Integer>>( 9, null ) );
assertFalse( cursor.available() );
assertFalse( cursor.next() );
assertFalse( cursor.available() );
-
+
cursor.before( new Tuple<Integer, SingletonOrOrderedSet<Integer>>( 9, null ) );
assertTrue( cursor.previous() );
assertTrue( cursor.available() );
@@ -247,7 +247,7 @@ public class AvlTreeMapNoDupsCursorTest
assertTrue( cursor.available() );
assertEquals( 10, ( int ) cursor.get().getKey() );
assertEquals( 10, ( int ) cursor.get().getValue().getSingleton() );
-
+
assertTrue( cursor.next() );
assertTrue( cursor.available() );
assertEquals( 11, ( int ) cursor.get().getKey() );
@@ -261,12 +261,12 @@ public class AvlTreeMapNoDupsCursorTest
assertTrue( cursor.available() );
assertEquals( 11, ( int ) cursor.get().getKey() );
assertEquals( 11, ( int ) cursor.get().getValue().getSingleton() );
-
+
assertTrue( cursor.previous() );
assertTrue( cursor.available() );
assertEquals( 10, ( int ) cursor.get().getKey() );
assertEquals( 10, ( int ) cursor.get().getValue().getSingleton() );
-
+
assertTrue( cursor.previous() );
assertTrue( cursor.available() );
assertEquals( 7, ( int ) cursor.get().getKey() );
@@ -313,123 +313,123 @@ public class AvlTreeMapNoDupsCursorTest
assertTrue( cursor.available() );
assertEquals( 3, ( int ) cursor.get().getKey() );
assertEquals( 3, ( int ) cursor.get().getValue().getSingleton() );
-
+
// position after first object
cursor.after( new Tuple<Integer, SingletonOrOrderedSet<Integer>>( 5, null ) );
assertTrue( cursor.next() );
assertTrue( cursor.available() );
assertEquals( 7, ( int ) cursor.get().getKey() );
assertEquals( 7, ( int ) cursor.get().getValue().getSingleton() );
-
+
cursor.after( new Tuple<Integer, SingletonOrOrderedSet<Integer>>( 5, null ) );
assertTrue( cursor.previous() );
assertTrue( cursor.available() );
assertEquals( 3, ( int ) cursor.get().getKey() );
assertEquals( 3, ( int ) cursor.get().getValue().getSingleton() );
-
+
// position before last object
cursor.after( new Tuple<Integer, SingletonOrOrderedSet<Integer>>( 10, null ) );
assertTrue( cursor.next() );
assertTrue( cursor.available() );
assertEquals( 11, ( int ) cursor.get().getKey() );
assertEquals( 11, ( int ) cursor.get().getValue().getSingleton() );
-
+
cursor.after( new Tuple<Integer, SingletonOrOrderedSet<Integer>>( 10, null ) );
assertTrue( cursor.previous() );
assertTrue( cursor.available() );
assertEquals( 10, ( int ) cursor.get().getKey() );
assertEquals( 10, ( int ) cursor.get().getValue().getSingleton() );
-
+
// position on last object
cursor.after( new Tuple<Integer, SingletonOrOrderedSet<Integer>>( 11, null ) );
assertFalse( cursor.next() );
assertFalse( cursor.available() );
-
+
cursor.after( new Tuple<Integer, SingletonOrOrderedSet<Integer>>( 11, null ) );
assertTrue( cursor.previous() );
assertTrue( cursor.available() );
assertEquals( 11, ( int ) cursor.get().getKey() );
assertEquals( 11, ( int ) cursor.get().getValue().getSingleton() );
-
+
// position after last object
cursor.after( new Tuple<Integer, SingletonOrOrderedSet<Integer>>( 20, null ) );
assertFalse( cursor.next() );
assertFalse( cursor.available() );
-
+
cursor.after( new Tuple<Integer, SingletonOrOrderedSet<Integer>>( 20, null ) );
assertTrue( cursor.previous() );
assertTrue( cursor.available() );
assertEquals( 11, ( int ) cursor.get().getKey() );
assertEquals( 11, ( int ) cursor.get().getValue().getSingleton() );
-
+
// position after last object
cursor.before( new Tuple<Integer, SingletonOrOrderedSet<Integer>>( 20, null ) );
assertFalse( cursor.next() );
assertFalse( cursor.available() );
-
+
cursor.before( new Tuple<Integer, SingletonOrOrderedSet<Integer>>( 20, null ) );
assertTrue( cursor.previous() );
assertTrue( cursor.available() );
assertEquals( 11, ( int ) cursor.get().getKey() );
assertEquals( 11, ( int ) cursor.get().getValue().getSingleton() );
-
+
// position on last object
cursor.before( new Tuple<Integer, SingletonOrOrderedSet<Integer>>( 11, null ) );
assertTrue( cursor.next() );
assertTrue( cursor.available() );
assertEquals( 11, ( int ) cursor.get().getKey() );
assertEquals( 11, ( int ) cursor.get().getValue().getSingleton() );
-
+
cursor.before( new Tuple<Integer, SingletonOrOrderedSet<Integer>>( 11, null ) );
assertTrue( cursor.previous() );
assertTrue( cursor.available() );
assertEquals( 10, ( int ) cursor.get().getKey() );
assertEquals( 10, ( int ) cursor.get().getValue().getSingleton() );
-
+
// position before last object
cursor.before( new Tuple<Integer, SingletonOrOrderedSet<Integer>>( 10, null ) );
assertTrue( cursor.next() );
assertTrue( cursor.available() );
assertEquals( 10, ( int ) cursor.get().getKey() );
assertEquals( 10, ( int ) cursor.get().getValue().getSingleton() );
-
+
cursor.before( new Tuple<Integer, SingletonOrOrderedSet<Integer>>( 10, null ) );
assertTrue( cursor.previous() );
assertTrue( cursor.available() );
assertEquals( 7, ( int ) cursor.get().getKey() );
assertEquals( 7, ( int ) cursor.get().getValue().getSingleton() );
-
+
// position after first object
cursor.before( new Tuple<Integer, SingletonOrOrderedSet<Integer>>( 5, null ) );
assertTrue( cursor.next() );
assertTrue( cursor.available() );
assertEquals( 7, ( int ) cursor.get().getKey() );
assertEquals( 7, ( int ) cursor.get().getValue().getSingleton() );
-
+
cursor.before( new Tuple<Integer, SingletonOrOrderedSet<Integer>>( 5, null ) );
assertTrue( cursor.previous() );
assertTrue( cursor.available() );
assertEquals( 3, ( int ) cursor.get().getKey() );
assertEquals( 3, ( int ) cursor.get().getValue().getSingleton() );
-
+
// position on first object
cursor.before( new Tuple<Integer, SingletonOrOrderedSet<Integer>>( 3, null ) );
assertTrue( cursor.next() );
assertTrue( cursor.available() );
assertEquals( 3, ( int ) cursor.get().getKey() );
assertEquals( 3, ( int ) cursor.get().getValue().getSingleton() );
-
+
cursor.before( new Tuple<Integer, SingletonOrOrderedSet<Integer>>( 3, null ) );
assertFalse( cursor.previous() );
assertFalse( cursor.available() );
-
+
// position before first object
cursor.before( new Tuple<Integer, SingletonOrOrderedSet<Integer>>( 2, null ) );
assertTrue( cursor.next() );
assertTrue( cursor.available() );
assertEquals( 3, ( int ) cursor.get().getKey() );
assertEquals( 3, ( int ) cursor.get().getValue().getSingleton() );
-
+
cursor.before( new Tuple<Integer, SingletonOrOrderedSet<Integer>>( 2, null ) );
assertFalse( cursor.previous() );
assertFalse( cursor.available() );
@@ -449,7 +449,7 @@ public class AvlTreeMapNoDupsCursorTest
cursor.beforeValue( 0, null );
}
-
+
@Test
public void testCursorWithDupValues() throws Exception
{
@@ -460,22 +460,22 @@ public class AvlTreeMapNoDupsCursorTest
cursor.next();
Tuple<Integer, SingletonOrOrderedSet<Integer>> t = cursor.get();
-
+
assertEquals( 3, t.getKey().intValue() );
-
+
assertEquals( AvlTreeImpl.class, t.getValue().getOrderedSet().getClass() );
-
+
AvlTree<Integer> dupsTree = t.getValue().getOrderedSet();
assertEquals( 3, dupsTree.getSize() );
-
+
AvlTreeCursor<Integer> valCursor = new AvlTreeCursor<Integer>( dupsTree );
-
+
assertTrue( valCursor.next() );
assertEquals( 3, valCursor.get().intValue() );
-
+
assertTrue( valCursor.next() );
assertEquals( 7, valCursor.get().intValue() );
-
+
assertTrue( valCursor.next() );
assertEquals( 10, valCursor.get().intValue() );
Modified: directory/apacheds/trunk/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMapTest.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMapTest.java?rev=1235258&r1=1235257&r2=1235258&view=diff
==============================================================================
--- directory/apacheds/trunk/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMapTest.java (original)
+++ directory/apacheds/trunk/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMapTest.java Tue Jan 24 14:10:56 2012
@@ -48,10 +48,9 @@ import org.slf4j.LoggerFactory;
public class AvlTreeMapTest
{
-
private static final Logger LOG = LoggerFactory.getLogger( AvlTreeTest.class );
- Comparator<Integer> comparator = new Comparator<Integer>()
+ Comparator<Integer> comparator = new Comparator<Integer>()
{
public int compare( Integer i1, Integer i2 )
@@ -61,7 +60,7 @@ public class AvlTreeMapTest
};
-
+
private AvlTreeMapImpl<Integer, Integer> createTree()
{
return new AvlTreeMapImpl<Integer, Integer>( comparator, comparator, true );
@@ -82,7 +81,7 @@ public class AvlTreeMapTest
if ( LOG.isDebugEnabled() )
{
-
+
}
}
@@ -97,7 +96,7 @@ public class AvlTreeMapTest
assertNotNull( tree.getLast() );
assertTrue( tree.getFirst().getKey().equals( 7 ) );
assertTrue( tree.getFirst().getValue().getSingleton().equals( 1 ) );
-
+
tree.insert( 10, 2 );
assertEquals( 2, tree.getSize() );
assertNotNull( tree.getFirst() );
@@ -122,14 +121,14 @@ public class AvlTreeMapTest
AvlTreeMap<Integer, Integer> tree = createTree();
// to override the value tree should disable duplicate keys
tree = new AvlTreeMapImpl<Integer, Integer>( comparator, comparator, false );
-
+
assertNull( tree.insert( 43, 891 ) );
assertEquals( 891, tree.find( 43 ).getValue().getSingleton().intValue() );
-
+
assertNotNull( tree.insert( 43, 16 ) );
assertEquals( 16, tree.find( 43 ).getValue().getSingleton().intValue() );
}
-
+
@Test
public void testInsert()
@@ -137,7 +136,7 @@ public class AvlTreeMapTest
AvlTreeMap<Integer, Integer> tree = createTree();
assertNull( tree.insert( 3, 1 ) );
assertFalse( tree.isEmpty() );
-
+
assertTrue( 1 == tree.insert( 3, 1 ) );
assertTrue( 1 == tree.getSize() );
@@ -176,23 +175,23 @@ public class AvlTreeMapTest
assertNull( tree.insert( 3, 3 ) );
assertFalse( tree.isEmpty() );
- if( LOG.isDebugEnabled() )
+ if ( LOG.isDebugEnabled() )
{
-
+
}
-
+
assertTrue( 1 == tree.insert( 3, 1 ) );// should be ignored
assertTrue( 1 == tree.getSize() );
-
+
LinkedAvlMapNode node = tree.find( 3 );
assertNotNull( node );
-
- assertTrue( node.value.getOrderedSet().getClass() == AvlTreeImpl.class );
-
+
+ assertTrue( node.value.getOrderedSet().getClass() == AvlTreeImpl.class );
+
AvlTree dupsTree = ( ( SingletonOrOrderedSet ) node.value ).getOrderedSet();
assertEquals( 3, dupsTree.getSize() );
}
-
+
@Test
public void testRemove()
@@ -201,18 +200,18 @@ public class AvlTreeMapTest
tree.insert( 3, 3 );
tree.insert( 2, 2 );
tree.insert( 1, 1 );
-
+
tree.remove( 2, 2 );
- assertEquals("1,3", getInorderForm( tree ));
-
+ assertEquals( "1,3", getInorderForm( tree ) );
+
tree.remove( 1, 1 );
- assertEquals("3", getInorderForm( tree ));
+ assertEquals( "3", getInorderForm( tree ) );
assertTrue( 3 == tree.getRoot().key );
-
+
assertNull( tree.remove( 777, 0 ) );// key not present
assertTrue( 3 == tree.remove( 3, 3 ) );
- assertTrue(tree.isEmpty());
-
+ assertTrue( tree.isEmpty() );
+
tree.insert( 37, 37 );
tree.insert( 39, 39 );
tree.insert( 27, 27 );
@@ -230,64 +229,64 @@ public class AvlTreeMapTest
tree.remove( 39, 39 );
assertEquals( "21,27,37,38", getInorderForm( tree ) );
-
+
assertTrue( 37 == tree.getRoot().key ); // check the root value
-
+
tree.remove( 38, 38 ); // a double right rotation has to happen after this
assertTrue( 27 == tree.getRoot().key ); // check the root value after double right rotation
assertEquals( "21,27,37", getInorderForm( tree ) );
-
- if( LOG.isDebugEnabled() )
+
+ if ( LOG.isDebugEnabled() )
{
-
+
}
}
-
+
@Test
public void testRemoveWithDuplicateKeys()
{
AvlTreeMap<Integer, Integer> tree = createTree();
tree.insert( 1, 1 );
-
+
// insert duplicates
tree.insert( 3, 3 );
tree.insert( 3, 2 );
tree.insert( 3, 1 );
-
+
tree.insert( 2, 3 );
-
+
tree.remove( 2, 3 );
- assertEquals("1,3", getInorderForm( tree ));
+ assertEquals( "1,3", getInorderForm( tree ) );
assertEquals( 2, tree.getSize() );
-
+
tree.remove( 3, 3 );
// removing a duplicate key,value shouldn't change the size
- assertEquals("1,3", getInorderForm( tree ));
+ assertEquals( "1,3", getInorderForm( tree ) );
assertEquals( 2, tree.getSize() );
-
+
tree.remove( 3, 3 );
- assertEquals("1,3", getInorderForm( tree ));
+ assertEquals( "1,3", getInorderForm( tree ) );
assertEquals( 2, tree.getSize() );
-
+
// add some more
tree.insert( 3, 3 );
tree.insert( 3, 4 );
assertEquals( 2, tree.getSize() );
-
+
tree.remove( 3, 3 );
- assertEquals("1,3", getInorderForm( tree ));
+ assertEquals( "1,3", getInorderForm( tree ) );
assertEquals( 2, tree.getSize() );
-
+
tree.remove( 3, 2 );
tree.remove( 3, 1 );
tree.remove( 3, 4 ); // is the last value in the dupsTree should remove the whole
// node with key 3
-
+
assertEquals( 1, tree.getSize() );
}
-
-
+
+
/**
* checks the root node value(s) when duplicates are allowed and
* only single node(size one) is present
@@ -299,43 +298,43 @@ public class AvlTreeMapTest
assertTrue( tree.isDupsAllowed() );
tree.insert( 3, 4 );
tree.insert( 3, 5 );
-
+
assertEquals( 1, tree.getSize() );
-
+
assertTrue( 4 == tree.remove( 3, 4 ) );
assertNotNull( tree.getRoot() ); // still root should be not null
assertEquals( 1, tree.getSize() );
-
+
assertTrue( 5 == tree.remove( 3, 5 ) );
assertNull( tree.getRoot() );
-
+
tree.insert( 1, 1 );
tree.insert( 1, 2 );
tree.insert( 1, 3 );
assertNotNull( tree.getRoot() );
assertEquals( 1, tree.getSize() );
-
+
tree.remove( 1 );
assertNull( tree.getRoot() );
}
-
-
+
+
@Test
public void testRemoveWithoutDupKeys()
{
AvlTreeMap<Integer, Integer> tree = createTree();
tree = new AvlTreeMapImpl<Integer, Integer>( comparator, comparator, false );
assertFalse( tree.isDupsAllowed() );
-
+
tree.insert( 3, 4 );
assertTrue( 4 == tree.insert( 3, 5 ) );
assertEquals( 1, tree.getSize() );
-
+
assertNotNull( tree.remove( 3, 5 ) );
assertNull( tree.getRoot() );
}
-
-
+
+
@Test
public void testRemoveWithKeyOnly()
{
@@ -344,27 +343,27 @@ public class AvlTreeMapTest
tree.insert( 3, 1 );
tree.insert( 3, 2 );
tree.insert( 4, 4 );
-
+
SingletonOrOrderedSet<Integer> set = tree.remove( 3 );
assertNotNull( set );
assertNull( tree.find( 3 ) );
-
+
AvlTree<Integer> valueTree = set.getOrderedSet();
assertNotNull( valueTree );
assertTrue( 2 == valueTree.getSize() );
assertNotNull( valueTree.find( 1 ) );
assertNotNull( valueTree.find( 2 ) );
-
+
tree = new AvlTreeMapImpl<Integer, Integer>( comparator, comparator, false );
tree.insert( 7, 4 );
-
+
set = tree.remove( 7 );
assertNotNull( set );
assertNull( tree.find( 7 ) );
assertTrue( 4 == set.getSingleton() );
}
-
+
@Test
public void testSingleRightRotation()
{
@@ -377,7 +376,7 @@ public class AvlTreeMapTest
assertEquals( "1,2,3", getInorderForm( tree ) );
}
-
+
@Test
public void testRemoveAll()
{
@@ -387,15 +386,15 @@ public class AvlTreeMapTest
assertFalse( tree.isEmpty() );
assertEquals( 2, tree.getSize() );
-
+
tree.removeAll();
-
+
assertTrue( tree.isEmpty() );
assertEquals( 0, tree.getSize() );
assertNull( tree.getFirst() );
assertNull( tree.getLast() );
assertNull( tree.getRoot() );
-
+
// re-insert
assertNull( tree.insert( 3, 1 ) );
tree.insert( 37, 2 );
@@ -403,42 +402,42 @@ public class AvlTreeMapTest
assertEquals( 2, tree.getSize() );
}
-
+
private String getInorderForm( AvlTreeMap<Integer, Integer> tree )
{
- StringBuilder sb = new StringBuilder();
- List<LinkedAvlMapNode<Integer,Integer>> path = new ArrayList<LinkedAvlMapNode<Integer,Integer>>();
-
- traverse( tree.getRoot(), path );
- int i;
- for( i=0; i < path.size() -1; i++ )
- {
- sb.append( path.get( i ).key )
- .append( ',' );
- }
-
- sb.append( path.get( i ).key );
-
- return sb.toString();
- }
-
-
- private void traverse( LinkedAvlMapNode<Integer,Integer> startNode, List<LinkedAvlMapNode<Integer,Integer>> path )
- {
- //1. pre-order
-
- if( startNode.left != null )
- {
- traverse( startNode.left, path );
- }
-
- path.add( startNode ); //2. in-order NOTE: change this line's position to change the type of traversal
-
- if( startNode.right != null )
- {
- traverse( startNode.right, path );
- }
- //3. post-order
+ StringBuilder sb = new StringBuilder();
+ List<LinkedAvlMapNode<Integer, Integer>> path = new ArrayList<LinkedAvlMapNode<Integer, Integer>>();
+
+ traverse( tree.getRoot(), path );
+ int i;
+ for ( i = 0; i < path.size() - 1; i++ )
+ {
+ sb.append( path.get( i ).key )
+ .append( ',' );
+ }
+
+ sb.append( path.get( i ).key );
+
+ return sb.toString();
+ }
+
+
+ private void traverse( LinkedAvlMapNode<Integer, Integer> startNode, List<LinkedAvlMapNode<Integer, Integer>> path )
+ {
+ //1. pre-order
+
+ if ( startNode.left != null )
+ {
+ traverse( startNode.left, path );
+ }
+
+ path.add( startNode ); //2. in-order NOTE: change this line's position to change the type of traversal
+
+ if ( startNode.right != null )
+ {
+ traverse( startNode.right, path );
+ }
+ //3. post-order
}
}
|