private void doRangeQuery ( DBID o_p , AbstractMTreeNode < O , ? , ? > node , O q , double r_q , ModifiableDoubleDBIDList result ) { double d1 = 0. ; if ( o_p != null ) { d1 = distanceQuery . distance ( o_p , q ) ; index . statistics . countDistanceCalculation ( ) ; } if ( ! node . isLeaf ( ) ) { for ( int i = 0 ; i < node . getNumEntries ( ) ; i ++ ) { MTreeEntry entry = node . getEntry ( i ) ; DBID o_r = entry . getRoutingObjectID ( ) ; double r_or = entry . getCoveringRadius ( ) ; double d2 = o_p != null ? entry . getParentDistance ( ) : 0. ; double diff = Math . abs ( d1 - d2 ) ; double sum = r_q + r_or ; if ( diff <= sum ) { double d3 = distanceQuery . distance ( o_r , q ) ; index . statistics . countDistanceCalculation ( ) ; if ( d3 <= sum ) { AbstractMTreeNode < O , ? , ? > child = index . getNode ( ( ( DirectoryEntry ) entry ) . getPageID ( ) ) ; doRangeQuery ( o_r , child , q , r_q , result ) ; } } } } else { for ( int i = 0 ; i < node . getNumEntries ( ) ; i ++ ) { MTreeEntry entry = node . getEntry ( i ) ; DBID o_j = entry . getRoutingObjectID ( ) ; double d2 = o_p != null ? entry . getParentDistance ( ) : 0. ; double diff = Math . abs ( d1 - d2 ) ; if ( diff <= r_q ) { double d3 = distanceQuery . distance ( o_j , q ) ; index . statistics . countDistanceCalculation ( ) ; if ( d3 <= r_q ) { result . add ( d3 , o_j ) ; } } } } }
Performs a range query on the specified subtree . It recursively traverses all paths from the specified node which cannot be excluded from leading to qualifying objects .