View Javadoc

1   /*
2    *  Licensed to the Apache Software Foundation (ASF) under one
3    *  or more contributor license agreements.  See the NOTICE file
4    *  distributed with this work for additional information
5    *  regarding copyright ownership.  The ASF licenses this file
6    *  to you under the Apache License, Version 2.0 (the
7    *  "License"); you may not use this file except in compliance
8    *  with the License.  You may obtain a copy of the License at
9    *
10   *    http://www.apache.org/licenses/LICENSE-2.0
11   *
12   *  Unless required by applicable law or agreed to in writing,
13   *  software distributed under the License is distributed on an
14   *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   *  KIND, either express or implied.  See the License for the
16   *  specific language governing permissions and limitations
17   *  under the License.
18   *
19   */
20  package org.apache.directory.mavibot.btree.memory;
21  
22  
23  import static org.junit.Assert.assertEquals;
24  import static org.junit.Assert.assertFalse;
25  import static org.junit.Assert.assertNotNull;
26  import static org.junit.Assert.assertNull;
27  import static org.junit.Assert.assertTrue;
28  import static org.junit.Assert.fail;
29  
30  import java.io.IOException;
31  import java.lang.reflect.Array;
32  import java.util.ArrayList;
33  import java.util.HashSet;
34  import java.util.List;
35  import java.util.Random;
36  import java.util.Set;
37  
38  import org.apache.directory.mavibot.btree.Page;
39  import org.apache.directory.mavibot.btree.Tuple;
40  import org.apache.directory.mavibot.btree.TupleCursor;
41  import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
42  import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
43  import org.apache.directory.mavibot.btree.serializer.IntSerializer;
44  import org.apache.directory.mavibot.btree.serializer.LongSerializer;
45  import org.apache.directory.mavibot.btree.serializer.StringSerializer;
46  import org.junit.Ignore;
47  import org.junit.Test;
48  
49  
50  /**
51   * A unit test class for in-memory BTree
52   * 
53   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
54   */
55  public class InMemoryBTreeTest
56  {
57      // Some values to inject in a btree
58      private static int[] sortedValues = new int[]
59          {
60              0, 1, 2, 4, 5, 6, 8, 9, 11, 12,
61              13, 14, 16, 19, 21, 22, 23, 25, 26, 28,
62              30, 31, 32, 34, 36, 37, 38, 39, 41, 42,
63              44, 45, 47, 50, 52, 53, 54, 55, 56, 58,
64              59, 60, 63, 64, 67, 68, 70, 72, 73, 74,
65              76, 77, 79, 80, 81, 82, 85, 88, 89, 90,
66              92, 93, 95, 97, 98, 100, 101, 102, 103, 104,
67              105, 106, 107, 109, 110, 111, 112, 117, 118, 120,
68              121, 128, 129, 130, 131, 132, 135, 136, 137, 138,
69              139, 140, 141, 142, 143, 146, 147, 148, 149, 150,
70              152, 154, 156, 160, 161, 162, 163, 165, 167, 168,
71              169, 171, 173, 174, 175, 176, 177, 178, 179, 180,
72              181, 182, 183, 189, 190, 193, 194, 195, 199, 200,
73              202, 203, 205, 206, 207, 208, 209, 210, 212, 215,
74              216, 217, 219, 220, 222, 223, 224, 225, 226, 227,
75              228, 230, 231, 235, 236, 238, 239, 241, 242, 243,
76              245, 246, 247, 249, 250, 251, 252, 254, 256, 257,
77              258, 259, 261, 262, 263, 264, 266, 268, 272, 273,
78              274, 276, 277, 278, 279, 282, 283, 286, 289, 290,
79              292, 293, 294, 296, 298, 299, 300, 301, 303, 305,
80              308, 310, 316, 317, 318, 319, 322, 323, 324, 326,
81              327, 329, 331, 333, 334, 335, 336, 337, 338, 339,
82              340, 341, 346, 347, 348, 349, 350, 351, 352, 353,
83              355, 356, 357, 358, 359, 361, 365, 366, 373, 374,
84              375, 379, 380, 381, 382, 384, 385, 387, 388, 389,
85              390, 392, 393, 395, 396, 397, 398, 399, 400, 401,
86              404, 405, 406, 407, 410, 411, 412, 416, 417, 418,
87              420, 421, 422, 424, 426, 427, 428, 430, 431, 432,
88              433, 436, 439, 441, 443, 444, 445, 446, 447, 448,
89              449, 450, 451, 452, 453, 454, 455, 456, 458, 459,
90              464, 466, 469, 470, 471, 472, 475, 477, 478, 482,
91              483, 484, 485, 486, 488, 490, 491, 492, 493, 495,
92              496, 497, 500, 502, 503, 504, 505, 506, 507, 509,
93              510, 514, 516, 518, 520, 521, 523, 524, 526, 527,
94              528, 529, 530, 532, 533, 535, 538, 539, 540, 542,
95              543, 544, 546, 547, 549, 550, 551, 553, 554, 558,
96              559, 561, 563, 564, 566, 567, 568, 569, 570, 571,
97              572, 576, 577, 578, 580, 582, 583, 586, 588, 589,
98              590, 592, 593, 596, 597, 598, 599, 600, 601, 604,
99              605, 606, 607, 609, 610, 613, 615, 617, 618, 619,
100             620, 621, 626, 627, 628, 631, 632, 633, 635, 636,
101             637, 638, 639, 640, 641, 643, 645, 647, 648, 649,
102             650, 651, 652, 653, 655, 656, 658, 659, 660, 662,
103             666, 669, 673, 674, 675, 676, 677, 678, 680, 681,
104             682, 683, 685, 686, 687, 688, 689, 690, 691, 692,
105             693, 694, 696, 698, 699, 700, 701, 705, 708, 709,
106             711, 713, 714, 715, 719, 720, 723, 725, 726, 727,
107             728, 731, 732, 733, 734, 735, 736, 739, 740, 743,
108             744, 745, 746, 747, 749, 750, 752, 753, 762, 763,
109             765, 766, 768, 770, 772, 773, 774, 776, 777, 779,
110             782, 784, 785, 788, 790, 791, 793, 794, 795, 798,
111             799, 800, 801, 803, 804, 805, 808, 810, 812, 813,
112             814, 816, 818, 821, 822, 823, 824, 827, 828, 829,
113             831, 832, 833, 834, 835, 837, 838, 839, 840, 843,
114             846, 847, 849, 852, 853, 854, 856, 857, 859, 860,
115             863, 864, 865, 866, 867, 868, 869, 872, 873, 877,
116             880, 881, 882, 883, 887, 888, 889, 890, 891, 894,
117             895, 897, 898, 899, 902, 904, 905, 907, 908, 910,
118             911, 912, 915, 916, 917, 918, 919, 923, 925, 926,
119             927, 928, 929, 930, 932, 935, 936, 937, 938, 939,
120             944, 945, 947, 952, 953, 954, 955, 956, 957, 958,
121             960, 967, 970, 971, 972, 974, 975, 976, 978, 979,
122             980, 981, 983, 984, 985, 987, 988, 989, 991, 995
123     };
124 
125 
126     /**
127      * Checks the created BTree contains the expected values
128      */
129     private boolean checkTreeLong( Set<Long> expected, BTree<Long, String> btree ) throws IOException
130     {
131         // We loop on all the expected value to see if they have correctly been inserted
132         // into the btree
133         for ( Long key : expected )
134         {
135             try
136             {
137                 btree.get( key );
138             }
139             catch ( KeyNotFoundException knfe )
140             {
141                 return false;
142             }
143         }
144 
145         return true;
146     }
147 
148 
149     /**
150      * Test the insertion of elements in a BTree. We will try 1000 times to insert 1000
151      * random elements in [0..1024], and check every tree to see if all the added elements
152      * are present. This pretty much validate the the insertion, assuming that due to the
153      * randomization of the injected values, we will statically meet all the use cases.
154      * @throws Exception
155      */
156     @Test
157     public void testPageInsert() throws Exception
158     {
159         Set<Long> expected = new HashSet<Long>();
160         List<Long> added = new ArrayList<Long>();
161 
162         Random random = new Random( System.nanoTime() );
163 
164         int nbError = 0;
165 
166         long l1 = System.currentTimeMillis();
167         int n = 0;
168         long delta = l1;
169         int nbTrees = 1000;
170         int nbElems = 1000;
171 
172         for ( int j = 0; j < nbTrees; j++ )
173         {
174             BTree<Long, String> btree = new BTree<Long, String>( "test", new LongSerializer(), new StringSerializer() );
175             btree.setPageSize( 32 );
176 
177             for ( int i = 0; i < nbElems; i++ )
178             {
179                 Long key = ( long ) random.nextInt( 1024 );
180                 String value = "V" + key;
181                 expected.add( key );
182                 added.add( key );
183 
184                 //System.out.println( "Adding " + i + "th : " + key );
185 
186                 try
187                 {
188                     btree.insert( key, value );
189                 }
190                 catch ( Exception e )
191                 {
192                     e.printStackTrace();
193                     System.out.println( btree );
194                     System.out.println( "Error while adding " + value );
195                     nbError++;
196                     btree.close();
197 
198                     return;
199                 }
200             }
201 
202             assertTrue( checkTreeLong( expected, btree ) );
203 
204             /* For debug only
205             if ( !checkTree( expected, btree ) )
206             {
207                 boolean isFirst = true;
208                 
209                 for ( Long key : added )
210                 {
211                     if ( isFirst )
212                     {
213                         isFirst = false;
214                     }
215                     else
216                     {
217                         System.out.print( ", " );
218                     }
219                     
220                     System.out.print( key );
221                 }
222             }
223             */
224 
225             if ( j % 10000 == 0 )
226             {
227                 if ( n > 0 )
228                 {
229                     long t0 = System.currentTimeMillis();
230                     System.out.println( "Delta" + n + ": " + ( t0 - delta ) );
231                     delta = t0;
232                 }
233 
234                 n++;
235             }
236 
237             expected.clear();
238             added.clear();
239 
240             btree.close();
241         }
242 
243         long l2 = System.currentTimeMillis();
244 
245         System.out.println( "Delta : " + ( l2 - l1 ) + ", nbError = " + nbError
246             + ", Nb insertion per second : " + ( nbTrees * nbElems * 1000 ) / ( l2 - l1 ) );
247     }
248 
249 
250     /**
251      * Test the deletion of elements in a BTree. We will try 1000 times to delete 1000
252      * random elements in [0..1024], and check every tree to see if all the removed elements
253      * are absent. This pretty much validate the the deletion operation is valid, assuming 
254      * that due to the randomization of the deleted values, we will statically meet all the 
255      * use cases.
256      * @throws Exception
257      */
258     @Test
259     public void testPageDeleteRandom() throws IOException
260     {
261         Set<Long> expected = new HashSet<Long>();
262         List<Long> added = new ArrayList<Long>();
263 
264         Random random = new Random( System.nanoTime() );
265 
266         int nbError = 0;
267 
268         long l1 = System.currentTimeMillis();
269         int n = 0;
270         long delta = l1;
271         int nbTrees = 1000;
272         int nbElems = 1000;
273 
274         for ( int j = 0; j < nbTrees; j++ )
275         {
276             BTree<Long, String> btree = new BTree<Long, String>( "test", new LongSerializer(), new StringSerializer() );
277             btree.setPageSize( 8 );
278 
279             for ( int i = 0; i < nbElems; i++ )
280             {
281                 Long key = ( long ) random.nextInt( 1024 );
282                 String value = "V" + key;
283                 expected.add( key );
284                 added.add( key );
285 
286                 //System.out.println( "Adding " + i + "th : " + key );
287 
288                 try
289                 {
290                     btree.insert( key, value );
291                 }
292                 catch ( Exception e )
293                 {
294                     e.printStackTrace();
295                     System.out.println( btree );
296                     System.out.println( "Error while adding " + value );
297                     nbError++;
298                     btree.close();
299 
300                     return;
301                 }
302             }
303 
304             assertTrue( checkTreeLong( expected, btree ) );
305 
306             // Now, delete the elements
307             /*
308             boolean isFirst = true;
309 
310             for ( long element : added )
311             {
312                 if ( isFirst )
313                 {
314                     isFirst = false;
315                 }
316                 else
317                 {
318                     System.out.print( ", " );
319                 }
320 
321                 System.out.print( element );
322             }
323 
324             //System.out.println( "\n--------------------" );
325              */
326 
327             //int i = 0;
328 
329             for ( long element : expected )
330             {
331                 //System.out.println( "Deleting #" + i + " : " + element );
332                 //i++;
333                 //System.out.println( btree );
334                 Tuple<Long, String> tuple = btree.delete( element );
335 
336                 if ( tuple == null )
337                 {
338                     System.out.println( btree );
339                 }
340 
341                 assertEquals( Long.valueOf( element ), tuple.getKey() );
342 
343                 checkNull( btree, element );
344 
345                 //System.out.println( "" );
346             }
347 
348             if ( j % 10000 == 0 )
349             {
350                 if ( n > 0 )
351                 {
352                     long t0 = System.currentTimeMillis();
353                     System.out.println( "Delta" + n + ": " + ( t0 - delta ) );
354                     delta = t0;
355                 }
356 
357                 n++;
358 
359             }
360 
361             expected.clear();
362             added.clear();
363 
364             btree.close();
365         }
366 
367         long l2 = System.currentTimeMillis();
368 
369         System.out.println( "Delta : " + ( l2 - l1 ) + ", nbError = " + nbError
370             + ", Nb deletion per second : " + ( nbTrees * nbElems * 1000 ) / ( l2 - l1 ) );
371     }
372 
373 
374     @Test
375     public void testDeleteDebug() throws IOException
376     {
377         long[] values = new long[]
378             {
379                 148, 746, 525, 327, 1, 705, 171, 1023, 769, 1021,
380                 128, 772, 744, 771, 925, 884, 346, 519, 989, 350,
381                 649, 895, 464, 164, 190, 298, 203, 69, 483, 38,
382                 266, 83, 88, 285, 879, 342, 231, 432, 722, 432,
383                 258, 307, 237, 151, 43, 36, 135, 166, 325, 886,
384                 878, 307, 925, 835, 800, 895, 519, 947, 703, 27,
385                 324, 668, 40, 943, 804, 230, 223, 584, 828, 575,
386                 69, 955, 344, 325, 896, 423, 855, 783, 225, 447,
387                 28, 23, 262, 679, 782, 517, 412, 878, 641, 940,
388                 368, 245, 1005, 226, 939, 320, 396, 437, 373, 61
389         };
390 
391         BTree<Long, String> btree = new BTree<Long, String>( "test", new LongSerializer(), new StringSerializer() );
392         btree.setPageSize( 8 );
393 
394         for ( long value : values )
395         {
396             String strValue = "V" + value;
397 
398             try
399             {
400                 btree.insert( value, strValue );
401             }
402             catch ( Exception e )
403             {
404                 e.printStackTrace();
405                 System.out.println( btree );
406                 System.out.println( "Error while adding " + value );
407                 btree.close();
408 
409                 return;
410             }
411         }
412 
413         long[] deletes = new long[]
414             {
415                 1,
416                 828,
417                 285,
418                 804,
419                 258,
420                 262,
421         };
422 
423         for ( long value : deletes )
424         {
425             Tuple<Long, String> tuple = btree.delete( value );
426 
427             if ( tuple != null )
428             {
429                 assertEquals( Long.valueOf( value ), tuple.getKey() );
430             }
431 
432             checkNull( btree, value );
433         }
434 
435         btree.close();
436     }
437 
438 
439     /**
440      * Test the deletion of elements from a BTree.
441      */
442     @Test
443     public void testPageDelete() throws Exception
444     {
445         Set<Long> expected = new HashSet<Long>();
446         List<Long> added = new ArrayList<Long>();
447 
448         Random random = new Random( System.nanoTime() );
449 
450         BTree<Long, String> btree = new BTree<Long, String>( "test", new LongSerializer(), new StringSerializer() );
451         btree.setPageSize( 8 );
452 
453         // Insert some values
454         for ( int i = 0; i < 8; i++ )
455         {
456             Long key = ( long ) random.nextInt( 1024 );
457             String value = "V" + key;
458             added.add( key );
459 
460             try
461             {
462                 btree.insert( key, value );
463             }
464             catch ( Exception e )
465             {
466                 e.printStackTrace();
467                 System.out.println( btree );
468                 System.out.println( "Error while adding " + value );
469                 btree.close();
470 
471                 return;
472             }
473         }
474 
475         assertTrue( checkTreeLong( expected, btree ) );
476 
477         // Now, delete entries
478         for ( long key : added )
479         {
480             //System.out.println( "Removing " + key + " from " + btree );
481             try
482             {
483                 btree.delete( key );
484             }
485             catch ( Exception e )
486             {
487                 e.printStackTrace();
488                 System.out.println( btree );
489                 System.out.println( "Error while deleting " + key );
490                 btree.close();
491 
492                 return;
493             }
494 
495             assertTrue( checkTreeLong( expected, btree ) );
496         }
497 
498         btree.close();
499     }
500 
501 
502     /**
503      * This test is used to debug some corner cases.
504      * We don't run it except to check a special condition
505      */
506     @Test
507     @Ignore("This is a debug test")
508     public void testPageInsertDebug() throws Exception
509     {
510         BTree<Long, String> btree = new BTree<Long, String>( "test", new LongSerializer(), new StringSerializer() );
511         btree.setPageSize( 4 );
512 
513         Long[] elems = new Long[]
514             {
515                 235L, 135L, 247L, 181L, 12L, 112L, 117L, 253L,
516                 37L, 158L, 56L, 118L, 184L, 101L, 173L, 126L,
517                 61L, 81L, 140L, 173L, 32L, 163L, 224L, 114L,
518                 133L, 18L, 14L, 82L, 107L, 219L, 244L, 255L,
519                 6L, 103L, 170L, 151L, 134L, 196L, 155L, 97L,
520                 80L, 122L, 89L, 253L, 33L, 101L, 56L, 168L,
521                 253L, 187L, 99L, 58L, 151L, 206L, 34L, 96L,
522                 20L, 188L, 143L, 150L, 76L, 111L, 234L, 66L,
523                 12L, 194L, 164L, 190L, 19L, 192L, 161L, 147L,
524                 92L, 89L, 237L, 187L, 250L, 13L, 233L, 34L,
525                 187L, 232L, 248L, 237L, 129L, 1L, 233L, 252L,
526                 18L, 98L, 56L, 121L, 162L, 233L, 29L, 48L,
527                 176L, 48L, 182L, 130L
528         };
529 
530         int size = 0;
531         for ( Long elem : elems )
532         {
533             size++;
534             String value = "V" + elem;
535             btree.insert( elem, value );
536 
537             System.out.println( "Adding " + elem + " :\n" + btree );
538 
539             for ( int i = 0; i < size; i++ )
540             {
541                 try
542                 {
543                     btree.get( elems[i] );
544                 }
545                 catch ( KeyNotFoundException knfe )
546                 {
547                     System.out.println( "Bad tree, missing " + elems[i] + ", " + btree );
548                 }
549             }
550 
551             if ( size == 27 )
552             {
553                 System.out.println( btree );
554             }
555             //System.out.println( "added " + elem + ":\n" + btree );
556         }
557 
558         //System.out.println( btree );
559 
560         btree.close();
561     }
562 
563 
564     /*
565     @Test
566     public void testPageRemove() throws Exception
567     {
568         Long[] keys = new Long[]{  101L, 113L, 20L, 72L, 215L, 239L, 108L, 21L };
569         
570         BTree<Long, String> btree = new BTree<Long, String>( new LongComparator(), 8 );
571         System.out.println( btree );
572 
573         for ( Long key : keys )
574         {
575             btree.insert( key, "V" + key );
576         }
577         
578         System.out.println( btree );
579         
580         // Remove from the left
581         btree.remove( 20L );
582         System.out.println( btree );
583         
584         // Remove from the right
585         btree.remove( 239L );
586         System.out.println( btree );
587         
588         // Remove from the middle
589         btree.remove( 72L );
590         System.out.println( btree );
591         
592         // Remove all the remaining elements
593         btree.remove( 101L );
594         System.out.println( btree );
595         btree.remove( 108L );
596         System.out.println( btree );
597         btree.remove( 215L );
598         System.out.println( btree );
599         btree.remove( 113L );
600         System.out.println( btree );
601         btree.remove( 21L );
602         System.out.println( btree );
603         
604         btree.close();
605     }
606     */
607 
608     /**
609      * Test the browse method going forward
610      * @throws Exception
611      */
612     @Test
613     public void testBrowseForward() throws Exception
614     {
615         // Create a BTree with pages containing 8 elements
616         BTree<Integer, String> btree = new BTree<Integer, String>( "test", new IntSerializer(), new StringSerializer() );
617         btree.setPageSize( 8 );
618 
619         // Inject the values
620         for ( int value : sortedValues )
621         {
622             String strValue = "V" + value;
623 
624             btree.insert( value, strValue );
625         }
626 
627         // Check that the tree contains all the values
628         for ( int key : sortedValues )
629         {
630             String value = btree.get( key );
631 
632             assertNotNull( value );
633         }
634 
635         // Browse starting at position 10
636         int pos = 10;
637         TupleCursor<Integer, String> cursor = btree.browseFrom( sortedValues[pos] );
638 
639         while ( cursor.hasNext() )
640         {
641             Tuple<Integer, String> tuple = cursor.next();
642             
643             assertNotNull( tuple );
644             Integer val = sortedValues[pos];
645             Integer res = tuple.getKey();
646             assertEquals( val, res );
647             pos++;
648         }
649 
650         cursor.close();
651 
652         // Now, start on a non existing key (7)
653         cursor = btree.browseFrom( 7 );
654 
655         // We should start reading values superior to 7, so value 8 at position 6 in the array
656         pos = 6;
657 
658         while ( cursor.hasNext() )
659         {
660             Tuple<Integer, String> tuple = cursor.next();
661 
662             assertNotNull( tuple );
663             Integer val = sortedValues[pos];
664             Integer res = tuple.getKey();
665             assertEquals( val, res );
666             pos++;
667         }
668 
669         cursor.close();
670 
671         // Last, let's browse with no key, we should get all the values
672         cursor = btree.browse();
673 
674         pos = 0;
675 
676         while ( cursor.hasNext() )
677         {
678             Tuple<Integer, String> tuple = cursor.next();
679             
680             assertNotNull( tuple );
681             Integer val = sortedValues[pos];
682             Integer res = tuple.getKey();
683             assertEquals( val, res );
684             pos++;
685         }
686 
687         cursor.close();
688         btree.close();
689     }
690 
691 
692     /**
693      * Test the browse method going backward
694      * @throws Exception
695      */
696     @Test
697     public void testBrowseBackward() throws Exception
698     {
699         // Create a BTree with pages containing 8 elements
700         BTree<Integer, String> btree = new BTree<Integer, String>( "test", new IntSerializer(), new StringSerializer() );
701         btree.setPageSize( 8 );
702 
703         // Inject the values
704         for ( int value : sortedValues )
705         {
706             String strValue = "V" + value;
707 
708             btree.insert( value, strValue );
709         }
710 
711         // Check that the tree contains all the values
712         for ( int key : sortedValues )
713         {
714             String value = btree.get( key );
715 
716             assertNotNull( value );
717         }
718 
719         // Browse starting at position 10
720         int pos = 10;
721         TupleCursor<Integer, String> cursor = btree.browseFrom( sortedValues[pos] );
722 
723         while ( cursor.hasPrev() )
724         {
725             Tuple<Integer, String> tuple = cursor.prev();
726 
727             pos--;
728 
729             assertNotNull( tuple );
730             Integer val = sortedValues[pos];
731             Integer res = tuple.getKey();
732             assertEquals( val, res );
733         }
734 
735         cursor.close();
736 
737         // Now, start on a non existing key (7)
738         cursor = btree.browseFrom( 7 );
739 
740         // We should start reading values superior to 7, so value 8 at position 6 in the array
741         pos = 6;
742 
743         while ( cursor.hasPrev() )
744         {
745             Tuple<Integer, String> tuple = cursor.prev();
746 
747             pos--;
748             assertNotNull( tuple );
749             Integer val = sortedValues[pos];
750             Integer res = tuple.getKey();
751             assertEquals( val, res );
752         }
753 
754         cursor.close();
755 
756         // Last, let's browse with no key, we should get no values
757         cursor = btree.browse();
758 
759         pos = 0;
760 
761         assertFalse( cursor.hasPrev() );
762 
763         cursor.close();
764         btree.close();
765     }
766 
767 
768     /**
769      * Test a browse over an empty tree
770      */
771     @Test
772     public void testBrowseEmptyTree() throws Exception
773     {
774         // Create a BTree with pages containing 8 elements
775         BTree<Integer, String> btree = new BTree<Integer, String>( "test", new IntSerializer(), new StringSerializer() );
776         btree.setPageSize( 8 );
777 
778         TupleCursor<Integer, String> cursor = btree.browse();
779 
780         assertFalse( cursor.hasNext() );
781         assertFalse( cursor.hasPrev() );
782 
783         cursor.close();
784         btree.close();
785     }
786 
787 
788     /**
789      * Test a browse forward and backward
790      */
791     @Test
792     public void testBrowseForwardBackward() throws Exception
793     {
794         // Create a BTree with pages containing 4 elements
795         BTree<Integer, String> btree = new BTree<Integer, String>( "test", new IntSerializer(), new StringSerializer() );
796         btree.setPageSize( 4 );
797 
798         for ( int i = 0; i < 16; i++ )
799         {
800             String strValue = "V" + i;
801             btree.insert( i, strValue );
802         }
803 
804         // Start to browse in the middle
805         TupleCursor<Integer, String> cursor = btree.browseFrom( 8 );
806 
807         assertTrue( cursor.hasNext() );
808 
809         // Get 8
810         assertEquals( 8, cursor.next().getKey().intValue() );
811 
812         // get 9
813         assertEquals( 9, cursor.next().getKey().intValue() );
814 
815         // get 10
816         assertEquals( 10, cursor.next().getKey().intValue() );
817 
818         // get 11
819         assertEquals( 11, cursor.next().getKey().intValue() );
820 
821         // get 12 (now, we must have gone through at least 2 pages)
822         assertEquals( 12, cursor.next().getKey().intValue() );
823 
824         assertTrue( cursor.hasPrev() );
825 
826         // Lets go backward.
827         assertEquals( 11, cursor.prev().getKey().intValue() );
828 
829         // Get 10
830         assertEquals( 10, cursor.prev().getKey().intValue() );
831 
832         // Get 9
833         assertEquals( 9, cursor.prev().getKey().intValue() );
834 
835         // Get 8
836         assertEquals( 8, cursor.prev().getKey().intValue() );
837 
838         // Get 7
839         assertEquals( 7, cursor.prev().getKey().intValue() );
840 
841         cursor.close();
842         btree.close();
843     }
844 
845 
846     /**
847      * Test various deletions in a tree, when we have full leaves
848      */
849     @Test
850     public void testDeleteFromFullLeaves() throws Exception
851     {
852         // Create a BTree with pages containing 4 elements
853         BTree<Integer, String> btree = createTwoLevelBTreeFullLeaves();
854 
855         // Test removals leadings to various RemoveResult.
856         // The tree remains the same after the deletion
857         // First, no borrow nor merge
858         btree.delete( 1 );
859 
860         checkNull( btree, 1 );
861 
862         btree.insert( 1, "V1" );
863 
864         btree.delete( 3 );
865 
866         checkNull( btree, 3 );
867 
868         btree.insert( 3, "V3" );
869 
870         btree.delete( 4 );
871 
872         checkNull( btree, 4 );
873 
874         btree.insert( 4, "V4" );
875 
876         btree.delete( 11 );
877 
878         checkNull( btree, 11 );
879 
880         btree.insert( 11, "V11" );
881 
882         btree.delete( 20 );
883 
884         checkNull( btree, 20 );
885 
886         btree.insert( 20, "V20" );
887 
888         btree.delete( 0 );
889 
890         checkNull( btree, 0 );
891 
892         btree.delete( 5 );
893 
894         checkNull( btree, 5 );
895 
896         btree.delete( 9 );
897 
898         checkNull( btree, 9 );
899 
900         btree.close();
901     }
902 
903 
904     /**
905      * Test the exist() method
906      */
907     @Test
908     public void testExist() throws IOException
909     {
910         // Create a BTree with pages containing 4 elements
911         BTree<Integer, String> btree = createTwoLevelBTreeFullLeaves();
912 
913         for ( int i = 1; i < 21; i++ )
914         {
915             assertTrue( btree.hasKey( 5 ) );
916         }
917 
918         assertFalse( btree.hasKey( 0 ) );
919         assertFalse( btree.hasKey( 21 ) );
920     }
921 
922 
923     /**
924      * Test various deletions in a tree, leadings to borrowFromSibling
925      */
926     @Test
927     public void testDeleteBorrowFromSibling() throws Exception
928     {
929         // Create a BTree with pages containing 4 elements
930         BTree<Integer, String> btree = createTwoLevelBTreeFullLeaves();
931 
932         // Delete some useless elements to simulate the tree we want to test
933         // Make the left leaf to contain N/2 elements
934         btree.delete( 3 );
935         btree.delete( 4 );
936 
937         // Make the right leaf to contain N/2 elements
938         btree.delete( 19 );
939         btree.delete( 20 );
940 
941         // Make the middle leaf to contain N/2 elements
942         btree.delete( 11 );
943         btree.delete( 12 );
944 
945         // Delete the leftmost key
946         btree.delete( 1 );
947 
948         checkNull( btree, 1 );
949 
950         // Delete the rightmost key
951         btree.delete( 18 );
952 
953         checkNull( btree, 18 );
954 
955         // Delete one element in the left page, but not the first one
956         btree.delete( 5 );
957 
958         checkNull( btree, 5 );
959 
960         // Delete the one element in the right page, but the first one
961         btree.delete( 16 );
962 
963         checkNull( btree, 16 );
964 
965         btree.close();
966 
967         // Now do that with a deeper btree
968         btree = createMultiLevelBTreeLeavesHalfFull();
969 
970         // Add some more elements on the second leaf before deleting some elements in the first leaf
971         btree.insert( 8, "V8" );
972         btree.insert( 9, "V9" );
973 
974         // and delete some
975         btree.delete( 2 );
976 
977         checkNull( btree, 2 );
978 
979         btree.delete( 6 );
980 
981         checkNull( btree, 6 );
982 
983         // Add some more elements on the pre-last leaf before deleting some elements in the last leaf
984         btree.insert( 96, "V96" );
985         btree.insert( 97, "V97" );
986 
987         // and delete some
988         btree.delete( 98 );
989 
990         checkNull( btree, 98 );
991 
992         btree.delete( 99 );
993 
994         checkNull( btree, 99 );
995 
996         // Now try to delete elements in the middle
997         btree.insert( 48, "V48" );
998 
999         btree.delete( 42 );
1000 
1001         checkNull( btree, 42 );
1002 
1003         btree.insert( 72, "V72" );
1004 
1005         btree.delete( 67 );
1006 
1007         checkNull( btree, 67 );
1008 
1009         btree.close();
1010     }
1011 
1012 
1013     /**
1014      * Test the browse method with a non existing key 
1015      * @throws Exception
1016      */
1017     @Test
1018     public void testBrowseNonExistingKey() throws Exception
1019     {
1020         // Create a BTree with pages containing 8 elements
1021         BTree<Integer, String> btree = new BTree<Integer, String>( "test", new IntSerializer(), new StringSerializer() );
1022         btree.setPageSize( 8 );
1023         for ( int i = 0; i < 11; i++ )
1024         {
1025             btree.insert( i, String.valueOf( i ) );
1026         }
1027 
1028         for ( int i = 0; i < 11; i++ )
1029         {
1030             assertNotNull( btree.get( i ) );
1031         }
1032 
1033         assertTrue( btree.hasKey( 8 ) );
1034         assertFalse( btree.hasKey( 11 ) );
1035 
1036         TupleCursor<Integer, String> cursor = btree.browseFrom( 11 );
1037         assertFalse( cursor.hasNext() );
1038         btree.close();
1039     }
1040 
1041 
1042     private Page<Integer, String> createLeaf( BTree<Integer, String> btree, long revision,
1043         Tuple<Integer, String>... tuples )
1044     {
1045         Leaf<Integer, String> leaf = new Leaf<Integer, String>( btree );
1046         int pos = 0;
1047         leaf.revision = revision;
1048         leaf.nbElems = tuples.length;
1049         leaf.keys = new Integer[leaf.nbElems];
1050         leaf.values = ( ValueHolder<String>[] ) Array
1051             .newInstance( ValueHolder.class, leaf.nbElems );
1052 
1053         for ( Tuple<Integer, String> tuple : tuples )
1054         {
1055             leaf.keys[pos] = tuple.getKey();
1056             leaf.values[pos] = btree.createValueHolder( tuple.getValue() );
1057             pos++;
1058         }
1059 
1060         return leaf;
1061     }
1062 
1063 
1064     private void addPage( BTree<Integer, String> btree, Node<Integer, String> node, Page<Integer, String> page, int pos )
1065         throws EndOfFileExceededException, IOException
1066     {
1067         Tuple<Integer, String> leftmost = page.findLeftMost();
1068 
1069         if ( pos > 0 )
1070         {
1071             node.keys[pos - 1] = leftmost.getKey();
1072         }
1073 
1074         node.children[pos] = page;
1075     }
1076 
1077 
1078     /**
1079      * Creates a 2 level depth tree of full pages
1080      */
1081     private BTree<Integer, String> createTwoLevelBTreeFullLeaves() throws IOException
1082     {
1083         BTree<Integer, String> btree = new BTree<Integer, String>( "test", new IntSerializer(), new StringSerializer() );
1084         btree.setPageSize( 4 );
1085 
1086         // Create a tree with 5 children containing 4 elements each. The tree is full.
1087         int[] keys = new int[]
1088             { 1, 2, 5, 6, 3, 4, 9, 10, 7, 8, 13, 14, 11, 12, 17, 18, 15, 16, 19, 20 };
1089 
1090         for ( int key : keys )
1091         {
1092             String value = "V" + key;
1093             btree.insert( key, value );
1094         }
1095 
1096         return btree;
1097     }
1098 
1099 
1100     /**
1101      * Creates a 2 level depth tree of half full pages
1102      */
1103     private BTree<Integer, String> createTwoLevelBTreeHalfFullLeaves() throws IOException
1104     {
1105         BTree<Integer, String> btree = new BTree<Integer, String>( "test", new IntSerializer(), new StringSerializer() );
1106         btree.setPageSize( 4 );
1107 
1108         // Create a tree with 5 children containing 4 elements each. The tree is full.
1109         int[] keys = new int[]
1110             { 1, 2, 17, 18, 13, 14, 9, 10, 5, 6, 3 };
1111 
1112         for ( int key : keys )
1113         {
1114             String value = "V" + key;
1115             btree.insert( key, value );
1116         }
1117 
1118         // Regulate the tree by removing the last value added, so that all the leaves have only 2 elements
1119         btree.delete( 3 );
1120 
1121         return btree;
1122     }
1123 
1124     /** A set used to check that the tree contains the contained elements */
1125     private Set<Integer> EXPECTED1 = new HashSet<Integer>();
1126 
1127 
1128     /**
1129      * Creates a 3 level depth tree, with each page containing only N/2 elements
1130      */
1131     private BTree<Integer, String> createMultiLevelBTreeLeavesHalfFull() throws IOException
1132     {
1133         // Create a BTree with pages containing 4 elements
1134         int pageSize = 4;
1135 
1136         BTree<Integer, String> btree = new BTree<Integer, String>( "test", new IntSerializer(), new StringSerializer(),
1137             pageSize );
1138 
1139         Node<Integer, String> root = new Node<Integer, String>( btree, 1L, pageSize );
1140 
1141         // Create the tree with 3 levels, all the leaves containing only N/2 elements
1142         int counter = 1;
1143         for ( int i = 0; i < pageSize + 1; i++ )
1144         {
1145             Node<Integer, String> node = new Node<Integer, String>( btree, 1L, pageSize );
1146 
1147             for ( int j = 0; j < pageSize + 1; j++ )
1148             {
1149                 int even = counter * 2;
1150 
1151                 @SuppressWarnings("unchecked")
1152                 Page<Integer, String> leaf = createLeaf(
1153                     btree,
1154                     1L,
1155                     new Tuple<Integer, String>( even, "v" + even ),
1156                     new Tuple<Integer, String>( even + 1, "v" + ( even + 1 ) )
1157                     );
1158 
1159                 counter += 2;
1160 
1161                 addPage( btree, node, leaf, j );
1162 
1163                 EXPECTED1.add( even );
1164                 EXPECTED1.add( even + 1 );
1165             }
1166 
1167             addPage( btree, root, node, i );
1168         }
1169 
1170         btree.setRoot( root );
1171 
1172         return btree;
1173     }
1174 
1175 
1176     /**
1177      * Remove an element from the tree, checking that the removal was successful 
1178      * @param btree The btree on which we remove an element
1179      * @param element The removed element
1180      * @param expected The expected set of elements
1181      */
1182     private void checkRemoval( BTree<Integer, String> btree, int element, Set<Integer> expected ) throws IOException
1183     {
1184         Tuple<Integer, String> removed = btree.delete( element );
1185         assertEquals( element, removed.getKey().intValue() );
1186         assertEquals( "v" + element, removed.getValue() );
1187 
1188         checkNull( btree, element );
1189 
1190         expected.remove( element );
1191         checkTree( btree, expected );
1192     }
1193 
1194 
1195     /**
1196      * Check that the tree contains all the elements in the expected set, and that
1197      * all the elements in the tree are also present in the set
1198      * 
1199      * @param btree The tree to check
1200      * @param expected The set with the expected elements
1201      */
1202     private void checkTree( BTree<Integer, String> btree, Set<Integer> expected )
1203     {
1204         try
1205         {
1206             TupleCursor<Integer, String> cursor = btree.browse();
1207             Integer value = null;
1208 
1209             while ( cursor.hasNext() )
1210             {
1211                 Tuple<Integer, String> tuple = cursor.next();
1212 
1213                 if ( value == null )
1214                 {
1215                     value = tuple.getKey();
1216                 }
1217                 else
1218                 {
1219                     assertTrue( value < tuple.getKey() );
1220                     value = tuple.getKey();
1221                 }
1222 
1223                 assertTrue( expected.contains( value ) );
1224                 expected.remove( value );
1225             }
1226 
1227             assertEquals( 0, expected.size() );
1228         }
1229         catch ( IOException ioe )
1230         {
1231             fail();
1232         }
1233     }
1234 
1235 
1236     /**
1237      * Remove a set of values from a btree
1238      * 
1239      * @param btree The modified btree
1240      * @param expected The set of expected values to update
1241      * @param values The values to remove
1242      */
1243     private void delete( BTree<Integer, String> btree, Set<Integer> expected, int... values ) throws IOException
1244     {
1245         for ( int value : values )
1246         {
1247             btree.delete( value );
1248             expected.remove( value );
1249         }
1250     }
1251 
1252 
1253     /**
1254      * Test deletions in a tree with more than one level. We are specifically testing
1255      * the deletions that will generate a merge in the leaves.
1256      */
1257     @Test
1258     public void testDeleteMultiLevelsLeadingToLeafMerge() throws Exception
1259     {
1260         BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
1261 
1262         // Case 1 : delete the leftmost element in the btree in the leftmost leaf
1263         Tuple<Integer, String> removed = btree.delete( 2 );
1264         assertEquals( 2, removed.getKey().intValue() );
1265         assertEquals( "v2", removed.getValue() );
1266         checkNull( btree, 2 );
1267 
1268         // delete the third element in the first leaf
1269         removed = btree.delete( 7 );
1270         assertEquals( 7, removed.getKey().intValue() );
1271         assertEquals( "v7", removed.getValue() );
1272         checkNull( btree, 7 );
1273 
1274         // Case 2 : Delete the second element in the leftmost leaf
1275         removed = btree.delete( 6 );
1276         assertEquals( 6, removed.getKey().intValue() );
1277         assertEquals( "v6", removed.getValue() );
1278         checkNull( btree, 6 );
1279 
1280         // delete the third element in the first leaf
1281         removed = btree.delete( 11 );
1282         assertEquals( 11, removed.getKey().intValue() );
1283         assertEquals( "v11", removed.getValue() );
1284         checkNull( btree, 11 );
1285 
1286         // Case 3 : delete the rightmost element in the btree in the rightmost leaf
1287         removed = btree.delete( 99 );
1288         assertEquals( 99, removed.getKey().intValue() );
1289         assertEquals( "v99", removed.getValue() );
1290         checkNull( btree, 99 );
1291 
1292         // delete the third element in the last leaf
1293         removed = btree.delete( 98 );
1294         assertEquals( 98, removed.getKey().intValue() );
1295         assertEquals( "v98", removed.getValue() );
1296         checkNull( btree, 98 );
1297 
1298         // Case 2 : Delete the first element in the rightmost leaf
1299         removed = btree.delete( 94 );
1300         assertEquals( 94, removed.getKey().intValue() );
1301         assertEquals( "v94", removed.getValue() );
1302         checkNull( btree, 94 );
1303 
1304         // delete the third element in the last leaf
1305         removed = btree.delete( 95 );
1306         assertEquals( 95, removed.getKey().intValue() );
1307         assertEquals( "v95", removed.getValue() );
1308         checkNull( btree, 95 );
1309 
1310         // Case 5 : delete the leftmost element which is referred in the root node
1311         removed = btree.delete( 22 );
1312         assertEquals( 22, removed.getKey().intValue() );
1313         assertEquals( "v22", removed.getValue() );
1314         checkNull( btree, 22 );
1315 
1316         // delete the third element in the last leaf
1317         removed = btree.delete( 27 );
1318         assertEquals( 27, removed.getKey().intValue() );
1319         assertEquals( "v27", removed.getValue() );
1320         checkNull( btree, 27 );
1321 
1322         // Case 6 : delete the leftmost element in a leaf in the middle of the tree
1323         removed = btree.delete( 70 );
1324         assertEquals( 70, removed.getKey().intValue() );
1325         assertEquals( "v70", removed.getValue() );
1326         checkNull( btree, 70 );
1327 
1328         // delete the third element in the leaf
1329         removed = btree.delete( 71 );
1330         assertEquals( 71, removed.getKey().intValue() );
1331         assertEquals( "v71", removed.getValue() );
1332         checkNull( btree, 71 );
1333 
1334         // Case 7 : delete the rightmost element in a leaf in the middle of the tree
1335         removed = btree.delete( 51 );
1336         assertEquals( 51, removed.getKey().intValue() );
1337         assertEquals( "v51", removed.getValue() );
1338         checkNull( btree, 51 );
1339 
1340         // delete the third element in the leaf
1341         removed = btree.delete( 50 );
1342         assertEquals( 50, removed.getKey().intValue() );
1343         assertEquals( "v50", removed.getValue() );
1344         checkNull( btree, 50 );
1345 
1346         btree.close();
1347     }
1348 
1349 
1350     /**
1351      * Test various deletions in a two level high tree, when we have leaves
1352      * containing N/2 elements (thus each deletion leads to a merge)
1353      */
1354     @Test
1355     public void testDelete2LevelsTreeWithHalfFullLeaves() throws Exception
1356     {
1357         // Create a BTree with pages containing 4 elements
1358         BTree<Integer, String> btree = createTwoLevelBTreeHalfFullLeaves();
1359 
1360         // Test removals leadings to various merges.
1361         // Delete from the middle, not the leftmost value of the leaf
1362         btree.delete( 10 );
1363         checkNull( btree, 10 );
1364 
1365         // Delete the extraneous value
1366         btree.delete( 9 );
1367         checkNull( btree, 9 );
1368 
1369         // Delete the leftmost element in the middle
1370         btree.delete( 13 );
1371         checkNull( btree, 13 );
1372 
1373         // Delete the extraneous value
1374         btree.delete( 14 );
1375         checkNull( btree, 14 );
1376 
1377         // Delete the rightmost value
1378         btree.delete( 18 );
1379         checkNull( btree, 18 );
1380 
1381         // Delete the extraneous value
1382         btree.delete( 5 );
1383         checkNull( btree, 5 );
1384 
1385         // Delete the leftmost value of the right leaf
1386         btree.delete( 6 );
1387         checkNull( btree, 6 );
1388 
1389         btree.close();
1390     }
1391 
1392 
1393     /**
1394      * Test deletions in a tree with more than one level. We are specifically testing
1395      * the deletions that will make a node borrowing some element from a sibling.
1396      * 
1397      * 1: remove the leftmost element
1398      */
1399     @Test
1400     public void testDeleteMultiLevelsLeadingToNodeBorrowRight1() throws Exception
1401     {
1402         BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
1403 
1404         // deleting as many elements as necessary to get the node ready for a merge
1405         delete( btree, EXPECTED1, 2, 3, 6, 7 );
1406 
1407         // delete the element
1408         checkRemoval( btree, 10, EXPECTED1 );
1409 
1410         btree.close();
1411     }
1412 
1413 
1414     /**
1415      * Test deletions in a tree with more than one level. We are specifically testing
1416      * the deletions that will make a node borrowing some element from a sibling.
1417      * 
1418      * 2: remove an element on the leftmost page but not the first one
1419      */
1420     @Test
1421     public void testDeleteMultiLevelsLeadingToNodeBorrowRight2() throws Exception
1422     {
1423         BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
1424 
1425         // deleting as many elements as necessary to get the node ready for a merge
1426         delete( btree, EXPECTED1, 2, 3, 6, 7 );
1427 
1428         // delete the element
1429         checkRemoval( btree, 11, EXPECTED1 );
1430 
1431         btree.close();
1432     }
1433 
1434 
1435     /**
1436      * Test deletions in a tree with more than one level. We are specifically testing
1437      * the deletions that will make a node borrowing some element from a sibling.
1438      * 
1439      * 3: remove an element on the rightmost page on the leftmost node on the upper level
1440      */
1441     @Test
1442     public void testDeleteMultiLevelsLeadingToNodeBorrowRight3() throws Exception
1443     {
1444         BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
1445 
1446         // deleting as many elements as necessary to get the node ready for a merge
1447         delete( btree, EXPECTED1, 2, 3, 6, 7 );
1448 
1449         // delete the element
1450         checkRemoval( btree, 19, EXPECTED1 );
1451 
1452         btree.close();
1453     }
1454 
1455 
1456     /**
1457      * Test deletions in a tree with more than one level. We are specifically testing
1458      * the deletions that will make a node borrowing some element from a sibling.
1459      * 
1460      * 4: remove the first element in a page in the middle of the first node
1461      */
1462     @Test
1463     public void testDeleteMultiLevelsLeadingToNodeBorrowRight4() throws Exception
1464     {
1465         BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
1466 
1467         // deleting as many elements as necessary to get the node ready for a merge
1468         delete( btree, EXPECTED1, 2, 3, 6, 7 );
1469 
1470         // delete the element
1471         checkRemoval( btree, 14, EXPECTED1 );
1472 
1473         btree.close();
1474     }
1475 
1476 
1477     /**
1478      * Test deletions in a tree with more than one level. We are specifically testing
1479      * the deletions that will make a node borrowing some element from a sibling.
1480      * 
1481      * 5: remove the second element in a page in the middle of the first node
1482      */
1483     @Test
1484     public void testDeleteMultiLevelsLeadingToNodeBorrowRight5() throws Exception
1485     {
1486         BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
1487 
1488         // deleting as many elements as necessary to get the node ready for a merge
1489         delete( btree, EXPECTED1, 2, 3, 6, 7 );
1490 
1491         // delete the element
1492         checkRemoval( btree, 15, EXPECTED1 );
1493 
1494         btree.close();
1495     }
1496 
1497 
1498     /**
1499      * Test deletions in a tree with more than one level. We are specifically testing
1500      * the deletions that will make a node borrowing some element from a sibling.
1501      * 
1502      * 1: remove the rightmost element
1503      */
1504     @Test
1505     public void testDeleteMultiLevelsLeadingToNodeBorrowLeft1() throws Exception
1506     {
1507         BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
1508 
1509         // deleting as many elements as necessary to get the node ready for a merge
1510         delete( btree, EXPECTED1, 94, 95, 98, 99 );
1511 
1512         // delete the element
1513         checkRemoval( btree, 91, EXPECTED1 );
1514 
1515         btree.close();
1516     }
1517 
1518 
1519     /**
1520      * Test deletions in a tree with more than one level. We are specifically testing
1521      * the deletions that will make a node borrowing some element from a sibling.
1522      * 
1523      * 1: remove the element before the rightmost element
1524      */
1525     @Test
1526     public void testDeleteMultiLevelsLeadingToNodeBorrowLeft2() throws Exception
1527     {
1528         BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
1529 
1530         // deleting as many elements as necessary to get the node ready for a merge
1531         delete( btree, EXPECTED1, 94, 95, 98, 99 );
1532 
1533         // delete the element
1534         checkRemoval( btree, 90, EXPECTED1 );
1535 
1536         btree.close();
1537     }
1538 
1539 
1540     /**
1541      * Test deletions in a tree with more than one level. We are specifically testing
1542      * the deletions that will make a node borrowing some element from a sibling.
1543      * 
1544      * 1: remove the leftmost element  of the rightmost leaf
1545      */
1546     @Test
1547     public void testDeleteMultiLevelsLeadingToNodeBorrowLeft3() throws Exception
1548     {
1549         BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
1550 
1551         // deleting as many elements as necessary to get the node ready for a merge
1552         delete( btree, EXPECTED1, 94, 95, 98, 99 );
1553 
1554         // delete the element
1555         checkRemoval( btree, 82, EXPECTED1 );
1556 
1557         btree.close();
1558     }
1559 
1560 
1561     /**
1562      * Test deletions in a tree with more than one level. We are specifically testing
1563      * the deletions that will make a node borrowing some element from a sibling.
1564      * 
1565      * 1: remove the second elemnt of the leftmost page on the rightmost second level node
1566      */
1567     @Test
1568     public void testDeleteMultiLevelsLeadingToNodeBorrowLeft4() throws Exception
1569     {
1570         BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
1571 
1572         // deleting as many elements as necessary to get the node ready for a merge
1573         delete( btree, EXPECTED1, 94, 95, 98, 99 );
1574 
1575         // delete the element
1576         checkRemoval( btree, 83, EXPECTED1 );
1577 
1578         btree.close();
1579     }
1580 
1581 
1582     /**
1583      * Test deletions in a tree with more than one level. We are specifically testing
1584      * the deletions that will make a node borrowing some element from a sibling.
1585      * 
1586      * 6: remove the first element of a leaf in the middle of the tree
1587      */
1588     @Test
1589     public void testDeleteMultiLevelsLeadingToNodeBorrowLeft6() throws Exception
1590     {
1591         BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
1592 
1593         // deleting as many elements as necessary to get the node ready for a merge
1594         delete( btree, EXPECTED1, 42, 43, 46, 47 );
1595 
1596         // delete 
1597         checkRemoval( btree, 50, EXPECTED1 );
1598 
1599         btree.close();
1600     }
1601 
1602 
1603     /**
1604      * Test deletions in a tree with more than one level. We are specifically testing
1605      * the deletions that will make a node borrowing some element from a sibling.
1606      * 
1607      * 7: remove the second element of a leaf in the middle of the tree
1608      */
1609     @Test
1610     public void testDeleteMultiLevelsLeadingToNodeBorrowLeft7() throws Exception
1611     {
1612         BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
1613 
1614         // deleting as many elements as necessary to get the node ready for a merge
1615         delete( btree, EXPECTED1, 42, 43, 46, 47 );
1616 
1617         // delete 
1618         checkRemoval( btree, 51, EXPECTED1 );
1619 
1620         btree.close();
1621     }
1622 
1623 
1624     /**
1625      * Test deletions in a tree with more than one level. We are specifically testing
1626      * the deletions that will make a node borrowing some element from a sibling.
1627      * 
1628      * 8: remove the last element of a leaf in the middle of the tree
1629      */
1630     @Test
1631     public void testDeleteMultiLevelsLeadingToNodeBorrowLeft8() throws Exception
1632     {
1633         BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
1634 
1635         // deleting as many elements as necessary to get the node ready for a merge
1636         delete( btree, EXPECTED1, 42, 43, 46, 47 );
1637 
1638         // delete 
1639         checkRemoval( btree, 59, EXPECTED1 );
1640 
1641         btree.close();
1642     }
1643 
1644 
1645     /**
1646      * Test deletions in a tree with more than one level. We are specifically testing
1647      * the deletions that will make a node borrowing some element from a sibling.
1648      * 
1649      * 9: remove the element before the last one of a leaf in the middle of the tree
1650      */
1651     @Test
1652     public void testDeleteMultiLevelsLeadingToNodeBorrowLeft9() throws Exception
1653     {
1654         BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
1655 
1656         // deleting as many elements as necessary to get the node ready for a merge
1657         delete( btree, EXPECTED1, 42, 43, 46, 47 );
1658 
1659         // delete 
1660         checkRemoval( btree, 58, EXPECTED1 );
1661 
1662         btree.close();
1663     }
1664 
1665 
1666     /**
1667      * Test deletions in a tree with more than one level. We are specifically testing
1668      * the deletions that will make a node borrowing some element from a sibling.
1669      * 
1670      * 10: remove the mid element of a leaf in the middle of the tree
1671      */
1672     @Test
1673     public void testDeleteMultiLevelsLeadingToNodeBorrowLeft10() throws Exception
1674     {
1675         BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
1676 
1677         // deleting as many elements as necessary to get the node ready for a merge
1678         delete( btree, EXPECTED1, 42, 43, 46, 47 );
1679 
1680         // delete 
1681         checkRemoval( btree, 54, EXPECTED1 );
1682 
1683         btree.close();
1684     }
1685 
1686 
1687     /**
1688      * Test deletions in a tree with more than one level. We are specifically testing
1689      * the deletions that will make a node borrowing some element from a sibling.
1690      * 
1691      * 11: remove the mid+1 element of a leaf in the middle of the tree
1692      */
1693     @Test
1694     public void testDeleteMultiLevelsLeadingToNodeBorrowLeft11() throws Exception
1695     {
1696         BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
1697 
1698         // deleting as many elements as necessary to get the node ready for a merge
1699         delete( btree, EXPECTED1, 42, 43, 46, 47 );
1700 
1701         // delete 
1702         checkRemoval( btree, 55, EXPECTED1 );
1703 
1704         btree.close();
1705     }
1706 
1707 
1708     /**
1709      * Test the addition of elements with null values
1710      */
1711     @Test
1712     public void testAdditionNullValues() throws IOException
1713     {
1714         BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
1715 
1716         // Adding an element with a null value
1717         btree.insert( 100, null );
1718 
1719         assertTrue( btree.hasKey( 100 ) );
1720 
1721         try
1722         {
1723             assertNull( btree.get( 100 ) );
1724         }
1725         catch ( KeyNotFoundException knfe )
1726         {
1727             fail();
1728         }
1729 
1730         Tuple<Integer, String> deleted = btree.delete( 100 );
1731 
1732         assertNotNull( deleted );
1733         assertNull( deleted.getValue() );
1734     }
1735 
1736 
1737     /**
1738      * Test the insertion of 5 million elements in a BTree
1739      * @throws Exception
1740      */
1741     @Test
1742     public void testBrowse500K() throws Exception
1743     {
1744         Random random = new Random( System.nanoTime() );
1745 
1746         int nbError = 0;
1747 
1748         int n = 0;
1749         int nbElems = 500000;
1750         long delta = System.currentTimeMillis();
1751 
1752         // Create a BTree with 5 million entries
1753         BTree<Long, String> btree = new BTree<Long, String>( "test", new LongSerializer(), new StringSerializer() );
1754         btree.setPageSize( 32 );
1755 
1756         for ( int i = 0; i < nbElems; i++ )
1757         {
1758             Long key = ( long ) random.nextLong();
1759             String value = Long.toString( key );
1760 
1761             try
1762             {
1763                 btree.insert( key, value );
1764             }
1765             catch ( Exception e )
1766             {
1767                 e.printStackTrace();
1768                 System.out.println( btree );
1769                 System.out.println( "Error while adding " + value );
1770                 nbError++;
1771                 btree.close();
1772 
1773                 return;
1774             }
1775 
1776             if ( i % 100000 == 0 )
1777             {
1778                 if ( n > 0 )
1779                 {
1780                     long t0 = System.currentTimeMillis();
1781                     System.out.println( "Delta" + n + ": " + ( t0 - delta ) );
1782                     delta = t0;
1783                 }
1784 
1785                 n++;
1786             }
1787         }
1788 
1789         // Now browse them
1790         long l1 = System.currentTimeMillis();
1791 
1792         TupleCursor<Long, String> cursor = btree.browse();
1793 
1794         int nb = 0;
1795         long elem = Long.MIN_VALUE;
1796 
1797         while ( cursor.hasNext() )
1798         {
1799             Tuple<Long, String> res = cursor.next();
1800 
1801             if ( res.getKey() > elem )
1802             {
1803                 elem = res.getKey();
1804                 nb++;
1805             }
1806         }
1807 
1808         System.out.println( "Nb elements read : " + nb );
1809 
1810         cursor.close();
1811         btree.close();
1812 
1813         long l2 = System.currentTimeMillis();
1814 
1815         System.out.println( "Delta : " + ( l2 - l1 ) + ", nbError = " + nbError
1816             + ", Nb searches per second : " + ( ( nbElems * 1000 ) / ( l2 - l1 ) ) );
1817     }
1818 
1819 
1820     private void checkNull( BTree<Long, String> btree, long key ) throws IOException
1821     {
1822         try
1823         {
1824             btree.get( key );
1825             fail();
1826         }
1827         catch ( KeyNotFoundException knfe )
1828         {
1829             // expected
1830         }
1831     }
1832 
1833 
1834     private void checkNull( BTree<Integer, String> btree, int key ) throws IOException
1835     {
1836         try
1837         {
1838             btree.get( key );
1839             fail();
1840         }
1841         catch ( KeyNotFoundException knfe )
1842         {
1843             // expected
1844         }
1845     }
1846 
1847 
1848     /**
1849      * Test a browse forward and backward
1850      */
1851     @Test
1852     public void testBrowseForwardBackwardExtremes() throws Exception
1853     {
1854         // Create a BTree with pages containing 4 elements
1855         BTree<Integer, String> btree = new BTree<Integer, String>( "test", new IntSerializer(), new StringSerializer() );
1856         btree.setPageSize( 4 );
1857 
1858         for ( int i = 8; i < 13; i++ )
1859         {
1860             String strValue = "V" + i;
1861             btree.insert( i, strValue );
1862         }
1863 
1864         // Start to browse in the middle
1865         TupleCursor<Integer, String> cursor = btree.browseFrom( 8 );
1866 
1867         assertTrue( cursor.hasNext() );
1868 
1869         // Get 8
1870         assertEquals( 8, cursor.next().getKey().intValue() );
1871 
1872         // get 9
1873         assertEquals( 9, cursor.next().getKey().intValue() );
1874 
1875         // get 10
1876         assertEquals( 10, cursor.next().getKey().intValue() );
1877 
1878         // get 11
1879         assertEquals( 11, cursor.next().getKey().intValue() );
1880 
1881         // get 12 (now, we must have gone through at least 2 pages)
1882         assertEquals( 12, cursor.next().getKey().intValue() );
1883 
1884         assertFalse( cursor.hasNext() );
1885         assertTrue( cursor.hasPrev() );
1886 
1887         // Lets go backward.
1888         assertEquals( 11, cursor.prev().getKey().intValue() );
1889 
1890         // Get 10
1891         assertEquals( 10, cursor.prev().getKey().intValue() );
1892 
1893         // Get 9
1894         assertEquals( 9, cursor.prev().getKey().intValue() );
1895 
1896         // Get 8
1897         assertEquals( 8, cursor.prev().getKey().intValue() );
1898 
1899         assertFalse( cursor.hasPrev() );
1900         assertTrue( cursor.hasNext() );
1901 
1902         cursor.close();
1903         btree.close();
1904     }
1905 
1906 
1907     @Test
1908     public void testNextAfterPrev() throws Exception
1909     {
1910         IntSerializer serializer = new IntSerializer();
1911 
1912         BTreeConfiguration<Integer, Integer> config = new BTreeConfiguration<Integer, Integer>();
1913         config.setName( "master" );
1914         config.setPageSize( 4 );
1915         config.setSerializers( serializer, serializer );
1916         BTree<Integer, Integer> btree = new BTree<Integer, Integer>( config );
1917 
1918         int i = 7;
1919         for ( int k = 0; k < i; k++ )
1920         {
1921             btree.insert( k, k );
1922         }
1923 
1924         // 3 is the last element of the first leaf
1925         TupleCursor<Integer, Integer> cursor = btree.browseFrom( 4 );
1926 
1927         assertTrue( cursor.hasNext() );
1928         Tuple<Integer, Integer> tuple = cursor.next();
1929         assertEquals( Integer.valueOf( 4 ), tuple.getKey() );
1930         assertEquals( Integer.valueOf( 4 ), tuple.getValue() );
1931 
1932         assertTrue( cursor.hasPrev() );
1933         tuple = cursor.prev();
1934         assertEquals( Integer.valueOf( 3 ), tuple.getKey() );
1935         assertEquals( Integer.valueOf( 3 ), tuple.getValue() );
1936 
1937         assertTrue( cursor.hasNext() );
1938         tuple = cursor.next();
1939         assertEquals( Integer.valueOf( 4 ), tuple.getKey() );
1940         assertEquals( Integer.valueOf( 4 ), tuple.getValue() );
1941         cursor.close();
1942         btree.close();
1943     }
1944 
1945     
1946     @Test
1947     public void testCheckRootPageContents() throws Exception
1948     {
1949         IntSerializer ser = new IntSerializer();
1950         BTree<Integer, Integer> btree = new BTree<Integer,Integer>( "master1", ser, ser );
1951         btree.setPageSize( 4 );
1952         btree.init();
1953 
1954         for( int i=1; i < 8; i++ )
1955         {
1956             btree.insert( i, i );
1957         }
1958 
1959         System.out.println( btree.rootPage );
1960         assertEquals( 2, btree.rootPage.getNbElems() );
1961 
1962         assertEquals( 7, btree.rootPage.findRightMost().getKey().intValue() );
1963 
1964         assertEquals( 1, btree.rootPage.findLeftMost().getKey().intValue() );
1965 
1966         btree.close();
1967     }
1968 
1969 }