Author: elecharny
Date: Sun Jun 24 23:41:08 2012
New Revision: 1353362
URL: http://svn.apache.org/viewvc?rev=1353362&view=rev
Log:
o Added the delete() method in BTree, with a preliminary implementation that
only works for removing in the root page
o Added a test for the delete method
o Added some classes to propagate the result of a delete operation
Added:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/DeleteResult.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/NotPresentResult.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/RemoveResult.java
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BTree.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/Node.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.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/BTree.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BTree.java?rev=1353362&r1=1353361&r2=1353362&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
Sun Jun 24 23:41:08 2012
@@ -191,6 +191,80 @@ public class BTree<K, V>
/**
+ * Delete the entry whch key is given as a parameter. If the entry exists,
it will
+ * be removed from the tree, the old tuple will be returned. Otherwise,
null is returned.
+ *
+ * @param key The key for the entry we try to remove
+ * @return A Tuple<K, V> containing the removed entry, or null if it's not
found.
+ */
+ public Tuple<K, V> delete( K key ) throws IOException
+ {
+ if ( key == null )
+ {
+ throw new IllegalArgumentException( "Key must not be null" );
+ }
+
+ long revision = generateRevision();
+
+ return delete( key, revision );
+ }
+
+
+ /**
+ * Delete the entry which key is given as a parameter. If the entry
exists, it will
+ * be removed from the tree, the old tuple will be returned. Otherwise,
null is returned.
+ *
+ * @param key The key for the entry we try to remove
+ * @return A Tuple<K, V> containing the removed entry, or null if it's not
found.
+ */
+ private Tuple<K, V> delete( K key, long revision ) throws IOException
+ {
+ // Commented atm, we will have to play around the idea of transactions
later
+ //acquireWriteLock();
+
+ try
+ {
+ // If the key exists, the existing value will be replaced. We
store it
+ // to return it to the caller.
+ Tuple<K, V> tuple = null;
+
+ // Try to delete the entry starting from the root page. Here, the
root
+ // page may be either a Node or a Leaf
+ DeleteResult<K, V> result = rootPage.delete( revision, key, null );
+
+ if ( result instanceof NotPresentResult )
+ {
+ // Key not found.
+ return null;
+ }
+
+ if ( result instanceof RemoveResult )
+ {
+ // The element was found, and removed
+ RemoveResult<K, V> removeResult = (RemoveResult<K, V>)result;
+
+ Page<K, V> newPage = removeResult.modifiedPage;
+
+ // This is a new root
+ rootPage = newPage;
+ tuple = removeResult.getRemovedElement();
+ }
+
+ // Save the rootPage into the roots with the new revision.
+ roots.put( revision, rootPage );
+
+ // Return the value we have found if it was modified
+ return tuple;
+ }
+ finally
+ {
+ // See above
+ //releaseWriteLock()
+ }
+ }
+
+
+ /**
* Find a value in the tree, given its key. if the key is not found,
* it will return null.
*
Added:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/DeleteResult.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/DeleteResult.java?rev=1353362&view=auto
==============================================================================
---
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/DeleteResult.java
(added)
+++
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/DeleteResult.java
Sun Jun 24 23:41:08 2012
@@ -0,0 +1,32 @@
+/*
+ * 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 an delete operation.
+ *
+ * @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>
+ */
+interface DeleteResult<K, V>
+{
+}
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=1353362&r1=1353361&r2=1353362&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
Sun Jun 24 23:41:08 2012
@@ -98,6 +98,77 @@ public class Leaf<K, V> extends Abstract
return result;
}
}
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public DeleteResult<K, V> delete( long revision, K key, Page<K, V> parent )
+ {
+ // Find the key in the page
+ int pos = findPos( key );
+
+ // If the parent is null, then this page is the root page.
+ if ( parent == null )
+ {
+ // Just remove the entry if it's present
+ if ( pos < 0 )
+ {
+ DeleteResult<K, V> result = removeElementFromRoot( revision,
-( pos + 1 ) );
+
+ return result;
+ }
+ else
+ {
+ // Not found : retur the not present result.
+ return NotPresentResult.NOT_PRESENT;
+ }
+ }
+ else
+ {
+ // The current page is not the root
+ return null;
+ }
+ }
+
+
+ /**
+ * Remove the element at a given position. The
+ *
+ * @param revision The revision of the modified page
+ * @param key The key to insert
+ * @param value The value to insert
+ * @param pos The position into the page
+ * @return The modified page with the <K,V> element added
+ */
+ private DeleteResult<K, V> removeElementFromRoot( long revision,int pos )
+ {
+ // First copy the current page, but remove one element in the copied
page
+ Leaf<K, V> newRoot = new Leaf<K, V>( btree, revision, nbElems - 1 );
+
+ // Get the removed element
+ Tuple<K, V> removedElement = new Tuple<K, V>();
+ removedElement.setKey( keys[pos] );
+ removedElement.setValue( values[pos] );
+
+ // Deal with the special case of an page with only one element by
skipping
+ // the copy, as we won't have any remaining element in the page
+ if ( nbElems > 1 )
+ {
+ // Copy the keys and the values up to the insertion position
+ System.arraycopy( keys, 0, newRoot.keys, 0, pos );
+ System.arraycopy( values, 0, newRoot.values, 0, pos );
+
+ // And copy the elements after the position
+ System.arraycopy( keys, pos + 1, newRoot.keys, pos, keys.length -
pos - 1 );
+ System.arraycopy( values, pos + 1, newRoot.values, pos,
values.length - pos - 1 );
+ }
+
+ // Create the result
+ DeleteResult<K, V> result = new RemoveResult<K, V>( newRoot,
removedElement );
+
+ return result;
+ }
/**
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=1353362&r1=1353361&r2=1353362&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
Sun Jun 24 23:41:08 2012
@@ -41,9 +41,7 @@ public class Node<K, V> extends Abstract
*
* @param btree the parent BTree
* @param revision the Node revision
- * @param key The new key
- * @param leftPage The left page
- * @param rightPage The right page
+ * @param nbElems The number of elements in this Node
*/
/* No qualifier */ Node( BTree<K, V> btree, long revision, int nbElems )
{
@@ -139,6 +137,15 @@ public class Node<K, V> extends Abstract
/**
* {@inheritDoc}
*/
+ public DeleteResult<K, V> delete( long revision, K key, Page<K, V> parent )
+ {
+ return null;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
public V find( K key )
{
int pos = findPos( key );
Added:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/NotPresentResult.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/NotPresentResult.java?rev=1353362&view=auto
==============================================================================
---
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/NotPresentResult.java
(added)
+++
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/NotPresentResult.java
Sun Jun 24 23:41:08 2012
@@ -0,0 +1,38 @@
+/*
+ * 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 an delete operation, when the key to delete is not present in
the tree.
+ *
+ * @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>
+ */
+class NotPresentResult<K, V> implements DeleteResult<K, V>
+{
+ public static final NotPresentResult NOT_PRESENT = new NotPresentResult();
+
+ private NotPresentResult()
+ {
+ // Do nothing
+ }
+}
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java?rev=1353362&r1=1353361&r2=1353362&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java
(original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java
Sun Jun 24 23:41:08 2012
@@ -53,6 +53,19 @@ public interface Page<K, V>
* @return Either a modified Page or an Overflow element if the Page was
full
*/
InsertResult<K, V> insert( long revision, K key, V value );
+
+
+ /**
+ * delete an entry with the given key from this page. We first find the
place were to
+ * remove the <K,V> into the tree, by recursively browsing the pages :<br/>
+ * <p>
+ *
+ * @param revision The new revision for the modified pages
+ * @param key The key to delete
+ * @param parent The parent page
+ * @return
+ */
+ DeleteResult<K, V> delete( long revision, K key, Page<K, V> parent );
/**
@@ -91,7 +104,7 @@ public interface Page<K, V>
/**
- * @return the id
+ * @return the page ID
*/
long getId();
Added:
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=1353362&view=auto
==============================================================================
---
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/RemoveResult.java
(added)
+++
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/RemoveResult.java
Sun Jun 24 23:41:08 2012
@@ -0,0 +1,82 @@
+/*
+ * 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 RemoveResult<K, V> implements DeleteResult<K, V>
+{
+ /** The modified page reference */
+ protected Page<K, V> modifiedPage;
+
+ /** The removed element if the key was found in the tree*/
+ protected Tuple<K, V> removedElement;
+
+ /**
+ * The default constructor for RemoveResult.
+ *
+ * @param modifiedPage The modified page
+ * @param removedElement The removed element (can be null if the key
wasn't present in the tree)
+ */
+ public RemoveResult( Page<K, V> modifiedPage, Tuple<K, V> removedElement )
+ {
+ this.modifiedPage = modifiedPage;
+ this.removedElement = removedElement;
+ }
+
+
+ /**
+ * @return the modifiedPage
+ */
+ public Page<K, V> getModifiedPage()
+ {
+ return modifiedPage;
+ }
+
+
+ /**
+ * @return the removed element
+ */
+ public Tuple<K, V> getRemovedElement()
+ {
+ return removedElement;
+ }
+
+
+ /**
+ * @see Object#toString()
+ */
+ public String toString()
+ {
+ StringBuilder sb = new StringBuilder();
+
+ sb.append( "RemoveResult, removed element = " ).append( removedElement
);
+ sb.append( ", modifiedPage = " ).append( modifiedPage );
+
+ 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=1353362&r1=1353361&r2=1353362&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
Sun Jun 24 23:41:08 2012
@@ -210,6 +210,64 @@ public class BTreeTest
System.out.println( "Delta : " + ( l2 - l1 ) + ", nbError = " +
nbError );
}
+
+
+ /**
+ * Test the deletion of elements from a BTree.
+ */
+ @Test
+ public void testPageDelete() throws Exception
+ {
+ Set<Long> expected = new HashSet<Long>();
+ List<Long> added = new ArrayList<Long>();
+
+ Random random = new Random( System.nanoTime() );
+
+ BTree<Long, String> btree = new BTree<Long, String>( new
LongComparator() );
+ btree.setPageSize( 8 );
+
+ // Insert some values
+ for ( int i = 0; i < 8; i++ )
+ {
+ Long key = (long)random.nextInt( 1024 );
+ String value = "V" + key;
+ added.add( key );
+
+ try
+ {
+ btree.insert( key, value );
+ }
+ catch ( Exception e)
+ {
+ e.printStackTrace();
+ System.out.println( btree );
+ System.out.println( "Error while adding " + value );
+ return;
+ }
+ }
+
+ assertTrue( checkTree( expected, btree ) );
+
+ // Now, delete entries
+ for ( long key : added )
+ {
+ System.out.println( "Removing " + key + " from " + btree );
+ try
+ {
+ btree.delete( key );
+ }
+ catch ( Exception e)
+ {
+ e.printStackTrace();
+ System.out.println( btree );
+ System.out.println( "Error while deleting " + key );
+ return;
+ }
+
+ assertTrue( checkTree( expected, btree ) );
+ }
+
+ }
/**
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
