/*
    *  Licensed to the Apache Software Foundation (ASF) under one
    *  or more contributor license agreements.  See the NOTICE file
    *  distributed with this work for additional information
    *  regarding copyright ownership.  The ASF licenses this file
    *  to you under the Apache License, Version 2.0 (the
    *  "License"); you may not use this file except in compliance
    *  with the License.  You may obtain a copy of the License at
    *
   *    http://www.apache.org/licenses/LICENSE-2.0
   *
   *  Unless required by applicable law or agreed to in writing,
   *  software distributed under the License is distributed on an
   *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
   *  KIND, either express or implied.  See the License for the
   *  specific language governing permissions and limitations
   *  under the License.
   *
   */
  package org.apache.directory.mavibot.btree;
  
  
  import java.io.IOException;
  import java.lang.reflect.Array;
  import java.util.List;
  
  
  /**
   * A MVCC Node. It stores the keys and references to its children page. It does not
   * contain any value.
   *
   * @param <K> The type for the Key
   * @param <V> The type for the stored value
   *
   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
   */
  /* No qualifier */class InMemoryNode<K, V> extends AbstractPage<K, V>
  {
      /**
       * 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 nbElems The number of elements in this Node
       */
      @SuppressWarnings("unchecked")
      InMemoryNode( BTree<K, V> btree, long revision, int nbElems )
      {
          super( btree, revision, nbElems );
  
          // Create the children array
          children = ( PageHolder<K, V>[] ) Array.newInstance( PageHolder.class, nbElems + 1 );
      }
  
  
      /**
       * 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")
      InMemoryNode( BTree<K, V> btree, long revision, K key, Page<K, V> leftPage, Page<K, V> rightPage )
      {
          super( btree, revision, 1 );
  
          // Create the children array, and store the left and right children
          children = ( PageHolder[] ) Array.newInstance( PageHolder.class, btree.getPageSize() + 1 );
  
          children[0] = new PageHolder<K, V>( btree, leftPage );
          children[1] = new PageHolder<K, V>( btree, 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...
          setKeys( ( KeyHolder<K>[] ) Array.newInstance( KeyHolder.class, btree.getPageSize() ) );
  
          setKey( 0, new KeyHolder<K>( key ) );
      }
  
  
      /**
       * {@inheritDoc}
       */
      public InsertResult<K, V> insert( K key, V value, long revision ) throws IOException
      {
          // Find the key into this leaf
          int pos = findPos( key );
  
          if ( pos < 0 )
          {
              // The key has been found in the page. As it's a Node, that means
             // we must go down in the right child to insert the value
             pos = -( pos++ );
         }
 
         // Get the child page into which we will insert the <K, V> tuple
         Page<K, V> child = children[pos].getValue();
 
         // and insert the <K, V> into this child
         InsertResult<K, V> result = child.insert( key, value, revision );
 
         // Ok, now, we have injected the <K, V> tuple down the tree. Let's check
         // the result to see if we have to split the current page
         if ( result instanceof ModifyResult )
         {
             // The child has been modified.
             return replaceChild( revision, ( ModifyResult<K, V> ) result, pos );
         }
         else
         {
             // The child has been split. We have to insert the new pivot in the
             // current page, and to reference the two new pages
             SplitResult<K, V> splitResult = ( SplitResult<K, V> ) result;
             K pivot = splitResult.getPivot();
             Page<K, V> leftPage = splitResult.getLeftPage();
             Page<K, V> rightPage = splitResult.getRightPage();
 
             // We have to deal with the two cases :
             // - the current page is full, we have to split it
             // - the current page is not full, we insert the new pivot
             if ( nbElems == btree.getPageSize() )
             {
                 // The page is full
                 result = addAndSplit( splitResult.getCopiedPages(), revision, pivot, leftPage, rightPage, pos );
             }
             else
             {
                 // The page can contain the new pivot, let's insert it
                 result = insertChild( splitResult.getCopiedPages(), revision, pivot, leftPage, rightPage, pos );
             }
 
             return result;
         }
     }
 
 
     /**
      * Modifies the current node after a remove has been done in one of its children.
      * The node won't be merged with another node.
      *
      * @param removeResult The result of a remove operation
      * @param index the position of the key, not transformed
      * @param pos The position of the key, as a positive value
      * @param found If the key has been found in the page
      * @return The new result
      * @throws IOException If we have an error while trying to access the page
      */
     private RemoveResult<K, V> handleRemoveResult( RemoveResult<K, V> removeResult, int index, int pos, boolean found )
         throws IOException
     {
         // Simplest case : the element has been removed from the underlying page,
         // we just have to copy the current page an modify the reference to link to
         // the modified page.
         InMemoryNode<K, V> newPage = copy( revision );
 
         Page<K, V> modifiedPage = removeResult.getModifiedPage();
 
         if ( found )
         {
             newPage.children[index + 1] = new PageHolder<K, V>( btree, modifiedPage );
         }
         else
         {
             newPage.children[index] = new PageHolder<K, V>( btree, modifiedPage );
         }
 
         if ( pos < 0 )
         {
             newPage.setKey( index, new KeyHolder<K>( removeResult.getModifiedPage().getLeftMostKey() ) );
         }
 
         // Modify the result and return
         removeResult.setModifiedPage( newPage );
         removeResult.addCopiedPage( this );
 
         return removeResult;
     }
 
 
     /**
      * Handles the removal of an element from the root page, when two of its children
      * have been merged.
      *
      * @param mergedResult The merge result
      * @param pos The position in the current root
      * @param found Tells if the removed key is present in the root page
      * @return The resulting root page
      * @throws IOException If we have an error while trying to access the page
      */
     private RemoveResult<K, V> handleRootRemove( MergedWithSiblingResult<K, V> mergedResult, int pos, boolean found )
         throws IOException
     {
         RemoveResult<K, V> removeResult = null;
 
         // If the current node contains only one key, then the merged result will be
         // the new root. Deal with this case
         if ( nbElems == 1 )
         {
             removeResult = new RemoveResult<K, V>( mergedResult.getCopiedPages(), mergedResult.getModifiedPage(),
                 mergedResult.getRemovedElement() );
 
             removeResult.addCopiedPage( this );
         }
         else
         {
             // Remove the element and update the reference to the changed pages
             removeResult = removeKey( mergedResult, revision, pos );
         }
 
         return removeResult;
     }
 
 
     /**
      * Borrows an element from the right sibling, creating a new sibling with one
      * less element and creating a new page where the element to remove has been
      * deleted and the borrowed element added on the right.
      *
      * @param revision The new revision for all the pages
      * @param sibling The right sibling
      * @param pos The position of the element to remove
      * @return The resulting pages
      * @throws IOException If we have an error while trying to access the page
      */
     private DeleteResult<K, V> borrowFromRight( long revision, MergedWithSiblingResult<K, V> mergedResult,
         InMemoryNode<K, V> sibling, int pos ) throws IOException
     {
         // Create the new sibling, with one less element at the beginning
         InMemoryNode<K, V> newSibling = new InMemoryNode<K, V>( btree, revision, sibling.getNbElems() - 1 );
 
         K siblingKey = sibling.children[0].getValue().getLeftMostKey();
 
         // Copy the keys and children of the old sibling in the new sibling
         System.arraycopy( sibling.getKeys(), 1, newSibling.getKeys(), 0, newSibling.getNbElems() );
         System.arraycopy( sibling.children, 1, newSibling.children, 0, newSibling.getNbElems() + 1 );
 
         // Create the new page and add the new element at the end
         // First copy the current node, with the same size
         InMemoryNode<K, V> newNode = new InMemoryNode<K, V>( btree, revision, nbElems );
 
         // Copy the keys and the values up to the insertion position
         int index = Math.abs( pos );
 
         // Copy the key and children from sibling
         newNode.setKey( nbElems - 1, new KeyHolder<K>( siblingKey ) ); // 1
         newNode.children[nbElems] = sibling.children[0]; // 8
 
         if ( index < 2 )
         {
             // Copy the keys
             System.arraycopy( getKeys(), 1, newNode.getKeys(), 0, nbElems - 1 );
 
             // Inject the modified page
             Page<K, V> modifiedPage = mergedResult.getModifiedPage();
             newNode.children[0] = new PageHolder<K, V>( btree, modifiedPage );
 
             // Copy the children
             System.arraycopy( children, 2, newNode.children, 1, nbElems - 1 );
         }
         else
         {
             if ( index > 2 )
             {
                 // Copy the keys before the deletion point
                 System.arraycopy( getKeys(), 0, newNode.getKeys(), 0, index - 2 ); // 4
             }
 
             // Inject the new modified page key
             newNode.setKey( index - 2, new KeyHolder<K>( mergedResult.getModifiedPage().getLeftMostKey() ) ); // 2
 
             if ( index < nbElems )
             {
                 // Copy the remaining keys after the deletion point
                 System.arraycopy( getKeys(), index, newNode.getKeys(), index - 1, nbElems - index ); // 3
 
                 // Copy the remaining children after the deletion point
                 System.arraycopy( children, index + 1, newNode.children, index, nbElems - index ); // 7
             }
 
             // Copy the children before the deletion point
             System.arraycopy( children, 0, newNode.children, 0, index - 1 ); // 5
 
             // Inject the modified page
             Page<K, V> modifiedPage = mergedResult.getModifiedPage();
             newNode.children[index - 1] = new PageHolder<K, V>( btree, modifiedPage ); // 6
         }
 
         // Create the result
         DeleteResult<K, V> result = new BorrowedFromRightResult<K, V>( mergedResult.getCopiedPages(), newNode,
             newSibling, mergedResult.getRemovedElement() );
 
         result.addCopiedPage( this );
         result.addCopiedPage( sibling );
 
         return result;
     }
 
 
     /**
      * Borrows an element from the left sibling, creating a new sibling with one
      * less element and creating a new page where the element to remove has been
      * deleted and the borrowed element added on the left.
      *
      * @param revision The new revision for all the pages
      * @param sibling The left sibling
      * @param pos The position of the element to remove
      * @return The resulting pages
      * @throws IOException If we have an error while trying to access the page
      */
     private DeleteResult<K, V> borrowFromLeft( long revision, MergedWithSiblingResult<K, V> mergedResult,
         InMemoryNode<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();
 
         // Create the new sibling, with one less element at the end
         InMemoryNode<K, V> newSibling = new InMemoryNode<K, V>( btree, revision, sibling.getNbElems() - 1 );
 
         // Copy the keys and children of the old sibling in the new sibling
         System.arraycopy( sibling.getKeys(), 0, newSibling.getKeys(), 0, newSibling.getNbElems() );
         System.arraycopy( sibling.children, 0, newSibling.children, 0, newSibling.getNbElems() + 1 );
 
         // Create the new page and add the new element at the beginning
         // First copy the current node, with the same size
         InMemoryNode<K, V> newNode = new InMemoryNode<K, V>( btree, revision, nbElems );
 
         // Sets the first children
         newNode.children[0] = new PageHolder<K, V>( btree, siblingChild ); //1
 
         int index = Math.abs( pos );
 
         if ( index < 2 )
         {
             newNode.setKey( 0, new KeyHolder<K>( mergedResult.getModifiedPage().getLeftMostKey() ) );
             System.arraycopy( getKeys(), 1, newNode.getKeys(), 1, nbElems - 1 );
 
             Page<K, V> modifiedPage = mergedResult.getModifiedPage();
             newNode.children[1] = new PageHolder<K, V>( btree, modifiedPage );
             System.arraycopy( children, 2, newNode.children, 2, nbElems - 1 );
         }
         else
         {
             // Set the first key
             newNode.setKey( 0, new KeyHolder<K>( children[0].getValue().getLeftMostKey() ) ); //2
 
             if ( index > 2 )
             {
                 // Copy the keys before the deletion point
                 System.arraycopy( getKeys(), 0, newNode.getKeys(), 1, index - 2 ); // 4
             }
 
             // Inject the modified key
             newNode.setKey( index - 1, new KeyHolder<K>( mergedResult.getModifiedPage().getLeftMostKey() ) ); // 3
 
             if ( index < nbElems )
             {
                 // Add copy the remaining keys after the deletion point
                 System.arraycopy( getKeys(), index, newNode.getKeys(), index, nbElems - index ); // 5
 
                 // Copy the remaining children after the insertion point
                 System.arraycopy( children, index + 1, newNode.children, index + 1, nbElems - index ); // 8
             }
 
             // Copy the children before the insertion point
             System.arraycopy( children, 0, newNode.children, 1, index - 1 ); // 6
 
             // Insert the modified page
             Page<K, V> modifiedPage = mergedResult.getModifiedPage();
             newNode.children[index] = new PageHolder<K, V>( btree, modifiedPage ); // 7
         }
 
         // Create the result
         DeleteResult<K, V> result = new BorrowedFromLeftResult<K, V>( mergedResult.getCopiedPages(), newNode,
             newSibling,
             mergedResult.getRemovedElement() );
 
         result.addCopiedPage( this );
         result.addCopiedPage( sibling );
 
         return result;
     }
 
 
     /**
      * We have to merge the node with its sibling, both have N/2 elements before the element
      * removal.
      *
      * @param revision The revision
      * @param mergedResult The result of the merge
      * @param sibling The Page we will merge the current page with
      * @param isLeft Tells if the sibling is on the left
      * @param pos The position of the key that has been removed
      * @return The page resulting of the merge
      * @throws IOException If we have an error while trying to access the page
      */
     private DeleteResult<K, V> mergeWithSibling( long revision, MergedWithSiblingResult<K, V> mergedResult,
         InMemoryNode<K, V> sibling, boolean isLeft, int pos ) throws IOException
     {
         // Create the new node. It will contain N - 1 elements (the maximum number)
         // as we merge two nodes that contain N/2 elements minus the one we remove
         InMemoryNode<K, V> newNode = new InMemoryNode<K, V>( btree, revision, btree.getPageSize() );
         Tuple<K, V> removedElement = mergedResult.getRemovedElement();
         int half = btree.getPageSize() / 2;
         int index = Math.abs( pos );
 
         if ( isLeft )
         {
             // The sibling is on the left. Copy all of its elements in the new node first
             System.arraycopy( sibling.getKeys(), 0, newNode.getKeys(), 0, half ); //1
             System.arraycopy( sibling.children, 0, newNode.children, 0, half + 1 ); //2
 
             // Then copy all the elements up to the deletion point
             if ( index < 2 )
             {
                 newNode.setKey( half, new KeyHolder<K>( mergedResult.getModifiedPage().getLeftMostKey() ) );
                 System.arraycopy( getKeys(), 1, newNode.getKeys(), half + 1, half - 1 );
 
                 Page<K, V> modifiedPage = mergedResult.getModifiedPage();
                 newNode.children[half + 1] = new PageHolder<K, V>( btree, 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.setKey( half, new KeyHolder<K>( children[0].getValue().getLeftMostKey() ) ); // 3
 
                 if ( index > 2 )
                 {
                     System.arraycopy( getKeys(), 0, newNode.getKeys(), half + 1, index - 2 ); //4
                 }
 
                 // Inject the new merged key
                 newNode.setKey( half + index - 1, new KeyHolder<K>( mergedResult.getModifiedPage().getLeftMostKey() ) ); //5
 
                 if ( index < half )
                 {
                     System.arraycopy( getKeys(), index, newNode.getKeys(), half + index, half - index ); //6
                     System.arraycopy( children, index + 1, newNode.children, half + index + 1, half - index ); //9
                 }
 
                 // Copy the children before the deletion point
                 System.arraycopy( children, 0, newNode.children, half + 1, index - 1 ); // 7
 
                 // Inject the new merged child
                 Page<K, V> modifiedPage = mergedResult.getModifiedPage();
                 newNode.children[half + index] = new PageHolder<K, V>( btree, modifiedPage ); //8
             }
         }
         else
         {
             // The sibling is on the right.
             if ( index < 2 )
             {
                 // Copy the keys
                 System.arraycopy( getKeys(), 1, newNode.getKeys(), 0, half - 1 );
 
                 // Insert the first child
                 Page<K, V> modifiedPage = mergedResult.getModifiedPage();
                 newNode.children[0] = new PageHolder<K, V>( btree, modifiedPage );
 
                 // Copy the node children
                 System.arraycopy( children, 2, newNode.children, 1, half - 1 );
             }
             else
             {
                 // Copy the keys and children before the deletion point
                 if ( index > 2 )
                 {
                     // Copy the first keys
                     System.arraycopy( getKeys(), 0, newNode.getKeys(), 0, index - 2 ); //1
                 }
 
                 // Copy the first children
                 System.arraycopy( children, 0, newNode.children, 0, index - 1 ); //6
 
                 // Inject the modified key
                 newNode.setKey( index - 2, new KeyHolder<K>( mergedResult.getModifiedPage().getLeftMostKey() ) ); //2
 
                 // Inject the modified children
                 Page<K, V> modifiedPage = mergedResult.getModifiedPage();
                 newNode.children[index - 1] = new PageHolder<K, V>( btree, modifiedPage ); // 7
 
                 // Add the remaining node's key if needed
                 if ( index < half )
                 {
                     System.arraycopy( getKeys(), index, newNode.getKeys(), index - 1, half - index ); //5
 
                     // Add the remining children if below half
                     System.arraycopy( children, index + 1, newNode.children, index, half - index ); // 8
                 }
             }
 
             // Inject the new key from sibling
             newNode.setKey( half - 1, new KeyHolder<K>( sibling.findLeftMost().getKey() ) ); //3
 
             // Copy the sibling keys
             System.arraycopy( sibling.getKeys(), 0, newNode.getKeys(), half, half );
 
             // Add the sibling children
             System.arraycopy( sibling.children, 0, newNode.children, half, half + 1 ); // 9
         }
 
         // And create the result
         DeleteResult<K, V> result = new MergedWithSiblingResult<K, V>( mergedResult.getCopiedPages(), newNode,
             removedElement );
 
         result.addCopiedPage( this );
         result.addCopiedPage( sibling );
 
         return result;
     }
 
 
     /**
      * {@inheritDoc}
      */
     /* no qualifier */ DeleteResult<K, V> delete( K key, V value, long revision, Page<K, V> parent, int parentPos )
         throws IOException
     {
         // We first try to delete the element from the child it belongs to
         // Find the key in the page
         int pos = findPos( key );
         boolean found = pos < 0;
         int index = pos;
         Page<K, V> child = null;
         DeleteResult<K, V> deleteResult = null;
 
         if ( found )
         {
             index = -( pos + 1 );
             child = children[-pos].getValue();
             deleteResult = ((AbstractPage<K, V>)child).delete( key, value, revision, this, -pos );
         }
         else
         {
             child = children[pos].getValue();
             deleteResult = ((AbstractPage<K, V>)child).delete( key, value, revision, this, pos );
         }
 
         // If the key is not present in the tree, we simply return
         if ( deleteResult instanceof NotPresentResult )
         {
             // Nothing to do...
             return deleteResult;
         }
 
         // If we just modified the child, return a modified page
         if ( deleteResult instanceof RemoveResult )
         {
             RemoveResult<K, V> removeResult = handleRemoveResult( ( RemoveResult<K, V> ) deleteResult, index, pos,
                 found );
 
             return removeResult;
         }
 
         // If we had to borrow an element in the child, then have to update
         // the current page
         if ( deleteResult instanceof BorrowedFromSiblingResult )
         {
             RemoveResult<K, V> removeResult = handleBorrowedResult( ( BorrowedFromSiblingResult<K, V> ) deleteResult,
                 pos );
 
             return removeResult;
         }
 
         // Last, not least, we have merged two child pages. We now have to remove
         // an element from the local page, and to deal with the result.
         if ( deleteResult instanceof MergedWithSiblingResult )
         {
             MergedWithSiblingResult<K, V> mergedResult = ( MergedWithSiblingResult<K, V> ) deleteResult;
 
             // If the parent is null, then this page is the root page.
             if ( parent == null )
             {
                 RemoveResult<K, V> result = handleRootRemove( mergedResult, pos, found );
 
                 return result;
             }
 
             // We have some parent. Check if the current page is not half full
             int halfSize = btree.getPageSize() / 2;
 
             if ( nbElems > halfSize )
             {
                 // The page has more than N/2 elements.
                 // We simply remove the element from the page, and if it was the leftmost,
                 // we return the new pivot (it will replace any instance of the removed
                 // key in its parents)
                 RemoveResult<K, V> result = removeKey( mergedResult, revision, pos );
 
                 return result;
             }
             else
             {
                 // We will remove one element from a page that will have less than N/2 elements,
                 // which will lead to some reorganization : either we can borrow an element from
                 // a sibling, or we will have to merge two pages
                 int siblingPos = selectSibling( parent, parentPos );
 
                 InMemoryNode<K, V> sibling = ( InMemoryNode<K, V> ) ( ( ( InMemoryNode<K, V> ) parent ).children[siblingPos]
                     .getValue() );
 
                 if ( sibling.getNbElems() > halfSize )
                 {
                     // The sibling contains enough elements
                     // We can borrow the element from the sibling
                     if ( siblingPos < parentPos )
                     {
                         DeleteResult<K, V> result = borrowFromLeft( revision, mergedResult, sibling, pos );
 
                         return result;
                     }
                     else
                     {
                         // Borrow from the right
                         DeleteResult<K, V> result = borrowFromRight( revision, mergedResult, sibling, pos );
 
                         return result;
                     }
                 }
                 else
                 {
                     // We need to merge the sibling with the current page
                     DeleteResult<K, V> result = mergeWithSibling( revision, mergedResult, sibling,
                         ( siblingPos < parentPos ), pos );
 
                     return result;
                 }
             }
         }
 
         // We should never reach this point
         return null;
     }
 
 
     /**
      * The deletion in a children has moved an element from one of its sibling. The key
      * is present in the current node.
      * @param borrowedResult The result of the deletion from the children
      * @param pos The position the key was found in the current node
      * @return The result
      * @throws IOException If we have an error while trying to access the page
      */
     private RemoveResult<K, V> handleBorrowedResult( BorrowedFromSiblingResult<K, V> borrowedResult, int pos )
         throws IOException
     {
         Page<K, V> modifiedPage = borrowedResult.getModifiedPage();
         Page<K, V> modifiedSibling = borrowedResult.getModifiedSibling();
 
         InMemoryNode<K, V> newPage = copy( revision );
 
         if ( pos < 0 )
         {
             pos = -( pos + 1 );
 
             if ( borrowedResult.isFromRight() )
             {
                 // Update the keys
                 newPage.setKey( pos, new KeyHolder<K>( modifiedPage.findLeftMost().getKey() ) );
                 newPage.setKey( pos + 1, new KeyHolder<K>( modifiedSibling.findLeftMost().getKey() ) );
 
                 // Update the children
                 newPage.children[pos + 1] = new PageHolder<K, V>( btree, modifiedPage );
                 newPage.children[pos + 2] = new PageHolder<K, V>( btree, modifiedSibling );
             }
             else
             {
                 // Update the keys
                 newPage.setKey( pos, new KeyHolder<K>( modifiedPage.findLeftMost().getKey() ) );
 
                 // Update the children
                 newPage.children[pos] = new PageHolder<K, V>( btree, modifiedSibling );
                 newPage.children[pos + 1] = new PageHolder<K, V>( btree, modifiedPage );
             }
         }
         else
         {
             if ( borrowedResult.isFromRight() )
             {
                 // Update the keys
                 newPage.setKey( pos, new KeyHolder<K>( modifiedSibling.findLeftMost().getKey() ) );
 
                 // Update the children
                 newPage.children[pos] = new PageHolder<K, V>( btree, modifiedPage );
                 newPage.children[pos + 1] = new PageHolder<K, V>( btree, modifiedSibling );
             }
             else
             {
                 // Update the keys
                 newPage.setKey( pos - 1, new KeyHolder<K>( modifiedPage.findLeftMost().getKey() ) );
 
                 // Update the children
                 newPage.children[pos - 1] = new PageHolder<K, V>( btree, modifiedSibling );
                 newPage.children[pos] = new PageHolder<K, V>( btree, modifiedPage );
             }
         }
 
         // Modify the result and return
         RemoveResult<K, V> removeResult = new RemoveResult<K, V>( borrowedResult.getCopiedPages(), newPage,
             borrowedResult.getRemovedElement() );
 
         removeResult.addCopiedPage( this );
 
         return removeResult;
     }
 
 
     /**
      * Remove the key at a given position.
      *
      * @param mergedResult The page we will remove a key from
      * @param revision The revision of the modified page
      * @param pos The position into the page of the element to remove
      * @return The modified page with the <K,V> element added
      * @throws IOException If we have an error while trying to access the page
      */
     private RemoveResult<K, V> removeKey( MergedWithSiblingResult<K, V> mergedResult, long revision, int pos )
         throws IOException
     {
         // First copy the current page, but remove one element in the copied page
         InMemoryNode<K, V> newNode = new InMemoryNode<K, V>( btree, revision, nbElems - 1 );
 
         int index = Math.abs( pos ) - 2;
 
         //
         if ( index < 0 )
         {
             // Copy the keys and the children
             System.arraycopy( getKeys(), 1, newNode.getKeys(), 0, newNode.nbElems );
             Page<K, V> modifiedPage = mergedResult.getModifiedPage();
             newNode.children[0] = new PageHolder<K, V>( btree, modifiedPage );
             System.arraycopy( children, 2, newNode.children, 1, nbElems - 1 );
         }
         else
         {
             // Copy the keys
             if ( index > 0 )
             {
                 System.arraycopy( getKeys(), 0, newNode.getKeys(), 0, index );
             }
 
             newNode.setKey( index, new KeyHolder<K>( mergedResult.getModifiedPage().findLeftMost().getKey() ) );
 
             if ( index < nbElems - 2 )
             {
                 System.arraycopy( getKeys(), index + 2, newNode.getKeys(), index + 1, nbElems - index - 2 );
             }
 
             // Copy the children
             System.arraycopy( children, 0, newNode.children, 0, index + 1 );
 
             Page<K, V> modifiedPage = mergedResult.getModifiedPage();
             newNode.children[index + 1] = new PageHolder<K, V>( btree, modifiedPage );
 
             if ( index < nbElems - 2 )
             {
                 System.arraycopy( children, index + 3, newNode.children, index + 2, nbElems - index - 2 );
             }
         }
 
         // Create the result
         RemoveResult<K, V> result = new RemoveResult<K, V>( mergedResult.getCopiedPages(), newNode,
             mergedResult.getRemovedElement() );
 
         result.addCopiedPage( this );
 
         return result;
     }
 
 
     /**
      * Set the value at a give position
      *
      * @param pos The position in the values array
      * @param value the value to inject
      */
     /* no qualifier */void setValue( int pos, Page<K, V> value )
     {
         children[pos] = new PageHolder<K, V>( btree, value );
     }
 
 
     /**
      * This method is used when we have to replace a child in a page when we have
      * found the key in the tree (the value will be changed, so we have made
      * copies of the existing pages).
      *
      * @param revision The current revision
      * @param result The modified page
      * @param pos The position of the found key
      * @return A modified page
      * @throws IOException If we have an error while trying to access the page
      */
     private InsertResult<K, V> replaceChild( long revision, ModifyResult<K, V> result, int pos ) throws IOException
     {
         // Just copy the current page and update its revision
         Page<K, V> newPage = copy( revision );
 
         // Last, we update the children table of the newly created page
         // to point on the modified child
         Page<K, V> modifiedPage = result.getModifiedPage();
 
         ( ( InMemoryNode<K, V> ) newPage ).children[pos] = new PageHolder<K, V>( btree, modifiedPage );
 
         // We can return the result, where we update the modifiedPage,
         // to avoid the creation of a new object
         result.setModifiedPage( newPage );
 
         result.addCopiedPage( this );
 
         return result;
     }
 
 
     /**
      * 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.
      *
      * @param copiedPages the list of copied pages
      * @param revision The revision of the modified page
      * @param key The key to insert
      * @param leftPage The left child
      * @param rightPage The right child
      * @param pos The position into the page
      * @return The modified page with the <K,V> element added
      * @throws IOException If we have an error while trying to access the page
      */
     private InsertResult<K, V> insertChild( List<Page<K, V>> copiedPages, long revision, K key, Page<K, V> leftPage,
         Page<K, V> rightPage, int pos )
         throws IOException
     {
         // First copy the current page, but add one element in the copied page
         InMemoryNode<K, V> newNode = new InMemoryNode<K, V>( btree, revision, nbElems + 1 );
 
         // Copy the keys and the children up to the insertion position
         if ( nbElems > 0 )
         {
             System.arraycopy( getKeys(), 0, newNode.getKeys(), 0, pos );
             System.arraycopy( children, 0, newNode.children, 0, pos );
         }
 
         // Add the new key and children
         newNode.setKey( pos, new KeyHolder<K>( key ) );
 
         // 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] = new PageHolder<K, V>( btree, leftPage );
         newNode.children[pos + 1] = new PageHolder<K, V>( btree, rightPage );
 
         // And copy the remaining keys and children
         if ( nbElems > 0 )
         {
             System.arraycopy( getKeys(), pos, newNode.getKeys(), pos + 1, getKeys().length - pos );
             System.arraycopy( children, pos + 1, newNode.children, pos + 2, children.length - pos - 1 );
         }
 
         // Create the result
         InsertResult<K, V> result = new ModifyResult<K, V>( copiedPages, newNode, null );
         result.addCopiedPage( this );
 
         return result;
     }
 
 
     /**
      * Splits a full page into two new pages, a left, a right and a pivot element. The new pages will
      * each contains half of the original elements. <br/>
      * The pivot will be computed, depending on the place
      * we will inject the newly added element. <br/>
      * If the newly added element is in the middle, we will use it
      * as a pivot. Otherwise, we will use either the last element in the left page if the element is added
      * on the left, or the first element in the right page if it's added on the right.
      *
      * @param copiedPages the list of copied pages
      * @param revision The new revision for all the created pages
      * @param pivot The key that will be move up after the split
      * @param leftPage The left child
      * @param rightPage The right child
      * @param pos The position of the insertion of the new element
      * @return An OverflowPage containing the pivot, and the new left and right pages
      * @throws IOException If we have an error while trying to access the page
      */
     private InsertResult<K, V> addAndSplit( List<Page<K, V>> copiedPages, long revision, K pivot, Page<K, V> leftPage,
         Page<K, V> rightPage, int pos ) throws IOException
     {
         int middle = btree.getPageSize() >> 1;
 
         // Create two new pages
         InMemoryNode<K, V> newLeftPage = new InMemoryNode<K, V>( btree, revision, middle );
         InMemoryNode<K, V> newRightPage = new InMemoryNode<K, V>( btree, revision, middle );
 
         // Determinate where to store the new value
         // If it's before the middle, insert the value on the left,
         // the key in the middle will become the new pivot
         if ( pos < middle )
         {
             // Copy the keys and the children up to the insertion position
             System.arraycopy( getKeys(), 0, newLeftPage.getKeys(), 0, pos );
             System.arraycopy( children, 0, newLeftPage.children, 0, pos );
 
             // Add the new element
             newLeftPage.setKey( pos, new KeyHolder<K>( pivot ) );
             newLeftPage.children[pos] = new PageHolder<K, V>( btree, leftPage );
             newLeftPage.children[pos + 1] = new PageHolder<K, V>( btree, rightPage );
 
             // And copy the remaining elements minus the new pivot
             System.arraycopy( getKeys(), pos, newLeftPage.getKeys(), pos + 1, middle - pos - 1 );
             System.arraycopy( children, pos + 1, newLeftPage.children, pos + 2, middle - pos - 1 );
 
             // Copy the keys and the children in the right page
             System.arraycopy( getKeys(), middle, newRightPage.getKeys(), 0, middle );
             System.arraycopy( children, middle, newRightPage.children, 0, middle + 1 );
 
             // Create the result
             InsertResult<K, V> result = new SplitResult<K, V>( copiedPages, getKey( middle - 1 ), newLeftPage,
                 newRightPage );
             result.addCopiedPage( this );
 
             return result;
         }
         else if ( pos == middle )
         {
             // A special case : the pivot will be propagated up in the tree
             // The left and right pages will be spread on the two new pages
             // Copy the keys and the children up to the insertion position (here, middle)
             System.arraycopy( getKeys(), 0, newLeftPage.getKeys(), 0, middle );
             System.arraycopy( children, 0, newLeftPage.children, 0, middle );
             newLeftPage.children[middle] = new PageHolder<K, V>( btree, leftPage );
 
             // And process the right page now
             System.arraycopy( getKeys(), middle, newRightPage.getKeys(), 0, middle );
             System.arraycopy( children, middle + 1, newRightPage.children, 1, middle );
             newRightPage.children[0] = new PageHolder<K, V>( btree, rightPage );
 
             // Create the result
             InsertResult<K, V> result = new SplitResult<K, V>( copiedPages, pivot, newLeftPage, newRightPage );
             result.addCopiedPage( this );
 
             return result;
         }
         else
         {
             // Copy the keys and the children up to the middle
             System.arraycopy( getKeys(), 0, newLeftPage.getKeys(), 0, middle );
             System.arraycopy( children, 0, newLeftPage.children, 0, middle + 1 );
 
             // Copy the keys and the children in the right page up to the pos
             System.arraycopy( getKeys(), middle + 1, newRightPage.getKeys(), 0, pos - middle - 1 );
             System.arraycopy( children, middle + 1, newRightPage.children, 0, pos - middle - 1 );
 
             // Add the new element
             newRightPage.setKey( pos - middle - 1, new KeyHolder<K>( pivot ) );
             newRightPage.children[pos - middle - 1] = new PageHolder<K, V>( btree, leftPage );
             newRightPage.children[pos - middle] = new PageHolder<K, V>( btree, rightPage );
 
             // And copy the remaining elements minus the new pivot
             System.arraycopy( getKeys(), pos, newRightPage.getKeys(), pos - middle, nbElems - pos );
             System.arraycopy( children, pos + 1, newRightPage.children, pos + 1 - middle, nbElems - pos );
 
             // Create the result
             InsertResult<K, V> result = new SplitResult<K, V>( copiedPages, getKey( middle ), newLeftPage, newRightPage );
             result.addCopiedPage( this );
 
             return result;
         }
     }
 
 
     /**
      * Copies the current page and all its keys, with a new revision.
      *
      * @param revision The new revision
      * @return The copied page
      */
     protected InMemoryNode<K, V> copy( long revision )
     {
         InMemoryNode<K, V> newPage = new InMemoryNode<K, V>( btree, revision, nbElems );
 
         // Copy the keys
         System.arraycopy( getKeys(), 0, newPage.getKeys(), 0, nbElems );
 
         // Copy the children
         System.arraycopy( children, 0, newPage.children, 0, nbElems + 1 );
 
         return newPage;
     }
 
 
     /**
      * {@inheritDoc}
      */
     public K getLeftMostKey()
     {
         return children[0].getValue().getLeftMostKey();
     }
 
 
     /**
      * {@inheritDoc}
      */
     public K getRightMostKey()
     {
         int index = ( nbElems + 1 ) - 1;
 
         if ( children[index] != null )
         {
             return children[index].getValue().getRightMostKey();
         }
 
         return children[nbElems - 1].getValue().getRightMostKey();
     }
 
 
     /**
      * {@inheritDoc}
      */
     public boolean isLeaf()
     {
         return false;
     }
 
 
     /**
      * {@inheritDoc}
      */
     public boolean isNode()
     {
         return true;
     }
 
 
     /**
      * @see Object#toString()
      */
     public String toString()
     {
         StringBuilder sb = new StringBuilder();
 
         sb.append( "Node[" );
         sb.append( super.toString() );
         sb.append( "] -> {" );
 
         if ( nbElems > 0 )
         {
             // Start with the first child
             if ( children[0] == null )
             {
                 sb.append( "null" );
             }
             else
             {
                 sb.append( 'r' ).append( children[0].getValue().getRevision() );
             }
 
             for ( int i = 0; i < nbElems; i++ )
             {
                 sb.append( "|<" ).append( getKey( i ) ).append( ">|" );
 
                 if ( children[i + 1] == null )
                 {
                     sb.append( "null" );
                 }
                 else
                 {
                     sb.append( 'r' ).append( children[i + 1].getValue().getRevision() );
                 }
             }
         }
 
         sb.append( "}" );
 
         return sb.toString();
     }
 }