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, 69 insertions, 54 deletions

diff --git a/src/de/lmu/ifi/dbs/elki/index/preprocessed/knn/MaterializeKNNPreprocessor.java b/src/de/lmu/ifi/dbs/elki/index/preprocessed/knn/MaterializeKNNPreprocessor.java
index f792833e..3f79d748 100644
--- a/src/de/lmu/ifi/dbs/elki/index/preprocessed/knn/MaterializeKNNPreprocessor.java
+++ b/src/de/lmu/ifi/dbs/elki/index/preprocessed/knn/MaterializeKNNPreprocessor.java
@@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.preprocessed.knn;
  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
@@ -34,17 +34,19 @@ 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.DBIDs;
 import de.lmu.ifi.dbs.elki.database.ids.SetDBIDs;
+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.DatabaseQuery;
 import de.lmu.ifi.dbs.elki.database.query.knn.KNNQuery;
 import de.lmu.ifi.dbs.elki.database.relation.Relation;
 import de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction;
-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.index.DynamicIndex;
 import de.lmu.ifi.dbs.elki.logging.Logging;
 import de.lmu.ifi.dbs.elki.logging.progress.FiniteProgress;
 import de.lmu.ifi.dbs.elki.logging.progress.StepProgress;
+import de.lmu.ifi.dbs.elki.logging.statistics.Duration;
+import de.lmu.ifi.dbs.elki.logging.statistics.LongStatistic;
 import de.lmu.ifi.dbs.elki.utilities.documentation.Description;
 import de.lmu.ifi.dbs.elki.utilities.documentation.Title;
 
@@ -52,7 +54,7 @@ import de.lmu.ifi.dbs.elki.utilities.documentation.Title;
  * A preprocessor for annotation of the k nearest neighbors (and their
  * distances) to each database object.
  * 
- * Used for example by {@link de.lmu.ifi.dbs.elki.algorithm.outlier.LOF}.
+ * Used for example by {@link de.lmu.ifi.dbs.elki.algorithm.outlier.lof.LOF}.
  * 
  * @author Erich Schubert
  * 
@@ -65,7 +67,7 @@ import de.lmu.ifi.dbs.elki.utilities.documentation.Title;
  */
 @Title("Materialize kNN Neighborhood preprocessor")
 @Description("Materializes the k nearest neighbors of objects of a database.")
-public class MaterializeKNNPreprocessor<O, D extends Distance<D>> extends AbstractMaterializeKNNPreprocessor<O, D, KNNResult<D>> {
+public class MaterializeKNNPreprocessor<O, D extends Distance<D>> extends AbstractMaterializeKNNPreprocessor<O, D, KNNList<D>> implements DynamicIndex {
   /**
    * Logger to use.
    */
@@ -108,35 +110,44 @@ public class MaterializeKNNPreprocessor<O, D extends Distance<D>> extends Abstra
     createStorage();
 
     ArrayDBIDs ids = DBIDUtil.ensureArray(relation.getDBIDs());
-    FiniteProgress progress = getLogger().isVerbose() ? new FiniteProgress("Materializing k nearest neighbors (k=" + k + ")", ids.size(), getLogger()) : null;
 
+    if (LOG.isStatistics()) {
+      LOG.statistics(new LongStatistic(this.getClass().getName() + ".k", k));
+    }
+    Duration duration = LOG.isStatistics() ? LOG.newDuration(this.getClass().getName() + ".precomputation-time") : null;
+    if (duration != null) {
+      duration.begin();
+    }
+    FiniteProgress progress = getLogger().isVerbose() ? new FiniteProgress("Materializing k nearest neighbors (k=" + k + ")", ids.size(), getLogger()) : null;
     // Try bulk
-    List<? extends KNNResult<D>> kNNList = null;
-    if(usebulk) {
+    List<? extends KNNList<D>> kNNList = null;
+    if (usebulk) {
       kNNList = knnQuery.getKNNForBulkDBIDs(ids, k);
-      if(kNNList != null) {
+      if (kNNList != null) {
         int i = 0;
-        for(DBIDIter id = ids.iter(); id.valid(); id.advance(), i++) {
+        for (DBIDIter id = ids.iter(); id.valid(); id.advance(), i++) {
           storage.put(id, kNNList.get(i));
-          if(progress != null) {
+          if (progress != null) {
             progress.incrementProcessed(getLogger());
           }
         }
       }
-    }
-    else {
-      for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) {
-        KNNResult<D> knn = knnQuery.getKNNForDBID(iter, k);
+    } else {
+      for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) {
+        KNNList<D> knn = knnQuery.getKNNForDBID(iter, k);
         storage.put(iter, knn);
-        if(progress != null) {
+        if (progress != null) {
           progress.incrementProcessed(getLogger());
         }
       }
     }
-
-    if(progress != null) {
+    if (progress != null) {
       progress.ensureCompleted(getLogger());
     }
+    if (duration != null) {
+      duration.end();
+      LOG.statistics(duration);
+    }
   }
 
   @Override
@@ -146,10 +157,9 @@ public class MaterializeKNNPreprocessor<O, D extends Distance<D>> extends Abstra
 
   @Override
   public void insertAll(DBIDs ids) {
-    if(storage == null && ids.size() > 0) {
+    if (storage == null && ids.size() > 0) {
       preprocess();
-    }
-    else {
+    } else {
       objectsInserted(ids);
     }
   }
@@ -176,30 +186,30 @@ public class MaterializeKNNPreprocessor<O, D extends Distance<D>> extends Abstra
 
     ArrayDBIDs aids = DBIDUtil.ensureArray(ids);
     // materialize the new kNNs
-    if(stepprog != null) {
+    if (stepprog != null) {
       stepprog.beginStep(1, "New insertions ocurred, materialize their new kNNs.", getLogger());
     }
     // Bulk-query kNNs
-    List<? extends KNNResult<D>> kNNList = knnQuery.getKNNForBulkDBIDs(aids, k);
+    List<? extends KNNList<D>> kNNList = knnQuery.getKNNForBulkDBIDs(aids, k);
     // Store in storage
     DBIDIter iter = aids.iter();
-    for(int i = 0; i < aids.size(); i++, iter.advance()) {
+    for (int i = 0; i < aids.size(); i++, iter.advance()) {
       storage.put(iter, kNNList.get(i));
     }
 
     // update the affected kNNs
-    if(stepprog != null) {
+    if (stepprog != null) {
       stepprog.beginStep(2, "New insertions ocurred, update the affected kNNs.", getLogger());
     }
     ArrayDBIDs rkNN_ids = updateKNNsAfterInsertion(ids);
 
     // inform listener
-    if(stepprog != null) {
+    if (stepprog != null) {
       stepprog.beginStep(3, "New insertions ocurred, inform listeners.", getLogger());
     }
     fireKNNsInserted(ids, rkNN_ids);
 
-    if(stepprog != null) {
+    if (stepprog != null) {
       stepprog.setCompleted(getLogger());
     }
   }
@@ -215,21 +225,21 @@ public class MaterializeKNNPreprocessor<O, D extends Distance<D>> extends Abstra
   private ArrayDBIDs updateKNNsAfterInsertion(DBIDs ids) {
     ArrayModifiableDBIDs rkNN_ids = DBIDUtil.newArray();
     DBIDs oldids = DBIDUtil.difference(relation.getDBIDs(), ids);
-    for(DBIDIter iter = oldids.iter(); iter.valid(); iter.advance()) {
-      KNNResult<D> kNNs = storage.get(iter);
+    for (DBIDIter iter = oldids.iter(); iter.valid(); iter.advance()) {
+      KNNList<D> kNNs = storage.get(iter);
       D knnDist = kNNs.get(kNNs.size() - 1).getDistance();
       // look for new kNNs
       KNNHeap<D> heap = null;
-      for(DBIDIter iter2 = ids.iter(); iter2.valid(); iter2.advance()) {
+      for (DBIDIter iter2 = ids.iter(); iter2.valid(); iter2.advance()) {
         D dist = distanceQuery.distance(iter, iter2);
-        if(dist.compareTo(knnDist) <= 0) {
-          if(heap == null) {
-            heap = KNNUtil.newHeap(kNNs);
+        if (dist.compareTo(knnDist) <= 0) {
+          if (heap == null) {
+            heap = DBIDUtil.newHeap(kNNs);
           }
           heap.add(dist, iter2);
         }
       }
-      if(heap != null) {
+      if (heap != null) {
         kNNs = heap.toKNNList();
         storage.put(iter, kNNs);
         rkNN_ids.add(iter);
@@ -248,10 +258,10 @@ public class MaterializeKNNPreprocessor<O, D extends Distance<D>> extends Abstra
   private ArrayDBIDs updateKNNsAfterDeletion(DBIDs ids) {
     SetDBIDs idsSet = DBIDUtil.ensureSet(ids);
     ArrayModifiableDBIDs rkNN_ids = DBIDUtil.newArray();
-    for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) {
-      KNNResult<D> kNNs = storage.get(iditer);
-      for(DBIDIter it = kNNs.iter(); it.valid(); it.advance()) {
-        if(idsSet.contains(it)) {
+    for (DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) {
+      KNNList<D> kNNs = storage.get(iditer);
+      for (DBIDIter it = kNNs.iter(); it.valid(); it.advance()) {
+        if (idsSet.contains(it)) {
           rkNN_ids.add(iditer);
           break;
         }
@@ -259,9 +269,9 @@ public class MaterializeKNNPreprocessor<O, D extends Distance<D>> extends Abstra
     }
 
     // update the kNNs of the RkNNs
-    List<? extends KNNResult<D>> kNNList = knnQuery.getKNNForBulkDBIDs(rkNN_ids, k);
+    List<? extends KNNList<D>> kNNList = knnQuery.getKNNForBulkDBIDs(rkNN_ids, k);
     DBIDIter iter = rkNN_ids.iter();
-    for(int i = 0; i < rkNN_ids.size(); i++, iter.advance()) {
+    for (int i = 0; i < rkNN_ids.size(); i++, iter.advance()) {
       storage.put(iter, kNNList.get(i));
     }
 
@@ -278,26 +288,26 @@ public class MaterializeKNNPreprocessor<O, D extends Distance<D>> extends Abstra
     StepProgress stepprog = getLogger().isVerbose() ? new StepProgress(3) : null;
 
     // delete the materialized (old) kNNs
-    if(stepprog != null) {
+    if (stepprog != null) {
       stepprog.beginStep(1, "New deletions ocurred, remove their materialized kNNs.", getLogger());
     }
-    for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) {
+    for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) {
       storage.delete(iter);
     }
 
     // update the affected kNNs
-    if(stepprog != null) {
+    if (stepprog != null) {
       stepprog.beginStep(2, "New deletions ocurred, update the affected kNNs.", getLogger());
     }
     ArrayDBIDs rkNN_ids = updateKNNsAfterDeletion(ids);
 
     // inform listener
-    if(stepprog != null) {
+    if (stepprog != null) {
       stepprog.beginStep(3, "New deletions ocurred, inform listeners.", getLogger());
     }
     fireKNNsRemoved(ids, rkNN_ids);
 
-    if(stepprog != null) {
+    if (stepprog != null) {
       stepprog.ensureCompleted(getLogger());
     }
   }
@@ -314,8 +324,8 @@ public class MaterializeKNNPreprocessor<O, D extends Distance<D>> extends Abstra
   protected void fireKNNsInserted(DBIDs insertions, DBIDs updates) {
     KNNChangeEvent e = new KNNChangeEvent(this, KNNChangeEvent.Type.INSERT, insertions, updates);
     Object[] listeners = listenerList.getListenerList();
-    for(int i = listeners.length - 2; i >= 0; i -= 2) {
-      if(listeners[i] == KNNListener.class) {
+    for (int i = listeners.length - 2; i >= 0; i -= 2) {
+      if (listeners[i] == KNNListener.class) {
         ((KNNListener) listeners[i + 1]).kNNsChanged(e);
       }
     }
@@ -332,8 +342,8 @@ public class MaterializeKNNPreprocessor<O, D extends Distance<D>> extends Abstra
   protected void fireKNNsRemoved(DBIDs removals, DBIDs updates) {
     KNNChangeEvent e = new KNNChangeEvent(this, KNNChangeEvent.Type.DELETE, removals, updates);
     Object[] listeners = listenerList.getListenerList();
-    for(int i = listeners.length - 2; i >= 0; i -= 2) {
-      if(listeners[i] == KNNListener.class) {
+    for (int i = listeners.length - 2; i >= 0; i -= 2) {
+      if (listeners[i] == KNNListener.class) {
         ((KNNListener) listeners[i + 1]).kNNsChanged(e);
       }
     }
@@ -374,6 +384,11 @@ public class MaterializeKNNPreprocessor<O, D extends Distance<D>> extends Abstra
   }
 
   @Override
+  public void logStatistics() {
+    // TODO: can we log some sensible statistics?
+  }
+
+  @Override
   protected Logging getLogger() {
     return LOG;
   }
@@ -390,7 +405,7 @@ public class MaterializeKNNPreprocessor<O, D extends Distance<D>> extends Abstra
    * @param <O> The object type
    * @param <D> The distance type
    */
-  public static class Factory<O, D extends Distance<D>> extends AbstractMaterializeKNNPreprocessor.Factory<O, D, KNNResult<D>> {
+  public static class Factory<O, D extends Distance<D>> extends AbstractMaterializeKNNPreprocessor.Factory<O, D, KNNList<D>> {
     /**
      * Index factory.
      * 
@@ -403,7 +418,7 @@ public class MaterializeKNNPreprocessor<O, D extends Distance<D>> extends Abstra
 
     @Override
     public MaterializeKNNPreprocessor<O, D> instantiate(Relation<O> relation) {
-      MaterializeKNNPreprocessor<O, D> instance = new MaterializeKNNPreprocessor<O, D>(relation, distanceFunction, k);
+      MaterializeKNNPreprocessor<O, D> instance = new MaterializeKNNPreprocessor<>(relation, distanceFunction, k);
       return instance;
     }
 
@@ -417,8 +432,8 @@ public class MaterializeKNNPreprocessor<O, D extends Distance<D>> extends Abstra
     public static class Parameterizer<O, D extends Distance<D>> extends AbstractMaterializeKNNPreprocessor.Factory.Parameterizer<O, D> {
       @Override
       protected Factory<O, D> makeInstance() {
-        return new Factory<O, D>(k, distanceFunction);
+        return new Factory<>(k, distanceFunction);
       }
     }
   }
-}
\ No newline at end of file
+}