1 files changed, 63 insertions, 40 deletions

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 59a6d6e3..20a120e5 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
@@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.knn;
  This file is part of ELKI:
  Environment for Developing KDD-Applications Supported by Index-Structures
 
- Copyright (C) 2013
+ Copyright (C) 2014
  Ludwig-Maximilians-Universität München
  Lehr- und Forschungseinheit für Datenbanksysteme
  ELKI Development Team
@@ -30,11 +30,12 @@ import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs;
 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.ids.distance.KNNHeap;
-import de.lmu.ifi.dbs.elki.database.ids.distance.KNNList;
+import de.lmu.ifi.dbs.elki.database.ids.KNNHeap;
+import de.lmu.ifi.dbs.elki.database.ids.KNNList;
 import de.lmu.ifi.dbs.elki.database.query.LinearScanQuery;
 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.database.relation.Relation;
+import de.lmu.ifi.dbs.elki.distance.distancefunction.PrimitiveDistanceFunction;
 
 /**
  * Instance of this query for a particular database.
@@ -45,69 +46,91 @@ import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance;
  * @author Erich Schubert
  * 
  * @apiviz.uses PrimitiveDistanceQuery
+ * @apiviz.uses PrimitiveDistanceFunction
  */
-public class LinearScanPrimitiveDistanceKNNQuery<O, D extends Distance<D>> extends AbstractDistanceKNNQuery<O, D> implements LinearScanQuery {
+public class LinearScanPrimitiveDistanceKNNQuery<O> extends AbstractDistanceKNNQuery<O> implements LinearScanQuery {
+  /**
+   * Unboxed distance function.
+   */
+  private PrimitiveDistanceFunction<? super O> rawdist;
+
   /**
    * Constructor.
    * 
    * @param distanceQuery Distance function to use
    */
-  public LinearScanPrimitiveDistanceKNNQuery(PrimitiveDistanceQuery<O, D> distanceQuery) {
+  public LinearScanPrimitiveDistanceKNNQuery(PrimitiveDistanceQuery<O> distanceQuery) {
     super(distanceQuery);
+    rawdist = distanceQuery.getDistanceFunction();
   }
 
-  /**
-   * Perform a linear scan batch kNN for primitive distance functions.
-   * 
-   * @param objs Objects list
-   * @param heaps Heaps array
-   */
-  protected void linearScanBatchKNN(List<O> objs, List<KNNHeap<D>> heaps) {
-    final int size = objs.size();
-    // Linear scan style KNN.
-    for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) {
-      O candidate = relation.get(iter);
-      for(int index = 0; index < size; index++) {
-        O object = objs.get(index);
-        heaps.get(index).insert(distanceQuery.distance(object, candidate), iter);
-      }
-    }
+  @Override
+  public KNNList getKNNForDBID(DBIDRef id, int k) {
+    return linearScan(relation, relation.iterDBIDs(), relation.get(id), DBIDUtil.newHeap(k)).toKNNList();
   }
 
   @Override
-  public KNNList<D> getKNNForDBID(DBIDRef id, int k) {
-    final O obj = relation.get(id);
-    KNNHeap<D> heap = DBIDUtil.newHeap(distanceQuery.getDistanceFactory(), k);
-    for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) {
-      heap.insert(distanceQuery.distance(obj, iter), iter);
-    }
-    return heap.toKNNList();
+  public KNNList getKNNForObject(O obj, int k) {
+    return linearScan(relation, relation.iterDBIDs(), obj, DBIDUtil.newHeap(k)).toKNNList();
   }
 
-  @Override
-  public KNNList<D> getKNNForObject(O obj, int k) {
-    KNNHeap<D> heap = DBIDUtil.newHeap(distanceQuery.getDistanceFactory(), k);
-    for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) {
-      heap.insert(distanceQuery.distance(obj, iter), iter);
+  /**
+   * Main loop of the linear scan.
+   * 
+   * @param relation Data relation
+   * @param iter ID iterator
+   * @param obj Query object
+   * @param heap Output heap
+   * @return Heap
+   */
+  private KNNHeap linearScan(Relation<? extends O> relation, DBIDIter iter, final O obj, KNNHeap heap) {
+    double max = Double.POSITIVE_INFINITY;
+    while(iter.valid()) {
+      final double dist = rawdist.distance(obj, relation.get(iter));
+      if(dist <= max) {
+        max = heap.insert(dist, iter);
+      }
+      iter.advance();
     }
-    return heap.toKNNList();
+    return heap;
   }
 
   @Override
-  public List<KNNList<D>> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) {
+  public List<KNNList> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) {
     final int size = ids.size();
-    final List<KNNHeap<D>> heaps = new ArrayList<>(size);
+    final List<KNNHeap> heaps = new ArrayList<>(size);
     List<O> objs = new ArrayList<>(size);
     for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) {
-      heaps.add(DBIDUtil.newHeap(distanceQuery.getDistanceFactory(), k));
+      heaps.add(DBIDUtil.newHeap(k));
       objs.add(relation.get(iter));
     }
     linearScanBatchKNN(objs, heaps);
 
-    List<KNNList<D>> result = new ArrayList<>(heaps.size());
-    for(KNNHeap<D> heap : heaps) {
+    List<KNNList> result = new ArrayList<>(heaps.size());
+    for(KNNHeap heap : heaps) {
       result.add(heap.toKNNList());
     }
     return result;
   }
+
+  /**
+   * Perform a linear scan batch kNN for primitive distance functions.
+   * 
+   * @param objs Objects list
+   * @param heaps Heaps array
+   */
+  protected void linearScanBatchKNN(List<O> objs, List<KNNHeap> heaps) {
+    final int size = objs.size();
+    // Linear scan style KNN.
+    for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) {
+      O candidate = relation.get(iter);
+      for(int index = 0; index < size; index++) {
+        final KNNHeap heap = heaps.get(index);
+        final double dist = rawdist.distance(objs.get(index), candidate);
+        if(dist <= heap.getKNNDistance()) {
+          heap.insert(dist, iter);
+        }
+      }
+    }
+  }
 }
\ No newline at end of file