1 files changed, 78 insertions, 226 deletions

diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/KNNList.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/KNNList.java
index 02a5264c..b19612f2 100644
--- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/KNNList.java
+++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/KNNList.java
@@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures.heap;
  This file is part of ELKI:
  Environment for Developing KDD-Applications Supported by Index-Structures
 
- Copyright (C) 2011
+ Copyright (C) 2012
  Ludwig-Maximilians-Universität München
  Lehr- und Forschungseinheit für Datenbanksysteme
  ELKI Development Team
@@ -23,15 +23,15 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures.heap;
  along with this program.  If not, see <http://www.gnu.org/licenses/>.
  */
 
-import java.util.AbstractList;
-import java.util.ArrayList;
-import java.util.Collection;
+import java.util.AbstractCollection;
 import java.util.Iterator;
 import java.util.List;
+import java.util.Queue;
 
 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.query.DistanceResultPair;
+import de.lmu.ifi.dbs.elki.database.query.knn.KNNResult;
+import de.lmu.ifi.dbs.elki.database.query.knn.KNNUtil;
 import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance;
 
 /**
@@ -39,49 +39,60 @@ import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance;
  * 
  * @author Erich Schubert
  * 
- * @apiviz.composedOf DBIDItr
- * @apiviz.composedOf DBIDView
- * @apiviz.composedOf DistanceItr
- * @apiviz.composedOf DistanceView
- * 
- * @param <D>
+ * @param <D> Distance type
  */
-public class KNNList<D extends Distance<D>> extends ArrayList<DistanceResultPair<D>> {
-  /**
-   * Serial ID
-   */
-  private static final long serialVersionUID = 1L;
-
+public class KNNList<D extends Distance<D>> extends AbstractCollection<DistanceResultPair<D>> implements KNNResult<D> {
   /**
    * The value of k this was materialized for.
    */
   private final int k;
 
   /**
-   * The maximum distance to return if size() &lt; k
+   * The actual data array.
    */
-  private final D maxdist;
+  private final Object[] data;
 
   /**
-   * Constructor, to be called from KNNHeap only!
+   * Constructor, to be called from KNNHeap only. Use {@link KNNHeap#toKNNList}
+   * instead!
    * 
-   * @param heap Calling heap.
-   * @param maxdist infinite distance to return.
+   * @param heap Calling heap
    */
-  protected KNNList(KNNHeap<D> heap, D maxdist) {
-    super(heap.size());
+  protected KNNList(KNNHeap<D> heap) {
+    super();
+    this.data = new Object[heap.size()];
     this.k = heap.getK();
-    this.maxdist = maxdist;
+    assert(heap.size() >= this.k) : "Heap doesn't contain enough objects!";
     // Get sorted data from heap; but in reverse.
-    int i;
-    for(i = 0; i < heap.size(); i++) {
-      super.add(null);
+    int i = heap.size();
+    while(!heap.isEmpty()) {
+      i--;
+      assert (i >= 0);
+      data[i] = heap.poll();
     }
+    assert (data.length == 0 || data[0] != null);
+    assert (heap.size() == 0);
+  }
+
+  /**
+   * Constructor. With a KNNHeap, use {@link KNNHeap#toKNNList} instead!
+   * 
+   * @param heap Calling heap
+   * @param k K value
+   */
+  public KNNList(Queue<D> heap, int k) {
+    super();
+    this.data = new Object[heap.size()];
+    this.k = k;
+    assert(heap.size() >= this.k) : "Heap doesn't contain enough objects!";
+    // Get sorted data from heap; but in reverse.
+    int i = heap.size();
     while(!heap.isEmpty()) {
       i--;
       assert (i >= 0);
-      super.set(i, heap.poll());
+      data[i] = heap.poll();
     }
+    assert (data.length == 0 || data[0] != null);
     assert (heap.size() == 0);
   }
 
@@ -99,30 +110,19 @@ public class KNNList<D extends Distance<D>> extends ArrayList<DistanceResultPair
    * 
    * @return Maximum distance
    */
+  @Override
   public D getKNNDistance() {
-    if(size() < getK()) {
-      return maxdist;
-    }
     return get(getK() - 1).getDistance();
   }
 
   /**
-   * Get maximum distance in list
-   */
-  public D getMaximumDistance() {
-    if(isEmpty()) {
-      return maxdist;
-    }
-    return get(size() - 1).getDistance();
-  }
-
-  /**
    * View as ArrayDBIDs
    * 
    * @return Static DBIDs
    */
+  @Override
   public ArrayDBIDs asDBIDs() {
-    return new DBIDView(this);
+    return KNNUtil.asDBIDs(this);
   }
 
   /**
@@ -130,221 +130,73 @@ public class KNNList<D extends Distance<D>> extends ArrayList<DistanceResultPair
    * 
    * @return List of distances view
    */
+  @Override
   public List<D> asDistanceList() {
-    return new DistanceView<D>(this);
+    return KNNUtil.asDistanceList(this);
   }
 
   /* Make the list unmodifiable! */
 
   @Override
-  public boolean add(DistanceResultPair<D> e) {
-    throw new UnsupportedOperationException();
-  }
-
-  @Override
-  public void add(int index, DistanceResultPair<D> element) {
-    throw new UnsupportedOperationException();
-  }
-
-  @Override
-  public boolean addAll(Collection<? extends DistanceResultPair<D>> c) {
-    throw new UnsupportedOperationException();
-  }
-
+  public String toString() {
+    StringBuffer buf = new StringBuffer();
+    buf.append("kNNList[");
+    Iterator<DistanceResultPair<D>> iter = this.iterator();
+    while(iter.hasNext()) {
+      DistanceResultPair<D> pair = iter.next();
+      buf.append(pair.getDistance()).append(":").append(pair.getDBID());
+      if(iter.hasNext()) {
+        buf.append(",");
+      }
+    }
+    buf.append("]");
+    return buf.toString();
+  }
+
+  @SuppressWarnings("unchecked")
   @Override
-  public boolean addAll(int index, Collection<? extends DistanceResultPair<D>> c) {
-    throw new UnsupportedOperationException();
+  public DistanceResultPair<D> get(int index) {
+    return (DistanceResultPair<D>) data[index];
   }
 
   @Override
-  public void clear() {
-    throw new UnsupportedOperationException();
+  public Iterator<DistanceResultPair<D>> iterator() {
+    return new Itr();
   }
 
   @Override
-  public DistanceResultPair<D> remove(int index) {
-    throw new UnsupportedOperationException();
-  }
-
-  @Override
-  public boolean remove(Object o) {
-    throw new UnsupportedOperationException();
-  }
-
-  @Override
-  public DistanceResultPair<D> set(int index, DistanceResultPair<D> element) {
-    throw new UnsupportedOperationException();
-  }
-
-  @Override
-  public void trimToSize() {
-    throw new UnsupportedOperationException();
+  public int size() {
+    return data.length;
   }
 
   /**
-   * Proxy iterator for accessing DBIDs.
+   * Iterator
    * 
    * @author Erich Schubert
-   */
-  protected static class DBIDItr implements Iterator<DBID> {
-    /**
-     * The real iterator.
-     */
-    Iterator<? extends DistanceResultPair<?>> itr;
-
-    /**
-     * Constructor.
-     */
-    protected DBIDItr(Iterator<? extends DistanceResultPair<?>> itr) {
-      super();
-      this.itr = itr;
-    }
-
-    @Override
-    public boolean hasNext() {
-      return itr.hasNext();
-    }
-
-    @Override
-    public DBID next() {
-      return itr.next().getDBID();
-    }
-
-    @Override
-    public void remove() {
-      itr.remove();
-    }
-  }
-
-  /**
-   * A view on the DBIDs of the result
    * 
-   * @author Erich Schubert
+   * @apiviz.exclude
    */
-  protected static class DBIDView extends AbstractList<DBID> implements ArrayDBIDs {
+  private class Itr implements Iterator<DistanceResultPair<D>> {
     /**
-     * The true list.
+     * Cursor position
      */
-    final List<? extends DistanceResultPair<?>> parent;
-
-    /**
-     * Constructor.
-     * 
-     * @param parent Owner
-     */
-    public DBIDView(List<? extends DistanceResultPair<?>> parent) {
-      super();
-      this.parent = parent;
-    }
-
-    @Override
-    public DBID get(int i) {
-      return parent.get(i).getDBID();
-    }
-
-    @Override
-    public Collection<DBID> asCollection() {
-      return this;
-    }
-
-    @Override
-    public Iterator<DBID> iterator() {
-      return new DBIDItr(parent.iterator());
-    }
-
-    @Override
-    public int size() {
-      return parent.size();
-    }
-  }
-
-  /**
-   * Proxy iterator for accessing DBIDs.
-   * 
-   * @author Erich Schubert
-   */
-  protected static class DistanceItr<D extends Distance<D>> implements Iterator<D> {
-    /**
-     * The real iterator.
-     */
-    Iterator<? extends DistanceResultPair<D>> itr;
-
-    /**
-     * Constructor.
-     */
-    protected DistanceItr(Iterator<? extends DistanceResultPair<D>> itr) {
-      super();
-      this.itr = itr;
-    }
+    private int pos = -1;
 
     @Override
     public boolean hasNext() {
-      return itr.hasNext();
+      return pos + 1 < data.length;
     }
 
+    @SuppressWarnings("unchecked")
     @Override
-    public D next() {
-      return itr.next().getDistance();
+    public DistanceResultPair<D> next() {
+      pos++;
+      return (DistanceResultPair<D>) data[pos];
     }
 
     @Override
     public void remove() {
-      itr.remove();
-    }
-  }
-
-  /**
-   * A view on the Distances of the result
-   * 
-   * @author Erich Schubert
-   */
-  protected static class DistanceView<D extends Distance<D>> extends AbstractList<D> implements List<D> {
-    /**
-     * The true list.
-     */
-    final List<? extends DistanceResultPair<D>> parent;
-
-    /**
-     * Constructor.
-     * 
-     * @param parent Owner
-     */
-    public DistanceView(List<? extends DistanceResultPair<D>> parent) {
-      super();
-      this.parent = parent;
+      throw new UnsupportedOperationException("kNN results are unmodifiable.");
     }
-
-    @Override
-    public D get(int i) {
-      return parent.get(i).getDistance();
-    }
-
-    @Override
-    public Iterator<D> iterator() {
-      return new DistanceItr<D>(parent.iterator());
-    }
-
-    @Override
-    public int size() {
-      return parent.size();
-    }
-  }
-
-  /**
-   * View as ArrayDBIDs
-   * 
-   * @return Static DBIDs
-   */
-  public static ArrayDBIDs asDBIDs(List<? extends DistanceResultPair<?>> list) {
-    return new DBIDView(list);
-  }
-
-  /**
-   * View as list of distances
-   * 
-   * @return List of distances view
-   */
-  public static <D extends Distance<D>> List<D> asDistanceList(List<? extends DistanceResultPair<D>> list) {
-    return new DistanceView<D>(list);
   }
 }
\ No newline at end of file