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;
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   * A Cursor is used to fetch elements in a BTree and is returned by the
31   * @see BTree#browse method. The cursor <strng>must</strong> be closed
32   * when the user is done with it.
33   * <p>
34   *
35   * @param <K> The type for the Key
36   * @param <V> The type for the stored value
37   *
38   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
39   */
40  public class TupleCursor<K, V>
41  {
42      /** A marker to tell that we are before the first element */
43      private static final int BEFORE_FIRST = -1;
44  
45      /** A marker to tell that we are after the last element */
46      private static final int AFTER_LAST = -2;
47  
48      /** The stack of pages from the root down to the leaf */
49      protected ParentPos<K, V>[] stack;
50  
51      /** The stack's depth */
52      protected int depth = 0;
53  
54      /** The transaction used for this cursor */
55      protected ReadTransaction<K, V> transaction;
56  
57  
58      /**
59       * Creates a new instance of Cursor.
60       */
61      protected TupleCursor()
62      {
63      }
64  
65  
66      /**
67       * Creates a new instance of Cursor, starting on a page at a given position.
68       *
69       * @param transaction The transaction this operation is protected by
70       * @param stack The stack of parent's from root to this page
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       * Change the position in the current cursor to set it after the last key
82       */
83      public void afterLast() throws IOException
84      {
85          // First check that we have elements in the BTree
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                 // We have N+1 children if the page is a Node, so we don't decrement the nbElems field
105                 parentPos.pos = parentPos.page.getNbElems();
106             }
107 
108             child = ( ( AbstractPage<K, V> ) parentPos.page ).getPage( parentPos.pos );
109         }
110 
111         // and leaf
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      * Change the position in the current cursor before the first key
132      */
133     public void beforeFirst() throws IOException
134     {
135         // First check that we have elements in the BTree
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         // and leaf
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      * Tells if the cursor can return a next element
175      *
176      * @return true if there are some more elements
177      * @throws IOException
178      * @throws EndOfFileExceededException
179      */
180     public boolean hasNext() throws EndOfFileExceededException, IOException
181     {
182         // First check that we have elements in the BTree
183         if ( ( stack == null ) || ( stack.length == 0 ) )
184         {
185             return false;
186         }
187 
188         // Take the leaf and check if we have no mare values
189         ParentPos<K, V> parentPos = stack[depth];
190 
191         if ( parentPos.page == null )
192         {
193             // Empty BTree, get out
194             return false;
195         }
196 
197         if ( parentPos.pos == AFTER_LAST )
198         {
199             // Ok, here, we have reached the last value in the leaf. We have to go up and
200             // see if we have some remaining values
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                     // The parent has some remaining values on the right, get out
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             // Not the last position, we have a next value
224             return true;
225         }
226         else
227         {
228             // Check if we have some more value
229             if ( ( parentPos.valueCursor != null ) && parentPos.valueCursor.hasNext() )
230             {
231                 // No problem, we still have some values to read
232                 return true;
233             }
234 
235             // Ok, here, we have reached the last value in the leaf. We have to go up and
236             // see if we have some remaining values
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                     // The parent has some remaining values on the right, get out
246                     return true;
247                 }
248                 else
249                 {
250                     currentDepth--;
251                 }
252             }
253 
254             // We are done, there are no more value left
255             return false;
256         }
257     }
258 
259 
260     /**
261      * Find the next key/value
262      *
263      * @return A Tuple containing the found key and value
264      * @throws IOException
265      * @throws EndOfFileExceededException
266      */
267     public Tuple<K, V> next() throws EndOfFileExceededException, IOException
268     {
269         // First check that we have elements in the BTree
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             // This is the end : no more value
280             throw new NoSuchElementException( "No more tuples present" );
281         }
282 
283         if ( parentPos.pos == parentPos.page.getNbElems() )
284         {
285             // End of the leaf. We have to go back into the stack up to the
286             // parent, and down to the leaf
287             parentPos = findNextParentPos();
288 
289             // we also need to check for the type of page cause
290             // findNextParentPos will never return a null ParentPos
291             if ( ( parentPos == null ) || ( parentPos.page == null ) )
292             {
293                 // This is the end : no more value
294                 throw new NoSuchElementException( "No more tuples present" );
295             }
296         }
297 
298         V value = null;
299 
300         if ( parentPos.valueCursor.hasNext() )
301         {
302             // Deal with the BeforeFirst case
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                     // This is the end : no more value
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      * Get the next non-duplicate key.
350      * If the BTree contains :
351      *
352      *  <ul>
353      *    <li><1,0></li>
354      *    <li><1,1></li>
355      *    <li><1,2></li>
356      *    <li><2,0></li>
357      *    <li><2,1></li>
358      *  </ul>
359      *
360      *  and cursor is present at <1,1> then the returned tuple will be <2,0> (not <1,2>)
361      *
362      * @return A Tuple containing the found key and value
363      * @throws EndOfFileExceededException
364      * @throws IOException
365      */
366     public Tuple<K, V> nextKey() throws EndOfFileExceededException, IOException
367     {
368         // First check that we have elements in the BTree
369         if ( ( stack == null ) || ( stack.length == 0 ) )
370         {
371             // This is the end : no more value
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             // This is the end : no more value
380             throw new NoSuchElementException( "No more tuples present" );
381         }
382 
383         if ( parentPos.pos == ( parentPos.page.getNbElems() - 1 ) )
384         {
385             // End of the leaf. We have to go back into the stack up to the
386             // parent, and down to the next leaf
387             ParentPos<K, V> newParentPos = findNextParentPos();
388 
389             // we also need to check the result of the call to
390             // findNextParentPos as it will return a null ParentPos
391             if ( ( newParentPos == null ) || ( newParentPos.page == null ) )
392             {
393                 // This is the end : no more value
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             // Get the next key
410             parentPos.pos++;
411         }
412 
413         // The key
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         // The value
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      * Tells if the cursor can return a next key
430      *
431      * @return true if there are some more keys
432      * @throws IOException
433      * @throws EndOfFileExceededException
434      */
435     public boolean hasNextKey() throws EndOfFileExceededException, IOException
436     {
437         // First check that we have elements in the BTree
438         if ( ( stack == null ) || ( stack.length == 0 ) )
439         {
440             // This is the end : no more key
441             return false;
442         }
443 
444         ParentPos<K, V> parentPos = stack[depth];
445 
446         if ( parentPos.page == null )
447         {
448             // This is the end : no more key
449             return false;
450         }
451 
452         if ( parentPos.pos == ( parentPos.page.getNbElems() - 1 ) )
453         {
454             // End of the leaf. We have to go back into the stack up to the
455             // parent, and down to the next leaf
456             return hasNextParentPos();
457         }
458         else
459         {
460             return true;
461         }
462     }
463 
464 
465     /**
466      * Tells if the cursor can return a previous element
467      *
468      * @return true if there are some more elements
469      * @throws IOException
470      * @throws EndOfFileExceededException
471      */
472     public boolean hasPrev() throws EndOfFileExceededException, IOException
473     {
474         // First check that we have elements in the BTree
475         if ( ( stack == null ) || ( stack.length == 0 ) )
476         {
477             return false;
478         }
479 
480         // Take the leaf and check if we have no mare values
481         ParentPos<K, V> parentPos = stack[depth];
482 
483         if ( parentPos.page == null )
484         {
485             // Empty BTree, get out
486             return false;
487         }
488 
489         if ( parentPos.pos > 0 )
490         {
491             // get out, we have values on the left
492             return true;
493         }
494         else
495         {
496             // Check that we are not before the first value
497             if ( parentPos.pos == BEFORE_FIRST )
498             {
499                 return false;
500             }
501 
502             // Check if we have some more value
503             if ( parentPos.valueCursor.hasPrev() )
504             {
505                 return true;
506             }
507 
508             // Ok, here, we have reached the first value in the leaf. We have to go up and
509             // see if we have some remaining values
510             int currentDepth = depth - 1;
511 
512             while ( currentDepth >= 0 )
513             {
514                 parentPos = stack[currentDepth];
515 
516                 if ( parentPos.pos > 0 )
517                 {
518                     // The parent has some remaining values on the right, get out
519                     return true;
520                 }
521                 else
522                 {
523                     currentDepth--;
524                 }
525             }
526 
527             return false;
528         }
529     }
530 
531 
532     /**
533      * Find the previous key/value
534      *
535      * @return A Tuple containing the found key and value
536      * @throws IOException
537      * @throws EndOfFileExceededException
538      */
539     public Tuple<K, V> prev() throws EndOfFileExceededException, IOException
540     {
541         // First check that we have elements in the BTree
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             // This is the end : no more value
552             throw new NoSuchElementException( "No more tuples present" );
553         }
554 
555         if ( ( parentPos.pos == 0 ) && ( !parentPos.valueCursor.hasPrev() ) )
556         {
557             // End of the leaf. We have to go back into the stack up to the
558             // parent, and down to the leaf
559             parentPos = findPrevParentPos();
560 
561             // we also need to check for the type of page cause
562             // findPrevParentPos will never return a null ParentPos
563             if ( ( parentPos == null ) || ( parentPos.page == null ) )
564             {
565                 // This is the end : no more value
566                 throw new NoSuchElementException( "No more tuples present" );
567             }
568         }
569 
570         V value = null;
571 
572         if ( parentPos.valueCursor.hasPrev() )
573         {
574             // Deal with the AfterLast case
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                     // This is the end : no more value
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      * Get the previous non-duplicate key.
623      * If the BTree contains :
624      *
625      *  <ul>
626      *    <li><1,0></li>
627      *    <li><1,1></li>
628      *    <li><1,2></li>
629      *    <li><2,0></li>
630      *    <li><2,1></li>
631      *  </ul>
632      *
633      *  and cursor is present at <2,1> then the returned tuple will be <1,0> (not <2,0>)
634      *
635      * @return A Tuple containing the found key and value
636      * @throws EndOfFileExceededException
637      * @throws IOException
638      */
639     public Tuple<K, V> prevKey() throws EndOfFileExceededException, IOException
640     {
641         // First check that we have elements in the BTree
642         if ( ( stack == null ) || ( stack.length == 0 ) )
643         {
644             // This is the end : no more value
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             // This is the end : no more value
653             throw new NoSuchElementException( "No more tuples present" );
654         }
655 
656         if ( parentPos.pos == 0 )
657         {
658             // Beginning of the leaf. We have to go back into the stack up to the
659             // parent, and down to the leaf
660             parentPos = findPrevParentPos();
661 
662             if ( ( parentPos == null ) || ( parentPos.page == null ) )
663             {
664                 // This is the end : no more value
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         // Update the Tuple
681         AbstractPage<K, V> leaf = ( AbstractPage<K, V> ) ( parentPos.page );
682 
683         // The key
684         Tuple<K, V> tuple = new Tuple<K, V>();
685         tuple.setKey( leaf.getKey( parentPos.pos ) );
686 
687         // The value
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      * Tells if the cursor can return a previous key
699      *
700      * @return true if there are some more keys
701      * @throws IOException
702      * @throws EndOfFileExceededException
703      */
704     public boolean hasPrevKey() throws EndOfFileExceededException, IOException
705     {
706         // First check that we have elements in the BTree
707         if ( ( stack == null ) || ( stack.length == 0 ) )
708         {
709             // This is the end : no more key
710             return false;
711         }
712 
713         ParentPos<K, V> parentPos = stack[depth];
714 
715         if ( parentPos.page == null )
716         {
717             // This is the end : no more key
718             return false;
719         }
720 
721         switch ( parentPos.pos )
722         {
723             case 0:
724                 // Beginning of the leaf. We have to go back into the stack up to the
725                 // parent, and down to the leaf
726                 return hasPrevParentPos();
727 
728             case -1:
729                 // no previous key
730                 return false;
731 
732             default:
733                 // we have a previous key
734                 return true;
735         }
736     }
737 
738 
739     /**
740      * Tells if there is a next ParentPos
741      *
742      * @return the new ParentPos instance, or null if we have no following leaf
743      * @throws IOException
744      * @throws EndOfFileExceededException
745      */
746     private boolean hasNextParentPos() throws EndOfFileExceededException, IOException
747     {
748         if ( depth == 0 )
749         {
750             // No need to go any further, there is only one leaf in the btree
751             return false;
752         }
753 
754         int currentDepth = depth - 1;
755         Page<K, V> child = null;
756 
757         // First, go up the tree until we find a Node which has some element on the right
758         while ( currentDepth >= 0 )
759         {
760             // We first go up the tree, until we reach a page whose current position
761             // is not the last one
762             ParentPos<K, V> parentPos = stack[currentDepth];
763 
764             if ( parentPos.pos + 1 > parentPos.page.getNbElems() )
765             {
766                 // No more element on the right : go up
767                 currentDepth--;
768             }
769             else
770             {
771                 // We can pick the next element at this level
772                 child = ( ( AbstractPage<K, V> ) parentPos.page ).getPage( parentPos.pos + 1 );
773 
774                 // and go down the tree through the nodes
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      * Find the leaf containing the following elements.
791      *
792      * @return the new ParentPos instance, or null if we have no following leaf
793      * @throws IOException
794      * @throws EndOfFileExceededException
795      */
796     private ParentPos<K, V> findNextParentPos() throws EndOfFileExceededException, IOException
797     {
798         if ( depth == 0 )
799         {
800             // No need to go any further, there is only one leaf in the btree
801             return null;
802         }
803 
804         int currentDepth = depth - 1;
805         Page<K, V> child = null;
806 
807         // First, go up the tree until we find a Node which has some element on the right
808         while ( currentDepth >= 0 )
809         {
810             // We first go up the tree, until we reach a page whose current position
811             // is not the last one
812             ParentPos<K, V> parentPos = stack[currentDepth];
813 
814             if ( parentPos.pos + 1 > parentPos.page.getNbElems() )
815             {
816                 // No more element on the right : go up
817                 currentDepth--;
818             }
819             else
820             {
821                 // We can pick the next element at this level
822                 parentPos.pos++;
823                 child = ( ( AbstractPage<K, V> ) parentPos.page ).getPage( parentPos.pos );
824 
825                 // and go down the tree through the nodes
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                 // and the leaf
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      * Find the leaf containing the previous elements.
851      *
852      * @return the new ParentPos instance, or null if we have no previous leaf
853      * @throws IOException
854      * @throws EndOfFileExceededException
855      */
856     private ParentPos<K, V> findPrevParentPos() throws EndOfFileExceededException, IOException
857     {
858         if ( depth == 0 )
859         {
860             // No need to go any further, there is only one leaf in the btree
861             return null;
862         }
863 
864         int currentDepth = depth - 1;
865         Page<K, V> child = null;
866 
867         // First, go up the tree until we find a Node which has some element on the left
868         while ( currentDepth >= 0 )
869         {
870             // We first go up the tree, until we reach a page whose current position
871             // is not the last one
872             ParentPos<K, V> parentPos = stack[currentDepth];
873 
874             if ( parentPos.pos == 0 )
875             {
876                 // No more element on the right : go up
877                 currentDepth--;
878             }
879             else
880             {
881                 // We can pick the next element at this level
882                 parentPos.pos--;
883                 child = ( ( AbstractPage<K, V> ) parentPos.page ).getPage( parentPos.pos );
884 
885                 // and go down the tree through the nodes
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                 // and the leaf
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      * Tells if there is a prev ParentPos
913      *
914      * @return the new ParentPos instance, or null if we have no previous leaf
915      * @throws IOException
916      * @throws EndOfFileExceededException
917      */
918     private boolean hasPrevParentPos() throws EndOfFileExceededException, IOException
919     {
920         if ( depth == 0 )
921         {
922             // No need to go any further, there is only one leaf in the btree
923             return false;
924         }
925 
926         int currentDepth = depth - 1;
927         Page<K, V> child = null;
928 
929         // First, go up the tree until we find a Node which has some element on the right
930         while ( currentDepth >= 0 )
931         {
932             // We first go up the tree, until we reach a page whose current position
933             // is not the last one
934             ParentPos<K, V> parentPos = stack[currentDepth];
935 
936             if ( parentPos.pos == 0 )
937             {
938                 // No more element on the left : go up
939                 currentDepth--;
940             }
941             else
942             {
943                 // We can pick the previous element at this level
944                 child = ( ( AbstractPage<K, V> ) parentPos.page ).getPage( parentPos.pos - 1 );
945 
946                 // and go down the tree through the nodes
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      * {@inheritDoc}
963      */
964     public void close()
965     {
966         transaction.close();
967     }
968 
969 
970     /**
971      * Get the creation date
972      * @return The creation date for this cursor
973      */
974     public long getCreationDate()
975     {
976         return transaction.getCreationDate();
977     }
978 
979 
980     /**
981      * Get the current revision
982      *
983      * @return The revision this cursor is based on
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 }