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 2013/02/03 14:26:50 UTC
svn commit: r1441910 - in /labs/mavibot/trunk/mavibot/src:
main/java/org/apache/mavibot/btree/ test/java/org/apache/mavibot/btree/
Author: elecharny
Date: Sun Feb 3 13:26:50 2013
New Revision: 1441910
URL: http://svn.apache.org/viewvc?rev=1441910&view=rev
Log:
Added the exist() method, with the associated test
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/InMemoryBTreeTest.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=1441910&r1=1441909&r2=1441910&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 Feb 3 13:26:50 2013
@@ -803,6 +803,19 @@ public class BTree<K, V>
/**
+ * Check if there is an element associated with the given key.
+ *
+ * @param key The key we are looking at
+ * @return true if the Key exists in the BTree
+ * @throws IOException
+ */
+ public boolean exist( K key ) throws IOException
+ {
+ return rootPage.exist( key );
+ }
+
+
+ /**
* Find a value in the tree, given its key. if the key is not found,
* it will return null.
*
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=1441910&r1=1441909&r2=1441910&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 Feb 3 13:26:50 2013
@@ -371,6 +371,24 @@ public class Leaf<K, V> extends Abstract
/**
* {@inheritDoc}
*/
+ public boolean exist( K key )
+ {
+ int pos = findPos( key );
+
+ if ( pos < 0 )
+ {
+ return true;
+ }
+ else
+ {
+ return false;
+ }
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
public V get( K key ) throws KeyNotFoundException
{
int pos = findPos( key );
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=1441910&r1=1441909&r2=1441910&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 Feb 3 13:26:50 2013
@@ -20,6 +20,7 @@
package org.apache.mavibot.btree;
+import java.io.IOException;
import java.lang.reflect.Array;
import java.util.LinkedList;
@@ -729,6 +730,26 @@ import java.util.LinkedList;
/**
+ * {@inheritDoc}
+ */
+ public boolean exist( K key ) throws IOException
+ {
+ int pos = findPos( key );
+
+ if ( pos < 0 )
+ {
+ // Here, if we have found the key in the node, then we must go down into
+ // the right child, not the left one
+ return children[-pos].exist( key );
+ }
+ else
+ {
+ return children[pos].exist( key );
+ }
+ }
+
+
+ /**
* {@inheritDoc}
*/
public V get( K key ) throws KeyNotFoundException
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=1441910&r1=1441909&r2=1441910&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 Feb 3 13:26:50 2013
@@ -20,6 +20,7 @@
package org.apache.mavibot.btree;
+import java.io.IOException;
import java.util.LinkedList;
@@ -74,6 +75,16 @@ import java.util.LinkedList;
/**
+ * Check if there is an element associated with the given key.
+ *
+ * @param key The key we are looking at
+ * @return true if the Key exists in the BTree
+ * @throws IOException If we have an error while trying to access the page
+ */
+ boolean exist( K key ) throws IOException;
+
+
+ /**
* Get the value associated with the given key, if any. If we don't have
* one, this method will throw a KeyNotFoundException.<br/>
* Note that we may get back null if a null value has been associated
Modified: labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/InMemoryBTreeTest.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/InMemoryBTreeTest.java?rev=1441910&r1=1441909&r2=1441910&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/InMemoryBTreeTest.java (original)
+++ labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/InMemoryBTreeTest.java Sun Feb 3 13:26:50 2013
@@ -890,6 +890,25 @@ public class InMemoryBTreeTest
/**
+ * Test the exist() method
+ */
+ @Test
+ public void testExist() throws IOException
+ {
+ // Create a BTree with pages containing 4 elements
+ BTree<Integer, String> btree = createTwoLevelBTreeFullLeaves();
+
+ for ( int i = 1; i < 21; i++ )
+ {
+ assertTrue( btree.exist( 5 ) );
+ }
+
+ assertFalse( btree.exist( 0 ) );
+ assertFalse( btree.exist( 21 ) );
+ }
+
+
+ /**
* Test various deletions in a tree, leadings to borrowFromSibling
*/
@Test
@@ -1024,7 +1043,7 @@ public class InMemoryBTreeTest
// 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 };
+ { 1, 2, 5, 6, 3, 4, 9, 10, 7, 8, 13, 14, 11, 12, 17, 18, 15, 16, 19, 20 };
for ( int key : keys )
{
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@labs.apache.org
For additional commands, e-mail: commits-help@labs.apache.org