diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/database/query')
32 files changed, 322 insertions, 148 deletions
diff --git a/src/de/lmu/ifi/dbs/elki/database/query/DistanceDBIDResult.java b/src/de/lmu/ifi/dbs/elki/database/query/DistanceDBIDResult.java new file mode 100644 index 00000000..ead3eebc --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/query/DistanceDBIDResult.java @@ -0,0 +1,41 @@ +package de.lmu.ifi.dbs.elki.database.query; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +import java.util.List; + +import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; + +/** + * Collection of objects and their distances. + * + * @author Erich Schubert + * + * @apiviz.composedOf DistanceResultPair + * + * @param <D> Distance type + */ +public interface DistanceDBIDResult<D extends Distance<D>> extends List<DistanceResultPair<D>> { + // Empty. TODO: add "sorted" property? +} diff --git a/src/de/lmu/ifi/dbs/elki/database/query/DistanceResultPair.java b/src/de/lmu/ifi/dbs/elki/database/query/DistanceResultPair.java index e7403628..b6cc129b 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/DistanceResultPair.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/DistanceResultPair.java @@ -24,6 +24,7 @@ package de.lmu.ifi.dbs.elki.database.query; */ import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; import de.lmu.ifi.dbs.elki.utilities.pairs.PairInterface; @@ -35,7 +36,7 @@ import de.lmu.ifi.dbs.elki.utilities.pairs.PairInterface; * * @param <D> Distance type */ -public interface DistanceResultPair<D extends Distance<?>> extends PairInterface<D, DBID>, Comparable<DistanceResultPair<D>> { +public interface DistanceResultPair<D extends Distance<?>> extends PairInterface<D, DBID>, Comparable<DistanceResultPair<D>>, DBIDRef { /** * Getter for first * @@ -51,13 +52,6 @@ public interface DistanceResultPair<D extends Distance<?>> extends PairInterface public void setDistance(D first); /** - * Getter for second element in pair - * - * @return second element in pair - */ - public DBID getDBID(); - - /** * Setter for second * * @param second new value for second element diff --git a/src/de/lmu/ifi/dbs/elki/database/query/DoubleDistanceResultPair.java b/src/de/lmu/ifi/dbs/elki/database/query/DoubleDistanceResultPair.java index e0be7c40..23abc327 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/DoubleDistanceResultPair.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/DoubleDistanceResultPair.java @@ -24,6 +24,7 @@ package de.lmu.ifi.dbs.elki.database.query; */ import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; /** @@ -71,6 +72,21 @@ public class DoubleDistanceResultPair implements DistanceResultPair<DoubleDistan } @Override + public int getIntegerID() { + return id.getIntegerID(); + } + + @Override + public boolean sameDBID(DBIDRef other) { + return id.sameDBID(other); + } + + @Override + public int compareDBID(DBIDRef other) { + return id.compareDBID(other); + } + + @Override public void setID(DBID id) { this.id = id; } @@ -127,10 +143,10 @@ public class DoubleDistanceResultPair implements DistanceResultPair<DoubleDistan } if(obj instanceof DoubleDistanceResultPair) { DoubleDistanceResultPair ddrp = (DoubleDistanceResultPair) obj; - return distance == ddrp.distance && id.equals(ddrp.id); + return distance == ddrp.distance && id.sameDBID(ddrp.id); } DistanceResultPair<?> other = (DistanceResultPair<?>) obj; - return other.getDistance().equals(distance) && id.equals(other.getDBID()); + return other.getDistance().equals(distance) && id.sameDBID(other.getDBID()); } /** diff --git a/src/de/lmu/ifi/dbs/elki/database/query/GenericDistanceDBIDList.java b/src/de/lmu/ifi/dbs/elki/database/query/GenericDistanceDBIDList.java new file mode 100644 index 00000000..2283c401 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/query/GenericDistanceDBIDList.java @@ -0,0 +1,68 @@ +package de.lmu.ifi.dbs.elki.database.query; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +import java.util.ArrayList; +import java.util.Collection; + +import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; + +/** + * Default class to keep a list of distance-object pairs. + * + * @author Erich Schubert + * + * @param <D> Distance type + */ +public class GenericDistanceDBIDList<D extends Distance<D>> extends ArrayList<DistanceResultPair<D>> implements DistanceDBIDResult<D> { + /** + * Serialization Version + */ + private static final long serialVersionUID = 1L; + + /** + * Constructor. + */ + public GenericDistanceDBIDList() { + super(); + } + + /** + * Constructor. + * + * @param c existing collection + */ + public GenericDistanceDBIDList(Collection<? extends DistanceResultPair<D>> c) { + super(c); + } + + /** + * Constructor. + * + * @param initialCapacity Capacity + */ + public GenericDistanceDBIDList(int initialCapacity) { + super(initialCapacity); + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/query/GenericDistanceResultPair.java b/src/de/lmu/ifi/dbs/elki/database/query/GenericDistanceResultPair.java index 4b838560..414f145a 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/GenericDistanceResultPair.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/GenericDistanceResultPair.java @@ -24,6 +24,7 @@ package de.lmu.ifi.dbs.elki.database.query; */ import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; import de.lmu.ifi.dbs.elki.utilities.pairs.Pair; @@ -74,6 +75,21 @@ public class GenericDistanceResultPair<D extends Distance<D>> extends Pair<D, DB public final DBID getDBID() { return second; } + + @Override + public int getIntegerID() { + return second.getIntegerID(); + } + + @Override + public boolean sameDBID(DBIDRef other) { + return second.sameDBID(other); + } + + @Override + public int compareDBID(DBIDRef other) { + return second.compareDBID(other); + } /** * Setter for second @@ -105,7 +121,7 @@ public class GenericDistanceResultPair<D extends Distance<D>> extends Pair<D, DB return false; } DistanceResultPair<?> other = (DistanceResultPair<?>) obj; - return first.equals(other.getDistance()) && second.equals(other.getDBID()); + return first.equals(other.getDistance()) && second.sameDBID(other.getDBID()); } @Override diff --git a/src/de/lmu/ifi/dbs/elki/database/query/distance/AbstractDatabaseDistanceQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/distance/AbstractDatabaseDistanceQuery.java index 92c116e3..ed1ee50c 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/distance/AbstractDatabaseDistanceQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/distance/AbstractDatabaseDistanceQuery.java @@ -24,6 +24,7 @@ package de.lmu.ifi.dbs.elki.database.query.distance; */ import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; @@ -46,7 +47,7 @@ public abstract class AbstractDatabaseDistanceQuery<O, D extends Distance<D>> ex } @Override - public D distance(O o1, DBID id2) { + public D distance(O o1, DBIDRef id2) { if(o1 instanceof DBID) { return distance((DBID) o1, id2); } @@ -54,7 +55,7 @@ public abstract class AbstractDatabaseDistanceQuery<O, D extends Distance<D>> ex } @Override - public D distance(DBID id1, O o2) { + public D distance(DBIDRef id1, O o2) { if(o2 instanceof DBID) { return distance(id1, (DBID) o2); } diff --git a/src/de/lmu/ifi/dbs/elki/database/query/distance/AbstractDistanceQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/distance/AbstractDistanceQuery.java index 10dde0ad..b85ddef0 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/distance/AbstractDistanceQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/distance/AbstractDistanceQuery.java @@ -23,7 +23,7 @@ package de.lmu.ifi.dbs.elki.database.query.distance; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.query.AbstractDataBasedQuery; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; @@ -55,7 +55,7 @@ public abstract class AbstractDistanceQuery<O, D extends Distance<D>> extends Ab * @return the distance between the two objects specified by their object ids */ @Override - public abstract D distance(DBID id1, DBID id2); + public abstract D distance(DBIDRef id1, DBIDRef id2); /** * Returns the distance between the two objects specified by their object ids. @@ -65,7 +65,7 @@ public abstract class AbstractDistanceQuery<O, D extends Distance<D>> extends Ab * @return the distance between the two objects specified by their object ids */ @Override - public abstract D distance(O o1, DBID id2); + public abstract D distance(O o1, DBIDRef id2); /** * Returns the distance between the two objects specified by their object ids. @@ -75,7 +75,7 @@ public abstract class AbstractDistanceQuery<O, D extends Distance<D>> extends Ab * @return the distance between the two objects specified by their object ids */ @Override - public abstract D distance(DBID id1, O o2); + public abstract D distance(DBIDRef id1, O o2); /** * Returns the distance between the two objects specified by their object ids. diff --git a/src/de/lmu/ifi/dbs/elki/database/query/distance/DBIDDistanceQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/distance/DBIDDistanceQuery.java index 2bb45623..28ca9b16 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/distance/DBIDDistanceQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/distance/DBIDDistanceQuery.java @@ -24,6 +24,7 @@ package de.lmu.ifi.dbs.elki.database.query.distance; */ import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancefunction.DBIDDistanceFunction; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; @@ -56,7 +57,7 @@ public class DBIDDistanceQuery<D extends Distance<D>> extends AbstractDatabaseDi } @Override - public D distance(DBID id1, DBID id2) { + public D distance(DBIDRef id1, DBIDRef id2) { if(id1 == null) { throw new UnsupportedOperationException("This distance function can only be used for objects stored in the database."); } diff --git a/src/de/lmu/ifi/dbs/elki/database/query/distance/DistanceQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/distance/DistanceQuery.java index 1986b246..c026162d 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/distance/DistanceQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/distance/DistanceQuery.java @@ -23,7 +23,7 @@ package de.lmu.ifi.dbs.elki.database.query.distance; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.query.DatabaseQuery; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction; @@ -48,7 +48,7 @@ public interface DistanceQuery<O, D extends Distance<?>> extends DatabaseQuery { * @param id2 second object id * @return the distance between the two objects specified by their object ids */ - D distance(DBID id1, DBID id2); + D distance(DBIDRef id1, DBIDRef id2); /** * Returns the distance between the two objects specified by their object ids. @@ -57,7 +57,7 @@ public interface DistanceQuery<O, D extends Distance<?>> extends DatabaseQuery { * @param id2 second object id * @return the distance between the two objects specified by their object ids */ - D distance(O o1, DBID id2); + D distance(O o1, DBIDRef id2); /** * Returns the distance between the two objects specified by their object ids. @@ -66,7 +66,7 @@ public interface DistanceQuery<O, D extends Distance<?>> extends DatabaseQuery { * @param o2 second object * @return the distance between the two objects specified by their object ids */ - D distance(DBID id1, O o2); + D distance(DBIDRef id1, O o2); /** * Returns the distance between the two objects specified by their object ids. diff --git a/src/de/lmu/ifi/dbs/elki/database/query/distance/PrimitiveDistanceQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/distance/PrimitiveDistanceQuery.java index 5015dee1..75bd9e39 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/distance/PrimitiveDistanceQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/distance/PrimitiveDistanceQuery.java @@ -23,7 +23,7 @@ package de.lmu.ifi.dbs.elki.database.query.distance; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancefunction.PrimitiveDistanceFunction; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; @@ -57,20 +57,20 @@ public class PrimitiveDistanceQuery<O, D extends Distance<D>> extends AbstractDi } @Override - public D distance(DBID id1, DBID id2) { + public D distance(DBIDRef id1, DBIDRef id2) { O o1 = relation.get(id1); O o2 = relation.get(id2); return distance(o1, o2); } @Override - public D distance(O o1, DBID id2) { + public D distance(O o1, DBIDRef id2) { O o2 = relation.get(id2); return distance(o1, o2); } @Override - public D distance(DBID id1, O o2) { + public D distance(DBIDRef id1, O o2) { O o1 = relation.get(id1); return distance(o1, o2); } diff --git a/src/de/lmu/ifi/dbs/elki/database/query/distance/PrimitiveDistanceSimilarityQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/distance/PrimitiveDistanceSimilarityQuery.java index 4988c925..930d195c 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/distance/PrimitiveDistanceSimilarityQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/distance/PrimitiveDistanceSimilarityQuery.java @@ -23,7 +23,7 @@ package de.lmu.ifi.dbs.elki.database.query.distance; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.query.DistanceSimilarityQuery; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancefunction.PrimitiveDistanceFunction; @@ -61,20 +61,20 @@ public class PrimitiveDistanceSimilarityQuery<O, D extends Distance<D>> extends } @Override - public D similarity(DBID id1, DBID id2) { + public D similarity(DBIDRef id1, DBIDRef id2) { O o1 = relation.get(id1); O o2 = relation.get(id2); return similarity(o1, o2); } @Override - public D similarity(O o1, DBID id2) { + public D similarity(O o1, DBIDRef id2) { O o2 = relation.get(id2); return similarity(o1, o2); } @Override - public D similarity(DBID id1, O o2) { + public D similarity(DBIDRef id1, O o2) { O o1 = relation.get(id1); return similarity(o1, o2); } diff --git a/src/de/lmu/ifi/dbs/elki/database/query/knn/AbstractDistanceKNNQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/knn/AbstractDistanceKNNQuery.java index 731148e8..e5df1452 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/knn/AbstractDistanceKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/knn/AbstractDistanceKNNQuery.java @@ -23,7 +23,7 @@ package de.lmu.ifi.dbs.elki.database.query.knn; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.query.AbstractDataBasedQuery; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; @@ -50,7 +50,7 @@ public abstract class AbstractDistanceKNNQuery<O, D extends Distance<D>> extends } @Override - abstract public KNNResult<D> getKNNForDBID(DBID id, int k); + abstract public KNNResult<D> getKNNForDBID(DBIDRef id, int k); @Override abstract public KNNResult<D> getKNNForObject(O obj, int k); diff --git a/src/de/lmu/ifi/dbs/elki/database/query/knn/KNNQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/knn/KNNQuery.java index 80d91180..13bf58c2 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/knn/KNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/knn/KNNQuery.java @@ -28,6 +28,7 @@ import java.util.Map; import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.query.DatabaseQuery; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNHeap; @@ -51,7 +52,7 @@ public interface KNNQuery<O, D extends Distance<D>> extends DatabaseQuery { * @param k Number of neighbors requested * @return neighbors */ - public KNNResult<D> getKNNForDBID(DBID id, int k); + public KNNResult<D> getKNNForDBID(DBIDRef id, int k); /** * Bulk query method diff --git a/src/de/lmu/ifi/dbs/elki/database/query/knn/KNNResult.java b/src/de/lmu/ifi/dbs/elki/database/query/knn/KNNResult.java index d45fd8d7..e7612fcc 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/knn/KNNResult.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/knn/KNNResult.java @@ -23,10 +23,10 @@ package de.lmu.ifi.dbs.elki.database.query.knn; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.Collection; import java.util.List; import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; +import de.lmu.ifi.dbs.elki.database.query.DistanceDBIDResult; import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; @@ -39,7 +39,7 @@ import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; * * @apiviz.composedOf DistanceResultPair */ -public interface KNNResult<D extends Distance<D>> extends Collection<DistanceResultPair<D>> { +public interface KNNResult<D extends Distance<D>> extends DistanceDBIDResult<D> { /** * Size */ @@ -58,6 +58,7 @@ public interface KNNResult<D extends Distance<D>> extends Collection<DistanceRes * * @param index */ + @Override public DistanceResultPair<D> get(int index); /** diff --git a/src/de/lmu/ifi/dbs/elki/database/query/knn/KNNUtil.java b/src/de/lmu/ifi/dbs/elki/database/query/knn/KNNUtil.java index 1179edb5..01deeaa0 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/knn/KNNUtil.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/knn/KNNUtil.java @@ -23,7 +23,6 @@ package de.lmu.ifi.dbs.elki.database.query.knn; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.AbstractCollection; import java.util.AbstractList; import java.util.Iterator; import java.util.List; @@ -31,6 +30,7 @@ import java.util.List; import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; @@ -49,7 +49,7 @@ public final class KNNUtil { * * @param <D> Distance */ - protected static class KNNSubList<D extends Distance<D>> extends AbstractCollection<DistanceResultPair<D>> implements KNNResult<D> { + protected static class KNNSubList<D extends Distance<D>> extends AbstractList<DistanceResultPair<D>> implements KNNResult<D> { /** * Parameter k */ @@ -240,6 +240,18 @@ public final class KNNUtil { public DBID getDBID() { return cur.getDBID(); } + + @Override + public boolean sameDBID(DBIDRef other) { + return getIntegerID() == other.getIntegerID(); + } + + @Override + public int compareDBID(DBIDRef o) { + final int thisVal = getIntegerID(); + final int anotherVal = o.getIntegerID(); + return (thisVal < anotherVal ? -1 : (thisVal == anotherVal ? 0 : 1)); + } } /** @@ -284,9 +296,9 @@ public final class KNNUtil { } @Override - public boolean contains(DBID o) { - for(DBID id : this) { - if(id.equals(o)) { + public boolean contains(DBIDRef o) { + for (DBIDIter iter = iter(); iter.valid(); iter.advance()) { + if(iter.sameDBID(o)) { return true; } } @@ -304,7 +316,7 @@ public final class KNNUtil { */ @Override @Deprecated - public int binarySearch(DBID key) { + public int binarySearch(DBIDRef key) { throw new UnsupportedOperationException("Since the result is usually not sorted, a binary Search does not make sense!"); } } diff --git a/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanKNNQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanKNNQuery.java index d6492f43..b51dad4c 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanKNNQuery.java @@ -31,6 +31,8 @@ import java.util.Map.Entry; import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; import de.lmu.ifi.dbs.elki.database.ids.ArrayModifiableDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.query.LinearScanQuery; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; @@ -64,28 +66,29 @@ public class LinearScanKNNQuery<O, D extends Distance<D>> extends AbstractDistan */ private void linearScanBatchKNN(ArrayDBIDs ids, List<KNNHeap<D>> heaps) { // The distance is computed on database IDs - for(DBID candidateID : relation.iterDBIDs()) { - Integer index = -1; - for(DBID id : ids) { - index++; + for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { + DBID candidateID = iter.getDBID(); + int index = 0; + for (DBIDIter iter2 = ids.iter(); iter2.valid(); iter2.advance()) { KNNHeap<D> heap = heaps.get(index); - heap.add(distanceQuery.distance(id, candidateID), candidateID); + heap.add(distanceQuery.distance(iter2, candidateID), candidateID); + index++; } } } @Override - public KNNResult<D> getKNNForDBID(DBID id, int k) { + public KNNResult<D> getKNNForDBID(DBIDRef id, int k) { KNNHeap<D> heap = new KNNHeap<D>(k); if(PrimitiveDistanceQuery.class.isInstance(distanceQuery)) { O obj = relation.get(id); - for(DBID candidateID : relation.iterDBIDs()) { - heap.add(distanceQuery.distance(obj, relation.get(candidateID)), candidateID); + for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { + heap.add(distanceQuery.distance(obj, relation.get(iter)), iter); } } else { - for(DBID candidateID : relation.iterDBIDs()) { - heap.add(distanceQuery.distance(id, candidateID), candidateID); + for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { + heap.add(distanceQuery.distance(id, iter), iter); } } return heap.toKNNList(); @@ -122,9 +125,8 @@ public class LinearScanKNNQuery<O, D extends Distance<D>> extends AbstractDistan @Override public KNNResult<D> getKNNForObject(O obj, int k) { KNNHeap<D> heap = new KNNHeap<D>(k); - for(DBID candidateID : relation.iterDBIDs()) { - O candidate = relation.get(candidateID); - heap.add(distanceQuery.distance(obj, candidate), candidateID); + for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { + heap.add(distanceQuery.distance(obj, iter), iter); } return heap.toKNNList(); } diff --git a/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanPrimitiveDistanceKNNQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanPrimitiveDistanceKNNQuery.java index 07632a34..59987282 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanPrimitiveDistanceKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanPrimitiveDistanceKNNQuery.java @@ -30,6 +30,8 @@ import java.util.Map.Entry; import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.query.distance.PrimitiveDistanceQuery; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNHeap; @@ -63,7 +65,8 @@ public class LinearScanPrimitiveDistanceKNNQuery<O, D extends Distance<D>> exten protected void linearScanBatchKNN(List<O> objs, List<KNNHeap<D>> heaps) { final int size = objs.size(); // Linear scan style KNN. - for(DBID candidateID : relation.iterDBIDs()) { + for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { + DBID candidateID = iter.getDBID(); O candidate = relation.get(candidateID); for(int index = 0; index < size; index++) { O object = objs.get(index); @@ -74,7 +77,7 @@ public class LinearScanPrimitiveDistanceKNNQuery<O, D extends Distance<D>> exten } @Override - public KNNResult<D> getKNNForDBID(DBID id, int k) { + public KNNResult<D> getKNNForDBID(DBIDRef id, int k) { return getKNNForObject(relation.get(id), k); } @@ -83,9 +86,9 @@ public class LinearScanPrimitiveDistanceKNNQuery<O, D extends Distance<D>> exten final int size = ids.size(); final List<KNNHeap<D>> heaps = new ArrayList<KNNHeap<D>>(size); List<O> objs = new ArrayList<O>(size); - for(DBID id : ids) { + for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { heaps.add(new KNNHeap<D>(k)); - objs.add(relation.get(id)); + objs.add(relation.get(iter)); } linearScanBatchKNN(objs, heaps); diff --git a/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanRawDoubleDistanceKNNQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanRawDoubleDistanceKNNQuery.java index 3f7dc04f..a10aaac5 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanRawDoubleDistanceKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanRawDoubleDistanceKNNQuery.java @@ -26,7 +26,8 @@ package de.lmu.ifi.dbs.elki.database.query.knn; import java.util.Arrays; import java.util.List; -import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.query.DoubleDistanceResultPair; import de.lmu.ifi.dbs.elki.database.query.distance.PrimitiveDistanceQuery; import de.lmu.ifi.dbs.elki.distance.distancefunction.PrimitiveDoubleDistanceFunction; @@ -56,7 +57,7 @@ public class LinearScanRawDoubleDistanceKNNQuery<O> extends LinearScanPrimitiveD } @Override - public KNNResult<DoubleDistance> getKNNForDBID(DBID id, int k) { + public KNNResult<DoubleDistance> getKNNForDBID(DBIDRef id, int k) { return getKNNForObject(relation.get(id), k); } @@ -67,10 +68,10 @@ public class LinearScanRawDoubleDistanceKNNQuery<O> extends LinearScanPrimitiveD // Optimization for double distances. final KNNHeap<DoubleDistance> heap = new KNNHeap<DoubleDistance>(k); double max = Double.POSITIVE_INFINITY; - for(DBID candidateID : relation.iterDBIDs()) { - final double doubleDistance = rawdist.doubleDistance(obj, relation.get(candidateID)); + for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { + final double doubleDistance = rawdist.doubleDistance(obj, relation.get(iter)); if(doubleDistance <= max) { - heap.add(new DoubleDistanceResultPair(doubleDistance, candidateID)); + heap.add(new DoubleDistanceResultPair(doubleDistance, iter.getDBID())); // Update cutoff if(heap.size() >= heap.getK()) { max = ((DoubleDistanceResultPair) heap.peek()).getDoubleDistance(); @@ -91,13 +92,13 @@ public class LinearScanRawDoubleDistanceKNNQuery<O> extends LinearScanPrimitiveD // The distance is computed on arbitrary vectors, we can reduce object // loading by working on the actual vectors. - for(DBID candidateID : relation.iterDBIDs()) { - O candidate = relation.get(candidateID); + for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { + O candidate = relation.get(iter); for(int index = 0; index < size; index++) { final KNNHeap<DoubleDistance> heap = heaps.get(index); double doubleDistance = rawdist.doubleDistance(objs.get(index), candidate); if(doubleDistance <= max[index]) { - heap.add(new DoubleDistanceResultPair(doubleDistance, candidateID)); + heap.add(new DoubleDistanceResultPair(doubleDistance, iter.getDBID())); if(heap.size() >= heap.getK()) { max[index] = ((DoubleDistanceResultPair) heap.peek()).getDoubleDistance(); } diff --git a/src/de/lmu/ifi/dbs/elki/database/query/knn/PreprocessorKNNQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/knn/PreprocessorKNNQuery.java index 93321609..09f93945 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/knn/PreprocessorKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/knn/PreprocessorKNNQuery.java @@ -30,6 +30,8 @@ import java.util.Map.Entry; import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.query.AbstractDataBasedQuery; import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; import de.lmu.ifi.dbs.elki.database.relation.Relation; @@ -77,7 +79,7 @@ public class PreprocessorKNNQuery<O, D extends Distance<D>, T extends KNNResult< } @Override - public KNNResult<D> getKNNForDBID(DBID id, int k) { + public KNNResult<D> getKNNForDBID(DBIDRef id, int k) { if(!warned && k > preprocessor.getK()) { LoggingUtil.warning("Requested more neighbors than preprocessed!"); } @@ -112,8 +114,8 @@ public class PreprocessorKNNQuery<O, D extends Distance<D>, T extends KNNResult< } List<KNNResult<D>> result = new ArrayList<KNNResult<D>>(ids.size()); if(k < preprocessor.getK()) { - for(DBID id : ids) { - KNNResult<D> dr = preprocessor.get(id); + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + KNNResult<D> dr = preprocessor.get(iter); int subk = k; D kdist = dr.get(subk - 1).getDistance(); while(subk < dr.size()) { @@ -135,8 +137,8 @@ public class PreprocessorKNNQuery<O, D extends Distance<D>, T extends KNNResult< } } else { - for(DBID id : ids) { - result.add(preprocessor.get(id)); + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + result.add(preprocessor.get(iter)); } } return result; diff --git a/src/de/lmu/ifi/dbs/elki/database/query/range/AbstractDistanceRangeQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/range/AbstractDistanceRangeQuery.java index 60426034..871c5e9e 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/range/AbstractDistanceRangeQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/range/AbstractDistanceRangeQuery.java @@ -23,11 +23,9 @@ package de.lmu.ifi.dbs.elki.database.query.range; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.List; - -import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.query.AbstractDataBasedQuery; -import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; +import de.lmu.ifi.dbs.elki.database.query.DistanceDBIDResult; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; @@ -57,8 +55,8 @@ public abstract class AbstractDistanceRangeQuery<O, D extends Distance<D>> exten } @Override - abstract public List<DistanceResultPair<D>> getRangeForDBID(DBID id, D range); + abstract public DistanceDBIDResult<D> getRangeForDBID(DBIDRef id, D range); @Override - abstract public List<DistanceResultPair<D>> getRangeForObject(O obj, D range); + abstract public DistanceDBIDResult<D> getRangeForObject(O obj, D range); }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanPrimitiveDistanceRangeQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanPrimitiveDistanceRangeQuery.java index dfe0b581..758d603e 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanPrimitiveDistanceRangeQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanPrimitiveDistanceRangeQuery.java @@ -23,10 +23,8 @@ package de.lmu.ifi.dbs.elki.database.query.range; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.List; - -import de.lmu.ifi.dbs.elki.database.ids.DBID; -import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.query.DistanceDBIDResult; import de.lmu.ifi.dbs.elki.database.query.distance.PrimitiveDistanceQuery; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; @@ -54,7 +52,8 @@ public class LinearScanPrimitiveDistanceRangeQuery<O, D extends Distance<D>> ext } @Override - public List<DistanceResultPair<D>> getRangeForDBID(DBID id, D range) { + public DistanceDBIDResult<D> getRangeForDBID(DBIDRef id, D range) { + // Note: subtle optimization. Get "id" only once! return getRangeForObject(relation.get(id), range); } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanRangeQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanRangeQuery.java index a7bb7db9..c8ddb1ec 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanRangeQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanRangeQuery.java @@ -23,12 +23,12 @@ package de.lmu.ifi.dbs.elki.database.query.range; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.ArrayList; import java.util.Collections; -import java.util.List; -import de.lmu.ifi.dbs.elki.database.ids.DBID; -import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.query.DistanceDBIDResult; +import de.lmu.ifi.dbs.elki.database.query.GenericDistanceDBIDList; import de.lmu.ifi.dbs.elki.database.query.GenericDistanceResultPair; import de.lmu.ifi.dbs.elki.database.query.LinearScanQuery; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; @@ -56,12 +56,12 @@ public class LinearScanRangeQuery<O, D extends Distance<D>> extends AbstractDist } @Override - public List<DistanceResultPair<D>> getRangeForDBID(DBID id, D range) { - List<DistanceResultPair<D>> result = new ArrayList<DistanceResultPair<D>>(); - for(DBID currentID : relation.iterDBIDs()) { - D currentDistance = distanceQuery.distance(id, currentID); + public DistanceDBIDResult<D> getRangeForDBID(DBIDRef id, D range) { + GenericDistanceDBIDList<D> result = new GenericDistanceDBIDList<D>(); + for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { + D currentDistance = distanceQuery.distance(id, iter); if(currentDistance.compareTo(range) <= 0) { - result.add(new GenericDistanceResultPair<D>(currentDistance, currentID)); + result.add(new GenericDistanceResultPair<D>(currentDistance, iter.getDBID())); } } Collections.sort(result); @@ -69,12 +69,12 @@ public class LinearScanRangeQuery<O, D extends Distance<D>> extends AbstractDist } @Override - public List<DistanceResultPair<D>> getRangeForObject(O obj, D range) { - List<DistanceResultPair<D>> result = new ArrayList<DistanceResultPair<D>>(); - for(DBID currentID : relation.iterDBIDs()) { - D currentDistance = distanceQuery.distance(currentID, obj); + public DistanceDBIDResult<D> getRangeForObject(O obj, D range) { + GenericDistanceDBIDList<D> result = new GenericDistanceDBIDList<D>(); + for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { + D currentDistance = distanceQuery.distance(obj, iter); if(currentDistance.compareTo(range) <= 0) { - result.add(new GenericDistanceResultPair<D>(currentDistance, currentID)); + result.add(new GenericDistanceResultPair<D>(currentDistance, iter.getDBID())); } } Collections.sort(result); diff --git a/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanRawDoubleDistanceRangeQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanRawDoubleDistanceRangeQuery.java index 18d1d173..c5ce2f55 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanRawDoubleDistanceRangeQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanRawDoubleDistanceRangeQuery.java @@ -23,13 +23,13 @@ package de.lmu.ifi.dbs.elki.database.query.range; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.ArrayList; import java.util.Collections; -import java.util.List; -import de.lmu.ifi.dbs.elki.database.ids.DBID; -import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.query.DistanceDBIDResult; import de.lmu.ifi.dbs.elki.database.query.DoubleDistanceResultPair; +import de.lmu.ifi.dbs.elki.database.query.GenericDistanceDBIDList; import de.lmu.ifi.dbs.elki.database.query.LinearScanQuery; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.database.query.distance.PrimitiveDistanceQuery; @@ -56,18 +56,18 @@ public class LinearScanRawDoubleDistanceRangeQuery<O> extends LinearScanRangeQue } @Override - public List<DistanceResultPair<DoubleDistance>> getRangeForDBID(DBID id, DoubleDistance range) { + public DistanceDBIDResult<DoubleDistance> getRangeForDBID(DBIDRef id, DoubleDistance range) { if(distanceQuery instanceof PrimitiveDistanceQuery && distanceQuery.getDistanceFunction() instanceof PrimitiveDoubleDistanceFunction) { @SuppressWarnings("unchecked") PrimitiveDoubleDistanceFunction<O> rawdist = (PrimitiveDoubleDistanceFunction<O>) distanceQuery.getDistanceFunction(); double epsilon = range.doubleValue(); O qo = relation.get(id); - List<DistanceResultPair<DoubleDistance>> result = new ArrayList<DistanceResultPair<DoubleDistance>>(); - for(DBID currentID : relation.iterDBIDs()) { - double doubleDistance = rawdist.doubleDistance(qo, relation.get(currentID)); + GenericDistanceDBIDList<DoubleDistance> result = new GenericDistanceDBIDList<DoubleDistance>(); + for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { + double doubleDistance = rawdist.doubleDistance(qo, relation.get(iter)); if(doubleDistance <= epsilon) { - result.add(new DoubleDistanceResultPair(doubleDistance, currentID)); + result.add(new DoubleDistanceResultPair(doubleDistance, iter.getDBID())); } } Collections.sort(result); @@ -79,17 +79,17 @@ public class LinearScanRawDoubleDistanceRangeQuery<O> extends LinearScanRangeQue } @Override - public List<DistanceResultPair<DoubleDistance>> getRangeForObject(O obj, DoubleDistance range) { + public DistanceDBIDResult<DoubleDistance> getRangeForObject(O obj, DoubleDistance range) { if(distanceQuery instanceof PrimitiveDistanceQuery && distanceQuery.getDistanceFunction() instanceof PrimitiveDoubleDistanceFunction) { @SuppressWarnings("unchecked") PrimitiveDoubleDistanceFunction<O> rawdist = (PrimitiveDoubleDistanceFunction<O>) distanceQuery.getDistanceFunction(); double epsilon = range.doubleValue(); - List<DistanceResultPair<DoubleDistance>> result = new ArrayList<DistanceResultPair<DoubleDistance>>(); - for(DBID currentID : relation.iterDBIDs()) { - double doubleDistance = rawdist.doubleDistance(obj, relation.get(currentID)); + GenericDistanceDBIDList<DoubleDistance> result = new GenericDistanceDBIDList<DoubleDistance>(); + for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { + double doubleDistance = rawdist.doubleDistance(obj, relation.get(iter)); if(doubleDistance <= epsilon) { - result.add(new DoubleDistanceResultPair(doubleDistance, currentID)); + result.add(new DoubleDistanceResultPair(doubleDistance, iter.getDBID())); } } Collections.sort(result); diff --git a/src/de/lmu/ifi/dbs/elki/database/query/range/RangeQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/range/RangeQuery.java index c2dbecd6..2c6842bf 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/range/RangeQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/range/RangeQuery.java @@ -23,11 +23,9 @@ package de.lmu.ifi.dbs.elki.database.query.range; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.List; - -import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.query.DatabaseQuery; -import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; +import de.lmu.ifi.dbs.elki.database.query.DistanceDBIDResult; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; /** @@ -36,7 +34,7 @@ import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; * @author Erich Schubert * * @apiviz.landmark - * @apiviz.uses DistanceResultPair oneway - - «create» + * @apiviz.uses DistanceDBIDResult oneway - - «create» * * @param <O> Object type * @param <D> Distance type @@ -49,7 +47,7 @@ public interface RangeQuery<O, D extends Distance<D>> extends DatabaseQuery { * @param range Query range * @return neighbors */ - public List<DistanceResultPair<D>> getRangeForDBID(DBID id, D range); + public DistanceDBIDResult<D> getRangeForDBID(DBIDRef id, D range); /** * Get the nearest neighbors for a particular object in a given query range @@ -58,5 +56,5 @@ public interface RangeQuery<O, D extends Distance<D>> extends DatabaseQuery { * @param range Query range * @return neighbors */ - public List<DistanceResultPair<D>> getRangeForObject(O obj, D range); + public DistanceDBIDResult<D> getRangeForObject(O obj, D range); }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/query/rknn/AbstractRKNNQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/rknn/AbstractRKNNQuery.java index 86e82c7e..fe4f49e1 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/rknn/AbstractRKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/rknn/AbstractRKNNQuery.java @@ -25,7 +25,7 @@ package de.lmu.ifi.dbs.elki.database.query.rknn; import java.util.List; -import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.query.AbstractDataBasedQuery; import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; @@ -53,5 +53,5 @@ public abstract class AbstractRKNNQuery<O, D extends Distance<D>> extends Abstra } @Override - abstract public List<DistanceResultPair<D>> getRKNNForDBID(DBID id, int k); + abstract public List<DistanceResultPair<D>> getRKNNForDBID(DBIDRef id, int k); }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/query/rknn/LinearScanRKNNQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/rknn/LinearScanRKNNQuery.java index 1449d7f0..1f901828 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/rknn/LinearScanRKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/rknn/LinearScanRKNNQuery.java @@ -29,6 +29,8 @@ import java.util.List; import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; import de.lmu.ifi.dbs.elki.database.query.GenericDistanceResultPair; @@ -76,12 +78,12 @@ public class LinearScanRKNNQuery<O, D extends Distance<D>> extends AbstractRKNNQ List<? extends KNNResult<D>> kNNLists = knnQuery.getKNNForBulkDBIDs(allIDs, k); int i = 0; - for(DBID qid : allIDs) { + for (DBIDIter iter = allIDs.iter(); iter.valid(); iter.advance()) { KNNResult<D> knn = kNNLists.get(i); int last = Math.min(k - 1, knn.size() - 1); - D dist = distanceQuery.distance(obj, qid); + D dist = distanceQuery.distance(obj, iter); if(last < k - 1 || dist.compareTo(knn.get(last).getDistance()) < 1) { - rNNlist.add(new GenericDistanceResultPair<D>(dist, qid)); + rNNlist.add(new GenericDistanceResultPair<D>(dist, iter.getDBID())); } i++; } @@ -90,8 +92,24 @@ public class LinearScanRKNNQuery<O, D extends Distance<D>> extends AbstractRKNNQ } @Override - public List<DistanceResultPair<D>> getRKNNForDBID(DBID id, int k) { - return getRKNNForBulkDBIDs(id, k).get(0); + public List<DistanceResultPair<D>> getRKNNForDBID(DBIDRef id, int k) { + ArrayList<DistanceResultPair<D>> rNNList = new ArrayList<DistanceResultPair<D>>(); + + ArrayDBIDs allIDs = DBIDUtil.ensureArray(relation.getDBIDs()); + List<? extends KNNResult<D>> kNNList = knnQuery.getKNNForBulkDBIDs(allIDs, k); + + int i = 0; + for (DBIDIter iter = allIDs.iter(); iter.valid(); iter.advance()) { + KNNResult<D> knn = kNNList.get(i); + for(DistanceResultPair<D> n : knn) { + if(n.sameDBID(id)) { + rNNList.add(new GenericDistanceResultPair<D>(n.getDistance(), iter.getDBID())); + } + } + i++; + } + Collections.sort(rNNList); + return rNNList; } @Override @@ -105,12 +123,13 @@ public class LinearScanRKNNQuery<O, D extends Distance<D>> extends AbstractRKNNQ List<? extends KNNResult<D>> kNNList = knnQuery.getKNNForBulkDBIDs(allIDs, k); int i = 0; - for(DBID qid : allIDs) { + for (DBIDIter iter = allIDs.iter(); iter.valid(); iter.advance()) { + DBID qid = iter.getDBID(); KNNResult<D> knn = kNNList.get(i); for(DistanceResultPair<D> n : knn) { int j = 0; - for(DBID id : ids) { - if(n.getDBID().equals(id)) { + for (DBIDIter iter2 = ids.iter(); iter2.valid(); iter2.advance()) { + if(n.getDBID().sameDBID(iter2)) { List<DistanceResultPair<D>> rNN = rNNList.get(j); rNN.add(new GenericDistanceResultPair<D>(n.getDistance(), qid)); } diff --git a/src/de/lmu/ifi/dbs/elki/database/query/rknn/PreprocessorRKNNQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/rknn/PreprocessorRKNNQuery.java index 2f8e841a..ab8c3b30 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/rknn/PreprocessorRKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/rknn/PreprocessorRKNNQuery.java @@ -27,7 +27,8 @@ import java.util.ArrayList; import java.util.List; import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.query.AbstractDataBasedQuery; import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; import de.lmu.ifi.dbs.elki.database.relation.Relation; @@ -74,7 +75,7 @@ public class PreprocessorRKNNQuery<O, D extends Distance<D>> extends AbstractDat } @Override - public List<DistanceResultPair<D>> getRKNNForDBID(DBID id, int k) { + public List<DistanceResultPair<D>> getRKNNForDBID(DBIDRef id, int k) { if(!warned && k != preprocessor.getK()) { LoggingUtil.warning("Requested more neighbors than preprocessed!"); } @@ -92,8 +93,8 @@ public class PreprocessorRKNNQuery<O, D extends Distance<D>> extends AbstractDat LoggingUtil.warning("Requested more neighbors than preprocessed!"); } List<List<DistanceResultPair<D>>> result = new ArrayList<List<DistanceResultPair<D>>>(ids.size()); - for(DBID id : ids) { - result.add(preprocessor.getRKNN(id)); + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + result.add(preprocessor.getRKNN(iter.getDBID())); } return result; } diff --git a/src/de/lmu/ifi/dbs/elki/database/query/rknn/RKNNQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/rknn/RKNNQuery.java index e707b6ce..9ff6f790 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/rknn/RKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/rknn/RKNNQuery.java @@ -26,7 +26,7 @@ package de.lmu.ifi.dbs.elki.database.query.rknn; import java.util.List; import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.query.DatabaseQuery; import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; @@ -49,7 +49,7 @@ public interface RKNNQuery<O, D extends Distance<D>> extends DatabaseQuery { * @param k number of neighbors requested * @return reverse k nearest neighbors */ - public List<DistanceResultPair<D>> getRKNNForDBID(DBID id, int k); + public List<DistanceResultPair<D>> getRKNNForDBID(DBIDRef id, int k); /** * Get the reverse k nearest neighbors for a particular object. diff --git a/src/de/lmu/ifi/dbs/elki/database/query/similarity/AbstractDBIDSimilarityQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/similarity/AbstractDBIDSimilarityQuery.java index 1af1c624..3d5ff71f 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/similarity/AbstractDBIDSimilarityQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/similarity/AbstractDBIDSimilarityQuery.java @@ -23,7 +23,7 @@ package de.lmu.ifi.dbs.elki.database.query.similarity; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; @@ -46,12 +46,12 @@ public abstract class AbstractDBIDSimilarityQuery<O, D extends Distance<D>> exte } @Override - public D similarity(O o1, DBID id2) { + public D similarity(O o1, DBIDRef id2) { throw new UnsupportedOperationException("This distance function can only be used for objects when referenced by ID."); } @Override - public D similarity(DBID id1, O o2) { + public D similarity(DBIDRef id1, O o2) { throw new UnsupportedOperationException("This distance function can only be used for objects when referenced by ID."); } diff --git a/src/de/lmu/ifi/dbs/elki/database/query/similarity/AbstractSimilarityQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/similarity/AbstractSimilarityQuery.java index 316d155c..21abe219 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/similarity/AbstractSimilarityQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/similarity/AbstractSimilarityQuery.java @@ -23,7 +23,7 @@ package de.lmu.ifi.dbs.elki.database.query.similarity; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.query.AbstractDataBasedQuery; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; @@ -55,7 +55,7 @@ public abstract class AbstractSimilarityQuery<O, D extends Distance<D>> extends * @return the distance between the two objects specified by their object ids */ @Override - public abstract D similarity(DBID id1, DBID id2); + public abstract D similarity(DBIDRef id1, DBIDRef id2); /** * Returns the distance between the two objects specified by their object ids. @@ -65,7 +65,7 @@ public abstract class AbstractSimilarityQuery<O, D extends Distance<D>> extends * @return the distance between the two objects specified by their object ids */ @Override - public abstract D similarity(O o1, DBID id2); + public abstract D similarity(O o1, DBIDRef id2); /** * Returns the distance between the two objects specified by their object ids. @@ -75,7 +75,7 @@ public abstract class AbstractSimilarityQuery<O, D extends Distance<D>> extends * @return the distance between the two objects specified by their object ids */ @Override - public abstract D similarity(DBID id1, O o2); + public abstract D similarity(DBIDRef id1, O o2); /** * Returns the distance between the two objects specified by their object ids. diff --git a/src/de/lmu/ifi/dbs/elki/database/query/similarity/PrimitiveSimilarityQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/similarity/PrimitiveSimilarityQuery.java index f57e0bd5..5a604d0c 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/similarity/PrimitiveSimilarityQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/similarity/PrimitiveSimilarityQuery.java @@ -23,7 +23,7 @@ package de.lmu.ifi.dbs.elki.database.query.similarity; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; import de.lmu.ifi.dbs.elki.distance.similarityfunction.PrimitiveSimilarityFunction; @@ -54,20 +54,20 @@ public class PrimitiveSimilarityQuery<O, D extends Distance<D>> extends Abstract } @Override - public D similarity(DBID id1, DBID id2) { + public D similarity(DBIDRef id1, DBIDRef id2) { O o1 = relation.get(id1); O o2 = relation.get(id2); return similarity(o1, o2); } @Override - public D similarity(O o1, DBID id2) { + public D similarity(O o1, DBIDRef id2) { O o2 = relation.get(id2); return similarity(o1, o2); } @Override - public D similarity(DBID id1, O o2) { + public D similarity(DBIDRef id1, O o2) { O o1 = relation.get(id1); return similarity(o1, o2); } diff --git a/src/de/lmu/ifi/dbs/elki/database/query/similarity/SimilarityQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/similarity/SimilarityQuery.java index c3fdaaa4..b25d13fc 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/similarity/SimilarityQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/similarity/SimilarityQuery.java @@ -23,7 +23,7 @@ package de.lmu.ifi.dbs.elki.database.query.similarity; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.query.DatabaseQuery; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; @@ -50,7 +50,7 @@ public interface SimilarityQuery<O, D extends Distance<?>> extends DatabaseQuery * @return the similarity between the two objects specified by their object * ids */ - public abstract D similarity(DBID id1, DBID id2); + public abstract D similarity(DBIDRef id1, DBIDRef id2); /** * Returns the similarity between the two objects specified by their object @@ -61,7 +61,7 @@ public interface SimilarityQuery<O, D extends Distance<?>> extends DatabaseQuery * @return the similarity between the two objects specified by their object * ids */ - public abstract D similarity(O o1, DBID id2); + public abstract D similarity(O o1, DBIDRef id2); /** * Returns the similarity between the two objects specified by their object @@ -72,7 +72,7 @@ public interface SimilarityQuery<O, D extends Distance<?>> extends DatabaseQuery * @return the similarity between the two objects specified by their object * ids */ - public abstract D similarity(DBID id1, O o2); + public abstract D similarity(DBIDRef id1, O o2); /** * Returns the similarity between the two objects specified by their object |