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