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/25 13:22:34 UTC
svn commit: r1365521 - in /labs/mavibot/trunk/mavibot/src:
main/java/org/apache/mavibot/btree/Node.java
test/java/org/apache/mavibot/btree/BTreeTest.java
Author: elecharny
Date: Wed Jul 25 11:22:34 2012
New Revision: 1365521
URL: http://svn.apache.org/viewvc?rev=1365521&view=rev
Log:
o Added the borrowFromLeft method in Node
o Added some tests
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
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=1365521&r1=1365520&r2=1365521&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 Wed Jul 25 11:22:34 2012
@@ -280,6 +280,72 @@ import java.util.LinkedList;
/**
+ * Borrow an element from the left sibling, creating a new sibling with one
+ * less element and creating a new page where the element to remove has been
+ * deleted and the borrowed element added on the left.
+ *
+ * @param revision The new revision for all the pages
+ * @param sibling The left sibling
+ * @param pos The position of the element to remove
+ * @return The resulting pages
+ */
+ private DeleteResult<K, V> borrowFromLeft( long revision, MergedWithSiblingResult<K, V> mergedResult,
+ Node<K, V> sibling, int pos )
+ {
+ // The sibling is on the left, borrow the rightmost element
+ Page<K, V> siblingChild = sibling.children[sibling.nbElems];
+
+ // Create the new sibling, with one less element at the end
+ Node<K, V> newSibling = new Node<K, V>( btree, revision, sibling.getNbElems() - 1 );
+
+ // Copy the keys and children of the old sibling in the new sibling
+ System.arraycopy( sibling.keys, 0, newSibling.keys, 0, newSibling.getNbElems() );
+ System.arraycopy( sibling.children, 0, newSibling.children, 0, sibling.getNbElems() );
+
+ // Create the new page and add the new element at the beginning
+ // First copy the current node, with the same size
+ Node<K, V> newNode = new Node<K, V>( btree, revision, nbElems );
+
+ // Copy the keys and the values up to the insertion position
+ newNode.children[0] = siblingChild;
+
+ int index = Math.abs( pos );
+
+ if ( index == 0 )
+ {
+ newNode.keys[0] = mergedResult.getModifiedPage().getKey( 0 );
+ System.arraycopy( keys, 1, newNode.keys, 1, nbElems - 1 );
+
+ newNode.children[1] = mergedResult.getModifiedPage();
+ System.arraycopy( children, 2, newNode.children, 2, nbElems - 1 );
+ }
+ else
+ {
+ if ( index > 1 )
+ {
+ System.arraycopy( keys, 0, newNode.keys, 0, index - 1 );
+ System.arraycopy( children, 0, newNode.children, 1, index - 1 );
+ }
+
+ newNode.keys[index - 1] = mergedResult.getModifiedPage().getKey( 0 );
+ newNode.children[index] = mergedResult.getModifiedPage();
+
+ if ( index < nbElems )
+ {
+ System.arraycopy( keys, index, newNode.keys, index, nbElems - index );
+ System.arraycopy( children, index + 1, newNode.children, index + 1, nbElems - index );
+ }
+ }
+
+ // Create the result
+ DeleteResult<K, V> result = new BorrowedFromLeftResult<K, V>( newNode, newSibling,
+ mergedResult.getRemovedElement(), newNode.findLeftMost().getKey() );
+
+ return result;
+ }
+
+
+ /**
* {@inheritDoc}
*/
public DeleteResult<K, V> delete( long revision, K key, Page<K, V> parent, int parentPos )
@@ -372,9 +438,9 @@ import java.util.LinkedList;
// We can borrow the element from the sibling
if ( siblingPos < parentPos )
{
- //DeleteResult<K, V> result = borrowFromLeft( revision, sibling, pos );
+ DeleteResult<K, V> result = borrowFromLeft( revision, mergedResult, sibling, pos );
- return null;
+ return result;
}
else
{
@@ -428,7 +494,7 @@ import java.util.LinkedList;
else
{
// Update the keys
- newPage.keys[pos] = modifiedPage.getKey( 0 );
+ newPage.keys[pos] = modifiedPage.findLeftMost().getKey();
// Update the children
newPage.children[pos] = modifiedSibling;
@@ -449,7 +515,7 @@ import java.util.LinkedList;
else
{
// Update the keys
- newPage.keys[pos - 1] = modifiedPage.getKey( 0 );
+ newPage.keys[pos - 1] = modifiedPage.findLeftMost().getKey();
// Update the children
newPage.children[pos - 1] = modifiedSibling;
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=1365521&r1=1365520&r2=1365521&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 Jul 25 11:22:34 2012
@@ -1254,7 +1254,6 @@ public class BTreeTest
* 6: remove the first element of a leaf in the middle of the tree
*/
@Test
- @Ignore
public void testDeleteMultiLevelsLeadingToNodeBorrowLeft6() throws Exception
{
BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
@@ -1274,7 +1273,6 @@ public class BTreeTest
* 7: remove the second element of a leaf in the middle of the tree
*/
@Test
- @Ignore
public void testDeleteMultiLevelsLeadingToNodeBorrowLeft7() throws Exception
{
BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
@@ -1294,7 +1292,6 @@ public class BTreeTest
* 8: remove the last element of a leaf in the middle of the tree
*/
@Test
- @Ignore
public void testDeleteMultiLevelsLeadingToNodeBorrowLeft8() throws Exception
{
BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
@@ -1314,7 +1311,6 @@ public class BTreeTest
* 9: remove the element before the last one of a leaf in the middle of the tree
*/
@Test
- @Ignore
public void testDeleteMultiLevelsLeadingToNodeBorrowLeft9() throws Exception
{
BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
@@ -1334,7 +1330,6 @@ public class BTreeTest
* 10: remove the mid element of a leaf in the middle of the tree
*/
@Test
- @Ignore
public void testDeleteMultiLevelsLeadingToNodeBorrowLeft10() throws Exception
{
BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
@@ -1354,7 +1349,6 @@ public class BTreeTest
* 11: remove the mid+1 element of a leaf in the middle of the tree
*/
@Test
- @Ignore
public void testDeleteMultiLevelsLeadingToNodeBorrowLeft11() throws Exception
{
BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@labs.apache.org
For additional commands, e-mail: commits-help@labs.apache.org