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