You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@labs.apache.org by el...@apache.org on 2012/07/03 21:45:52 UTC
svn commit: r1356890 - in /labs/mavibot/trunk/mavibot/src:
main/java/org/apache/mavibot/btree/Node.java
test/java/org/apache/mavibot/btree/BTreeTest.java
test/java/org/apache/mavibot/btree/LeafTest.java
Author: elecharny
Date: Tue Jul 3 19:45:51 2012
New Revision: 1356890
URL: http://svn.apache.org/viewvc?rev=1356890&view=rev
Log:
o Fixed some bugs in the Node.delete() operation
o Fixed some compilation errors in LeafTest
o Added some test for the delete operation
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Node.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
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=1356890&r1=1356889&r2=1356890&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 Tue Jul 3 19:45:51 2012
@@ -157,7 +157,7 @@ import java.util.LinkedList;
// The key is present in the page
pos = - ( pos + 1 );
- DeleteResult<K, V> deleteResult = children[pos].delete( revision, key, this, pos );
+ DeleteResult<K, V> deleteResult = children[pos + 1].delete( revision, key, this, pos );
if ( deleteResult instanceof NotPresentResult )
{
@@ -172,7 +172,7 @@ 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] = removeResult.getModifiedPage();
+ newPage.children[pos + 1] = removeResult.getModifiedPage();
if ( removeResult.getNewLeftMost() != key )
{
@@ -180,7 +180,7 @@ import java.util.LinkedList;
}
// Modify the result and return
- removeResult.setModifiedPage( this );
+ removeResult.setModifiedPage( newPage );
removeResult.setNewLeftMost( newPage.keys[0] );
return removeResult;
@@ -192,8 +192,8 @@ import java.util.LinkedList;
// 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.getModifiedSibling();
- newPage.children[pos] = borrowedResult.getModifiedPage();
+ newPage.children[pos] = borrowedResult.getModifiedSibling();
+ newPage.children[pos + 1] = borrowedResult.getModifiedPage();
newPage.keys[pos] = borrowedResult.getNewLeftMost();
// Modify the result and return
@@ -209,8 +209,8 @@ import java.util.LinkedList;
// 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.getModifiedPage();
- newPage.children[pos + 1] = borrowedResult.getModifiedSibling();
+ 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,
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=1356890&r1=1356889&r2=1356890&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 Tue Jul 3 19:45:51 2012
@@ -624,8 +624,13 @@ public class BTreeTest
btree.insert( key, value );
}
- // Now delete one element in the middle of a leaf
+ // Delete one element in the middle of a leaf
btree.delete( 10 );
assertNull( btree.find( 10 ) );
+
+ // Delete one element at the beginning of a leaf
+ btree.delete( 13 );
+ assertNull( btree.find( 13 ) );
+ assertEquals( Integer.valueOf( 14 ), ((Node<Integer, String>)btree.rootPage).keys[2] );
}
}
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=1356890&r1=1356889&r2=1356890&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 Tue Jul 3 19:45:51 2012
@@ -56,7 +56,7 @@ public class LeafTest
{
InsertResult<Long, String> result = leaf.insert( 1L, key, value );
- return (Leaf<Long, String>)((ModifyResult)result).modifiedPage;
+ return (Leaf<Long, String>)((ModifyResult<Long, String>)result).getModifiedPage();
}
@@ -111,8 +111,8 @@ public class LeafTest
assertTrue( result instanceof RemoveResult );
- Tuple<Long, String> removedElement = ((RemoveResult)result).removedElement;
- Page<Long, String> newLeaf = ((RemoveResult)result).modifiedPage;
+ Tuple<Long, String> removedElement = ((RemoveResult<Long, String>)result).getRemovedElement();
+ Page<Long, String> newLeaf = ((RemoveResult<Long, String>)result).getModifiedPage();
assertEquals( Long.valueOf( 3L), removedElement.getKey() );
assertEquals( "v3", removedElement.getValue() );
@@ -144,9 +144,9 @@ public class LeafTest
RemoveResult<Long, String> removeResult = (RemoveResult<Long, String>)result;
- Tuple<Long, String> removedElement = removeResult.removedElement;
- Page<Long, String> newLeaf = removeResult.modifiedPage;
- Long leftMost = removeResult.newLeftMost;
+ Tuple<Long, String> removedElement = removeResult.getRemovedElement();
+ Page<Long, String> newLeaf = removeResult.getModifiedPage();
+ Long leftMost = removeResult.getNewLeftMost();
assertEquals( Long.valueOf( 2L), leftMost );
assertEquals( Long.valueOf( 1L), removedElement.getKey() );
@@ -165,7 +165,7 @@ public class LeafTest
* an element in a left page with more than N/2 elements
*/
@Test
- public void testRemoveBorrowingFromLeftSibling()
+ public void testDeleteBorrowingFromLeftSibling()
{
Node<Long, String> parent = new Node<Long, String>( btree, 1L, 2 );
Leaf<Long, String> left = new Leaf<Long, String>( btree );
@@ -205,7 +205,7 @@ public class LeafTest
assertTrue( result instanceof BorrowedFromLeftResult );
BorrowedFromLeftResult<Long, String> borrowed = (BorrowedFromLeftResult<Long, String>)result;
- assertEquals( Long.valueOf( 5L ), borrowed.newLeftMost );
+ assertEquals( Long.valueOf( 5L ), borrowed.getNewLeftMost() );
Tuple<Long, String> removedKey = borrowed.getRemovedElement();
assertEquals( Long.valueOf( 7L ), removedKey.getKey() );
@@ -235,7 +235,7 @@ public class LeafTest
* an element in a right page with more than N/2 elements
*/
@Test
- public void testRemoveBorrowingFromRightSibling()
+ public void testDeleteBorrowingFromRightSibling()
{
Node<Long, String> parent = new Node<Long, String>( btree, 1L, 2 );
Leaf<Long, String> left = new Leaf<Long, String>( btree );
@@ -275,7 +275,7 @@ public class LeafTest
assertTrue( result instanceof BorrowedFromRightResult );
BorrowedFromRightResult<Long, String> borrowed = (BorrowedFromRightResult<Long, String>)result;
- assertEquals( Long.valueOf( 11L ), borrowed.newLeftMost );
+ assertEquals( Long.valueOf( 11L ), borrowed.getNewLeftMost() );
Tuple<Long, String> removedKey = borrowed.getRemovedElement();
assertEquals( Long.valueOf( 7L ), removedKey.getKey() );
@@ -305,7 +305,7 @@ public class LeafTest
* it with one of its sibling, if both has N/2 elements
*/
@Test
- public void testRemoveMergeWithSibling()
+ public void testDeleteMergeWithSibling()
{
Node<Long, String> parent = new Node<Long, String>( btree, 1L, 2 );
Leaf<Long, String> left = new Leaf<Long, String>( btree );
@@ -344,7 +344,7 @@ public class LeafTest
assertTrue( result instanceof MergedWithSiblingResult );
MergedWithSiblingResult<Long, String> merged = (MergedWithSiblingResult<Long, String>)result;
- assertEquals( Long.valueOf( 1L ), merged.newLeftMost );
+ assertEquals( Long.valueOf( 1L ), merged.getNewLeftMost() );
Tuple<Long, String> removedKey = merged.getRemovedElement();
assertEquals( Long.valueOf( 7L ), removedKey.getKey() );
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@labs.apache.org
For additional commands, e-mail: commits-help@labs.apache.org