Import Debian changes 0.5.0~beta2-1

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

  * New upstream beta release.
  * Needs GNU Trove 3, in NEW.
  * Build with OpenJDK7, as OpenJDK6 complains.

elki (0.5.0~beta1-1) unstable; urgency=low

  * New upstream beta release.
  * Needs GNU Trove 3, not yet in Debian (private package)
  * Build with OpenJDK7, as OpenJDK6 complains.

1 files changed, 183 insertions, 0 deletions

diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/RTreeQuadraticSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/RTreeQuadraticSplit.java
new file mode 100644
index 00000000..8f61771d
--- /dev/null
+++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/RTreeQuadraticSplit.java
@@ -0,0 +1,183 @@
+package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.split;
+
+/*
+ This file is part of ELKI:
+ Environment for Developing KDD-Applications Supported by Index-Structures
+
+ Copyright (C) 2012
+ 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.BitSet;
+
+import de.lmu.ifi.dbs.elki.data.ModifiableHyperBoundingBox;
+import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable;
+import de.lmu.ifi.dbs.elki.data.spatial.SpatialUtil;
+import de.lmu.ifi.dbs.elki.utilities.datastructures.arraylike.ArrayAdapter;
+import de.lmu.ifi.dbs.elki.utilities.documentation.Reference;
+import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer;
+
+/**
+ * Quadratic-time complexity greedy split as used by the original R-Tree.
+ * 
+ * <p>
+ * Antonin Guttman:<br/>
+ * R-Trees: A Dynamic Index Structure For Spatial Searching<br />
+ * in Proceedings of the 1984 ACM SIGMOD international conference on Management
+ * of data.
+ * </p>
+ * 
+ * @author Erich Schubert
+ */
+@Reference(authors = "Antonin Guttman", title = "R-Trees: A Dynamic Index Structure For Spatial Searching", booktitle = "Proceedings of the 1984 ACM SIGMOD international conference on Management of data", url = "http://dx.doi.org/10.1145/971697.602266")
+public class RTreeQuadraticSplit implements SplitStrategy {
+  /**
+   * Static instance.
+   */
+  public static final RTreeQuadraticSplit STATIC = new RTreeQuadraticSplit();
+
+  @Override
+  public <E extends SpatialComparable, A> BitSet split(A entries, ArrayAdapter<E, A> getter, int minEntries) {
+    final int num = getter.size(entries);
+    // Object assignment, and processed objects
+    BitSet assignment = new BitSet(num);
+    BitSet assigned = new BitSet(num);
+    // MBRs and Areas of current assignments
+    ModifiableHyperBoundingBox mbr1, mbr2;
+    double area1 = 0, area2 = 0;
+    // PickSeeds - find worst pair
+    {
+      double worst = Double.NEGATIVE_INFINITY;
+      int w1 = 0, w2 = 0;
+
+      // Compute individual areas
+      double[] areas = new double[num];
+      for(int e1 = 0; e1 < num - 1; e1++) {
+        final E e1i = getter.get(entries, e1);
+        areas[e1] = SpatialUtil.volume(e1i);
+      }
+      // Compute area increase
+      for(int e1 = 0; e1 < num - 1; e1++) {
+        final E e1i = getter.get(entries, e1);
+        for(int e2 = e1 + 1; e2 < num; e2++) {
+          final E e2i = getter.get(entries, e2);
+          final double areaJ = SpatialUtil.volumeUnion(e1i, e2i);
+          final double d = areaJ - areas[e1] - areas[e2];
+          if(d > worst) {
+            worst = d;
+            w1 = e1;
+            w2 = e2;
+          }
+        }
+      }
+      // Data to keep
+      // Mark both as used
+      assigned.set(w1);
+      assigned.set(w2);
+      // Assign second to second set
+      assignment.set(w2);
+      // Initial mbrs and areas
+      area1 = areas[w1];
+      area2 = areas[w2];
+      mbr1 = new ModifiableHyperBoundingBox(getter.get(entries, w1));
+      mbr2 = new ModifiableHyperBoundingBox(getter.get(entries, w2));
+    }
+    // Second phase, QS2+QS3
+    {
+      int in1 = 1, in2 = 1;
+      int remaining = num - 2;
+      while(remaining > 0) {
+        // Shortcut when minEntries must be fulfilled
+        if(in1 + remaining <= minEntries) {
+          // No need to updated assigned, no changes to assignment.
+          break;
+        }
+        if(in2 + remaining <= minEntries) {
+          // Mark unassigned for second.
+          // Don't bother to update assigned, though
+          for(int pos = assigned.nextClearBit(0); pos < num; pos = assigned.nextClearBit(pos + 1)) {
+            assignment.set(pos);
+          }
+          break;
+        }
+        // PickNext
+        double greatestPreference = Double.NEGATIVE_INFINITY;
+        int best = -1;
+        E best_i = null;
+        boolean preferSecond = false;
+        for(int pos = assigned.nextClearBit(0); pos < num; pos = assigned.nextClearBit(pos + 1)) {
+          // Cost of putting object into both mbrs
+          final E pos_i = getter.get(entries, pos);
+          final double d1 = SpatialUtil.volumeUnion(mbr1, pos_i) - area1;
+          final double d2 = SpatialUtil.volumeUnion(mbr2, pos_i) - area2;
+          // Preference
+          final double preference = Math.abs(d1 - d2);
+          if(preference > greatestPreference) {
+            greatestPreference = preference;
+            best = pos;
+            best_i = pos_i;
+            // Prefer smaller increase
+            preferSecond = (d2 < d1);
+          }
+        }
+        // QS3: tie handling
+        if(greatestPreference == 0) {
+          // Prefer smaller area
+          if(area1 != area2) {
+            preferSecond = (area2 < area1);
+          }
+          else {
+            // Prefer smaller group size
+            preferSecond = (in2 < in1);
+          }
+        }
+        // Mark as used.
+        assigned.set(best);
+        remaining--;
+        if(!preferSecond) {
+          in1++;
+          mbr1.extend(best_i);
+          area1 = SpatialUtil.volume(mbr1);
+        }
+        else {
+          in2++;
+          assignment.set(best);
+          mbr2.extend(best_i);
+          area2 = SpatialUtil.volume(mbr2);
+        }
+        // Loop from QS2
+      }
+      // Note: "assigned" and "remaining" likely not updated!
+    }
+    return assignment;
+  }
+
+  /**
+   * Parameterization class.
+   * 
+   * @author Erich Schubert
+   * 
+   * @apiviz.exclude
+   */
+  public static class Parameterizer extends AbstractParameterizer {
+    @Override
+    protected RTreeQuadraticSplit makeInstance() {
+      return RTreeQuadraticSplit.STATIC;
+    }
+  }
+}
\ No newline at end of file