< V > void find ( Object [ ] node , Comparator < V > comparator , Object target , Op mode , boolean forwards ) { // TODO : should not require parameter 'forwards' - consider modifying index to represent both // child and key position, as opposed to just key position (which necessitates a different value depending // on which direction you're moving in. Prerequisite for making Path public and using to implement general // search depth = - 1 ; if ( target instanceof BTree . Special ) { if ( target == POSITIVE_INFINITY ) moveEnd ( node , forwards ) ; else if ( target == NEGATIVE_INFINITY ) moveStart ( node , forwards ) ; else throw new AssertionError ( ) ; return ; } while ( true ) { int keyEnd = getKeyEnd ( node ) ; // search for the target in the current node int i = BTree . find ( comparator , target , node , 0 , keyEnd ) ; if ( i >= 0 ) { // exact match. transform exclusive bounds into the correct index by moving back or forwards one push ( node , i ) ; switch ( mode ) { case HIGHER : successor ( ) ; break ; case LOWER : predecessor ( ) ; } return ; } i = - i - 1 ; // traverse into the appropriate child if ( ! isLeaf ( node ) ) { push ( node , forwards ? i - 1 : i ) ; node = ( Object [ ] ) node [ keyEnd + i ] ; continue ; } // bottom of the tree and still not found. pick the right index to satisfy Op switch ( mode ) { case FLOOR : case LOWER : i -- ; } if ( i < 0 ) { push ( node , 0 ) ; predecessor ( ) ; } else if ( i >= keyEnd ) { push ( node , keyEnd - 1 ) ; successor ( ) ; } else { push ( node , i ) ; } return ; } }
Find the provided key in the tree rooted at node and store the root to it in the path