directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From elecha...@apache.org
Subject svn commit: r1549961 [2/3] - in /directory/mavibot/trunk/mavibot/src: main/java/org/apache/directory/mavibot/btree/ main/java/org/apache/directory/mavibot/btree/managed/ main/java/org/apache/directory/mavibot/btree/memory/ test/java/org/apache/director...
Date Tue, 10 Dec 2013 20:42:17 GMT
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Leaf.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Leaf.java?rev=1549961&r1=1549960&r2=1549961&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Leaf.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Leaf.java Tue Dec 10 20:42:16 2013
@@ -20,13 +20,17 @@
 package org.apache.directory.mavibot.btree.memory;
 
 
-import static org.apache.directory.mavibot.btree.memory.InternalUtil.setDupsContainer;
-
 import java.io.IOException;
 import java.lang.reflect.Array;
 
+import org.apache.directory.mavibot.btree.DeleteResult;
+import org.apache.directory.mavibot.btree.InsertResult;
+import org.apache.directory.mavibot.btree.Page;
+import org.apache.directory.mavibot.btree.ParentPos;
+import org.apache.directory.mavibot.btree.Transaction;
 import org.apache.directory.mavibot.btree.Tuple;
 import org.apache.directory.mavibot.btree.TupleCursor;
+import org.apache.directory.mavibot.btree.ValueCursor;
 import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
 import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
 
@@ -42,7 +46,7 @@ import org.apache.directory.mavibot.btre
 /* No qualifier */class Leaf<K, V> extends AbstractPage<K, V>
 {
     /** Values associated with keys */
-    protected ElementHolder<V, K, V>[] values;
+    protected ValueHolder<V>[] values;
 
 
     /**
@@ -69,15 +73,7 @@ import org.apache.directory.mavibot.btre
     {
         super( btree, revision, nbElems );
 
-        if ( btree.isAllowDuplicates() )
-        {
-            this.values = ( MultipleMemoryHolder<K, V>[] ) Array.newInstance( MultipleMemoryHolder.class,
-                nbElems );
-        }
-        else
-        {
-            this.values = ( MemoryHolder<K, V>[] ) Array.newInstance( MemoryHolder.class, nbElems );
-        }
+        this.values = ( ValueHolder<V>[] ) Array.newInstance( ValueHolder.class, nbElems );
     }
 
 
@@ -156,81 +152,35 @@ import org.apache.directory.mavibot.btre
 
         int index = -( pos + 1 );
 
-        if ( btree.isAllowDuplicates() )
-        {
-            MultipleMemoryHolder<K, V> mvHolder = ( MultipleMemoryHolder<K, V> ) values[index];
-
-            //FIXME should the internal sub-tree should be deleted from RM?
-
-            V existingVal = mvHolder.getValue();
+        ValueHolder<V> valueHolder = values[index];
 
-            if ( value == null ) // this is a case to delete entire <K,sub-BTree> or <K,single-V>
-            {
-                removedElement = new Tuple<K, V>( keys[index], existingVal ); // the entire value was removed
-                keyRemoved = true;
-            }
-            else
+        if ( value == null )
+        {
+            // we have to delete the whole value
+            removedElement = new Tuple<K, V>( keys[index], valueHolder.getCursor().next() ); // the entire value was removed
+            keyRemoved = true;
+        }
+        else
+        {
+            if ( valueHolder.contains( value ) )
             {
-                if ( mvHolder.isSingleValue() )
+                // this is a case to delete entire <K,sub-BTree> or <K,single-V>
+                if ( valueHolder.size() == 1 ) 
                 {
-                    if ( btree.getValueSerializer().compare( value, existingVal ) == 0 )
-                    {
-                        removedElement = new Tuple<K, V>( keys[index], existingVal ); // the entire value was removed
-                        keyRemoved = true;
-                    }
-                    else
-                    // value is not found
-                    {
-                        return NotPresentResult.NOT_PRESENT;
-                    }
+                    // Ok, we can remove the value
+                    removedElement = new Tuple<K, V>( keys[index], null ); // the entire value was removed
+                    keyRemoved = true;
                 }
                 else
                 {
-                    BTree<V, V> dups = ( BTree<V, V> ) existingVal;
-
-                    if ( dups.hasKey( value ) )
-                    {
-                        dups.delete( value );
-
-                        if ( dups.getNbElems() == 0 )
-                        {
-                            keyRemoved = true;
-                        }
-                        else
-                        {
-                            if ( dups.getNbElems() == 1 )
-                            {
-                                //FIXME switch to single value mode
-                                mvHolder.switchToSingleValMode();
-                            }
-                        }
-
-                        removedElement = new Tuple<K, V>( keys[index], value ); // we deleted only one value (even if it is from a tree of size 1)
-                    }
-                    else
-                    // value is not found
-                    {
-                        return NotPresentResult.NOT_PRESENT;
-                    }
+                    // Update the ValueHolder
+                    valueHolder.remove( value );
+                    removedElement = new Tuple<K, V>( keys[index], value ); // the entire value was removed
                 }
             }
-        }
-        else
-        {
-            V existing = values[index].getValue();
-
-            if ( ( ( existing == null ) && ( value == null ) ) || ( value == null ) )
-            {
-                removedElement = new Tuple<K, V>( keys[index], existing );
-                keyRemoved = true;
-            }
-            else if ( btree.getValueSerializer().compare( value, existing ) == 0 )
-            {
-                removedElement = new Tuple<K, V>( keys[index], value );
-                keyRemoved = true;
-            }
             else
             {
+                // Not found
                 return NotPresentResult.NOT_PRESENT;
             }
         }
@@ -273,7 +223,7 @@ import org.apache.directory.mavibot.btre
                 // Check in both next and previous page, if they have the same parent
                 // and select the biggest page with the same parent to borrow an element.
                 int siblingPos = selectSibling( ( Node<K, V> ) parent, parentPos );
-                Leaf<K, V> sibling = ( Leaf<K, V> ) ( ( ( Node<K, V> ) parent ).children[siblingPos].getValue() );
+                Leaf<K, V> sibling = ( Leaf<K, V> ) ( ( ( Node<K, V> ) parent ).children[siblingPos] );
 
                 if ( sibling.getNbElems() == halfSize )
                 {
@@ -406,7 +356,7 @@ import org.apache.directory.mavibot.btre
     {
         // The sibling is on the left, borrow the rightmost element
         K siblingKey = sibling.keys[sibling.getNbElems() - 1];
-        ElementHolder<V, K, V> siblingValue = sibling.values[sibling.getNbElems() - 1];
+        ValueHolder<V> siblingValue = sibling.values[sibling.getNbElems() - 1];
 
         // Create the new sibling, with one less element at the end
         Leaf<K, V> newSibling = ( Leaf<K, V> ) sibling.copy( revision, sibling.getNbElems() - 1 );
@@ -453,7 +403,7 @@ import org.apache.directory.mavibot.btre
     {
         // The sibling is on the left, borrow the rightmost element
         K siblingKey = sibling.keys[0];
-        ElementHolder<V, K, V> siblingHolder = sibling.values[0];
+        ValueHolder<V> siblingHolder = sibling.values[0];
 
         // Create the new sibling
         Leaf<K, V> newSibling = new Leaf<K, V>( btree, revision, sibling.getNbElems() - 1 );
@@ -533,24 +483,11 @@ import org.apache.directory.mavibot.btre
 
         if ( pos < 0 )
         {
-            if ( btree.isAllowDuplicates() )
-            {
-                MultipleMemoryHolder<K, V> mvHolder = ( MultipleMemoryHolder<K, V> ) values[-( pos + 1 )];
-                if ( mvHolder.isSingleValue() )
-                {
-                    return mvHolder.getValue();
-                }
-                else
-                {
-                    // always return the first value for get(key) when duplicates are allowed
-                    BTree<V, V> dupTree = ( BTree<V, V> ) mvHolder.getValue();
-                    return dupTree.rootPage.getLeftMostKey();
-                }
-            }
-
-            V v = values[-( pos + 1 )].getValue();
-
-            return v;
+            ValueHolder<V> valueHolder = ( ValueHolder<V> ) values[-( pos + 1 )];
+            
+            V value = valueHolder.getCursor().next();
+            
+            return value;
         }
         else
         {
@@ -563,7 +500,7 @@ import org.apache.directory.mavibot.btre
      * {@inheritDoc}
      */
     @Override
-    public DuplicateKeyVal<V> getValues( K key ) throws KeyNotFoundException, IOException, IllegalArgumentException
+    public ValueCursor<V> getValues( K key ) throws KeyNotFoundException, IOException, IllegalArgumentException
     {
         if ( !btree.isAllowDuplicates() )
         {
@@ -574,14 +511,9 @@ import org.apache.directory.mavibot.btre
 
         if ( pos < 0 )
         {
-            MultipleMemoryHolder<K, V> mvHolder = ( MultipleMemoryHolder<K, V> ) values[-( pos + 1 )];
-
-            if ( mvHolder.isSingleValue() )
-            {
-                return new DuplicateKeyVal<V>( mvHolder.getValue() );
-            }
+            ValueHolder<V> valueHolder = ( ValueHolder<V> ) values[-( pos + 1 )];
 
-            return new DuplicateKeyVal<V>( ( BTree<V, V> ) mvHolder.getValue() );
+            return valueHolder.getCursor();
         }
         else
         {
@@ -613,25 +545,9 @@ import org.apache.directory.mavibot.btre
 
         if ( pos < 0 )
         {
-            if ( btree.isAllowDuplicates() )
-            {
-                MultipleMemoryHolder<K, V> mvHolder = ( MultipleMemoryHolder<K, V> ) values[-( pos + 1 )];
-                if ( mvHolder.isSingleValue() )
-                {
-                    return ( btree.getValueSerializer().compare( value, mvHolder.getValue() ) == 0 );
-                }
-                else
-                {
-                    // always return the first value for get(key) when duplicates are allowed
-                    BTree<V, V> dupTree = ( ( BTree<V, V> ) mvHolder.getValue() );
-                    return dupTree.hasKey( value );
-                }
-            }
-            else
-            {
-                V v = values[-( pos + 1 )].getValue();
-                return ( btree.getValueSerializer().compare( value, v ) == 0 );
-            }
+            ValueHolder<V> valueHolder = values[-( pos + 1 )];
+            
+            return valueHolder.contains( value );
         }
         else
         {
@@ -643,7 +559,7 @@ import org.apache.directory.mavibot.btre
     /**
      * {@inheritDoc}
      */
-    public ElementHolder<V, K, V> getValue( int pos )
+    public ValueHolder<V> getValue( int pos )
     {
         if ( pos < nbElems )
         {
@@ -661,7 +577,7 @@ import org.apache.directory.mavibot.btre
      * @param pos The position in the values array
      * @param value the value to inject
      */
-    public void setValue( int pos, ElementHolder<V, K, V> value )
+    public void setValue( int pos, ValueHolder<V> value )
     {
         values[pos] = value;
     }
@@ -677,11 +593,14 @@ import org.apache.directory.mavibot.btre
 
         if ( pos < 0 )
         {
-            int index = -( pos + 1 );
+            pos = -( pos + 1 );
+
+            // Start at the beginning of the page
+            ParentPos<K, V> parentPos = new ParentPos<K, V>( this, pos );
+            
+            // Create the value cursor
+            parentPos.valueCursor = values[pos].getCursor();
 
-            // The first element has been found. Create the cursor
-            ParentPos<K, V> parentPos = new ParentPos<K, V>( this, index );
-            setDupsContainer( parentPos, btree );
             stack[depth] = parentPos;
 
             cursor = new TupleCursorImpl<K, V>( btree, transaction, stack, depth );
@@ -692,18 +611,42 @@ import org.apache.directory.mavibot.btre
             if ( pos < nbElems )
             {
                 ParentPos<K, V> parentPos = new ParentPos<K, V>( this, pos );
-                setDupsContainer( parentPos, btree );
+
+                // Create the value cursor
+                parentPos.valueCursor = values[pos].getCursor();
+                
                 stack[depth] = parentPos;
 
                 cursor = new TupleCursorImpl<K, V>( btree, transaction, stack, depth );
             }
-            else
+            else if ( nbElems > 0 )
             {
-                // Not found : return a null cursor
-                ParentPos<K, V> parentPos = new ParentPos<K, V>( null, -1 );
+                // after the last element
+                ParentPos<K, V> parentPos = new ParentPos<K, V>( this, nbElems - 1 );
+
+                // Create the value cursor
+                parentPos.valueCursor = values[nbElems - 1].getCursor();
+                
                 stack[depth] = parentPos;
 
-                return new TupleCursorImpl<K, V>( btree, transaction, stack, depth );
+                cursor = new TupleCursorImpl<K, V>( btree, transaction, stack, depth );
+                
+                try
+                {
+                    cursor.afterLast();
+                }
+                catch ( IOException e )
+                {
+                    // TODO Auto-generated catch block
+                    e.printStackTrace();
+                }
+            }
+            else
+            {
+                // Not found, because there are no elements : return a null cursor
+                stack[depth] = null;
+
+                cursor = new TupleCursorImpl<K, V>( btree, transaction, null, 0 );
             }
         }
 
@@ -731,7 +674,8 @@ import org.apache.directory.mavibot.btre
             // Start at the beginning of the page
             ParentPos<K, V> parentPos = new ParentPos<K, V>( this, pos );
 
-            setDupsContainer( parentPos, btree );
+            // Create the value cursor
+            parentPos.valueCursor = values[0].getCursor();
 
             stack[depth] = parentPos;
 
@@ -782,54 +726,26 @@ import org.apache.directory.mavibot.btre
             newLeaf = ( Leaf<K, V> ) copy( revision, nbElems );
         }
 
-        V oldValue = null;
+        // Get the previous value from the leaf (it's a copy)
+        ValueHolder<V> valueHolder = newLeaf.values[pos];
+        V replacedValue = null;
 
-        if ( btree.isAllowDuplicates() )
+        if ( !valueHolder.contains( value ) )
         {
-            MultipleMemoryHolder<K, V> mvHolder = ( MultipleMemoryHolder<K, V> ) newLeaf.values[pos];
-
-            if ( mvHolder.isSingleValue() )
-            {
-                V singleVal = mvHolder.getValue();
-
-                // see if the given value already matches
-                if ( btree.getValueSerializer().compare( value, singleVal ) == 0 )
-                {
-                    oldValue = value;
-                }
-                else
-                // create a sub-tree
-                {
-                    mvHolder.createAndSwitchToSubTree();
-                }
-            }
-
-            // if oldValue is null then the given 'value' is different and needs to be added
-            // ('oldValue' will be not null if it matched with the 'singleValue', see above nested if block )
-            if ( oldValue == null )
-            {
-                BTree<V, V> dupValues = ( BTree<V, V> ) mvHolder.getValue();
-
-                // return value will always be null  here 
-                if ( !dupValues.hasKey( value ) )
-                {
-                    dupValues.insert( value, null, 0 );
-                }
-                else
-                {
-                    oldValue = value;
-                }
-            }
+            valueHolder.add( value );
+            newLeaf.values[pos] = valueHolder;
         }
         else
         {
-            // Now we can inject the value
-            oldValue = newLeaf.values[pos].getValue();
-            newLeaf.values[pos] = btree.createValueHolder( value );
+            // As strange as it sounds, we need to remove the value to reinject it.
+            // There are cases where the value retrieval just use one part of the
+            // value only (typically for LDAP Entries, where we use the DN)
+            replacedValue = valueHolder.remove( value );
+            valueHolder.add( value );
         }
 
         // Create the result
-        InsertResult<K, V> result = new ModifyResult<K, V>( newLeaf, oldValue );
+        InsertResult<K, V> result = new ModifyResult<K, V>( newLeaf, replacedValue );
         result.addCopiedPage( this );
 
         return result;
@@ -852,19 +768,7 @@ import org.apache.directory.mavibot.btre
         Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, nbElems + 1 );
 
         // Atm, store the value in memory
-
-        ElementHolder valueHolder = null;
-
-        if ( btree.isAllowDuplicates() )
-        {
-            valueHolder = new MultipleMemoryHolder<K, V>( btree, value );
-        }
-        else
-        {
-            valueHolder = new MemoryHolder<K, V>( btree, value );
-        }
-
-        //ValueHolder<K, V> valueHolder = btree.createHolder( value );
+        ValueHolder<V> valueHolder = new ValueHolder<V>( btree, value );
 
         // Deal with the special case of an empty page
         if ( nbElems == 0 )
@@ -912,7 +816,7 @@ import org.apache.directory.mavibot.btre
         int middle = btree.getPageSize() >> 1;
         Leaf<K, V> leftLeaf = null;
         Leaf<K, V> rightLeaf = null;
-        ElementHolder<V, K, V> valueHolder = btree.createValueHolder( value );
+        ValueHolder<V> valueHolder = new ValueHolder<V>( btree, value );
 
         // Determinate where to store the new value
         if ( pos <= middle )
@@ -1001,15 +905,7 @@ import org.apache.directory.mavibot.btre
     {
         V val = null;
 
-        if ( btree.isAllowDuplicates() )
-        {
-            BTree<V, V> dupTree = ( BTree<V, V> ) values[0].getValue();
-            val = dupTree.rootPage.getLeftMostKey();
-        }
-        else
-        {
-            val = values[0].getValue();
-        }
+        val = values[0].getCursor().next();
 
         return new Tuple<K, V>( keys[0], val );
     }
@@ -1022,15 +918,9 @@ import org.apache.directory.mavibot.btre
     {
         V val = null;
 
-        if ( btree.isAllowDuplicates() )
-        {
-            BTree<V, V> dupTree = ( BTree<V, V> ) values[nbElems - 1].getValue();
-            val = dupTree.rootPage.getRightMostKey();
-        }
-        else
-        {
-            val = values[nbElems - 1].getValue();
-        }
+        ValueCursor<V> valueCursor = values[nbElems - 1].getCursor();
+        valueCursor.afterLast();
+        val = valueCursor.prev();
 
         return new Tuple<K, V>( keys[nbElems - 1], val );
     }

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/MergedWithSiblingResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/MergedWithSiblingResult.java?rev=1549961&r1=1549960&r2=1549961&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/MergedWithSiblingResult.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/MergedWithSiblingResult.java Tue Dec 10 20:42:16 2013
@@ -22,6 +22,7 @@ package org.apache.directory.mavibot.btr
 
 import java.util.List;
 
+import org.apache.directory.mavibot.btree.Page;
 import org.apache.directory.mavibot.btree.Tuple;
 
 

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/ModifyResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/ModifyResult.java?rev=1549961&r1=1549960&r2=1549961&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/ModifyResult.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/ModifyResult.java Tue Dec 10 20:42:16 2013
@@ -22,6 +22,9 @@ package org.apache.directory.mavibot.btr
 
 import java.util.List;
 
+import org.apache.directory.mavibot.btree.InsertResult;
+import org.apache.directory.mavibot.btree.Page;
+
 
 /**
  * The result of an insert operation, when the child has not been split. It contains the

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Node.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Node.java?rev=1549961&r1=1549960&r2=1549961&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Node.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Node.java Tue Dec 10 20:42:16 2013
@@ -24,8 +24,14 @@ import java.io.IOException;
 import java.lang.reflect.Array;
 import java.util.List;
 
+import org.apache.directory.mavibot.btree.DeleteResult;
+import org.apache.directory.mavibot.btree.InsertResult;
+import org.apache.directory.mavibot.btree.Page;
+import org.apache.directory.mavibot.btree.ParentPos;
+import org.apache.directory.mavibot.btree.Transaction;
 import org.apache.directory.mavibot.btree.Tuple;
 import org.apache.directory.mavibot.btree.TupleCursor;
+import org.apache.directory.mavibot.btree.ValueCursor;
 import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
 import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
 
@@ -42,7 +48,7 @@ import org.apache.directory.mavibot.btre
 /* No qualifier */class Node<K, V> extends AbstractPage<K, V>
 {
     /** Children pages associated with keys. */
-    protected ElementHolder<Page<K, V>, K, V>[] children;
+    protected Page<K, V>[] children;
 
 
     /**
@@ -60,7 +66,7 @@ import org.apache.directory.mavibot.btre
         super( btree, revision, nbElems );
 
         // Create the children array
-        children = ( ElementHolder<Page<K, V>, K, V>[] ) Array.newInstance( ElementHolder.class, nbElems + 1 );
+        children = ( Page<K, V>[] ) Array.newInstance( Page.class, nbElems + 1 );
     }
 
 
@@ -81,41 +87,7 @@ import org.apache.directory.mavibot.btre
         super( btree, revision, 1 );
 
         // Create the children array, and store the left and right children
-        children = ( MemoryHolder[] ) Array.newInstance( MemoryHolder.class,
-            btree.getPageSize() + 1 );
-
-        children[0] = btree.createPageHolder( leftPage );
-        children[1] = btree.createPageHolder( rightPage );
-
-        // Create the keys array and store the pivot into it
-        // We get the type of array to create from the btree
-        // Yes, this is an hack...
-        Class<?> keyType = btree.getKeyType();
-        keys = ( K[] ) Array.newInstance( keyType, btree.getPageSize() );
-
-        keys[0] = key;
-    }
-
-
-    /**
-     * Creates a new Node which will contain only one key, with references to
-     * a left and right page. This is a specific constructor used by the btree
-     * when the root was full when we added a new value.
-     * 
-     * @param btree the parent BTree
-     * @param revision the Node revision
-     * @param key The new key
-     * @param leftPage The left page
-     * @param rightPage The right page
-     */
-    @SuppressWarnings("unchecked")
-    /* No qualifier */Node( BTree<K, V> btree, long revision, K key, ElementHolder<Page<K, V>, K, V> leftPage,
-        ElementHolder<Page<K, V>, K, V> rightPage )
-    {
-        super( btree, revision, 1 );
-
-        // Create the children array, and store the left and right children
-        children = ( ElementHolder<Page<K, V>, K, V>[] ) Array.newInstance( MemoryHolder.class,
+        children = ( Page[] ) Array.newInstance( Page.class,
             btree.getPageSize() + 1 );
 
         children[0] = leftPage;
@@ -147,7 +119,7 @@ import org.apache.directory.mavibot.btre
         }
 
         // Get the child page into which we will insert the <K, V> tuple
-        Page<K, V> child = children[pos].getValue();
+        Page<K, V> child = children[pos];
 
         // and insert the <K, V> into this child
         InsertResult<K, V> result = child.insert( revision, key, value );
@@ -210,11 +182,11 @@ import org.apache.directory.mavibot.btre
 
         if ( found )
         {
-            newPage.children[index + 1] = createHolder( modifiedPage );
+            newPage.children[index + 1] = modifiedPage;
         }
         else
         {
-            newPage.children[index] = createHolder( modifiedPage );
+            newPage.children[index] = modifiedPage;
         }
 
         if ( pos < 0 )
@@ -281,7 +253,7 @@ import org.apache.directory.mavibot.btre
         // Create the new sibling, with one less element at the beginning
         Node<K, V> newSibling = new Node<K, V>( btree, revision, sibling.getNbElems() - 1 );
 
-        K siblingKey = sibling.children[0].getValue().getLeftMostKey();
+        K siblingKey = sibling.children[0].getLeftMostKey();
 
         // Copy the keys and children of the old sibling in the new sibling
         System.arraycopy( sibling.keys, 1, newSibling.keys, 0, newSibling.getNbElems() );
@@ -305,7 +277,7 @@ import org.apache.directory.mavibot.btre
 
             // Inject the modified page
             Page<K, V> modifiedPage = mergedResult.getModifiedPage();
-            newNode.children[0] = createHolder( modifiedPage );
+            newNode.children[0] = modifiedPage;
 
             // Copy the children
             System.arraycopy( children, 2, newNode.children, 1, nbElems - 1 );
@@ -335,7 +307,7 @@ import org.apache.directory.mavibot.btre
 
             // Inject the modified page
             Page<K, V> modifiedPage = mergedResult.getModifiedPage();
-            newNode.children[index - 1] = createHolder( modifiedPage ); // 6
+            newNode.children[index - 1] = modifiedPage; // 6
         }
 
         // Create the result
@@ -364,7 +336,7 @@ import org.apache.directory.mavibot.btre
         Node<K, V> sibling, int pos ) throws IOException
     {
         // The sibling is on the left, borrow the rightmost element
-        Page<K, V> siblingChild = sibling.children[sibling.nbElems].getValue();
+        Page<K, V> siblingChild = sibling.children[sibling.nbElems];
 
         // Create the new sibling, with one less element at the end
         Node<K, V> newSibling = new Node<K, V>( btree, revision, sibling.getNbElems() - 1 );
@@ -378,7 +350,7 @@ import org.apache.directory.mavibot.btre
         Node<K, V> newNode = new Node<K, V>( btree, revision, nbElems );
 
         // Sets the first children
-        newNode.children[0] = createHolder( siblingChild ); //1
+        newNode.children[0] = siblingChild; //1
 
         int index = Math.abs( pos );
 
@@ -388,13 +360,13 @@ import org.apache.directory.mavibot.btre
             System.arraycopy( keys, 1, newNode.keys, 1, nbElems - 1 );
 
             Page<K, V> modifiedPage = mergedResult.getModifiedPage();
-            newNode.children[1] = createHolder( modifiedPage );
+            newNode.children[1] = modifiedPage;
             System.arraycopy( children, 2, newNode.children, 2, nbElems - 1 );
         }
         else
         {
             // Set the first key
-            newNode.keys[0] = children[0].getValue().getLeftMostKey(); //2
+            newNode.keys[0] = children[0].getLeftMostKey(); //2
 
             if ( index > 2 )
             {
@@ -419,7 +391,7 @@ import org.apache.directory.mavibot.btre
 
             // Insert the modified page
             Page<K, V> modifiedPage = mergedResult.getModifiedPage();
-            newNode.children[index] = createHolder( modifiedPage ); // 7
+            newNode.children[index] = modifiedPage; // 7
         }
 
         // Create the result
@@ -469,14 +441,14 @@ import org.apache.directory.mavibot.btre
                 System.arraycopy( keys, 1, newNode.keys, half + 1, half - 1 );
 
                 Page<K, V> modifiedPage = mergedResult.getModifiedPage();
-                newNode.children[half + 1] = createHolder( modifiedPage );
+                newNode.children[half + 1] = modifiedPage;
                 System.arraycopy( children, 2, newNode.children, half + 2, half - 1 );
             }
             else
             {
                 // Copy the left part of the node keys up to the deletion point
                 // Insert the new key
-                newNode.keys[half] = children[0].getValue().getLeftMostKey(); // 3
+                newNode.keys[half] = children[0].getLeftMostKey(); // 3
 
                 if ( index > 2 )
                 {
@@ -497,7 +469,7 @@ import org.apache.directory.mavibot.btre
 
                 // Inject the new merged child
                 Page<K, V> modifiedPage = mergedResult.getModifiedPage();
-                newNode.children[half + index] = createHolder( modifiedPage ); //8
+                newNode.children[half + index] = modifiedPage; //8
             }
         }
         else
@@ -510,7 +482,7 @@ import org.apache.directory.mavibot.btre
 
                 // Insert the first child
                 Page<K, V> modifiedPage = mergedResult.getModifiedPage();
-                newNode.children[0] = createHolder( modifiedPage );
+                newNode.children[0] = modifiedPage;
 
                 // Copy the node children
                 System.arraycopy( children, 2, newNode.children, 1, half - 1 );
@@ -532,7 +504,7 @@ import org.apache.directory.mavibot.btre
 
                 // Inject the modified children
                 Page<K, V> modifiedPage = mergedResult.getModifiedPage();
-                newNode.children[index - 1] = createHolder( modifiedPage ); // 7
+                newNode.children[index - 1] = modifiedPage; // 7
 
                 // Add the remaining node's key if needed
                 if ( index < half )
@@ -582,12 +554,12 @@ import org.apache.directory.mavibot.btre
         if ( found )
         {
             index = -( pos + 1 );
-            child = children[-pos].getValue();
+            child = children[-pos];
             deleteResult = child.delete( revision, key, value, this, -pos );
         }
         else
         {
-            child = children[pos].getValue();
+            child = children[pos];
             deleteResult = child.delete( revision, key, value, this, pos );
         }
 
@@ -651,7 +623,7 @@ import org.apache.directory.mavibot.btre
                 // a sibling, or we will have to merge two pages
                 int siblingPos = selectSibling( ( Node<K, V> ) parent, parentPos );
 
-                Node<K, V> sibling = ( Node<K, V> ) ( ( ( Node<K, V> ) parent ).children[siblingPos].getValue() );
+                Node<K, V> sibling = ( Node<K, V> ) ( ( ( Node<K, V> ) parent ).children[siblingPos] );
 
                 if ( sibling.getNbElems() > halfSize )
                 {
@@ -714,8 +686,8 @@ import org.apache.directory.mavibot.btre
                 newPage.keys[pos + 1] = modifiedSibling.findLeftMost().getKey();
 
                 // Update the children
-                newPage.children[pos + 1] = createHolder( modifiedPage );
-                newPage.children[pos + 2] = createHolder( modifiedSibling );
+                newPage.children[pos + 1] = modifiedPage;
+                newPage.children[pos + 2] = modifiedSibling;
             }
             else
             {
@@ -723,8 +695,8 @@ import org.apache.directory.mavibot.btre
                 newPage.keys[pos] = modifiedPage.findLeftMost().getKey();
 
                 // Update the children
-                newPage.children[pos] = createHolder( modifiedSibling );
-                newPage.children[pos + 1] = createHolder( modifiedPage );
+                newPage.children[pos] = modifiedSibling;
+                newPage.children[pos + 1] = modifiedPage;
             }
         }
         else
@@ -735,8 +707,8 @@ import org.apache.directory.mavibot.btre
                 newPage.keys[pos] = modifiedSibling.findLeftMost().getKey();
 
                 // Update the children
-                newPage.children[pos] = createHolder( modifiedPage );
-                newPage.children[pos + 1] = createHolder( modifiedSibling );
+                newPage.children[pos] = modifiedPage;
+                newPage.children[pos + 1] = modifiedSibling;
             }
             else
             {
@@ -744,8 +716,8 @@ import org.apache.directory.mavibot.btre
                 newPage.keys[pos - 1] = modifiedPage.findLeftMost().getKey();
 
                 // Update the children
-                newPage.children[pos - 1] = createHolder( modifiedSibling );
-                newPage.children[pos] = createHolder( modifiedPage );
+                newPage.children[pos - 1] = modifiedSibling;
+                newPage.children[pos] = modifiedPage;
             }
         }
 
@@ -782,7 +754,7 @@ import org.apache.directory.mavibot.btre
             // Copy the keys and the children
             System.arraycopy( keys, 1, newNode.keys, 0, newNode.nbElems );
             Page<K, V> modifiedPage = mergedResult.getModifiedPage();
-            newNode.children[0] = createHolder( modifiedPage );
+            newNode.children[0] = modifiedPage;
             System.arraycopy( children, 2, newNode.children, 1, nbElems - 1 );
         }
         else
@@ -804,7 +776,7 @@ import org.apache.directory.mavibot.btre
             System.arraycopy( children, 0, newNode.children, 0, index + 1 );
 
             Page<K, V> modifiedPage = mergedResult.getModifiedPage();
-            newNode.children[index + 1] = createHolder( modifiedPage );
+            newNode.children[index + 1] = modifiedPage;
 
             if ( index < nbElems - 2 )
             {
@@ -833,11 +805,11 @@ import org.apache.directory.mavibot.btre
         {
             // Here, if we have found the key in the node, then we must go down into
             // the right child, not the left one
-            return children[-pos].getValue().get( key );
+            return children[-pos].get( key );
         }
         else
         {
-            return children[pos].getValue().get( key );
+            return children[pos].get( key );
         }
     }
 
@@ -846,7 +818,7 @@ import org.apache.directory.mavibot.btre
      * {@inheritDoc}
      */
     @Override
-    public DuplicateKeyVal<V> getValues( K key ) throws KeyNotFoundException, IOException, IllegalArgumentException
+    public ValueCursor<V> getValues( K key ) throws KeyNotFoundException, IOException, IllegalArgumentException
     {
         int pos = findPos( key );
 
@@ -854,11 +826,11 @@ import org.apache.directory.mavibot.btre
         {
             // Here, if we have found the key in the node, then we must go down into
             // the right child, not the left one
-            return children[-pos].getValue().getValues( key );
+            return children[-pos].getValues( key );
         }
         else
         {
-            return children[pos].getValue().getValues( key );
+            return children[pos].getValues( key );
         }
     }
 
@@ -875,11 +847,11 @@ import org.apache.directory.mavibot.btre
         {
             // Here, if we have found the key in the node, then we must go down into
             // the right child, not the left one
-            return children[-pos].getValue().hasKey( key );
+            return children[-pos].hasKey( key );
         }
         else
         {
-            Page<K, V> page = children[pos].getValue();
+            Page<K, V> page = children[pos];
 
             if ( page == null )
             {
@@ -903,11 +875,11 @@ import org.apache.directory.mavibot.btre
         {
             // Here, if we have found the key in the node, then we must go down into
             // the right child, not the left one
-            return children[-pos].getValue().contains( key, value );
+            return children[-pos].contains( key, value );
         }
         else
         {
-            return children[pos].getValue().contains( key, value );
+            return children[pos].contains( key, value );
         }
     }
 
@@ -918,7 +890,7 @@ import org.apache.directory.mavibot.btre
      * @param pos The position in the values array
      * @param value the value to inject
      */
-    public void setValue( int pos, ElementHolder<Page<K, V>, K, V> value )
+    public void setValue( int pos, Page<K, V> value )
     {
         children[pos] = value;
     }
@@ -931,7 +903,7 @@ import org.apache.directory.mavibot.btre
     {
         if ( pos < nbElems + 1 )
         {
-            return children[pos].getValue();
+            return children[pos];
         }
         else
         {
@@ -956,7 +928,7 @@ import org.apache.directory.mavibot.btre
         // We first stack the current page
         stack[depth++] = new ParentPos<K, V>( this, pos );
         
-        Page<K, V> page = children[pos].getValue();
+        Page<K, V> page = children[pos];
 
         return page.browse( key, transaction, stack, depth );
     }
@@ -970,7 +942,7 @@ import org.apache.directory.mavibot.btre
     {
         stack[depth++] = new ParentPos<K, V>( this, 0 );
         
-        Page<K, V> page = children[0].getValue();
+        Page<K, V> page = children[0];
 
         return page.browse( transaction, stack, depth );
     }
@@ -996,7 +968,7 @@ import org.apache.directory.mavibot.btre
         // to point on the modified child
         Page<K, V> modifiedPage = result.getModifiedPage();
 
-        ( ( Node<K, V> ) newPage ).children[pos] = createHolder( modifiedPage );
+        ( ( Node<K, V> ) newPage ).children[pos] = modifiedPage;
 
         // We can return the result, where we update the modifiedPage,
         // to avoid the creation of a new object
@@ -1009,19 +981,6 @@ import org.apache.directory.mavibot.btre
 
 
     /**
-     * Creates a new holder contaning a reference to a Page
-     * 
-     * @param page The page we will refer to
-     * @return A holder contaning a reference to the child page
-     * @throws IOException If we have an error while trying to access the page
-     */
-    private ElementHolder<Page<K, V>, K, V> createHolder( Page<K, V> page ) throws IOException
-    {
-        return btree.createPageHolder( page );
-    }
-
-
-    /**
      * Adds a new key into a copy of the current page at a given position. We return the
      * modified page. The new page will have one more key than the current page.
      * 
@@ -1053,8 +1012,8 @@ import org.apache.directory.mavibot.btre
 
         // If the BTree is managed, we now have to write the modified page on disk
         // and to add this page to the list of modified pages
-        newNode.children[pos] = createHolder( leftPage );
-        newNode.children[pos + 1] = createHolder( rightPage );
+        newNode.children[pos] = leftPage;
+        newNode.children[pos + 1] = rightPage;
 
         // And copy the remaining keys and children
         if ( nbElems > 0 )
@@ -1109,8 +1068,8 @@ import org.apache.directory.mavibot.btre
 
             // Add the new element
             newLeftPage.keys[pos] = pivot;
-            newLeftPage.children[pos] = createHolder( leftPage );
-            newLeftPage.children[pos + 1] = createHolder( rightPage );
+            newLeftPage.children[pos] = leftPage;
+            newLeftPage.children[pos + 1] = rightPage;
 
             // And copy the remaining elements minus the new pivot
             System.arraycopy( keys, pos, newLeftPage.keys, pos + 1, middle - pos - 1 );
@@ -1133,12 +1092,12 @@ import org.apache.directory.mavibot.btre
             // Copy the keys and the children up to the insertion position (here, middle)
             System.arraycopy( keys, 0, newLeftPage.keys, 0, middle );
             System.arraycopy( children, 0, newLeftPage.children, 0, middle );
-            newLeftPage.children[middle] = createHolder( leftPage );
+            newLeftPage.children[middle] = leftPage;
 
             // And process the right page now
             System.arraycopy( keys, middle, newRightPage.keys, 0, middle );
             System.arraycopy( children, middle + 1, newRightPage.children, 1, middle );
-            newRightPage.children[0] = createHolder( rightPage );
+            newRightPage.children[0] = rightPage;
 
             // Create the result
             InsertResult<K, V> result = new SplitResult<K, V>( copiedPages, pivot, newLeftPage, newRightPage );
@@ -1158,8 +1117,8 @@ import org.apache.directory.mavibot.btre
 
             // Add the new element
             newRightPage.keys[pos - middle - 1] = pivot;
-            newRightPage.children[pos - middle - 1] = createHolder( leftPage );
-            newRightPage.children[pos - middle] = createHolder( rightPage );
+            newRightPage.children[pos - middle - 1] = leftPage;
+            newRightPage.children[pos - middle] = rightPage;
 
             // And copy the remaining elements minus the new pivot
             System.arraycopy( keys, pos, newRightPage.keys, pos - middle, nbElems - pos );
@@ -1199,7 +1158,7 @@ import org.apache.directory.mavibot.btre
      */
     public K getLeftMostKey() throws EndOfFileExceededException, IOException
     {
-        return children[0].getValue().getLeftMostKey();
+        return children[0].getLeftMostKey();
     }
 
 
@@ -1212,10 +1171,10 @@ import org.apache.directory.mavibot.btre
 
         if ( children[index] != null )
         {
-            return children[index].getValue().getRightMostKey();
+            return children[index].getRightMostKey();
         }
 
-        return children[nbElems - 1].getValue().getRightMostKey();
+        return children[nbElems - 1].getRightMostKey();
     }
 
 
@@ -1224,7 +1183,7 @@ import org.apache.directory.mavibot.btre
      */
     public Tuple<K, V> findLeftMost() throws EndOfFileExceededException, IOException
     {
-        return children[0].getValue().findLeftMost();
+        return children[0].findLeftMost();
     }
 
 
@@ -1233,7 +1192,7 @@ import org.apache.directory.mavibot.btre
      */
     public Tuple<K, V> findRightMost() throws EndOfFileExceededException, IOException
     {
-        return children[nbElems].getValue().findRightMost();
+        return children[nbElems].findRightMost();
     }
 
 
@@ -1248,39 +1207,32 @@ import org.apache.directory.mavibot.btre
         sb.append( super.toString() );
         sb.append( "] -> {" );
 
-        try
+        if ( nbElems > 0 )
         {
-            if ( nbElems > 0 )
+            // Start with the first child
+            if ( children[0] == null )
             {
-                // Start with the first child
-                if ( children[0] == null )
+                sb.append( "null" );
+            }
+            else
+            {
+                sb.append( 'r' ).append( children[0].getRevision() );
+            }
+
+            for ( int i = 0; i < nbElems; i++ )
+            {
+                sb.append( "|<" ).append( keys[i] ).append( ">|" );
+
+                if ( children[i + 1] == null )
                 {
                     sb.append( "null" );
                 }
                 else
                 {
-                    sb.append( 'r' ).append( children[0].getValue().getRevision() );
-                }
-
-                for ( int i = 0; i < nbElems; i++ )
-                {
-                    sb.append( "|<" ).append( keys[i] ).append( ">|" );
-
-                    if ( children[i + 1] == null )
-                    {
-                        sb.append( "null" );
-                    }
-                    else
-                    {
-                        sb.append( 'r' ).append( children[i + 1].getValue().getRevision() );
-                    }
+                    sb.append( 'r' ).append( children[i + 1].getRevision() );
                 }
             }
         }
-        catch ( IOException ioe )
-        {
-            // Do nothing
-        }
 
         sb.append( "}" );
 
@@ -1297,22 +1249,15 @@ import org.apache.directory.mavibot.btre
 
         if ( nbElems > 0 )
         {
-            try
-            {
-                // Start with the first child
-                sb.append( children[0].getValue().dumpPage( tabs + "    " ) );
+            // Start with the first child
+            sb.append( children[0].dumpPage( tabs + "    " ) );
 
-                for ( int i = 0; i < nbElems; i++ )
-                {
-                    sb.append( tabs );
-                    sb.append( "<" );
-                    sb.append( keys[i] ).append( ">\n" );
-                    sb.append( children[i + 1].getValue().dumpPage( tabs + "    " ) );
-                }
-            }
-            catch ( IOException ioe )
+            for ( int i = 0; i < nbElems; i++ )
             {
-                // Do nothing
+                sb.append( tabs );
+                sb.append( "<" );
+                sb.append( keys[i] ).append( ">\n" );
+                sb.append( children[i + 1].dumpPage( tabs + "    " ) );
             }
         }
 

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/NotPresentResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/NotPresentResult.java?rev=1549961&r1=1549960&r2=1549961&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/NotPresentResult.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/NotPresentResult.java Tue Dec 10 20:42:16 2013
@@ -20,6 +20,8 @@
 package org.apache.directory.mavibot.btree.memory;
 
 
+import org.apache.directory.mavibot.btree.DeleteResult;
+import org.apache.directory.mavibot.btree.Page;
 import org.apache.directory.mavibot.btree.Tuple;
 
 

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/RemoveResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/RemoveResult.java?rev=1549961&r1=1549960&r2=1549961&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/RemoveResult.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/RemoveResult.java Tue Dec 10 20:42:16 2013
@@ -22,6 +22,7 @@ package org.apache.directory.mavibot.btr
 
 import java.util.List;
 
+import org.apache.directory.mavibot.btree.Page;
 import org.apache.directory.mavibot.btree.Tuple;
 
 

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/SplitResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/SplitResult.java?rev=1549961&r1=1549960&r2=1549961&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/SplitResult.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/SplitResult.java Tue Dec 10 20:42:16 2013
@@ -22,6 +22,9 @@ package org.apache.directory.mavibot.btr
 
 import java.util.List;
 
+import org.apache.directory.mavibot.btree.InsertResult;
+import org.apache.directory.mavibot.btree.Page;
+
 
 /**
  * The result of an insert operation, when the page has been split. It contains

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/TupleCursorImpl.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/TupleCursorImpl.java?rev=1549961&r1=1549960&r2=1549961&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/TupleCursorImpl.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/TupleCursorImpl.java Tue Dec 10 20:42:16 2013
@@ -20,13 +20,12 @@
 package org.apache.directory.mavibot.btree.memory;
 
 
-import static org.apache.directory.mavibot.btree.memory.InternalUtil.changeNextDupsContainer;
-import static org.apache.directory.mavibot.btree.memory.InternalUtil.changePrevDupsContainer;
-import static org.apache.directory.mavibot.btree.memory.InternalUtil.setDupsContainer;
-
 import java.io.IOException;
 import java.util.NoSuchElementException;
 
+import org.apache.directory.mavibot.btree.Page;
+import org.apache.directory.mavibot.btree.ParentPos;
+import org.apache.directory.mavibot.btree.Transaction;
 import org.apache.directory.mavibot.btree.Tuple;
 import org.apache.directory.mavibot.btree.TupleCursor;
 import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
@@ -57,9 +56,6 @@ public class TupleCursorImpl<K, V> imple
     /** The stack's depth */
     private int depth = 0;
 
-    /** The BTree we are walking */
-    private BTree<K, V> btree;
-
     private boolean allowDuplicates;
 
 
@@ -73,92 +69,131 @@ public class TupleCursorImpl<K, V> imple
     {
         this.transaction = transaction;
         this.stack = stack;
-        this.btree = btree;
         this.allowDuplicates = btree.isAllowDuplicates();
         this.depth = depth;
     }
 
 
     /**
-     * Find the next key/value
-     * 
-     * @return A Tuple containing the found key and value
-     * @throws IOException 
-     * @throws EndOfFileExceededException 
+     * Closes the cursor, thus releases the associated transaction
      */
-    public Tuple<K, V> next() throws EndOfFileExceededException, IOException
+    public void close()
+    {
+        transaction.close();
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public long getRevision()
+    {
+        return transaction.getRevision();
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public long getCreationDate()
+    {
+        return transaction.getCreationDate();
+    }
+    
+    
+    /**
+     * {@inheritDoc}
+     */
+    public void afterLast() throws IOException
     {
         // First check that we have elements in the BTree
         if ( ( stack == null ) || ( stack.length == 0 ) )
         {
-            throw new NoSuchElementException( "No tuple present" );
+            return;
         }
 
-        ParentPos<K, V> parentPos = stack[depth];
+        Page<K, V> child = null;
 
-        if ( parentPos.page == null )
+        for ( int i = 0; i < depth; i++ )
         {
-            // This is the end : no more value
-            throw new NoSuchElementException( "No more tuples present" );
+            ParentPos<K, V> parentPos = stack[i];
+            
+            if ( child != null )
+            {
+                parentPos.page = child;
+                parentPos.pos = ((Node<K, V>)child).nbElems;
+            }
+            else
+            {
+                // We have N+1 children if the page is a Node, so we don't decrement the nbElems field
+                parentPos.pos = ((Node<K, V>)parentPos.page).nbElems;
+            }
+
+            child = ((Node<K, V>)parentPos.page).children[parentPos.pos];
         }
+        
+        // and leaf
+        ParentPos<K, V> parentPos = stack[depth];
 
-        if ( parentPos.pos == parentPos.page.getNbElems() )
+        if ( child == null )
         {
-            // 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.page == null || ( parentPos.page instanceof Node ) )
-            {
-                // This is the end : no more value
-                throw new NoSuchElementException( "No more tuples present" );
-            }
+            parentPos.pos = ((Leaf<K, V>)parentPos.page).nbElems - 1;
+        }
+        else
+        {
+            parentPos.page = child;
+            parentPos.pos = ((Leaf<K, V>)child).nbElems - 1;
         }
 
-        // can happen if next() is called after prev()
-        if ( parentPos.pos == BEFORE_FIRST )
+        parentPos.valueCursor = ((Leaf<K, V>)parentPos.page).values[parentPos.pos].getCursor();
+        parentPos.valueCursor.afterLast();
+        parentPos.pos = AFTER_LAST;
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public void beforeFirst() throws IOException
+    {
+        // First check that we have elements in the BTree
+        if ( ( stack == null ) || ( stack.length == 0 ) )
         {
-            parentPos.pos = 0;
+            return;
         }
 
-        Leaf<K, V> leaf = ( Leaf<K, V> ) ( parentPos.page );
-        tuple.setKey( leaf.keys[parentPos.pos] );
+        Page<K, V> child = null;
 
-        if ( allowDuplicates )
+        for ( int i = 0; i < depth; i++ )
         {
-            MultipleMemoryHolder<K, V> mvHolder = ( MultipleMemoryHolder<K, V> ) leaf.values[parentPos.pos];
+            ParentPos<K, V> parentPos = stack[i];
+            parentPos.pos = 0;
 
-            if ( mvHolder.isSingleValue() )
+            if ( child != null )
             {
-                tuple.setValue( mvHolder.getValue() );
-                parentPos.pos++;
+                parentPos.page = child;
             }
-            else
-            {
-                setDupsContainer( parentPos, btree );
 
-                tuple.setValue( parentPos.valueCursor.rootPage.getKey( parentPos.dupPos ) );
-                parentPos.dupPos++;
+            child = ((Node<K, V>)parentPos.page).children[0];
+        }
 
-                if ( parentPos.valueCursor.getNbElems() == parentPos.dupPos )
-                {
-                    parentPos.pos++;
-                    changeNextDupsContainer( parentPos, btree );
-                }
-            }
+        // and leaf
+        ParentPos<K, V> parentPos = stack[depth];
+        parentPos.pos = BEFORE_FIRST;
+
+        if ( child != null )
+        {
+            parentPos.page = child;
         }
-        else
+        
+        if ( parentPos.valueCursor != null )
         {
-            tuple.setValue( leaf.values[parentPos.pos].getValue() );
-            parentPos.pos++;
+            parentPos.valueCursor = ((Leaf<K, V>)parentPos.page).values[0].getCursor();
+            parentPos.valueCursor.beforeFirst();
         }
-
-        return tuple;
     }
-
-
+    
+    
     /**
      * Find the leaf containing the following elements.
      * 
@@ -184,7 +219,7 @@ public class TupleCursorImpl<K, V> imple
             // is not the last one
             ParentPos<K, V> parentPos = stack[currentDepth];
 
-            if ( parentPos.pos == parentPos.page.getNbElems() )
+            if ( parentPos.pos + 1 > parentPos.page.getNbElems() )
             {
                 // No more element on the right : go up
                 currentDepth--;
@@ -193,36 +228,32 @@ public class TupleCursorImpl<K, V> imple
             {
                 // We can pick the next element at this level
                 parentPos.pos++;
-                child = ((Node<K, V>)parentPos.page).children[parentPos.pos].getValue();
+                child = ((Node<K, V>)parentPos.page).children[parentPos.pos];
                 
                 // and go down the tree through the nodes
                 while ( currentDepth < depth - 1 )
                 {
                     currentDepth++;
                     parentPos = stack[currentDepth];
-                    parentPos.page = child;
                     parentPos.pos = 0;
-                    child = ((Node<K, V>)parentPos.page).children[parentPos.pos].getValue();
+                    parentPos.page = child;
+                    child = ((Node<K, V>)child).children[0];
                 }
 
                 // and the leaf
                 parentPos = stack[depth];
-                parentPos.pos = 0;
                 parentPos.page = child;
-                
-                if ( allowDuplicates )
-                {
-                    changeNextDupsContainer( parentPos, btree );
-                }
+                parentPos.pos = 0;
+                parentPos.valueCursor = ((Leaf<K, V>)child).values[0].getCursor();
 
                 return parentPos;
             }
         }
-        
+
         return null;
     }
-
-
+    
+    
     /**
      * Find the leaf containing the previous elements.
      * 
@@ -257,7 +288,7 @@ public class TupleCursorImpl<K, V> imple
             {
                 // We can pick the next element at this level
                 parentPos.pos--;
-                child = ((Node<K, V>)parentPos.page).children[parentPos.pos].getValue();
+                child = ((Node<K, V>)parentPos.page).children[parentPos.pos];
                 
                 // and go down the tree through the nodes
                 while ( currentDepth < depth - 1 )
@@ -266,18 +297,16 @@ public class TupleCursorImpl<K, V> imple
                     parentPos = stack[currentDepth];
                     parentPos.pos = child.getNbElems();
                     parentPos.page = child;
-                    child = ((Node<K, V>)parentPos.page).children[((Node<K, V>)parentPos.page).nbElems].getValue();
+                    child = ((Node<K, V>)parentPos.page).children[((Node<K, V>)parentPos.page).nbElems];
                 }
 
                 // and the leaf
                 parentPos = stack[depth];
-                parentPos.pos = child.getNbElems();
+                parentPos.pos = child.getNbElems() - 1;
                 parentPos.page = child;
-
-                if ( allowDuplicates )
-                {
-                    changePrevDupsContainer( parentPos, btree );
-                }
+                ValueHolder<V> valueHolder = ((Leaf<K, V>)parentPos.page).values[parentPos.pos];
+                parentPos.valueCursor = valueHolder.getCursor();
+                parentPos.valueCursor.afterLast();
 
                 return parentPos;
             }
@@ -288,131 +317,6 @@ public class TupleCursorImpl<K, V> imple
 
 
     /**
-     * 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 tuple 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 ) && ( parentPos.dupPos == 0 ) )
-        {
-            // 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.page == null || ( parentPos.page instanceof Node ) )
-            {
-                // This is the end : no more value
-                throw new NoSuchElementException( "No more tuples present" );
-            }
-        }
-
-        Leaf<K, V> leaf = ( Leaf<K, V> ) ( parentPos.page );
-
-        if ( allowDuplicates )
-        {
-            boolean posDecremented = false;
-
-            // can happen if prev() was called after next()
-            if ( parentPos.pos == parentPos.page.getNbElems() )
-            {
-                parentPos.pos--;
-                posDecremented = true;
-            }
-
-            MultipleMemoryHolder<K, V> mvHolder = ( MultipleMemoryHolder<K, V> ) leaf.values[parentPos.pos];
-
-            boolean prevHasSubtree = false;
-            // if the current key has only one value then advance to previous position
-            if ( mvHolder.isSingleValue() )
-            {
-                if ( !posDecremented )
-                {
-                    parentPos.pos--;
-                    mvHolder = ( MultipleMemoryHolder<K, V> ) leaf.values[parentPos.pos];
-                    posDecremented = true;
-                }
-
-                if ( mvHolder.isSingleValue() )
-                {
-                    tuple.setKey( leaf.keys[parentPos.pos] );
-                    tuple.setValue( mvHolder.getValue() );
-                }
-                else
-                {
-                    prevHasSubtree = true;
-                }
-            }
-            else
-            {
-                prevHasSubtree = true;
-            }
-
-            if ( prevHasSubtree )
-            {
-                setDupsContainer( parentPos, btree );
-
-                if ( parentPos.dupPos == parentPos.valueCursor.getNbElems() )
-                {
-                    parentPos.dupPos--;
-                }
-                else if ( parentPos.dupPos == 0 )
-                {
-                    changePrevDupsContainer( parentPos, btree );
-                    parentPos.pos--;
-
-                    if ( parentPos.valueCursor != null )
-                    {
-                        parentPos.dupPos--;
-                    }
-                }
-                else
-                {
-                    parentPos.dupPos--;
-                }
-
-                tuple.setKey( leaf.keys[parentPos.pos] );
-
-                if ( parentPos.valueCursor != null )
-                {
-                    tuple.setValue( parentPos.valueCursor.rootPage.getKey( parentPos.dupPos ) );
-                }
-                else
-                {
-                    tuple.setValue( leaf.values[parentPos.pos].getValue() );
-                }
-            }
-        }
-        else
-        {
-            parentPos.pos--;
-            tuple.setKey( leaf.keys[parentPos.pos] );
-            tuple.setValue( leaf.values[parentPos.pos].getValue() );
-        }
-
-        return tuple;
-    }
-
-
-    /**
      * {@inheritDoc} 
      */
     public boolean hasNext() throws EndOfFileExceededException, IOException
@@ -422,7 +326,8 @@ public class TupleCursorImpl<K, V> imple
         {
             return false;
         }
-
+        
+        // Take the leaf and check if we have no mare values
         ParentPos<K, V> parentPos = stack[depth];
 
         if ( parentPos.page == null )
@@ -436,7 +341,7 @@ public class TupleCursorImpl<K, V> imple
             return false;
         }
         
-        if ( parentPos.pos < parentPos.page.getNbElems() )
+        if ( parentPos.pos < parentPos.page.getNbElems() - 1 )
         {
             // Not the last position, we have a next value
             return true;
@@ -444,9 +349,8 @@ public class TupleCursorImpl<K, V> imple
         else
         {
             // Check if we have some more value
-            if ( allowDuplicates && ( parentPos.valueCursor != null )  && ( parentPos.dupPos < parentPos.valueCursor.getNbElems() - 1 ) )
+            if ( parentPos.valueCursor.hasNext() )
             {
-                // We have some more values
                 return true;
             }
             
@@ -476,50 +380,132 @@ public class TupleCursorImpl<K, V> imple
 
 
     /**
-     * {@inheritDoc} 
+     * {@inheritDoc}
      */
-    public boolean hasPrev() throws EndOfFileExceededException, IOException
+    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;
         }
 
-        // 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
+            // This is the end : no more key
             return false;
         }
-
-        if ( parentPos.pos > 0 )
+        
+        if ( parentPos.pos == ( parentPos.page.getNbElems() - 1 ) )
         {
-            // get out, we have values on the left
-            return true;
+            // 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
         {
-            // Check that we are not before the first value
-            if ( parentPos.pos == BEFORE_FIRST )
-            {
-                return false;
-            }
-            
-            // Check if we have some more value
-            if ( allowDuplicates && ( parentPos.dupPos > 0 ) )
-            {
-                return true;
-            }
+            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 )
+
+    /**
+     * 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 = ((Node<K, V>)parentPos.page).children[parentPos.pos + 1];
+                
+                // and go down the tree through the nodes
+                while ( currentDepth < depth - 1 )
+                {
+                    currentDepth++;
+                    child = ((Node<K, V>)child).children[0];
+                }
+
+                return true;
+            }
+        }
+
+        return false;
+    }
+
+
+    /**
+     * {@inheritDoc} 
+     */
+    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];
                 
@@ -540,78 +526,173 @@ public class TupleCursorImpl<K, V> imple
 
 
     /**
-     * Closes the cursor, thus releases the associated transaction
+     * {@inheritDoc}
      */
-    public void close()
+    public boolean hasPrevKey() throws EndOfFileExceededException, IOException
     {
-        transaction.close();
-    }
+        // 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;
+        }
+    }
+    
+    
     /**
-     * @return The revision this cursor is based on
+     * Tells if there is a prev ParentPos
+     * 
+     * @return the new ParentPos instance, or null if we have no previous leaf
+     * @throws IOException 
+     * @throws EndOfFileExceededException 
      */
-    public long getRevision()
+    private boolean hasPrevParentPos() throws EndOfFileExceededException, IOException
     {
-        return transaction.getRevision();
-    }
+        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;
 
-    /**
-     * @return The creation date for this cursor
-     */
-    public long getCreationDate()
-    {
-        return transaction.getCreationDate();
+        // 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 = ((Node<K, V>)parentPos.page).children[parentPos.pos - 1];
+                
+                // and go down the tree through the nodes
+                while ( currentDepth < depth - 1 )
+                {
+                    currentDepth++;
+                    child = ((Node<K, V>)child).children[child.getNbElems()];
+                }
+
+                return true;
+            }
+        }
+
+        return false;
     }
 
 
     /**
      * {@inheritDoc}
      */
-    public boolean hasNextKey() throws EndOfFileExceededException, IOException
+    public Tuple<K, V> next() 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;
+            throw new NoSuchElementException( "No tuple present" );
         }
 
         ParentPos<K, V> parentPos = stack[depth];
 
-        if ( parentPos.page == null )
+        if ( ( parentPos.page == null ) || ( parentPos.pos == AFTER_LAST ) )
         {
-            // This is the end : no more key
-            return false;
+            // This is the end : no more value
+            throw new NoSuchElementException( "No more tuples present" );
         }
-        
-        if ( parentPos.pos == ( parentPos.page.getNbElems() - 1 ) )
+
+        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 next leaf
+            // parent, and down to the leaf
             parentPos = findNextParentPos();
 
-            // we also need to check the result of the call to
-            // findNextParentPos as it will return a null ParentPos
+            // 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 key
-                return false;
+                // This is the end : no more value
+                throw new NoSuchElementException( "No more tuples present" );
             }
-            else
+        }
+
+        V value = null;
+        
+        if ( parentPos.valueCursor.hasNext() )
+        {
+            // Deal with the BeforeFirst case
+            if ( parentPos.pos == BEFORE_FIRST )
             {
-                // We have more keys
-                return true;
+                parentPos.pos++;
             }
+            
+            value = parentPos.valueCursor.next();
         }
         else
         {
-            return true;
+            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 = ( ( Leaf<K, V> ) parentPos.page ).getValue( parentPos.pos );
+                
+                parentPos.valueCursor = valueHolder.getCursor();
+                
+                value = parentPos.valueCursor.next();
+            }
+            catch ( IllegalArgumentException e )
+            {
+                e.printStackTrace();
+            }
         }
+        
+        Leaf<K, V> leaf = ( Leaf<K, V> ) ( parentPos.page );
+        tuple.setKey( leaf.keys[parentPos.pos] );
+        tuple.setValue( value );
+
+        return tuple;
     }
 
-    
+
     /**
      * {@inheritDoc}
      */
@@ -636,14 +717,24 @@ public class TupleCursorImpl<K, V> imple
         {
             // End of the leaf. We have to go back into the stack up to the
             // parent, and down to the next leaf
-            parentPos = findNextParentPos();
+            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 ( ( parentPos == null ) || ( parentPos.page == null ) )
+            if ( ( newParentPos == null ) || ( newParentPos.page == null ) )
             {
                 // This is the end : no more value
-                throw new NoSuchElementException( "No more tuples present" );
+                Leaf<K, V> leaf = ( Leaf<K, V> ) ( parentPos.page );
+                ValueHolder<V> valueHolder = leaf.values[parentPos.pos];
+                parentPos.pos = AFTER_LAST;
+                parentPos.valueCursor = valueHolder.getCursor();
+                parentPos.valueCursor.afterLast();
+                
+                return null;
+            }
+            else
+            {
+                parentPos = newParentPos;
             }
         }
         else
@@ -657,91 +748,104 @@ public class TupleCursorImpl<K, V> imple
         tuple.setKey( leaf.keys[parentPos.pos] );
         
         // The value
-        if ( allowDuplicates )
-        {
-            MultipleMemoryHolder mvHolder = ( MultipleMemoryHolder<V, V> ) leaf.values[parentPos.pos];
-
-            if( !mvHolder.isSingleValue() )
-            {
-                BTree<V, V> valueCursor = ( BTree ) mvHolder.getValue();
-                parentPos.valueCursor = valueCursor;
-                parentPos.dupPos = 0;
-            }
-            
-            TupleCursor<V, V> cursor = parentPos.valueCursor.browse();
-            cursor.beforeFirst();
-            
-            V value = cursor.next().getKey();
-            tuple.setValue( value );
-        }
-        else
-        {
-            V value = leaf.values[parentPos.pos].getValue();
-            tuple.setValue( value );
-        }
+        ValueHolder<V> valueHolder = leaf.values[parentPos.pos];
+        parentPos.valueCursor = valueHolder.getCursor();
+        V value = parentPos.valueCursor.next();
+        tuple.setValue( value );
 
         return tuple;
     }
 
 
     /**
-     * {@inheritDoc}
+     * {@inheritDoc} 
      */
-    public boolean hasPrevKey() throws EndOfFileExceededException, IOException
+    public Tuple<K, V> prev() 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;
+            throw new NoSuchElementException( "No more tuple present" );
         }
 
         ParentPos<K, V> parentPos = stack[depth];
 
-        if ( parentPos.page == null )
+        if ( ( parentPos.page == null ) || ( parentPos.pos == BEFORE_FIRST ) )
         {
-            // This is the end : no more key
-            return false;
+            // This is the end : no more value
+            throw new NoSuchElementException( "No more tuples present" );
         }
-        
-        if ( parentPos.pos == 0 )
+
+        if ( ( parentPos.pos == 0 ) && ( !parentPos.valueCursor.hasPrev() ) )
         {
-            // Beginning of the leaf. We have to go back into the stack up to the
+            // End 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 ) )
+            // we also need to check for the type of page cause
+            // findPrevParentPos will never return a null ParentPos
+            if ( ( parentPos == null ) || ( parentPos.page == null ) || ( parentPos.page instanceof Node ) )
             {
-                // This is the end : no more key
-                return false;
+                // This is the end : no more value
+                throw new NoSuchElementException( "No more tuples present" );
             }
-            else
+        }
+        
+        V value = null;
+        
+        if ( parentPos.valueCursor.hasPrev() )
+        {
+            // Deal with the AfterLast case
+            if ( parentPos.pos == AFTER_LAST )
             {
-                return true;
+                parentPos.pos = parentPos.page.getNbElems() - 1;
             }
+            
+            value = parentPos.valueCursor.prev();
         }
         else
         {
-            return true;
+            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 = ( ( Leaf<K, V> ) parentPos.page ).getValue( parentPos.pos );
+                    
+                    parentPos.valueCursor = valueHolder.getCursor();
+                    parentPos.valueCursor.afterLast();
+                    
+                    value = parentPos.valueCursor.prev();
+                }
+                catch ( IllegalArgumentException e )
+                {
+                    e.printStackTrace();
+                }
+            }
         }
+
+
+        Leaf<K, V> leaf = ( Leaf<K, V> ) ( parentPos.page );
+        tuple.setKey( leaf.keys[parentPos.pos] );
+        tuple.setValue( value );
+
+        return tuple;
     }
 
 
     /**
-     * Moves the cursor to the previous non-duplicate key
-     * If the BTree contains 
-     * 
-     *  <ul>
-     *    <li><1,0></li>
-     *    <li><1,1></li>
-     *    <li><2,0></li>
-     *    <li><2,1></li>
-     *  </ul>
-     *   
-     *  and cursor is present at <2,1> then the cursor will move to <1,1>
-     * 
-     * @throws EndOfFileExceededException
-     * @throws IOException
+     * {@inheritDoc}
      */
     public Tuple<K, V> prevKey() throws EndOfFileExceededException, IOException
     {
@@ -784,7 +888,6 @@ public class TupleCursorImpl<K, V> imple
             }
         }
         
-        
         // Update the Tuple 
         Leaf<K, V> leaf = ( Leaf<K, V> ) ( parentPos.page );
 
@@ -792,121 +895,26 @@ public class TupleCursorImpl<K, V> imple
         tuple.setKey( leaf.keys[parentPos.pos] );
 
         // The value
-        if ( allowDuplicates )
-        {
-            MultipleMemoryHolder mvHolder = ( MultipleMemoryHolder<V, V> ) leaf.values[parentPos.pos];
-
-            if( !mvHolder.isSingleValue() )
-            {
-                parentPos.valueCursor = ( BTree ) mvHolder.getValue();
-                parentPos.dupPos = 0;
-            }
-            
-            TupleCursor<V, V> cursor = parentPos.valueCursor.browse();
-            cursor.beforeFirst();
-            
-            V value = cursor.next().getKey();
-            tuple.setValue( value );
-        }
-        else
-        {
-            V value = leaf.values[parentPos.pos].getValue();
-            tuple.setValue( value );
-        }
+        ValueHolder<V> valueHolder = leaf.values[parentPos.pos];
+        parentPos.valueCursor = valueHolder.getCursor();
+        V value = parentPos.valueCursor.next();
+        tuple.setValue( value );
         
         return tuple;
     }
-
-
-    /**
-     * {@inheritDoc}
-     */
-    public void beforeFirst() throws IOException
+    
+    
+    public String toString()
     {
-        // First check that we have elements in the BTree
-        if ( ( stack == null ) || ( stack.length == 0 ) )
-        {
-            return;
-        }
-
-        Page<K, V> child = null;
-
-        for ( int i = 0; i < depth; i++ )
-        {
-            ParentPos<K, V> parentPos = stack[i];
-            parentPos.pos = 0;
-
-            if ( child != null )
-            {
-                parentPos.page = child;
-            }
-
-            child = ((Node<K, V>)parentPos.page).children[0].getValue();
-        }
+        StringBuilder sb = new StringBuilder();
         
-        // and leaf
-        ParentPos<K, V> parentPos = stack[depth];
-        parentPos.pos = BEFORE_FIRST;
-
-        if ( child != null )
-        {
-            parentPos.page = child;
-        }
-
-        if ( allowDuplicates )
-        {
-            setDupsContainer( parentPos, btree );
-        }
-    }
-
-
-    /**
-     * Places the cursor at the end of the last position
-     * 
-     * @throws IOException
-     */
-    public void afterLast() throws IOException
-    {
-        // First check that we have elements in the BTree
-        if ( ( stack == null ) || ( stack.length == 0 ) )
-        {
-            return;
-        }
-
-        Page<K, V> child = null;
-
-        // Go fown the tree picking the rightmost element of each Node
-        for ( int i = 0; i < depth; i++ )
-        {
-            ParentPos<K, V> parentPos = stack[i];
-            
-            if ( child != null )
-            {
-                parentPos.page = child;
-                parentPos.pos = ((Node<K, V>)child).nbElems;
-            }
-            else
-            {
-                // We have N+1 children if the page is a Node, so we don't decrement the nbElems field
-                parentPos.pos = ((Node<K, V>)parentPos.page).nbElems;
-            }
-
-            child = ((Node<K, V>)parentPos.page).children[parentPos.pos].getValue();
-        }
+        sb.append( "TupleCursor, depth = " ).append( depth ).append( "\n" );
         
-        // and now, the leaf
-        ParentPos<K, V> parentPos = stack[depth];
-
-        if ( child != null )
+        for ( int i = 0; i <= depth; i++ )
         {
-            parentPos.page = child;
-        }
-
-        parentPos.pos = AFTER_LAST;
-
-        if ( allowDuplicates )
-        {
-            setDupsContainer( parentPos, btree );
+            sb.append( "    " ).append( stack[i] ).append( "\n" );
         }
+        
+        return sb.toString();
     }
 }



Mime
View raw message