1 /* 2 * This file is part of ELKI: 3 * Environment for Developing KDD-Applications Supported by Index-Structures 4 * 5 * Copyright (C) 2018 6 * ELKI Development Team 7 * 8 * This program is free software: you can redistribute it and/or modify 9 * it under the terms of the GNU Affero General Public License as published by 10 * the Free Software Foundation, either version 3 of the License, or 11 * (at your option) any later version. 12 * 13 * This program is distributed in the hope that it will be useful, 14 * but WITHOUT ANY WARRANTY; without even the implied warranty of 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 * GNU Affero General Public License for more details. 17 * 18 * You should have received a copy of the GNU Affero General Public License 19 * along with this program. If not, see <http://www.gnu.org/licenses/>. 20 */ 21 package de.lmu.ifi.dbs.elki.database.query.range; 22 23 import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; 24 import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; 25 import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; 26 import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDList; 27 import de.lmu.ifi.dbs.elki.database.ids.ModifiableDoubleDBIDList; 28 import de.lmu.ifi.dbs.elki.database.query.LinearScanQuery; 29 import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; 30 import de.lmu.ifi.dbs.elki.database.relation.Relation; 31 32 /** 33 * Default linear scan range query class. 34 * 35 * @author Erich Schubert 36 * @since 0.4.0 37 * 38 * @has - - - DistanceQuery 39 * 40 * @param <O> Database object type 41 */ 42 public class LinearScanDistanceRangeQuery<O> extends AbstractDistanceRangeQuery<O> implements LinearScanQuery { 43 /** 44 * Constructor. 45 * 46 * @param distanceQuery Distance function to use 47 */ LinearScanDistanceRangeQuery(DistanceQuery<O> distanceQuery)48 public LinearScanDistanceRangeQuery(DistanceQuery<O> distanceQuery) { 49 super(distanceQuery); 50 } 51 52 @Override getRangeForDBID(DBIDRef id, double range)53 public DoubleDBIDList getRangeForDBID(DBIDRef id, double range) { 54 final DistanceQuery<O> dq = distanceQuery; 55 ModifiableDoubleDBIDList result = DBIDUtil.newDistanceDBIDList(); 56 for(DBIDIter iter = getRelation().getDBIDs().iter(); iter.valid(); iter.advance()) { 57 final double currentDistance = dq.distance(id, iter); 58 if(currentDistance <= range) { 59 result.add(currentDistance, iter); 60 } 61 } 62 result.sort(); 63 return result; 64 } 65 66 @Override getRangeForObject(O obj, double range)67 public DoubleDBIDList getRangeForObject(O obj, double range) { 68 final DistanceQuery<O> dq = distanceQuery; 69 ModifiableDoubleDBIDList result = DBIDUtil.newDistanceDBIDList(); 70 for(DBIDIter iter = getRelation().getDBIDs().iter(); iter.valid(); iter.advance()) { 71 final double currentDistance = dq.distance(obj, iter); 72 if(currentDistance <= range) { 73 result.add(currentDistance, iter); 74 } 75 } 76 result.sort(); 77 return result; 78 } 79 80 @Override getRangeForDBID(DBIDRef id, double range, ModifiableDoubleDBIDList neighbors)81 public void getRangeForDBID(DBIDRef id, double range, ModifiableDoubleDBIDList neighbors) { 82 final DistanceQuery<O> dq = distanceQuery; 83 for(DBIDIter iter = getRelation().iterDBIDs(); iter.valid(); iter.advance()) { 84 final double currentDistance = dq.distance(id, iter); 85 if(currentDistance <= range) { 86 neighbors.add(currentDistance, iter); 87 } 88 } 89 } 90 91 @Override getRangeForObject(O obj, double range, ModifiableDoubleDBIDList neighbors)92 public void getRangeForObject(O obj, double range, ModifiableDoubleDBIDList neighbors) { 93 final Relation<? extends O> relation = getRelation(); 94 final DistanceQuery<O> dq = distanceQuery; 95 for(DBIDIter iter = relation.iterDBIDs(); iter.valid(); iter.advance()) { 96 final double currentDistance = dq.distance(obj, iter); 97 if(currentDistance <= range) { 98 neighbors.add(currentDistance, iter); 99 } 100 } 101 } 102 } 103