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