You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@labs.apache.org by ka...@apache.org on 2013/04/14 16:37:55 UTC
svn commit: r1467782 - in
/labs/mavibot/branches/mavibot-multivalue-support/mavibot/src:
main/java/org/apache/mavibot/btree/Cursor.java
test/java/org/apache/mavibot/btree/BTreeDuplicateKeyTest.java
Author: kayyagari
Date: Sun Apr 14 14:37:54 2013
New Revision: 1467782
URL: http://svn.apache.org/r1467782
Log:
o fixed the moveToXXX methods
o added more tests
Modified:
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/Cursor.java
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/test/java/org/apache/mavibot/btree/BTreeDuplicateKeyTest.java
Modified: labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/Cursor.java
URL: http://svn.apache.org/viewvc/labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/Cursor.java?rev=1467782&r1=1467781&r2=1467782&view=diff
==============================================================================
--- labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/Cursor.java (original)
+++ labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/Cursor.java Sun Apr 14 14:37:54 2013
@@ -99,7 +99,9 @@ public class Cursor<K, V>
// parent, and down to the leaf
parentPos = findNextParentPos();
- if ( parentPos.page == null )
+ // we also need to check for the type of page cause
+ // findNextParentPos will never return a null ParentPos
+ if ( parentPos.page == null || ( parentPos.page instanceof Node ) )
{
// This is the end : no more value
throw new NoSuchElementException( "No more tuples present" );
@@ -164,7 +166,7 @@ public class Cursor<K, V>
if ( parentPos == null )
{
stack.push( lastParentPos );
- return null;
+ return lastParentPos;
}
if ( parentPos.pos == parentPos.page.getNbElems() )
@@ -191,7 +193,7 @@ public class Cursor<K, V>
if( allowDuplicates )
{
- setDupsContainer( newParentPos, btree );
+ changeNextDupsContainer( newParentPos, btree );
}
return newParentPos;
@@ -280,7 +282,9 @@ public class Cursor<K, V>
// parent, and down to the leaf
parentPos = findPreviousParentPos();
- if ( parentPos.page == null )
+ // we also need to check for the type of page cause
+ // findPrevParentPos will never return a null ParentPos
+ if ( parentPos.page == null || ( parentPos.page instanceof Node ) )
{
// This is the end : no more value
throw new NoSuchElementException( "No more tuples present" );
@@ -288,7 +292,6 @@ public class Cursor<K, V>
}
Leaf<K, V> leaf = ( Leaf<K, V> ) ( parentPos.page );
-
if( allowDuplicates )
{
@@ -452,11 +455,20 @@ public class Cursor<K, V>
return;
}
- if ( parentPos.pos == parentPos.page.getNbElems() )
+ if ( parentPos.pos == ( parentPos.page.getNbElems() - 1 ) )
{
// End of the leaf. We have to go back into the stack up to the
// parent, and down to the leaf
+ // increment the position cause findNextParentPos checks "parentPos.pos == parentPos.page.getNbElems()"
+ parentPos.pos++;
parentPos = findNextParentPos();
+
+ // if the returned value is a Node that means cursor is already at the last position
+ // call afterLast() to restore the stack with the path to the right most element
+ if( parentPos.page instanceof Node )
+ {
+ afterLast();
+ }
}
else
{
@@ -497,6 +509,13 @@ public class Cursor<K, V>
// End of the leaf. We have to go back into the stack up to the
// parent, and down to the leaf
parentPos = findPreviousParentPos();
+
+ // if the returned value is a Node that means cursor is already at the first position
+ // call beforeFirst() to restore the stack to the initial state
+ if( parentPos.page instanceof Node )
+ {
+ beforeFirst();
+ }
}
else
{
Modified: labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/test/java/org/apache/mavibot/btree/BTreeDuplicateKeyTest.java
URL: http://svn.apache.org/viewvc/labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/test/java/org/apache/mavibot/btree/BTreeDuplicateKeyTest.java?rev=1467782&r1=1467781&r2=1467782&view=diff
==============================================================================
--- labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/test/java/org/apache/mavibot/btree/BTreeDuplicateKeyTest.java (original)
+++ labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/test/java/org/apache/mavibot/btree/BTreeDuplicateKeyTest.java Sun Apr 14 14:37:54 2013
@@ -20,9 +20,12 @@
package org.apache.mavibot.btree;
-import static org.junit.Assert.*;
+import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertNull;
import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
import java.io.IOException;
import java.util.NoSuchElementException;
@@ -360,7 +363,7 @@ public class BTreeDuplicateKeyTest
}
- @Test
+ @Test(expected = NoSuchElementException.class)
public void testMoveLast() throws Exception
{
StringSerializer serializer = new StringSerializer();
@@ -389,10 +392,15 @@ public class BTreeDuplicateKeyTest
cursor.beforeFirst();
assertEquals( "c", cursor.next().getKey() );
+
+ cursor.afterLast();
+ assertFalse( cursor.hasNext() );
+ // make sure it throws NoSuchElementException
+ cursor.next();
}
- @Test
+ @Test(expected = NoSuchElementException.class)
public void testMoveToNextPrevNonDuplicateKey() throws Exception
{
StringSerializer serializer = new StringSerializer();
@@ -471,5 +479,142 @@ public class BTreeDuplicateKeyTest
tuple = cursor.next();
assertEquals( "a", tuple.getKey() );
assertEquals( "0", tuple.getValue() );
+
+ cursor.close();
+
+ cursor = btree.browseFrom("y");
+ cursor.moveToNextNonDuplicateKey();
+ assertTrue( cursor.hasPrev() );
+ tuple = cursor.prev();
+ assertEquals( "y", tuple.getKey() );
+ assertEquals( "6", tuple.getValue() );
+ cursor.close();
+
+ cursor = btree.browse();
+ cursor.beforeFirst();
+ assertFalse( cursor.hasPrev() );
+ // make sure it throws NoSuchElementException
+ cursor.prev();
+ }
+
+
+ /**
+ * Test for moving between two leaves. When moveToNextNonDuplicateKey is called
+ * and cursor is on the last element of the current leaf.
+ *
+ * @throws Exception
+ */
+ @Test
+ public void testMoveToNextAndPrevWithPageBoundaries() throws Exception
+ {
+ IntSerializer serializer = new IntSerializer();
+
+ BTreeConfiguration<Integer, Integer> config = new BTreeConfiguration<Integer, Integer>();
+ config.setAllowDuplicates( true );
+ config.setName( "master" );
+ config.setPageSize( 4 );
+ config.setSerializers( serializer, serializer );
+ BTree<Integer, Integer> btree = new BTree<Integer, Integer>( config );
+
+ int i = 7;
+ for ( int k=0; k < i; k++ )
+ {
+ btree.insert( k, k );
+ }
+
+ // 3 is the last element of the first leaf
+ Cursor<Integer, Integer> cursor = btree.browseFrom(3);
+ cursor.moveToNextNonDuplicateKey();
+
+ assertTrue( cursor.hasNext() );
+ Tuple<Integer, Integer> tuple = cursor.next();
+ assertEquals( Integer.valueOf( 4 ), tuple.getKey() );
+ assertEquals( Integer.valueOf( 4 ), tuple.getValue() );
+ cursor.close();
+
+ cursor = btree.browseFrom(3);
+ cursor.moveToNextNonDuplicateKey();
+
+ assertTrue( cursor.hasPrev() );
+ tuple = cursor.prev();
+ assertEquals( Integer.valueOf( 3 ), tuple.getKey() );
+ assertEquals( Integer.valueOf( 3 ), tuple.getValue() );
+ cursor.close();
+
+ // 4 is the first element of the second leaf
+ cursor = btree.browseFrom(4);
+ cursor.moveToPrevNonDuplicateKey();
+
+ assertTrue( cursor.hasPrev() );
+ tuple = cursor.prev();
+ assertEquals( Integer.valueOf( 3 ), tuple.getKey() );
+ assertEquals( Integer.valueOf( 3 ), tuple.getValue() );
+
+ // the below assertion won't work cause of the index position
+ // issue when prev() and next() are called subsequently (in any order)
+// assertTrue( cursor.hasNext() );
+// tuple = cursor.next();
+// assertEquals( Integer.valueOf( 4 ), tuple.getKey() );
+// assertEquals( Integer.valueOf( 4 ), tuple.getValue() );
+ cursor.close();
+
+ // test the extremes of the BTree instead of that of leaves
+ cursor = btree.browseFrom(6);
+ cursor.moveToNextNonDuplicateKey();
+ assertFalse( cursor.hasNext() );
+ assertTrue( cursor.hasPrev() );
+ tuple = cursor.prev();
+ assertEquals( Integer.valueOf( 6 ), tuple.getKey() );
+ assertEquals( Integer.valueOf( 6 ), tuple.getValue() );
+ cursor.close();
+
+ cursor = btree.browse();
+ cursor.moveToPrevNonDuplicateKey();
+ assertTrue( cursor.hasNext() );
+ assertFalse( cursor.hasPrev() );
+ tuple = cursor.next();
+ assertEquals( Integer.valueOf( 0 ), tuple.getKey() );
+ assertEquals( Integer.valueOf( 0 ), tuple.getValue() );
+ cursor.close();
+ }
+
+
+ @Test
+ public void testNextAfterPrev() throws Exception
+ {
+ IntSerializer serializer = new IntSerializer();
+
+ BTreeConfiguration<Integer, Integer> config = new BTreeConfiguration<Integer, Integer>();
+ config.setAllowDuplicates( true );
+ config.setName( "master" );
+ config.setPageSize( 4 );
+ config.setSerializers( serializer, serializer );
+ BTree<Integer, Integer> btree = new BTree<Integer, Integer>( config );
+
+ int i = 7;
+ for ( int k=0; k < i; k++ )
+ {
+ btree.insert( k, k );
+ }
+
+ // 3 is the last element of the first leaf
+ Cursor<Integer, Integer> cursor = btree.browseFrom(4);
+
+ assertTrue( cursor.hasNext() );
+ Tuple<Integer, Integer> tuple = cursor.next();
+ assertEquals( Integer.valueOf( 4 ), tuple.getKey() );
+ assertEquals( Integer.valueOf( 4 ), tuple.getValue() );
+
+ assertTrue( cursor.hasPrev() );
+ tuple = cursor.prev();
+ assertEquals( Integer.valueOf( 4 ), tuple.getKey() );
+ assertEquals( Integer.valueOf( 4 ), tuple.getValue() );
+
+ assertTrue( cursor.hasNext() );
+ tuple = cursor.next();
+ assertEquals( Integer.valueOf( 4 ), tuple.getKey() );
+ assertEquals( Integer.valueOf( 4 ), tuple.getValue() );
+ cursor.close();
+
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@labs.apache.org
For additional commands, e-mail: commits-help@labs.apache.org