Import Upstream version 0.6.0

22 files changed, 1518 insertions, 948 deletions

diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/AbstractIntegerDBIDFactory.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/AbstractIntegerDBIDFactory.java
index 061deb08..72ecb9be 100644
--- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/AbstractIntegerDBIDFactory.java
+++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/AbstractIntegerDBIDFactory.java
@@ -47,12 +47,12 @@ import de.lmu.ifi.dbs.elki.persistent.FixedSizeByteBufferSerializer;
  * Abstract base class for DBID factories.
  * 
  * @author Erich Schubert
- *
+ * 
  * @apiviz.uses IntegerDBID oneway - - «create»
  * @apiviz.uses IntegerDBIDPair oneway - - «create»
  * @apiviz.uses IntegerDBIDRange oneway - - «create»
- * @apiviz.uses TroveArrayModifiableDBIDs oneway - - «create»
  * @apiviz.uses TroveHashSetModifiableDBIDs oneway - - «create»
+ * @apiviz.uses IntegerArrayDBIDs oneway - - «create»
  */
 abstract class AbstractIntegerDBIDFactory implements DBIDFactory {
   /**
@@ -67,9 +67,10 @@ abstract class AbstractIntegerDBIDFactory implements DBIDFactory {
 
   @Override
   public void assignVar(DBIDVar var, int val) {
-    if (var instanceof IntegerDBIDVar) {
-      ((IntegerDBIDVar)var).internalSetIndex(val);
-    } else {
+    if(var instanceof IntegerDBIDVar) {
+      ((IntegerDBIDVar) var).internalSetIndex(val);
+    }
+    else {
       var.set(new IntegerDBID(val));
     }
   }
@@ -139,7 +140,7 @@ abstract class AbstractIntegerDBIDFactory implements DBIDFactory {
   @SuppressWarnings("unchecked")
   @Override
   public <D extends Distance<D>> DistanceDBIDPair<D> newDistancePair(D val, DBIDRef id) {
-    if (val instanceof DoubleDistance) {
+    if(val instanceof DoubleDistance) {
       return (DistanceDBIDPair<D>) new DoubleDistanceIntegerDBIDPair(((DoubleDistance) val).doubleValue(), id.internalGetIndex());
     }
     return new DistanceIntegerDBIDPair<>(val, id.internalGetIndex());
@@ -149,12 +150,12 @@ abstract class AbstractIntegerDBIDFactory implements DBIDFactory {
   public DoubleDistanceDBIDPair newDistancePair(double val, DBIDRef id) {
     return new DoubleDistanceIntegerDBIDPair(val, id.internalGetIndex());
   }
-  
+
   @SuppressWarnings("unchecked")
   @Override
   public <D extends Distance<D>> KNNHeap<D> newHeap(D factory, int k) {
-    if (factory instanceof DoubleDistance) {
-      return (KNNHeap<D>) new DoubleDistanceIntegerDBIDKNNListHeap(k);
+    if(factory instanceof DoubleDistance) {
+      return (KNNHeap<D>) newDoubleDistanceHeap(k);
     }
     return new DistanceDBIDPairKNNHeap<>(k);
   }
@@ -162,24 +163,34 @@ abstract class AbstractIntegerDBIDFactory implements DBIDFactory {
   @SuppressWarnings("unchecked")
   @Override
   public <D extends Distance<D>> KNNHeap<D> newHeap(KNNList<D> exist) {
-    if (exist instanceof DoubleDistanceKNNList) {
-      DoubleDistanceKNNHeap heap = new DoubleDistanceIntegerDBIDKNNListHeap(exist.getK());
+    if(exist instanceof DoubleDistanceKNNList) {
+      DoubleDistanceKNNHeap heap = newDoubleDistanceHeap(exist.getK());
       // Insert backwards, as this will produce a proper heap
-      for (int i = exist.size() - 1; i >= 0; i--) {
-        heap.add((DoubleDistanceDBIDPair) exist.get(i));
+      for(int i = exist.size() - 1; i >= 0; i--) {
+        heap.insert((DoubleDistanceDBIDPair) exist.get(i));
       }
       return (KNNHeap<D>) heap;
-    } else {
+    }
+    else {
       DistanceDBIDPairKNNHeap<D> heap = new DistanceDBIDPairKNNHeap<>(exist.getK());
       // Insert backwards, as this will produce a proper heap
-      for (int i = exist.size() - 1; i >= 0; i--) {
-        heap.add(exist.get(i));
+      for(int i = exist.size() - 1; i >= 0; i--) {
+        heap.insert(exist.get(i));
       }
       return heap;
     }
   }
 
   @Override
+  public DoubleDistanceKNNHeap newDoubleDistanceHeap(int k) {
+    // TODO: benchmark threshold!
+    if(k > 1000) {
+      return new DoubleDistanceIntegerDBIDKNNHeap(k);
+    }
+    return new DoubleDistanceIntegerDBIDSortedKNNList(k);
+  }
+
+  @Override
   public ByteBufferSerializer<DBID> getDBIDSerializer() {
     return IntegerDBID.DYNAMIC_SERIALIZER;
   }
diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/ArrayModifiableIntegerDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/ArrayModifiableIntegerDBIDs.java
index dfff45b4..2fc94ddb 100644
--- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/ArrayModifiableIntegerDBIDs.java
+++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/ArrayModifiableIntegerDBIDs.java
@@ -47,7 +47,7 @@ public class ArrayModifiableIntegerDBIDs implements ArrayModifiableDBIDs, Intege
   /**
    * Occupied size.
    */
-  private int size = 0;
+  private int size;
 
   /**
    * Initial size.
@@ -57,11 +57,12 @@ public class ArrayModifiableIntegerDBIDs implements ArrayModifiableDBIDs, Intege
   /**
    * Constructor.
    * 
-   * @param size Initial size
+   * @param isize Initial size
    */
-  protected ArrayModifiableIntegerDBIDs(int size) {
+  protected ArrayModifiableIntegerDBIDs(int isize) {
     super();
-    this.store = new int[size];
+    this.store = new int[isize < 3 ? 3 : isize];
+    // default this.size = 0;
   }
 
   /**
@@ -70,6 +71,7 @@ public class ArrayModifiableIntegerDBIDs implements ArrayModifiableDBIDs, Intege
   protected ArrayModifiableIntegerDBIDs() {
     super();
     this.store = new int[INITIAL_SIZE];
+    // default: this.size = 0;
   }
 
   /**
@@ -79,7 +81,15 @@ public class ArrayModifiableIntegerDBIDs implements ArrayModifiableDBIDs, Intege
    */
   protected ArrayModifiableIntegerDBIDs(DBIDs existing) {
     this(existing.size());
-    this.addDBIDs(existing);
+    if (existing instanceof IntegerDBIDRange) {
+      IntegerDBIDRange range = (IntegerDBIDRange) existing;
+      for (int i = 0; i < range.len; i++) {
+        store[i] = range.start + i;
+      }
+      size = range.len;
+    } else {
+      this.addDBIDs(existing);
+    }
   }
 
   @Override
@@ -99,10 +109,9 @@ public class ArrayModifiableIntegerDBIDs implements ArrayModifiableDBIDs, Intege
 
   @Override
   public void assignVar(int index, DBIDVar var) {
-    if(var instanceof IntegerDBIDVar) {
+    if (var instanceof IntegerDBIDVar) {
       ((IntegerDBIDVar) var).internalSetIndex(store[index]);
-    }
-    else {
+    } else {
       // less efficient, involves object creation.
       var.set(get(index));
     }
@@ -114,23 +123,32 @@ public class ArrayModifiableIntegerDBIDs implements ArrayModifiableDBIDs, Intege
    * @param minsize Desired size
    */
   private void ensureSize(int minsize) {
-    int asize = store.length;
-    // Ensure a minimum size, to not run into an infinite loop below!
-    if (asize < 2) {
-      asize = 2;
-    }
-    while(asize < minsize) {
-      asize = (asize >> 1) + asize;
+    if (minsize <= store.length) {
+      return;
     }
-    if(asize > store.length) {
-      store = Arrays.copyOf(store, asize);
+    int asize = store.length;
+    while (asize < minsize) {
+      asize = (asize >>> 1) + asize;
     }
+    final int[] prev = store;
+    store = new int[asize];
+    System.arraycopy(prev, 0, store, 0, size);
+  }
+
+  /**
+   * Grow array by 50%.
+   */
+  private void grow() {
+    final int newsize = store.length + (store.length >>> 1);
+    final int[] prev = store;
+    store = new int[newsize];
+    System.arraycopy(prev, 0, store, 0, size);
   }
 
   @Override
   public boolean addDBIDs(DBIDs ids) {
     ensureSize(size + ids.size());
-    for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) {
+    for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) {
       store[size] = iter.internalGetIndex();
       ++size;
     }
@@ -140,11 +158,11 @@ public class ArrayModifiableIntegerDBIDs implements ArrayModifiableDBIDs, Intege
   @Override
   public boolean removeDBIDs(DBIDs ids) {
     boolean success = false;
-    for(DBIDIter id = ids.iter(); id.valid(); id.advance()) {
+    for (DBIDIter id = ids.iter(); id.valid(); id.advance()) {
       int rm = id.internalGetIndex();
       // TODO: when sorted, use binary search!
-      for(int i = 0; i < size; i++) {
-        if(store[i] == rm) {
+      for (int i = 0; i < size; i++) {
+        if (store[i] == rm) {
           --size;
           store[i] = store[size];
           success = true;
@@ -157,8 +175,8 @@ public class ArrayModifiableIntegerDBIDs implements ArrayModifiableDBIDs, Intege
 
   @Override
   public boolean add(DBIDRef e) {
-    if(size == store.length) {
-      ensureSize(size + 1);
+    if (size == store.length) {
+      grow();
     }
     store[size] = e.internalGetIndex();
     ++size;
@@ -169,8 +187,8 @@ public class ArrayModifiableIntegerDBIDs implements ArrayModifiableDBIDs, Intege
   public boolean remove(DBIDRef o) {
     int rm = o.internalGetIndex();
     // TODO: when sorted, use binary search!
-    for(int i = 0; i < size; i++) {
-      if(store[i] == rm) {
+    for (int i = 0; i < size; i++) {
+      if (store[i] == rm) {
         --size;
         store[i] = store[size];
         return true;
@@ -190,7 +208,7 @@ public class ArrayModifiableIntegerDBIDs implements ArrayModifiableDBIDs, Intege
   public DBID remove(int index) {
     DBID ret = new IntegerDBID(store[index]);
     --size;
-    if(size > 0) {
+    if (size > 0) {
       store[index] = store[size];
     }
     return ret;
@@ -210,8 +228,8 @@ public class ArrayModifiableIntegerDBIDs implements ArrayModifiableDBIDs, Intege
   public boolean contains(DBIDRef o) {
     // TODO: recognize sorted arrays, then use binary search?
     int oid = o.internalGetIndex();
-    for(int i = 0; i < size; i++) {
-      if(store[i] == oid) {
+    for (int i = 0; i < size; i++) {
+      if (store[i] == oid) {
         return true;
       }
     }
@@ -241,7 +259,12 @@ public class ArrayModifiableIntegerDBIDs implements ArrayModifiableDBIDs, Intege
   }
 
   @Override
-  public IntegerDBIDArrayMIter iter() {
+  public Slice slice(int begin, int end) {
+    return new Slice(begin, end);
+  }
+
+  @Override
+  public Itr iter() {
     return new Itr();
   }
 
@@ -303,4 +326,131 @@ public class ArrayModifiableIntegerDBIDs implements ArrayModifiableDBIDs, Intege
       return Integer.toString(internalGetIndex()) + "@" + pos;
     }
   }
+
+  /**
+   * Slice of an array.
+   * 
+   * @author Erich Schubert
+   * 
+   * @apiviz.exclude
+   */
+  private class Slice implements IntegerArrayDBIDs {
+    /**
+     * Slice positions.
+     */
+    final int begin, end;
+
+    /**
+     * Constructor.
+     * 
+     * @param begin Begin, inclusive
+     * @param end End, exclusive
+     */
+    public Slice(int begin, int end) {
+      super();
+      this.begin = begin;
+      this.end = end;
+    }
+
+    @Override
+    public int size() {
+      return end - begin;
+    }
+
+    @Override
+    public boolean contains(DBIDRef o) {
+      // TODO: recognize sorted arrays, then use binary search?
+      int oid = o.internalGetIndex();
+      for (int i = begin; i < end; i++) {
+        if (store[i] == oid) {
+          return true;
+        }
+      }
+      return false;
+    }
+
+    @Override
+    public boolean isEmpty() {
+      return begin == end;
+    }
+
+    @Override
+    public DBID get(int i) {
+      return ArrayModifiableIntegerDBIDs.this.get(begin + i);
+    }
+
+    @Override
+    public void assignVar(int index, DBIDVar var) {
+      ArrayModifiableIntegerDBIDs.this.assignVar(begin + index, var);
+    }
+
+    @Override
+    public int binarySearch(DBIDRef key) {
+      return Arrays.binarySearch(store, begin, end, key.internalGetIndex()) - begin;
+    }
+
+    @Override
+    public SliceItr iter() {
+      return new SliceItr();
+    }
+
+    @Override
+    public Slice slice(int begin, int end) {
+      return new Slice(begin + begin, begin + end);
+    }
+
+    /**
+     * Iterator class.
+     * 
+     * @author Erich Schubert
+     * 
+     * @apiviz.exclude
+     */
+    private class SliceItr implements IntegerDBIDArrayIter {
+      /**
+       * Iterator position.
+       */
+      int pos = begin;
+
+      @Override
+      public int internalGetIndex() {
+        return store[pos];
+      }
+
+      @Override
+      public boolean valid() {
+        return pos < end && pos >= begin;
+      }
+
+      @Override
+      public void advance() {
+        ++pos;
+      }
+
+      @Override
+      public int getOffset() {
+        return pos;
+      }
+
+      @Override
+      public void advance(int count) {
+        pos += count;
+      }
+
+      @Override
+      public void retract() {
+        --pos;
+      }
+
+      @Override
+      public void seek(int off) {
+        pos = off;
+      }
+
+      @Override
+      public String toString() {
+        return Integer.toString(internalGetIndex()) + "@" + pos;
+      }
+    }
+  }
 }
diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/ArrayStaticIntegerDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/ArrayStaticIntegerDBIDs.java
index 4b4b5a42..fcb426ac 100644
--- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/ArrayStaticIntegerDBIDs.java
+++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/ArrayStaticIntegerDBIDs.java
@@ -36,14 +36,12 @@ import de.lmu.ifi.dbs.elki.logging.LoggingUtil;
  * Static (no modifications allowed) set of Database Object IDs.
  * 
  * @author Erich Schubert
- * 
- * @apiviz.has IntegerDBID
  */
 public class ArrayStaticIntegerDBIDs implements IntegerArrayStaticDBIDs {
   /**
    * The actual storage.
    */
-  protected int[] ids;
+  protected int[] store;
 
   /**
    * Constructor.
@@ -52,12 +50,58 @@ public class ArrayStaticIntegerDBIDs implements IntegerArrayStaticDBIDs {
    */
   public ArrayStaticIntegerDBIDs(int... ids) {
     super();
-    this.ids = ids;
+    this.store = ids;
+  }
+
+  @Override
+  public int size() {
+    return store.length;
+  }
+
+  @Override
+  public boolean isEmpty() {
+    return store.length == 0;
+  }
+
+  @Override
+  public boolean contains(DBIDRef o) {
+    final int oid = DBIDUtil.asInteger(o);
+    for (int i = 0; i < store.length; i++) {
+      if (store[i] == oid) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  @Override
+  public DBID get(int i) {
+    return DBIDFactory.FACTORY.importInteger(store[i]);
+  }
+
+  @Override
+  public void assignVar(int i, DBIDVar var) {
+    if (var instanceof IntegerDBIDVar) {
+      ((IntegerDBIDVar) var).internalSetIndex(store[i]);
+    } else {
+      // Much less efficient:
+      var.set(get(i));
+    }
+  }
+
+  @Override
+  public int binarySearch(DBIDRef key) {
+    return Arrays.binarySearch(store, DBIDUtil.asInteger(key));
   }
 
   @Override
-  public IntegerDBIDArrayIter iter() {
-    return new DBIDItr();
+  public Itr iter() {
+    return new Itr();
+  }
+
+  @Override
+  public Slice slice(int begin, int end) {
+    return new Slice(begin, end);
   }
 
   /**
@@ -67,7 +111,7 @@ public class ArrayStaticIntegerDBIDs implements IntegerArrayStaticDBIDs {
    * 
    * @apiviz.exclude
    */
-  protected class DBIDItr implements IntegerDBIDArrayIter {
+  protected class Itr implements IntegerDBIDArrayIter {
     /**
      * Position within array.
      */
@@ -75,7 +119,7 @@ public class ArrayStaticIntegerDBIDs implements IntegerArrayStaticDBIDs {
 
     @Override
     public boolean valid() {
-      return pos < ids.length && pos >= 0;
+      return pos < store.length && pos >= 0;
     }
 
     @Override
@@ -105,12 +149,12 @@ public class ArrayStaticIntegerDBIDs implements IntegerArrayStaticDBIDs {
 
     @Override
     public int internalGetIndex() {
-      return ids[pos];
+      return store[pos];
     }
 
     @Override
     public boolean equals(Object other) {
-      if(other instanceof DBID) {
+      if (other instanceof DBID) {
         LoggingUtil.warning("Programming error detected: DBIDItr.equals(DBID). Use sameDBID()!", new Throwable());
       }
       return super.equals(other);
@@ -122,44 +166,130 @@ public class ArrayStaticIntegerDBIDs implements IntegerArrayStaticDBIDs {
     }
   }
 
-  @Override
-  public int size() {
-    return ids.length;
-  }
+  /**
+   * Slice of an array.
+   * 
+   * @author Erich Schubert
+   * 
+   * @apiviz.exclude
+   */
+  private class Slice implements IntegerArrayDBIDs {
+    /**
+     * Slice positions.
+     */
+    final int begin, end;
 
-  @Override
-  public boolean isEmpty() {
-    return ids.length == 0;
-  }
+    /**
+     * Constructor.
+     * 
+     * @param begin Begin, inclusive
+     * @param end End, exclusive
+     */
+    public Slice(int begin, int end) {
+      super();
+      this.begin = begin;
+      this.end = end;
+    }
 
-  @Override
-  public boolean contains(DBIDRef o) {
-    final int oid = DBIDUtil.asInteger(o);
-    for(int i = 0; i < ids.length; i++) {
-      if(ids[i] == oid) {
-        return true;
+    @Override
+    public int size() {
+      return end - begin;
+    }
+
+    @Override
+    public boolean contains(DBIDRef o) {
+      // TODO: recognize sorted arrays, then use binary search?
+      int oid = o.internalGetIndex();
+      for (int i = begin; i < end; i++) {
+        if (store[i] == oid) {
+          return true;
+        }
       }
+      return false;
     }
-    return false;
-  }
 
-  @Override
-  public DBID get(int i) {
-    return DBIDFactory.FACTORY.importInteger(ids[i]);
-  }
+    @Override
+    public boolean isEmpty() {
+      return begin == end;
+    }
 
-  @Override
-  public void assignVar(int i, DBIDVar var) {
-    if (var instanceof IntegerDBIDVar) {
-      ((IntegerDBIDVar)var).internalSetIndex(ids[i]);
-    } else {
-      // Much less efficient:
-      var.set(get(i));
+    @Override
+    public DBID get(int i) {
+      return ArrayStaticIntegerDBIDs.this.get(begin + i);
     }
-  }
 
-  @Override
-  public int binarySearch(DBIDRef key) {
-    return Arrays.binarySearch(ids, DBIDUtil.asInteger(key));
+    @Override
+    public void assignVar(int index, DBIDVar var) {
+      ArrayStaticIntegerDBIDs.this.assignVar(begin + index, var);
+    }
+
+    @Override
+    public int binarySearch(DBIDRef key) {
+      return Arrays.binarySearch(store, begin, end, key.internalGetIndex()) - begin;
+    }
+
+    @Override
+    public SliceItr iter() {
+      return new SliceItr();
+    }
+
+    @Override
+    public Slice slice(int begin, int end) {
+      return new Slice(begin + begin, begin + end);
+    }
+
+    /**
+     * Iterator class.
+     * 
+     * @author Erich Schubert
+     * 
+     * @apiviz.exclude
+     */
+    private class SliceItr implements IntegerDBIDArrayIter {
+      /**
+       * Iterator position.
+       */
+      int pos = begin;
+
+      @Override
+      public int internalGetIndex() {
+        return store[pos];
+      }
+
+      @Override
+      public boolean valid() {
+        return pos < end && pos >= begin;
+      }
+
+      @Override
+      public void advance() {
+        ++pos;
+      }
+
+      @Override
+      public int getOffset() {
+        return pos;
+      }
+
+      @Override
+      public void advance(int count) {
+        pos += count;
+      }
+
+      @Override
+      public void retract() {
+        --pos;
+      }
+
+      @Override
+      public void seek(int off) {
+        pos = begin + off;
+      }
+
+      @Override
+      public String toString() {
+        return Integer.toString(internalGetIndex()) + "@" + pos;
+      }
+    }
   }
-}
\ No newline at end of file
+}
diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDKNNHeap.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDKNNHeap.java
index 6c88c2d8..96babaa3 100644
--- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDKNNHeap.java
+++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDKNNHeap.java
@@ -90,7 +90,7 @@ public class DoubleDistanceIntegerDBIDKNNHeap implements DoubleDistanceKNNHeap {
   @Override
   @Deprecated
   public DoubleDistance getKNNDistance() {
-    if (heap.size() < k) {
+    if(heap.size() < k) {
       return DoubleDistance.INFINITE_DISTANCE;
     }
     return new DoubleDistance(kdist);
@@ -103,41 +103,92 @@ public class DoubleDistanceIntegerDBIDKNNHeap implements DoubleDistanceKNNHeap {
 
   @Override
   @Deprecated
-  public void add(DoubleDistance distance, DBIDRef id) {
-    add(distance.doubleValue(), id);
+  public void insert(DoubleDistance distance, DBIDRef id) {
+    final double dist = distance.doubleValue();
+    final int iid = id.internalGetIndex();
+    if(heap.size() < k) {
+      heap.add(dist, iid);
+      if(heap.size() >= k) {
+        kdist = heap.peekKey();
+      }
+      return;
+    }
+    // Tied with top:
+    if(dist >= kdist) {
+      if(dist == kdist) {
+        addToTies(iid);
+      }
+      return;
+    }
+    // Old top element: (kdist, previd)
+    updateHeap(dist, iid);
   }
 
   @Override
   @Deprecated
-  public void add(Double distance, DBIDRef id) {
-    add(distance.doubleValue(), id);
+  public void insert(Double distance, DBIDRef id) {
+    final double dist = distance.doubleValue();
+    final int iid = id.internalGetIndex();
+    if(heap.size() < k) {
+      heap.add(dist, iid);
+      if(heap.size() >= k) {
+        kdist = heap.peekKey();
+      }
+      return;
+    }
+    // Tied with top:
+    if(dist >= kdist) {
+      if(dist == kdist) {
+        addToTies(iid);
+      }
+      return;
+    }
+    // Old top element: (kdist, previd)
+    updateHeap(dist, iid);
   }
 
   @Override
-  public final void add(final double distance, final DBIDRef id) {
-    if (distance > kdist) {
-      return;
-    }
+  public final double insert(final double distance, final DBIDRef id) {
     final int iid = id.internalGetIndex();
-    if (heap.size() < k) {
+    if(heap.size() < k) {
       heap.add(distance, iid);
-      if (heap.size() >= k) {
+      if(heap.size() >= k) {
         kdist = heap.peekKey();
       }
-      return;
+      return kdist;
     }
     // Tied with top:
-    if (distance >= kdist) {
-      addToTies(iid);
-      return;
+    if(distance >= kdist) {
+      if(distance == kdist) {
+        addToTies(iid);
+      }
+      return kdist;
     }
     // Old top element: (kdist, previd)
     updateHeap(distance, iid);
+    return kdist;
   }
 
   @Override
-  public void add(DoubleDistanceDBIDPair e) {
-    add(e.doubleDistance(), e);
+  public void insert(final DoubleDistanceDBIDPair e) {
+    final double distance = e.doubleDistance();
+    final int iid = e.internalGetIndex();
+    if(heap.size() < k) {
+      heap.add(distance, iid);
+      if(heap.size() >= k) {
+        kdist = heap.peekKey();
+      }
+      return;
+    }
+    // Tied with top:
+    if(distance >= kdist) {
+      if(distance == kdist) {
+        addToTies(iid);
+      }
+      return;
+    }
+    // Old top element: (kdist, previd)
+    updateHeap(distance, iid);
   }
 
   /**
@@ -152,9 +203,10 @@ public class DoubleDistanceIntegerDBIDKNNHeap implements DoubleDistanceKNNHeap {
     heap.replaceTopElement(distance, iid);
     kdist = heap.peekKey();
     // If the kdist improved, zap ties.
-    if (kdist < prevdist) {
+    if(kdist < prevdist) {
       numties = 0;
-    } else {
+    }
+    else {
       addToTies(previd);
     }
   }
@@ -165,7 +217,7 @@ public class DoubleDistanceIntegerDBIDKNNHeap implements DoubleDistanceKNNHeap {
    * @param id Id to add
    */
   private final void addToTies(int id) {
-    if (ties.length == numties) {
+    if(ties.length == numties) {
       ties = Arrays.copyOf(ties, (ties.length << 1) + 1); // grow.
     }
     ties[numties] = id;
@@ -175,10 +227,11 @@ public class DoubleDistanceIntegerDBIDKNNHeap implements DoubleDistanceKNNHeap {
   @Override
   public DoubleDistanceIntegerDBIDPair poll() {
     final DoubleDistanceIntegerDBIDPair ret;
-    if (numties > 0) {
+    if(numties > 0) {
       ret = new DoubleDistanceIntegerDBIDPair(kdist, ties[numties - 1]);
       --numties;
-    } else {
+    }
+    else {
       ret = new DoubleDistanceIntegerDBIDPair(heap.peekKey(), heap.peekValue());
       heap.poll();
     }
@@ -189,16 +242,17 @@ public class DoubleDistanceIntegerDBIDKNNHeap implements DoubleDistanceKNNHeap {
    * Pop the topmost element.
    */
   protected void pop() {
-    if (numties > 0) {
+    if(numties > 0) {
       --numties;
-    } else {
+    }
+    else {
       heap.poll();
     }
   }
 
   @Override
   public DoubleDistanceIntegerDBIDPair peek() {
-    if (numties > 0) {
+    if(numties > 0) {
       return new DoubleDistanceIntegerDBIDPair(kdist, ties[numties - 1]);
     }
     return new DoubleDistanceIntegerDBIDPair(heap.peekKey(), heap.peekValue());
@@ -222,7 +276,21 @@ public class DoubleDistanceIntegerDBIDKNNHeap implements DoubleDistanceKNNHeap {
 
   @Override
   public DoubleDistanceIntegerDBIDKNNList toKNNList() {
-    return new DoubleDistanceIntegerDBIDKNNList(this);
+    final int hsize = heap.size();
+    DoubleDistanceIntegerDBIDKNNList ret = new DoubleDistanceIntegerDBIDKNNList(k, hsize + numties);
+    // Add ties:
+    for(int i = 0; i < numties; i++) {
+      ret.dists[hsize + i] = kdist;
+      ret.ids[hsize + i] = ties[i];
+    }
+    for(int j = hsize - 1; j >= 0; j--) {
+      ret.dists[j] = heap.peekKey();
+      ret.ids[j] = heap.peekValue();
+      heap.poll();
+    }
+    ret.size = hsize + numties;
+    ret.sort();
+    return ret;
   }
 
   /**
@@ -231,9 +299,10 @@ public class DoubleDistanceIntegerDBIDKNNHeap implements DoubleDistanceKNNHeap {
    * @return distance
    */
   protected double peekDistance() {
-    if (numties > 0) {
+    if(numties > 0) {
       return kdist;
-    } else {
+    }
+    else {
       return heap.peekKey();
     }
   }
@@ -244,7 +313,7 @@ public class DoubleDistanceIntegerDBIDKNNHeap implements DoubleDistanceKNNHeap {
    * @return internal id
    */
   protected int peekInternalDBID() {
-    if (numties > 0) {
+    if(numties > 0) {
       return ties[numties - 1];
     }
     return heap.peekValue();
diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDKNNList.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDKNNList.java
index a74497e8..f6515d88 100644
--- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDKNNList.java
+++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDKNNList.java
@@ -22,47 +22,21 @@ package de.lmu.ifi.dbs.elki.database.ids.integer;
  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.Arrays;
-
-import de.lmu.ifi.dbs.elki.database.ids.DBIDRef;
-import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceDBIDPair;
 import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceDBIDListIter;
 import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceKNNList;
-import de.lmu.ifi.dbs.elki.database.ids.distance.ModifiableDoubleDistanceDBIDList;
 import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance;
 
 /**
- * Class to store double distance, integer DBID results.
+ * kNN list, but without automatic sorting. Use with care, as others may expect
+ * the results to be sorted!
  * 
  * @author Erich Schubert
- * 
- * @apiviz.uses DoubleIntegerArrayQuickSort
  */
-public class DoubleDistanceIntegerDBIDKNNList implements ModifiableDoubleDistanceDBIDList, DoubleDistanceKNNList, IntegerDBIDs {
-  /**
-   * Initial size allocation.
-   */
-  private static final int INITIAL_SIZE = 21;
-
+public class DoubleDistanceIntegerDBIDKNNList extends DoubleDistanceIntegerDBIDList implements DoubleDistanceKNNList {
   /**
    * The k value this list was generated for.
    */
-  int k;
-
-  /**
-   * The size
-   */
-  int size;
-
-  /**
-   * Distance values
-   */
-  double[] dists;
-
-  /**
-   * DBIDs
-   */
-  int[] ids;
+  final int k;
 
   /**
    * Constructor.
@@ -70,8 +44,6 @@ public class DoubleDistanceIntegerDBIDKNNList implements ModifiableDoubleDistanc
   public DoubleDistanceIntegerDBIDKNNList() {
     super();
     this.k = -1;
-    this.dists = new double[INITIAL_SIZE];
-    this.ids = new int[INITIAL_SIZE];
   }
 
   /**
@@ -80,75 +52,20 @@ public class DoubleDistanceIntegerDBIDKNNList implements ModifiableDoubleDistanc
    * @param k K parameter
    * @param size Actual size
    */
-  public DoubleDistanceIntegerDBIDKNNList(int k, int size) {
-    super();
+  public DoubleDistanceIntegerDBIDKNNList(final int k, int size) {
+    super(size);
     this.k = k;
-    if (size > 0) {
-      this.dists = new double[size];
-      this.ids = new int[size];
-    } else {
-      this.dists = new double[INITIAL_SIZE];
-      this.ids = new int[INITIAL_SIZE];
-    }
-  }
-
-  /**
-   * Constructor from heap.
-   * 
-   * @param heap KNN heap.
-   */
-  public DoubleDistanceIntegerDBIDKNNList(DoubleDistanceIntegerDBIDKNNHeap heap) {
-    super();
-    this.k = heap.getK();
-    this.size = heap.size();
-    this.dists = new double[size];
-    this.ids = new int[size];
-    for (int i = size - 1; i >= 0; i--) {
-      dists[i] = heap.peekDistance();
-      ids[i] = heap.peekInternalDBID();
-      heap.pop();
-    }
-  }
-
-  @Override
-  public DoubleDistanceIntegerDBIDListIter iter() {
-    return new Itr();
-  }
-
-  @Override
-  public boolean contains(DBIDRef o) {
-    final int q = o.internalGetIndex();
-    for (int i = 0; i < size; i++) {
-      if (q == ids[i]) {
-        return true;
-      }
-    }
-    return false;
-  }
-
-  @Override
-  public boolean isEmpty() {
-    return size == 0;
-  }
-
-  @Override
-  public int size() {
-    return size;
   }
 
   @Override
   public int getK() {
-    if (k <= 0) {
-      return size - 1;
-    }
     return k;
   }
 
-  @Override
-  public DoubleDistanceIntegerDBIDPair get(int index) {
-    return new DoubleDistanceIntegerDBIDPair(dists[index], ids[index]);
-  }
-
+  /**
+   * @deprecated Since you know this is a double distance heap, use
+   *             {@link #doubleKNNDistance()}
+   */
   @Override
   @Deprecated
   public DoubleDistance getKNNDistance() {
@@ -157,65 +74,7 @@ public class DoubleDistanceIntegerDBIDKNNList implements ModifiableDoubleDistanc
 
   @Override
   public double doubleKNNDistance() {
-    if (k <= 0) {
-      return dists[size - 1];
-    }
-    if (size < k) {
-      return Double.POSITIVE_INFINITY;
-    }
-    return dists[k - 1];
-  }
-
-  /**
-   * Add an entry, consisting of distance and internal index.
-   * 
-   * @param dist Distance
-   * @param id Internal index
-   */
-  protected void add(double dist, int id) {
-    if (size == dists.length) {
-      final int newlength = (dists.length << 1) + 1;
-      dists = Arrays.copyOf(dists, newlength);
-      ids = Arrays.copyOf(ids, newlength);
-    }
-    dists[size] = dist;
-    ids[size] = id;
-    ++size;
-  }
-
-  @Override
-  @Deprecated
-  public void add(DoubleDistance dist, DBIDRef id) {
-    add(dist.doubleValue(), id);
-  }
-
-  @Override
-  public void add(double dist, DBIDRef id) {
-    add(dist, id.internalGetIndex());
-  }
-
-  @Override
-  public void add(DoubleDistanceDBIDPair pair) {
-    add(pair.doubleDistance(), pair.internalGetIndex());
-  }
-
-  @Override
-  public void sort() {
-    DoubleIntegerArrayQuickSort.sort(dists, ids, 0, size);
-  }
-
-  /**
-   * Reverse the list.
-   */
-  protected void reverse() {
-    for (int i = 0, j = size - 1; i < j; i++, j--) {
-      double tmpd = dists[j];
-      dists[j] = dists[i];
-      dists[i] = tmpd;
-      int tmpi = ids[j];
-      ids[j] = ids[i];
-      ids[i] = tmpi;
-    }
+    return (size >= k) ? dists[k - 1] : Double.POSITIVE_INFINITY;
   }
 
   @Override
@@ -232,67 +91,4 @@ public class DoubleDistanceIntegerDBIDKNNList implements ModifiableDoubleDistanc
     buf.append(']');
     return buf.toString();
   }
-
-  /**
-   * List iterator.
-   * 
-   * @author Erich Schubert
-   * 
-   * @apiviz.exclude
-   */
-  private class Itr implements DoubleDistanceIntegerDBIDListIter {
-    int offset = 0;
-
-    @Override
-    public boolean valid() {
-      return offset < size;
-    }
-
-    @Override
-    public void advance() {
-      ++offset;
-    }
-
-    @Override
-    public int getOffset() {
-      return offset;
-    }
-
-    @Override
-    public void advance(int count) {
-      offset += count;
-    }
-
-    @Override
-    public void retract() {
-      offset--;
-    }
-
-    @Override
-    public void seek(int off) {
-      offset = off;
-    }
-
-    @Override
-    public int internalGetIndex() {
-      return ids[offset];
-    }
-
-    @Override
-    public double doubleDistance() {
-      return dists[offset];
-    }
-
-    @Override
-    public DoubleDistanceDBIDPair getDistancePair() {
-      return new DoubleDistanceIntegerDBIDPair(dists[offset], ids[offset]);
-    }
-
-    @Override
-    @Deprecated
-    public DoubleDistance getDistance() {
-      return new DoubleDistance(dists[offset]);
-    }
-
-  }
 }
diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDKNNListHeap.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDList.java
index ffc2266e..0db0204c 100644
--- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDKNNListHeap.java
+++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDList.java
@@ -22,13 +22,11 @@ package de.lmu.ifi.dbs.elki.database.ids.integer;
  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.Arrays;
 
 import de.lmu.ifi.dbs.elki.database.ids.DBIDRef;
 import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceDBIDListIter;
 import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceDBIDPair;
-import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceKNNHeap;
-import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceKNNList;
+import de.lmu.ifi.dbs.elki.database.ids.distance.ModifiableDoubleDistanceDBIDList;
 import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance;
 
 /**
@@ -38,11 +36,11 @@ import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance;
  * 
  * @apiviz.uses DoubleIntegerArrayQuickSort
  */
-public class DoubleDistanceIntegerDBIDKNNListHeap implements DoubleDistanceKNNHeap, DoubleDistanceKNNList, IntegerDBIDs {
+public class DoubleDistanceIntegerDBIDList implements ModifiableDoubleDistanceDBIDList, IntegerDBIDs {
   /**
-   * The k value this list was generated for.
+   * Initial size allocation.
    */
-  int k;
+  private static final int INITIAL_SIZE = 21;
 
   /**
    * The size
@@ -60,28 +58,44 @@ public class DoubleDistanceIntegerDBIDKNNListHeap implements DoubleDistanceKNNHe
   int[] ids;
 
   /**
+   * Empty.
+   */
+  private static final double[] EMPTY_DISTS = new double[0];
+
+  /**
+   * Empty.
+   */
+  private static final int[] EMPTY_IDS = new int[0];
+
+  /**
+   * Constructor.
+   */
+  public DoubleDistanceIntegerDBIDList() {
+    dists = EMPTY_DISTS;
+    ids = EMPTY_IDS;
+  }
+
+  /**
    * Constructor.
    * 
-   * @param k K parameter
+   * @param size Initial size
    */
-  public DoubleDistanceIntegerDBIDKNNListHeap(int k) {
-    super();
-    this.k = k;
-    this.size = 0;
-    this.dists = new double[k + 1];
-    this.ids = new int[k + 1];
+  public DoubleDistanceIntegerDBIDList(int size) {
+    this.dists = new double[size];
+    this.ids = new int[size];
+    // This is default anyway: this.size = 0;
   }
 
   @Override
-  public DoubleDistanceIntegerDBIDListIter iter() {
+  public Itr iter() {
     return new Itr();
   }
 
   @Override
   public boolean contains(DBIDRef o) {
     final int q = o.internalGetIndex();
-    for(int i = 0; i < size; i++) {
-      if(q == ids[i]) {
+    for (int i = 0; i < size; i++) {
+      if (q == ids[i]) {
         return true;
       }
     }
@@ -99,151 +113,123 @@ public class DoubleDistanceIntegerDBIDKNNListHeap implements DoubleDistanceKNNHe
   }
 
   @Override
-  public int getK() {
-    return k;
-  }
-
-  @Override
   public DoubleDistanceIntegerDBIDPair get(int index) {
     return new DoubleDistanceIntegerDBIDPair(dists[index], ids[index]);
   }
 
-  @Override
-  @Deprecated
-  public DoubleDistance getKNNDistance() {
-    return new DoubleDistance(doubleKNNDistance());
-  }
-
-  @Override
-  public double doubleKNNDistance() {
-    if(size < k) {
-      return Double.POSITIVE_INFINITY;
-    }
-    return dists[k - 1];
-  }
-
   /**
    * Add an entry, consisting of distance and internal index.
    * 
    * @param dist Distance
    * @param id Internal index
    */
-  protected void append(double dist, int id) {
-    ensureSize(size + 1);
+  protected void addInternal(double dist, int id) {
+    if (size == dists.length) {
+      grow();
+    }
     dists[size] = dist;
     ids[size] = id;
     ++size;
   }
 
   /**
-   * Add a new element to the heap/list.
-   * 
-   * @param dist Distance
-   * @param id Object ID
+   * Grow the data storage.
    */
-  protected void add(double dist, int id) {
-    if(size < k) {
-      dists[size] = dist;
-      ids[size] = id;
-      ++size;
-      if(size == k) {
-        sort();
-      }
-      return;
-    }
-    if (dist > dists[size - 1]) {
+  protected void grow() {
+    if (dists == EMPTY_DISTS) {
+      dists = new double[INITIAL_SIZE];
+      ids = new int[INITIAL_SIZE];
       return;
     }
-    // Ensure we have enough space.
-    ensureSize(size + 1);
-    // Insertion sort:
-    int pos = size;
-    while(pos > 0 && dists[pos - 1] > dist) {
-      dists[pos] = dists[pos - 1];
-      ids[pos] = ids[pos - 1];
-      --pos;
-    }
-    dists[pos] = dist;
-    ids[pos] = id;
-    ++size;
-    // Truncate if necessary:
-    if(dists[k] > dists[k - 1]) {
-      size = k;
-    }
-  }
-
-  /**
-   * Ensure we have enough space.
-   * 
-   * @param size Desired size
-   */
-  private void ensureSize(int size) {
-    if(size > dists.length) {
-      final int newlength = Math.max(size, (dists.length << 1) + 1);
-      dists = Arrays.copyOf(dists, newlength);
-      ids = Arrays.copyOf(ids, newlength);
-    }
+    final int len = dists.length;
+    final int newlength = len + (len >> 1);
+    double[] odists = dists;
+    dists = new double[newlength];
+    System.arraycopy(odists, 0, dists, 0, odists.length);
+    int[] oids = ids;
+    ids = new int[newlength];
+    System.arraycopy(oids, 0, ids, 0, oids.length);
   }
 
   @Override
   @Deprecated
   public void add(DoubleDistance dist, DBIDRef id) {
-    add(dist.doubleValue(), id);
-  }
-
-  @Override
-  @Deprecated
-  public void add(Double dist, DBIDRef id) {
-    add(dist.doubleValue(), id);
+    addInternal(dist.doubleValue(), id.internalGetIndex());
   }
 
   @Override
   public void add(double dist, DBIDRef id) {
-    add(dist, id.internalGetIndex());
+    addInternal(dist, id.internalGetIndex());
   }
 
   @Override
   public void add(DoubleDistanceDBIDPair pair) {
-    add(pair.doubleDistance(), pair.internalGetIndex());
-  }
-
-  /**
-   * Sort the current contents of the list.
-   */
-  protected void sort() {
-    DoubleIntegerArrayQuickSort.sort(dists, ids, 0, size);
+    addInternal(pair.doubleDistance(), pair.internalGetIndex());
   }
 
   @Override
   public void clear() {
     size = 0;
-    Arrays.fill(dists, Double.NaN);
-    Arrays.fill(ids, -1);
+    // TODO: put NaN/-1 everywhere, or don't care?
   }
 
   @Override
-  public DoubleDistanceIntegerDBIDPair poll() {
-    return new DoubleDistanceIntegerDBIDPair(dists[k], ids[k]);
+  public void sort() {
+    DoubleIntegerArrayQuickSort.sort(dists, ids, 0, size);
   }
 
-  @Override
-  public DoubleDistanceIntegerDBIDPair peek() {
-    return new DoubleDistanceIntegerDBIDPair(dists[k], ids[k]);
+  /**
+   * Reverse the list.
+   */
+  protected void reverse() {
+    for (int i = 0, j = size - 1; i < j; i++, j--) {
+      double tmpd = dists[j];
+      dists[j] = dists[i];
+      dists[i] = tmpd;
+      int tmpi = ids[j];
+      ids[j] = ids[i];
+      ids[i] = tmpi;
+    }
   }
 
-  @Override
-  public DoubleDistanceKNNList toKNNList() {
-    return this;
+  /**
+   * Truncate the list to the given size.
+   * 
+   * @param newsize New size
+   */
+  public void truncate(int newsize) {
+    if (newsize < size) {
+      double[] odists = dists;
+      dists = new double[newsize];
+      System.arraycopy(odists, 0, dists, 0, newsize);
+      int[] oids = ids;
+      ids = new int[newsize];
+      System.arraycopy(oids, 0, ids, 0, newsize);
+      size = newsize;
+    }
+  }
+
+  /**
+   * Get the distance of the object at position pos.
+   * 
+   * Usually, you should be using an iterator instead. This part of the API is
+   * not stable.
+   * 
+   * @param pos Position
+   * @return Double distance.
+   */
+  public double getDoubleDistance(int pos) {
+    return dists[pos];
   }
 
   @Override
   public String toString() {
     StringBuilder buf = new StringBuilder();
-    buf.append("kNNListHeap[");
-    for(DoubleDistanceDBIDListIter iter = this.iter(); iter.valid();) {
+    buf.append("DistanceDBIDList[");
+    for (DoubleDistanceDBIDListIter iter = this.iter(); iter.valid();) {
       buf.append(iter.doubleDistance()).append(':').append(iter.internalGetIndex());
       iter.advance();
-      if(iter.valid()) {
+      if (iter.valid()) {
         buf.append(',');
       }
     }
@@ -259,8 +245,18 @@ public class DoubleDistanceIntegerDBIDKNNListHeap implements DoubleDistanceKNNHe
    * @apiviz.exclude
    */
   private class Itr implements DoubleDistanceIntegerDBIDListIter {
+    /**
+     * Current offset.
+     */
     int offset = 0;
 
+    /**
+     * Constructor.
+     */
+    private Itr() {
+      super();
+    }
+
     @Override
     public boolean valid() {
       return offset < size;
@@ -283,7 +279,7 @@ public class DoubleDistanceIntegerDBIDKNNListHeap implements DoubleDistanceKNNHe
 
     @Override
     public void retract() {
-      offset--;
+      --offset;
     }
 
     @Override
diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDPairKNNListHeap.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDPairKNNListHeap.java
new file mode 100644
index 00000000..aa0a9739
--- /dev/null
+++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDPairKNNListHeap.java
@@ -0,0 +1,339 @@
+package de.lmu.ifi.dbs.elki.database.ids.integer;
+
+/*
+ This file is part of ELKI:
+ Environment for Developing KDD-Applications Supported by Index-Structures
+
+ Copyright (C) 2013
+ 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 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.DoubleDistanceDBIDListIter;
+import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceDBIDPair;
+import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceKNNHeap;
+import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceKNNList;
+import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance;
+
+/**
+ * Finalized KNN List.
+ * 
+ * @author Erich Schubert
+ * 
+ * @apiviz.composedOf DoubleDistanceDBIDPair
+ * @apiviz.has DoubleDistanceDBIDListIter
+ */
+public class DoubleDistanceIntegerDBIDPairKNNListHeap implements DoubleDistanceKNNList, DoubleDistanceKNNHeap {
+  /**
+   * The value of k this was materialized for.
+   */
+  private final int k;
+
+  /**
+   * The actual data array.
+   */
+  private DoubleDistanceIntegerDBIDPair[] data;
+
+  /**
+   * Current size
+   */
+  private int size;
+
+  /**
+   * Constructor.
+   * 
+   * @param k K parameter
+   */
+  public DoubleDistanceIntegerDBIDPairKNNListHeap(int k) {
+    super();
+    this.data = new DoubleDistanceIntegerDBIDPair[k + 5];
+    this.k = k;
+    this.size = 0;
+  }
+
+  @Override
+  public void clear() {
+    for(int i = 0; i < size; i++) {
+      data[i] = null; // discard
+    }
+    size = 0;
+  }
+
+  @Override
+  public double insert(double distance, DBIDRef id) {
+    final int kminus1 = k - 1;
+    if(size < k || distance <= data[kminus1].doubleDistance()) {
+      // Ensure we have enough space.
+      if(size > data.length) {
+        grow();
+      }
+      insertionSort(new DoubleDistanceIntegerDBIDPair(distance, id.internalGetIndex()));
+      // Truncate if necessary:
+      if(size > k && data[k].doubleDistance() > data[kminus1].doubleDistance()) {
+        truncate();
+      }
+    }
+    return (size < k) ? Double.POSITIVE_INFINITY : get(kminus1).doubleDistance();
+  }
+
+  private void truncate() {
+    for(int i = k; i < size; i++) {
+      data[i] = null; // discard
+    }
+    size = k;
+  }
+
+  @Override
+  @Deprecated
+  public void insert(Double distance, DBIDRef id) {
+    final int kminus1 = k - 1;
+    if(size < k || distance.doubleValue() <= data[kminus1].doubleDistance()) {
+      // Ensure we have enough space.
+      if(size > data.length) {
+        grow();
+      }
+      insertionSort(new DoubleDistanceIntegerDBIDPair(distance.doubleValue(), id.internalGetIndex()));
+      // Truncate if necessary:
+      if(size > k && data[k].doubleDistance() > data[kminus1].doubleDistance()) {
+        truncate();
+      }
+    }
+  }
+
+  @Override
+  @Deprecated
+  public void insert(DoubleDistance dist, DBIDRef id) {
+    final int kminus1 = k - 1;
+    if(size < k || dist.doubleValue() <= data[kminus1].doubleDistance()) {
+      // Ensure we have enough space.
+      if(size > data.length) {
+        grow();
+      }
+      insertionSort(new DoubleDistanceIntegerDBIDPair(dist.doubleValue(), id.internalGetIndex()));
+      // Truncate if necessary:
+      if(size > k && data[k].doubleDistance() > data[kminus1].doubleDistance()) {
+        truncate();
+      }
+    }
+  }
+
+  @Override
+  public void insert(DoubleDistanceDBIDPair e) {
+    final int kminus1 = k - 1;
+    final double dist = e.doubleDistance();
+    if(size < k || dist <= data[kminus1].doubleDistance()) {
+      // Ensure we have enough space.
+      if(size > data.length) {
+        grow();
+      }
+      if(e instanceof DoubleDistanceIntegerDBIDPair) {
+        insertionSort((DoubleDistanceIntegerDBIDPair) e);
+      }
+      else {
+        insertionSort(new DoubleDistanceIntegerDBIDPair(dist, e.internalGetIndex()));
+      }
+      // Truncate if necessary:
+      if(size > k && data[k].doubleDistance() > data[kminus1].doubleDistance()) {
+        truncate();
+      }
+    }
+  }
+
+  /**
+   * Perform insertion sort.
+   * 
+   * @param obj Object to insert
+   */
+  private void insertionSort(DoubleDistanceIntegerDBIDPair obj) {
+    // Insertion sort:
+    int pos = size;
+    while(pos > 0) {
+      final int prev = pos - 1;
+      DoubleDistanceIntegerDBIDPair pobj = data[prev];
+      if(pobj.doubleDistance() <= obj.doubleDistance()) {
+        break;
+      }
+      data[pos] = pobj;
+      pos = prev;
+    }
+    data[pos] = obj;
+    ++size;
+  }
+
+  private void grow() {
+    final DoubleDistanceIntegerDBIDPair[] old = data;
+    data = new DoubleDistanceIntegerDBIDPair[data.length + (data.length >> 1)];
+    System.arraycopy(old, 0, data, 0, old.length);
+  }
+
+  @Override
+  public DoubleDistanceIntegerDBIDPair poll() {
+    assert (size > 0);
+    return data[size--];
+  }
+
+  @Override
+  public DoubleDistanceIntegerDBIDPair peek() {
+    assert (size > 0);
+    return data[size - 1];
+  }
+
+  @Override
+  public DoubleDistanceKNNList toKNNList() {
+    return this;
+  }
+
+  @Override
+  public int getK() {
+    return k;
+  }
+
+  @Override
+  @Deprecated
+  public DoubleDistance getKNNDistance() {
+    if(size < k) {
+      return DoubleDistance.INFINITE_DISTANCE;
+    }
+    return get(k - 1).getDistance();
+  }
+
+  @Override
+  public double doubleKNNDistance() {
+    if(size < k) {
+      return Double.POSITIVE_INFINITY;
+    }
+    return get(k - 1).doubleDistance();
+  }
+
+  @Override
+  public String toString() {
+    StringBuilder buf = new StringBuilder();
+    buf.append("kNNList[");
+    for(DoubleDistanceDBIDListIter iter = this.iter(); iter.valid();) {
+      buf.append(iter.doubleDistance()).append(':').append(DBIDUtil.toString(iter));
+      iter.advance();
+      if(iter.valid()) {
+        buf.append(',');
+      }
+    }
+    buf.append(']');
+    return buf.toString();
+  }
+
+  @Override
+  public DoubleDistanceIntegerDBIDPair get(int index) {
+    return data[index];
+  }
+
+  @Override
+  public DoubleDistanceIntegerDBIDListIter iter() {
+    return new Itr();
+  }
+
+  @Override
+  public int size() {
+    return size;
+  }
+
+  @Override
+  public boolean contains(DBIDRef o) {
+    for(DBIDIter iter = iter(); iter.valid(); iter.advance()) {
+      if(DBIDUtil.equal(iter, o)) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  @Override
+  public boolean isEmpty() {
+    return size == 0;
+  }
+
+  /**
+   * Iterator.
+   * 
+   * @author Erich Schubert
+   * 
+   * @apiviz.exclude
+   */
+  private class Itr implements DoubleDistanceIntegerDBIDListIter {
+    /**
+     * Cursor position.
+     */
+    private int pos = 0;
+
+    @Override
+    public int internalGetIndex() {
+      return get(pos).internalGetIndex();
+    }
+
+    @Override
+    public boolean valid() {
+      return pos < size;
+    }
+
+    @Override
+    public void advance() {
+      pos++;
+    }
+
+    /**
+     * {@inheritDoc}
+     * 
+     * @deprecated use {@link #doubleDistance}!
+     */
+    @Override
+    @Deprecated
+    public DoubleDistance getDistance() {
+      return get(pos).getDistance();
+    }
+
+    @Override
+    public double doubleDistance() {
+      return get(pos).doubleDistance();
+    }
+
+    @Override
+    public DoubleDistanceIntegerDBIDPair getDistancePair() {
+      return get(pos);
+    }
+
+    @Override
+    public int getOffset() {
+      return pos;
+    }
+
+    @Override
+    public void advance(int count) {
+      pos += count;
+    }
+
+    @Override
+    public void retract() {
+      --pos;
+    }
+
+    @Override
+    public void seek(int off) {
+      pos = off;
+    }
+  }
+}
diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDPairList.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDPairList.java
new file mode 100644
index 00000000..5b33d3f9
--- /dev/null
+++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDPairList.java
@@ -0,0 +1,234 @@
+package de.lmu.ifi.dbs.elki.database.ids.integer;
+
+/*
+ This file is part of ELKI:
+ Environment for Developing KDD-Applications Supported by Index-Structures
+
+ Copyright (C) 2013
+ 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.Arrays;
+
+import de.lmu.ifi.dbs.elki.database.ids.DBIDRef;
+import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceDBIDListIter;
+import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceDBIDPair;
+import de.lmu.ifi.dbs.elki.database.ids.distance.ModifiableDoubleDistanceDBIDList;
+import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DistanceDBIDResultUtil;
+import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance;
+
+/**
+ * Class to store double distance, integer DBID results.
+ * 
+ * @author Erich Schubert
+ */
+public class DoubleDistanceIntegerDBIDPairList implements ModifiableDoubleDistanceDBIDList, IntegerDBIDs {
+  /**
+   * The size
+   */
+  int size;
+
+  /**
+   * Distance values
+   */
+  DoubleDistanceIntegerDBIDPair[] data;
+
+  /**
+   * Constructor.
+   */
+  public DoubleDistanceIntegerDBIDPairList() {
+    super();
+    this.data = new DoubleDistanceIntegerDBIDPair[21];
+  }
+
+  /**
+   * Constructor.
+   * 
+   * @param size Initial size
+   */
+  public DoubleDistanceIntegerDBIDPairList(int size) {
+    super();
+    if (size > 0) {
+      size = 21;
+    }
+    this.data = new DoubleDistanceIntegerDBIDPair[size];
+  }
+
+  @Override
+  public DoubleDistanceIntegerDBIDListIter iter() {
+    return new Itr();
+  }
+
+  @Override
+  public boolean contains(DBIDRef o) {
+    final int q = o.internalGetIndex();
+    for (int i = 0; i < size; i++) {
+      if (q == data[i].internalGetIndex()) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  @Override
+  public boolean isEmpty() {
+    return size == 0;
+  }
+
+  @Override
+  public int size() {
+    return size;
+  }
+
+  @Override
+  public DoubleDistanceIntegerDBIDPair get(int index) {
+    return data[index];
+  }
+
+  /**
+   * Add an entry, consisting of distance and internal index.
+   * 
+   * @param pair entry
+   */
+  protected void addInternal(DoubleDistanceIntegerDBIDPair pair) {
+    if (size == data.length) {
+      DoubleDistanceIntegerDBIDPair[] old = data;
+      data = new DoubleDistanceIntegerDBIDPair[(data.length << 1) + 1];
+      System.arraycopy(old, 0, data, 0, old.length);
+    }
+    data[size++] = pair;
+  }
+
+  @Override
+  @Deprecated
+  public void add(DoubleDistance dist, DBIDRef id) {
+    add(dist.doubleValue(), id);
+  }
+
+  @Override
+  public void add(double dist, DBIDRef id) {
+    addInternal(new DoubleDistanceIntegerDBIDPair(dist, id.internalGetIndex()));
+  }
+
+  @Override
+  public void add(DoubleDistanceDBIDPair pair) {
+    if (pair instanceof DoubleDistanceIntegerDBIDPair) {
+      addInternal((DoubleDistanceIntegerDBIDPair) pair);
+    } else {
+      addInternal(new DoubleDistanceIntegerDBIDPair(pair.doubleDistance(), pair.internalGetIndex()));
+    }
+  }
+
+  @Override
+  public void clear() {
+    Arrays.fill(data, null);
+    size = 0;
+  }
+
+  @Override
+  public void sort() {
+    Arrays.sort(data, 0, size, DistanceDBIDResultUtil.distanceComparator());
+  }
+
+  /**
+   * Reverse the list.
+   */
+  protected void reverse() {
+    for (int i = 0, j = size - 1; i < j; i++, j--) {
+      DoubleDistanceIntegerDBIDPair tmpd = data[j];
+      data[j] = data[i];
+      data[i] = tmpd;
+    }
+  }
+
+  @Override
+  public String toString() {
+    StringBuilder buf = new StringBuilder();
+    buf.append("kNNList[");
+    for (DoubleDistanceDBIDListIter iter = this.iter(); iter.valid();) {
+      buf.append(iter.doubleDistance()).append(':').append(iter.internalGetIndex());
+      iter.advance();
+      if (iter.valid()) {
+        buf.append(',');
+      }
+    }
+    buf.append(']');
+    return buf.toString();
+  }
+
+  /**
+   * List iterator.
+   * 
+   * @author Erich Schubert
+   * 
+   * @apiviz.exclude
+   */
+  private class Itr implements DoubleDistanceIntegerDBIDListIter {
+    int offset = 0;
+
+    @Override
+    public boolean valid() {
+      return offset < size;
+    }
+
+    @Override
+    public void advance() {
+      ++offset;
+    }
+
+    @Override
+    public int getOffset() {
+      return offset;
+    }
+
+    @Override
+    public void advance(int count) {
+      offset += count;
+    }
+
+    @Override
+    public void retract() {
+      offset--;
+    }
+
+    @Override
+    public void seek(int off) {
+      offset = off;
+    }
+
+    @Override
+    public int internalGetIndex() {
+      return data[offset].internalGetIndex();
+    }
+
+    @Override
+    public double doubleDistance() {
+      return data[offset].doubleDistance();
+    }
+
+    @Override
+    public DoubleDistanceDBIDPair getDistancePair() {
+      return data[offset];
+    }
+
+    @Override
+    @Deprecated
+    public DoubleDistance getDistance() {
+      return new DoubleDistance(data[offset].doubleDistance());
+    }
+  }
+}
diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDSortedKNNList.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDSortedKNNList.java
new file mode 100644
index 00000000..c4c60bc0
--- /dev/null
+++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDSortedKNNList.java
@@ -0,0 +1,157 @@
+package de.lmu.ifi.dbs.elki.database.ids.integer;
+
+/*
+ This file is part of ELKI:
+ Environment for Developing KDD-Applications Supported by Index-Structures
+
+ Copyright (C) 2013
+ 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 de.lmu.ifi.dbs.elki.database.ids.DBIDRef;
+import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceDBIDListIter;
+import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceDBIDPair;
+import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceKNNHeap;
+import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceKNNList;
+import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance;
+
+/**
+ * Track the k nearest neighbors, with insertion sort to ensure the correct
+ * order.
+ * 
+ * @author Erich Schubert
+ */
+public class DoubleDistanceIntegerDBIDSortedKNNList extends DoubleDistanceIntegerDBIDKNNList implements DoubleDistanceKNNHeap {
+  /**
+   * Constructor.
+   * 
+   * @param k K parameter
+   */
+  public DoubleDistanceIntegerDBIDSortedKNNList(int k) {
+    super(k, k + 11);
+  }
+
+  /**
+   * Add a new element to the heap/list.
+   * 
+   * @param dist Distance
+   * @param id Object ID
+   */
+  @Override
+  protected final void addInternal(final double dist, final int id) {
+    if(size >= k && dist > dists[k - 1]) {
+      return;
+    }
+    insertionSort(dist, id);
+  }
+
+  /**
+   * Insertion sort a single object.
+   * 
+   * @param dist New distance
+   * @param id New id
+   */
+  private void insertionSort(final double dist, final int id) {
+    // Ensure we have enough space.
+    if(size == dists.length) {
+      grow();
+    }
+    int pos = size;
+    while(pos > 0) {
+      final int pre = pos - 1;
+      final double predist = dists[pre];
+      if(predist <= dist) {
+        break;
+      }
+      dists[pos] = predist;
+      ids[pos] = ids[pre];
+      pos = pre;
+    }
+    dists[pos] = dist;
+    ids[pos] = id;
+    ++size;
+    if(size > k && dists[k] > dists[k - 1]) {
+      size = k; // truncate
+    }
+    return;
+  }
+
+  @Override
+  public double insert(double dist, DBIDRef id) {
+    final int kminus1 = k - 1;
+    final int iid = id.internalGetIndex();
+    if(size >= k && dist > dists[kminus1]) {
+      return (size >= k) ? dists[kminus1] : Double.POSITIVE_INFINITY;
+    }
+    insertionSort(dist, iid);
+    return (size >= k) ? dists[kminus1] : Double.POSITIVE_INFINITY;
+  }
+
+  @Override
+  public void add(double dist, DBIDRef id) {
+    addInternal(dist, id.internalGetIndex());
+  }
+
+  @Override
+  @Deprecated
+  public void insert(Double dist, DBIDRef id) {
+    addInternal(dist.doubleValue(), id.internalGetIndex());
+  }
+
+  @Override
+  public void insert(DoubleDistanceDBIDPair e) {
+    addInternal(e.doubleDistance(), e.internalGetIndex());
+  }
+
+  @Override
+  @Deprecated
+  public void insert(DoubleDistance dist, DBIDRef id) {
+    addInternal(dist.doubleValue(), id.internalGetIndex());
+  }
+
+  @Override
+  public DoubleDistanceIntegerDBIDPair poll() {
+    final int last = size - 1;
+    return new DoubleDistanceIntegerDBIDPair(dists[last], ids[last]);
+  }
+
+  @Override
+  public DoubleDistanceIntegerDBIDPair peek() {
+    final int last = size - 1;
+    return new DoubleDistanceIntegerDBIDPair(dists[last], ids[last]);
+  }
+
+  @Override
+  public DoubleDistanceKNNList toKNNList() {
+    return this;
+  }
+
+  @Override
+  public String toString() {
+    StringBuilder buf = new StringBuilder();
+    buf.append("kNNListHeap[");
+    for(DoubleDistanceDBIDListIter iter = this.iter(); iter.valid();) {
+      buf.append(iter.doubleDistance()).append(':').append(iter.internalGetIndex());
+      iter.advance();
+      if(iter.valid()) {
+        buf.append(',');
+      }
+    }
+    buf.append(']');
+    return buf.toString();
+  }
+}
diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerArrayDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerArrayDBIDs.java
index 61a12b3f..286bedf9 100644
--- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerArrayDBIDs.java
+++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerArrayDBIDs.java
@@ -33,4 +33,7 @@ import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs;
 public interface IntegerArrayDBIDs extends IntegerDBIDs, ArrayDBIDs {
   @Override
   IntegerDBIDArrayIter iter();
+  
+  @Override
+  IntegerArrayDBIDs slice(int begin, int end);
 }
diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBID.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBID.java
index 40243695..6b7ec5ac 100644
--- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBID.java
+++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBID.java
@@ -25,9 +25,11 @@ package de.lmu.ifi.dbs.elki.database.ids.integer;
 
 import java.nio.ByteBuffer;
 
+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.DBIDArrayIter;
 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.DBIDVar;
 import de.lmu.ifi.dbs.elki.logging.LoggingUtil;
 import de.lmu.ifi.dbs.elki.persistent.ByteArrayUtil;
@@ -47,7 +49,6 @@ import de.lmu.ifi.dbs.elki.persistent.FixedSizeByteBufferSerializer;
  * 
  * @author Erich Schubert
  * 
- * @apiviz.landmark
  * @apiviz.composedOf DynamicSerializer
  * @apiviz.composedOf StaticSerializer
  */
@@ -88,6 +89,16 @@ final class IntegerDBID implements DBID, IntegerDBIDRef {
   }
 
   @Override
+  public int size() {
+    return 1;
+  }
+
+  @Override
+  public boolean isEmpty() {
+    return false;
+  }
+
+  @Override
   public String toString() {
     return Integer.toString(id);
   }
@@ -120,8 +131,8 @@ final class IntegerDBID implements DBID, IntegerDBIDRef {
   }
 
   @Override
-  public DBIDArrayIter iter() {
-    return new DBIDItr();
+  public Itr iter() {
+    return new Itr();
   }
 
   @Override
@@ -146,16 +157,20 @@ final class IntegerDBID implements DBID, IntegerDBIDRef {
   }
 
   @Override
-  public int size() {
-    return 1;
-  }
-
-  @Override
   public int binarySearch(DBIDRef key) {
     final int other = key.internalGetIndex();
     return (other == id) ? 0 : (other < id) ? -1 : -2;
   }
 
+  @Override
+  public ArrayDBIDs slice(int begin, int end) {
+    if (begin == 0 && end == 1) {
+      return this;
+    } else {
+      return DBIDUtil.EMPTYDBIDS;
+    }
+  }
+
   /**
    * Pseudo iterator for DBIDs interface.
    * 
@@ -163,7 +178,7 @@ final class IntegerDBID implements DBID, IntegerDBIDRef {
    * 
    * @apiviz.exclude
    */
-  protected class DBIDItr implements DBIDArrayIter, IntegerDBIDRef {
+  protected class Itr implements DBIDArrayIter, IntegerDBIDRef {
     /**
      * Iterator position: We use an integer so we can support retract().
      */
@@ -224,11 +239,6 @@ final class IntegerDBID implements DBID, IntegerDBIDRef {
     }
   }
 
-  @Override
-  public boolean isEmpty() {
-    return false;
-  }
-
   /**
    * Dynamic sized serializer, using varint.
    * 
diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDArrayQuickSort.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDArrayQuickSort.java
index 90a97609..d6cadf60 100644
--- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDArrayQuickSort.java
+++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDArrayQuickSort.java
@@ -42,7 +42,7 @@ import de.lmu.ifi.dbs.elki.utilities.documentation.Reference;
  * 
  * @author Erich Schubert
  * 
- * @apiviz.uses TroveArrayModifiableDBIDs
+ * @apiviz.uses IntegerArrayDBIDs
  */
 @Reference(authors = "Vladimir Yaroslavskiy", title = "Dual-Pivot Quicksort", booktitle = "http://iaroslavski.narod.ru/quicksort/", url = "http://iaroslavski.narod.ru/quicksort/")
 class IntegerDBIDArrayQuickSort {
diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDIter.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDIter.java
index cc241475..721e6e4e 100644
--- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDIter.java
+++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDIter.java
@@ -28,6 +28,8 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDIter;
  * Iterator for integer DBIDs.
  * 
  * @author Erich Schubert
+ * 
+ * @apiviz.landmark
  */
 public interface IntegerDBIDIter extends IntegerDBIDRef, DBIDIter {
   // Empty
diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDPair.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDPair.java
index 1b1ab154..12e9b685 100644
--- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDPair.java
+++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDPair.java
@@ -29,8 +29,6 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDPair;
  * DBID pair using two ints for storage.
  * 
  * @author Erich Schubert
- * 
- * @apiviz.has IntegerDBID
  */
 public class IntegerDBIDPair implements DBIDPair {
   /**
diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDRange.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDRange.java
index 3ceb163d..e418db5f 100644
--- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDRange.java
+++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDRange.java
@@ -23,22 +23,21 @@ package de.lmu.ifi.dbs.elki.database.ids.integer;
  along with this program.  If not, see <http://www.gnu.org/licenses/>.
  */
 
+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.DBIDArrayIter;
 import de.lmu.ifi.dbs.elki.database.ids.DBIDFactory;
 import de.lmu.ifi.dbs.elki.database.ids.DBIDRange;
 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.DBIDVar;
+import de.lmu.ifi.dbs.elki.database.ids.SetDBIDs;
 
 /**
  * Representing a DBID range allocation.
  * 
  * @author Erich Schubert
- * 
- * @apiviz.has IntegerDBID
  */
-class IntegerDBIDRange implements DBIDRange {
+final class IntegerDBIDRange implements IntegerDBIDs, DBIDRange, SetDBIDs {
   /**
    * Start value.
    */
@@ -72,8 +71,77 @@ class IntegerDBIDRange implements DBIDRange {
   }
 
   @Override
-  public DBIDArrayIter iter() {
-    return new DBIDItr(start, len);
+  public boolean contains(DBIDRef o) {
+    int oid = o.internalGetIndex();
+    if (oid < start) {
+      return false;
+    }
+    if (oid >= start + len) {
+      return false;
+    }
+    return true;
+  }
+
+  @Override
+  public DBID get(int i) {
+    if (i > len || i < 0) {
+      throw new ArrayIndexOutOfBoundsException();
+    }
+    return DBIDFactory.FACTORY.importInteger(start + i);
+  }
+
+  /**
+   * For storage array offsets.
+   * 
+   * @param dbid ID reference
+   * @return array offset
+   */
+  @Override
+  public int getOffset(DBIDRef dbid) {
+    return dbid.internalGetIndex() - start;
+  }
+
+  @Override
+  public void assignVar(int index, DBIDVar var) {
+    if (var instanceof IntegerDBIDVar) {
+      ((IntegerDBIDVar) var).internalSetIndex(start + index);
+    } else {
+      // Much less efficient:
+      var.set(get(index));
+    }
+  }
+
+  @Override
+  public int binarySearch(DBIDRef key) {
+    int keyid = DBIDUtil.asInteger(key);
+    if (keyid < start) {
+      return -1;
+    }
+    final int off = keyid - start;
+    if (off < len) {
+      return off;
+    }
+    return -(len + 1);
+  }
+
+  @Override
+  public String toString() {
+    return "[" + start + " to " + (start + len - 1) + "]";
+  }
+
+  @Override
+  public final int mapDBIDToOffset(DBIDRef dbid) {
+    return dbid.internalGetIndex() - start;
+  }
+
+  @Override
+  public ArrayDBIDs slice(int begin, int end) {
+    return new IntegerDBIDRange(begin + start, end - begin);
+  }
+
+  @Override
+  public Itr iter() {
+    return new Itr(start, len);
   }
 
   /**
@@ -83,30 +151,29 @@ class IntegerDBIDRange implements DBIDRange {
    * 
    * @apiviz.exclude
    */
-  protected static class DBIDItr implements DBIDArrayIter, IntegerDBIDRef {
+  private final static class Itr implements IntegerDBIDArrayIter {
     /**
      * Current position.
      */
-    int pos = 0;
-    
+    private int pos;
+
     /**
      * Interval length.
      */
-    final int len;
+    final private int len;
 
     /**
      * Interval start.
      */
-    final int start;
-    
+    final private int start;
+
     /**
      * Constructor.
-     *
+     * 
      * @param start Interval start
      * @param len Interval length
      */
-    DBIDItr(int start, int len) {
-      super();
+    public Itr(final int start, final int len) {
       this.start = start;
       this.len = len;
     }
@@ -118,7 +185,7 @@ class IntegerDBIDRange implements DBIDRange {
 
     @Override
     public void advance() {
-      pos++;
+      ++pos;
     }
 
     @Override
@@ -128,7 +195,7 @@ class IntegerDBIDRange implements DBIDRange {
 
     @Override
     public void retract() {
-      pos--;
+      --pos;
     }
 
     @Override
@@ -156,68 +223,4 @@ class IntegerDBIDRange implements DBIDRange {
       return Integer.toString(internalGetIndex());
     }
   }
-
-  @Override
-  public boolean contains(DBIDRef o) {
-    int oid = DBIDUtil.asInteger(o);
-    if(oid < start) {
-      return false;
-    }
-    if(oid >= start + len) {
-      return false;
-    }
-    return true;
-  }
-
-  @Override
-  public DBID get(int i) {
-    if(i > len || i < 0) {
-      throw new ArrayIndexOutOfBoundsException();
-    }
-    return DBIDFactory.FACTORY.importInteger(start + i);
-  }
-
-  /**
-   * For storage array offsets.
-   * 
-   * @param dbid ID reference
-   * @return array offset
-   */
-  @Override
-  public int getOffset(DBIDRef dbid) {
-    return dbid.internalGetIndex() - start;
-  }
-
-  @Override
-  public void assignVar(int index, DBIDVar var) {
-    if (var instanceof IntegerDBIDVar) {
-      ((IntegerDBIDVar)var).internalSetIndex(start + index);
-    } else {
-      // Much less efficient:
-      var.set(get(index));
-    }
-  }
-
-  @Override
-  public int binarySearch(DBIDRef key) {
-    int keyid = DBIDUtil.asInteger(key);
-    if(keyid < start) {
-      return -1;
-    }
-    final int off = keyid - start;
-    if(off < len) {
-      return off;
-    }
-    return -(len + 1);
-  }
-
-  @Override
-  public String toString() {
-    return "[" + start + " to " + (start + len - 1) + "]";
-  }
-
-  @Override
-  public int mapDBIDToOffset(DBIDRef dbid) {
-    return dbid.internalGetIndex() - start;
-  }
-}
\ No newline at end of file
+}
diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDRef.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDRef.java
index dc63b117..0e1e82a9 100644
--- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDRef.java
+++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDRef.java
@@ -29,6 +29,8 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDRef;
  * DBID reference that references an integer value.
  * 
  * @author Erich Schubert
+ * 
+ * @apiviz.landmark
  */
 interface IntegerDBIDRef extends DBIDRef {
   /**
diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDVar.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDVar.java
index 57d400df..9120c0d7 100644
--- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDVar.java
+++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDVar.java
@@ -23,8 +23,10 @@ package de.lmu.ifi.dbs.elki.database.ids.integer;
  along with this program.  If not, see <http://www.gnu.org/licenses/>.
  */
 
+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.DBIDVar;
 import de.lmu.ifi.dbs.elki.logging.LoggingUtil;
 
@@ -87,13 +89,13 @@ class IntegerDBIDVar implements DBIDVar, IntegerDBIDs {
   }
 
   @Override
-  public IntegerDBIDArrayIter iter() {
-    return new DBIDItr();
+  public int size() {
+    return 1;
   }
 
   @Override
-  public int size() {
-    return 1;
+  public boolean isEmpty() {
+    return false;
   }
 
   @Override
@@ -107,6 +109,35 @@ class IntegerDBIDVar implements DBIDVar, IntegerDBIDs {
     return id == o.internalGetIndex();
   }
 
+  @Override
+  public void assignVar(int i, DBIDVar var) {
+    if (var instanceof IntegerDBIDVar) {
+      ((IntegerDBIDVar) var).internalSetIndex(i);
+    } else {
+      // Much less efficient:
+      var.set(get(i));
+    }
+  }
+
+  @Override
+  public ArrayDBIDs slice(int begin, int end) {
+    if (begin == 0 && end == 1) {
+      return this;
+    } else {
+      return DBIDUtil.EMPTYDBIDS;
+    }
+  }
+
+  @Override
+  public String toString() {
+    return Integer.toString(id);
+  }
+
+  @Override
+  public Itr iter() {
+    return new Itr();
+  }
+
   /**
    * Pseudo iterator for DBIDs interface.
    * 
@@ -114,53 +145,53 @@ class IntegerDBIDVar implements DBIDVar, IntegerDBIDs {
    * 
    * @apiviz.exclude
    */
-  protected class DBIDItr implements IntegerDBIDArrayIter, IntegerDBIDRef {
+  protected class Itr implements IntegerDBIDArrayIter, IntegerDBIDRef {
     /**
      * Iterator position: We use an integer so we can support retract().
      */
     int pos = 0;
-
+  
     @Override
     public void advance() {
       pos++;
     }
-
+  
     @Override
     public void advance(int count) {
       pos += count;
     }
-
+  
     @Override
     public void retract() {
       pos--;
     }
-
+  
     @Override
     public void seek(int off) {
       pos = off;
     }
-
+  
     @Override
     public int getOffset() {
       return pos;
     }
-
+  
     @Override
     public int internalGetIndex() {
       return IntegerDBIDVar.this.id;
     }
-
+  
     @Override
     public boolean valid() {
       return (pos == 0);
     }
-
+  
     @Override
     public int hashCode() {
       // Override, because we also are overriding equals.
       return super.hashCode();
     }
-
+  
     @Override
     public boolean equals(Object other) {
       if (other instanceof DBID) {
@@ -168,30 +199,10 @@ class IntegerDBIDVar implements DBIDVar, IntegerDBIDs {
       }
       return super.equals(other);
     }
-
+  
     @Override
     public String toString() {
       return Integer.toString(internalGetIndex());
     }
   }
-
-  @Override
-  public boolean isEmpty() {
-    return false;
-  }
-
-  @Override
-  public void assignVar(int i, DBIDVar var) {
-    if (var instanceof IntegerDBIDVar) {
-      ((IntegerDBIDVar) var).internalSetIndex(i);
-    } else {
-      // Much less efficient:
-      var.set(get(i));
-    }
-  }
-
-  @Override
-  public String toString() {
-    return Integer.toString(id);
-  }
 }
diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDs.java
index 4acf91e6..14faa72a 100644
--- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDs.java
+++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDs.java
@@ -28,6 +28,8 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDs;
  * Integer DBID collection.
  * 
  * @author Erich Schubert
+ * 
+ * @apiviz.has IntegerDBIDIter
  */
 public interface IntegerDBIDs extends DBIDs {
   @Override
diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayDBIDs.java
deleted file mode 100644
index 6980176a..00000000
--- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayDBIDs.java
+++ /dev/null
@@ -1,192 +0,0 @@
-package de.lmu.ifi.dbs.elki.database.ids.integer;
-
-/*
- This file is part of ELKI:
- Environment for Developing KDD-Applications Supported by Index-Structures
-
- Copyright (C) 2013
- 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 gnu.trove.list.TIntList;
-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.ids.DBIDVar;
-import de.lmu.ifi.dbs.elki.logging.LoggingUtil;
-
-/**
- * Abstract base class for GNU Trove array based lists.
- * 
- * @author Erich Schubert
- * 
- * @apiviz.has IntegerDBID
- * @apiviz.has DBIDItr
- */
-public abstract class TroveArrayDBIDs implements IntegerArrayDBIDs {
-  /**
-   * Get the array store.
-   * 
-   * @return the store
-   */
-  protected abstract TIntList getStore();
-
-  @Override
-  public IntegerDBIDArrayMIter iter() {
-    return new DBIDItr(getStore());
-  }
-
-  @Override
-  public DBID get(int index) {
-    return new IntegerDBID(getStore().get(index));
-  }
-
-  @Override
-  public void assignVar(int index, DBIDVar var) {
-    if (var instanceof IntegerDBIDVar) {
-      ((IntegerDBIDVar)var).internalSetIndex(getStore().get(index));
-    } else {
-      // Much less efficient:
-      var.set(get(index));
-    }
-  }
-
-  @Override
-  public int size() {
-    return getStore().size();
-  }
-
-  @Override
-  public boolean isEmpty() {
-    return getStore().isEmpty();
-  }
-
-  @Override
-  public boolean contains(DBIDRef o) {
-    return getStore().contains(DBIDUtil.asInteger(o));
-  }
-
-  @Override
-  public int binarySearch(DBIDRef key) {
-    return getStore().binarySearch(DBIDUtil.asInteger(key));
-  }
-
-  @Override
-  public String toString() {
-    StringBuilder buf = new StringBuilder();
-    buf.append('[');
-    for(DBIDIter iter = iter(); iter.valid(); iter.advance()) {
-      if(buf.length() > 1) {
-        buf.append(", ");
-      }
-      buf.append(((IntegerDBIDRef) iter).internalGetIndex());
-    }
-    buf.append(']');
-    return buf.toString();
-  }
-
-  /**
-   * Iterate over a Trove IntList, ELKI/C-style.
-   * 
-   * @author Erich Schubert
-   * 
-   * @apiviz.exclude
-   */
-  protected static class DBIDItr implements IntegerDBIDArrayMIter {
-    /**
-     * Current position.
-     */
-    int pos = 0;
-
-    /**
-     * The actual store we use.
-     */
-    TIntList store;
-
-    /**
-     * Constructor.
-     * 
-     * @param store The actual trove store
-     */
-    public DBIDItr(TIntList store) {
-      super();
-      this.store = store;
-    }
-
-    @Override
-    public boolean valid() {
-      return pos < store.size() && pos >= 0;
-    }
-
-    @Override
-    public void advance() {
-      pos++;
-    }
-
-    @Override
-    public void advance(int count) {
-      pos += count;
-    }
-
-    @Override
-    public void retract() {
-      pos--;
-    }
-
-    @Override
-    public void seek(int off) {
-      pos = off;
-    }
-
-    @Override
-    public int getOffset() {
-      return pos;
-    }
-
-    @Override
-    public int internalGetIndex() {
-      return store.get(pos);
-    }
-
-    @Override
-    public void remove() {
-      store.removeAt(pos);
-      pos--;
-    }
-    
-    @Override
-    public int hashCode() {
-      // Since we add a warning to 'equals', we also override hashCode.
-      return super.hashCode();
-    }
-
-    @Override
-    public boolean equals(Object other) {
-      if(other instanceof DBID) {
-        LoggingUtil.warning("Programming error detected: DBIDItr.equals(DBID). Use DBIDUtil.equal(iter, id)!", new Throwable());
-      }
-      return super.equals(other);
-    }
-
-    @Override
-    public String toString() {
-      return Integer.toString(internalGetIndex());
-    }
-  }
-}
\ No newline at end of file
diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayModifiableDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayModifiableDBIDs.java
deleted file mode 100644
index 41191b10..00000000
--- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayModifiableDBIDs.java
+++ /dev/null
@@ -1,155 +0,0 @@
-package de.lmu.ifi.dbs.elki.database.ids.integer;
-
-/*
- This file is part of ELKI:
- Environment for Developing KDD-Applications Supported by Index-Structures
-
- Copyright (C) 2013
- 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 gnu.trove.list.array.TIntArrayList;
-
-import java.util.Comparator;
-
-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.ids.DBIDs;
-
-/**
- * Class using a GNU Trove int array list as storage.
- * 
- * @author Erich Schubert
- */
-class TroveArrayModifiableDBIDs extends TroveArrayDBIDs implements ArrayModifiableDBIDs {
-  /**
-   * The actual trove array list
-   */
-  private TIntArrayList store;
-
-  /**
-   * Constructor.
-   * 
-   * @param size Initial size
-   */
-  protected TroveArrayModifiableDBIDs(int size) {
-    super();
-    this.store = new TIntArrayList(size);
-  }
-
-  /**
-   * Constructor.
-   */
-  protected TroveArrayModifiableDBIDs() {
-    super();
-    this.store = new TIntArrayList();
-  }
-
-  /**
-   * Constructor.
-   * 
-   * @param existing Existing ids
-   */
-  protected TroveArrayModifiableDBIDs(DBIDs existing) {
-    this(existing.size());
-    this.addDBIDs(existing);
-  }
-
-  @Override
-  protected TIntArrayList getStore() {
-    return store;
-  }
-
-  @Override
-  public boolean addDBIDs(DBIDs ids) {
-    boolean success = false;
-    store.ensureCapacity(ids.size());
-    for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) {
-      success |= store.add(DBIDUtil.asInteger(iter));
-    }
-    return success;
-  }
-
-  @Override
-  public boolean removeDBIDs(DBIDs ids) {
-    boolean success = false;
-    for (DBIDIter id = ids.iter(); id.valid(); id.advance()) {
-      success |= store.remove(DBIDUtil.asInteger(id));
-    }
-    return success;
-  }
-
-  @Override
-  public boolean add(DBIDRef e) {
-    return store.add(DBIDUtil.asInteger(e));
-  }
-
-  @Override
-  public boolean remove(DBIDRef o) {
-    return store.remove(DBIDUtil.asInteger(o));
-  }
-
-  @Override
-  public DBID set(int index, DBIDRef element) {
-    int prev = store.set(index, DBIDUtil.asInteger(element));
-    return new IntegerDBID(prev);
-  }
-
-  @Override
-  public DBID remove(int index) {
-    return new IntegerDBID(store.removeAt(index));
-  }
-
-  @Override
-  public void clear() {
-    store.clear();
-  }
-
-  @Override
-  public void sort() {
-    store.sort();
-  }
-
-  @Override
-  public void sort(Comparator<? super DBIDRef> comparator) {
-    // TODO: we no longer produce a lot of DBIDs anymore, but it would be even
-    // cooler if we could access store._data directly...
-    int[] data = store.toArray();
-    IntegerDBIDArrayQuickSort.sort(data, comparator);
-    store.clear();
-    store.add(data);
-  }
-
-  @Override
-  public void sort(int start, int end, Comparator<? super DBIDRef> comparator) {
-    // TODO: we no longer produce a lot of DBIDs anymore, but it would be even
-    // cooler if we could access store._data directly...
-    int[] data = store.toArray();
-    IntegerDBIDArrayQuickSort.sort(data, start, end, comparator);
-    store.clear();
-    store.add(data);
-  }
-
-  @Override
-  public void swap(int a, int b) {
-    store.set(a, store.set(b, store.get(a)));
-  }
-}
diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveHashSetModifiableDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveHashSetModifiableDBIDs.java
index 9ebdccea..35276606 100644
--- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveHashSetModifiableDBIDs.java
+++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveHashSetModifiableDBIDs.java
@@ -1,16 +1,5 @@
 package de.lmu.ifi.dbs.elki.database.ids.integer;
 
-import gnu.trove.impl.hash.THashPrimitiveIterator;
-import gnu.trove.impl.hash.TIntHash;
-import gnu.trove.set.hash.TIntHashSet;
-import de.lmu.ifi.dbs.elki.database.ids.DBIDIter;
-import de.lmu.ifi.dbs.elki.database.ids.DBIDMIter;
-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.HashSetModifiableDBIDs;
-import de.lmu.ifi.dbs.elki.utilities.datastructures.iterator.Iter;
-
 /*
  This file is part of ELKI:
  Environment for Developing KDD-Applications Supported by Index-Structures
@@ -34,13 +23,23 @@ import de.lmu.ifi.dbs.elki.utilities.datastructures.iterator.Iter;
  along with this program.  If not, see <http://www.gnu.org/licenses/>.
  */
 
+import gnu.trove.impl.hash.THashPrimitiveIterator;
+import gnu.trove.impl.hash.TIntHash;
+import gnu.trove.set.hash.TIntHashSet;
+import de.lmu.ifi.dbs.elki.database.ids.DBIDIter;
+import de.lmu.ifi.dbs.elki.database.ids.DBIDMIter;
+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.HashSetModifiableDBIDs;
+import de.lmu.ifi.dbs.elki.utilities.datastructures.iterator.Iter;
+
 /**
  * Implementation using GNU Trove Int Hash Sets.
  * 
  * @author Erich Schubert
  * 
- * @apiviz.has IntegerDBID
- * @apiviz.has DBIDItr
+ * @apiviz.has Itr
  */
 class TroveHashSetModifiableDBIDs implements HashSetModifiableDBIDs, IntegerDBIDs {
   /**
@@ -77,15 +76,15 @@ class TroveHashSetModifiableDBIDs implements HashSetModifiableDBIDs, IntegerDBID
   }
 
   @Override
-  public IntegerDBIDMIter iter() {
-    return new DBIDItr(store);
+  public Itr iter() {
+    return new Itr(store);
   }
 
   @Override
   public boolean addDBIDs(DBIDs ids) {
     store.ensureCapacity(ids.size());
     boolean success = false;
-    for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) {
+    for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) {
       success |= store.add(DBIDUtil.asInteger(iter));
     }
     return success;
@@ -94,7 +93,7 @@ class TroveHashSetModifiableDBIDs implements HashSetModifiableDBIDs, IntegerDBID
   @Override
   public boolean removeDBIDs(DBIDs ids) {
     boolean success = false;
-    for (DBIDIter id = ids.iter(); id.valid(); id.advance()) {
+    for(DBIDIter id = ids.iter(); id.valid(); id.advance()) {
       success |= store.remove(DBIDUtil.asInteger(id));
     }
     return success;
@@ -113,8 +112,8 @@ class TroveHashSetModifiableDBIDs implements HashSetModifiableDBIDs, IntegerDBID
   @Override
   public boolean retainAll(DBIDs set) {
     boolean modified = false;
-    for (DBIDMIter it = iter(); it.valid(); it.advance()) {
-      if (!set.contains(it)) {
+    for(DBIDMIter it = iter(); it.valid(); it.advance()) {
+      if(!set.contains(it)) {
         it.remove();
         modified = true;
       }
@@ -146,8 +145,8 @@ class TroveHashSetModifiableDBIDs implements HashSetModifiableDBIDs, IntegerDBID
   public String toString() {
     StringBuilder buf = new StringBuilder();
     buf.append('[');
-    for (DBIDIter iter = iter(); iter.valid(); iter.advance()) {
-      if (buf.length() > 1) {
+    for(DBIDIter iter = iter(); iter.valid(); iter.advance()) {
+      if(buf.length() > 1) {
         buf.append(", ");
       }
       buf.append(iter.toString());
@@ -163,7 +162,7 @@ class TroveHashSetModifiableDBIDs implements HashSetModifiableDBIDs, IntegerDBID
    * 
    * @apiviz.exclude
    */
-  protected static class DBIDItr implements IntegerDBIDMIter {
+  protected static class Itr implements IntegerDBIDMIter {
     /**
      * The actual iterator. We don't have multi inheritance.
      */
@@ -174,7 +173,7 @@ class TroveHashSetModifiableDBIDs implements HashSetModifiableDBIDs, IntegerDBID
      * 
      * @param hash Trove hash
      */
-    public DBIDItr(TIntHash hash) {
+    public Itr(TIntHash hash) {
       super();
       this.it = new TIntHashItr(hash);
     }
diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/UnmodifiableIntegerArrayDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/UnmodifiableIntegerArrayDBIDs.java
index ba30f54f..d1c37ab9 100644
--- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/UnmodifiableIntegerArrayDBIDs.java
+++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/UnmodifiableIntegerArrayDBIDs.java
@@ -33,7 +33,7 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDVar;
  * 
  * @author Erich Schubert
  * 
- * @apiviz.uses TroveArrayDBIDs
+ * @apiviz.uses IntegerArrayDBIDs
  * @apiviz.has UnmodifiableDBIDIter
  */
 public class UnmodifiableIntegerArrayDBIDs implements IntegerArrayStaticDBIDs {
@@ -96,6 +96,11 @@ public class UnmodifiableIntegerArrayDBIDs implements IntegerArrayStaticDBIDs {
     return inner.binarySearch(key);
   }
 
+  @Override
+  public IntegerArrayDBIDs slice(int begin, int end) {
+    return new UnmodifiableIntegerArrayDBIDs(inner.slice(begin, end));
+  }
+
   /**
    * Make an existing DBIDMIter unmodifiable.
    * 
@@ -151,7 +156,7 @@ public class UnmodifiableIntegerArrayDBIDs implements IntegerArrayStaticDBIDs {
     public int internalGetIndex() {
       return it.internalGetIndex();
     }
-    
+
     @Override
     public String toString() {
       return it.toString();