Author: elecharny
Date: Wed Jun 27 17:44:42 2012
New Revision: 1354644
URL: http://svn.apache.org/viewvc?rev=1354644&view=rev
Log:
o Fixed many issues in the merge from a right sibling
o Added a test for this case
o Added some images
o Renamed the BorrowedFromSiblingResult class to
BorrowedFromLeftResult/BorrowedFromRightResult
Added:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromLeftResult.java
- copied, changed from r1354047,
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromSiblingResult.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromRightResult.java
Removed:
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/Leaf.java
labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/BTreeTest.java
labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/LeafTest.java
Copied:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromLeftResult.java
(from r1354047,
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/BorrowedFromLeftResult.java?p2=labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromLeftResult.java&p1=labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromSiblingResult.java&r1=1354047&r2=1354644&rev=1354644&view=diff
==============================================================================
---
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromSiblingResult.java
(original)
+++
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromLeftResult.java
Wed Jun 27 17:44:42 2012
@@ -28,7 +28,7 @@ package org.apache.mavibot.btree;
* @author <a href="mailto:[email protected]";>Mavibot labs Project</a>
*/
-/* No qualifier */ class BorrowedFromSiblingResult<K, V> implements
DeleteResult<K, V>
+/* No qualifier */ class BorrowedFromLeftResult<K, V> implements
DeleteResult<K, V>
{
/** The modified page reference */
protected Page<K, V> modifiedPage;
@@ -49,7 +49,7 @@ package org.apache.mavibot.btree;
* @param
* @param removedElement The removed element (can be null if the key
wasn't present in the tree)
*/
- public BorrowedFromSiblingResult( Page<K, V> modifiedPage, Page<K, V>
modifiedSibling, Tuple<K, V> removedElement, K newLeftMost )
+ public BorrowedFromLeftResult( Page<K, V> modifiedPage, Page<K, V>
modifiedSibling, Tuple<K, V> removedElement, K newLeftMost )
{
this.modifiedPage = modifiedPage;
this.modifiedSibling = modifiedSibling;
Added:
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=1354644&view=auto
==============================================================================
---
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromRightResult.java
(added)
+++
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromRightResult.java
Wed Jun 27 17:44:42 2012
@@ -0,0 +1,110 @@
+/*
+ * 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. 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 */ class BorrowedFromRightResult<K, V> implements
DeleteResult<K, V>
+{
+ /** The modified page reference */
+ protected Page<K, V> modifiedPage;
+
+ /** The modified sibling reference */
+ protected Page<K, V> modifiedSibling;
+
+ /** The removed element if the key was found in the tree*/
+ protected Tuple<K, V> removedElement;
+
+ /** The new leftmost element if the removed k was on position 0. Null
otherwise */
+ protected K newLeftMost;
+
+ /**
+ * The default constructor for RemoveResult.
+ *
+ * @param modifiedPage The modified page
+ * @param
+ * @param removedElement The removed element (can be null if the key
wasn't present in the tree)
+ */
+ public BorrowedFromRightResult( Page<K, V> modifiedPage, Page<K, V>
modifiedSibling, Tuple<K, V> removedElement, K newLeftMost )
+ {
+ this.modifiedPage = modifiedPage;
+ this.modifiedSibling = modifiedSibling;
+ this.removedElement = removedElement;
+ this.newLeftMost = newLeftMost;
+ }
+
+
+ /**
+ * @return the modifiedPage
+ */
+ public Page<K, V> getModifiedPage()
+ {
+ return modifiedPage;
+ }
+
+
+ /**
+ * @return the modifiedSibling
+ */
+ public Page<K, V> getModifiedSibling()
+ {
+ return modifiedSibling;
+ }
+
+
+ /**
+ * @return the removed element
+ */
+ public Tuple<K, V> getRemovedElement()
+ {
+ return removedElement;
+ }
+
+
+ /**
+ * @return the newLeftMost
+ */
+ public K getNewLeftMost()
+ {
+ return newLeftMost;
+ }
+
+
+ /**
+ * @see Object#toString()
+ */
+ public String toString()
+ {
+ StringBuilder sb = new StringBuilder();
+
+ sb.append( "RemoveResult, removed element = " ).append( removedElement
);
+ sb.append( ", modifiedPage = " ).append( modifiedPage );
+ sb.append( ", new LeftMost = " ).append( newLeftMost );
+
+ return sb.toString();
+ }
+}
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=1354644&r1=1354643&r2=1354644&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
Wed Jun 27 17:44:42 2012
@@ -281,7 +281,7 @@ public class Leaf<K, V> extends Abstract
// Create the result
Tuple<K, V> removedElement = new Tuple<K, V>( keys[pos], values[pos] );
- DeleteResult<K, V> result = new BorrowedFromSiblingResult<K, V>(
newLeaf, newSibling, removedElement, siblingKey );
+ DeleteResult<K, V> result = new BorrowedFromLeftResult<K, V>( newLeaf,
newSibling, removedElement, siblingKey );
return result;
}
@@ -307,8 +307,8 @@ public class Leaf<K, V> extends Abstract
Leaf<K, V> newSibling = new Leaf<K, V>( btree, revision,
sibling.getNbElems() - 1 );
// Copy the keys and the values from 1 to N in the new sibling
- System.arraycopy( keys, 1, newSibling.keys, 0, nbElems - 1 );
- System.arraycopy( values, 1, newSibling.values, 0, nbElems - 1 );
+ System.arraycopy( sibling.keys, 1, newSibling.keys, 0, sibling.nbElems
- 1 );
+ System.arraycopy( sibling.values, 1, newSibling.values, 0,
sibling.nbElems - 1 );
// Create the new page and add the new element at the end
// First copy the current page, with the same size
@@ -328,12 +328,13 @@ public class Leaf<K, V> extends Abstract
// Update the prev/next references
newLeaf.prevPage = this.prevPage;
- newLeaf.nextPage = this.nextPage;
+ newLeaf.nextPage = newSibling;
+ newSibling.prevPage = newLeaf;
// Create the result
Tuple<K, V> removedElement = new Tuple<K, V>( keys[pos], values[pos] );
- DeleteResult<K, V> result = new BorrowedFromSiblingResult<K, V>(
newLeaf, newSibling, removedElement, siblingKey );
+ DeleteResult<K, V> result = new BorrowedFromRightResult<K, V>(
newLeaf, newSibling, removedElement, newSibling.keys[0] );
return result;
}
Modified:
labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/BTreeTest.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/BTreeTest.java?rev=1354644&r1=1354643&r2=1354644&view=diff
==============================================================================
---
labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/BTreeTest.java
(original)
+++
labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/BTreeTest.java
Wed Jun 27 17:44:42 2012
@@ -251,7 +251,7 @@ public class BTreeTest
// Now, delete entries
for ( long key : added )
{
- System.out.println( "Removing " + key + " from " + btree );
+ //System.out.println( "Removing " + key + " from " + btree );
try
{
btree.delete( key );
Modified:
labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/LeafTest.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/LeafTest.java?rev=1354644&r1=1354643&r2=1354644&view=diff
==============================================================================
---
labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/LeafTest.java
(original)
+++
labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/LeafTest.java
Wed Jun 27 17:44:42 2012
@@ -195,7 +195,7 @@ public class LeafTest
right = insert( right, 12L, "v12" );
right = insert( right, 13L, "v13" );
- // Crate the links between leaves
+ // Create the links between leaves
left.prevPage = null;
left.nextPage = target;
@@ -212,9 +212,9 @@ public class LeafTest
// Now, delete the element from the target page
DeleteResult<Long, String> result = target.delete( 2L, 7L, parent, 1 );
- assertTrue( result instanceof BorrowedFromSiblingResult );
+ assertTrue( result instanceof BorrowedFromLeftResult );
- BorrowedFromSiblingResult<Long, String> borrowed =
(BorrowedFromSiblingResult<Long, String>)result;
+ BorrowedFromLeftResult<Long, String> borrowed =
(BorrowedFromLeftResult<Long, String>)result;
assertEquals( Long.valueOf( 5L ), borrowed.newLeftMost );
Tuple<Long, String> removedKey = borrowed.getRemovedElement();
@@ -241,4 +241,87 @@ public class LeafTest
assertEquals( leftSibling, newLeaf.prevPage );
assertEquals( newLeaf.prevPage, leftSibling );
}
+
+
+ /**
+ * Check that deleting an element from a leaf with N/2 element works when
we borrow
+ * an element in a right page with more than N/2 elements
+ */
+ @Test
+ public void testRemoveBorrowingFromRightSibling()
+ {
+ Node<Long, String> parent = new Node<Long, String>( btree, 1L, 2 );
+ Leaf<Long, String> left = new Leaf<Long, String>( btree );
+ Leaf<Long, String> target = new Leaf<Long, String>( btree );
+ Leaf<Long, String> right = new Leaf<Long, String>( btree );
+
+ parent.children[0] = left;
+ parent.children[1] = target;
+ parent.children[2] = right;
+
+ // Fill the left page
+ left = insert( left, 1L, "v1" );
+ left = insert( left, 2L, "v2" );
+ left = insert( left, 3L, "v3" );
+ left = insert( left, 4L, "v4" );
+
+ // Fill the target page
+ target = insert( target, 6L, "v6" );
+ target = insert( target, 7L, "v7" );
+ target = insert( target, 8L, "v8" );
+ target = insert( target, 9L, "v9" );
+
+ // Fill the right page
+ right = insert( right, 10L, "v10" );
+ right = insert( right, 11L, "v11" );
+ right = insert( right, 12L, "v12" );
+ right = insert( right, 13L, "v13" );
+ right = insert( right, 14L, "v14" );
+
+ // Create the links between leaves
+ left.prevPage = null;
+ left.nextPage = target;
+
+ target.prevPage = left;
+ target.nextPage = right;
+
+ right.prevPage = target;
+ right.nextPage = null;
+
+ // Update the parent
+ parent.keys[0] = 6L;
+ parent.keys[1] = 10L;
+
+ // Now, delete the element from the target page
+ DeleteResult<Long, String> result = target.delete( 2L, 7L, parent, 1 );
+
+ assertTrue( result instanceof BorrowedFromRightResult );
+
+ BorrowedFromRightResult<Long, String> borrowed =
(BorrowedFromRightResult<Long, String>)result;
+ assertEquals( Long.valueOf( 11L ), borrowed.newLeftMost );
+ Tuple<Long, String> removedKey = borrowed.getRemovedElement();
+
+ assertEquals( Long.valueOf( 7L ), removedKey.getKey() );
+
+ // Check the modified leaf
+ Leaf<Long, String> newLeaf = (Leaf<Long,
String>)borrowed.getModifiedPage();
+
+ assertEquals( 4, newLeaf.nbElems );
+ assertEquals( Long.valueOf( 6L ), newLeaf.keys[0] );
+ assertEquals( Long.valueOf( 8L ), newLeaf.keys[1] );
+ assertEquals( Long.valueOf( 9L ), newLeaf.keys[2] );
+ assertEquals( Long.valueOf( 10L ), newLeaf.keys[3] );
+
+ // Check the sibling
+ Leaf<Long, String> rightSibling = (Leaf<Long,
String>)borrowed.getModifiedSibling();
+
+ assertEquals( 4, rightSibling.nbElems );
+ assertEquals( Long.valueOf( 11L ), rightSibling.keys[0] );
+ assertEquals( Long.valueOf( 12L ), rightSibling.keys[1] );
+ assertEquals( Long.valueOf( 13L ), rightSibling.keys[2] );
+ assertEquals( Long.valueOf( 14L ), rightSibling.keys[3] );
+
+ assertEquals( rightSibling, newLeaf.nextPage );
+ assertEquals( newLeaf.nextPage, rightSibling );
+ }
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
