Author: elecharny
Date: Thu Jul 5 23:06:04 2012
New Revision: 1357988
URL: http://svn.apache.org/viewvc?rev=1357988&view=rev
Log:
o Fixed the code that manage the merge of pages which have not enough elements,
except when we merge two pages
o Reorganized the hierarchy of DeleteResult classes
o Added some javadoc
o Added the getKey() method in Page
Added:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractBorrowedFromSiblingResult.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromSiblingResult.java
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractDeleteResult.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractPage.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromLeftResult.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromRightResult.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/DeleteResult.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Leaf.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/MergedWithSiblingResult.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Node.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/NotPresentResult.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java
Added:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractBorrowedFromSiblingResult.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractBorrowedFromSiblingResult.java?rev=1357988&view=auto
==============================================================================
---
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractBorrowedFromSiblingResult.java
(added)
+++
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractBorrowedFromSiblingResult.java
Thu Jul 5 23:06:04 2012
@@ -0,0 +1,104 @@
+/*
+ * 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.mavibot.btree;
+
+/**
+ * The result of a delete operation, when the child has not been merged, and
when
+ * we have borrowed an element from the left sibling. It contains the
+ * reference to the modified page, and the removed element.
+ *
+ * @param <K> The type for the Key
+ * @param <V> The type for the stored value
+
+ * @author <a href="mailto:[email protected]";>Mavibot labs Project</a>
+ */
+/* No qualifier */ abstract class AbstractBorrowedFromSiblingResult<K, V>
extends AbstractDeleteResult<K, V> implements BorrowedFromSiblingResult<K, V>
+{
+ /** The modified sibling reference */
+ private Page<K, V> modifiedSibling;
+
+ /** Tells if the sibling is the left or right one */
+ protected SiblingPosition position;
+
+ /** The two possible position for the sibling */
+ protected enum SiblingPosition
+ {
+ LEFT,
+ RIGHT
+ }
+
+ /**
+ * The default constructor for RemoveResult.
+ *
+ * @param modifiedPage The modified page
+ * @param modifiedSibling The modified sibling
+ * @param removedElement The removed element (can be null if the key
wasn't present in the tree)
+ * @param newLeftMost The element on the left of he current page
+ */
+ /* No qualifier */ AbstractBorrowedFromSiblingResult( Page<K, V>
modifiedPage, Page<K, V> modifiedSibling, Tuple<K, V> removedElement, K
newLeftMost, SiblingPosition position )
+ {
+ super( modifiedPage, removedElement, newLeftMost );
+ this.modifiedSibling = modifiedSibling;
+ this.position = position;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public Page<K, V> getModifiedSibling()
+ {
+ return modifiedSibling;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public boolean isFromLeft()
+ {
+ return position == SiblingPosition.LEFT;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public boolean isFromRight()
+ {
+ return position == SiblingPosition.RIGHT;
+ }
+
+
+ /**
+ * @see Object#toString()
+ */
+ public String toString()
+ {
+ StringBuilder sb = new StringBuilder();
+
+ sb.append( "\n removed element : " ).append( getRemovedElement() );
+ sb.append( "\n modifiedPage : " ).append( getModifiedPage() );
+ sb.append( "\n modifiedSibling : " ).append( getModifiedSibling() );
+ sb.append( "\n new LeftMost : " ).append( getNewLeftMost() );
+
+ return sb.toString();
+ }
+}
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractDeleteResult.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractDeleteResult.java?rev=1357988&r1=1357987&r2=1357988&view=diff
==============================================================================
---
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractDeleteResult.java
(original)
+++
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractDeleteResult.java
Thu Jul 5 23:06:04 2012
@@ -54,18 +54,18 @@ package org.apache.mavibot.btree;
/**
- * @return the modifiedPage
+ * {@inheritDoc}
*/
- /* No qualifier */ Page<K, V> getModifiedPage()
+ public Page<K, V> getModifiedPage()
{
return modifiedPage;
}
/**
- * @return the removed element
+ * {@inheritDoc}
*/
- /* No qualifier */ Tuple<K, V> getRemovedElement()
+ public Tuple<K, V> getRemovedElement()
{
return removedElement;
}
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractPage.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractPage.java?rev=1357988&r1=1357987&r2=1357988&view=diff
==============================================================================
---
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractPage.java
(original)
+++
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractPage.java
Thu Jul 5 23:06:04 2012
@@ -138,12 +138,28 @@ public abstract class AbstractPage<K, V>
* So for the following table of keys : <br/>
* <pre>
* +---+---+---+---+
- * | a | b | c | d |
+ * | b | d | f | h |
* +---+---+---+---+
* 0 1 2 3
* </pre>
- * looking for 'a' will return -1 (-(0+1)) and looking for 'c' will return
-3 (-(2+1)).<br/>
+ * looking for 'b' will return -1 (-(0+1)) and looking for 'f' will return
-3 (-(2+1)).<br/>
* Computing the real position is just a matter to get -(position++).
+ * <p/>
+ * If we don't find the key in the table, we will return the position of
the key
+ * immediately above the key we are looking for. <br/>
+ * For instance, looking for :
+ * <ul>
+ * <li>'a' will return 0</li>
+ * <li>'b' will return -1</li>
+ * <li>'c' will return 1</li>
+ * <li>'d' will return -2</li>
+ * <li>'e' will return 2</li>
+ * <li>'f' will return -3</li>
+ * <li>'g' will return 3</li>
+ * <li>'h' will return -4</li>
+ * <li>'i' will return 4</li>
+ * </ul>
+ *
*
* @param key The key to find
* @return The position in the page.
@@ -258,7 +274,23 @@ public abstract class AbstractPage<K, V>
{
this.id = id;
}
+
+ /**
+ * {@inheritDoc}
+ */
+ public K getKey( int pos )
+ {
+ if ( pos < nbElems )
+ {
+ return keys[pos];
+ }
+ else
+ {
+ return null;
+ }
+ }
+
/**
* @see Object#toString()
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromLeftResult.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromLeftResult.java?rev=1357988&r1=1357987&r2=1357988&view=diff
==============================================================================
---
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromLeftResult.java
(original)
+++
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromLeftResult.java
Thu Jul 5 23:06:04 2012
@@ -29,13 +29,10 @@ package org.apache.mavibot.btree;
* @author <a href="mailto:[email protected]";>Mavibot labs Project</a>
*/
-/* No qualifier */ class BorrowedFromLeftResult<K, V> extends
AbstractDeleteResult<K, V>
+/* No qualifier */ class BorrowedFromLeftResult<K, V> extends
AbstractBorrowedFromSiblingResult<K, V>
{
- /** The modified sibling reference */
- private Page<K, V> modifiedSibling;
-
/**
- * The default constructor for RemoveResult.
+ * The default constructor for BorrowedFromLeftResult.
*
* @param modifiedPage The modified page
* @param modifiedSibling The modified sibling
@@ -44,17 +41,7 @@ package org.apache.mavibot.btree;
*/
/* No qualifier */ BorrowedFromLeftResult( Page<K, V> modifiedPage,
Page<K, V> modifiedSibling, Tuple<K, V> removedElement, K newLeftMost )
{
- super( modifiedPage, removedElement, newLeftMost );
- this.modifiedSibling = modifiedSibling;
- }
-
-
- /**
- * @return the modifiedSibling
- */
- /* No qualifier */ Page<K, V> getModifiedSibling()
- {
- return modifiedSibling;
+ super( modifiedPage, modifiedSibling, removedElement, newLeftMost,
AbstractBorrowedFromSiblingResult.SiblingPosition.LEFT );
}
@@ -65,9 +52,8 @@ package org.apache.mavibot.btree;
{
StringBuilder sb = new StringBuilder();
- sb.append( "RemoveResult, removed element = " ).append(
getRemovedElement() );
- sb.append( ", modifiedPage = " ).append( getModifiedPage() );
- sb.append( ", new LeftMost = " ).append( getNewLeftMost() );
+ sb.append( "Borrowed from left" );
+ sb.append( super.toString() );
return sb.toString();
}
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromRightResult.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromRightResult.java?rev=1357988&r1=1357987&r2=1357988&view=diff
==============================================================================
---
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromRightResult.java
(original)
+++
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromRightResult.java
Thu Jul 5 23:06:04 2012
@@ -28,31 +28,19 @@ package org.apache.mavibot.btree;
* @author <a href="mailto:[email protected]";>Mavibot labs Project</a>
*/
-/* No qualifier */ class BorrowedFromRightResult<K, V> extends
AbstractDeleteResult<K, V>
+/* No qualifier */ class BorrowedFromRightResult<K, V> extends
AbstractBorrowedFromSiblingResult<K, V>
{
- /** The modified sibling reference */
- private Page<K, V> modifiedSibling;
-
/**
- * The default constructor for RemoveResult.
+ * The default constructor for BorrowedFromRightResult.
*
* @param modifiedPage The modified page
- * @param
+ * @param modifiedSibling The modified sibling
* @param removedElement The removed element (can be null if the key
wasn't present in the tree)
+ * @param newLeftMost The element on the left of he current page
*/
/* No qualifier */ BorrowedFromRightResult( Page<K, V> modifiedPage,
Page<K, V> modifiedSibling, Tuple<K, V> removedElement, K newLeftMost )
{
- super( modifiedPage, removedElement, newLeftMost );
- this.modifiedSibling = modifiedSibling;
- }
-
-
- /**
- * @return the modifiedSibling
- */
- /* No qualifier */ Page<K, V> getModifiedSibling()
- {
- return modifiedSibling;
+ super( modifiedPage, modifiedSibling, removedElement, newLeftMost,
AbstractBorrowedFromSiblingResult.SiblingPosition.RIGHT );
}
@@ -63,9 +51,8 @@ package org.apache.mavibot.btree;
{
StringBuilder sb = new StringBuilder();
- sb.append( "RemoveResult, removed element = " ).append(
getRemovedElement() );
- sb.append( ", modifiedPage = " ).append( getModifiedPage() );
- sb.append( ", new LeftMost = " ).append( getNewLeftMost() );
+ sb.append( "Borrowed from right" );
+ sb.append( super.toString() );
return sb.toString();
}
Added:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromSiblingResult.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromSiblingResult.java?rev=1357988&view=auto
==============================================================================
---
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromSiblingResult.java
(added)
+++
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromSiblingResult.java
Thu Jul 5 23:06:04 2012
@@ -0,0 +1,52 @@
+/*
+ * 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.mavibot.btree;
+
+/**
+ * The result of an delete operation, when we have borrowed some element from
a sibling.
+ *
+ * @param <K> The type for the Key
+ * @param <V> The type for the stored value
+
+ * @author <a href="mailto:[email protected]";>Mavibot labs Project</a>
+ */
+interface BorrowedFromSiblingResult<K, V> extends DeleteResult<K, V>
+{
+ /**
+ * @return the modifiedSibling
+ */
+ Page<K, V> getModifiedSibling();
+
+
+ /**
+ * Tells if the sibling is on the left
+ *
+ * @return True if the sibling is on the left
+ */
+ boolean isFromLeft();
+
+
+ /**
+ * Tells if the sibling is on the right
+ *
+ * @return True if the sibling is on the right
+ */
+ boolean isFromRight();
+}
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/DeleteResult.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/DeleteResult.java?rev=1357988&r1=1357987&r2=1357988&view=diff
==============================================================================
---
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/DeleteResult.java
(original)
+++
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/DeleteResult.java
Thu Jul 5 23:06:04 2012
@@ -29,4 +29,14 @@ package org.apache.mavibot.btree;
*/
interface DeleteResult<K, V>
{
+ /**
+ * @return the modifiedPage
+ */
+ Page<K, V> getModifiedPage();
+
+
+ /**
+ * @return the removed element
+ */
+ Tuple<K, V> getRemovedElement();
}
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Leaf.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Leaf.java?rev=1357988&r1=1357987&r2=1357988&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Leaf.java
(original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Leaf.java
Thu Jul 5 23:06:04 2012
@@ -155,7 +155,7 @@ public class Leaf<K, V> extends Abstract
}
else
{
- // We can borrow the element from the sibling
+ // We can borrow the element from the left sibling
if ( siblingPos < parentPos )
{
DeleteResult<K, V> result = borrowFromLeft( revision,
sibling, index );
@@ -164,7 +164,7 @@ public class Leaf<K, V> extends Abstract
}
else
{
- // Borrow from the right
+ // Borrow from the right sibling
DeleteResult<K, V> result = borrowFromRight( revision,
sibling, index );
return result;
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/MergedWithSiblingResult.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/MergedWithSiblingResult.java?rev=1357988&r1=1357987&r2=1357988&view=diff
==============================================================================
---
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/MergedWithSiblingResult.java
(original)
+++
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/MergedWithSiblingResult.java
Thu Jul 5 23:06:04 2012
@@ -50,9 +50,10 @@ package org.apache.mavibot.btree;
{
StringBuilder sb = new StringBuilder();
- sb.append( "MergedWithSiblingResult, removed element = " ).append(
getRemovedElement() );
- sb.append( ", modifiedPage = " ).append( getModifiedPage() );
- sb.append( ", new LeftMost = " ).append( getNewLeftMost() );
+ sb.append( "MergedWithSiblingResult" );
+ sb.append( "\n removed element : " ).append( getRemovedElement() );
+ sb.append( "\n modifiedPage : " ).append( getModifiedPage() );
+ sb.append( "\n new LeftMost : " ).append( getNewLeftMost() );
return sb.toString();
}
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Node.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Node.java?rev=1357988&r1=1357987&r2=1357988&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Node.java
(original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Node.java
Thu Jul 5 23:06:04 2012
@@ -155,9 +155,9 @@ import java.util.LinkedList;
if ( pos < 0 )
{
// The key is present in the page
- pos = - ( pos + 1 );
+ int index = - ( pos + 1 );
- DeleteResult<K, V> deleteResult = children[pos + 1].delete(
revision, key, this, pos );
+ DeleteResult<K, V> deleteResult = children[index + 1].delete(
revision, key, this, index + 1 );
if ( deleteResult instanceof NotPresentResult )
{
@@ -172,11 +172,11 @@ import java.util.LinkedList;
// we just have to copy the current page an modify the
reference to link to
// the modified page.
Node<K, V> newPage = copy( revision );
- newPage.children[pos + 1] = removeResult.getModifiedPage();
+ newPage.children[index + 1] = removeResult.getModifiedPage();
if ( removeResult.getNewLeftMost() != key )
{
- newPage.keys[pos] = removeResult.getNewLeftMost();
+ newPage.keys[index] = removeResult.getNewLeftMost();
}
// Modify the result and return
@@ -185,38 +185,9 @@ import java.util.LinkedList;
return removeResult;
}
- else if ( deleteResult instanceof BorrowedFromLeftResult )
+ else if ( deleteResult instanceof BorrowedFromSiblingResult )
{
- BorrowedFromLeftResult<K, V> borrowedResult =
(BorrowedFromLeftResult<K, V>)deleteResult;
-
- // The child has borrowed an element from its left sibling. We
have to copy
- // the current page and modify the references
- Node<K, V> newPage = copy( revision );
- newPage.children[pos] = borrowedResult.getModifiedSibling();
- newPage.children[pos + 1] = borrowedResult.getModifiedPage();
- newPage.keys[pos] = borrowedResult.getNewLeftMost();
-
- // Modify the result and return
- RemoveResult<K, V> removeResult = new RemoveResult<K, V>( this,
- borrowedResult.getRemovedElement(), this.keys[0] );
-
- return removeResult;
- }
- else if ( deleteResult instanceof BorrowedFromLeftResult )
- {
- BorrowedFromRightResult<K, V> borrowedResult =
(BorrowedFromRightResult<K, V>)deleteResult;
-
- // The child has borrowed an element from its left sibling. We
have to copy
- // the current page and modify the references
- Node<K, V> newPage = copy( revision );
- newPage.children[pos + 1] = borrowedResult.getModifiedPage();
- newPage.children[pos + 2] =
borrowedResult.getModifiedSibling();
-
- // Modify the result and return
- RemoveResult<K, V> removeResult = new RemoveResult<K, V>( this,
- borrowedResult.getRemovedElement(), this.keys[0] );
-
- return removeResult;
+ return borrowedResult( deleteResult, pos );
}
else if ( deleteResult instanceof MergedWithSiblingResult )
{
@@ -241,9 +212,9 @@ import java.util.LinkedList;
else
{
// Just remove the entry if it's present
- int index = findPos(
mergedResult.getRemovedElement().getKey() );
+ int newIndex = findPos(
mergedResult.getRemovedElement().getKey() );
- DeleteResult<K, V> result = removeKey( revision, index
);
+ DeleteResult<K, V> result = removeKey( revision,
newIndex );
return result;
}
@@ -295,7 +266,7 @@ import java.util.LinkedList;
// 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)
- DeleteResult<K, V> result = removeKey( revision, pos );
+ DeleteResult<K, V> result = removeKey( revision, index
);
return result;
}
@@ -329,6 +300,10 @@ import java.util.LinkedList;
return removeResult;
}
+ else if ( deleteResult instanceof
AbstractBorrowedFromSiblingResult )
+ {
+ return borrowedResult( deleteResult, pos );
+ }
}
@@ -337,6 +312,76 @@ import java.util.LinkedList;
/**
+ * The deletion in a children has moved an element from one of its
sibling. The key
+ * is present in the current node.
+ * @param deleteResult The result of the deletion from the children
+ * @param pos The position the key was found in the current node
+ * @return
+ */
+ private DeleteResult<K, V> borrowedResult( DeleteResult<K, V>
deleteResult, int pos )
+ {
+ BorrowedFromSiblingResult<K, V> borrowedResult =
(BorrowedFromSiblingResult<K, V>)deleteResult;
+
+ Page<K, V> modifiedPage = borrowedResult.getModifiedPage();
+ Page<K, V> modifiedSibling = borrowedResult.getModifiedSibling();
+
+ Node<K, V> newPage = copy( revision );
+
+ if ( pos < 0 )
+ {
+ pos = - ( pos + 1 );
+
+ if ( borrowedResult.isFromRight() )
+ {
+ // Update the keys
+ newPage.keys[pos] = modifiedPage.getKey( 0 );
+ newPage.keys[pos + 1] = modifiedSibling.getKey( 0 );
+
+ // Update the children
+ newPage.children[pos + 1] = modifiedPage;
+ newPage.children[pos + 2] = modifiedSibling;
+ }
+ else
+ {
+ // Update the keys
+ newPage.keys[pos] = modifiedPage.getKey( 0 );
+
+ // Update the children
+ newPage.children[pos] = modifiedSibling;
+ newPage.children[pos + 1] = modifiedPage;
+ }
+ }
+ else
+ {
+ if ( borrowedResult.isFromRight() )
+ {
+ // Update the keys
+ newPage.keys[pos] = modifiedSibling.getKey( 0 );
+
+ // Update the children
+ newPage.children[pos] = modifiedPage;
+ newPage.children[pos + 1] = modifiedSibling;
+ }
+ else
+ {
+ // Update the keys
+ newPage.keys[pos - 1] = modifiedPage.getKey( 0 );
+
+ // Update the children
+ newPage.children[pos - 1] = modifiedSibling;
+ newPage.children[pos] = modifiedPage;
+ }
+ }
+
+ // Modify the result and return
+ RemoveResult<K, V> removeResult = new RemoveResult<K, V>( newPage,
+ borrowedResult.getRemovedElement(), newPage.keys[0] );
+
+ return removeResult;
+ }
+
+
+ /**
* Remove the key at a given position.
*
* @param revision The revision of the modified page
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/NotPresentResult.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/NotPresentResult.java?rev=1357988&r1=1357987&r2=1357988&view=diff
==============================================================================
---
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/NotPresentResult.java
(original)
+++
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/NotPresentResult.java
Thu Jul 5 23:06:04 2012
@@ -40,4 +40,22 @@ package org.apache.mavibot.btree;
{
// Do nothing
}
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public Page<K, V> getModifiedPage()
+ {
+ return null;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public Tuple<K, V> getRemovedElement()
+ {
+ return null;
+ }
}
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java?rev=1357988&r1=1357987&r2=1357988&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java
(original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java
Thu Jul 5 23:06:04 2012
@@ -115,6 +115,14 @@ import java.util.LinkedList;
/**
+ * Return the key at a given position
+ * @param pos The position of the key we want to retrieve
+ * @return The key found at the given position
+ */
+ K getKey( int pos );
+
+
+ /**
* Pretty-print the tree with tabs
* @param tabs The tabs to add in front of each node
* @return A pretty-print dump of the tree
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
