directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From elecha...@apache.org
Subject svn commit: r1235258 [7/8] - in /directory/apacheds/trunk: core-annotations/src/main/java/org/apache/directory/server/core/annotations/ core-annotations/src/main/java/org/apache/directory/server/core/factory/ core-annotations/src/test/java/org/apache/d...
Date Tue, 24 Jan 2012 14:11:01 GMT
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
     }
 
 }



Mime
View raw message