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