You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@directory.apache.org by el...@apache.org on 2012/01/24 15:11:01 UTC
svn commit: r1235258 [6/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...
Modified: directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/ArrayTree.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/ArrayTree.java?rev=1235258&r1=1235257&r2=1235258&view=diff
==============================================================================
--- directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/ArrayTree.java (original)
+++ directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/ArrayTree.java Tue Jan 24 14:10:56 2012
@@ -38,26 +38,27 @@ public class ArrayTree<K>
/** The array containing the data */
private K[] array;
-
+
/** The current number of elements in the array. May be lower than the array size */
private int size;
-
+
/** The extend size to use when increasing the array size */
private static final int INCREMENT = 16;
-
+
+
/**
* Creates a new instance of AVLTree.
*
* @param comparator the comparator to be used for comparing keys
*/
- public ArrayTree( Comparator<K> comparator)
+ public ArrayTree( Comparator<K> comparator )
{
this.comparator = comparator;
- array = (K[])new Object[INCREMENT];
+ array = ( K[] ) new Object[INCREMENT];
size = 0;
}
-
-
+
+
/**
* Creates a new instance of AVLTree.
*
@@ -66,23 +67,23 @@ public class ArrayTree<K>
public ArrayTree( Comparator<K> comparator, K[] array )
{
this.comparator = comparator;
-
+
if ( array != null )
{
size = array.length;
int arraySize = size;
-
+
if ( size % INCREMENT != 0 )
{
arraySize += INCREMENT - size % INCREMENT;
}
-
- this.array = (K[])new Object[arraySize];
+
+ this.array = ( K[] ) new Object[arraySize];
System.arraycopy( array, 0, this.array, 0, size );
}
}
-
-
+
+
/**
* @return the comparator associated with this tree
*/
@@ -90,8 +91,8 @@ public class ArrayTree<K>
{
return comparator;
}
-
-
+
+
/**
* Inserts a key. Null value insertion is not allowed.
*
@@ -106,21 +107,21 @@ public class ArrayTree<K>
// We don't allow null values in the tree
return null;
}
-
+
// Check if the key already exists, and if so, return the
// existing one
K existing = find( key );
-
+
if ( existing != null )
{
return existing;
}
-
+
if ( size == array.length )
{
// The array is full, let's extend it
- K[] newArray = (K[])new Object[size + INCREMENT];
-
+ K[] newArray = ( K[] ) new Object[size + INCREMENT];
+
System.arraycopy( array, 0, newArray, 0, size );
array = newArray;
}
@@ -131,11 +132,11 @@ public class ArrayTree<K>
// parts and copying the right part one slot on the right.
array[size++] = key;
Arrays.sort( array, 0, size, comparator );
-
+
return null;
}
-
-
+
+
/**q<
* Reduce the array size if neede
*/
@@ -144,14 +145,14 @@ public class ArrayTree<K>
// We will reduce the array size when the number of elements
// in it is leaving twice the number of INCREMENT empty slots.
// We then remove INCREMENT slots
- if ( ( array.length - size ) > (INCREMENT << 1) )
+ if ( ( array.length - size ) > ( INCREMENT << 1 ) )
{
- K[] newArray = (K[])new Object[array.length - INCREMENT];
+ K[] newArray = ( K[] ) new Object[array.length - INCREMENT];
System.arraycopy( array, 0, newArray, 0, array.length );
}
}
-
-
+
+
/**
* Removes a key present in the tree
*
@@ -162,7 +163,7 @@ public class ArrayTree<K>
{
// Search for the key position in the tree
int pos = getPosition( key );
-
+
if ( pos != -1 )
{
// Found...
@@ -171,12 +172,12 @@ public class ArrayTree<K>
// If the element is not the last one, we have to
// move the end of the array one step to the left
System.arraycopy( array, pos + 1, array, pos, size - pos - 1 );
-
+
reduceArray();
}
-
- size --;
-
+
+ size--;
+
return key;
}
else
@@ -184,8 +185,8 @@ public class ArrayTree<K>
return null;
}
}
-
-
+
+
/**
* Tests if the tree is empty.
*
@@ -193,10 +194,10 @@ public class ArrayTree<K>
*/
public boolean isEmpty()
{
- return size == 0;
+ return size == 0;
}
-
+
/**
* returns the number of nodes present in this tree.
*
@@ -206,37 +207,38 @@ public class ArrayTree<K>
{
return size;
}
-
-
+
+
/**
* @return a list of the stored keys in this tree
*/
public List<K> getKeys()
{
List<K> list = new ArrayList<K>( size );
-
+
for ( int i = 0; i < size; i++ )
{
list.add( array[i] );
}
-
+
return list;
}
+
/**
* Prints the contents of AVL tree in pretty format
*/
- public void printTree()
+ public void printTree()
{
- if( isEmpty() )
+ if ( isEmpty() )
{
System.out.println( "Tree is empty" );
return;
}
-
+
boolean isFirst = false;
-
- for ( K key:array )
+
+ for ( K key : array )
{
if ( isFirst )
{
@@ -246,12 +248,12 @@ public class ArrayTree<K>
{
System.out.print( ", " );
}
-
+
System.out.println( key );
}
}
-
-
+
+
/**
* Get the element at a given position
* @param position The position in the tree
@@ -264,11 +266,11 @@ public class ArrayTree<K>
{
throw new ArrayIndexOutOfBoundsException();
}
-
+
return array[position];
}
-
-
+
+
/**
* Get the first element in the tree. It sets the current position to this
* element.
@@ -285,8 +287,8 @@ public class ArrayTree<K>
return null;
}
}
-
-
+
+
/**
* Get the last element in the tree. It sets the current position to this
* element.
@@ -304,6 +306,7 @@ public class ArrayTree<K>
}
}
+
/**
* Finds a key higher than the given key. Sets the current position to this
* element.
@@ -318,13 +321,13 @@ public class ArrayTree<K>
{
return null;
}
-
+
switch ( size )
{
- case 0 :
+ case 0:
return null;
-
- case 1 :
+
+ case 1:
if ( comparator.compare( array[0], key ) > 0 )
{
return array[0];
@@ -333,8 +336,8 @@ public class ArrayTree<K>
{
return null;
}
-
- case 2 :
+
+ case 2:
if ( comparator.compare( array[0], key ) > 0 )
{
return array[0];
@@ -347,17 +350,17 @@ public class ArrayTree<K>
{
return null;
}
-
- default :
+
+ default:
// Split the array in two parts, the left part an the right part
int current = size >> 1;
int start = 0;
int end = size - 1;
-
+
while ( end - start + 1 > 2 )
{
- int res = comparator.compare( array[current], key ) ;
-
+ int res = comparator.compare( array[current], key );
+
if ( res == 0 )
{
// Current can't be equal to zero at this point
@@ -366,20 +369,20 @@ public class ArrayTree<K>
else if ( res < 0 )
{
start = current;
- current = (current + end + 1) >> 1;
+ current = ( current + end + 1 ) >> 1;
}
else
{
end = current;
- current = (current + start + 1) >> 1 ;
+ current = ( current + start + 1 ) >> 1;
}
}
-
+
switch ( end - start + 1 )
{
- case 1 :
+ case 1:
int res = comparator.compare( array[start], key );
-
+
if ( res <= 0 )
{
if ( start == size )
@@ -393,31 +396,31 @@ public class ArrayTree<K>
}
return array[start];
-
- case 2 :
+
+ case 2:
res = comparator.compare( array[start], key );
-
+
if ( res <= 0 )
{
res = comparator.compare( array[start + 1], key );
-
+
if ( res <= 0 )
{
- if ( start == size - 2)
+ if ( start == size - 2 )
{
return null;
}
-
+
return array[start + 2];
}
-
+
return array[start + 1];
}
return array[start];
}
}
-
+
return null;
}
@@ -435,13 +438,13 @@ public class ArrayTree<K>
{
return null;
}
-
+
switch ( size )
{
- case 0 :
+ case 0:
return null;
-
- case 1 :
+
+ case 1:
if ( comparator.compare( array[0], key ) >= 0 )
{
return array[0];
@@ -450,8 +453,8 @@ public class ArrayTree<K>
{
return null;
}
-
- case 2 :
+
+ case 2:
if ( comparator.compare( array[0], key ) >= 0 )
{
return array[0];
@@ -464,17 +467,17 @@ public class ArrayTree<K>
{
return null;
}
-
- default :
+
+ default:
// Split the array in two parts, the left part an the right part
int current = size >> 1;
int start = 0;
int end = size - 1;
-
+
while ( end - start + 1 > 2 )
{
- int res = comparator.compare( array[current], key ) ;
-
+ int res = comparator.compare( array[current], key );
+
if ( res == 0 )
{
return array[current];
@@ -482,21 +485,21 @@ public class ArrayTree<K>
else if ( res < 0 )
{
start = current;
- current = (current + end + 1) >> 1;
+ current = ( current + end + 1 ) >> 1;
}
else
{
end = current;
- current = (current + start + 1) >> 1 ;
+ current = ( current + start + 1 ) >> 1;
}
}
-
+
switch ( end - start + 1 )
{
- case 1 :
+ case 1:
int res = comparator.compare( array[start], key );
-
- if ( res >= 0)
+
+ if ( res >= 0 )
{
return array[start];
}
@@ -511,31 +514,31 @@ public class ArrayTree<K>
return array[start + 1];
}
}
-
- case 2 :
+
+ case 2:
res = comparator.compare( array[start], key );
-
+
if ( res < 0 )
{
res = comparator.compare( array[start + 1], key );
-
+
if ( res < 0 )
{
- if ( start == size - 2)
+ if ( start == size - 2 )
{
return null;
}
-
+
return array[start + 2];
}
-
+
return array[start + 1];
}
return array[start];
}
}
-
+
return null;
}
@@ -553,13 +556,13 @@ public class ArrayTree<K>
{
return null;
}
-
+
switch ( size )
{
- case 0 :
+ case 0:
return null;
-
- case 1 :
+
+ case 1:
if ( comparator.compare( array[0], key ) >= 0 )
{
return null;
@@ -568,8 +571,8 @@ public class ArrayTree<K>
{
return array[0];
}
-
- case 2 :
+
+ case 2:
if ( comparator.compare( array[0], key ) >= 0 )
{
return null;
@@ -582,17 +585,17 @@ public class ArrayTree<K>
{
return array[1];
}
-
- default :
+
+ default:
// Split the array in two parts, the left part an the right part
int current = size >> 1;
int start = 0;
int end = size - 1;
-
+
while ( end - start + 1 > 2 )
{
- int res = comparator.compare( array[current], key ) ;
-
+ int res = comparator.compare( array[current], key );
+
if ( res == 0 )
{
// Current can't be equal to zero at this point
@@ -601,18 +604,18 @@ public class ArrayTree<K>
else if ( res < 0 )
{
start = current;
- current = (current + end + 1) >> 1;
+ current = ( current + end + 1 ) >> 1;
}
else
{
end = current;
- current = (current + start + 1) >> 1 ;
+ current = ( current + start + 1 ) >> 1;
}
}
-
+
switch ( end - start + 1 )
{
- case 1 :
+ case 1:
// Three cases :
// o The value is equal to the current position, or below
// the current position :
@@ -622,8 +625,8 @@ public class ArrayTree<K>
// o The value is above the current position :
// - return the current position
int res = comparator.compare( array[start], key );
-
- if ( res >= 0)
+
+ if ( res >= 0 )
{
// start can be equal to 0. Check that
if ( start == 1 )
@@ -639,8 +642,8 @@ public class ArrayTree<K>
{
return array[start];
}
-
- case 2 :
+
+ case 2:
// Four cases :
// o the value is equal the current position, or below
// the first position :
@@ -651,7 +654,7 @@ public class ArrayTree<K>
// or equal the second position, return the first position
// o otherwise, return the second position
res = comparator.compare( array[start], key );
-
+
if ( res >= 0 )
{
if ( start == 0 )
@@ -669,11 +672,11 @@ public class ArrayTree<K>
}
else
{
- return array[start + 1];
+ return array[start + 1];
}
}
}
-
+
return null;
}
@@ -691,13 +694,13 @@ public class ArrayTree<K>
{
return null;
}
-
+
switch ( size )
{
- case 0 :
+ case 0:
return null;
-
- case 1 :
+
+ case 1:
if ( comparator.compare( array[0], key ) <= 0 )
{
return array[0];
@@ -706,10 +709,10 @@ public class ArrayTree<K>
{
return null;
}
-
- case 2 :
+
+ case 2:
int res = comparator.compare( array[0], key );
-
+
if ( res > 0 )
{
return null;
@@ -718,9 +721,9 @@ public class ArrayTree<K>
{
return array[0];
}
-
+
res = comparator.compare( array[1], key );
-
+
if ( res == 0 )
{
return array[1];
@@ -733,17 +736,17 @@ public class ArrayTree<K>
{
return array[1];
}
-
- default :
+
+ default:
// Split the array in two parts, the left part an the right part
int current = size >> 1;
int start = 0;
int end = size - 1;
-
+
while ( end - start + 1 > 2 )
{
- res = comparator.compare( array[current], key ) ;
-
+ res = comparator.compare( array[current], key );
+
if ( res == 0 )
{
return array[current];
@@ -751,18 +754,18 @@ public class ArrayTree<K>
else if ( res < 0 )
{
start = current;
- current = (current + end + 1) >> 1;
+ current = ( current + end + 1 ) >> 1;
}
else
{
end = current;
- current = (current + start + 1) >> 1 ;
+ current = ( current + start + 1 ) >> 1;
}
}
-
+
switch ( end - start + 1 )
{
- case 1 :
+ case 1:
// Three cases :
// o The value is equal to the current position, or below
// the current position :
@@ -772,8 +775,8 @@ public class ArrayTree<K>
// o The value is above the current position :
// - return the current position
res = comparator.compare( array[start], key );
-
- if ( res > 0)
+
+ if ( res > 0 )
{
// start can be equal to 0. Check that
if ( start == 1 )
@@ -789,8 +792,8 @@ public class ArrayTree<K>
{
return array[start];
}
-
- case 2 :
+
+ case 2:
// Four cases :
// o the value is equal the current position, or below
// the first position :
@@ -801,7 +804,7 @@ public class ArrayTree<K>
// or equal the second position, return the first position
// o otherwise, return the second position
res = comparator.compare( array[start], key );
-
+
if ( res > 0 )
{
if ( start == 0 )
@@ -813,24 +816,24 @@ public class ArrayTree<K>
return array[start - 1];
}
}
-
+
res = comparator.compare( array[start + 1], key );
-
+
if ( res > 0 )
{
return array[start];
}
else
{
- return array[start + 1];
+ return array[start + 1];
}
}
}
-
+
return null;
}
-
-
+
+
/**
* Find an element in the array.
*
@@ -843,13 +846,13 @@ public class ArrayTree<K>
{
return null;
}
-
+
switch ( size )
{
- case 0 :
+ case 0:
return null;
-
- case 1 :
+
+ case 1:
if ( comparator.compare( array[0], key ) == 0 )
{
return array[0];
@@ -858,8 +861,8 @@ public class ArrayTree<K>
{
return null;
}
-
- case 2 :
+
+ case 2:
if ( comparator.compare( array[0], key ) == 0 )
{
return array[0];
@@ -870,19 +873,19 @@ public class ArrayTree<K>
}
else
{
- return null;
+ return null;
}
-
- default :
+
+ default:
// Split the array in two parts, the left part an the right part
int current = size >> 1;
int start = 0;
int end = size - 1;
-
+
while ( end - start + 1 > 2 )
{
- int res = comparator.compare( array[current], key ) ;
-
+ int res = comparator.compare( array[current], key );
+
if ( res == 0 )
{
return array[current];
@@ -890,19 +893,19 @@ public class ArrayTree<K>
else if ( res < 0 )
{
start = current;
- current = (current + end + 1) >> 1;
+ current = ( current + end + 1 ) >> 1;
}
else
{
end = current;
- current = (current + start + 1) >> 1 ;
+ current = ( current + start + 1 ) >> 1;
}
}
-
+
switch ( end - start + 1 )
{
- case 1 :
- if ( comparator.compare( array[start], key ) == 0 )
+ case 1:
+ if ( comparator.compare( array[start], key ) == 0 )
{
return array[start];
}
@@ -910,8 +913,8 @@ public class ArrayTree<K>
{
return null;
}
-
- case 2 :
+
+ case 2:
if ( comparator.compare( array[start], key ) == 0 )
{
return array[start];
@@ -922,14 +925,14 @@ public class ArrayTree<K>
}
else
{
- return null;
+ return null;
}
}
}
-
+
return null;
}
-
+
/**
* Find the element position in the array.
@@ -943,13 +946,13 @@ public class ArrayTree<K>
{
return -1;
}
-
+
switch ( size )
{
- case 0 :
+ case 0:
return -1;
-
- case 1 :
+
+ case 1:
if ( comparator.compare( array[0], key ) == 0 )
{
return 0;
@@ -958,8 +961,8 @@ public class ArrayTree<K>
{
return -1;
}
-
- case 2 :
+
+ case 2:
if ( comparator.compare( array[0], key ) == 0 )
{
return 0;
@@ -970,19 +973,19 @@ public class ArrayTree<K>
}
else
{
- return -1;
+ return -1;
}
-
- default :
+
+ default:
// Split the array in two parts, the left part an the right part
int current = size >> 1;
int start = 0;
int end = size - 1;
-
+
while ( end - start + 1 > 2 )
{
- int res = comparator.compare( array[current], key ) ;
-
+ int res = comparator.compare( array[current], key );
+
if ( res == 0 )
{
return current;
@@ -990,19 +993,19 @@ public class ArrayTree<K>
else if ( res < 0 )
{
start = current;
- current = (current + end + 1) >> 1;
+ current = ( current + end + 1 ) >> 1;
}
else
{
end = current;
- current = (current + start + 1) >> 1 ;
+ current = ( current + start + 1 ) >> 1;
}
}
-
+
switch ( end - start + 1 )
{
- case 1 :
- if ( comparator.compare( array[start], key ) == 0 )
+ case 1:
+ if ( comparator.compare( array[start], key ) == 0 )
{
return start;
}
@@ -1010,8 +1013,8 @@ public class ArrayTree<K>
{
return -1;
}
-
- case 2 :
+
+ case 2:
if ( comparator.compare( array[start], key ) == 0 )
{
return start;
@@ -1022,15 +1025,15 @@ public class ArrayTree<K>
}
else
{
- return -1;
+ return -1;
}
}
}
-
+
return -1;
}
-
-
+
+
/**
* Find the element position in the array, or the position of the closest greater element in the array.
*
@@ -1043,13 +1046,13 @@ public class ArrayTree<K>
{
return -1;
}
-
+
switch ( size )
{
- case 0 :
+ case 0:
return -1;
-
- case 1 :
+
+ case 1:
if ( comparator.compare( array[0], key ) > 0 )
{
return 0;
@@ -1058,32 +1061,32 @@ public class ArrayTree<K>
{
return -1;
}
-
- case 2 :
+
+ case 2:
if ( comparator.compare( array[0], key ) > 0 )
{
return 0;
}
-
+
if ( comparator.compare( array[1], key ) > 0 )
{
return 1;
}
else
{
- return -1;
+ return -1;
}
-
- default :
+
+ default:
// Split the array in two parts, the left part an the right part
int current = size >> 1;
int start = 0;
int end = size - 1;
-
+
while ( end - start + 1 > 2 )
{
- int res = comparator.compare( array[current], key ) ;
-
+ int res = comparator.compare( array[current], key );
+
if ( res == 0 )
{
if ( current != size - 1 )
@@ -1098,18 +1101,18 @@ public class ArrayTree<K>
else if ( res < 0 )
{
start = current;
- current = (current + end + 1) >> 1;
+ current = ( current + end + 1 ) >> 1;
}
else
{
end = current;
- current = (current + start + 1) >> 1 ;
+ current = ( current + start + 1 ) >> 1;
}
}
-
+
switch ( end - start + 1 )
{
- case 1 :
+ case 1:
if ( comparator.compare( array[start], key ) > 0 )
{
return start;
@@ -1118,28 +1121,28 @@ public class ArrayTree<K>
{
return -1;
}
-
- case 2 :
+
+ case 2:
if ( comparator.compare( array[start], key ) > 0 )
{
return start;
}
-
+
if ( comparator.compare( array[end], key ) > 0 )
{
return end;
}
else
{
- return -1;
+ return -1;
}
}
}
-
+
return -1;
}
-
-
+
+
/**
* Find the element position in the array, or the position of the closest greater element in the array.
*
@@ -1152,13 +1155,13 @@ public class ArrayTree<K>
{
return -1;
}
-
+
switch ( size )
{
- case 0 :
+ case 0:
return -1;
-
- case 1 :
+
+ case 1:
if ( comparator.compare( array[0], key ) < 0 )
{
return 0;
@@ -1167,32 +1170,32 @@ public class ArrayTree<K>
{
return -1;
}
-
- case 2 :
+
+ case 2:
if ( comparator.compare( array[1], key ) < 0 )
{
return 1;
}
-
+
if ( comparator.compare( array[0], key ) < 0 )
{
return 0;
}
else
{
- return -1;
+ return -1;
}
-
- default :
+
+ default:
// Split the array in two parts, the left part an the right part
int current = size >> 1;
int start = 0;
int end = size - 1;
-
+
while ( end - start + 1 > 2 )
{
- int res = comparator.compare( array[current], key ) ;
-
+ int res = comparator.compare( array[current], key );
+
if ( res == 0 )
{
if ( current == 0 )
@@ -1207,19 +1210,19 @@ public class ArrayTree<K>
else if ( res < 0 )
{
start = current;
- current = (current + end + 1) >> 1;
+ current = ( current + end + 1 ) >> 1;
}
else
{
end = current;
- current = (current + start + 1) >> 1 ;
+ current = ( current + start + 1 ) >> 1;
}
}
-
+
switch ( end - start + 1 )
{
- case 1 :
- if ( comparator.compare( array[start], key ) < 0 )
+ case 1:
+ if ( comparator.compare( array[start], key ) < 0 )
{
return start;
}
@@ -1227,28 +1230,28 @@ public class ArrayTree<K>
{
return -1;
}
-
- case 2 :
+
+ case 2:
if ( comparator.compare( array[end], key ) < 0 )
{
return end;
}
-
+
if ( comparator.compare( array[start], key ) < 0 )
{
return start;
}
else
{
- return -1;
+ return -1;
}
}
}
-
+
return -1;
}
-
+
/**
* Tells if a key exist in the array.
*
@@ -1259,26 +1262,26 @@ public class ArrayTree<K>
{
return find( key ) != null;
}
-
-
+
+
/**
* {@inheritDoc}
*/
public String toString()
{
- if( isEmpty() )
+ if ( isEmpty() )
{
return "[]";
}
-
+
StringBuilder sb = new StringBuilder();
-
+
boolean isFirst = true;
-
- for ( int i = 0; i < size; i ++ )
+
+ for ( int i = 0; i < size; i++ )
{
K key = array[i];
-
+
if ( isFirst )
{
isFirst = false;
@@ -1287,10 +1290,10 @@ public class ArrayTree<K>
{
sb.append( ", " );
}
-
+
sb.append( key );
}
-
+
return sb.toString();
}
}
Modified: directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeImpl.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeImpl.java?rev=1235258&r1=1235257&r2=1235258&view=diff
==============================================================================
--- directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeImpl.java (original)
+++ directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeImpl.java Tue Jan 24 14:10:56 2012
@@ -40,24 +40,25 @@ public class AvlTreeImpl<K> implements A
/** node representing the start of the doubly linked list formed with the tree nodes */
private LinkedAvlNode<K> first;
-
+
/** node representing the end of the doubly linked list formed with the tree nodes */
private LinkedAvlNode<K> last;
/** size of the tree */
private int size;
+
/**
* Creates a new instance of AVLTree.
*
* @param comparator the comparator to be used for comparing keys
*/
- public AvlTreeImpl( Comparator<K> comparator)
+ public AvlTreeImpl( Comparator<K> comparator )
{
this.comparator = comparator;
}
-
-
+
+
/* (non-Javadoc)
* @see org.apache.directory.server.core.avltree.AvlTree#getComparator()
*/
@@ -65,8 +66,8 @@ public class AvlTreeImpl<K> implements A
{
return comparator;
}
-
-
+
+
/* (non-Javadoc)
* @see org.apache.directory.server.core.avltree.AvlTree#insert(K)
*/
@@ -75,35 +76,35 @@ public class AvlTreeImpl<K> implements A
LinkedAvlNode<K> node, temp;
LinkedAvlNode<K> parent = null;
int c;
-
+
if ( root == null )
{
- root = new LinkedAvlNode<K>( key );
- first = root;
- last = root;
- size++;
- return null;
+ root = new LinkedAvlNode<K>( key );
+ first = root;
+ last = root;
+ size++;
+ return null;
}
-
+
node = new LinkedAvlNode<K>( key );
-
+
temp = root;
-
+
List<LinkedAvlNode<K>> treePath = new ArrayList<LinkedAvlNode<K>>();
- while( temp != null )
+ while ( temp != null )
{
- treePath.add(0, temp ); // last node first, for the sake of balance factor computation
+ treePath.add( 0, temp ); // last node first, for the sake of balance factor computation
parent = temp;
-
+
c = comparator.compare( key, temp.getKey() );
-
- if( c == 0 )
+
+ if ( c == 0 )
{
return key; // key already exists
}
-
- if( c < 0 )
+
+ if ( c < 0 )
{
temp.isLeft = true;
temp = temp.getLeft();
@@ -114,8 +115,8 @@ public class AvlTreeImpl<K> implements A
temp = temp.getRight();
}
}
-
- if( ( c = comparator.compare( key, parent.getKey() ) ) < 0 )
+
+ if ( ( c = comparator.compare( key, parent.getKey() ) ) < 0 )
{
parent.setLeft( node );
}
@@ -123,68 +124,69 @@ public class AvlTreeImpl<K> implements A
{
parent.setRight( node );
}
-
+
insertInList( node, parent, c );
-
+
treePath.add( 0, node );
- balance(treePath);
-
+ balance( treePath );
+
size++;
return null;
}
-
-
- private void removeFromList(LinkedAvlNode<K> node)
+
+
+ private void removeFromList( LinkedAvlNode<K> node )
{
- if( node.next == null && node.previous == null ) // should happen in case of tree having single node
+ if ( node.next == null && node.previous == null ) // should happen in case of tree having single node
{
first = last = null;
}
- else if( node.next == null ) // last node
+ else if ( node.next == null ) // last node
{
node.previous.next = null;
last = node.previous;
}
- else if( node.previous == null ) // first node
+ else if ( node.previous == null ) // first node
{
node.next.previous = null;
first = node.next;
}
- else // somewhere in middle
+ else
+ // somewhere in middle
{
node.previous.next = node.next;
node.next.previous = node.previous;
}
-
+
}
-
-
- private void insertInList(LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode, int pos)
+
+
+ private void insertInList( LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode, int pos )
{
- if( pos < 0 )
+ if ( pos < 0 )
{
- if( last == null )
+ if ( last == null )
{
- last = parentNode;
+ last = parentNode;
}
-
- if( parentNode.previous == null )
+
+ if ( parentNode.previous == null )
{
first = node;
}
else
{
- parentNode.previous.next = node ;
+ parentNode.previous.next = node;
node.previous = parentNode.previous;
}
-
+
node.next = parentNode;
parentNode.previous = node;
}
- else if( pos > 0 )
+ else if ( pos > 0 )
{
- if( parentNode.next == null )
+ if ( parentNode.next == null )
{
last = node;
}
@@ -195,11 +197,11 @@ public class AvlTreeImpl<K> implements A
}
node.previous = parentNode;
parentNode.next = node;
- }
-
+ }
+
}
-
-
+
+
/* (non-Javadoc)
* @see org.apache.directory.server.core.avltree.AvlTree#remove(K)
*/
@@ -207,43 +209,43 @@ public class AvlTreeImpl<K> implements A
{
LinkedAvlNode<K> temp = null;
LinkedAvlNode<K> y = null;
-
+
List<LinkedAvlNode<K>> treePath = new ArrayList<LinkedAvlNode<K>>();
-
- treePath = find( key, root, treePath);
-
- if( treePath == null )
+
+ treePath = find( key, root, treePath );
+
+ if ( treePath == null )
{
return null;
}
-
+
temp = treePath.remove( 0 );
// remove from the doubly linked
- removeFromList(temp);
-
- if( temp.isLeaf() )
- {
- if( temp == root )
- {
- root = null;
- size--;
- return key;
+ removeFromList( temp );
+
+ if ( temp.isLeaf() )
+ {
+ if ( temp == root )
+ {
+ root = null;
+ size--;
+ return key;
}
-
- if( !treePath.isEmpty() )
+
+ if ( !treePath.isEmpty() )
{
detachNodes( temp, treePath.get( 0 ) );
}
}
else
{
- if( temp.left != null )
+ if ( temp.left != null )
{
List<LinkedAvlNode<K>> leftTreePath = findMax( temp.left );
y = leftTreePath.remove( 0 );
-
- if( leftTreePath.isEmpty() ) // y is the left child of root and y is a leaf
+
+ if ( leftTreePath.isEmpty() ) // y is the left child of root and y is a leaf
{
detachNodes( y, temp );
}
@@ -251,13 +253,13 @@ public class AvlTreeImpl<K> implements A
{
detachNodes( y, leftTreePath.remove( 0 ) );
}
-
+
leftTreePath.addAll( treePath );
treePath = leftTreePath;
-
+
y.right = temp.right; // assign the right here left will be assigned in replaceNode()
- if( temp == root )
+ if ( temp == root )
{
y.left = temp.left;
root = y;
@@ -267,12 +269,12 @@ public class AvlTreeImpl<K> implements A
replaceNode( temp, y, treePath.get( 0 ) );
}
}
- else if( temp.right != null )
+ else if ( temp.right != null )
{
List<LinkedAvlNode<K>> rightTreePath = findMin( temp.right );
y = rightTreePath.remove( 0 );
-
- if( rightTreePath.isEmpty() )
+
+ if ( rightTreePath.isEmpty() )
{
detachNodes( y, temp ); // y is the right child of root and y is a leaf
}
@@ -280,13 +282,13 @@ public class AvlTreeImpl<K> implements A
{
detachNodes( y, rightTreePath.remove( 0 ) );
}
-
+
rightTreePath.addAll( treePath );
treePath = rightTreePath;
-
+
y.right = temp.right; // assign the right here left will be assigned in replaceNode()
-
- if( temp == root )
+
+ if ( temp == root )
{
y.right = temp.right;
root = y;
@@ -297,15 +299,15 @@ public class AvlTreeImpl<K> implements A
}
}
}
-
- treePath.add( 0, y ); // y can be null but getBalance returns 0 so np
- balance( treePath );
-
- size--;
- return key;
+
+ treePath.add( 0, y ); // y can be null but getBalance returns 0 so np
+ balance( treePath );
+
+ size--;
+ return key;
}
-
-
+
+
/**
* Balances the tree by visiting the nodes present in the List of nodes present in the
* treePath parameter.<br><br>
@@ -320,38 +322,39 @@ public class AvlTreeImpl<K> implements A
private void balance( List<LinkedAvlNode<K>> treePath )
{
LinkedAvlNode<K> parentNode = null;
-
+
int size = treePath.size();
-
- for( LinkedAvlNode<K> node: treePath )
+
+ for ( LinkedAvlNode<K> node : treePath )
{
int balFactor = getBalance( node );
- if( node != root && treePath.indexOf( node ) < ( size - 1 ) )
+ if ( node != root && treePath.indexOf( node ) < ( size - 1 ) )
{
parentNode = treePath.get( treePath.indexOf( node ) + 1 );
}
- if( balFactor > 1 )
+ if ( balFactor > 1 )
{
- if( getBalance( node.right ) <= -1)
+ if ( getBalance( node.right ) <= -1 )
{
//------rotate double-left--------
rotateSingleRight( node.right, node );
rotateSingleLeft( node, parentNode );
}
- else // rotate single-left
+ else
+ // rotate single-left
{
- rotateSingleLeft( node, parentNode );
+ rotateSingleLeft( node, parentNode );
}
}
- else if( balFactor < -1 )
+ else if ( balFactor < -1 )
{
- if( getBalance( node.left ) >= 1)
+ if ( getBalance( node.left ) >= 1 )
{
- //------rotate double-right--------
- rotateSingleLeft( node.left, node );
- rotateSingleRight( node, parentNode );
+ //------rotate double-right--------
+ rotateSingleLeft( node.left, node );
+ rotateSingleRight( node, parentNode );
}
else
{
@@ -360,17 +363,17 @@ public class AvlTreeImpl<K> implements A
}
}
}
-
+
/* (non-Javadoc)
* @see org.apache.directory.server.core.avltree.AvlTree#isEmpty()
*/
public boolean isEmpty()
{
- return root == null;
+ return root == null;
}
-
+
/* (non-Javadoc)
* @see org.apache.directory.server.core.avltree.AvlTree#getSize()
*/
@@ -379,7 +382,8 @@ public class AvlTreeImpl<K> implements A
{
return size;
}
-
+
+
/**
* Set the size of the tree.
*
@@ -387,12 +391,12 @@ public class AvlTreeImpl<K> implements A
*
* @param size the size of the tree
*/
- /* no protection */ void setSize( int size )
+ /* no protection */void setSize( int size )
{
this.size = size;
}
-
-
+
+
/**
* Set the root of the tree.
*
@@ -400,12 +404,12 @@ public class AvlTreeImpl<K> implements A
*
* @param root the root of the tree
*/
- /* no protection */ void setRoot( LinkedAvlNode<K> root )
+ /* no protection */void setRoot( LinkedAvlNode<K> root )
{
this.root = root;
}
-
+
/**
* Set the first element of the tree
*
@@ -413,13 +417,13 @@ public class AvlTreeImpl<K> implements A
*
* @param first the first element to be added
*/
- /* no protection */ void setFirst( LinkedAvlNode<K> first )
+ /* no protection */void setFirst( LinkedAvlNode<K> first )
{
this.first = first;
size++;
}
-
+
/**
* Set the last element of the tree
*
@@ -427,7 +431,7 @@ public class AvlTreeImpl<K> implements A
*
* @param last the last element to be added
*/
- /* no protection */ void setLast( LinkedAvlNode<K> last )
+ /* no protection */void setLast( LinkedAvlNode<K> last )
{
this.last = last;
}
@@ -440,8 +444,8 @@ public class AvlTreeImpl<K> implements A
{
return root;
}
-
-
+
+
/* (non-Javadoc)
* @see org.apache.directory.server.core.avltree.AvlTree#getKeys()
*/
@@ -449,36 +453,37 @@ public class AvlTreeImpl<K> implements A
{
List<K> keys = new ArrayList<K>();
LinkedAvlNode<K> node = first;
-
- while( node != null )
+
+ while ( node != null )
{
keys.add( node.key );
node = node.next;
}
-
+
return keys;
}
+
/* (non-Javadoc)
* @see org.apache.directory.server.core.avltree.AvlTree#printTree()
*/
- public void printTree()
+ public void printTree()
{
- if( isEmpty() )
+ if ( isEmpty() )
{
System.out.println( "Tree is empty" );
return;
}
-
+
getRoot().setDepth( 0 );
System.out.println( getRoot() );
-
+
visit( getRoot().getRight(), getRoot() );
-
+
visit( getRoot().getLeft(), getRoot() );
}
-
+
/* (non-Javadoc)
* @see org.apache.directory.server.core.avltree.AvlTree#getFirst()
@@ -488,7 +493,7 @@ public class AvlTreeImpl<K> implements A
return first;
}
-
+
/* (non-Javadoc)
* @see org.apache.directory.server.core.avltree.AvlTree#getLast()
*/
@@ -497,66 +502,66 @@ public class AvlTreeImpl<K> implements A
return last;
}
-
+
/**
* Rotate the node left side once.
*
* @param node the LinkedAvlNode to be rotated
* @param parentNode parent LinkedAvlNode of node
*/
- private void rotateSingleLeft(LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode)
+ private void rotateSingleLeft( LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode )
{
LinkedAvlNode<K> temp;
//------rotate single-left--------
-
+
temp = node.right;
node.right = temp.left;
temp.left = node;
-
- if( node == root )
+
+ if ( node == root )
{
- root = temp;
+ root = temp;
}
- else if( parentNode != null )
+ else if ( parentNode != null )
{
- if( parentNode.left == node )
+ if ( parentNode.left == node )
{
parentNode.left = temp;
}
- else if( parentNode.right == node )
+ else if ( parentNode.right == node )
{
parentNode.right = temp;
}
}
}
-
-
+
+
/**
* Rotate the node right side once.
*
* @param node the LinkedAvlNode to be rotated
* @param parentNode parent LinkedAvlNode of node
*/
- private void rotateSingleRight(LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode)
+ private void rotateSingleRight( LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode )
{
LinkedAvlNode<K> temp;
//------rotate single-right--------
-
+
temp = node.left;
node.left = temp.right;
temp.right = node;
-
- if( node == root )
+
+ if ( node == root )
{
- root = temp;
+ root = temp;
}
- else if( parentNode != null )
+ else if ( parentNode != null )
{
- if( parentNode.left == node )
+ if ( parentNode.left == node )
{
parentNode.left = temp;
}
- else if( parentNode.right == node )
+ else if ( parentNode.right == node )
{
parentNode.right = temp;
}
@@ -565,13 +570,13 @@ public class AvlTreeImpl<K> implements A
when the 'parentNode' param is null then the node under rotation is a child of ROOT.
Most likely this condition executes when the root node is deleted and balancing is required.
*/
- else if( root != null && root.left == node )
+ else if ( root != null && root.left == node )
{
root.left = temp;
// no need to check for right node
}
}
-
+
/**
* Detach a LinkedAvlNode from its parent
@@ -579,15 +584,15 @@ public class AvlTreeImpl<K> implements A
* @param node the LinkedAvlNode to be detached
* @param parentNode the parent LinkedAvlNode of the node
*/
- private void detachNodes(LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode)
+ private void detachNodes( LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode )
{
- if( parentNode != null )
+ if ( parentNode != null )
{
- if( node == parentNode.left )
+ if ( node == parentNode.left )
{
parentNode.left = node.left;
}
- else if( node == parentNode.right )
+ else if ( node == parentNode.right )
{
parentNode.right = node.left;
}
@@ -603,24 +608,24 @@ public class AvlTreeImpl<K> implements A
* @param replaceNode the LinkedAvlNode to replace the deleteNode
* @param parentNode the parent LinkedAvlNode of deleteNode
*/
- private void replaceNode(LinkedAvlNode<K> deleteNode, LinkedAvlNode<K> replaceNode, LinkedAvlNode<K> parentNode)
+ private void replaceNode( LinkedAvlNode<K> deleteNode, LinkedAvlNode<K> replaceNode, LinkedAvlNode<K> parentNode )
{
- if( parentNode != null )
+ if ( parentNode != null )
{
replaceNode.left = deleteNode.left;
-
- if( deleteNode == parentNode.left )
+
+ if ( deleteNode == parentNode.left )
{
parentNode.left = replaceNode;
}
- else if( deleteNode == parentNode.right )
+ else if ( deleteNode == parentNode.right )
{
parentNode.right = replaceNode;
}
}
}
-
-
+
+
/**
*
* Find a LinkedAvlNode with the given key value in the tree starting from the startNode.
@@ -633,28 +638,28 @@ public class AvlTreeImpl<K> implements A
private List<LinkedAvlNode<K>> find( K key, LinkedAvlNode<K> startNode, List<LinkedAvlNode<K>> path )
{
int c;
-
- if( startNode == null )
+
+ if ( startNode == null )
{
return null;
}
-
+
path.add( 0, startNode );
c = comparator.compare( key, startNode.key );
-
- if( c == 0 )
+
+ if ( c == 0 )
{
return path;
}
- else if( c > 0 )
+ else if ( c > 0 )
{
return find( key, startNode.right, path );
}
- else if( c < 0 )
+ else if ( c < 0 )
{
return find( key, startNode.left, path );
}
-
+
return null;
}
@@ -664,13 +669,13 @@ public class AvlTreeImpl<K> implements A
*/
public LinkedAvlNode<K> findGreater( K key )
{
- LinkedAvlNode<K> result = fetchNonNullNode( key, root, root);
+ LinkedAvlNode<K> result = fetchNonNullNode( key, root, root );
- if( result == null )
+ if ( result == null )
{
return null;
}
- else if( comparator.compare( key, result.key ) < 0 )
+ else if ( comparator.compare( key, result.key ) < 0 )
{
return result;
}
@@ -684,13 +689,13 @@ public class AvlTreeImpl<K> implements A
*/
public LinkedAvlNode<K> findGreaterOrEqual( K key )
{
- LinkedAvlNode<K> result = fetchNonNullNode( key, root, root);
+ LinkedAvlNode<K> result = fetchNonNullNode( key, root, root );
- if( result == null )
+ if ( result == null )
{
return null;
}
- else if( comparator.compare( key, result.key ) <= 0 )
+ else if ( comparator.compare( key, result.key ) <= 0 )
{
return result;
}
@@ -704,13 +709,13 @@ public class AvlTreeImpl<K> implements A
*/
public LinkedAvlNode<K> findLess( K key )
{
- LinkedAvlNode<K> result = fetchNonNullNode( key, root, root);
+ LinkedAvlNode<K> result = fetchNonNullNode( key, root, root );
- if( result == null )
+ if ( result == null )
{
return null;
}
- else if( comparator.compare( key, result.key ) > 0 )
+ else if ( comparator.compare( key, result.key ) > 0 )
{
return result;
}
@@ -724,13 +729,13 @@ public class AvlTreeImpl<K> implements A
*/
public LinkedAvlNode<K> findLessOrEqual( K key )
{
- LinkedAvlNode<K> result = fetchNonNullNode( key, root, root);
+ LinkedAvlNode<K> result = fetchNonNullNode( key, root, root );
- if( result == null )
+ if ( result == null )
{
return null;
}
- else if( comparator.compare( key, result.key ) >= 0 )
+ else if ( comparator.compare( key, result.key ) >= 0 )
{
return result;
}
@@ -746,63 +751,64 @@ public class AvlTreeImpl<K> implements A
*/
private LinkedAvlNode<K> fetchNonNullNode( K key, LinkedAvlNode<K> startNode, LinkedAvlNode<K> parent )
{
-
- if( startNode == null )
+
+ if ( startNode == null )
{
return parent;
}
-
+
int c = comparator.compare( key, startNode.key );
-
+
parent = startNode;
- if( c > 0 )
+ if ( c > 0 )
{
return fetchNonNullNode( key, startNode.right, parent );
}
- else if( c < 0 )
+ else if ( c < 0 )
{
return fetchNonNullNode( key, startNode.left, parent );
}
-
+
return startNode;
}
-
+
+
/* (non-Javadoc)
* @see org.apache.directory.server.core.avltree.AvlTree#find(K)
*/
public LinkedAvlNode<K> find( K key )
{
- return find( key, root);
+ return find( key, root );
}
-
- private LinkedAvlNode<K> find( K key, LinkedAvlNode<K> startNode)
+
+ private LinkedAvlNode<K> find( K key, LinkedAvlNode<K> startNode )
{
int c;
-
- if( startNode == null )
+
+ if ( startNode == null )
{
return null;
}
-
+
c = comparator.compare( key, startNode.key );
-
- if( c > 0 )
+
+ if ( c > 0 )
{
startNode.isLeft = false;
return find( key, startNode.right );
}
- else if( c < 0 )
+ else if ( c < 0 )
{
startNode.isLeft = true;
return find( key, startNode.left );
}
-
+
return startNode;
}
-
-
+
+
/**
* Find the LinkedAvlNode having the max key value in the tree starting from the startNode.
*
@@ -814,31 +820,31 @@ public class AvlTreeImpl<K> implements A
LinkedAvlNode<K> x = startNode;
LinkedAvlNode<K> y = null;
List<LinkedAvlNode<K>> path;
-
- if( x == null )
+
+ if ( x == null )
{
return null;
}
-
- while( x.right != null )
+
+ while ( x.right != null )
{
x.isLeft = false;
y = x;
x = x.right;
}
-
- path = new ArrayList<LinkedAvlNode<K>>(2);
+
+ path = new ArrayList<LinkedAvlNode<K>>( 2 );
path.add( x );
-
+
if ( y != null )
{
- path.add( y );
+ path.add( y );
}
-
+
return path;
}
-
+
/**
* Find the LinkedAvlNode having the min key value in the tree starting from the startNode.
*
@@ -850,31 +856,31 @@ public class AvlTreeImpl<K> implements A
LinkedAvlNode<K> x = startNode;
LinkedAvlNode<K> y = null;
List<LinkedAvlNode<K>> path;
-
- if( x == null )
+
+ if ( x == null )
{
return null;
}
-
- while( x.left != null )
+
+ while ( x.left != null )
{
x.isLeft = true;
y = x;
x = x.left;
}
-
- path = new ArrayList<LinkedAvlNode<K>>(2);
+
+ path = new ArrayList<LinkedAvlNode<K>>( 2 );
path.add( x );
-
+
if ( y != null )
{
- path.add( y );
+ path.add( y );
}
-
+
return path;
}
-
-
+
+
/**
* Get balance-factor of the given LinkedAvlNode.
*
@@ -883,50 +889,50 @@ public class AvlTreeImpl<K> implements A
*/
private int getBalance( LinkedAvlNode<K> node )
{
- if( node == null)
+ if ( node == null )
{
return 0;
}
-
+
return node.getBalance();
}
-
-
- private void visit( LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode )
+
+
+ private void visit( LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode )
{
- if( node == null )
+ if ( node == null )
{
return;
}
-
- if( !node.isLeaf() )
+
+ if ( !node.isLeaf() )
{
node.setDepth( parentNode.getDepth() + 1 );
}
-
- for( int i=0; i < parentNode.getDepth(); i++ )
+
+ for ( int i = 0; i < parentNode.getDepth(); i++ )
{
System.out.print( "| " );
}
String type = "";
- if( node == parentNode.left )
+ if ( node == parentNode.left )
{
type = "L";
}
- else if( node == parentNode.right )
+ else if ( node == parentNode.right )
{
type = "R";
}
-
+
System.out.println( "|--" + node + type );
-
+
if ( node.getRight() != null )
{
visit( node.getRight(), node );
}
-
- if( node.getLeft() != null )
+
+ if ( node.getLeft() != null )
{
visit( node.getLeft(), node );
}
Modified: directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMap.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMap.java?rev=1235258&r1=1235257&r2=1235258&view=diff
==============================================================================
--- directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMap.java (original)
+++ directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMap.java Tue Jan 24 14:10:56 2012
@@ -23,6 +23,7 @@ package org.apache.directory.server.core
import java.util.Comparator;
import java.util.List;
+
/**
* An interface to the AVL tree based map. The implementations
* should hold a value(s) along with a key
@@ -78,7 +79,7 @@ public interface AvlTreeMap<K, V>
*/
SingletonOrOrderedSet<V> remove( K key );
-
+
/**
* Tests if the tree is logically empty.
*
Modified: directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMapImpl.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMapImpl.java?rev=1235258&r1=1235257&r2=1235258&view=diff
==============================================================================
--- directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMapImpl.java (original)
+++ directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMapImpl.java Tue Jan 24 14:10:56 2012
@@ -1146,15 +1146,15 @@ public class AvlTreeMapImpl<K, V> implem
{
return allowDuplicates;
}
-
-
+
+
/**
* removes all the nodes from the tree
*/
public void removeAll()
{
LinkedAvlMapNode<K, V> tmp;
-
+
while ( first != null )
{
tmp = first;
Modified: directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMapNoDupsWrapperCursor.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMapNoDupsWrapperCursor.java?rev=1235258&r1=1235257&r2=1235258&view=diff
==============================================================================
--- directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMapNoDupsWrapperCursor.java (original)
+++ directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMapNoDupsWrapperCursor.java Tue Jan 24 14:10:56 2012
@@ -19,6 +19,7 @@
*/
package org.apache.directory.server.core.avltree;
+
import org.apache.directory.shared.ldap.model.cursor.AbstractTupleCursor;
import org.apache.directory.shared.ldap.model.cursor.InvalidCursorPositionException;
import org.apache.directory.shared.ldap.model.cursor.Tuple;
@@ -31,110 +32,110 @@ import org.apache.directory.shared.ldap.
*
* @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
*/
-public class AvlTreeMapNoDupsWrapperCursor<K,V> extends AbstractTupleCursor<K, V>
+public class AvlTreeMapNoDupsWrapperCursor<K, V> extends AbstractTupleCursor<K, V>
{
private final AvlSingletonOrOrderedSetCursor<K, V> wrapped;
- private final Tuple<K,V> returnedTuple = new Tuple<K, V>();
-
-
+ private final Tuple<K, V> returnedTuple = new Tuple<K, V>();
+
+
public AvlTreeMapNoDupsWrapperCursor( AvlSingletonOrOrderedSetCursor<K, V> wrapped )
{
this.wrapped = wrapped;
}
-
+
public void afterKey( K key ) throws Exception
{
wrapped.afterKey( key );
}
-
+
public void afterValue( K key, V value ) throws Exception
{
throw new UnsupportedOperationException( "This Cursor does not support duplicate keys." );
}
-
+
public void beforeKey( K key ) throws Exception
{
wrapped.beforeKey( key );
}
-
+
public void beforeValue( K key, V value ) throws Exception
{
throw new UnsupportedOperationException( "This Cursor does not support duplicate keys." );
}
-
+
public void after( Tuple<K, V> element ) throws Exception
{
wrapped.afterKey( element.getKey() );
}
-
+
public void afterLast() throws Exception
{
wrapped.afterLast();
}
-
+
public boolean available()
{
return wrapped.available();
}
-
+
public void before( Tuple<K, V> element ) throws Exception
{
wrapped.beforeKey( element.getKey() );
}
-
+
public void beforeFirst() throws Exception
{
wrapped.beforeFirst();
}
-
+
public boolean first() throws Exception
{
return wrapped.first();
}
-
+
public Tuple<K, V> get() throws Exception
{
if ( wrapped.available() )
{
Tuple<K, SingletonOrOrderedSet<V>> tuple = wrapped.get();
-
+
if ( tuple.getValue().isOrderedSet() )
{
System.out.println( "tuple key = " + tuple.getKey() );
tuple.getValue().getOrderedSet().printTree();
}
-
+
returnedTuple.setBoth( tuple.getKey(), tuple.getValue().getSingleton() );
return returnedTuple;
}
-
+
throw new InvalidCursorPositionException();
}
-
+
public boolean last() throws Exception
{
return wrapped.last();
}
-
+
public boolean next() throws Exception
{
return wrapped.next();
}
-
+
public boolean previous() throws Exception
{
return wrapped.previous();
Modified: directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMarshaller.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMarshaller.java?rev=1235258&r1=1235257&r2=1235258&view=diff
==============================================================================
--- directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMarshaller.java (original)
+++ directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMarshaller.java Tue Jan 24 14:10:56 2012
@@ -43,10 +43,10 @@ public class AvlTreeMarshaller<E> implem
/** marshaller to be used for marshalling the keys */
private Marshaller<E> keyMarshaller;
-
+
/** key Comparator for the AvlTree */
private Comparator<E> comparator;
-
+
/**
* Creates a new instance of AvlTreeMarshaller with a custom key
@@ -81,23 +81,23 @@ public class AvlTreeMarshaller<E> implem
*/
public byte[] serialize( AvlTree<E> tree )
{
- if( tree.isEmpty() )
+ if ( tree.isEmpty() )
{
return EMPTY_TREE;
}
LinkedAvlNode<E> x = tree.getFirst().next;
-
- while( x != null )
+
+ while ( x != null )
{
- x.setIndex( x.previous.getIndex() + 1 );
+ x.setIndex( x.previous.getIndex() + 1 );
x = x.next;
}
-
+
ByteArrayOutputStream byteStream = new ByteArrayOutputStream();
DataOutputStream out = new DataOutputStream( byteStream );
byte[] data = null;
-
+
try
{
out.writeByte( 0 ); // represents the start of AvlTree byte stream
@@ -107,15 +107,15 @@ public class AvlTreeMarshaller<E> implem
data = byteStream.toByteArray();
out.close();
}
- catch( IOException e )
+ catch ( IOException e )
{
e.printStackTrace();
}
-
+
return data;
}
-
+
/**
* writes the content of the AVLTree to an output stream.
* The current format is
@@ -130,34 +130,34 @@ public class AvlTreeMarshaller<E> implem
private void writeTree( LinkedAvlNode<E> node, DataOutputStream out ) throws IOException
{
byte[] data = keyMarshaller.serialize( node.getKey() );
-
+
out.writeInt( data.length ); // data-length
out.write( data ); // data
out.writeInt( node.getIndex() ); // index
-
- if( node.getLeft() != null )
+
+ if ( node.getLeft() != null )
{
out.writeInt( 2 ); // left
writeTree( node.getLeft(), out );
}
else
{
- out.writeInt( 0 );
+ out.writeInt( 0 );
}
-
- if( node.getRight() != null )
+
+ if ( node.getRight() != null )
{
out.writeInt( 4 ); // right
writeTree( node.getRight(), out );
}
else
{
- out.writeInt( 0 );
+ out.writeInt( 0 );
}
-
+
}
-
+
/**
* Creates an AVLTree from given bytes of data.
*
@@ -177,43 +177,43 @@ public class AvlTreeMarshaller<E> implem
ByteArrayInputStream bin = new ByteArrayInputStream( data );
DataInputStream din = new DataInputStream( bin );
-
+
byte startByte = din.readByte();
-
- if( startByte != 0 )
+
+ if ( startByte != 0 )
{
throw new IOException( I18n.err( I18n.ERR_443 ) );
}
-
+
int size = din.readInt();
-
- LinkedAvlNode[] nodes = new LinkedAvlNode[ size ];
+
+ LinkedAvlNode[] nodes = new LinkedAvlNode[size];
LinkedAvlNode<E> root = readTree( din, null, nodes );
-
+
AvlTreeImpl<E> tree = new AvlTreeImpl<E>( comparator );
-
+
tree.setRoot( root );
-
+
tree.setFirst( nodes[0] );
-
+
// Update the size
tree.setSize( size );
-
- if( nodes.length >= 1 )
+
+ if ( nodes.length >= 1 )
{
- tree.setLast( nodes[ nodes.length - 1 ] );
+ tree.setLast( nodes[nodes.length - 1] );
}
-
- for( int i = 0; i < nodes.length - 1; i++ )
+
+ for ( int i = 0; i < nodes.length - 1; i++ )
{
- nodes[ i ].setNext( nodes[ i + 1] );
- nodes[ i + 1].setPrevious( nodes[ i ] );
+ nodes[i].setNext( nodes[i + 1] );
+ nodes[i + 1].setPrevious( nodes[i] );
}
return tree;
}
-
+
/**
* Reads the data from given InputStream and creates the LinkedAvlNodes to
* form the tree node = [size] [data-length] [data] [index] [child-marker]
@@ -224,35 +224,36 @@ public class AvlTreeMarshaller<E> implem
* @return the deserialized AvlTree node
* @throws IOException on failures to deserialize or read from the stream
*/
- public LinkedAvlNode<E> readTree( DataInputStream in, LinkedAvlNode<E> node, LinkedAvlNode[] nodes ) throws IOException
+ public LinkedAvlNode<E> readTree( DataInputStream in, LinkedAvlNode<E> node, LinkedAvlNode[] nodes )
+ throws IOException
{
int dLen = in.readInt();
-
- byte[] data = new byte[ dLen ];
+
+ byte[] data = new byte[dLen];
//noinspection ResultOfMethodCallIgnored
in.readFully( data );
E key = keyMarshaller.deserialize( data );
node = new LinkedAvlNode( key );
-
+
int index = in.readInt();
- nodes[ index ] = node;
-
+ nodes[index] = node;
+
int childMarker = in.readInt();
-
- if( childMarker == 2)
+
+ if ( childMarker == 2 )
{
node.setLeft( readTree( in, node.getLeft(), nodes ) );
}
-
+
childMarker = in.readInt();
-
- if( childMarker == 4 )
+
+ if ( childMarker == 4 )
{
node.setRight( readTree( in, node.getRight(), nodes ) );
}
-
+
return node;
}
}
Modified: directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeSingleton.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeSingleton.java?rev=1235258&r1=1235257&r2=1235258&view=diff
==============================================================================
--- directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeSingleton.java (original)
+++ directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeSingleton.java Tue Jan 24 14:10:56 2012
@@ -19,6 +19,7 @@
*/
package org.apache.directory.server.core.avltree;
+
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
@@ -35,14 +36,14 @@ public class AvlTreeSingleton<K> impleme
{
private final LinkedAvlNode<K> singleton;
private final Comparator<K> comparator;
-
-
+
+
public AvlTreeSingleton( K key, Comparator<K> comparator )
{
this.singleton = new LinkedAvlNode<K>( key );
this.comparator = comparator;
}
-
+
/**
* {@inheritDoc}
@@ -57,7 +58,7 @@ public class AvlTreeSingleton<K> impleme
return null;
}
-
+
/**
* {@inheritDoc}
*/
@@ -71,7 +72,7 @@ public class AvlTreeSingleton<K> impleme
return null;
}
-
+
/**
* {@inheritDoc}
*/
@@ -84,7 +85,7 @@ public class AvlTreeSingleton<K> impleme
return null;
}
-
+
/**
* {@inheritDoc}
@@ -99,7 +100,7 @@ public class AvlTreeSingleton<K> impleme
return null;
}
-
+
/**
* {@inheritDoc}
*/
@@ -121,7 +122,7 @@ public class AvlTreeSingleton<K> impleme
{
return comparator;
}
-
+
/**
* {@inheritDoc}
@@ -131,7 +132,7 @@ public class AvlTreeSingleton<K> impleme
return singleton;
}
-
+
/**
* {@inheritDoc}
*/
@@ -140,7 +141,7 @@ public class AvlTreeSingleton<K> impleme
return Collections.singletonList( singleton.getKey() );
}
-
+
/**
* {@inheritDoc}
*/
@@ -148,7 +149,7 @@ public class AvlTreeSingleton<K> impleme
{
return singleton;
}
-
+
/**
* {@inheritDoc}
@@ -167,25 +168,25 @@ public class AvlTreeSingleton<K> impleme
return 1;
}
-
+
public K insert( K key )
{
throw new UnsupportedOperationException( I18n.err( I18n.ERR_444 ) );
}
-
+
public boolean isEmpty()
{
return false;
}
-
+
public void printTree()
{
System.out.println( "[ " + singleton + " ]" );
}
-
+
public K remove( K key )
{
throw new UnsupportedOperationException( I18n.err( I18n.ERR_444 ) );
Modified: directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/KeyTupleAvlCursor.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/KeyTupleAvlCursor.java?rev=1235258&r1=1235257&r2=1235258&view=diff
==============================================================================
--- directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/KeyTupleAvlCursor.java (original)
+++ directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/KeyTupleAvlCursor.java Tue Jan 24 14:10:56 2012
@@ -32,12 +32,12 @@ import org.apache.directory.shared.ldap.
*
* @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
*/
-public class KeyTupleAvlCursor<K,V> extends AbstractTupleCursor<K,V>
+public class KeyTupleAvlCursor<K, V> extends AbstractTupleCursor<K, V>
{
private final AvlTreeCursor<V> wrapped;
private final K key;
- private Tuple<K,V> returnedTuple = new Tuple<K,V>();
+ private Tuple<K, V> returnedTuple = new Tuple<K, V>();
private boolean valueAvailable;
@@ -83,7 +83,7 @@ public class KeyTupleAvlCursor<K,V> exte
public void beforeValue( K key, V value ) throws Exception
{
checkNotClosed( "beforeValue()" );
- if ( key != null && ! key.equals( this.key ) )
+ if ( key != null && !key.equals( this.key ) )
{
throw new UnsupportedOperationException( I18n.err( I18n.ERR_446 ) );
}
@@ -96,7 +96,7 @@ public class KeyTupleAvlCursor<K,V> exte
public void afterValue( K key, V value ) throws Exception
{
checkNotClosed( "afterValue()" );
- if ( key != null && ! key.equals( this.key ) )
+ if ( key != null && !key.equals( this.key ) )
{
throw new UnsupportedOperationException( I18n.err( I18n.ERR_446 ) );
}
@@ -114,7 +114,7 @@ public class KeyTupleAvlCursor<K,V> exte
* @param element the valueTuple who's value is used to position this Cursor
* @throws Exception if there are failures to position the Cursor
*/
- public void before( Tuple<K,V> element ) throws Exception
+ public void before( Tuple<K, V> element ) throws Exception
{
checkNotClosed( "before()" );
wrapped.before( element.getValue() );
@@ -122,7 +122,7 @@ public class KeyTupleAvlCursor<K,V> exte
}
- public void after( Tuple<K,V> element ) throws Exception
+ public void after( Tuple<K, V> element ) throws Exception
{
checkNotClosed( "after()" );
wrapped.after( element.getValue() );
@@ -194,7 +194,7 @@ public class KeyTupleAvlCursor<K,V> exte
}
- public Tuple<K,V> get() throws Exception
+ public Tuple<K, V> get() throws Exception
{
checkNotClosed( "get()" );
if ( valueAvailable )
Modified: directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/LinkedAvlMapNode.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/LinkedAvlMapNode.java?rev=1235258&r1=1235257&r2=1235258&view=diff
==============================================================================
--- directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/LinkedAvlMapNode.java (original)
+++ directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/LinkedAvlMapNode.java Tue Jan 24 14:10:56 2012
@@ -29,7 +29,7 @@ public class LinkedAvlMapNode<K, V>
{
/** The key stored in the node */
K key;
-
+
/** the value stored in the node */
SingletonOrOrderedSet<V> value;
Modified: directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/LinkedAvlNode.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/LinkedAvlNode.java?rev=1235258&r1=1235257&r2=1235258&view=diff
==============================================================================
--- directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/LinkedAvlNode.java (original)
+++ directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/LinkedAvlNode.java Tue Jan 24 14:10:56 2012
@@ -25,30 +25,30 @@ package org.apache.directory.server.core
*
* @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
*/
-public class LinkedAvlNode<T>
+public class LinkedAvlNode<T>
{
/** The data stored in the node */
T key;
-
+
/** The left child */
LinkedAvlNode<T> left;
-
+
/** The right child */
LinkedAvlNode<T> right;
-
+
/** The next node, superior to the current node */
LinkedAvlNode<T> next;
/** The previous node, inferior to the current node */
LinkedAvlNode<T> previous;
-
+
int depth;
int index;
-
+
boolean isLeft;
int height = 1;
-
-
+
+
/**
* Creates a new instance of LinkedAvlNode, containing a given value.
*
@@ -86,99 +86,113 @@ public class LinkedAvlNode<T>
}
- public LinkedAvlNode<T> getLeft() {
+ public LinkedAvlNode<T> getLeft()
+ {
return left;
}
- public LinkedAvlNode<T> getRight() {
+ public LinkedAvlNode<T> getRight()
+ {
return right;
}
- public T getKey() {
+
+ public T getKey()
+ {
return key;
}
+
public boolean isLeaf()
{
return ( right == null && left == null );
}
-
- public int getDepth() {
+
+
+ public int getDepth()
+ {
return depth;
}
- public void setDepth( int depth ) {
+
+ public void setDepth( int depth )
+ {
this.depth = depth;
}
+
public int getHeight()
{
return height;
}
-
-
- public void setNext( LinkedAvlNode<T> next )
- {
- this.next = next;
- }
-
-
- public void setPrevious( LinkedAvlNode<T> previous )
- {
- this.previous = previous;
- }
-
-
+
+
+ public void setNext( LinkedAvlNode<T> next )
+ {
+ this.next = next;
+ }
+
+
+ public void setPrevious( LinkedAvlNode<T> previous )
+ {
+ this.previous = previous;
+ }
+
+
public int computeHeight()
{
- if(right == null && left == null)
+ if ( right == null && left == null )
{
height = 1;
return height;
}
-
- int lh,rh;
-
- if( isLeft )
+
+ int lh, rh;
+
+ if ( isLeft )
{
lh = ( left == null ? -1 : left.computeHeight() );
rh = ( right == null ? -1 : right.getHeight() );
}
- else
+ else
{
rh = ( right == null ? -1 : right.computeHeight() );
lh = ( left == null ? -1 : left.getHeight() );
}
-
+
height = 1 + Math.max( lh, rh );
-
+
return height;
}
-
+
+
public int getBalance()
{
int lh = ( left == null ? 0 : left.computeHeight() );
int rh = ( right == null ? 0 : right.computeHeight() );
-
+
return ( rh - lh );
}
+
public int getIndex()
{
- return index;
+ return index;
}
- public void setIndex(int index)
+
+ public void setIndex( int index )
{
this.index = index;
}
@Override
- public String toString() {
+ public String toString()
+ {
return "[" + key + "]";
}
-
+
}
Modified: directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/Marshaller.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/Marshaller.java?rev=1235258&r1=1235257&r2=1235258&view=diff
==============================================================================
--- directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/Marshaller.java (original)
+++ directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/Marshaller.java Tue Jan 24 14:10:56 2012
@@ -33,5 +33,6 @@ public interface Marshaller<E>
{
byte[] serialize( E object ) throws IOException;
+
E deserialize( byte[] bytes ) throws IOException;
}