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