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