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