| /* |
| * 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(); |
| } |
| } |