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.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   * A Cursor is used to fetch elements in a BTree and is returned by the
36   * @see BTree#browse method. The cursor <strng>must</strong> be closed
37   * when the user is done with it.
38   * <p>
39   *
40   * @param <K> The type for the Key
41   * @param <V> The type for the stored value
42   * 
43   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
44   */
45  public class TupleCursorImpl<K, V> implements TupleCursor<K, V>
46  {
47      /** The transaction used for this cursor */
48      private Transaction<K, V> transaction;
49  
50      /** The Tuple used to return the results */
51      private Tuple<K, V> tuple = new Tuple<K, V>();
52  
53      /** The stack of pages from the root down to the leaf */
54      private ParentPos<K, V>[] stack;
55      
56      /** The stack's depth */
57      private int depth = 0;
58  
59      private boolean allowDuplicates;
60  
61  
62      /**
63       * Creates a new instance of Cursor, starting on a page at a given position.
64       * 
65       * @param transaction The transaction this operation is protected by
66       * @param stack The stack of parent's from root to this page
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       * Closes the cursor, thus releases the associated transaction
79       */
80      public void close()
81      {
82          transaction.close();
83      }
84  
85  
86      /**
87       * {@inheritDoc}
88       */
89      public long getRevision()
90      {
91          return transaction.getRevision();
92      }
93  
94  
95      /**
96       * {@inheritDoc}
97       */
98      public long getCreationDate()
99      {
100         return transaction.getCreationDate();
101     }
102     
103     
104     /**
105      * {@inheritDoc}
106      */
107     public void afterLast() throws IOException
108     {
109         // First check that we have elements in the BTree
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                 // We have N+1 children if the page is a Node, so we don't decrement the nbElems field
129                 parentPos.pos = ((Node<K, V>)parentPos.page).nbElems;
130             }
131 
132             child = ((Node<K, V>)parentPos.page).children[parentPos.pos];
133         }
134         
135         // and leaf
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      * {@inheritDoc}
156      */
157     public void beforeFirst() throws IOException
158     {
159         // First check that we have elements in the BTree
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         // and leaf
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      * Find the leaf containing the following elements.
199      * 
200      * @return the new ParentPos instance, or null if we have no following leaf
201      * @throws IOException 
202      * @throws EndOfFileExceededException 
203      */
204     private ParentPos<K, V> findNextParentPos() throws EndOfFileExceededException, IOException
205     {
206         if ( depth == 0 )
207         {
208             // No need to go any further, there is only one leaf in the btree
209             return null;
210         }
211 
212         int currentDepth = depth - 1;
213         Page<K, V> child = null;
214 
215         // First, go up the tree until we find a Node which has some element on the right
216         while ( currentDepth >= 0 )
217         {
218             // We first go up the tree, until we reach a page whose current position
219             // is not the last one
220             ParentPos<K, V> parentPos = stack[currentDepth];
221 
222             if ( parentPos.pos + 1 > parentPos.page.getNbElems() )
223             {
224                 // No more element on the right : go up
225                 currentDepth--;
226             }
227             else
228             {
229                 // We can pick the next element at this level
230                 parentPos.pos++;
231                 child = ((Node<K, V>)parentPos.page).children[parentPos.pos];
232                 
233                 // and go down the tree through the nodes
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                 // and the leaf
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      * Find the leaf containing the previous elements.
259      * 
260      * @return the new ParentPos instance, or null if we have no previous leaf
261      * @throws IOException 
262      * @throws EndOfFileExceededException 
263      */
264     private ParentPos<K, V> findPrevParentPos() throws EndOfFileExceededException, IOException
265     {
266         if ( depth == 0 )
267         {
268             // No need to go any further, there is only one leaf in the btree
269             return null;
270         }
271 
272         int currentDepth = depth - 1;
273         Page<K, V> child = null;
274 
275         // First, go up the tree until we find a Node which has some element on the left
276         while ( currentDepth >= 0 )
277         {
278             // We first go up the tree, until we reach a page whose current position
279             // is not the last one
280             ParentPos<K, V> parentPos = stack[currentDepth];
281 
282             if ( parentPos.pos == 0 )
283             {
284                 // No more element on the right : go up
285                 currentDepth--;
286             }
287             else
288             {
289                 // We can pick the next element at this level
290                 parentPos.pos--;
291                 child = ((Node<K, V>)parentPos.page).children[parentPos.pos];
292                 
293                 // and go down the tree through the nodes
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                 // and the leaf
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      * {@inheritDoc} 
321      */
322     public boolean hasNext() throws EndOfFileExceededException, IOException
323     {
324         // First check that we have elements in the BTree
325         if ( ( stack == null ) || ( stack.length == 0 ) )
326         {
327             return false;
328         }
329         
330         // Take the leaf and check if we have no mare values
331         ParentPos<K, V> parentPos = stack[depth];
332 
333         if ( parentPos.page == null )
334         {
335             // Empty BTree, get out
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             // Not the last position, we have a next value
347             return true;
348         }
349         else
350         {
351             // Check if we have some more value
352             if ( parentPos.valueCursor.hasNext() )
353             {
354                 return true;
355             }
356             
357             // Ok, here, we have reached the last value in the leaf. We have to go up and 
358             // see if we have some remaining values
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                     // The parent has some remaining values on the right, get out
368                     return true;
369                 }
370                 else
371                 {
372                     currentDepth --;
373                 }
374             }
375             
376             // We are done, there are no more value left
377             return false;
378         }
379     }
380 
381 
382     /**
383      * {@inheritDoc}
384      */
385     public boolean hasNextKey() throws EndOfFileExceededException, IOException
386     {
387         // First check that we have elements in the BTree
388         if ( ( stack == null ) || ( stack.length == 0 ) )
389         {
390             // This is the end : no more key
391             return false;
392         }
393 
394         ParentPos<K, V> parentPos = stack[depth];
395 
396         if ( parentPos.page == null )
397         {
398             // This is the end : no more key
399             return false;
400         }
401         
402         if ( parentPos.pos == ( parentPos.page.getNbElems() - 1 ) )
403         {
404             // End of the leaf. We have to go back into the stack up to the
405             // parent, and down to the next leaf
406             return hasNextParentPos();
407         }
408         else
409         {
410             return true;
411         }
412     }
413 
414 
415     /**
416      * Tells if there is a next ParentPos
417      * 
418      * @return the new ParentPos instance, or null if we have no following leaf
419      * @throws IOException 
420      * @throws EndOfFileExceededException 
421      */
422     private boolean hasNextParentPos() throws EndOfFileExceededException, IOException
423     {
424         if ( depth == 0 )
425         {
426             // No need to go any further, there is only one leaf in the btree
427             return false;
428         }
429 
430         int currentDepth = depth - 1;
431         Page<K, V> child = null;
432 
433         // First, go up the tree until we find a Node which has some element on the right
434         while ( currentDepth >= 0 )
435         {
436             // We first go up the tree, until we reach a page whose current position
437             // is not the last one
438             ParentPos<K, V> parentPos = stack[currentDepth];
439 
440             if ( parentPos.pos + 1 > parentPos.page.getNbElems() )
441             {
442                 // No more element on the right : go up
443                 currentDepth--;
444             }
445             else
446             {
447                 // We can pick the next element at this level
448                 child = ((Node<K, V>)parentPos.page).children[parentPos.pos + 1];
449                 
450                 // and go down the tree through the nodes
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      * {@inheritDoc} 
467      */
468     public boolean hasPrev() throws EndOfFileExceededException, IOException
469     {
470         // First check that we have elements in the BTree
471         if ( ( stack == null ) || ( stack.length == 0 ) )
472         {
473             return false;
474         }
475 
476         // Take the leaf and check if we have no mare values
477         ParentPos<K, V> parentPos = stack[depth];
478 
479         if ( parentPos.page == null )
480         {
481             // Empty BTree, get out
482             return false;
483         }
484 
485         if ( parentPos.pos > 0 )
486         {
487             // get out, we have values on the left
488             return true;
489         }
490         else
491         {
492             // Check that we are not before the first value
493             if ( parentPos.pos == BEFORE_FIRST )
494             {
495                 return false;
496             }
497             
498             // Check if we have some more value
499             if ( parentPos.valueCursor.hasPrev() )
500             {
501                 return true;
502             }
503 
504             // Ok, here, we have reached the first value in the leaf. We have to go up and 
505             // see if we have some remaining values
506             int currentDepth = depth - 1;
507             
508             while ( currentDepth >= 0 )
509             {
510                 parentPos = stack[currentDepth];
511                 
512                 if ( parentPos.pos > 0 )
513                 {
514                     // The parent has some remaining values on the right, get out
515                     return true;
516                 }
517                 else
518                 {
519                     currentDepth --;
520                 }
521             }
522             
523             return false;
524         }
525     }
526 
527 
528     /**
529      * {@inheritDoc}
530      */
531     public boolean hasPrevKey() throws EndOfFileExceededException, IOException
532     {
533         // First check that we have elements in the BTree
534         if ( ( stack == null ) || ( stack.length == 0 ) )
535         {
536             // This is the end : no more key
537             return false;
538         }
539 
540         ParentPos<K, V> parentPos = stack[depth];
541 
542         if ( parentPos.page == null )
543         {
544             // This is the end : no more key
545             return false;
546         }
547         
548         if ( parentPos.pos == 0 )
549         {
550             // Beginning of the leaf. We have to go back into the stack up to the
551             // parent, and down to the leaf
552             return hasPrevParentPos();
553         }
554         else
555         {
556             return true;
557         }
558     }
559     
560     
561     /**
562      * Tells if there is a prev ParentPos
563      * 
564      * @return the new ParentPos instance, or null if we have no previous leaf
565      * @throws IOException 
566      * @throws EndOfFileExceededException 
567      */
568     private boolean hasPrevParentPos() throws EndOfFileExceededException, IOException
569     {
570         if ( depth == 0 )
571         {
572             // No need to go any further, there is only one leaf in the btree
573             return false;
574         }
575 
576         int currentDepth = depth - 1;
577         Page<K, V> child = null;
578 
579         // First, go up the tree until we find a Node which has some element on the right
580         while ( currentDepth >= 0 )
581         {
582             // We first go up the tree, until we reach a page whose current position
583             // is not the last one
584             ParentPos<K, V> parentPos = stack[currentDepth];
585 
586             if ( parentPos.pos == 0 )
587             {
588                 // No more element on the left : go up
589                 currentDepth--;
590             }
591             else
592             {
593                 // We can pick the previous element at this level
594                 child = ((Node<K, V>)parentPos.page).children[parentPos.pos - 1];
595                 
596                 // and go down the tree through the nodes
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      * {@inheritDoc}
613      */
614     public Tuple<K, V> next() throws EndOfFileExceededException, IOException
615     {
616         // First check that we have elements in the BTree
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             // This is the end : no more value
627             throw new NoSuchElementException( "No more tuples present" );
628         }
629 
630         if ( parentPos.pos == parentPos.page.getNbElems() )
631         {
632             // End of the leaf. We have to go back into the stack up to the
633             // parent, and down to the leaf
634             parentPos = findNextParentPos();
635 
636             // we also need to check for the type of page cause
637             // findNextParentPos will never return a null ParentPos
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 
645         V value = null;
646         
647         if ( parentPos.valueCursor.hasNext() )
648         {
649             // Deal with the BeforeFirst case
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                     // This is the end : no more value
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      * {@inheritDoc}
698      */
699     public Tuple<K, V> nextKey() throws EndOfFileExceededException, IOException
700     {
701         // First check that we have elements in the BTree
702         if ( ( stack == null ) || ( stack.length == 0 ) )
703         {
704             // This is the end : no more value
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             // This is the end : no more value
713             throw new NoSuchElementException( "No more tuples present" );
714         }
715 
716         if ( parentPos.pos == ( parentPos.page.getNbElems() - 1 ) )
717         {
718             // End of the leaf. We have to go back into the stack up to the
719             // parent, and down to the next leaf
720             ParentPos<K, V> newParentPos = findNextParentPos();
721 
722             // we also need to check the result of the call to
723             // findNextParentPos as it will return a null ParentPos
724             if ( ( newParentPos == null ) || ( newParentPos.page == null ) )
725             {
726                 // This is the end : no more value
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             // Get the next key
743             parentPos.pos++;
744         }
745 
746         // The key
747         Leaf<K, V> leaf = ( Leaf<K, V> ) ( parentPos.page );
748         tuple.setKey( leaf.keys[parentPos.pos] );
749         
750         // The value
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      * {@inheritDoc} 
762      */
763     public Tuple<K, V> prev() throws EndOfFileExceededException, IOException
764     {
765         // First check that we have elements in the BTree
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             // This is the end : no more value
776             throw new NoSuchElementException( "No more tuples present" );
777         }
778 
779         if ( ( parentPos.pos == 0 ) && ( !parentPos.valueCursor.hasPrev() ) )
780         {
781             // End of the leaf. We have to go back into the stack up to the
782             // parent, and down to the leaf
783             parentPos = findPrevParentPos();
784 
785             // we also need to check for the type of page cause
786             // findPrevParentPos will never return a null ParentPos
787             if ( ( parentPos == null ) || ( parentPos.page == null ) || ( parentPos.page instanceof Node ) )
788             {
789                 // This is the end : no more value
790                 throw new NoSuchElementException( "No more tuples present" );
791             }
792         }
793         
794         V value = null;
795         
796         if ( parentPos.valueCursor.hasPrev() )
797         {
798             // Deal with the AfterLast case
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                     // This is the end : no more value
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      * {@inheritDoc}
849      */
850     public Tuple<K, V> prevKey() throws EndOfFileExceededException, IOException
851     {
852         // First check that we have elements in the BTree
853         if ( ( stack == null ) || ( stack.length == 0 ) )
854         {
855             // This is the end : no more value
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             // This is the end : no more value
864             throw new NoSuchElementException( "No more tuples present" );
865         }
866 
867         if ( parentPos.pos == 0 )
868         {
869             // Beginning of the leaf. We have to go back into the stack up to the
870             // parent, and down to the leaf
871             parentPos = findPrevParentPos();
872 
873             if ( ( parentPos == null ) || ( parentPos.page == null ) )
874             {
875                 // This is the end : no more value
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         // Update the Tuple 
892         Leaf<K, V> leaf = ( Leaf<K, V> ) ( parentPos.page );
893 
894         // The key
895         tuple.setKey( leaf.keys[parentPos.pos] );
896 
897         // The value
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 }