void successor ( ) { Object [ ] node = currentNode ( ) ; int i = currentIndex ( ) ; if ( ! isLeaf ( node ) ) { // if we're on a key in a branch, we MUST have a descendant either side of us, // so we always go down the left-most child until we hit a leaf node = ( Object [ ] ) node [ getBranchKeyEnd ( node ) + i + 1 ] ; while ( ! isLeaf ( node ) ) { push ( node , - 1 ) ; node = ( Object [ ] ) node [ getBranchKeyEnd ( node ) ] ; } push ( node , 0 ) ; return ; } // if we haven't reached the end of this leaf, just increment our index and return i += 1 ; if ( i < getLeafKeyEnd ( node ) ) { // moved to the next key in the same leaf setIndex ( i ) ; return ; } // we've reached the end of this leaf, // so go up until we reach something we've not finished visiting while ( ! isRoot ( ) ) { pop ( ) ; i = currentIndex ( ) + 1 ; node = currentNode ( ) ; if ( i < getKeyEnd ( node ) ) { setIndex ( i ) ; return ; } } // we've visited the last key in the root node, so we're done setIndex ( getKeyEnd ( node ) ) ; }
move to the next key in the tree