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.managed;
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.assertTrue;
27  import static org.junit.Assert.fail;
28  
29  import java.io.File;
30  import java.io.IOException;
31  import java.util.NoSuchElementException;
32  import java.util.UUID;
33  
34  import org.apache.directory.mavibot.btree.Tuple;
35  import org.apache.directory.mavibot.btree.TupleCursor;
36  import org.apache.directory.mavibot.btree.exception.BTreeAlreadyManagedException;
37  import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
38  import org.apache.directory.mavibot.btree.serializer.LongSerializer;
39  import org.apache.directory.mavibot.btree.serializer.StringSerializer;
40  import org.junit.Before;
41  import org.junit.Rule;
42  import org.junit.Test;
43  import org.junit.rules.TemporaryFolder;
44  
45  
46  /**
47   * Tests the browse methods on a managed BTree
48   * 
49   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
50   */
51  public class ManagedBTreeBrowseTest
52  {
53      private BTree<Long, String> btree = null;
54  
55      private RecordManager recordManager1 = null;
56  
57      @Rule
58      public TemporaryFolder tempFolder = new TemporaryFolder();
59  
60      private File dataDir = null;
61  
62  
63      /**
64       * Create a BTree for this test
65       */
66      @Before
67      public void createBTree()
68      {
69          dataDir = tempFolder.newFolder( UUID.randomUUID().toString() );
70  
71          openRecordManagerAndBtree();
72  
73          try
74          {
75              // Create a new BTree which allows duplicate values
76              btree = recordManager1.addBTree( "test", new LongSerializer(), new StringSerializer(), true );
77          }
78          catch ( Exception e )
79          {
80              throw new RuntimeException( e );
81          }
82      }
83  
84  
85      /**
86       * Reload the BTree into a new record manager
87       */
88      private void openRecordManagerAndBtree()
89      {
90          try
91          {
92              if ( recordManager1 != null )
93              {
94                  recordManager1.close();
95              }
96  
97              // Now, try to reload the file back
98              recordManager1 = new RecordManager( dataDir.getAbsolutePath() );
99  
100             // load the last created btree
101             if ( btree != null )
102             {
103                 btree = recordManager1.getManagedTree( btree.getName() );
104             }
105         }
106         catch ( Exception e )
107         {
108             throw new RuntimeException( e );
109         }
110     }
111 
112 
113     /**
114      * Check a tuple
115      */
116     private void checkTuple( Tuple<Long, String> tuple, long key, String value ) throws EndOfFileExceededException, IOException
117     {
118         assertNotNull( tuple );
119         assertEquals( key, (long)tuple.getKey() );
120         assertEquals( value, tuple.getValue() );
121     }
122 
123 
124     /**
125      * Check a next() call
126      */
127     private void checkNext( TupleCursor<Long, String> cursor, long key, String value, boolean next, boolean prev ) throws EndOfFileExceededException, IOException
128     {
129         Tuple<Long, String> tuple = cursor.next();
130         
131         checkTuple( tuple, key, value );
132         assertEquals( next, cursor.hasNext() );
133         assertEquals( prev, cursor.hasPrev() );
134     }
135 
136 
137     /**
138      * Check a prev() call
139      */
140     private void checkPrev( TupleCursor<Long, String> cursor, long key, String value, boolean next, boolean prev ) throws EndOfFileExceededException, IOException
141     {
142         Tuple<Long, String> tuple = cursor.prev();
143         assertNotNull( tuple );
144         assertEquals( key, (long)tuple.getKey() );
145         assertEquals( value, tuple.getValue() );
146         assertEquals( next, cursor.hasNext() );
147         assertEquals( prev, cursor.hasPrev() );
148     }
149 
150     
151     /**
152      * Construct a String representation of a number padded with 0 on the left
153      */
154     private String toString( long value, int size )
155     {
156         String valueStr = Long.toString( value );
157         
158         StringBuilder sb = new StringBuilder();
159         
160         if ( size > valueStr.length() )
161         {
162             for ( int i = valueStr.length(); i < size; i++ )
163             {
164                 sb.append( "0" );
165             }
166         }
167         
168         sb.append( valueStr );
169         
170         return sb.toString();
171     }
172 
173 
174     
175     //----------------------------------------------------------------------------------------
176     // The Browse tests
177     //----------------------------------------------------------------------------------------
178     /**
179      * Test the browse methods on an empty btree  
180      */
181     @Test
182     public void testBrowseEmptyBTree() throws IOException, BTreeAlreadyManagedException
183     {
184         TupleCursor<Long, String> cursor = btree.browse();
185         
186         assertFalse( cursor.hasNext() );
187         assertFalse( cursor.hasPrev() );
188         
189         try
190         {
191             cursor.next();
192             fail();
193         }
194         catch ( NoSuchElementException nsee )
195         {
196             // Expected
197         }
198         
199         try
200         {
201             cursor.prev();
202             fail();
203         }
204         catch ( NoSuchElementException nsee )
205         {
206             // Expected
207         }
208         
209         assertEquals( -1L, cursor.getRevision() );
210     }
211 
212 
213     /**
214      * Test the browse methods on a btree containing just a leaf
215      */
216     @Test
217     public void testBrowseBTreeLeafNext() throws IOException, BTreeAlreadyManagedException
218     {
219         // Inject some data
220         btree.insert( 1L, "1" );
221         btree.insert( 4L, "4" );
222         btree.insert( 2L, "2" );
223         btree.insert( 3L, "3" );
224         btree.insert( 5L, "5" );
225 
226         // Create the cursor
227         TupleCursor<Long, String> cursor = btree.browse();
228         
229         // Move forward
230         cursor.beforeFirst();
231         
232         assertFalse( cursor.hasPrev() );
233         assertTrue( cursor.hasNext() );
234         
235         checkNext( cursor, 1L, "1", true, false );
236         checkNext( cursor, 2L, "2", true, true );
237         checkNext( cursor, 3L, "3", true, true );
238         checkNext( cursor, 4L, "4", true, true );
239         checkNext( cursor, 5L, "5", false, true );
240     }
241 
242 
243     /**
244      * Test the browse methods on a btree containing just a leaf
245      */
246     @Test
247     public void testBrowseBTreeLeafPrev() throws IOException, BTreeAlreadyManagedException
248     {
249         // Inject some data
250         btree.insert( 1L, "1" );
251         btree.insert( 4L, "4" );
252         btree.insert( 2L, "2" );
253         btree.insert( 3L, "3" );
254         btree.insert( 5L, "5" );
255 
256         // Create the cursor
257         TupleCursor<Long, String> cursor = btree.browse();
258         
259         // Move backward
260         cursor.afterLast();
261         
262         checkPrev( cursor, 5L, "5", false, true );
263         checkPrev( cursor, 4L, "4", true, true );
264         checkPrev( cursor, 3L, "3", true, true );
265         checkPrev( cursor, 2L, "2", true, true );
266         checkPrev( cursor, 1L, "1", true, false );
267     }
268 
269 
270     /**
271      * Test the browse methods on a btree containing just a leaf and see if we can
272      * move at the end or at the beginning
273      */
274     @Test
275     public void testBrowseBTreeLeafFirstLast() throws IOException, BTreeAlreadyManagedException
276     {
277         // Inject some data
278         btree.insert( 1L, "1" );
279         btree.insert( 4L, "4" );
280         btree.insert( 2L, "2" );
281         btree.insert( 3L, "3" );
282         btree.insert( 5L, "5" );
283 
284         // Create the cursor
285         TupleCursor<Long, String> cursor = btree.browse();
286         
287         // We should not be able to move backward
288         try
289         {
290             cursor.prev();
291             fail();
292         }
293         catch ( NoSuchElementException nsee )
294         {
295             // Expected
296         }
297 
298         // Start browsing three elements
299         assertFalse( cursor.hasPrev() );
300         assertTrue( cursor.hasNext() );
301         Tuple<Long, String> tuple = cursor.next();
302         tuple = cursor.next();
303         tuple = cursor.next();
304         
305         // We should be at 3 now
306         assertTrue( cursor.hasPrev() );
307         assertTrue( cursor.hasNext() );
308         assertEquals( 3L, (long)tuple.getKey() );
309         assertEquals( "3", tuple.getValue() );
310         
311         // Move to the end
312         cursor.afterLast();
313 
314         assertTrue( cursor.hasPrev() );
315         assertFalse( cursor.hasNext() );
316 
317         // We should not be able to move forward
318         try
319         {
320             cursor.next();
321             fail();
322         }
323         catch ( NoSuchElementException nsee )
324         {
325             // Expected
326         }
327 
328         
329         // We should be at 5
330         tuple = cursor.prev();
331         assertEquals( 5L, (long)tuple.getKey() );
332         assertEquals( "5", tuple.getValue() );
333         
334         assertTrue( cursor.hasPrev() );
335         assertFalse( cursor.hasNext() );
336 
337         // Move back to the origin
338         cursor.beforeFirst();
339         
340         assertFalse( cursor.hasPrev() );
341         assertTrue( cursor.hasNext() );
342 
343         // We should be at 1
344         tuple = cursor.next();
345         assertEquals( 1L, (long)tuple.getKey() );
346         assertEquals( "1", tuple.getValue() );
347         
348         assertFalse( cursor.hasPrev() );
349         assertTrue( cursor.hasNext() );
350     }
351 
352 
353     /**
354      * Test the browse methods on a btree containing just a leaf and see if we can
355      * move back and forth
356      */
357     @Test
358     public void testBrowseBTreeLeafNextPrev() throws IOException, BTreeAlreadyManagedException
359     {
360         // Inject some data
361         btree.insert( 1L, "1" );
362         btree.insert( 4L, "4" );
363         btree.insert( 2L, "2" );
364         btree.insert( 3L, "3" );
365         btree.insert( 5L, "5" );
366 
367         // Create the cursor
368         TupleCursor<Long, String> cursor = btree.browse();
369         
370         // We should not be able to move backward
371         try
372         {
373             cursor.prev();
374             fail();
375         }
376         catch ( NoSuchElementException nsee )
377         {
378             // Expected
379         }
380 
381         // Start browsing three elements
382         assertFalse( cursor.hasPrev() );
383         assertTrue( cursor.hasNext() );
384         Tuple<Long, String> tuple = cursor.next();
385         tuple = cursor.next();
386         tuple = cursor.next();
387         
388         // We should be at 3 now
389         assertTrue( cursor.hasPrev() );
390         assertTrue( cursor.hasNext() );
391         assertEquals( 3L, (long)tuple.getKey() );
392         assertEquals( "3", tuple.getValue() );
393         
394         // Now, move to the prev value
395         cursor.prev();
396         assertEquals( 2L, (long)tuple.getKey() );
397         assertEquals( "2", tuple.getValue() );
398         
399         // And to the next value
400         cursor.next();
401         assertEquals( 3L, (long)tuple.getKey() );
402         assertEquals( "3", tuple.getValue() );
403     }
404 
405 
406     /**
407      * Test the browse methods on a btree containing many nodes
408      */
409     @Test
410     public void testBrowseBTreeNodesNext() throws IOException, BTreeAlreadyManagedException
411     {
412         // Inject some data
413         for ( long i = 1; i < 1000L; i++ )
414         {
415             btree.insert( i, Long.toString( i ) );
416         }
417 
418         // Create the cursor
419         TupleCursor<Long, String> cursor = btree.browse();
420         
421         // Move forward
422         cursor.beforeFirst();
423         
424         assertFalse( cursor.hasPrev() );
425         assertTrue( cursor.hasNext() );
426 
427         checkNext( cursor, 1L, "1", true, false );
428         
429         for ( long i = 2L; i < 999L; i++ )
430         {
431             checkNext( cursor, i, Long.toString( i ), true, true );
432         }
433 
434         checkNext( cursor, 999L, "999", false, true );
435     }
436 
437 
438     /**
439      * Test the browse methods on a btree containing many nodes
440      */
441     @Test
442     public void testBrowseBTreeNodesPrev() throws IOException, BTreeAlreadyManagedException
443     {
444         // Inject some data
445         for ( long i = 1; i < 1000L; i++ )
446         {
447             btree.insert( i, Long.toString( i ) );
448         }
449 
450         // Create the cursor
451         TupleCursor<Long, String> cursor = btree.browse();
452         
453         // Move backward
454         cursor.afterLast();
455         
456         assertTrue( cursor.hasPrev() );
457         assertFalse( cursor.hasNext() );
458         
459         checkPrev( cursor, 999L, "999", false, true );
460         
461         for ( long i = 998L; i > 1L; i-- )
462         {
463             checkPrev( cursor, i, Long.toString( i ), true, true );
464         }
465 
466         checkPrev( cursor, 1L, "1", true, false );
467     }
468 
469 
470     /**
471      * Test the browse methods on a btree containing just a leaf with duplicate values
472      */
473     @Test
474     public void testBrowseBTreeLeafNextDups1() throws IOException, BTreeAlreadyManagedException
475     {
476         // Inject some duplicate data
477         btree.insert( 1L, "1" );
478         btree.insert( 1L, "4" );
479         btree.insert( 1L, "2" );
480         btree.insert( 1L, "3" );
481         btree.insert( 1L, "5" );
482 
483         // Create the cursor
484         TupleCursor<Long, String> cursor = btree.browse();
485         
486         // Move forward
487         cursor.beforeFirst();
488         
489         assertFalse( cursor.hasPrev() );
490         assertTrue( cursor.hasNext() );
491         
492         checkNext( cursor, 1L, "1", true, false );
493         checkNext( cursor, 1L, "2", true, true );
494         checkNext( cursor, 1L, "3", true, true );
495         checkNext( cursor, 1L, "4", true, true );
496         checkNext( cursor, 1L, "5", false, true );
497     }
498 
499 
500     /**
501      * Test the browse methods on a btree containing just a leaf with duplicate values
502      */
503     @Test
504     public void testBrowseBTreeLeafNextDupsN() throws IOException, BTreeAlreadyManagedException
505     {
506         // Inject some duplicate data
507         btree.insert( 1L, "1" );
508         btree.insert( 1L, "4" );
509         btree.insert( 1L, "2" );
510         btree.insert( 2L, "3" );
511         btree.insert( 3L, "5" );
512         btree.insert( 3L, "7" );
513         btree.insert( 3L, "6" );
514 
515         // Create the cursor
516         TupleCursor<Long, String> cursor = btree.browse();
517         
518         // Move forward
519         cursor.beforeFirst();
520         
521         assertFalse( cursor.hasPrev() );
522         assertTrue( cursor.hasNext() );
523         
524         checkNext( cursor, 1L, "1", true, false );
525         checkNext( cursor, 1L, "2", true, true );
526         checkNext( cursor, 1L, "4", true, true );
527         checkNext( cursor, 2L, "3", true, true );
528         checkNext( cursor, 3L, "5", true, true );
529         checkNext( cursor, 3L, "6", true, true );
530         checkNext( cursor, 3L, "7", false, true );
531     }
532 
533 
534     /**
535      * Test the browse methods on a btree containing just a leaf with duplicate values
536      */
537     @Test
538     public void testBrowseBTreeLeafPrevDups1() throws IOException, BTreeAlreadyManagedException
539     {
540         // Inject some duplicate data
541         btree.insert( 1L, "1" );
542         btree.insert( 1L, "4" );
543         btree.insert( 1L, "2" );
544         btree.insert( 1L, "3" );
545         btree.insert( 1L, "5" );
546 
547         // Create the cursor
548         TupleCursor<Long, String> cursor = btree.browse();
549         
550         // Move backward
551         cursor.afterLast();
552         
553         assertTrue( cursor.hasPrev() );
554         assertFalse( cursor.hasNext() );
555         
556         checkPrev( cursor, 1L, "5", false, true );
557         checkPrev( cursor, 1L, "4", true, true );
558         checkPrev( cursor, 1L, "3", true, true );
559         checkPrev( cursor, 1L, "2", true, true );
560         checkPrev( cursor, 1L, "1", true, false );
561     }
562 
563 
564     /**
565      * Test the browse methods on a btree containing just a leaf with duplicate values
566      */
567     @Test
568     public void testBrowseBTreeLeafPrevDupsN() throws IOException, BTreeAlreadyManagedException
569     {
570         // Inject some duplicate data
571         btree.insert( 1L, "1" );
572         btree.insert( 1L, "4" );
573         btree.insert( 1L, "2" );
574         btree.insert( 2L, "3" );
575         btree.insert( 3L, "5" );
576         btree.insert( 3L, "7" );
577         btree.insert( 3L, "6" );
578 
579         // Create the cursor
580         TupleCursor<Long, String> cursor = btree.browse();
581         
582         // Move backward
583         cursor.afterLast();
584         
585         assertTrue( cursor.hasPrev() );
586         assertFalse( cursor.hasNext() );
587         
588         checkPrev( cursor, 3L, "7", false, true );
589         checkPrev( cursor, 3L, "6", true, true );
590         checkPrev( cursor, 3L, "5", true, true );
591         checkPrev( cursor, 2L, "3", true, true );
592         checkPrev( cursor, 1L, "4", true, true );
593         checkPrev( cursor, 1L, "2", true, true );
594         checkPrev( cursor, 1L, "1", true, false );
595     }
596 
597 
598     /**
599      * Test the browse methods on a btree containing nodes with duplicate values
600      */
601     @Test
602     public void testBrowseBTreeNodesNextDupsN() throws IOException, BTreeAlreadyManagedException
603     {
604         // Inject some data
605         for ( long i = 1; i < 1000L; i++ )
606         {
607             for ( long j = 1; j < 10; j++ )
608             {
609                 btree.insert( i, Long.toString( j ) );
610             }
611         }
612 
613         // Create the cursor
614         TupleCursor<Long, String> cursor = btree.browse();
615         
616         // Move backward
617         cursor.beforeFirst();
618         
619         assertFalse( cursor.hasPrev() );
620         assertTrue( cursor.hasNext() );
621         boolean next = true;
622         boolean prev = false;
623         
624         for ( long i = 1L; i < 1000L; i++ )
625         {
626             for ( long j = 1L; j < 10L; j++ )
627             {
628                 checkNext( cursor, i, Long.toString( j ), next, prev );
629                 
630                 if ( ( i == 1L ) && ( j == 1L ) )
631                 {
632                     prev = true;
633                 }
634                 
635                 if ( ( i == 999L ) && ( j == 8L ) )
636                 {
637                     next = false;
638                 }
639             }
640         }
641     }
642 
643 
644     /**
645      * Test the browse methods on a btree containing nodes with duplicate values
646      */
647     @Test
648     public void testBrowseBTreeNodesPrevDupsN() throws IOException, BTreeAlreadyManagedException
649     {
650         // Inject some data
651         for ( long i = 1; i < 1000L; i++ )
652         {
653             for ( int j = 1; j < 10; j++ )
654             {
655                 btree.insert( i, Long.toString( j ) );
656             }
657         }
658 
659         // Create the cursor
660         TupleCursor<Long, String> cursor = btree.browse();
661         
662         // Move backward
663         cursor.afterLast();
664         
665         assertTrue( cursor.hasPrev() );
666         assertFalse( cursor.hasNext() );
667         boolean next = false;
668         boolean prev = true;
669         
670         for ( long i = 999L; i > 0L; i-- )
671         {
672             for ( long j = 9L; j > 0L; j-- )
673             {
674                 checkPrev( cursor, i, Long.toString( j ), next, prev );
675                 
676                 if ( ( i == 1L ) && ( j == 2L ) )
677                 {
678                     prev = false;
679                 }
680                 
681                 if ( ( i == 999L ) && ( j == 9L ) )
682                 {
683                     next = true;
684                 }
685             }
686         }
687     }
688     
689 
690     /**
691      * Test the browse methods on a btree containing just a leaf with duplicate values
692      * stored into a sub btree
693      */
694     @Test
695     public void testBrowseBTreeLeafNextDupsSubBTree1() throws IOException, BTreeAlreadyManagedException
696     {
697         // Inject some duplicate data which will be stored into a sub btree
698         for ( long i = 1L; i < 32L; i++ )
699         {
700             btree.insert( 1L, toString( i, 2 ) );
701         }
702 
703         // Create the cursor
704         TupleCursor<Long, String> cursor = btree.browse();
705         
706         // Move forward
707         cursor.beforeFirst();
708         
709         assertFalse( cursor.hasPrev() );
710         assertTrue( cursor.hasNext() );
711         
712         checkNext( cursor, 1L, "01", true, false );
713         
714         for ( long i = 2L; i < 31L; i++ )
715         {
716             checkNext( cursor, 1L, toString( i, 2 ), true, true );
717         }
718         
719         checkNext( cursor, 1L, "31", false, true );
720     }
721 
722     /**
723      * Test the browse methods on a btree containing just a leaf with duplicate values
724      */
725     @Test
726     public void testBrowseBTreeLeafPrevDupsSubBTree1() throws IOException, BTreeAlreadyManagedException
727     {
728         // Inject some duplicate data which will be stored into a sub btree
729         for ( long i = 1L; i < 32L; i++ )
730         {
731             btree.insert( 1L, toString( i, 2 ) );
732         }
733 
734         // Create the cursor
735         TupleCursor<Long, String> cursor = btree.browse();
736         
737         // Move backward
738         cursor.afterLast();
739         
740         assertTrue( cursor.hasPrev() );
741         assertFalse( cursor.hasNext() );
742         
743         checkPrev( cursor, 1L, "31", false, true );
744         
745         for ( long i = 30L; i > 1L; i-- )
746         {
747             checkPrev( cursor, 1L, toString( i, 2 ), true, true );
748         }
749         
750         checkPrev( cursor, 1L, "01", true, false );
751     }
752 
753 
754     //----------------------------------------------------------------------------------------
755     // The BrowseFrom tests
756     //----------------------------------------------------------------------------------------
757     /**
758      * Test the browseFrom method on an empty tree
759      */
760     @Test
761     public void testBrowseFromEmptyBTree() throws IOException, BTreeAlreadyManagedException
762     {
763         TupleCursor<Long, String> cursor = btree.browseFrom( 1L );
764         
765         assertFalse( cursor.hasNext() );
766         assertFalse( cursor.hasPrev() );
767         
768         try
769         {
770             cursor.next();
771             fail();
772         }
773         catch ( NoSuchElementException nsee )
774         {
775             // Expected
776         }
777         
778         try
779         {
780             cursor.prev();
781             fail();
782         }
783         catch ( NoSuchElementException nsee )
784         {
785             // Expected
786         }
787         
788         assertEquals( -1L, cursor.getRevision() );
789     }
790 
791 
792     /**
793      * Test the browseFrom methods on a btree containing just a leaf
794      */
795     @Test
796     public void testBrowseFromBTreeLeaf() throws IOException, BTreeAlreadyManagedException
797     {
798         // Inject some data
799         btree.insert( 1L, "1" );
800         btree.insert( 7L, "7" );
801         btree.insert( 3L, "3" );
802         btree.insert( 5L, "5" );
803         btree.insert( 9L, "9" );
804 
805         // Create the cursor, starting at 5
806         TupleCursor<Long, String> cursor = btree.browseFrom( 5L );
807         
808         assertTrue( cursor.hasPrev() );
809         assertTrue( cursor.hasNext() );
810         
811         // Move forward
812         checkNext( cursor, 5L, "5", true, true );
813         checkNext( cursor, 7L, "7", true, true );
814         checkNext( cursor, 9L, "9", false, true );
815         
816         cursor.close();
817         
818         // now, start at 5 and move backward
819         cursor = btree.browseFrom( 5L );
820         
821         assertTrue( cursor.hasPrev() );
822         assertTrue( cursor.hasNext() );
823         
824         // Move backward
825         checkPrev( cursor, 3L, "3", true, true );
826         checkPrev( cursor, 1L, "1", true, false );
827         cursor.close();
828         
829         // Start at the first key
830         cursor = btree.browseFrom( 1L );
831         assertFalse( cursor.hasPrev() );
832         assertTrue( cursor.hasNext() );
833 
834         checkNext( cursor, 1L, "1", true, false );
835         checkNext( cursor, 3L, "3", true, true );
836         
837         // Start before the first key
838         cursor = btree.browseFrom( 0L );
839         assertFalse( cursor.hasPrev() );
840         assertTrue( cursor.hasNext() );
841 
842         checkNext( cursor, 1L, "1", true, false );
843         checkNext( cursor, 3L, "3", true, true );
844         
845         // Start at the last key
846         cursor = btree.browseFrom( 9L );
847         assertTrue( cursor.hasPrev() );
848         assertTrue( cursor.hasNext() );
849 
850         checkNext( cursor, 9L, "9", false, true );
851         checkPrev( cursor, 7L, "7", true, true );
852 
853         // Start after the last key
854         cursor = btree.browseFrom( 10L );
855         assertTrue( cursor.hasPrev() );
856         assertFalse( cursor.hasNext() );
857 
858         checkPrev( cursor, 9L, "9", false, true );
859         checkPrev( cursor, 7L, "7", true, true );
860 
861         // Start in the middle with a non existent key
862         cursor = btree.browseFrom( 4L );
863         assertTrue( cursor.hasPrev() );
864         assertTrue( cursor.hasNext() );
865 
866         checkNext( cursor, 5L, "5", true, true );
867 
868         // Start in the middle with a non existent key
869         cursor = btree.browseFrom( 4L );
870 
871         checkPrev( cursor, 3L, "3", true, true );
872     }
873     
874     
875     /**
876      * Test the browseFrom method on a btree containing nodes with duplicate values
877      */
878     @Test
879     public void testBrowseFromBTreeNodesPrevDupsN() throws IOException, BTreeAlreadyManagedException
880     {
881         // Inject some data
882         for ( long i = 1; i < 1000L; i += 2 )
883         {
884             for ( int j = 1; j < 10; j++ )
885             {
886                 btree.insert( i, Long.toString( j ) );
887             }
888         }
889 
890         // Create the cursor
891         TupleCursor<Long, String> cursor = btree.browseFrom( 500L );
892         
893         // Move forward
894         
895         assertTrue( cursor.hasPrev() );
896         assertTrue( cursor.hasNext() );
897         boolean next = true;
898         boolean prev = true;
899         
900         for ( long i = 501L; i < 1000L; i += 2 )
901         {
902             for ( long j = 1L; j < 10L; j++ )
903             {
904                 if ( ( i == 999L ) && ( j == 9L ) )
905                 {
906                     next = false;
907                 }
908 
909                 checkNext( cursor, i, Long.toString( j ), next, prev );
910             }
911         }
912     }
913     
914     
915     //----------------------------------------------------------------------------------------
916     // The TupleCursor.moveToNext/PrevNonDuplicateKey method tests
917     //----------------------------------------------------------------------------------------
918    /**
919      * Test the TupleCursor.nextKey method on a btree containing nodes 
920      * with duplicate values.
921      */
922     @Test
923     public void testNextKey() throws IOException, BTreeAlreadyManagedException
924     {
925         // Inject some data
926         for ( long i = 1; i < 1000L; i++ )
927         {
928             for ( long j = 1; j < 10; j++ )
929             {
930                 btree.insert( i, Long.toString( j ) );
931             }
932         }
933 
934         // Create the cursor
935         TupleCursor<Long, String> cursor = btree.browse();
936         
937         // Move forward
938         cursor.beforeFirst();
939         
940         assertFalse( cursor.hasPrev() );
941         assertTrue( cursor.hasNext() );
942         boolean next = true;
943         boolean prev = false;
944         
945         for ( long i = 1L; i < 999L; i++ )
946         {
947             Tuple<Long, String> tuple = cursor.nextKey();
948             
949             checkTuple( tuple, i, "1" );
950 
951             if ( i == 999L ) 
952             {
953                 next = false;
954             }
955 
956             assertEquals( next, cursor.hasNext() );
957             assertEquals( prev, cursor.hasPrev() );
958             
959             if ( i == 1L )
960             {
961                 prev = true;
962             }
963        }
964     }
965     
966     
967     /**
968      * Test the TupleCursor.moveToPrevNonDuplicateKey method on a btree containing nodes 
969      * with duplicate values.
970      */
971     @Test
972     public void testPrevKey() throws IOException, BTreeAlreadyManagedException
973     {
974         // Inject some data
975         for ( long i = 1; i < 1000L; i++ )
976         {
977             for ( long j = 1; j < 10; j++ )
978             {
979                 btree.insert( i, Long.toString( j ) );
980             }
981         }
982 
983         // Create the cursor
984         TupleCursor<Long, String> cursor = btree.browse();
985         
986         // Move backward
987         cursor.afterLast();
988         
989         assertTrue( cursor.hasPrev() );
990         assertFalse( cursor.hasNext() );
991         boolean next = true;
992         boolean prev = true;
993         
994         for ( long i = 999L; i > 0L; i-- )
995         {
996             Tuple<Long, String> tuple = cursor.prevKey();
997             
998             if ( i == 1L ) 
999             {
1000                 prev = false;
1001             }
1002 
1003             checkTuple( tuple, i, "1" );
1004             assertEquals( next, cursor.hasNext() );
1005             assertEquals( prev, cursor.hasPrev() );
1006 
1007             if ( i == 999L )
1008             {
1009                 next = true;
1010             }
1011        }
1012     }
1013 }