Author: elecharny
Date: Wed Jun 20 13:08:17 2012
New Revision: 1352082
URL: http://svn.apache.org/viewvc?rev=1352082&view=rev
Log:
o Fixed the tests
o Fixed several bugs in the Node.addAndSplit() method (using the wrong page,
the wrong index, in two different cases)
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=1352082&r1=1352081&r2=1352082&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 Jun 20 13:08:17 2012
@@ -273,13 +273,11 @@ public class Node<K, V> extends Abstract
// Copy the keys and the children up to the insertion position
System.arraycopy( keys, 0, newLeftPage.keys, 0, middle );
System.arraycopy( children, 0, newLeftPage.children, 0, middle );
+ newLeftPage.children[middle] = leftPage;
// And process the right page now
- System.arraycopy( keys, middle, newLeftPage.keys, 0, middle );
- System.arraycopy( children, middle, newLeftPage.children, 1,
middle );
-
- // add the new references
- newLeftPage.children[middle] = leftPage;
+ System.arraycopy( keys, middle, newRightPage.keys, 0, middle );
+ System.arraycopy( children, middle + 1, newRightPage.children, 1,
middle );
newRightPage.children[0] = rightPage;
// Create the result
@@ -303,8 +301,8 @@ public class Node<K, V> extends Abstract
newRightPage.children[pos - middle] = rightPage;
// And copy the remaining elements minus the new pivot
- System.arraycopy( keys, pos, newLeftPage.keys, pos - middle,
nbElems - pos );
- System.arraycopy( children, pos, newLeftPage.children, pos + 1 -
middle, nbElems - pos );
+ System.arraycopy( keys, pos, newRightPage.keys, pos - middle,
nbElems - pos );
+ System.arraycopy( children, pos + 1, newRightPage.children, pos +
1 - middle, nbElems - pos );
// Create the result
InsertResult<K, V> result = new SplitResult<K, V>( keys[middle],
newLeftPage, newRightPage );
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=1352082&r1=1352081&r2=1352082&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 Jun 20 13:08:17 2012
@@ -38,8 +38,13 @@ import static org.junit.Assert.assertTru
*/
public class BTreeTest
{
+ /**
+ * Checks the created BTree contains the expected values
+ */
private boolean checkTree( Set<Long> expected, BTree<Long, String> btree )
throws IOException
{
+ // We loop on all the expected value to see if they have correctly
been inserted
+ // into the btree
for ( Long key : expected )
{
String value = btree.find( key );
@@ -48,69 +53,19 @@ public class BTreeTest
{
return false;
}
-
- //System.out.println( "found : " + value );
}
return true;
}
- private BTree<Long, String> loadTree( Long[] keys, String[] values )
throws IOException
- {
- BTree<Long, String> btree = new BTree<Long, String>( new
LongComparator(), 16 );
-
- for ( int i = 0; i < keys.length; i++ )
- {
- btree.insert( keys[i], values[i] );
- }
-
- return btree;
- }
-
-
- private void dump( List<Long> added )
- {
- boolean isFirst = true;
-
- for ( Long element : added )
- {
- if ( isFirst )
- {
- isFirst = false;
- }
- else
- {
- System.out.print( ", " );
- }
-
- System.out.print( element + "L" );
- }
-
- System.out.println();
- }
-
-
- @Test
- public void testPageInsert1() throws Exception
- {
- BTree<Long, String> btree = new BTree<Long, String>( new
LongComparator() );
-
- Long key = Long.valueOf( 10 );
- String value = "V10";
- btree.insert( key, value );
-
- key = Long.valueOf( 5 );
- value = "V5";
- btree.insert( key, value );
-
- key = Long.valueOf( 15 );
- value = "V15";
- btree.insert( key, value );
-
- //System.out.println( btree );
- }
-
+ /**
+ * Test the insertion of elements in a BTree. We will try 1000 times to
insert 1000
+ * random elements in [0..1024], and check every tree to see if all the
added elements
+ * are present. This pretty much validate the the insertion, assuming that
due to the
+ * randomization of the injected values, we will statically meet all the
use cases.
+ * @throws Exception
+ */
@Test
public void testPageInsert() throws Exception
{
@@ -123,14 +78,14 @@ public class BTreeTest
long l1 = System.currentTimeMillis();
- for ( int j = 0; j < 100; j++ )
+ for ( int j = 0; j < 1000; j++ )
{
BTree<Long, String> btree = new BTree<Long, String>( new
LongComparator() );
btree.setPageSize( 8 );
- for ( int i = 0; i < 65536; i++ )
+ for ( int i = 0; i < 1000; i++ )
{
- Long key = (long)random.nextInt( 256 );
+ Long key = (long)random.nextInt( 1024 );
String value = "V" + key;
expected.add( key );
added.add( key );
@@ -146,21 +101,33 @@ public class BTreeTest
e.printStackTrace();
System.out.println( btree );
System.out.println( "Error while adding " + value );
- dump( added );
nbError++;
return;
}
-
- //System.out.println( btree );
- //dump( added );
}
+ assertTrue( checkTree( expected, btree ) );
+
+ /* For debug only
if ( !checkTree( expected, btree ) )
{
- System.out.println( btree );
+ boolean isFirst = true;
+
+ for ( Long key : added )
+ {
+ if ( isFirst )
+ {
+ isFirst = false;
+ }
+ else
+ {
+ System.out.print( ", " );
+ }
+
+ System.out.print( key );
+ }
}
-
- assertTrue( checkTree( expected, btree ) );
+ */
expected.clear();
added.clear();
@@ -172,81 +139,55 @@ public class BTreeTest
}
- @Test
- public void testPageInsertEven() throws Exception
- {
- Long[] keys = new Long[]{ 2L, 4L, 6L, 8L };
- String[] values = new String[]{ "V2", "V4", "V6", "V8" };
-
- BTree<Long, String> btree = loadTree( keys, values );
-
- // Insert 1L
- btree.insert( 1L, "V1" );
-
- System.out.println( btree );
-
- btree = loadTree( keys, values );
-
- // Insert 3L
- btree.insert( 3L, "V3" );
-
- System.out.println( btree );
-
- btree = loadTree( keys, values );
-
- // Insert 5L
- btree.insert( 5L, "V5" );
-
- System.out.println( btree );
-
- btree = loadTree( keys, values );
-
- // Insert 7L
- btree.insert( 7L, "V7" );
-
- System.out.println( btree );
-
- btree = loadTree( keys, values );
-
- // Insert 9L
- btree.insert( 9L, "V9" );
-
- System.out.println( btree );
- }
-
-
- @Test
- public void testPageInsert2() throws Exception
- {
- Long[] keys = new Long[]{ 128L, 241L, 58L };
- String[] values = new String[]{ "V128", "V241", "V58" };
-
- BTree<Long, String> btree = loadTree( keys, values );
-
- System.out.println( btree );
- }
-
-
+ /**
+ * This test is used to debug some corner cases.
+ * We don't run it except to check a special condition
+ */
@Test
@Ignore
- public void testPageInsert3() throws Exception
+ public void testPageInsertDebug() throws Exception
{
BTree<Long, String> btree = new BTree<Long, String>( new
LongComparator() );
btree.setPageSize( 4 );
- Long[]elems = new Long[]
+ Long[] elems = new Long[]
{
- 102L, 198L, 229L, 202L, 160L, 108L, 128L, 130L,
- 233L, 226L, 215L, 88L, 217L, 235L, 173L, 81L,
- 133L, 131L, 199L, 237L, 100L, 70L, 203L, 216L,
- 90L, 114L, 133L, 103L, 127L, 144L, 163L
+ 235L, 135L, 247L, 181L, 12L, 112L, 117L, 253L,
+ 37L, 158L, 56L, 118L, 184L, 101L, 173L, 126L,
+ 61L, 81L, 140L, 173L, 32L, 163L, 224L, 114L,
+ 133L, 18L, 14L, 82L, 107L, 219L, 244L, 255L,
+ 6L, 103L, 170L, 151L, 134L, 196L, 155L, 97L,
+ 80L, 122L, 89L, 253L, 33L, 101L, 56L, 168L,
+ 253L, 187L, 99L, 58L, 151L, 206L, 34L, 96L,
+ 20L, 188L, 143L, 150L, 76L, 111L, 234L, 66L,
+ 12L, 194L, 164L, 190L, 19L, 192L, 161L, 147L,
+ 92L, 89L, 237L, 187L, 250L, 13L, 233L, 34L,
+ 187L, 232L, 248L, 237L, 129L, 1L, 233L, 252L,
+ 18L, 98L, 56L, 121L, 162L, 233L, 29L, 48L,
+ 176L, 48L, 182L, 130L
};
+ int size = 0;
for ( Long elem : elems )
{
+ size++;
String value = "V" + elem;
btree.insert( elem, value );
+ System.out.println( "Adding " + elem + " :\n" + btree );
+
+ for ( int i = 0; i < size; i++ )
+ {
+ if ( btree.find( elems[i] ) == null )
+ {
+ System.out.println("Bad tree, missing " + elems[i] + ", "
+ btree);
+ }
+ }
+
+ if ( size == 27 )
+ {
+ System.out.println( btree );
+ }
//System.out.println( "added " + elem + ":\n" + btree );
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
