Author: elecharny
Date: Wed Jun 27 17:24:06 2012
New Revision: 1354638
URL: http://svn.apache.org/viewvc?rev=1354638&view=rev
Log:
o Fixed the borrowFromLeft() method
o Added a test to check that borrowing an element from left is correct
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/LeafTest.java
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=1354638&r1=1354637&r2=1354638&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:24:06 2012
@@ -255,7 +255,7 @@ public class Leaf<K, V> extends Abstract
V siblingValue = sibling.values[sibling.getNbElems() - 1 ];
// Create the new sibling, with one less element at the end
- Page<K, V> newSibling = sibling.copy( revision, sibling.getNbElems() -
1 );
+ Leaf<K, V> newSibling = (Leaf<K, V>)sibling.copy( revision,
sibling.getNbElems() - 1 );
// Create the new page and add the new element at the beginning
// First copy the current page, with the same size
@@ -274,8 +274,9 @@ public class Leaf<K, V> extends Abstract
System.arraycopy( values, pos + 1, newLeaf.values, pos + 1,
values.length - pos - 1 );
// Update the prev/next references
- newLeaf.prevPage = this.prevPage;
+ newLeaf.prevPage = newSibling;
newLeaf.nextPage = this.nextPage;
+ newSibling.nextPage = newLeaf;
// Create the result
Tuple<K, V> removedElement = new Tuple<K, V>( keys[pos], values[pos] );
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=1354638&r1=1354637&r2=1354638&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:24:06 2012
@@ -158,4 +158,87 @@ public class LeafTest
assertEquals( "v3", newLeaf.find( 3L ) );
assertEquals( "v4", newLeaf.find( 4L ) );
}
+
+
+ /**
+ * Check that deleting an element from a leaf with N/2 element works when
we borrow
+ * an element in a left page with more than N/2 elements
+ */
+ @Test
+ public void testRemoveBorrowingFromLeftSibling()
+ {
+ 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" );
+ left = insert( left, 5L, "v5" );
+
+ // 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" );
+
+ // Crate 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 BorrowedFromSiblingResult );
+
+ BorrowedFromSiblingResult<Long, String> borrowed =
(BorrowedFromSiblingResult<Long, String>)result;
+ assertEquals( Long.valueOf( 5L ), 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( 5L ), newLeaf.keys[0] );
+ assertEquals( Long.valueOf( 6L ), newLeaf.keys[1] );
+ assertEquals( Long.valueOf( 8L ), newLeaf.keys[2] );
+ assertEquals( Long.valueOf( 9L ), newLeaf.keys[3] );
+
+ // Check the sibling
+ Leaf<Long, String> leftSibling = (Leaf<Long,
String>)borrowed.getModifiedSibling();
+
+ assertEquals( 4, leftSibling.nbElems );
+ assertEquals( Long.valueOf( 1L ), leftSibling.keys[0] );
+ assertEquals( Long.valueOf( 2L ), leftSibling.keys[1] );
+ assertEquals( Long.valueOf( 3L ), leftSibling.keys[2] );
+ assertEquals( Long.valueOf( 4L ), leftSibling.keys[3] );
+
+ assertEquals( leftSibling, newLeaf.prevPage );
+ assertEquals( newLeaf.prevPage, leftSibling );
+ }
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
