directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From elecha...@apache.org
Subject svn commit: r1527458 [12/14] - in /directory/mavibot/trunk/mavibot: img/ src/main/java/org/apache/directory/mavibot/btree/ src/main/java/org/apache/directory/mavibot/btree/managed/ src/main/java/org/apache/directory/mavibot/btree/memory/ src/main/java/...
Date Mon, 30 Sep 2013 06:32:28 GMT
Added: directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BTreeConfigurationTest.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BTreeConfigurationTest.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BTreeConfigurationTest.java (added)
+++ directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BTreeConfigurationTest.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,244 @@
+/*
+ *  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.directory.mavibot.btree.memory;
+
+
+import static org.junit.Assert.assertNotNull;
+
+import java.io.File;
+import java.io.IOException;
+
+import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
+import org.apache.directory.mavibot.btree.serializer.IntSerializer;
+import org.apache.directory.mavibot.btree.serializer.StringSerializer;
+import org.junit.Rule;
+import org.junit.Test;
+import org.junit.rules.TemporaryFolder;
+
+
+/**
+ * Test the creation of a BTree with a configuration.
+ * 
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class BTreeConfigurationTest
+{
+    @Rule
+    public TemporaryFolder tempFolder = new TemporaryFolder();
+
+    // Some values to inject in a btree
+    private static int[] sortedValues = new int[]
+        {
+            0, 1, 2, 4, 5, 6, 8, 9, 11, 12,
+            13, 14, 16, 19, 21, 22, 23, 25, 26, 28,
+            30, 31, 32, 34, 36, 37, 38, 39, 41, 42,
+            44, 45, 47, 50, 52, 53, 54, 55, 56, 58,
+            59, 60, 63, 64, 67, 68, 70, 72, 73, 74,
+            76, 77, 79, 80, 81, 82, 85, 88, 89, 90,
+            92, 93, 95, 97, 98, 100, 101, 102, 103, 104,
+            105, 106, 107, 109, 110, 111, 112, 117, 118, 120,
+            121, 128, 129, 130, 131, 132, 135, 136, 137, 138,
+            139, 140, 141, 142, 143, 146, 147, 148, 149, 150,
+            152, 154, 156, 160, 161, 162, 163, 165, 167, 168,
+            169, 171, 173, 174, 175, 176, 177, 178, 179, 180,
+            181, 182, 183, 189, 190, 193, 194, 195, 199, 200,
+            202, 203, 205, 206, 207, 208, 209, 210, 212, 215,
+            216, 217, 219, 220, 222, 223, 224, 225, 226, 227,
+            228, 230, 231, 235, 236, 238, 239, 241, 242, 243,
+            245, 246, 247, 249, 250, 251, 252, 254, 256, 257,
+            258, 259, 261, 262, 263, 264, 266, 268, 272, 273,
+            274, 276, 277, 278, 279, 282, 283, 286, 289, 290,
+            292, 293, 294, 296, 298, 299, 300, 301, 303, 305,
+            308, 310, 316, 317, 318, 319, 322, 323, 324, 326,
+            327, 329, 331, 333, 334, 335, 336, 337, 338, 339,
+            340, 341, 346, 347, 348, 349, 350, 351, 352, 353,
+            355, 356, 357, 358, 359, 361, 365, 366, 373, 374,
+            375, 379, 380, 381, 382, 384, 385, 387, 388, 389,
+            390, 392, 393, 395, 396, 397, 398, 399, 400, 401,
+            404, 405, 406, 407, 410, 411, 412, 416, 417, 418,
+            420, 421, 422, 424, 426, 427, 428, 430, 431, 432,
+            433, 436, 439, 441, 443, 444, 445, 446, 447, 448,
+            449, 450, 451, 452, 453, 454, 455, 456, 458, 459,
+            464, 466, 469, 470, 471, 472, 475, 477, 478, 482,
+            483, 484, 485, 486, 488, 490, 491, 492, 493, 495,
+            496, 497, 500, 502, 503, 504, 505, 506, 507, 509,
+            510, 514, 516, 518, 520, 521, 523, 524, 526, 527,
+            528, 529, 530, 532, 533, 535, 538, 539, 540, 542,
+            543, 544, 546, 547, 549, 550, 551, 553, 554, 558,
+            559, 561, 563, 564, 566, 567, 568, 569, 570, 571,
+            572, 576, 577, 578, 580, 582, 583, 586, 588, 589,
+            590, 592, 593, 596, 597, 598, 599, 600, 601, 604,
+            605, 606, 607, 609, 610, 613, 615, 617, 618, 619,
+            620, 621, 626, 627, 628, 631, 632, 633, 635, 636,
+            637, 638, 639, 640, 641, 643, 645, 647, 648, 649,
+            650, 651, 652, 653, 655, 656, 658, 659, 660, 662,
+            666, 669, 673, 674, 675, 676, 677, 678, 680, 681,
+            682, 683, 685, 686, 687, 688, 689, 690, 691, 692,
+            693, 694, 696, 698, 699, 700, 701, 705, 708, 709,
+            711, 713, 714, 715, 719, 720, 723, 725, 726, 727,
+            728, 731, 732, 733, 734, 735, 736, 739, 740, 743,
+            744, 745, 746, 747, 749, 750, 752, 753, 762, 763,
+            765, 766, 768, 770, 772, 773, 774, 776, 777, 779,
+            782, 784, 785, 788, 790, 791, 793, 794, 795, 798,
+            799, 800, 801, 803, 804, 805, 808, 810, 812, 813,
+            814, 816, 818, 821, 822, 823, 824, 827, 828, 829,
+            831, 832, 833, 834, 835, 837, 838, 839, 840, 843,
+            846, 847, 849, 852, 853, 854, 856, 857, 859, 860,
+            863, 864, 865, 866, 867, 868, 869, 872, 873, 877,
+            880, 881, 882, 883, 887, 888, 889, 890, 891, 894,
+            895, 897, 898, 899, 902, 904, 905, 907, 908, 910,
+            911, 912, 915, 916, 917, 918, 919, 923, 925, 926,
+            927, 928, 929, 930, 932, 935, 936, 937, 938, 939,
+            944, 945, 947, 952, 953, 954, 955, 956, 957, 958,
+            960, 967, 970, 971, 972, 974, 975, 976, 978, 979,
+            980, 981, 983, 984, 985, 987, 988, 989, 991, 995
+    };
+
+
+    /**
+     * Test the creation of a in-memory BTree using the BTreeConfiguration.
+     */
+    @Test
+    public void testConfigurationBasic() throws IOException, KeyNotFoundException
+    {
+        BTreeConfiguration<Integer, String> config = new BTreeConfiguration<Integer, String>();
+        config.setName( "basic" );
+        config.setPageSize( 32 );
+        config.setSerializers( new IntSerializer(), new StringSerializer() );
+
+        try
+        {
+            // Create the BTree
+            BTree<Integer, String> btree = new BTree<Integer, String>( config );
+
+            // Inject the values
+            for ( int value : sortedValues )
+            {
+                String strValue = "V" + value;
+
+                btree.insert( value, strValue );
+            }
+
+            // Check that the tree contains all the values
+            for ( int key : sortedValues )
+            {
+                String value = btree.get( key );
+
+                assertNotNull( value );
+            }
+
+            btree.close();
+        }
+        finally
+        {
+            // Erase the mavibot file now
+            File mavibotFile = new File( "", "mavibot" );
+
+            if ( mavibotFile.exists() )
+            {
+                mavibotFile.delete();
+            }
+
+            // Erase the journal too
+            File mavibotJournal = new File( "", "mavibot.log" );
+
+            if ( mavibotJournal.exists() )
+            {
+                mavibotJournal.delete();
+            }
+        }
+    }
+
+
+    /**
+     * Test the creation of a BTree using the BTreeConfiguration, flushing the 
+     * tree on disk, then reloading it in another BTree.
+     */
+    @Test
+    public void testConfigurationFlushReload() throws IOException, KeyNotFoundException
+    {
+        // Create a temporary file
+        File file = tempFolder.newFile( "testFlush.data" );
+        String parent = file.getParent();
+
+        try
+        {
+            BTreeConfiguration<Integer, String> config = new BTreeConfiguration<Integer, String>();
+            config.setPageSize( 32 );
+            config.setSerializers( new IntSerializer(), new StringSerializer() );
+
+            config.setFilePath( parent );
+            config.setName( "mavibot" );
+
+            // Create the BTree
+            BTree<Integer, String> btree = new BTree<Integer, String>( config );
+
+            // Inject the values
+            for ( int value : sortedValues )
+            {
+                String strValue = "V" + value;
+
+                btree.insert( value, strValue );
+            }
+
+            // Check that the tree contains all the values
+            for ( int key : sortedValues )
+            {
+                String value = btree.get( key );
+
+                assertNotNull( value );
+            }
+
+            // Flush the data
+            btree.close();
+
+            // Now, create a new BTree using the same configuration
+            BTree<Integer, String> btreeCopy = new BTree<Integer, String>( config );
+
+            // Check that the tree contains all the values
+            for ( int key : sortedValues )
+            {
+                String value = btreeCopy.get( key );
+
+                assertNotNull( value );
+            }
+
+            btreeCopy.close();
+        }
+        finally
+        {
+            // Erase the mavibot file now
+            File mavibotFile = new File( parent, "mavibot.db" );
+
+            if ( mavibotFile.exists() )
+            {
+                mavibotFile.delete();
+            }
+
+            // Erase the journal too
+            File mavibotJournal = new File( parent, "mavibot.db.log" );
+
+            if ( mavibotJournal.exists() )
+            {
+                mavibotJournal.delete();
+            }
+        }
+    }
+}

Added: directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BTreeDuplicateKeyTest.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BTreeDuplicateKeyTest.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BTreeDuplicateKeyTest.java (added)
+++ directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BTreeDuplicateKeyTest.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,701 @@
+/*
+ *   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.directory.mavibot.btree.memory;
+
+
+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;
+import java.util.UUID;
+
+import org.apache.directory.mavibot.btree.Cursor;
+import org.apache.directory.mavibot.btree.Tuple;
+import org.apache.directory.mavibot.btree.serializer.IntSerializer;
+import org.apache.directory.mavibot.btree.serializer.StringSerializer;
+import org.junit.Test;
+
+
+/**
+ * TODO BTreeDuplicateKeyTest.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class BTreeDuplicateKeyTest
+{
+    @Test
+    public void testInsertNullValue() throws IOException
+    {
+        IntSerializer serializer = new IntSerializer();
+
+        BTree<Integer, Integer> btree = new BTree<Integer, Integer>( "master", serializer, serializer );
+        btree.init();
+
+        btree.insert( 1, null );
+
+        Cursor<Integer, Integer> cursor = btree.browse();
+        assertTrue( cursor.hasNext() );
+
+        Tuple<Integer, Integer> t = cursor.next();
+
+        assertEquals( Integer.valueOf( 1 ), t.getKey() );
+        assertEquals( null, t.getValue() );
+
+        cursor.close();
+    }
+
+
+    @Test
+    public void testBrowseEmptyTree() throws IOException
+    {
+        IntSerializer serializer = new IntSerializer();
+
+        BTree<Integer, Integer> btree = new BTree<Integer, Integer>( "master", serializer, serializer );
+        btree.init();
+
+        Cursor<Integer, Integer> cursor = btree.browse();
+        assertFalse( cursor.hasNext() );
+        assertFalse( cursor.hasPrev() );
+
+        try
+        {
+            cursor.next();
+            fail( "Should not reach here" );
+        }
+        catch ( NoSuchElementException e )
+        {
+            assertTrue( true );
+        }
+
+        try
+        {
+            cursor.prev();
+            fail( "Should not reach here" );
+        }
+        catch ( NoSuchElementException e )
+        {
+            assertTrue( true );
+        }
+
+        cursor.close();
+    }
+
+
+    @Test
+    public void testDuplicateKey() throws IOException
+    {
+        IntSerializer serializer = new IntSerializer();
+
+        BTreeConfiguration<Integer, Integer> config = new BTreeConfiguration<Integer, Integer>();
+        config.setAllowDuplicates( true );
+        config.setName( "master" );
+        config.setSerializers( serializer, serializer );
+        BTree<Integer, Integer> btree = new BTree<Integer, Integer>( config );
+
+        btree.insert( 1, 1 );
+        btree.insert( 1, 2 );
+
+        Cursor<Integer, Integer> cursor = btree.browse();
+        assertTrue( cursor.hasNext() );
+
+        Tuple<Integer, Integer> t = cursor.next();
+
+        assertEquals( Integer.valueOf( 1 ), t.getKey() );
+        assertEquals( Integer.valueOf( 1 ), t.getValue() );
+
+        assertTrue( cursor.hasNext() );
+
+        t = cursor.next();
+
+        assertEquals( Integer.valueOf( 1 ), t.getKey() );
+        assertEquals( Integer.valueOf( 2 ), t.getValue() );
+
+        assertFalse( cursor.hasNext() );
+
+        // test backward move
+        assertTrue( cursor.hasPrev() );
+
+        t = cursor.prev();
+
+        assertEquals( Integer.valueOf( 1 ), t.getKey() );
+        assertEquals( Integer.valueOf( 2 ), t.getValue() );
+
+        assertTrue( cursor.hasPrev() );
+
+        t = cursor.prev();
+
+        assertEquals( Integer.valueOf( 1 ), t.getKey() );
+        assertEquals( Integer.valueOf( 1 ), t.getValue() );
+
+        assertFalse( cursor.hasPrev() );
+
+        // again forward
+        assertTrue( cursor.hasNext() );
+
+        t = cursor.next();
+
+        assertEquals( Integer.valueOf( 1 ), t.getKey() );
+        assertEquals( Integer.valueOf( 1 ), t.getValue() );
+
+        assertTrue( cursor.hasNext() );
+
+        t = cursor.next();
+
+        assertEquals( Integer.valueOf( 1 ), t.getKey() );
+        assertEquals( Integer.valueOf( 2 ), t.getValue() );
+
+        assertFalse( cursor.hasNext() );
+
+        cursor.close();
+    }
+
+
+    @Test
+    public void testGetDuplicateKey() throws Exception
+    {
+        IntSerializer serializer = new IntSerializer();
+
+        BTreeConfiguration<Integer, Integer> config = new BTreeConfiguration<Integer, Integer>();
+        config.setAllowDuplicates( true );
+        config.setName( "master" );
+        config.setSerializers( serializer, serializer );
+        BTree<Integer, Integer> btree = new BTree<Integer, Integer>( config );
+
+        Integer retVal = btree.insert( 1, 1 );
+        assertNull( retVal );
+
+        retVal = btree.insert( 1, 2 );
+        assertNull( retVal );
+
+        // check the return value when an existing value is added again
+        retVal = btree.insert( 1, 2 );
+        assertEquals( Integer.valueOf( 2 ), retVal );
+
+        assertEquals( Integer.valueOf( 1 ), btree.get( 1 ) );
+        assertTrue( btree.contains( 1, 1 ) );
+        assertTrue( btree.contains( 1, 2 ) );
+
+        assertFalse( btree.contains( 1, 0 ) );
+        assertFalse( btree.contains( 0, 1 ) );
+        assertFalse( btree.contains( 0, 0 ) );
+        assertFalse( btree.contains( null, 0 ) );
+        assertFalse( btree.contains( 0, null ) );
+        assertFalse( btree.contains( null, null ) );
+    }
+
+
+    @Test
+    public void testRemoveDuplicateKey() throws Exception
+    {
+        IntSerializer serializer = new IntSerializer();
+
+        BTreeConfiguration<Integer, Integer> config = new BTreeConfiguration<Integer, Integer>();
+        config.setAllowDuplicates( true );
+        config.setName( "master" );
+        config.setSerializers( serializer, serializer );
+        BTree<Integer, Integer> btree = new BTree<Integer, Integer>( config );
+
+        btree.insert( 1, 1 );
+        btree.insert( 1, 2 );
+
+        assertEquals( 2l, btree.getNbElems() );
+
+        Tuple<Integer, Integer> t = btree.delete( 1, 1 );
+        assertEquals( Integer.valueOf( 1 ), t.getKey() );
+        assertEquals( Integer.valueOf( 1 ), t.getValue() );
+
+        assertEquals( 1l, btree.getNbElems() );
+
+        t = btree.delete( 1, 2 );
+        assertEquals( Integer.valueOf( 1 ), t.getKey() );
+        assertEquals( Integer.valueOf( 2 ), t.getValue() );
+
+        assertEquals( 0l, btree.getNbElems() );
+
+        t = btree.delete( 1, 2 );
+        assertNull( t );
+    }
+
+
+    @Test
+    public void testFullPage() throws Exception
+    {
+        StringSerializer serializer = new StringSerializer();
+
+        BTreeConfiguration<String, String> config = new BTreeConfiguration<String, String>();
+        config.setAllowDuplicates( true );
+        config.setName( "master" );
+        config.setSerializers( serializer, serializer );
+        BTree<String, String> btree = new BTree<String, String>( config );
+
+        int i = 7;
+        for ( char ch = 'a'; ch <= 'z'; ch++ )
+        {
+            for ( int k = 0; k < i; k++ )
+            {
+                btree.insert( String.valueOf( ch ), UUID.randomUUID().toString() );
+            }
+        }
+
+        Cursor<String, String> cursor = btree.browse();
+
+        char ch = 'a';
+        int k = 0;
+
+        while ( cursor.hasNext() )
+        {
+            Tuple<String, String> t = cursor.next();
+            assertEquals( String.valueOf( ch ), t.getKey() );
+            k++;
+
+            if ( ( k % i ) == 0 )
+            {
+                ch++;
+            }
+        }
+
+        assertEquals( ( 'z' + 1 ), ch );
+
+        ch = 'z';
+
+        while ( cursor.hasPrev() )
+        {
+            Tuple<String, String> t = cursor.prev();
+            assertEquals( String.valueOf( ch ), t.getKey() );
+            k--;
+
+            if ( ( k % i ) == 0 )
+            {
+                ch--;
+            }
+        }
+
+        assertEquals( ( 'a' - 1 ), ch );
+        cursor.close();
+    }
+
+
+    @Test
+    public void testMoveFirst() throws Exception
+    {
+        StringSerializer serializer = new StringSerializer();
+
+        BTreeConfiguration<String, String> config = new BTreeConfiguration<String, String>();
+        config.setAllowDuplicates( true );
+        config.setName( "master" );
+        config.setSerializers( serializer, serializer );
+        BTree<String, String> btree = new BTree<String, String>( config );
+
+        for ( char ch = 'a'; ch <= 'z'; ch++ )
+        {
+            btree.insert( String.valueOf( ch ), UUID.randomUUID().toString() );
+        }
+
+        // add one more value for 'a'
+        btree.insert( String.valueOf( 'a' ), UUID.randomUUID().toString() );
+
+        Cursor<String, String> cursor = btree.browseFrom( "c" );
+
+        int i = 0;
+        while ( cursor.hasNext() )
+        {
+            assertNotNull( cursor.next() );
+            i++;
+        }
+        assertEquals( 24, i );
+
+        // now move the cursor first
+        cursor.beforeFirst();
+        assertTrue( cursor.hasNext() );
+        assertEquals( "c", cursor.next().getKey() );
+
+        i = 0;
+        while ( cursor.hasNext() )
+        {
+            assertNotNull( cursor.next() );
+            i++;
+        }
+        assertEquals( 23, i );
+
+        cursor.close();
+
+        cursor = btree.browse();
+
+        i = 0;
+        while ( cursor.hasNext() )
+        {
+            assertNotNull( cursor.next() );
+            i++;
+        }
+        assertEquals( 27, i );
+
+        // now move the cursor first
+        cursor.beforeFirst();
+        assertTrue( cursor.hasNext() );
+        assertEquals( "a", cursor.next().getKey() );
+
+        i = 0;
+        while ( cursor.hasNext() )
+        {
+            assertNotNull( cursor.next() );
+            i++;
+        }
+        assertEquals( 26, i );
+    }
+
+
+    @Test(expected = NoSuchElementException.class)
+    public void testMoveLast() throws Exception
+    {
+        StringSerializer serializer = new StringSerializer();
+
+        BTreeConfiguration<String, String> config = new BTreeConfiguration<String, String>();
+        config.setAllowDuplicates( true );
+        config.setName( "master" );
+        config.setSerializers( serializer, serializer );
+        BTree<String, String> btree = new BTree<String, String>( config );
+
+        for ( char ch = 'a'; ch <= 'z'; ch++ )
+        {
+            btree.insert( String.valueOf( ch ), UUID.randomUUID().toString() );
+        }
+
+        btree.insert( String.valueOf( 'z' ), UUID.randomUUID().toString() );
+
+        Cursor<String, String> cursor = btree.browseFrom( "c" );
+        cursor.afterLast();
+
+        assertFalse( cursor.hasNext() );
+        assertTrue( cursor.hasPrev() );
+        assertEquals( "z", cursor.prev().getKey() );
+        // the key, 'z', has two values
+        assertEquals( "z", cursor.prev().getKey() );
+        assertEquals( "y", cursor.prev().getKey() );
+
+        cursor.beforeFirst();
+        assertEquals( "c", cursor.next().getKey() );
+
+        cursor.afterLast();
+        assertFalse( cursor.hasNext() );
+        // make sure it throws NoSuchElementException
+        cursor.next();
+    }
+
+
+    @Test(expected = NoSuchElementException.class)
+    public void testMoveToNextPrevNonDuplicateKey() throws Exception
+    {
+        StringSerializer serializer = new StringSerializer();
+
+        BTreeConfiguration<String, String> config = new BTreeConfiguration<String, String>();
+        config.setAllowDuplicates( true );
+        config.setName( "master" );
+        config.setSerializers( serializer, serializer );
+        BTree<String, String> btree = new BTree<String, String>( config );
+
+        int i = 7;
+        for ( char ch = 'a'; ch <= 'z'; ch++ )
+        {
+            for ( int k = 0; k < i; k++ )
+            {
+                btree.insert( String.valueOf( ch ), String.valueOf( k ) );
+            }
+        }
+
+        Cursor<String, String> cursor = btree.browse();
+
+        assertTrue( cursor.hasNext() );
+        assertFalse( cursor.hasPrev() );
+        for ( int k = 0; k < 2; k++ )
+        {
+            assertEquals( "a", cursor.next().getKey() );
+        }
+
+        assertEquals( "a", cursor.next().getKey() );
+
+        cursor.moveToNextNonDuplicateKey();
+
+        assertEquals( "b", cursor.next().getKey() );
+
+        for ( char ch = 'b'; ch < 'z'; ch++ )
+        {
+            assertEquals( String.valueOf( ch ), cursor.next().getKey() );
+            cursor.moveToNextNonDuplicateKey();
+            char t = ch;
+            assertEquals( String.valueOf( ++t ), cursor.next().getKey() );
+        }
+
+        for ( int k = 0; k < i - 1; k++ )
+        {
+            assertEquals( "z", cursor.next().getKey() );
+        }
+
+        assertFalse( cursor.hasNext() );
+        assertTrue( cursor.hasPrev() );
+        Tuple<String, String> tuple = cursor.prev();
+        assertEquals( "z", tuple.getKey() );
+        assertEquals( "6", tuple.getValue() );
+
+        for ( char ch = 'z'; ch > 'a'; ch-- )
+        {
+            char t = ch;
+            t--;
+
+            assertEquals( String.valueOf( ch ), cursor.prev().getKey() );
+
+            cursor.moveToPrevNonDuplicateKey();
+
+            tuple = cursor.prev();
+            assertEquals( String.valueOf( t ), tuple.getKey() );
+        }
+
+        for ( int k = 5; k >= 0; k-- )
+        {
+            tuple = cursor.prev();
+            assertEquals( "a", tuple.getKey() );
+            assertEquals( String.valueOf( k ), tuple.getValue() );
+        }
+
+        assertTrue( cursor.hasNext() );
+        assertFalse( cursor.hasPrev() );
+        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();
+
+    }
+
+
+    /**
+     * Test for moving after a key and traversing backwards.
+     *
+     * @throws Exception
+     */
+    @Test
+    public void testMoveToNextAndTraverseBackward() throws Exception
+    {
+        IntSerializer serializer = new IntSerializer();
+
+        BTreeConfiguration<Integer, Integer> config = new BTreeConfiguration<Integer, Integer>();
+        config.setAllowDuplicates( true );
+        config.setName( "master" );
+        config.setPageSize( 8 );
+        config.setSerializers( serializer, serializer );
+        BTree<Integer, Integer> btree = new BTree<Integer, Integer>( config );
+
+        int i = 5;
+        for ( int k = 0; k < i; k++ )
+        {
+            btree.insert( k, k );
+        }
+
+        // 4 is the last element in the tree
+        Cursor<Integer, Integer> cursor = btree.browseFrom( 4 );
+        cursor.moveToNextNonDuplicateKey();
+
+        int currentKey = 4;
+        while ( cursor.hasPrev() )
+        {
+            assertEquals( Integer.valueOf( currentKey ), cursor.prev().getKey() );
+            currentKey--;
+        }
+
+        cursor.close();
+    }
+
+
+    /**
+     * Test for moving after a key and traversing backwards.
+     *
+     * @throws Exception
+     */
+    @Test
+    public void testMoveToPrevAndTraverseForward() throws Exception
+    {
+        IntSerializer serializer = new IntSerializer();
+
+        BTreeConfiguration<Integer, Integer> config = new BTreeConfiguration<Integer, Integer>();
+        config.setAllowDuplicates( true );
+        config.setName( "master" );
+        config.setPageSize( 8 );
+        config.setSerializers( serializer, serializer );
+        BTree<Integer, Integer> btree = new BTree<Integer, Integer>( config );
+
+        int i = 5;
+        for ( int k = 0; k < i; k++ )
+        {
+            btree.insert( k, k );
+        }
+
+        // 4 is the last element in the tree
+        Cursor<Integer, Integer> cursor = btree.browseFrom( 0 );
+        cursor.moveToPrevNonDuplicateKey();
+
+        int currentKey = 0;
+        while ( cursor.hasNext() )
+        {
+            assertEquals( Integer.valueOf( currentKey ), cursor.next().getKey() );
+            currentKey++;
+        }
+
+        cursor.close();
+    }
+
+}

Added: directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BTreeFlushTest.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BTreeFlushTest.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BTreeFlushTest.java (added)
+++ directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BTreeFlushTest.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,297 @@
+/*
+ *  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.directory.mavibot.btree.memory;
+
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+import java.io.File;
+import java.io.IOException;
+import java.util.Random;
+import java.util.Set;
+
+import org.apache.directory.mavibot.btree.Cursor;
+import org.apache.directory.mavibot.btree.Tuple;
+import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
+import org.apache.directory.mavibot.btree.serializer.IntSerializer;
+import org.apache.directory.mavibot.btree.serializer.LongSerializer;
+import org.apache.directory.mavibot.btree.serializer.StringSerializer;
+import org.junit.Rule;
+import org.junit.Test;
+import org.junit.rules.TemporaryFolder;
+
+
+/**
+ * A unit test class for BTree flush() operation
+ * 
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class BTreeFlushTest
+{
+    @Rule
+    public TemporaryFolder tempFolder = new TemporaryFolder();
+
+    // Some values to inject in a btree
+    private static int[] sortedValues = new int[]
+        {
+            0, 1, 2, 4, 5, 6, 8, 9, 11, 12,
+            13, 14, 16, 19, 21, 22, 23, 25, 26, 28,
+            30, 31, 32, 34, 36, 37, 38, 39, 41, 42,
+            44, 45, 47, 50, 52, 53, 54, 55, 56, 58,
+            59, 60, 63, 64, 67, 68, 70, 72, 73, 74,
+            76, 77, 79, 80, 81, 82, 85, 88, 89, 90,
+            92, 93, 95, 97, 98, 100, 101, 102, 103, 104,
+            105, 106, 107, 109, 110, 111, 112, 117, 118, 120,
+            121, 128, 129, 130, 131, 132, 135, 136, 137, 138,
+            139, 140, 141, 142, 143, 146, 147, 148, 149, 150,
+            152, 154, 156, 160, 161, 162, 163, 165, 167, 168,
+            169, 171, 173, 174, 175, 176, 177, 178, 179, 180,
+            181, 182, 183, 189, 190, 193, 194, 195, 199, 200,
+            202, 203, 205, 206, 207, 208, 209, 210, 212, 215,
+            216, 217, 219, 220, 222, 223, 224, 225, 226, 227,
+            228, 230, 231, 235, 236, 238, 239, 241, 242, 243,
+            245, 246, 247, 249, 250, 251, 252, 254, 256, 257,
+            258, 259, 261, 262, 263, 264, 266, 268, 272, 273,
+            274, 276, 277, 278, 279, 282, 283, 286, 289, 290,
+            292, 293, 294, 296, 298, 299, 300, 301, 303, 305,
+            308, 310, 316, 317, 318, 319, 322, 323, 324, 326,
+            327, 329, 331, 333, 334, 335, 336, 337, 338, 339,
+            340, 341, 346, 347, 348, 349, 350, 351, 352, 353,
+            355, 356, 357, 358, 359, 361, 365, 366, 373, 374,
+            375, 379, 380, 381, 382, 384, 385, 387, 388, 389,
+            390, 392, 393, 395, 396, 397, 398, 399, 400, 401,
+            404, 405, 406, 407, 410, 411, 412, 416, 417, 418,
+            420, 421, 422, 424, 426, 427, 428, 430, 431, 432,
+            433, 436, 439, 441, 443, 444, 445, 446, 447, 448,
+            449, 450, 451, 452, 453, 454, 455, 456, 458, 459,
+            464, 466, 469, 470, 471, 472, 475, 477, 478, 482,
+            483, 484, 485, 486, 488, 490, 491, 492, 493, 495,
+            496, 497, 500, 502, 503, 504, 505, 506, 507, 509,
+            510, 514, 516, 518, 520, 521, 523, 524, 526, 527,
+            528, 529, 530, 532, 533, 535, 538, 539, 540, 542,
+            543, 544, 546, 547, 549, 550, 551, 553, 554, 558,
+            559, 561, 563, 564, 566, 567, 568, 569, 570, 571,
+            572, 576, 577, 578, 580, 582, 583, 586, 588, 589,
+            590, 592, 593, 596, 597, 598, 599, 600, 601, 604,
+            605, 606, 607, 609, 610, 613, 615, 617, 618, 619,
+            620, 621, 626, 627, 628, 631, 632, 633, 635, 636,
+            637, 638, 639, 640, 641, 643, 645, 647, 648, 649,
+            650, 651, 652, 653, 655, 656, 658, 659, 660, 662,
+            666, 669, 673, 674, 675, 676, 677, 678, 680, 681,
+            682, 683, 685, 686, 687, 688, 689, 690, 691, 692,
+            693, 694, 696, 698, 699, 700, 701, 705, 708, 709,
+            711, 713, 714, 715, 719, 720, 723, 725, 726, 727,
+            728, 731, 732, 733, 734, 735, 736, 739, 740, 743,
+            744, 745, 746, 747, 749, 750, 752, 753, 762, 763,
+            765, 766, 768, 770, 772, 773, 774, 776, 777, 779,
+            782, 784, 785, 788, 790, 791, 793, 794, 795, 798,
+            799, 800, 801, 803, 804, 805, 808, 810, 812, 813,
+            814, 816, 818, 821, 822, 823, 824, 827, 828, 829,
+            831, 832, 833, 834, 835, 837, 838, 839, 840, 843,
+            846, 847, 849, 852, 853, 854, 856, 857, 859, 860,
+            863, 864, 865, 866, 867, 868, 869, 872, 873, 877,
+            880, 881, 882, 883, 887, 888, 889, 890, 891, 894,
+            895, 897, 898, 899, 902, 904, 905, 907, 908, 910,
+            911, 912, 915, 916, 917, 918, 919, 923, 925, 926,
+            927, 928, 929, 930, 932, 935, 936, 937, 938, 939,
+            944, 945, 947, 952, 953, 954, 955, 956, 957, 958,
+            960, 967, 970, 971, 972, 974, 975, 976, 978, 979,
+            980, 981, 983, 984, 985, 987, 988, 989, 991, 995
+    };
+
+
+    private String create100KElementsFile() throws IOException
+    {
+        Random random = new Random( System.nanoTime() );
+
+        int nbError = 0;
+
+        long l1 = System.currentTimeMillis();
+        int n = 0;
+        long delta = l1;
+        int nbElems = 100000;
+
+        BTree<Long, String> btree = new BTree<Long, String>( "test", new LongSerializer(), new StringSerializer() );
+        btree.setPageSize( 32 );
+
+        for ( int i = 0; i < nbElems; i++ )
+        {
+            Long key = ( long ) random.nextLong();
+            String value = Long.toString( key );
+
+            try
+            {
+                btree.insert( key, value );
+            }
+            catch ( Exception e )
+            {
+                e.printStackTrace();
+                System.out.println( btree );
+                System.out.println( "Error while adding " + value );
+                nbError++;
+
+                return null;
+            }
+
+            if ( i % 10000 == 0 )
+            {
+                if ( n > 0 )
+                {
+                    long t0 = System.currentTimeMillis();
+                    System.out.println( "Written " + i + " elements in : " + ( t0 - delta ) + "ms" );
+                    delta = t0;
+                }
+
+                n++;
+            }
+        }
+
+        long l2 = System.currentTimeMillis();
+
+        System.out.println( "Delta : " + ( l2 - l1 ) + ", nbError = " + nbError
+            + ", Nb insertion per second : " + ( ( nbElems ) / ( l2 - l1 ) ) * 1000 );
+
+        // Now, flush the btree
+
+        File tempFile = tempFolder.newFile( "mavibot.tmp" );
+
+        long t0 = System.currentTimeMillis();
+
+        btree.flush( tempFile );
+
+        long t1 = System.currentTimeMillis();
+
+        System.out.println( "Time to flush 100 000 elements : " + ( t1 - t0 ) + "ms" );
+        btree.close();
+
+        return tempFile.getCanonicalPath();
+    }
+
+
+    /**
+     * Checks the created BTree contains the expected values
+     */
+    private boolean checkTreeLong( 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 )
+        {
+            try
+            {
+                btree.get( key );
+            }
+            catch ( KeyNotFoundException knfe )
+            {
+                return false;
+            }
+        }
+
+        return true;
+    }
+
+
+    /**
+     * Test the browse method going backward
+     * @throws Exception
+     */
+    @Test
+    public void testFlushBTree() throws Exception
+    {
+        // Create a BTree with pages containing 8 elements
+        String path = tempFolder.getRoot().getCanonicalPath();
+
+        BTree<Integer, String> btree = new BTree<Integer, String>( "test", path, new IntSerializer(),
+            new StringSerializer() );
+        btree.setPageSize( 8 );
+
+        File journal = btree.getJournal();
+        File data = btree.getFile();
+
+        try
+        {
+            // Inject the values
+            for ( int value : sortedValues )
+            {
+                String strValue = "V" + value;
+
+                btree.insert( value, strValue );
+            }
+
+            // The journal must be full
+            assertTrue( journal.length() > 0 );
+
+            // Now, flush the btree
+            btree.flush();
+
+            // The journal must be empty
+            assertEquals( 0, journal.length() );
+
+            // Load the data into a new tree
+            BTree<Integer, String> btreeLoaded = new BTree<Integer, String>( "test", path, new IntSerializer(),
+                new StringSerializer() );
+            btree.setPageSize( 8 );
+
+            Cursor<Integer, String> cursor1 = btree.browse();
+            Cursor<Integer, String> cursor2 = btree.browse();
+
+            while ( cursor1.hasNext() )
+            {
+                assertTrue( cursor2.hasNext() );
+
+                Tuple<Integer, String> tuple1 = cursor1.next();
+                Tuple<Integer, String> tuple2 = cursor2.next();
+
+                assertEquals( tuple1.getKey(), tuple2.getKey() );
+                assertEquals( tuple1.getValue(), tuple2.getValue() );
+            }
+
+            assertFalse( cursor2.hasNext() );
+
+            btree.close();
+            btreeLoaded.close();
+        }
+        finally
+        {
+            data.delete();
+            journal.delete();
+        }
+    }
+
+
+    /**
+     * Test the insertion of 5 million elements in a BTree
+     * @throws Exception
+     */
+    @Test
+    public void testLoadBTreeFromFile() throws Exception
+    {
+        String data100K = create100KElementsFile();
+        File dataFile = new File( data100K );
+        BTree<Long, String> btree = new BTree<Long, String>(
+            "test",
+            dataFile.getParent(),
+            new LongSerializer(),
+            new StringSerializer() );
+        btree.setPageSize( 32 );
+    }
+}

Added: directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BulkDataSorterTest.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BulkDataSorterTest.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BulkDataSorterTest.java (added)
+++ directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BulkDataSorterTest.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,183 @@
+/*
+ *   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.directory.mavibot.btree.memory;
+
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+
+import java.io.DataOutputStream;
+import java.io.File;
+import java.io.FileOutputStream;
+import java.io.IOException;
+import java.lang.reflect.Array;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.Random;
+
+import org.apache.directory.mavibot.btree.Tuple;
+import org.apache.directory.mavibot.btree.util.IntTupleReaderWriter;
+import org.junit.Rule;
+import org.junit.Test;
+import org.junit.rules.TemporaryFolder;
+
+
+/**
+ * Test cases for BulkDataSorter.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class BulkDataSorterTest
+{
+    @Rule
+    public TemporaryFolder tempFolder = new TemporaryFolder();
+
+    private Comparator<Tuple<Integer, Integer>> tupleComp = new Comparator<Tuple<Integer, Integer>>()
+    {
+
+        @Override
+        public int compare( Tuple<Integer, Integer> o1, Tuple<Integer, Integer> o2 )
+        {
+            return o1.getKey().compareTo( o2.getKey() );
+        }
+    };
+
+
+    @Test
+    public void testSortedFileCount() throws IOException
+    {
+        int count = 7;
+        IntTupleReaderWriter itrw = new IntTupleReaderWriter();
+        Random random = new Random();
+
+        File dataFile = tempFolder.newFile( "tuple.data" );
+        DataOutputStream out = new DataOutputStream( new FileOutputStream( dataFile ) );
+
+        Tuple<Integer, Integer>[] arr = ( Tuple<Integer, Integer>[] ) Array.newInstance( Tuple.class, count );
+
+        for ( int i = 0; i < count; i++ )
+        {
+            int x = random.nextInt( 100 );
+            //System.out.println(x);
+
+            Tuple<Integer, Integer> t = new Tuple<Integer, Integer>( x, x );
+
+            arr[i] = t;
+
+            itrw.writeTuple( t, out );
+        }
+
+        out.close();
+
+        BulkDataSorter<Integer, Integer> bds = new BulkDataSorter<Integer, Integer>( itrw, tupleComp, 4 );
+        bds.sort( dataFile );
+
+        assertEquals( 2, bds.getWorkDir().list().length );
+
+        deleteDir( bds.getWorkDir() );
+    }
+
+
+    @Test
+    public void testSortedFileMerge() throws IOException
+    {
+        testSortedFileMerge( 10, 2 );
+        testSortedFileMerge( 100, 7 );
+        testSortedFileMerge( 1000, 25 );
+        testSortedFileMerge( 10000, 100 );
+        testSortedFileMerge( 10000, 101 );
+        testSortedFileMerge( 100000, 501 );
+    }
+
+
+    public void testSortedFileMerge( int count, int splitAfter ) throws IOException
+    {
+        IntTupleReaderWriter itrw = new IntTupleReaderWriter();
+        Random random = new Random();
+
+        File dataFile = tempFolder.newFile( "tuple.data" );
+
+        DataOutputStream out = new DataOutputStream( new FileOutputStream( dataFile ) );
+
+        Tuple<Integer, Integer>[] arr = ( Tuple<Integer, Integer>[] ) Array.newInstance( Tuple.class, count );
+
+        int randUpper = count;
+        if ( count < 100 )
+        {
+            randUpper = 100;
+        }
+
+        for ( int i = 0; i < count; i++ )
+        {
+            int x = random.nextInt( randUpper );
+            //System.out.println(x);
+
+            Tuple<Integer, Integer> t = new Tuple<Integer, Integer>( x, x );
+
+            arr[i] = t;
+
+            itrw.writeTuple( t, out );
+        }
+
+        out.close();
+
+        BulkDataSorter<Integer, Integer> bds = new BulkDataSorter<Integer, Integer>( itrw, tupleComp, splitAfter );
+        bds.sort( dataFile );
+
+        Iterator<Tuple<Integer, Integer>> itr = bds.getMergeSortedTuples();
+
+        Integer prev = null;
+        while ( itr.hasNext() )
+        {
+            Tuple<Integer, Integer> t = itr.next();
+
+            if ( prev == null )
+            {
+                prev = t.getKey();
+            }
+            else
+            {
+                assertTrue( prev <= t.getKey() );
+            }
+
+            //System.out.println(t);
+        }
+
+        deleteDir( bds.getWorkDir() );
+    }
+
+
+    private void deleteDir( File dir )
+    {
+        if ( dir.isFile() )
+        {
+            dir.delete();
+        }
+
+        File[] files = dir.listFiles();
+
+        for ( File f : files )
+        {
+            f.delete();
+        }
+
+        dir.delete();
+    }
+}



Mime
View raw message