Author: elecharny
Date: Tue Jul 3 13:28:19 2012
New Revision: 1356721
URL: http://svn.apache.org/viewvc?rev=1356721&view=rev
Log:
o Implemented some use case of deletion in a Node
o Made the Result fields protected, added some setters/getters
o Moved the selectSibling method to the AbstractPage class
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/BTree.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/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/RemoveResult.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/AbstractDeleteResult.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractDeleteResult.java?rev=1356721&r1=1356720&r2=1356721&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
Tue Jul 3 13:28:19 2012
@@ -30,13 +30,13 @@ package org.apache.mavibot.btree;
/* No qualifier */ abstract class AbstractDeleteResult<K, V> implements
DeleteResult<K, V>
{
/** The modified page reference */
- protected Page<K, V> modifiedPage;
+ private Page<K, V> modifiedPage;
/** The removed element if the key was found in the tree*/
- protected Tuple<K, V> removedElement;
+ private Tuple<K, V> removedElement;
/** The new leftmost element if the removed k was on position 0. Null
otherwise */
- protected K newLeftMost;
+ private K newLeftMost;
/**
* The default constructor for AbstractDeleteResult.
@@ -78,4 +78,22 @@ package org.apache.mavibot.btree;
{
return newLeftMost;
}
+
+
+ /**
+ * @param modifiedPage the modifiedPage to set
+ */
+ /* No qualifier */ void setModifiedPage( Page<K, V> modifiedPage )
+ {
+ this.modifiedPage = modifiedPage;
+ }
+
+
+ /**
+ * @param newLeftMost the newLeftMost to set
+ */
+ /* No qualifier */ void setNewLeftMost( K newLeftMost )
+ {
+ this.newLeftMost = newLeftMost;
+ }
}
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=1356721&r1=1356720&r2=1356721&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
Tue Jul 3 13:28:19 2012
@@ -76,6 +76,47 @@ public abstract class AbstractPage<K, V>
id = btree.generateRecordId();
}
+
+
+ /**
+ * Select the sibling (the prev or next page with the same parent) which
has
+ * the more element assuming it's above N/2
+ *
+ * @param parent The parent of the current page
+ * @param The position of the current page reference in its parent
+ * @return The position of the sibling, or -1 if we hav'nt found any
sibling
+ */
+ protected int selectSibling( Node<K, V> parent, int parentPos )
+ {
+ if ( parentPos == 0 )
+ {
+ // The current page is referenced on the left of its parent's page
:
+ // we will not have a previous page with the same parent
+ return 1;
+ }
+
+ if ( parentPos == parent.getNbElems() )
+ {
+ // The current page is referenced on the right of its parent's
page :
+ // we will not have a next page with the same parent
+ return -1;
+ }
+
+ Page<K, V> prevPage = parent.children[parentPos - 1];
+ Page<K, V> nextPage = parent.children[parentPos + 1];
+
+ int prevPageSize = prevPage.getNbElems();
+ int nextPageSize = nextPage.getNbElems();
+
+ if ( prevPageSize >= nextPageSize )
+ {
+ return parentPos - 1;
+ }
+ else
+ {
+ return parentPos + 1;
+ }
+ }
/**
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BTree.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BTree.java?rev=1356721&r1=1356720&r2=1356721&view=diff
==============================================================================
---
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BTree.java
(original)
+++
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BTree.java
Tue Jul 3 13:28:19 2012
@@ -259,7 +259,7 @@ public class BTree<K, V>
// The element was found, and removed
RemoveResult<K, V> removeResult = (RemoveResult<K, V>)result;
- Page<K, V> newPage = removeResult.modifiedPage;
+ Page<K, V> newPage = removeResult.getModifiedPage();
// This is a new root
rootPage = newPage;
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=1356721&r1=1356720&r2=1356721&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
Tue Jul 3 13:28:19 2012
@@ -65,9 +65,9 @@ package org.apache.mavibot.btree;
{
StringBuilder sb = new StringBuilder();
- sb.append( "RemoveResult, removed element = " ).append( removedElement
);
- sb.append( ", modifiedPage = " ).append( modifiedPage );
- sb.append( ", new LeftMost = " ).append( newLeftMost );
+ sb.append( "RemoveResult, removed element = " ).append(
getRemovedElement() );
+ sb.append( ", modifiedPage = " ).append( getModifiedPage() );
+ sb.append( ", new LeftMost = " ).append( getNewLeftMost() );
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=1356721&r1=1356720&r2=1356721&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
Tue Jul 3 13:28:19 2012
@@ -63,9 +63,9 @@ package org.apache.mavibot.btree;
{
StringBuilder sb = new StringBuilder();
- sb.append( "RemoveResult, removed element = " ).append( removedElement
);
- sb.append( ", modifiedPage = " ).append( modifiedPage );
- sb.append( ", new LeftMost = " ).append( newLeftMost );
+ sb.append( "RemoveResult, removed element = " ).append(
getRemovedElement() );
+ sb.append( ", modifiedPage = " ).append( getModifiedPage() );
+ sb.append( ", new LeftMost = " ).append( getNewLeftMost() );
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=1356721&r1=1356720&r2=1356721&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
Tue Jul 3 13:28:19 2012
@@ -330,50 +330,9 @@ public class Leaf<K, V> extends Abstract
return result;
}
-
- /**
- * Select the sibling (the prev or next page with the same parent) which
has
- * the more element assuming it's above N/2
- *
- * @param parent The parent of the current page
- * @param The position of the current page reference in its parent
- * @return The position of the sibling, or -1 if we hav'nt found any
sibling
- */
- private int selectSibling( Node<K, V> parent, int parentPos )
- {
- if ( parentPos == 0 )
- {
- // The current page is referenced on the left of its parent's page
:
- // we will not have a previous page with the same parent
- return 1;
- }
-
- if ( parentPos == parent.getNbElems() )
- {
- // The current page is referenced on the right of its parent's
page :
- // we will not have a next page with the same parent
- return -1;
- }
-
- Page<K, V> prevPage = parent.children[parentPos - 1];
- Page<K, V> nextPage = parent.children[parentPos + 1];
-
- int prevPageSize = prevPage.getNbElems();
- int nextPageSize = nextPage.getNbElems();
-
- if ( prevPageSize >= nextPageSize )
- {
- return parentPos - 1;
- }
- else
- {
- return parentPos + 1;
- }
- }
-
/**
- * Remove the element at a given position. The
+ * Remove the element at a given position.
*
* @param revision The revision of the modified page
* @param pos The position into the page of the element to remove
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=1356721&r1=1356720&r2=1356721&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
Tue Jul 3 13:28:19 2012
@@ -50,9 +50,9 @@ package org.apache.mavibot.btree;
{
StringBuilder sb = new StringBuilder();
- sb.append( "MergedWithSiblingResult, removed element = " ).append(
removedElement );
- sb.append( ", modifiedPage = " ).append( modifiedPage );
- sb.append( ", new LeftMost = " ).append( newLeftMost );
+ sb.append( "MergedWithSiblingResult, removed element = " ).append(
getRemovedElement() );
+ sb.append( ", modifiedPage = " ).append( getModifiedPage() );
+ sb.append( ", 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=1356721&r1=1356720&r2=1356721&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 13:28:19 2012
@@ -148,8 +148,231 @@ import java.util.LinkedList;
*/
public DeleteResult<K, V> delete( long revision, K key, Page<K, V> parent,
int parentPos )
{
+ // We first try to delete the element from the child it belongs to
+ // Find the key in the page
+ int pos = findPos( key );
+
+ if ( pos < 0 )
+ {
+ // The key is present in the page
+ pos = - ( pos + 1 );
+
+ DeleteResult<K, V> deleteResult = children[pos].delete( revision,
key, this, pos );
+
+ if ( deleteResult instanceof NotPresentResult )
+ {
+ // Nothing to do...
+ return deleteResult;
+ }
+ else if ( deleteResult instanceof RemoveResult )
+ {
+ RemoveResult<K, V> removeResult = (RemoveResult<K,
V>)deleteResult;
+
+ // Simplest case : the element has been removed from the
underlying page,
+ // 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();
+
+ if ( removeResult.getNewLeftMost() != key )
+ {
+ newPage.keys[pos] = removeResult.getNewLeftMost();
+ }
+
+ // Modify the result and return
+ removeResult.setModifiedPage( this );
+ removeResult.setNewLeftMost( newPage.keys[0] );
+
+ return removeResult;
+ }
+ else if ( deleteResult instanceof BorrowedFromLeftResult )
+ {
+ 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 - 1] =
borrowedResult.getModifiedSibling();
+ newPage.children[pos] = 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] = borrowedResult.getModifiedPage();
+ newPage.children[pos + 1] =
borrowedResult.getModifiedSibling();
+
+ // 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 MergedWithSiblingResult )
+ {
+ MergedWithSiblingResult<K, V> mergedResult =
(MergedWithSiblingResult<K, V>)deleteResult;
+
+ // Here, we have to delete an element from the current page,
and if the resulting
+ // page does not contain enough elements (ie below N/2), then
we have to borrow
+ // one element from a sibling or merge the page with a sibling.
+
+ // If the parent is null, then this page is the root page.
+ if ( parent == null )
+ {
+ // If the current node contains only one key, then the
merged result will be
+ // the new root. Deal with this case
+ if ( nbElems == 1 )
+ {
+ RemoveResult<K, V> removeResult = new RemoveResult<K,
V>( mergedResult.getModifiedPage(),
+ mergedResult.getRemovedElement(),
mergedResult.getNewLeftMost() );
+
+ return removeResult;
+ }
+ else
+ {
+ // Just remove the entry if it's present
+ int index = findPos(
mergedResult.getRemovedElement().getKey() );
+
+ DeleteResult<K, V> result = removeKey( revision, index
);
+
+ return result;
+ }
+ }
+ else
+ {
+ // The current page is not the root. Check if the leaf has
more than N/2
+ // elements
+ int halfSize = btree.pageSize/2;
+
+ if ( nbElems == halfSize )
+ {
+ // We have to find a sibling now, and either borrow an
entry from it
+ // if it has more than N/2 elements, or to merge the
two pages.
+ // Check in both next and previous page, if they have
the same parent
+ // and select the biggest page with the same parent to
borrow an element.
+ int siblingPos = selectSibling( (Node<K, V>)parent,
parentPos );
+
+ Leaf<K, V> sibling = (Leaf<K, V>)((Node<K,
V>)parent).children[siblingPos];
+
+ if ( sibling.getNbElems() == halfSize )
+ {
+ // We will merge the current page with its sibling
+ //DeleteResult<K, V> result = mergeWithSibling(
revision, sibling, ( siblingPos < pos), pos );
+
+ return null; //result;
+ }
+ else
+ {
+ // We can borrow the element from the sibling
+ if ( siblingPos < parentPos )
+ {
+ //DeleteResult<K, V> result = borrowFromLeft(
revision, sibling, pos );
+
+ return null; //result;
+ }
+ else
+ {
+ // Borrow from the right
+ //DeleteResult<K, V> result = borrowFromRight(
revision, sibling, pos );
+
+ return null; //result;
+ }
+ }
+ }
+ else
+ {
+ // The page has more than N/2 elements.
+ // 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 );
+
+ return result;
+ }
+ }
+ }
+ }
+ else
+ {
+ // The key is not present in the node. Copy the node, update the
references, and return
+ // the result
+ DeleteResult<K, V> deleteResult = children[pos].delete( revision,
key, this, pos );
+
+ if ( deleteResult instanceof RemoveResult )
+ {
+ RemoveResult<K, V> removeResult = (RemoveResult<K,
V>)deleteResult;
+
+ // Simplest case : the element has been removed from the
underlying page,
+ // 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();
+
+ if ( removeResult.getNewLeftMost() != null )
+ {
+ newPage.keys[pos] = removeResult.getNewLeftMost();
+ }
+
+ // Modify the result and return
+ removeResult.setModifiedPage( newPage );
+ removeResult.setNewLeftMost( newPage.keys[0] );
+
+ return removeResult;
+ }
+ }
+
+
return null;
}
+
+
+ /**
+ * Remove the key at a given position.
+ *
+ * @param revision The revision of the modified page
+ * @param pos The position into the page of the element to remove
+ * @return The modified page with the <K,V> element added
+ */
+ private DeleteResult<K, V> removeKey( long revision,int pos )
+ {
+ // Get the removed element
+ Tuple<K, V> removedElement = new Tuple<K, V>( keys[pos], null );
+
+ // First copy the current page, but remove one element in the copied
page
+ Node<K, V> newNode = new Node<K, V>( btree, revision, nbElems - 1 );
+
+ K newLeftMost = null;
+
+ // Deal with the special case of a node with only one element by
skipping
+ // the copy, as we won't have any remaining element in the page
+ // Copy the keys and the children up to the insertion position
+ System.arraycopy( keys, 0, newNode.keys, 0, pos );
+ System.arraycopy( children, 0, newNode.children, 0, pos );
+
+ // And copy the elements after the position
+ System.arraycopy( keys, pos + 1, newNode.keys, pos, keys.length - pos
- 1 );
+ System.arraycopy( children, pos + 1, newNode.children, pos,
children.length - pos - 1 );
+
+ if ( pos == 0 )
+ {
+ newLeftMost = newNode.keys[0];
+ }
+
+ // Create the result
+ DeleteResult<K, V> result = new RemoveResult<K, V>( newNode,
removedElement, newLeftMost );
+
+ return result;
+ }
/**
@@ -378,15 +601,15 @@ import java.util.LinkedList;
* @param revision The new revision
* @return The copied page
*/
- protected Page<K, V> copy( long revision )
+ protected Node<K, V> copy( long revision )
{
- Page<K, V> newPage = new Node<K, V>( btree, revision, nbElems );
+ Node<K, V> newPage = new Node<K, V>( btree, revision, nbElems );
// Copy the keys
- System.arraycopy( keys, 0, ((Node<K, V>)newPage).keys, 0, nbElems );
+ System.arraycopy( keys, 0, newPage.keys, 0, nbElems );
// Copy the children
- System.arraycopy( children, 0, ((Node<K, V>)newPage).children, 0,
nbElems + 1);
+ System.arraycopy( children, 0, newPage.children, 0, nbElems + 1);
return newPage;
}
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/RemoveResult.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/RemoveResult.java?rev=1356721&r1=1356720&r2=1356721&view=diff
==============================================================================
---
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/RemoveResult.java
(original)
+++
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/RemoveResult.java
Tue Jul 3 13:28:19 2012
@@ -50,9 +50,9 @@ package org.apache.mavibot.btree;
{
StringBuilder sb = new StringBuilder();
- sb.append( "RemoveResult, removed element = " ).append( removedElement
);
- sb.append( ", modifiedPage = " ).append( modifiedPage );
- sb.append( ", new LeftMost = " ).append( newLeftMost );
+ sb.append( "RemoveResult, removed element = " ).append(
getRemovedElement() );
+ sb.append( ", modifiedPage = " ).append( getModifiedPage() );
+ sb.append( ", new LeftMost = " ).append( getNewLeftMost() );
return sb.toString();
}
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=1356721&r1=1356720&r2=1356721&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 13:28:19 2012
@@ -33,6 +33,7 @@ import org.junit.Test;
import static org.junit.Assert.assertTrue;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertNull;
import static org.junit.Assert.assertEquals;
@@ -605,4 +606,26 @@ public class BTreeTest
cursor.close();
}
+
+
+ @Test
+ public void testDelete() throws Exception
+ {
+ // Create a BTree with pages containing 4 elements
+ BTree<Integer, String> btree = new BTree<Integer, String>( new
IntComparator() );
+ btree.setPageSize( 4 );
+
+ // Create a tree with 5 children containing 4 elements each. The tree
is full.
+ int[] keys = new int[] {1, 2, 5, 6, 3, 4, 9, 10, 7, 8, 9, 10, 7, 8,
13, 14, 11, 12, 17, 18, 15, 16, 19, 20 };
+
+ for ( int key : keys )
+ {
+ String value = "V" + key;
+ btree.insert( key, value );
+ }
+
+ // Now delete one element in the middle of a leaf
+ btree.delete( 10 );
+ assertNull( btree.find( 10 ) );
+ }
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
