static < E > int getMovedPosition ( E [ ] d , int del ) { int j = del ; for ( ; ; ) { if ( ++ j == d . length ) j = 0 ; // invariant: interval ]del, j] contains only non-null elements // whose index is in ]del, j] E test = d [ j ] ; if ( test == null ) return j ; int k = getIndex ( test , d . length ) ; // check if k is in ]del, j] (this interval can wrap over) if ( ( del < j ) ? ( del < k ) && ( k <= j ) : ( del < k ) || ( k <= j ) ) // the test element should not be shifted continue ; // else it should be shifted return j ; } }
Finds the position of the next element starting from the given position that would not be found by linear probing if the element at the given position are deleted . This should be the element whose index is smaller than this position .