1 files changed, 43 insertions, 9 deletions

diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/DBIDUtil.java b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDUtil.java
index cd2bd4e0..000659b9 100644
--- a/src/de/lmu/ifi/dbs/elki/database/ids/DBIDUtil.java
+++ b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDUtil.java
@@ -25,6 +25,7 @@ package de.lmu.ifi.dbs.elki.database.ids;
 
 import java.util.Random;
 
+import de.lmu.ifi.dbs.elki.database.ids.generic.UnmodifiableArrayDBIDs;
 import de.lmu.ifi.dbs.elki.database.ids.generic.UnmodifiableDBIDs;
 import de.lmu.ifi.dbs.elki.persistent.ByteBufferSerializer;
 
@@ -185,15 +186,45 @@ public final class DBIDUtil {
       return intersection(second, first);
     }
     ModifiableDBIDs inter = newHashSet(first.size());
-    for(DBID id : first) {
-      if(second.contains(id)) {
-        inter.add(id);
+    for(DBIDIter it = first.iter(); it.valid(); it.advance()) {
+      if(second.contains(it)) {
+        inter.add(it);
       }
     }
     return inter;
   }
 
   /**
+   * Compute the set symmetric intersection of two sets.
+   * 
+   * @param first First set
+   * @param second Second set
+   * @param firstonly OUTPUT: elements only in first. MUST BE EMPTY
+   * @param intersection OUTPUT: elements in intersection. MUST BE EMPTY
+   * @param secondonly OUTPUT: elements only in second. MUST BE EMPTY
+   */
+  // TODO: optimize?
+  public static void symmetricIntersection(DBIDs first, DBIDs second, HashSetModifiableDBIDs firstonly, HashSetModifiableDBIDs intersection, HashSetModifiableDBIDs secondonly) {
+    if(first.size() > second.size()) {
+      symmetricIntersection(second, first, secondonly, intersection, firstonly);
+      return;
+    }
+    assert(firstonly.size() == 0) : "OUTPUT set should be empty!";
+    assert(intersection.size() == 0) : "OUTPUT set should be empty!";
+    assert(secondonly.size() == 0) : "OUTPUT set should be empty!";
+    // Initialize with second
+    secondonly.addDBIDs(second);
+    for(DBIDIter it = first.iter(); it.valid(); it.advance()) {
+      // Try to remove
+      if(secondonly.remove(it)) {
+        intersection.add(it);
+      } else {
+        firstonly.add(it);
+      }
+    }
+  }
+
+  /**
    * Returns the union of the two specified collection of IDs.
    * 
    * @param ids1 the first collection
@@ -201,7 +232,7 @@ public final class DBIDUtil {
    * @return the union of ids1 and ids2 without duplicates
    */
   public static ModifiableDBIDs union(DBIDs ids1, DBIDs ids2) {
-    ModifiableDBIDs result = DBIDUtil.newHashSet();
+    ModifiableDBIDs result = DBIDUtil.newHashSet(Math.max(ids1.size(), ids2.size()));
     result.addDBIDs(ids1);
     result.addDBIDs(ids2);
     return result;
@@ -215,8 +246,7 @@ public final class DBIDUtil {
    * @return the difference of ids1 minus ids2
    */
   public static ModifiableDBIDs difference(DBIDs ids1, DBIDs ids2) {
-    ModifiableDBIDs result = DBIDUtil.newHashSet();
-    result.addDBIDs(ids1);
+    ModifiableDBIDs result = DBIDUtil.newHashSet(ids1);
     result.removeDBIDs(ids2);
     return result;
   }
@@ -231,7 +261,11 @@ public final class DBIDUtil {
     if(existing instanceof StaticDBIDs) {
       return (StaticDBIDs) existing;
     }
-    return new UnmodifiableDBIDs(existing);
+    if (existing instanceof ArrayDBIDs) {
+      return new UnmodifiableArrayDBIDs((ArrayDBIDs)existing);
+    } else {
+      return new UnmodifiableDBIDs(existing);
+    }
   }
 
   /**
@@ -293,7 +327,7 @@ public final class DBIDUtil {
    * 
    * @return DBID pair
    */
-  public static DBIDPair newPair(DBID id1, DBID id2) {
+  public static DBIDPair newPair(DBIDRef id1, DBIDRef id2) {
     return DBIDFactory.FACTORY.makePair(id1, id2);
   }
 
@@ -319,7 +353,7 @@ public final class DBIDUtil {
    */
   public static ModifiableDBIDs randomSample(DBIDs source, int k, Long seed) {
     if(k <= 0 || k > source.size()) {
-      throw new IllegalArgumentException("Illegal value for size of random sample: " + k);
+      throw new IllegalArgumentException("Illegal value for size of random sample: " + k+ " > "+source.size()+" or < 0");
     }
     final Random random;
     if(seed != null) {