You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@directory.apache.org by el...@apache.org on 2009/07/18 02:39:31 UTC
svn commit: r795286 - in
/directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree:
ArrayMarshaller.java ArrayTree.java ArrayTreeCursor.java
Author: elecharny
Date: Sat Jul 18 00:39:30 2009
New Revision: 795286
URL: http://svn.apache.org/viewvc?rev=795286&view=rev
Log:
Added the ArrayTree class and the associated cursor to replace the AvlTree
Added:
directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/ArrayMarshaller.java
Modified:
directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/ArrayTree.java
directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/ArrayTreeCursor.java
Added: directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/ArrayMarshaller.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/ArrayMarshaller.java?rev=795286&view=auto
==============================================================================
--- directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/ArrayMarshaller.java (added)
+++ directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/ArrayMarshaller.java Sat Jul 18 00:39:30 2009
@@ -0,0 +1,207 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+package org.apache.directory.server.core.avltree;
+
+
+import java.io.ByteArrayInputStream;
+import java.io.ByteArrayOutputStream;
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.util.Comparator;
+
+import org.apache.directory.shared.ldap.util.StringTools;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+import sun.reflect.Reflection;
+
+
+/**
+ * Class to serialize the Array data.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $Rev$, $Date$
+ */
+@SuppressWarnings("unchecked")
+public class ArrayMarshaller<E> implements Marshaller<ArrayTree<E>>
+{
+ /** static logger */
+ private static final Logger LOG = LoggerFactory.getLogger( ArrayMarshaller.class );
+
+ /** used for serialized form of an empty AvlTree */
+ private static final byte[] EMPTY_TREE = new byte[1];
+
+ /** 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
+ * Marshaller.
+ *
+ * @param comparator Comparator to be used for key comparision
+ * @param keyMarshaller marshaller for keys
+ */
+ public ArrayMarshaller( Comparator<E> comparator, Marshaller<E> keyMarshaller )
+ {
+ this.comparator = comparator;
+ this.keyMarshaller = keyMarshaller;
+ }
+
+
+ /**
+ * Creates a new instance of AvlTreeMarshaller with the default key
+ * Marshaller which uses Java Serialization.
+ *
+ * @param comparator Comparator to be used for key comparision
+ */
+ public ArrayMarshaller( Comparator<E> comparator )
+ {
+ this.comparator = comparator;
+ this.keyMarshaller = DefaultMarshaller.INSTANCE;
+ }
+
+
+ /**
+ * Marshals the given tree to bytes
+ * @param tree the tree to be marshalled
+ */
+ public byte[] serialize( ArrayTree<E> tree )
+ {
+ if ( ( tree == null ) || ( tree.size() == 0 ) )
+ {
+ return EMPTY_TREE;
+ }
+
+ ByteArrayOutputStream byteStream = new ByteArrayOutputStream();
+ DataOutputStream out = new DataOutputStream( byteStream );
+ byte[] data = null;
+
+ try
+ {
+ out.writeByte( 0 ); // represents the start of an Array byte stream
+ out.writeInt( tree.size() );
+
+ for ( int position = 0; position < tree.size(); position++ )
+ {
+ E value = tree.get( position );
+ byte[] bytes = keyMarshaller.serialize( value );
+
+ // Write the key length
+ out.writeInt( bytes.length );
+
+ // Write the key if its length is not null
+ if ( bytes.length != 0 )
+ {
+ out.write( bytes );
+ }
+ }
+
+ out.flush();
+ data = byteStream.toByteArray();
+
+ // Try to deserialize, just to see
+ try
+ {
+ deserialize( data );
+ }
+ catch (NullPointerException npe )
+ {
+ System.out.println( "Bad serialization, tree : [" + StringTools.dumpBytes( data ) + "]");
+ throw npe;
+ }
+
+ out.close();
+ }
+ catch( IOException e )
+ {
+ e.printStackTrace();
+ }
+
+ return data;
+ }
+
+
+ /**
+ * Creates an Array from given bytes of data.
+ *
+ * @param data byte array to be converted into an array
+ */
+ public ArrayTree<E> deserialize( byte[] data ) throws IOException
+ {
+ LOG.debug( "Deserializing the tree, called by {}", Reflection.getCallerClass( 2 ).getSimpleName() );
+
+ try
+ {
+ if ( ( data == null ) || ( data.length == 0 ) )
+ {
+ throw new IOException( "Null or empty data array is invalid." );
+ }
+
+ if ( ( data.length == 1 ) && ( data[0] == 0 ) )
+ {
+ E[] array = (E[])new Object[]{};
+ ArrayTree<E> tree = new ArrayTree<E>( comparator, array );
+ return tree;
+ }
+
+ ByteArrayInputStream bin = new ByteArrayInputStream( data );
+ DataInputStream din = new DataInputStream( bin );
+
+ byte startByte = din.readByte();
+
+ if( startByte != 0 )
+ {
+ throw new IOException("wrong array serialized data format");
+ }
+
+ int size = din.readInt();
+ E[] nodes = (E[])new Object[size];
+
+ for ( int i = 0; i < size; i++ )
+ {
+ // Read the object's size
+ int dataSize = din.readInt();
+
+ if ( dataSize != 0 )
+ {
+ byte[] bytes = new byte[ dataSize ];
+
+ din.read( bytes );
+ E key = keyMarshaller.deserialize( bytes );
+ nodes[i] = key;
+ }
+ }
+
+ ArrayTree<E> arrayTree = new ArrayTree<E>( comparator, nodes );
+
+ return arrayTree;
+ }
+ catch (NullPointerException npe )
+ {
+ System.out.println( "Bad tree : [" + StringTools.dumpBytes( data ) + "]");
+ throw npe;
+ }
+ }
+}
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=795286&r1=795285&r2=795286&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 Sat Jul 18 00:39:30 2009
@@ -46,9 +46,6 @@
/** The extend size to use when increasing the array size */
private static final int INCREMENT = 16;
- /** The current position in the array */
- private int position;
-
/**
* Creates a new instance of AVLTree.
*
@@ -59,7 +56,31 @@
this.comparator = comparator;
array = (K[])new Object[INCREMENT];
size = 0;
- position = 0;
+ }
+
+
+ /**
+ * Creates a new instance of AVLTree.
+ *
+ * @param comparator the comparator to be used for comparing keys
+ */
+ 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];
+ System.arraycopy( array, 0, this.array, 0, size );
+ }
}
@@ -73,14 +94,29 @@
/**
- * Inserts a key.
+ * Inserts a key. Null value insertion is not allowed.
*
- * @param key the item to be inserted
+ * @param key the item to be inserted, should not be null
* @return the replaced key if it already exists
* Note: Ignores if the given key already exists.
*/
public K insert( K key )
{
+ if ( key == null )
+ {
+ // 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
@@ -89,15 +125,19 @@
System.arraycopy( array, 0, newArray, 0, size );
array = newArray;
}
-
+
+ // Currently, just add the element at the end of the array
+ // and sort the array. We could be more efficient by inserting the
+ // element at the right position by splitting the array in two
+ // parts and copying the right part one slot on the right.
array[size++] = key;
Arrays.sort( array, 0, size, comparator );
- return key;
+ return null;
}
- /**
+ /**q<
* Reduce the array size if neede
*/
private void reduceArray()
@@ -122,7 +162,7 @@
public K remove( K key )
{
// Search for the key position in the tree
- int pos = findPosition( key );
+ int pos = getPosition( key );
if ( pos != -1 )
{
@@ -163,7 +203,7 @@
*
* @return the number of nodes present in this tree
*/
- public int getSize()
+ public int size()
{
return size;
}
@@ -217,12 +257,13 @@
* Get the element at a given position
* @param position The position in the tree
* @return The found key, or null if the position is out of scope
+ * @throws ArrayIndexOutOfBoundsException If the position is not within the array boundaries
*/
- public K get( int position )
+ public K get( int position ) throws ArrayIndexOutOfBoundsException
{
if ( ( position < 0 ) || ( position >= size ) )
{
- return null;
+ throw new ArrayIndexOutOfBoundsException();
}
return array[position];
@@ -230,32 +271,15 @@
/**
- * Get the element at the current position
- * @return The found key, or null if the position is out of scope
- */
- public K get()
- {
- if ( ( position < 0 ) || ( position >= size ) )
- {
- return null;
- }
-
- return array[position];
- }
-
-
- /**
* Get the first element in the tree. It sets the current position to this
* element.
* @return The first element of this tree
*/
public K getFirst()
{
- position = 0;
-
if ( size != 0 )
{
- return array[position];
+ return array[0];
}
else
{
@@ -265,51 +289,15 @@
/**
- * Get the next element in the tree, from the current position. The position is
- * changed accordingly
- * @return The next element of this tree
- */
- public K getNext()
- {
- if ( ( position < 0 ) || ( position >= size - 1 ) )
- {
- return null;
- }
-
- position++;
- return array[position];
- }
-
-
- /**
- * Get the previous element in the tree, from the current position. The position is
- * changed accordingly
- * @return The previous element of this tree
- */
- public K getPrevious()
- {
- if ( ( position <= 0 ) || ( position > size - 1 ) )
- {
- return null;
- }
-
- position--;
- return array[position];
- }
-
-
- /**
* Get the last element in the tree. It sets the current position to this
* element.
* @return The last element in this tree
*/
public K getLast()
{
- position = size - 1;
-
if ( size != 0 )
{
- return array[position];
+ return array[size - 1];
}
else
{
@@ -327,56 +315,111 @@
*/
public K findGreater( K key )
{
- if ( size == 0 )
+ if ( key == null )
{
return null;
}
- int current = size >> 1;
- int end = size;
- int start = 0;
- int previousCurrent = -1;
-
- while ( previousCurrent != current )
+ switch ( size )
{
- int res = comparator.compare( array[current], key ) ;
-
- if ( res == 0 )
- {
- if ( current == size - 1 )
+ case 0 :
+ return null;
+
+ case 1 :
+ if ( comparator.compare( array[0], key ) > 0 )
+ {
+ return array[0];
+ }
+ else
{
return null;
}
+
+ case 2 :
+ if ( comparator.compare( array[0], key ) > 0 )
+ {
+ return array[0];
+ }
+ else if ( comparator.compare( array[1], key ) > 0 )
+ {
+ return array[1];
+ }
else
{
- position = current + 1;
- return array[position];
+ return null;
+ }
+
+ 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 ) ;
+
+ if ( res == 0 )
+ {
+ // Current can't be equal to zero at this point
+ return array[current + 1];
+ }
+ else if ( res < 0 )
+ {
+ start = current;
+ current = (current + end + 1) >> 1;
+ }
+ else
+ {
+ end = current;
+ current = (current + start + 1) >> 1 ;
+ }
+ }
+
+ switch ( end - start + 1 )
+ {
+ case 1 :
+ int res = comparator.compare( array[start], key );
+
+ if ( res <= 0 )
+ {
+ if ( start == size )
+ {
+ return null;
+ }
+ else
+ {
+ return array[start + 1];
+ }
+ }
+
+ return array[start];
+
+ 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)
+ {
+ return null;
+ }
+
+ return array[start + 2];
+ }
+
+ return array[start + 1];
+ }
+
+ return array[start];
}
- }
- else if ( res < 0 )
- {
- start = current;
- previousCurrent = current;
- current = (start + end ) >> 1;
- }
- else
- {
- end = current;
- previousCurrent = current;
- current = (start + end ) >> 1 ;
- }
}
- // We haven't found the element, so take the next one
- if ( current == size - 1 )
- {
- return null;
- }
- else
- {
- position = current + 1;
- return array[position];
- }
+ return null;
}
@@ -389,49 +432,112 @@
*/
public K findGreaterOrEqual( K key )
{
- if ( size == 0 )
+ if ( key == null )
{
return null;
}
- int current = size >> 1;
- int end = size;
- int start = 0;
- int previousCurrent = -1;
-
- while ( previousCurrent != current )
+ switch ( size )
{
- int res = comparator.compare( array[current], key ) ;
-
- if ( res == 0 )
- {
- position = current;
- return array[current];
- }
- else if ( res < 0 )
- {
- start = current;
- previousCurrent = current;
- current = (current + end ) >> 1;
- }
- else
- {
- end = current;
- previousCurrent = current;
- current = (current + start ) >> 1 ;
- }
+ case 0 :
+ return null;
+
+ case 1 :
+ if ( comparator.compare( array[0], key ) >= 0 )
+ {
+ return array[0];
+ }
+ else
+ {
+ return null;
+ }
+
+ case 2 :
+ if ( comparator.compare( array[0], key ) >= 0 )
+ {
+ return array[0];
+ }
+ else if ( comparator.compare( array[1], key ) >= 0 )
+ {
+ return array[1];
+ }
+ else
+ {
+ return null;
+ }
+
+ 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 ) ;
+
+ if ( res == 0 )
+ {
+ return array[current];
+ }
+ else if ( res < 0 )
+ {
+ start = current;
+ current = (current + end + 1) >> 1;
+ }
+ else
+ {
+ end = current;
+ current = (current + start + 1) >> 1 ;
+ }
+ }
+
+ switch ( end - start + 1 )
+ {
+ case 1 :
+ int res = comparator.compare( array[start], key );
+
+ if ( res >= 0)
+ {
+ return array[start];
+ }
+ else
+ {
+ if ( start == size - 1 )
+ {
+ return null;
+ }
+ else
+ {
+ return array[start + 1];
+ }
+ }
+
+ 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)
+ {
+ return null;
+ }
+
+ return array[start + 2];
+ }
+
+ return array[start + 1];
+ }
+
+ return array[start];
+ }
}
- // We haven't found the element, so take the next one
- if ( current == size - 1 )
- {
- return null;
- }
- else
- {
- position = current + 1;
- return array[position];
- }
+ return null;
}
@@ -444,56 +550,132 @@
*/
public K findLess( K key )
{
- if ( size == 0 )
+ if ( key == null )
{
return null;
}
- int current = size >> 1;
- int end = size;
- int start = 0;
- int previousCurrent = -1;
-
- while ( previousCurrent != current )
+ switch ( size )
{
- int res = comparator.compare( array[current], key ) ;
-
- if ( res == 0 )
- {
- if ( current == 0 )
+ case 0 :
+ return null;
+
+ case 1 :
+ if ( comparator.compare( array[0], key ) >= 0 )
{
return null;
}
else
{
- position = current - 1;
- return array[position];
+ return array[0];
+ }
+
+ case 2 :
+ if ( comparator.compare( array[0], key ) >= 0 )
+ {
+ return null;
+ }
+ else if ( comparator.compare( array[1], key ) >= 0 )
+ {
+ return array[0];
+ }
+ else
+ {
+ return array[1];
+ }
+
+ 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 ) ;
+
+ if ( res == 0 )
+ {
+ // Current can't be equal to zero at this point
+ return array[current - 1];
+ }
+ else if ( res < 0 )
+ {
+ start = current;
+ current = (current + end + 1) >> 1;
+ }
+ else
+ {
+ end = current;
+ current = (current + start + 1) >> 1 ;
+ }
+ }
+
+ switch ( end - start + 1 )
+ {
+ case 1 :
+ // Three cases :
+ // o The value is equal to the current position, or below
+ // the current position :
+ // - if the current position is at the beginning
+ // of the array, return null
+ // - otherwise, return the previous position in the array
+ // o The value is above the current position :
+ // - return the current position
+ int res = comparator.compare( array[start], key );
+
+ if ( res >= 0)
+ {
+ // start can be equal to 0. Check that
+ if ( start == 1 )
+ {
+ return null;
+ }
+ else
+ {
+ return array[start - 1];
+ }
+ }
+ else
+ {
+ return array[start];
+ }
+
+ case 2 :
+ // Four cases :
+ // o the value is equal the current position, or below
+ // the first position :
+ // - if the current position is at the beginning
+ // of the array, return null
+ // - otherwise, return the previous element
+ // o the value is above the first position but below
+ // 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 )
+ {
+ return null;
+ }
+ else
+ {
+ return array[start - 1];
+ }
+ }
+ else if ( comparator.compare( array[start + 1], key ) >= 0 )
+ {
+ return array[start];
+ }
+ else
+ {
+ return array[start + 1];
+ }
}
- }
- else if ( res < 0 )
- {
- start = current;
- previousCurrent = current;
- current = (current + end ) >> 1;
- }
- else
- {
- end = current;
- previousCurrent = current;
- current = (current + start ) >> 1 ;
- }
}
- // We haven't found the element, so take the previous one
- if ( current == 0 )
- {
- return null;
- }
- else
- {
- position = current;
- return array[current];
- }
+ return null;
}
@@ -506,136 +688,578 @@
*/
public K findLessOrEqual( K key )
{
- if ( size == 0 )
+ if ( key == null )
{
return null;
}
- int current = size >> 1;
- int end = size;
- int start = 0;
- int previousCurrent = -1;
-
- while ( previousCurrent != current )
+ switch ( size )
{
- int res = comparator.compare( array[current], key ) ;
-
- if ( res == 0 )
- {
- position = current;
- return array[current];
- }
- else if ( res < 0 )
- {
- start = current;
- previousCurrent = current;
- current = (current + end ) >> 1;
- }
- else
- {
- end = current;
- previousCurrent = current;
- current = (current + start ) >> 1 ;
- }
+ case 0 :
+ return null;
+
+ case 1 :
+ if ( comparator.compare( array[0], key ) <= 0 )
+ {
+ return array[0];
+ }
+ else
+ {
+ return null;
+ }
+
+ case 2 :
+ int res = comparator.compare( array[0], key );
+
+ if ( res > 0 )
+ {
+ return null;
+ }
+ else if ( res == 0 )
+ {
+ return array[0];
+ }
+
+ res = comparator.compare( array[1], key );
+
+ if ( res == 0 )
+ {
+ return array[1];
+ }
+ else if ( comparator.compare( array[1], key ) > 0 )
+ {
+ return array[0];
+ }
+ else
+ {
+ return array[1];
+ }
+
+ 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 ) ;
+
+ if ( res == 0 )
+ {
+ return array[current];
+ }
+ else if ( res < 0 )
+ {
+ start = current;
+ current = (current + end + 1) >> 1;
+ }
+ else
+ {
+ end = current;
+ current = (current + start + 1) >> 1 ;
+ }
+ }
+
+ switch ( end - start + 1 )
+ {
+ case 1 :
+ // Three cases :
+ // o The value is equal to the current position, or below
+ // the current position :
+ // - if the current position is at the beginning
+ // of the array, return null
+ // - otherwise, return the previous position in the array
+ // o The value is above the current position :
+ // - return the current position
+ res = comparator.compare( array[start], key );
+
+ if ( res > 0)
+ {
+ // start can be equal to 0. Check that
+ if ( start == 1 )
+ {
+ return null;
+ }
+ else
+ {
+ return array[start - 1];
+ }
+ }
+ else
+ {
+ return array[start];
+ }
+
+ case 2 :
+ // Four cases :
+ // o the value is equal the current position, or below
+ // the first position :
+ // - if the current position is at the beginning
+ // of the array, return null
+ // - otherwise, return the previous element
+ // o the value is above the first position but below
+ // 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 )
+ {
+ return null;
+ }
+ else
+ {
+ return array[start - 1];
+ }
+ }
+
+ res = comparator.compare( array[start + 1], key );
+
+ if ( res > 0 )
+ {
+ return array[start];
+ }
+ else
+ {
+ return array[start + 1];
+ }
+ }
}
- // We haven't found the element, so take the previous one
- if ( current == 0 )
- {
- return null;
- }
- else
- {
- position = current - 1;
- return array[position];
- }
+ return null;
}
/**
- * Find
+ * Find an element in the array.
*
* @param key the key to find
- * @return the list of traversed LinkedAvlNode.
+ * @return the found node, or null
*/
public K find( K key )
{
- if ( size == 0 )
+ if ( key == null )
{
- position = 0;
return null;
}
- int current = size >> 1;
- int end = size;
- int start = 0;
- int previousCurrent = -1;
-
- while ( previousCurrent != current )
+ switch ( size )
{
- int res = comparator.compare( array[current], key ) ;
-
- if ( res == 0 )
- {
- position = current;
- return key;
- }
- else if ( res < 0 )
- {
- start = current;
- previousCurrent = current;
- current = (current + end ) >> 1;
- }
- else
- {
- end = current;
- previousCurrent = current;
- current = (current + start ) >> 1 ;
- }
+ case 0 :
+ return null;
+
+ case 1 :
+ if ( comparator.compare( array[0], key ) == 0 )
+ {
+ return array[0];
+ }
+ else
+ {
+ return null;
+ }
+
+ case 2 :
+ if ( comparator.compare( array[0], key ) == 0 )
+ {
+ return array[0];
+ }
+ else if ( comparator.compare( array[1], key ) == 0 )
+ {
+ return array[1];
+ }
+ else
+ {
+ return null;
+ }
+
+ 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 ) ;
+
+ if ( res == 0 )
+ {
+ return array[current];
+ }
+ else if ( res < 0 )
+ {
+ start = current;
+ current = (current + end + 1) >> 1;
+ }
+ else
+ {
+ end = current;
+ current = (current + start + 1) >> 1 ;
+ }
+ }
+
+ switch ( end - start + 1 )
+ {
+ case 1 :
+ if ( comparator.compare( array[start], key ) == 0 )
+ {
+ return array[start];
+ }
+ else
+ {
+ return null;
+ }
+
+ case 2 :
+ if ( comparator.compare( array[start], key ) == 0 )
+ {
+ return array[start];
+ }
+ else if ( comparator.compare( array[end], key ) == 0 )
+ {
+ return array[end];
+ }
+ else
+ {
+ return null;
+ }
+ }
}
- position = 0;
return null;
}
- private int findPosition( K key )
+ /**
+ * Find the element position in the array.
+ *
+ * @param key the key to find
+ * @return the position in the array, or -1 if not found
+ */
+ public int getPosition( K key )
+ {
+ if ( key == null )
+ {
+ return -1;
+ }
+
+ switch ( size )
+ {
+ case 0 :
+ return -1;
+
+ case 1 :
+ if ( comparator.compare( array[0], key ) == 0 )
+ {
+ return 0;
+ }
+ else
+ {
+ return -1;
+ }
+
+ case 2 :
+ if ( comparator.compare( array[0], key ) == 0 )
+ {
+ return 0;
+ }
+ else if ( comparator.compare( array[1], key ) == 0 )
+ {
+ return 1;
+ }
+ else
+ {
+ return -1;
+ }
+
+ 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 ) ;
+
+ if ( res == 0 )
+ {
+ return current;
+ }
+ else if ( res < 0 )
+ {
+ start = current;
+ current = (current + end + 1) >> 1;
+ }
+ else
+ {
+ end = current;
+ current = (current + start + 1) >> 1 ;
+ }
+ }
+
+ switch ( end - start + 1 )
+ {
+ case 1 :
+ if ( comparator.compare( array[start], key ) == 0 )
+ {
+ return start;
+ }
+ else
+ {
+ return -1;
+ }
+
+ case 2 :
+ if ( comparator.compare( array[start], key ) == 0 )
+ {
+ return start;
+ }
+ else if ( comparator.compare( array[end], key ) == 0 )
+ {
+ return end;
+ }
+ else
+ {
+ return -1;
+ }
+ }
+ }
+
+ return -1;
+ }
+
+
+ /**
+ * Find the element position in the array, or the position of the closest greater element in the array.
+ *
+ * @param key the key to find
+ * @return the position in the array, or -1 if not found
+ */
+ public int getAfterPosition( K key )
{
- if ( size == 0 )
+ if ( key == null )
{
return -1;
}
- int current = size >> 1;
- int end = size;
- int start = 0;
- int previousCurrent = -1;
+ switch ( size )
+ {
+ case 0 :
+ return -1;
+
+ case 1 :
+ if ( comparator.compare( array[0], key ) > 0 )
+ {
+ return 0;
+ }
+ else
+ {
+ return -1;
+ }
+
+ case 2 :
+ if ( comparator.compare( array[0], key ) > 0 )
+ {
+ return 0;
+ }
+
+ if ( comparator.compare( array[1], key ) > 0 )
+ {
+ return 1;
+ }
+ else
+ {
+ return -1;
+ }
+
+ 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 ) ;
+
+ if ( res == 0 )
+ {
+ if ( current != size - 1 )
+ {
+ return current + 1;
+ }
+ else
+ {
+ return -1;
+ }
+ }
+ else if ( res < 0 )
+ {
+ start = current;
+ current = (current + end + 1) >> 1;
+ }
+ else
+ {
+ end = current;
+ current = (current + start + 1) >> 1 ;
+ }
+ }
+
+ switch ( end - start + 1 )
+ {
+ case 1 :
+ if ( comparator.compare( array[start], key ) > 0 )
+ {
+ return start;
+ }
+ else
+ {
+ return -1;
+ }
+
+ 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;
+ }
+
+
+ /**
+ * Find the element position in the array, or the position of the closest greater element in the array.
+ *
+ * @param key the key to find
+ * @return the position in the array, or -1 if not found
+ */
+ public int getBeforePosition( K key )
+ {
+ if ( key == null )
+ {
+ return -1;
+ }
- while ( previousCurrent != current )
+ switch ( size )
{
- int res = comparator.compare( array[current], key ) ;
-
- if ( res == 0 )
- {
- position = current;
- return current;
- }
- else if ( res < 0 )
- {
- start = current;
- previousCurrent = current;
- current = (current + end ) >> 1;
- }
- else
- {
- end = current;
- previousCurrent = current;
- current = (current + start ) >> 1 ;
- }
+ case 0 :
+ return -1;
+
+ case 1 :
+ if ( comparator.compare( array[0], key ) < 0 )
+ {
+ return 0;
+ }
+ else
+ {
+ return -1;
+ }
+
+ case 2 :
+ if ( comparator.compare( array[1], key ) < 0 )
+ {
+ return 1;
+ }
+
+ if ( comparator.compare( array[0], key ) < 0 )
+ {
+ return 0;
+ }
+ else
+ {
+ return -1;
+ }
+
+ 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 ) ;
+
+ if ( res == 0 )
+ {
+ if ( current == 0 )
+ {
+ return -1;
+ }
+ else
+ {
+ return current - 1;
+ }
+ }
+ else if ( res < 0 )
+ {
+ start = current;
+ current = (current + end + 1) >> 1;
+ }
+ else
+ {
+ end = current;
+ current = (current + start + 1) >> 1 ;
+ }
+ }
+
+ switch ( end - start + 1 )
+ {
+ case 1 :
+ if ( comparator.compare( array[start], key ) < 0 )
+ {
+ return start;
+ }
+ else
+ {
+ return -1;
+ }
+
+ 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;
}
+
+
+ /**
+ * Tells if a key exist in the array.
+ *
+ * @param key The key to look for
+ * @return true if the key exist in the array
+ */
+ public boolean contains( K key )
+ {
+ return find( key ) != null;
+ }
/**
Modified: directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/ArrayTreeCursor.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/ArrayTreeCursor.java?rev=795286&r1=795285&r2=795286&view=diff
==============================================================================
--- directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/ArrayTreeCursor.java (original)
+++ directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree/ArrayTreeCursor.java Sat Jul 18 00:39:30 2009
@@ -47,6 +47,9 @@
/** A flag to tell if we are before the first node */
private boolean isBeforeFirst = true;
+
+ /** The current position in the array */
+ private int current;
/**
@@ -56,6 +59,7 @@
public ArrayTreeCursor( ArrayTree<K> array )
{
this.array = array;
+ current = -1;
}
@@ -72,18 +76,20 @@
return;
}
- K found = array.findGreater( element );
+ int found = array.getAfterPosition( element );
- if ( found == null )
+ if ( found == -1 )
{
- node = array.getLast();
- onNode = false;
- isAfterLast = true;
- isBeforeFirst = false;
+ // As the element has not been found, we move after the last
+ // position
+ afterLast();
return;
}
- node = found;
+ // The element has been found, we have to pick the node,
+ // set the current position, and update the flags.
+ current = found;
+ //node = array.get( current );
isAfterLast = false;
isBeforeFirst = false;
onNode = false;
@@ -96,6 +102,8 @@
public void afterLast() throws Exception
{
checkNotClosed( "afterLast" );
+
+ current = array.size() - 1;
node = array.getLast();
isBeforeFirst = false;
isAfterLast = true;
@@ -125,22 +133,21 @@
return;
}
- K found = array.findLess( element );
-
- if ( found == null )
- {
- node = array.getFirst();
- isAfterLast = false;
- isBeforeFirst = true;
- }
- else
+ int found = array.getBeforePosition( element );
+
+ // If the element has not been found, move to the
+ // first position
+ if ( found < 0 )
{
- node = found;
- isAfterLast = false;
- isBeforeFirst = false;
+ beforeFirst();
+ return;
}
- onNode = false;
+ current = found;
+ isAfterLast = false;
+ isBeforeFirst = false;
+ onNode = true;
+ node = array.get( current );
}
@@ -150,6 +157,8 @@
public void beforeFirst() throws Exception
{
checkNotClosed( "beforeFirst" );
+
+ current = 0;
node = array.getFirst();
isBeforeFirst = true;
isAfterLast = false;
@@ -164,6 +173,7 @@
{
checkNotClosed( "first" );
+ current = 0;
node = array.getFirst();
isBeforeFirst = false;
isAfterLast = false;
@@ -202,6 +212,8 @@
public boolean last() throws Exception
{
checkNotClosed( "last" );
+
+ current = array.size() - 1;
node = array.getLast();
isBeforeFirst = false;
isAfterLast = false;
@@ -216,28 +228,42 @@
{
checkNotClosed( "next" );
- if ( isAfterLast )
+ // If the array is empty, return false
+ if ( array.size() == 0 )
{
return false;
}
-
- if ( isBeforeFirst )
+
+ // If we are at the beginning
+ if ( isBeforeFirst )
{
+ current = 0;
node = array.getFirst();
isBeforeFirst = false;
isAfterLast = false;
onNode = node != null;
return onNode;
}
-
- node = array.getNext();
- onNode = node != null;
- if ( !onNode )
+ if ( isAfterLast )
+ {
+ return false;
+ }
+
+ if ( onNode )
{
- isAfterLast = true;
+ current++;
+
+ if ( current == array.size() )
+ {
+ afterLast();
+ return false;
+ }
}
+ node = array.get( current );
+ onNode = node != null;
+
return onNode;
}
@@ -248,7 +274,12 @@
public boolean previous() throws Exception
{
checkNotClosed( "previous" );
-
+
+ if ( array.size() == 0 )
+ {
+ return false;
+ }
+
if ( isBeforeFirst )
{
return false;
@@ -256,20 +287,27 @@
if ( isAfterLast )
{
+ current = array.size() - 1;
node = array.getLast();
isBeforeFirst = false;
isAfterLast = false;
return onNode = node != null;
}
- node = array.getPrevious();
- onNode = node != null;
-
- if ( !onNode )
+ if ( onNode )
{
- isBeforeFirst = true;
+ current--;
+
+ if ( current < 0 )
+ {
+ beforeFirst();
+ return false;
+ }
}
+ node = array.get( current );
+ onNode = node != null;
+
return onNode;
}
}