directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From elecha...@apache.org
Subject svn commit: r795286 - in /directory/apacheds/trunk/core-avl/src/main/java/org/apache/directory/server/core/avltree: ArrayMarshaller.java ArrayTree.java ArrayTreeCursor.java
Date Sat, 18 Jul 2009 00:39:31 GMT
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;
     }
 }



Mime
View raw message