1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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
48
49
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
65
66 @Before
67 public void createBTree()
68 {
69 dataDir = tempFolder.newFolder( UUID.randomUUID().toString() );
70
71 openRecordManagerAndBtree();
72
73 try
74 {
75
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
87
88 private void openRecordManagerAndBtree()
89 {
90 try
91 {
92 if ( recordManager1 != null )
93 {
94 recordManager1.close();
95 }
96
97
98 recordManager1 = new RecordManager( dataDir.getAbsolutePath() );
99
100
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
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
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
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
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
177
178
179
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
197 }
198
199 try
200 {
201 cursor.prev();
202 fail();
203 }
204 catch ( NoSuchElementException nsee )
205 {
206
207 }
208
209 assertEquals( -1L, cursor.getRevision() );
210 }
211
212
213
214
215
216 @Test
217 public void testBrowseBTreeLeafNext() throws IOException, BTreeAlreadyManagedException
218 {
219
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
227 TupleCursor<Long, String> cursor = btree.browse();
228
229
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
245
246 @Test
247 public void testBrowseBTreeLeafPrev() throws IOException, BTreeAlreadyManagedException
248 {
249
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
257 TupleCursor<Long, String> cursor = btree.browse();
258
259
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
272
273
274 @Test
275 public void testBrowseBTreeLeafFirstLast() throws IOException, BTreeAlreadyManagedException
276 {
277
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
285 TupleCursor<Long, String> cursor = btree.browse();
286
287
288 try
289 {
290 cursor.prev();
291 fail();
292 }
293 catch ( NoSuchElementException nsee )
294 {
295
296 }
297
298
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
306 assertTrue( cursor.hasPrev() );
307 assertTrue( cursor.hasNext() );
308 assertEquals( 3L, (long)tuple.getKey() );
309 assertEquals( "3", tuple.getValue() );
310
311
312 cursor.afterLast();
313
314 assertTrue( cursor.hasPrev() );
315 assertFalse( cursor.hasNext() );
316
317
318 try
319 {
320 cursor.next();
321 fail();
322 }
323 catch ( NoSuchElementException nsee )
324 {
325
326 }
327
328
329
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
338 cursor.beforeFirst();
339
340 assertFalse( cursor.hasPrev() );
341 assertTrue( cursor.hasNext() );
342
343
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
355
356
357 @Test
358 public void testBrowseBTreeLeafNextPrev() throws IOException, BTreeAlreadyManagedException
359 {
360
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
368 TupleCursor<Long, String> cursor = btree.browse();
369
370
371 try
372 {
373 cursor.prev();
374 fail();
375 }
376 catch ( NoSuchElementException nsee )
377 {
378
379 }
380
381
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
389 assertTrue( cursor.hasPrev() );
390 assertTrue( cursor.hasNext() );
391 assertEquals( 3L, (long)tuple.getKey() );
392 assertEquals( "3", tuple.getValue() );
393
394
395 cursor.prev();
396 assertEquals( 2L, (long)tuple.getKey() );
397 assertEquals( "2", tuple.getValue() );
398
399
400 cursor.next();
401 assertEquals( 3L, (long)tuple.getKey() );
402 assertEquals( "3", tuple.getValue() );
403 }
404
405
406
407
408
409 @Test
410 public void testBrowseBTreeNodesNext() throws IOException, BTreeAlreadyManagedException
411 {
412
413 for ( long i = 1; i < 1000L; i++ )
414 {
415 btree.insert( i, Long.toString( i ) );
416 }
417
418
419 TupleCursor<Long, String> cursor = btree.browse();
420
421
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
440
441 @Test
442 public void testBrowseBTreeNodesPrev() throws IOException, BTreeAlreadyManagedException
443 {
444
445 for ( long i = 1; i < 1000L; i++ )
446 {
447 btree.insert( i, Long.toString( i ) );
448 }
449
450
451 TupleCursor<Long, String> cursor = btree.browse();
452
453
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
472
473 @Test
474 public void testBrowseBTreeLeafNextDups1() throws IOException, BTreeAlreadyManagedException
475 {
476
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
484 TupleCursor<Long, String> cursor = btree.browse();
485
486
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
502
503 @Test
504 public void testBrowseBTreeLeafNextDupsN() throws IOException, BTreeAlreadyManagedException
505 {
506
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
516 TupleCursor<Long, String> cursor = btree.browse();
517
518
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
536
537 @Test
538 public void testBrowseBTreeLeafPrevDups1() throws IOException, BTreeAlreadyManagedException
539 {
540
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
548 TupleCursor<Long, String> cursor = btree.browse();
549
550
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
566
567 @Test
568 public void testBrowseBTreeLeafPrevDupsN() throws IOException, BTreeAlreadyManagedException
569 {
570
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
580 TupleCursor<Long, String> cursor = btree.browse();
581
582
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
600
601 @Test
602 public void testBrowseBTreeNodesNextDupsN() throws IOException, BTreeAlreadyManagedException
603 {
604
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
614 TupleCursor<Long, String> cursor = btree.browse();
615
616
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
646
647 @Test
648 public void testBrowseBTreeNodesPrevDupsN() throws IOException, BTreeAlreadyManagedException
649 {
650
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
660 TupleCursor<Long, String> cursor = btree.browse();
661
662
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
692
693
694 @Test
695 public void testBrowseBTreeLeafNextDupsSubBTree1() throws IOException, BTreeAlreadyManagedException
696 {
697
698 for ( long i = 1L; i < 32L; i++ )
699 {
700 btree.insert( 1L, toString( i, 2 ) );
701 }
702
703
704 TupleCursor<Long, String> cursor = btree.browse();
705
706
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
724
725 @Test
726 public void testBrowseBTreeLeafPrevDupsSubBTree1() throws IOException, BTreeAlreadyManagedException
727 {
728
729 for ( long i = 1L; i < 32L; i++ )
730 {
731 btree.insert( 1L, toString( i, 2 ) );
732 }
733
734
735 TupleCursor<Long, String> cursor = btree.browse();
736
737
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
756
757
758
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
776 }
777
778 try
779 {
780 cursor.prev();
781 fail();
782 }
783 catch ( NoSuchElementException nsee )
784 {
785
786 }
787
788 assertEquals( -1L, cursor.getRevision() );
789 }
790
791
792
793
794
795 @Test
796 public void testBrowseFromBTreeLeaf() throws IOException, BTreeAlreadyManagedException
797 {
798
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
806 TupleCursor<Long, String> cursor = btree.browseFrom( 5L );
807
808 assertTrue( cursor.hasPrev() );
809 assertTrue( cursor.hasNext() );
810
811
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
819 cursor = btree.browseFrom( 5L );
820
821 assertTrue( cursor.hasPrev() );
822 assertTrue( cursor.hasNext() );
823
824
825 checkPrev( cursor, 3L, "3", true, true );
826 checkPrev( cursor, 1L, "1", true, false );
827 cursor.close();
828
829
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
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
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
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
862 cursor = btree.browseFrom( 4L );
863 assertTrue( cursor.hasPrev() );
864 assertTrue( cursor.hasNext() );
865
866 checkNext( cursor, 5L, "5", true, true );
867
868
869 cursor = btree.browseFrom( 4L );
870
871 checkPrev( cursor, 3L, "3", true, true );
872 }
873
874
875
876
877
878 @Test
879 public void testBrowseFromBTreeNodesPrevDupsN() throws IOException, BTreeAlreadyManagedException
880 {
881
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
891 TupleCursor<Long, String> cursor = btree.browseFrom( 500L );
892
893
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
917
918
919
920
921
922 @Test
923 public void testNextKey() throws IOException, BTreeAlreadyManagedException
924 {
925
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
935 TupleCursor<Long, String> cursor = btree.browse();
936
937
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
969
970
971 @Test
972 public void testPrevKey() throws IOException, BTreeAlreadyManagedException
973 {
974
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
984 TupleCursor<Long, String> cursor = btree.browse();
985
986
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 }