/*
    *  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.util.NoSuchElementException;
  
  import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
  
  
  /**
   * A Cursor is used to fetch only keys in a BTree and is returned by the
   * @see BTree#browseKeys method. The cursor <strng>must</strong> be closed
   * when the user is done with it.
   * <p>
   *
   * @param <K> The type for the Key
   *
   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
   */
  public class KeyCursor<K>
  {
      /** A marker to tell that we are before the first element */
      private static final int BEFORE_FIRST = -1;
  
      /** A marker to tell that we are after the last element */
      private static final int AFTER_LAST = -2;
  
      /** The stack of pages from the root down to the leaf */
      protected ParentPos<K, K>[] stack;
  
      /** The stack's depth */
      protected int depth = 0;
  
      /** The transaction used for this cursor */
      protected ReadTransaction<K, K> transaction;
  
  
      /**
       * Creates a new instance of Cursor.
       */
      protected KeyCursor()
      {
      }
  
  
      /**
       * Creates a new instance of Cursor, starting on a page at a given position.
       *
       * @param transaction The transaction this operation is protected by
       * @param stack The stack of parent's from root to this page
       */
      public KeyCursor( ReadTransaction<K, K> transaction, ParentPos<K, K>[] stack, int depth )
      {
          this.transaction = transaction;
          this.stack = stack;
          this.depth = depth;
      }
  
  
      /**
       * Change the position in the current cursor to set it after the last key
       */
      public void afterLast() throws IOException
      {
          // First check that we have elements in the BTree
          if ( ( stack == null ) || ( stack.length == 0 ) )
          {
              return;
          }
  
          Page<K, K> child = null;
  
          for ( int i = 0; i < depth; i++ )
          {
              ParentPos<K, K> parentPos = stack[i];
  
              if ( child != null )
              {
                  parentPos.page = child;
                  parentPos.pos = child.getNbElems();
             }
             else
             {
                 // We have N+1 children if the page is a Node, so we don't decrement the nbElems field
                 parentPos.pos = parentPos.page.getNbElems();
             }
 
             child = ( ( AbstractPage<K, K> ) parentPos.page ).getPage( parentPos.pos );
         }
 
         // and leaf
         ParentPos<K, K> parentPos = stack[depth];
 
         if ( child == null )
         {
             parentPos.pos = parentPos.page.getNbElems() - 1;
         }
         else
         {
             parentPos.page = child;
             parentPos.pos = child.getNbElems() - 1;
         }
 
         parentPos.pos = AFTER_LAST;
     }
 
 
     /**
      * Change the position in the current cursor before the first key
      */
     public void beforeFirst() throws IOException
     {
         // First check that we have elements in the BTree
         if ( ( stack == null ) || ( stack.length == 0 ) )
         {
             return;
         }
 
         Page<K, K> child = null;
 
         for ( int i = 0; i < depth; i++ )
         {
             ParentPos<K, K> parentPos = stack[i];
             parentPos.pos = 0;
 
             if ( child != null )
             {
                 parentPos.page = child;
             }
 
             child = ( ( AbstractPage<K, K> ) parentPos.page ).getPage( 0 );
         }
 
         // and leaf
         ParentPos<K, K> parentPos = stack[depth];
         parentPos.pos = BEFORE_FIRST;
 
         if ( child != null )
         {
             parentPos.page = child;
         }
     }
 
 
     /**
      * Tells if the cursor can return a next element
      *
      * @return true if there are some more elements
      * @throws IOException
      * @throws EndOfFileExceededException
      */
     public boolean hasNext() throws EndOfFileExceededException, IOException
     {
         // First check that we have elements in the BTree
         if ( ( stack == null ) || ( stack.length == 0 ) )
         {
             return false;
         }
 
         // Take the leaf and check if we have no mare keys
         ParentPos<K, K> parentPos = stack[depth];
 
         if ( parentPos.page == null )
         {
             // Empty BTree, get out
             return false;
         }
 
         if ( parentPos.pos == AFTER_LAST )
         {
             return false;
         }
 
         if ( parentPos.pos == BEFORE_FIRST )
         {
             return true;
         }
 
         if ( parentPos.pos < parentPos.page.getNbElems() - 1 )
         {
             // Not the last position, we have a next key
             return true;
         }
         else
         {
             // Ok, here, we have reached the last key in the leaf. We have to go up and
             // see if we have some remaining keys
             int currentDepth = depth - 1;
 
             while ( currentDepth >= 0 )
             {
                 parentPos = stack[currentDepth];
 
                 if ( parentPos.pos < parentPos.page.getNbElems() )
                 {
                     // The parent has some remaining keys on the right, get out
                     return true;
                 }
                 else
                 {
                     currentDepth--;
                 }
             }
 
             // We are done, there are no more key left
             return false;
         }
     }
 
 
     /**
      * Find the next key
      *
      * @return the found key
      * @throws IOException
      * @throws EndOfFileExceededException
      */
     public K next() throws EndOfFileExceededException, IOException
     {
         // First check that we have elements in the BTree
         if ( ( stack == null ) || ( stack.length == 0 ) )
         {
             throw new NoSuchElementException( "No Key is present" );
         }
 
         ParentPos<K, K> parentPos = stack[depth];
 
         if ( ( parentPos.page == null ) || ( parentPos.pos == AFTER_LAST ) )
         {
             // This is the end : no more keys
             throw new NoSuchElementException( "No more keys present" );
         }
 
         if ( parentPos.pos == parentPos.page.getNbElems() )
         {
             // End of the leaf. We have to go back into the stack up to the
             // parent, and down to the leaf
             parentPos = findNextParentPos();
 
             // we also need to check for the type of page cause
             // findNextParentPos will never return a null ParentPos
             if ( ( parentPos == null ) || ( parentPos.page == null ) )
             {
                 // This is the end : no more keys
                 throw new NoSuchElementException( "No more keys present" );
             }
         }
 
         // Deal with the BeforeFirst case
         if ( parentPos.pos == BEFORE_FIRST )
         {
             parentPos.pos++;
         }
         else
         {
             if ( parentPos.pos == parentPos.page.getNbElems() - 1 )
             {
                 parentPos = findNextParentPos();
                 
                 if ( ( parentPos == null ) || ( parentPos.page == null ) )
                 {
                     // This is the end : no more keys
                     throw new NoSuchElementException( "No more keys present" );
                 }
             }
             else
             {
                 parentPos.pos++;
             }
         }
         
         AbstractPage<K, K> leaf = ( AbstractPage<K, K> ) ( parentPos.page );
 
         return leaf.getKey( parentPos.pos );
     }
 
 
     /**
      * Get the next key.
      */
     public K nextKey() throws EndOfFileExceededException, IOException
     {
         return next();
     }
 
 
     /**
      * Tells if the cursor can return a next key
      *
      * @return true if there are some more keys
      * @throws IOException
      * @throws EndOfFileExceededException
      */
     public boolean hasNextKey() throws EndOfFileExceededException, IOException
     {
         // First check that we have elements in the BTree
         if ( ( stack == null ) || ( stack.length == 0 ) )
         {
             // This is the end : no more key
             return false;
         }
 
         ParentPos<K, K> parentPos = stack[depth];
 
         if ( parentPos.page == null )
         {
             // This is the end : no more key
             return false;
         }
 
         if ( parentPos.pos == ( parentPos.page.getNbElems() - 1 ) )
         {
             // End of the leaf. We have to go back into the stack up to the
             // parent, and down to the next leaf
             return hasNextParentPos();
         }
         else
         {
             return true;
         }
     }
 
 
     /**
      * Tells if the cursor can return a previous element
      *
      * @return true if there are some more elements
      * @throws IOException
      * @throws EndOfFileExceededException
      */
     public boolean hasPrev() throws EndOfFileExceededException, IOException
     {
         // First check that we have elements in the BTree
         if ( ( stack == null ) || ( stack.length == 0 ) )
         {
             return false;
         }
 
         // Take the leaf and check if we have no mare keys
         ParentPos<K, K> parentPos = stack[depth];
 
         if ( parentPos.page == null )
         {
             // Empty BTree, get out
             return false;
         }
 
         if ( parentPos.pos > 0 )
         {
             // get out, we have keys on the left
             return true;
         }
         else
         {
             // Check that we are not before the first key
             if ( parentPos.pos == BEFORE_FIRST )
             {
                 return false;
             }
 
             if ( parentPos.pos == AFTER_LAST )
             {
                 return true;
             }
 
             // Ok, here, we have reached the first key in the leaf. We have to go up and
             // see if we have some remaining keys
             int currentDepth = depth - 1;
 
             while ( currentDepth >= 0 )
             {
                 parentPos = stack[currentDepth];
 
                 if ( parentPos.pos > 0 )
                 {
                     // The parent has some remaining keys on the right, get out
                     return true;
                 }
                 else
                 {
                     currentDepth--;
                 }
             }
 
             return false;
         }
     }
 
 
     /**
      * Find the previous key
      *
      * @return the found key
      * @throws IOException
      * @throws EndOfFileExceededException
      */
     public K prev() throws EndOfFileExceededException, IOException
     {
         // First check that we have elements in the BTree
         if ( ( stack == null ) || ( stack.length == 0 ) )
         {
             throw new NoSuchElementException( "No more keys present" );
         }
 
         ParentPos<K, K> parentPos = stack[depth];
 
         if ( ( parentPos.page == null ) || ( parentPos.pos == BEFORE_FIRST ) )
         {
             // This is the end : no more keys
             throw new NoSuchElementException( "No more keys present" );
         }
 
         // Deal with the AfterLast case
         if ( parentPos.pos == AFTER_LAST )
         {
             parentPos.pos = parentPos.page.getNbElems() - 1;
         }
         else
         {
             if ( parentPos.pos == 0 )
             {
                 parentPos = findPrevParentPos();
                 
                 if ( ( parentPos == null ) || ( parentPos.page == null ) )
                 {
                     // This is the end : no more keys
                     throw new NoSuchElementException( "No more keys present" );
                 }
             }
             else
             {
                 parentPos.pos--;
             }
         }
 
         AbstractPage<K, K> leaf = ( AbstractPage<K, K> ) ( parentPos.page );
 
         return leaf.getKey( parentPos.pos );
     }
 
 
     /**
      * Get the previous key.
      * 
      * @return the found key
      * @throws EndOfFileExceededException
      * @throws IOException
      */
     public K prevKey() throws EndOfFileExceededException, IOException
     {
         return prev();
     }
 
 
     /**
      * Tells if the cursor can return a previous key
      *
      * @return true if there are some more keys
      * @throws IOException
      * @throws EndOfFileExceededException
      */
     public boolean hasPrevKey() throws EndOfFileExceededException, IOException
     {
         // First check that we have elements in the BTree
         if ( ( stack == null ) || ( stack.length == 0 ) )
         {
             // This is the end : no more key
             return false;
         }
 
         ParentPos<K, K> parentPos = stack[depth];
 
         if ( parentPos.page == null )
         {
             // This is the end : no more key
             return false;
         }
 
         switch ( parentPos.pos )
         {
             case 0 :
                 // Beginning of the leaf. We have to go back into the stack up to the
                 // parent, and down to the leaf
                 return hasPrevParentPos();
                 
             case -1 :
                 // no previous key
                 return false;
                 
             default :
                 // we have a previous key
                 return true;
         }
     }
 
 
     /**
      * Tells if there is a next ParentPos
      *
      * @return the new ParentPos instance, or null if we have no following leaf
      * @throws IOException
      * @throws EndOfFileExceededException
      */
     private boolean hasNextParentPos() throws EndOfFileExceededException, IOException
     {
         if ( depth == 0 )
         {
             // No need to go any further, there is only one leaf in the btree
             return false;
         }
 
         int currentDepth = depth - 1;
         Page<K, K> 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, K> parentPos = stack[currentDepth];
 
             if ( parentPos.pos + 1 > parentPos.page.getNbElems() )
             {
                 // No more element on the right : go up
                 currentDepth--;
             }
             else
             {
                 // We can pick the next element at this level
                 child = ( ( AbstractPage<K, K> ) parentPos.page ).getPage( parentPos.pos + 1 );
 
                 // and go down the tree through the nodes
                 while ( currentDepth < depth - 1 )
                 {
                     currentDepth++;
                     child = ( ( AbstractPage<K, K> ) child ).getPage( 0 );
                 }
 
                 return true;
             }
         }
 
         return false;
     }
 
 
     /**
      * Find the leaf containing the following elements.
      *
      * @return the new ParentPos instance, or null if we have no following leaf
      * @throws IOException
      * @throws EndOfFileExceededException
      */
     private ParentPos<K, K> findNextParentPos() throws EndOfFileExceededException, IOException
     {
         if ( depth == 0 )
         {
             // No need to go any further, there is only one leaf in the btree
             return null;
         }
 
         int currentDepth = depth - 1;
         Page<K, K> 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, K> parentPos = stack[currentDepth];
 
             if ( parentPos.pos + 1 > parentPos.page.getNbElems() )
             {
                 // No more element on the right : go up
                 currentDepth--;
             }
             else
             {
                 // We can pick the next element at this level
                 parentPos.pos++;
                 child = ( ( AbstractPage<K, K> ) parentPos.page ).getPage( parentPos.pos );
 
                 // and go down the tree through the nodes
                 while ( currentDepth < depth - 1 )
                 {
                     currentDepth++;
                     parentPos = stack[currentDepth];
                     parentPos.pos = 0;
                     parentPos.page = child;
                     child = ( ( AbstractPage<K, K> ) child ).getPage( 0 );
                 }
 
                 // and the leaf
                 parentPos = stack[depth];
                 parentPos.page = child;
                 parentPos.pos = 0;
 
                 return parentPos;
             }
         }
 
         return null;
     }
 
 
     /**
      * Find the leaf containing the previous elements.
      *
      * @return the new ParentPos instance, or null if we have no previous leaf
      * @throws IOException
      * @throws EndOfFileExceededException
      */
     private ParentPos<K, K> findPrevParentPos() throws EndOfFileExceededException, IOException
     {
         if ( depth == 0 )
         {
             // No need to go any further, there is only one leaf in the btree
             return null;
         }
 
         int currentDepth = depth - 1;
         Page<K, K> child = null;
 
         // First, go up the tree until we find a Node which has some element on the left
         while ( currentDepth >= 0 )
         {
             // We first go up the tree, until we reach a page whose current position
             // is not the last one
             ParentPos<K, K> parentPos = stack[currentDepth];
 
             if ( parentPos.pos == 0 )
             {
                 // No more element on the right : go up
                 currentDepth--;
             }
             else
             {
                 // We can pick the next element at this level
                 parentPos.pos--;
                 child = ( ( AbstractPage<K, K> ) parentPos.page ).getPage( parentPos.pos );
 
                 // and go down the tree through the nodes
                 while ( currentDepth < depth - 1 )
                 {
                     currentDepth++;
                     parentPos = stack[currentDepth];
                     parentPos.pos = child.getNbElems();
                     parentPos.page = child;
                     child = ( ( AbstractPage<K, K> ) parentPos.page ).getPage( parentPos.page.getNbElems() );
                 }
 
                 // and the leaf
                 parentPos = stack[depth];
                 parentPos.pos = child.getNbElems() - 1;
                 parentPos.page = child;
 
                 return parentPos;
             }
         }
 
         return null;
     }
 
 
     /**
      * Tells if there is a prev ParentPos
      *
      * @return the new ParentPos instance, or null if we have no previous leaf
      * @throws IOException
      * @throws EndOfFileExceededException
      */
     private boolean hasPrevParentPos() throws EndOfFileExceededException, IOException
     {
         if ( depth == 0 )
         {
             // No need to go any further, there is only one leaf in the btree
             return false;
         }
 
         int currentDepth = depth - 1;
         Page<K, K> 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, K> parentPos = stack[currentDepth];
 
             if ( parentPos.pos == 0 )
             {
                 // No more element on the left : go up
                 currentDepth--;
             }
             else
             {
                 // We can pick the previous element at this level
                 child = ( ( AbstractPage<K, K> ) parentPos.page ).getPage( parentPos.pos - 1 );
 
                 // and go down the tree through the nodes
                 while ( currentDepth < depth - 1 )
                 {
                     currentDepth++;
                     child = ( ( AbstractPage<K, K> ) child ).getPage( child.getNbElems() );
                 }
 
                 return true;
             }
         }
 
         return false;
     }
 
 
     /**
      * {@inheritDoc}
      */
     public void close()
     {
         transaction.close();
     }
 
 
     /**
      * Get the creation date
      * @return The creation date for this cursor
      */
     public long getCreationDate()
     {
         return transaction.getCreationDate();
     }
 
 
     /**
      * Get the current revision
      *
      * @return The revision this cursor is based on
      */
     public long getRevision()
     {
         return transaction.getRevision();
     }
 
 
     public String toString()
     {
         StringBuilder sb = new StringBuilder();
 
         sb.append( "KeyCursor, depth = " ).append( depth ).append( "\n" );
 
         for ( int i = 0; i <= depth; i++ )
         {
             sb.append( "    " ).append( stack[i] ).append( "\n" );
         }
 
         return sb.toString();
     }
 }