directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From elecha...@apache.org
Subject svn commit: r1551251 - in /directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree: ./ memory/ persisted/
Date Mon, 16 Dec 2013 16:15:47 GMT
Author: elecharny
Date: Mon Dec 16 16:15:46 2013
New Revision: 1551251

URL: http://svn.apache.org/r1551251
Log:
Merged the various TupleCursor interface/abstract Class/classes into one single shared class

Added:
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/TupleCursor.java
      - copied, changed from r1551216, directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractTupleCursor.java
Removed:
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractTupleCursor.java
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/TupleCursorImpl.java
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/persisted/TupleCursorImpl.java
Modified:
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InMemoryLeaf.java
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/persisted/PersistedLeaf.java

Copied: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/TupleCursor.java
(from r1551216, directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractTupleCursor.java)
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/TupleCursor.java?p2=directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/TupleCursor.java&p1=directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractTupleCursor.java&r1=1551216&r2=1551251&rev=1551251&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractTupleCursor.java
(original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/TupleCursor.java
Mon Dec 16 16:15:46 2013
@@ -20,6 +20,9 @@
 package org.apache.directory.mavibot.btree;
 
 import java.io.IOException;
+import java.util.NoSuchElementException;
+
+import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
 
 
 /**
@@ -33,8 +36,14 @@ import java.io.IOException;
  * 
  * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
  */
-public abstract class AbstractTupleCursor<K, V> implements TupleCursor<K, V>
+public class TupleCursor<K, V>
 {
+    /** A marker to tell that we are before the first element */
+    private static final int BEFORE_FIRST = -1;
+    
+    /** A marker to tell that we are after the last element */
+    private static final int AFTER_LAST = -2;
+    
     /** The stack of pages from the root down to the leaf */
     protected ParentPos<K, V>[] stack;
     
@@ -53,7 +62,7 @@ public abstract class AbstractTupleCurso
      * @param transaction The transaction this operation is protected by
      * @param stack The stack of parent's from root to this page
      */
-    protected AbstractTupleCursor( Transaction<K, V> transaction, ParentPos<K, V>[]
stack, int depth )
+    public TupleCursor( Transaction<K, V> transaction, ParentPos<K, V>[] stack,
int depth )
     {
         this.transaction = transaction;
         this.stack = stack;
@@ -62,7 +71,7 @@ public abstract class AbstractTupleCurso
     
     
     /**
-     * {@inheritDoc}
+     * Change the position in the current cursor to set it after the last key
      */
     public void afterLast() throws IOException
     {
@@ -112,7 +121,7 @@ public abstract class AbstractTupleCurso
     
     
     /**
-     * {@inheritDoc}
+     * Change the position in the current cursor before the first key
      */
     public void beforeFirst() throws IOException
     {
@@ -155,6 +164,770 @@ public abstract class AbstractTupleCurso
 
 
     /**
+     * Tells if the cursor can return a next element
+     * 
+     * @return true if there are some more elements
+     * @throws IOException 
+     * @throws EndOfFileExceededException 
+     */
+    public boolean hasNext() throws EndOfFileExceededException, IOException
+    {
+        // First check that we have elements in the BTree
+        if ( ( stack == null ) || ( stack.length == 0 ) )
+        {
+            return false;
+        }
+        
+        // Take the leaf and check if we have no mare values
+        ParentPos<K, V> parentPos = stack[depth];
+
+        if ( parentPos.page == null )
+        {
+            // Empty BTree, get out
+            return false;
+        }
+
+        if ( parentPos.pos == AFTER_LAST )
+        {
+            return false;
+        }
+        
+        if ( parentPos.pos < parentPos.page.getNbElems() - 1 )
+        {
+            // Not the last position, we have a next value
+            return true;
+        }
+        else
+        {
+            // Check if we have some more value
+            if ( parentPos.valueCursor.hasNext() )
+            {
+                return true;
+            }
+            
+            // Ok, here, we have reached the last value in the leaf. We have to go up and

+            // see if we have some remaining values
+            int currentDepth = depth - 1;
+            
+            while ( currentDepth >= 0 )
+            {
+                parentPos = stack[currentDepth];
+                
+                if ( parentPos.pos < parentPos.page.getNbElems() )
+                {
+                    // The parent has some remaining values on the right, get out
+                    return true;
+                }
+                else
+                {
+                    currentDepth --;
+                }
+            }
+            
+            // We are done, there are no more value left
+            return false;
+        }
+    }
+
+
+    /**
+     * Find the next key/value
+     * 
+     * @return A Tuple containing the found key and value
+     * @throws IOException 
+     * @throws EndOfFileExceededException 
+     */
+    public Tuple<K, V> next() throws EndOfFileExceededException, IOException
+    {
+        // First check that we have elements in the BTree
+        if ( ( stack == null ) || ( stack.length == 0 ) )
+        {
+            throw new NoSuchElementException( "No tuple present" );
+        }
+
+        ParentPos<K, V> parentPos = stack[depth];
+
+        if ( ( parentPos.page == null ) || ( parentPos.pos == AFTER_LAST ) )
+        {
+            // This is the end : no more value
+            throw new NoSuchElementException( "No more tuples present" );
+        }
+
+        if ( parentPos.pos == parentPos.page.getNbElems() )
+        {
+            // End of the leaf. We have to go back into the stack up to the
+            // parent, and down to the leaf
+            parentPos = findNextParentPos();
+
+            // we also need to check for the type of page cause
+            // findNextParentPos will never return a null ParentPos
+            if ( ( parentPos == null ) || ( parentPos.page == null ) )
+            {
+                // This is the end : no more value
+                throw new NoSuchElementException( "No more tuples present" );
+            }
+        }
+
+        V value = null;
+        
+        if ( parentPos.valueCursor.hasNext() )
+        {
+            // Deal with the BeforeFirst case
+            if ( parentPos.pos == BEFORE_FIRST )
+            {
+                parentPos.pos++;
+            }
+            
+            value = parentPos.valueCursor.next();
+        }
+        else
+        {
+            if ( parentPos.pos == parentPos.page.getNbElems() - 1 )
+            {
+                parentPos = findNextParentPos();
+
+                if ( ( parentPos == null ) || ( parentPos.page == null ) )
+                {
+                    // This is the end : no more value
+                    throw new NoSuchElementException( "No more tuples present" );
+                }
+            }
+            else
+            {
+                parentPos.pos++;
+            }
+
+            try
+            {
+                ValueHolder<V> valueHolder = ( ( AbstractPage<K, V> ) parentPos.page
).getValue( parentPos.pos );
+                
+                parentPos.valueCursor = valueHolder.getCursor();
+                
+                value = parentPos.valueCursor.next();
+            }
+            catch ( IllegalArgumentException e )
+            {
+                e.printStackTrace();
+            }
+        }
+        
+        AbstractPage<K, V> leaf = ( AbstractPage<K, V> ) ( parentPos.page );
+        tuple.setKey( leaf.getKey( parentPos.pos ) );
+        tuple.setValue( value );
+
+        return tuple;
+    }
+
+
+    /**
+     * Get the next non-duplicate key.
+     * If the BTree contains :
+     * 
+     *  <ul>
+     *    <li><1,0></li>
+     *    <li><1,1></li>
+     *    <li><1,2></li>
+     *    <li><2,0></li>
+     *    <li><2,1></li>
+     *  </ul>
+     *   
+     *  and cursor is present at <1,1> then the returned tuple will be <2,0>
(not <1,2>)
+     *  
+     * @return A Tuple containing the found key and value
+     * @throws EndOfFileExceededException
+     * @throws IOException
+     */
+    public Tuple<K, V> nextKey() throws EndOfFileExceededException, IOException
+    {
+        // First check that we have elements in the BTree
+        if ( ( stack == null ) || ( stack.length == 0 ) )
+        {
+            // This is the end : no more value
+            throw new NoSuchElementException( "No more tuples present" );
+        }
+
+        ParentPos<K, V> parentPos = stack[depth];
+
+        if ( parentPos.page == null )
+        {
+            // This is the end : no more value
+            throw new NoSuchElementException( "No more tuples present" );
+        }
+
+        if ( parentPos.pos == ( parentPos.page.getNbElems() - 1 ) )
+        {
+            // End of the leaf. We have to go back into the stack up to the
+            // parent, and down to the next leaf
+            ParentPos<K, V> newParentPos = findNextParentPos();
+
+            // we also need to check the result of the call to
+            // findNextParentPos as it will return a null ParentPos
+            if ( ( newParentPos == null ) || ( newParentPos.page == null ) )
+            {
+                // This is the end : no more value
+                AbstractPage<K, V> leaf = ( AbstractPage<K, V> ) ( parentPos.page
);
+                ValueHolder<V> valueHolder = leaf.getValue( parentPos.pos );
+                parentPos.pos = AFTER_LAST;
+                parentPos.valueCursor = valueHolder.getCursor();
+                parentPos.valueCursor.afterLast();
+                
+                return null;
+            }
+            else
+            {
+                parentPos = newParentPos;
+            }
+        }
+        else
+        {
+            // Get the next key
+            parentPos.pos++;
+        }
+
+        // The key
+        AbstractPage<K, V> leaf = ( AbstractPage<K, V> ) ( parentPos.page );
+        tuple.setKey( leaf.getKey( parentPos.pos ) );
+        
+        // The value
+        ValueHolder<V> valueHolder = leaf.getValue( parentPos.pos );
+        parentPos.valueCursor = valueHolder.getCursor();
+        V value = parentPos.valueCursor.next();
+        tuple.setValue( value );
+
+        return tuple;
+    }
+
+
+    /**
+     * Tells if the cursor can return a next key
+     * 
+     * @return true if there are some more keys
+     * @throws IOException 
+     * @throws EndOfFileExceededException 
+     */
+    public boolean hasNextKey() throws EndOfFileExceededException, IOException
+    {
+        // First check that we have elements in the BTree
+        if ( ( stack == null ) || ( stack.length == 0 ) )
+        {
+            // This is the end : no more key
+            return false;
+        }
+
+        ParentPos<K, V> parentPos = stack[depth];
+
+        if ( parentPos.page == null )
+        {
+            // This is the end : no more key
+            return false;
+        }
+        
+        if ( parentPos.pos == ( parentPos.page.getNbElems() - 1 ) )
+        {
+            // End of the leaf. We have to go back into the stack up to the
+            // parent, and down to the next leaf
+            return hasNextParentPos();
+        }
+        else
+        {
+            return true;
+        }
+    }
+
+
+    /**
+     * Tells if the cursor can return a previous element
+     * 
+     * @return true if there are some more elements
+     * @throws IOException 
+     * @throws EndOfFileExceededException 
+     */
+    public boolean hasPrev() throws EndOfFileExceededException, IOException
+    {
+        // First check that we have elements in the BTree
+        if ( ( stack == null ) || ( stack.length == 0 ) )
+        {
+            return false;
+        }
+
+        // Take the leaf and check if we have no mare values
+        ParentPos<K, V> parentPos = stack[depth];
+
+        if ( parentPos.page == null )
+        {
+            // Empty BTree, get out
+            return false;
+        }
+
+        if ( parentPos.pos > 0 )
+        {
+            // get out, we have values on the left
+            return true;
+        }
+        else
+        {
+            // Check that we are not before the first value
+            if ( parentPos.pos == BEFORE_FIRST )
+            {
+                return false;
+            }
+            
+            // Check if we have some more value
+            if ( parentPos.valueCursor.hasPrev() )
+            {
+                return true;
+            }
+
+            // Ok, here, we have reached the first value in the leaf. We have to go up and

+            // see if we have some remaining values
+            int currentDepth = depth - 1;
+            
+            while ( currentDepth >= 0 )
+            {
+                parentPos = stack[currentDepth];
+                
+                if ( parentPos.pos > 0 )
+                {
+                    // The parent has some remaining values on the right, get out
+                    return true;
+                }
+                else
+                {
+                    currentDepth --;
+                }
+            }
+            
+            return false;
+        }
+    }
+
+
+    /**
+     * Find the previous key/value
+     * 
+     * @return A Tuple containing the found key and value
+     * @throws IOException 
+     * @throws EndOfFileExceededException 
+     */
+    public Tuple<K, V> prev() throws EndOfFileExceededException, IOException
+    {
+        // First check that we have elements in the BTree
+        if ( ( stack == null ) || ( stack.length == 0 ) )
+        {
+            throw new NoSuchElementException( "No more tuple present" );
+        }
+
+        ParentPos<K, V> parentPos = stack[depth];
+
+        if ( ( parentPos.page == null ) || ( parentPos.pos == BEFORE_FIRST ) )
+        {
+            // This is the end : no more value
+            throw new NoSuchElementException( "No more tuples present" );
+        }
+
+        if ( ( parentPos.pos == 0 ) && ( !parentPos.valueCursor.hasPrev() ) )
+        {
+            // End of the leaf. We have to go back into the stack up to the
+            // parent, and down to the leaf
+            parentPos = findPrevParentPos();
+
+            // we also need to check for the type of page cause
+            // findPrevParentPos will never return a null ParentPos
+            if ( ( parentPos == null ) || ( parentPos.page == null ) )
+            {
+                // This is the end : no more value
+                throw new NoSuchElementException( "No more tuples present" );
+            }
+        }
+        
+        V value = null;
+        
+        if ( parentPos.valueCursor.hasPrev() )
+        {
+            // Deal with the AfterLast case
+            if ( parentPos.pos == AFTER_LAST )
+            {
+                parentPos.pos = parentPos.page.getNbElems() - 1;
+            }
+            
+            value = parentPos.valueCursor.prev();
+        }
+        else
+        {
+            if ( parentPos.pos == 0 )
+            {
+                parentPos = findPrevParentPos();
+
+                if ( ( parentPos == null ) || ( parentPos.page == null ) )
+                {
+                    // This is the end : no more value
+                    throw new NoSuchElementException( "No more tuples present" );
+                }
+            }
+            else
+            {
+                parentPos.pos--;
+                
+                try
+                {
+                    ValueHolder<V> valueHolder = ( ( AbstractPage<K, V> ) parentPos.page
).getValue( parentPos.pos );
+                    
+                    parentPos.valueCursor = valueHolder.getCursor();
+                    parentPos.valueCursor.afterLast();
+                    
+                    value = parentPos.valueCursor.prev();
+                }
+                catch ( IllegalArgumentException e )
+                {
+                    e.printStackTrace();
+                }
+            }
+        }
+
+
+        AbstractPage<K, V> leaf = ( AbstractPage<K, V> ) ( parentPos.page );
+        tuple.setKey( leaf.getKey( parentPos.pos ) );
+        tuple.setValue( value );
+
+        return tuple;
+    }
+
+
+    /**
+     * Get the previous non-duplicate key.
+     * If the BTree contains :
+     * 
+     *  <ul>
+     *    <li><1,0></li>
+     *    <li><1,1></li>
+     *    <li><1,2></li>
+     *    <li><2,0></li>
+     *    <li><2,1></li>
+     *  </ul>
+     *   
+     *  and cursor is present at <2,1> then the returned tuple will be <1,0>
(not <2,0>)
+     *  
+     * @return A Tuple containing the found key and value
+     * @throws EndOfFileExceededException
+     * @throws IOException
+     */
+    public Tuple<K, V> prevKey() throws EndOfFileExceededException, IOException
+    {
+        // First check that we have elements in the BTree
+        if ( ( stack == null ) || ( stack.length == 0 ) )
+        {
+            // This is the end : no more value
+            throw new NoSuchElementException( "No more tuples present" );
+        }
+
+        ParentPos<K, V> parentPos = stack[depth];
+
+        if ( parentPos.page == null )
+        {
+            // This is the end : no more value
+            throw new NoSuchElementException( "No more tuples present" );
+        }
+
+        if ( parentPos.pos == 0 )
+        {
+            // Beginning of the leaf. We have to go back into the stack up to the
+            // parent, and down to the leaf
+            parentPos = findPrevParentPos();
+
+            if ( ( parentPos == null ) || ( parentPos.page == null ) )
+            {
+                // This is the end : no more value
+                throw new NoSuchElementException( "No more tuples present" );
+            }
+        }
+        else
+        {
+            if ( parentPos.pos == AFTER_LAST )
+            {
+                parentPos.pos = parentPos.page.getNbElems() - 1;
+            }
+            else
+            {
+                parentPos.pos--;
+            }
+        }
+        
+        // Update the Tuple 
+        AbstractPage<K, V> leaf = ( AbstractPage<K, V> ) ( parentPos.page );
+
+        // The key
+        tuple.setKey( leaf.getKey( parentPos.pos ) );
+
+        // The value
+        ValueHolder<V> valueHolder = leaf.getValue( parentPos.pos );
+        parentPos.valueCursor = valueHolder.getCursor();
+        V value = parentPos.valueCursor.next();
+        tuple.setValue( value );
+        
+        return tuple;
+    }
+
+
+    /**
+     * Tells if the cursor can return a previous key
+     * 
+     * @return true if there are some more keys
+     * @throws IOException 
+     * @throws EndOfFileExceededException 
+     */
+    public boolean hasPrevKey() throws EndOfFileExceededException, IOException
+    {
+        // First check that we have elements in the BTree
+        if ( ( stack == null ) || ( stack.length == 0 ) )
+        {
+            // This is the end : no more key
+            return false;
+        }
+
+        ParentPos<K, V> parentPos = stack[depth];
+
+        if ( parentPos.page == null )
+        {
+            // This is the end : no more key
+            return false;
+        }
+        
+        if ( parentPos.pos == 0 )
+        {
+            // Beginning of the leaf. We have to go back into the stack up to the
+            // parent, and down to the leaf
+            return hasPrevParentPos();
+        }
+        else
+        {
+            return true;
+        }
+    }
+
+
+    /**
+     * Tells if there is a next ParentPos
+     * 
+     * @return the new ParentPos instance, or null if we have no following leaf
+     * @throws IOException 
+     * @throws EndOfFileExceededException 
+     */
+    private boolean hasNextParentPos() throws EndOfFileExceededException, IOException
+    {
+        if ( depth == 0 )
+        {
+            // No need to go any further, there is only one leaf in the btree
+            return false;
+        }
+
+        int currentDepth = depth - 1;
+        Page<K, V> child = null;
+
+        // First, go up the tree until we find a Node which has some element on the right
+        while ( currentDepth >= 0 )
+        {
+            // We first go up the tree, until we reach a page whose current position
+            // is not the last one
+            ParentPos<K, V> parentPos = stack[currentDepth];
+
+            if ( parentPos.pos + 1 > parentPos.page.getNbElems() )
+            {
+                // No more element on the right : go up
+                currentDepth--;
+            }
+            else
+            {
+                // We can pick the next element at this level
+                child = ((AbstractPage<K, V>)parentPos.page).getPage( parentPos.pos
+ 1 );
+                
+                // and go down the tree through the nodes
+                while ( currentDepth < depth - 1 )
+                {
+                    currentDepth++;
+                    child = ((AbstractPage<K, V>)child).getPage( 0 );
+                }
+
+                return true;
+            }
+        }
+
+        return false;
+    }
+    
+    
+    /**
+     * Find the leaf containing the following elements.
+     * 
+     * @return the new ParentPos instance, or null if we have no following leaf
+     * @throws IOException 
+     * @throws EndOfFileExceededException 
+     */
+    private ParentPos<K, V> findNextParentPos() throws EndOfFileExceededException,
IOException
+    {
+        if ( depth == 0 )
+        {
+            // No need to go any further, there is only one leaf in the btree
+            return null;
+        }
+
+        int currentDepth = depth - 1;
+        Page<K, V> child = null;
+
+        // First, go up the tree until we find a Node which has some element on the right
+        while ( currentDepth >= 0 )
+        {
+            // We first go up the tree, until we reach a page whose current position
+            // is not the last one
+            ParentPos<K, V> parentPos = stack[currentDepth];
+
+            if ( parentPos.pos + 1 > parentPos.page.getNbElems() )
+            {
+                // No more element on the right : go up
+                currentDepth--;
+            }
+            else
+            {
+                // We can pick the next element at this level
+                parentPos.pos++;
+                child = ((AbstractPage<K, V>)parentPos.page).getPage( parentPos.pos
);
+                
+                // and go down the tree through the nodes
+                while ( currentDepth < depth - 1 )
+                {
+                    currentDepth++;
+                    parentPos = stack[currentDepth];
+                    parentPos.pos = 0;
+                    parentPos.page = child;
+                    child = ((AbstractPage<K, V>)child).getPage( 0 );
+                }
+
+                // and the leaf
+                parentPos = stack[depth];
+                parentPos.page = child;
+                parentPos.pos = 0;
+                parentPos.valueCursor = ((AbstractPage<K, V>)child).getValue( 0 ).getCursor();
+
+                return parentPos;
+            }
+        }
+
+        return null;
+    }
+    
+    
+    /**
+     * Find the leaf containing the previous elements.
+     * 
+     * @return the new ParentPos instance, or null if we have no previous leaf
+     * @throws IOException 
+     * @throws EndOfFileExceededException 
+     */
+    private ParentPos<K, V> findPrevParentPos() throws EndOfFileExceededException,
IOException
+    {
+        if ( depth == 0 )
+        {
+            // No need to go any further, there is only one leaf in the btree
+            return null;
+        }
+
+        int currentDepth = depth - 1;
+        Page<K, V> child = null;
+
+        // First, go up the tree until we find a Node which has some element on the left
+        while ( currentDepth >= 0 )
+        {
+            // We first go up the tree, until we reach a page whose current position
+            // is not the last one
+            ParentPos<K, V> parentPos = stack[currentDepth];
+
+            if ( parentPos.pos == 0 )
+            {
+                // No more element on the right : go up
+                currentDepth--;
+            }
+            else
+            {
+                // We can pick the next element at this level
+                parentPos.pos--;
+                child = ((AbstractPage<K, V>)parentPos.page).getPage( parentPos.pos
);
+                
+                // and go down the tree through the nodes
+                while ( currentDepth < depth - 1 )
+                {
+                    currentDepth++;
+                    parentPos = stack[currentDepth];
+                    parentPos.pos = child.getNbElems();
+                    parentPos.page = child;
+                    child = ((AbstractPage<K, V>)parentPos.page).getPage( parentPos.page.getNbElems()
);
+                }
+
+                // and the leaf
+                parentPos = stack[depth];
+                parentPos.pos = child.getNbElems() - 1;
+                parentPos.page = child;
+                ValueHolder<V> valueHolder = ((AbstractPage<K, V>)parentPos.page).getValue(
parentPos.pos );
+                parentPos.valueCursor = valueHolder.getCursor();
+                parentPos.valueCursor.afterLast();
+
+                return parentPos;
+            }
+        }
+        
+        return null;
+    }
+
+    
+    /**
+     * Tells if there is a prev ParentPos
+     * 
+     * @return the new ParentPos instance, or null if we have no previous leaf
+     * @throws IOException 
+     * @throws EndOfFileExceededException 
+     */
+    private boolean hasPrevParentPos() throws EndOfFileExceededException, IOException
+    {
+        if ( depth == 0 )
+        {
+            // No need to go any further, there is only one leaf in the btree
+            return false;
+        }
+
+        int currentDepth = depth - 1;
+        Page<K, V> child = null;
+
+        // First, go up the tree until we find a Node which has some element on the right
+        while ( currentDepth >= 0 )
+        {
+            // We first go up the tree, until we reach a page whose current position
+            // is not the last one
+            ParentPos<K, V> parentPos = stack[currentDepth];
+
+            if ( parentPos.pos == 0 )
+            {
+                // No more element on the left : go up
+                currentDepth--;
+            }
+            else
+            {
+                // We can pick the previous element at this level
+                child = ((AbstractPage<K, V>)parentPos.page).getPage( parentPos.pos
- 1 );
+                
+                // and go down the tree through the nodes
+                while ( currentDepth < depth - 1 )
+                {
+                    currentDepth++;
+                    child = ((AbstractPage<K, V>)child).getPage( child.getNbElems()
);
+                }
+
+                return true;
+            }
+        }
+
+        return false;
+    }
+
+
+    /**
      * {@inheritDoc}
      */
     public void close()
@@ -164,7 +937,8 @@ public abstract class AbstractTupleCurso
 
 
     /**
-     * {@inheritDoc}
+     * Get the creation date
+     * @return The creation date for this cursor
      */
     public long getCreationDate()
     {
@@ -173,7 +947,9 @@ public abstract class AbstractTupleCurso
 
 
     /**
-     * {@inheritDoc}
+     * Get the current revision
+     * 
+     * @return The revision this cursor is based on
      */
     public long getRevision()
     {

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InMemoryLeaf.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InMemoryLeaf.java?rev=1551251&r1=1551250&r2=1551251&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InMemoryLeaf.java
(original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InMemoryLeaf.java
Mon Dec 16 16:15:46 2013
@@ -24,6 +24,7 @@ import java.io.IOException;
 import java.lang.reflect.Array;
 
 import org.apache.directory.mavibot.btree.AbstractPage;
+import org.apache.directory.mavibot.btree.TupleCursor;
 import org.apache.directory.mavibot.btree.BTree;
 import org.apache.directory.mavibot.btree.BorrowedFromLeftResult;
 import org.apache.directory.mavibot.btree.BorrowedFromRightResult;
@@ -612,7 +613,7 @@ import org.apache.directory.mavibot.btre
 
             stack[depth] = parentPos;
 
-            cursor = new TupleCursorImpl<K, V>( transaction, stack, depth );
+            cursor = new TupleCursor<K, V>( transaction, stack, depth );
         }
         else
         {
@@ -626,7 +627,7 @@ import org.apache.directory.mavibot.btre
                 
                 stack[depth] = parentPos;
 
-                cursor = new TupleCursorImpl<K, V>( transaction, stack, depth );
+                cursor = new TupleCursor<K, V>( transaction, stack, depth );
             }
             else if ( nbElems > 0 )
             {
@@ -638,7 +639,7 @@ import org.apache.directory.mavibot.btre
                 
                 stack[depth] = parentPos;
 
-                cursor = new TupleCursorImpl<K, V>( transaction, stack, depth );
+                cursor = new TupleCursor<K, V>( transaction, stack, depth );
                 
                 try
                 {
@@ -655,7 +656,7 @@ import org.apache.directory.mavibot.btre
                 // Not found, because there are no elements : return a null cursor
                 stack[depth] = null;
 
-                cursor = new TupleCursorImpl<K, V>( transaction, null, 0 );
+                cursor = new TupleCursor<K, V>( transaction, null, 0 );
             }
         }
 
@@ -676,7 +677,7 @@ import org.apache.directory.mavibot.btre
             // The tree is empty, it's the root, we have nothing to return
             stack[depth] = new ParentPos<K, V>( null, -1 );
 
-            return new TupleCursorImpl<K, V>( transaction, stack, depth );
+            return new TupleCursor<K, V>( transaction, stack, depth );
         }
         else
         {
@@ -688,7 +689,7 @@ import org.apache.directory.mavibot.btre
 
             stack[depth] = parentPos;
 
-            cursor = new TupleCursorImpl<K, V>( transaction, stack, depth );
+            cursor = new TupleCursor<K, V>( transaction, stack, depth );
         }
 
         return cursor;

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/persisted/PersistedLeaf.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/persisted/PersistedLeaf.java?rev=1551251&r1=1551250&r2=1551251&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/persisted/PersistedLeaf.java
(original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/persisted/PersistedLeaf.java
Mon Dec 16 16:15:46 2013
@@ -24,6 +24,7 @@ import java.io.IOException;
 import java.lang.reflect.Array;
 
 import org.apache.directory.mavibot.btree.AbstractPage;
+import org.apache.directory.mavibot.btree.TupleCursor;
 import org.apache.directory.mavibot.btree.BTree;
 import org.apache.directory.mavibot.btree.BorrowedFromLeftResult;
 import org.apache.directory.mavibot.btree.BorrowedFromRightResult;
@@ -660,7 +661,7 @@ import org.apache.directory.mavibot.btre
 
             stack[depth] = parentPos;
 
-            cursor = new TupleCursorImpl<K, V>( btree, transaction, stack, depth );
+            cursor = new TupleCursor<K, V>( transaction, stack, depth );
         }
         else
         {
@@ -674,7 +675,7 @@ import org.apache.directory.mavibot.btre
 
                 stack[depth] = parentPos;
 
-                cursor = new TupleCursorImpl<K, V>( btree, transaction, stack, depth
);
+                cursor = new TupleCursor<K, V>( transaction, stack, depth );
             }
             else if ( nbElems > 0 )
             {
@@ -686,7 +687,7 @@ import org.apache.directory.mavibot.btre
                 
                 stack[depth] = parentPos;
 
-                cursor = new TupleCursorImpl<K, V>( btree, transaction, stack, depth
);
+                cursor = new TupleCursor<K, V>( transaction, stack, depth );
                 
                 try
                 {
@@ -703,7 +704,7 @@ import org.apache.directory.mavibot.btre
                 // Not found, because there are no elements : return a null cursor
                 stack[depth] = null;
 
-                cursor = new TupleCursorImpl<K, V>( btree, transaction, null, 0 );
+                cursor = new TupleCursor<K, V>( transaction, null, 0 );
             }
         }
 
@@ -724,7 +725,7 @@ import org.apache.directory.mavibot.btre
             // The tree is empty, it's the root, we have nothing to return
             stack[depth] = new ParentPos<K, V>( null, -1 );
 
-            return new TupleCursorImpl<K, V>( btree, transaction, stack, depth );
+            return new TupleCursor<K, V>( transaction, stack, depth );
         }
         else
         {
@@ -736,7 +737,7 @@ import org.apache.directory.mavibot.btre
 
             stack[depth] = parentPos;
 
-            cursor = new TupleCursorImpl<K, V>( btree, transaction, stack, depth );
+            cursor = new TupleCursor<K, V>( transaction, stack, depth );
         }
 
         return cursor;



Mime
View raw message