private void kdRangeSearch(int left,int right,int axis,O query,ModifiableDoubleDBIDList res,DBIDArrayIter iter,double radius){
  if (right - left <= leafsize) {
    for (iter.seek(left); iter.getOffset() < right; iter.advance()) {
      double dist=norm.distance(query,relation.get(iter));
      countObjectAccess();
      countDistanceComputation();
      if (dist <= radius) {
        res.add(dist,iter);
      }
    }
    return;
  }
  final int middle=(left + right) >>> 1;
  O split=relation.get(iter.seek(middle));
  countObjectAccess();
  final double delta=split.doubleValue(axis) - query.doubleValue(axis);
  final boolean onleft=(delta >= 0);
  final boolean onright=(delta <= 0);
  final boolean close=(Math.abs(delta) <= radius);
  final int next=(axis + 1) % dims;
  if (close) {
    double dist=norm.distance(query,split);
    countDistanceComputation();
    if (dist <= radius) {
      assert (iter.getOffset() == middle);
      res.add(dist,iter);
    }
  }
  if (left < middle && (onleft || close)) {
    kdRangeSearch(left,middle,next,query,res,iter,radius);
  }
  if (middle + 1 < right && (onright || close)) {
    kdRangeSearch(middle + 1,right,next,query,res,iter,radius);
  }
}

private void kdRangeSearch ( int left , int right , int axis , O query , ModifiableDoubleDBIDList res , DBIDArrayIter iter , double radius ) { if ( right - left <= leafsize ) { for ( iter . seek ( left ) ; iter . getOffset ( ) < right ; iter . advance ( ) ) { double dist = norm . distance ( query , relation . get ( iter ) ) ; countObjectAccess ( ) ; countDistanceComputation ( ) ; if ( dist <= radius ) { res . add ( dist , iter ) ; } } return ; } final int middle = ( left + right ) > > > 1 ; O split = relation . get ( iter . seek ( middle ) ) ; countObjectAccess ( ) ; final double delta = split . doubleValue ( axis ) - query . doubleValue ( axis ) ; final boolean onleft = ( delta >= 0 ) ; final boolean onright = ( delta <= 0 ) ; final boolean close = ( Math . abs ( delta ) <= radius ) ; final int next = ( axis + 1 ) % dims ; if ( close ) { double dist = norm . distance ( query , split ) ; countDistanceComputation ( ) ; if ( dist <= radius ) { assert ( iter . getOffset ( ) == middle ) ; res . add ( dist , iter ) ; } } if ( left < middle && ( onleft || close ) ) { kdRangeSearch ( left , middle , next , query , res , iter , radius ) ; } if ( middle + 1 < right && ( onright || close ) ) { kdRangeSearch ( middle + 1 , right , next , query , res , iter , radius ) ; } }
perform a knn search on the kd - tree .
