Import Debian changes 0.6.0~beta2-1

elki (0.6.0~beta2-1) unstable; urgency=low

  * New upstream beta release.
  * 3DPC extension is not yet included.

1 files changed, 34 insertions, 49 deletions

diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MetricalIndexKNNQuery.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MetricalIndexKNNQuery.java
index c2fafdae..f40e001b 100644
--- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MetricalIndexKNNQuery.java
+++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MetricalIndexKNNQuery.java
@@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query;
  This file is part of ELKI:
  Environment for Developing KDD-Applications Supported by Index-Structures
 
- Copyright (C) 2012
+ Copyright (C) 2013
  Ludwig-Maximilians-Universität München
  Lehr- und Forschungseinheit für Datenbanksysteme
  ELKI Development Team
@@ -23,25 +23,19 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query;
  along with this program.  If not, see <http://www.gnu.org/licenses/>.
  */
 
-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.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.query.distance.DistanceQuery;
 import de.lmu.ifi.dbs.elki.database.query.knn.AbstractDistanceKNNQuery;
-import de.lmu.ifi.dbs.elki.distance.DistanceUtil;
-import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNHeap;
-import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNResult;
-import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNUtil;
-import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance;
+import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance;
 import de.lmu.ifi.dbs.elki.index.tree.DirectoryEntry;
 import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree;
 import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTreeNode;
 import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.MTreeEntry;
-import de.lmu.ifi.dbs.elki.index.tree.query.GenericMTreeDistanceSearchCandidate;
-import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.Heap;
-import de.lmu.ifi.dbs.elki.utilities.exceptions.ExceptionMessages;
+import de.lmu.ifi.dbs.elki.index.tree.query.DoubleMTreeDistanceSearchCandidate;
+import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.ComparableMinHeap;
 
 /**
  * Instance of a KNN query for a particular spatial index.
@@ -53,11 +47,11 @@ import de.lmu.ifi.dbs.elki.utilities.exceptions.ExceptionMessages;
  * @param <O> Object type
  * @param <D> Distance type
  */
-public class MetricalIndexKNNQuery<O, D extends Distance<D>> extends AbstractDistanceKNNQuery<O, D> {
+public class MetricalIndexKNNQuery<O, D extends NumberDistance<D, ?>> extends AbstractDistanceKNNQuery<O, D> {
   /**
    * The index to use
    */
-  protected final AbstractMTree<O, D, ?, ?> index;
+  protected final AbstractMTree<O, D, ?, ?, ?> index;
 
   /**
    * Constructor.
@@ -65,55 +59,56 @@ public class MetricalIndexKNNQuery<O, D extends Distance<D>> extends AbstractDis
    * @param index Index to use
    * @param distanceQuery Distance query used
    */
-  public MetricalIndexKNNQuery(AbstractMTree<O, D, ?, ?> index, DistanceQuery<O, D> distanceQuery) {
+  public MetricalIndexKNNQuery(AbstractMTree<O, D, ?, ?, ?> index, DistanceQuery<O, D> distanceQuery) {
     super(distanceQuery);
     this.index = index;
   }
 
   @Override
-  public KNNResult<D> getKNNForObject(O q, int k) {
+  public KNNList<D> getKNNForObject(O q, int k) {
     if (k < 1) {
       throw new IllegalArgumentException("At least one object has to be requested!");
     }
+    index.statistics.countKNNQuery();
 
-    final D nullDistance = index.getDistanceFactory().nullDistance();
-    KNNHeap<D> knnList = KNNUtil.newHeap(distanceQuery.getDistanceFactory(), k);
+    KNNHeap<D> knnList = DBIDUtil.newHeap(distanceQuery.getDistanceFactory(), k);
     D d_k = knnList.getKNNDistance();
 
-    final Heap<GenericMTreeDistanceSearchCandidate<D>> pq = new Heap<GenericMTreeDistanceSearchCandidate<D>>();
+    final ComparableMinHeap<DoubleMTreeDistanceSearchCandidate> pq = new ComparableMinHeap<>();
 
     // push root
-    pq.add(new GenericMTreeDistanceSearchCandidate<D>(nullDistance, index.getRootID(), null, nullDistance));
+    pq.add(new DoubleMTreeDistanceSearchCandidate(0., index.getRootID(), null, 0.));
 
     // search in tree
     while (!pq.isEmpty()) {
-      GenericMTreeDistanceSearchCandidate<D> pqNode = pq.poll();
+      DoubleMTreeDistanceSearchCandidate pqNode = pq.poll();
 
-      if (knnList.size() >= k && pqNode.mindist.compareTo(d_k) > 0) {
+      if (knnList.size() >= k && pqNode.mindist > d_k.doubleValue()) {
         break;
       }
 
       AbstractMTreeNode<?, D, ?, ?> node = index.getNode(pqNode.nodeID);
       DBID id_p = pqNode.routingObjectID;
-      D d1 = pqNode.routingDistance;
+      double d1 = pqNode.routingDistance;
 
       // directory node
       if (!node.isLeaf()) {
         for (int i = 0; i < node.getNumEntries(); i++) {
-          MTreeEntry<D> entry = node.getEntry(i);
+          MTreeEntry entry = node.getEntry(i);
           DBID o_r = entry.getRoutingObjectID();
-          D r_or = entry.getCoveringRadius();
-          D d2 = id_p != null ? entry.getParentDistance() : nullDistance;
+          double r_or = entry.getCoveringRadius();
+          double d2 = id_p != null ? entry.getParentDistance() : 0.;
 
-          D diff = d1.compareTo(d2) > 0 ? d1.minus(d2) : d2.minus(d1);
+          double diff = Math.abs(d1 - d2);
 
-          D sum = d_k.plus(r_or);
+          double sum = d_k.doubleValue() + r_or;
 
-          if (diff.compareTo(sum) <= 0) {
-            D d3 = distanceQuery.distance(o_r, q);
-            D d_min = DistanceUtil.max(d3.minus(r_or), index.getDistanceFactory().nullDistance());
-            if (d_min.compareTo(d_k) <= 0) {
-              pq.add(new GenericMTreeDistanceSearchCandidate<D>(d_min, ((DirectoryEntry) entry).getPageID(), o_r, d3));
+          if (diff <= sum) {
+            double d3 = distanceQuery.distance(o_r, q).doubleValue();
+            index.statistics.countDistanceCalculation();
+            double d_min = Math.max(d3 - r_or, 0.);
+            if (d_min <= d_k.doubleValue()) {
+              pq.add(new DoubleMTreeDistanceSearchCandidate(d_min, ((DirectoryEntry) entry).getPageID(), o_r, d3));
             }
           }
         }
@@ -121,15 +116,16 @@ public class MetricalIndexKNNQuery<O, D extends Distance<D>> extends AbstractDis
       // data node
       else {
         for (int i = 0; i < node.getNumEntries(); i++) {
-          MTreeEntry<D> entry = node.getEntry(i);
+          MTreeEntry entry = node.getEntry(i);
           DBID o_j = entry.getRoutingObjectID();
 
-          D d2 = id_p != null ? entry.getParentDistance() : nullDistance;
+          double d2 = id_p != null ? entry.getParentDistance() : 0.;
 
-          D diff = (d1.compareTo(d2) > 0) ? d1.minus(d2) : d2.minus(d1);
+          double diff = Math.abs(d1 - d2);
 
-          if (diff.compareTo(d_k) <= 0) {
+          if (diff <= d_k.doubleValue()) {
             D d3 = distanceQuery.distance(o_j, q);
+            index.statistics.countDistanceCalculation();
             if (d3.compareTo(d_k) <= 0) {
               knnList.add(d3, o_j);
               d_k = knnList.getKNNDistance();
@@ -140,15 +136,4 @@ public class MetricalIndexKNNQuery<O, D extends Distance<D>> extends AbstractDis
     }
     return knnList.toKNNList();
   }
-
-  @Override
-  public KNNResult<D> getKNNForDBID(DBIDRef id, int k) {
-    return getKNNForObject(relation.get(id), k);
-  }
-
-  @Override
-  public List<KNNResult<D>> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) {
-    // TODO: implement
-    throw new UnsupportedOperationException(ExceptionMessages.UNSUPPORTED_NOT_YET);
-  }
 }