Import Upstream version 0.6.5~20141030

1 files changed, 97 insertions, 86 deletions

diff --git a/src/de/lmu/ifi/dbs/elki/data/VectorUtil.java b/src/de/lmu/ifi/dbs/elki/data/VectorUtil.java
index 0a018622..59200ea9 100644
--- a/src/de/lmu/ifi/dbs/elki/data/VectorUtil.java
+++ b/src/de/lmu/ifi/dbs/elki/data/VectorUtil.java
@@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.data;
  This file is part of ELKI:
  Environment for Developing KDD-Applications Supported by Index-Structures
 
- Copyright (C) 2013
+ Copyright (C) 2014
  Ludwig-Maximilians-Universität München
  Lehr- und Forschungseinheit für Datenbanksysteme
  ELKI Development Team
@@ -36,7 +36,6 @@ 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.relation.Relation;
 import de.lmu.ifi.dbs.elki.database.relation.RelationUtil;
-import de.lmu.ifi.dbs.elki.math.DoubleMinMax;
 import de.lmu.ifi.dbs.elki.math.MathUtil;
 import de.lmu.ifi.dbs.elki.math.linearalgebra.Matrix;
 import de.lmu.ifi.dbs.elki.math.linearalgebra.Vector;
@@ -60,23 +59,6 @@ public final class VectorUtil {
   }
 
   /**
-   * Return the range across all dimensions. Useful in particular for time
-   * series.
-   * 
-   * @param vec Vector to process.
-   * @return [min, max]
-   */
-  public static DoubleMinMax getRangeDouble(NumberVector<?> vec) {
-    DoubleMinMax minmax = new DoubleMinMax();
-
-    for(int i = 0; i < vec.getDimensionality(); i++) {
-      minmax.put(vec.doubleValue(i));
-    }
-
-    return minmax;
-  }
-
-  /**
    * Produce a new vector based on random numbers in [0:1].
    * 
    * @param factory Vector factory
@@ -85,7 +67,7 @@ public final class VectorUtil {
    * @param <V> vector type
    * @return new instance
    */
-  public static <V extends NumberVector<?>> V randomVector(NumberVector.Factory<V, ?> factory, int dim, Random r) {
+  public static <V extends NumberVector> V randomVector(NumberVector.Factory<V> factory, int dim, Random r) {
     return factory.newNumberVector(MathUtil.randomDoubleArray(dim, r));
   }
 
@@ -97,7 +79,7 @@ public final class VectorUtil {
    * @param <V> vector type
    * @return new instance
    */
-  public static <V extends NumberVector<?>> V randomVector(NumberVector.Factory<V, ?> factory, int dim) {
+  public static <V extends NumberVector> V randomVector(NumberVector.Factory<V> factory, int dim) {
     return randomVector(factory, dim, new Random());
   }
 
@@ -108,7 +90,7 @@ public final class VectorUtil {
    * @param v2 Second vector
    * @return angle
    */
-  public static double angleSparse(SparseNumberVector<?> v1, SparseNumberVector<?> v2) {
+  public static double angleSparse(SparseNumberVector v1, SparseNumberVector v2) {
     // TODO: exploit precomputed length, when available?
     // Length of first vector
     double l1 = 0., l2 = 0., cross = 0.;
@@ -145,9 +127,14 @@ public final class VectorUtil {
       l2 += val * val;
       i2 = v2.iterAdvance(i2);
     }
-
-    final double a = cross / (Math.sqrt(l1) * Math.sqrt(l2));
-    return (a > 1.) ? 1. : a;
+    if(cross == 0.) {
+      return 0.;
+    }
+    if(l1 == 0. || l2 == 0.) {
+      return 1.;
+    }
+    final double a = Math.sqrt((cross / l1) * (cross / l2));
+    return (a < 1.) ? a : 1.;
   }
 
   /**
@@ -158,35 +145,41 @@ public final class VectorUtil {
    * @param o Origin
    * @return Angle
    */
-  public static double angle(NumberVector<?> v1, NumberVector<?> v2, Vector o) {
-    final int dim1 = v1.getDimensionality(), dim2 = v1.getDimensionality(), dimo = v1.getDimensionality();
+  public static double angle(NumberVector v1, NumberVector v2, Vector o) {
+    final int dim1 = v1.getDimensionality(), dim2 = v2.getDimensionality(), dimo = o.getDimensionality();
     final int mindim = (dim1 <= dim2) ? dim1 : dim2;
     // Essentially, we want to compute this:
     // v1' = v1 - o, v2' = v2 - o
     // v1'.transposeTimes(v2') / (v1'.euclideanLength()*v2'.euclideanLength());
     // We can just compute all three in parallel.
     double[] oe = o.getArrayRef();
-    double s = 0, e1 = 0, e2 = 0;
+    double cross = 0., l1 = 0., l2 = 0.;
     for(int k = 0; k < mindim; k++) {
       final double dk = k < dimo ? oe[k] : 0.;
       final double r1 = v1.doubleValue(k) - dk;
       final double r2 = v2.doubleValue(k) - dk;
-      s += r1 * r2;
-      e1 += r1 * r1;
-      e2 += r2 * r2;
+      cross += r1 * r2;
+      l1 += r1 * r1;
+      l2 += r2 * r2;
     }
     for(int k = mindim; k < dim1; k++) {
       final double dk = k < dimo ? oe[k] : 0.;
       final double r1 = v1.doubleValue(k) - dk;
-      e1 += r1 * r1;
+      l1 += r1 * r1;
     }
     for(int k = mindim; k < dim2; k++) {
       final double dk = k < dimo ? oe[k] : 0.;
       final double r2 = v2.doubleValue(k) - dk;
-      e2 += r2 * r2;
+      l2 += r2 * r2;
+    }
+    if(cross == 0.) {
+      return 0.;
+    }
+    if(l1 == 0. || l2 == 0.) {
+      return 1.;
     }
-    final double a = Math.sqrt((s / e1) * (s / e2));
-    return (a > 1.) ? 1. : a;
+    final double a = Math.sqrt((cross / l1) * (cross / l2));
+    return (a < 1.) ? a : 1.;
   }
 
   /**
@@ -197,34 +190,40 @@ public final class VectorUtil {
    * @param o Origin
    * @return Angle
    */
-  public static double angle(NumberVector<?> v1, NumberVector<?> v2, NumberVector<?> o) {
-    final int dim1 = v1.getDimensionality(), dim2 = v1.getDimensionality(), dimo = o.getDimensionality();
+  public static double angle(NumberVector v1, NumberVector v2, NumberVector o) {
+    final int dim1 = v1.getDimensionality(), dim2 = v2.getDimensionality(), dimo = o.getDimensionality();
     final int mindim = (dim1 <= dim2) ? dim1 : dim2;
     // Essentially, we want to compute this:
     // v1' = v1 - o, v2' = v2 - o
     // v1'.transposeTimes(v2') / (v1'.euclideanLength()*v2'.euclideanLength());
     // We can just compute all three in parallel.
-    double s = 0, e1 = 0, e2 = 0;
+    double cross = 0, l1 = 0, l2 = 0;
     for(int k = 0; k < mindim; k++) {
       final double ok = k < dimo ? o.doubleValue(k) : 0.;
       final double r1 = v1.doubleValue(k) - ok;
       final double r2 = v2.doubleValue(k) - o.doubleValue(k);
-      s += r1 * r2;
-      e1 += r1 * r1;
-      e2 += r2 * r2;
+      cross += r1 * r2;
+      l1 += r1 * r1;
+      l2 += r2 * r2;
     }
     for(int k = mindim; k < dim1; k++) {
       final double ok = k < dimo ? o.doubleValue(k) : 0.;
       final double r1 = v1.doubleValue(k) - ok;
-      e1 += r1 * r1;
+      l1 += r1 * r1;
     }
     for(int k = mindim; k < dim2; k++) {
       final double ok = k < dimo ? o.doubleValue(k) : 0.;
       final double r2 = v2.doubleValue(k) - ok;
-      e2 += r2 * r2;
+      l2 += r2 * r2;
+    }
+    if(cross == 0.) {
+      return 0.;
+    }
+    if(l1 == 0. || l2 == 0.) {
+      return 1.;
     }
-    final double a = Math.sqrt((s / e1) * (s / e2));
-    return (a > 1.) ? 1. : a;
+    final double a = Math.sqrt((cross / l1) * (cross / l2));
+    return (a < 1.) ? a : 1.;
   }
 
   /**
@@ -236,33 +235,39 @@ public final class VectorUtil {
    * @param v2 second vector
    * @return Angle
    */
-  public static double cosAngle(NumberVector<?> v1, NumberVector<?> v2) {
-    if(v1 instanceof SparseNumberVector<?> && v2 instanceof SparseNumberVector<?>) {
-      return angleSparse((SparseNumberVector<?>) v1, (SparseNumberVector<?>) v2);
+  public static double cosAngle(NumberVector v1, NumberVector v2) {
+    if(v1 instanceof SparseNumberVector && v2 instanceof SparseNumberVector) {
+      return angleSparse((SparseNumberVector) v1, (SparseNumberVector) v2);
     }
-    final int dim1 = v1.getDimensionality(), dim2 = v1.getDimensionality();
+    final int dim1 = v1.getDimensionality(), dim2 = v2.getDimensionality();
     final int mindim = (dim1 <= dim2) ? dim1 : dim2;
     // Essentially, we want to compute this:
     // v1.transposeTimes(v2) / (v1.euclideanLength() * v2.euclideanLength());
     // We can just compute all three in parallel.
-    double s = 0, e1 = 0, e2 = 0;
+    double cross = 0, l1 = 0, l2 = 0;
     for(int k = 0; k < mindim; k++) {
       final double r1 = v1.doubleValue(k);
       final double r2 = v2.doubleValue(k);
-      s += r1 * r2;
-      e1 += r1 * r1;
-      e2 += r2 * r2;
+      cross += r1 * r2;
+      l1 += r1 * r1;
+      l2 += r2 * r2;
     }
     for(int k = mindim; k < dim1; k++) {
       final double r1 = v1.doubleValue(k);
-      e1 += r1 * r1;
+      l1 += r1 * r1;
     }
     for(int k = mindim; k < dim2; k++) {
       final double r2 = v2.doubleValue(k);
-      e2 += r2 * r2;
+      l2 += r2 * r2;
     }
-    final double a = Math.sqrt((s / e1) * (s / e2));
-    return (a > 1.) ? 1. : a;
+    if(cross == 0.) {
+      return 0.;
+    }
+    if(l1 == 0. || l2 == 0.) {
+      return 1.;
+    }
+    final double a = Math.sqrt((cross / l1) * (cross / l2));
+    return (a < 1.) ? a : 1.;
   }
 
   // TODO: add more precise but slower O(n^2) angle computation according to:
@@ -277,60 +282,66 @@ public final class VectorUtil {
    * @return Angle
    */
   public static double minCosAngle(SpatialComparable v1, SpatialComparable v2) {
-    if(v1 instanceof NumberVector<?> && v2 instanceof NumberVector<?>) {
-      return cosAngle((NumberVector<?>) v1, (NumberVector<?>) v2);
+    if(v1 instanceof NumberVector && v2 instanceof NumberVector) {
+      return cosAngle((NumberVector) v1, (NumberVector) v2);
     }
-    final int dim1 = v1.getDimensionality(), dim2 = v1.getDimensionality();
+    final int dim1 = v1.getDimensionality(), dim2 = v2.getDimensionality();
     final int mindim = (dim1 <= dim2) ? dim1 : dim2;
     // Essentially, we want to compute this:
     // absmax(v1.transposeTimes(v2))/(min(v1.euclideanLength())*min(v2.euclideanLength()));
     // We can just compute all three in parallel.
-    double s1 = 0, s2 = 0, e1 = 0, e2 = 0;
+    double s1 = 0, s2 = 0, l1 = 0, l2 = 0;
     for(int k = 0; k < mindim; k++) {
       final double min1 = v1.getMin(k), max1 = v1.getMax(k);
       final double min2 = v2.getMin(k), max2 = v2.getMax(k);
       final double p1 = min1 * min2, p2 = min1 * max2;
       final double p3 = max1 * min2, p4 = max1 * max2;
-      s1 += Math.max(Math.max(p1, p2), Math.max(p3, p4));
-      s2 += Math.min(Math.min(p1, p2), Math.min(p3, p4));
+      s1 += Math.max(p1 > p2 ? p1 : p2, p3 > p4 ? p3 : p4);
+      s2 += Math.min(p1 < p2 ? p1 : p2, p3 < p4 ? p3 : p4);
       if(max1 < 0) {
-        e1 += max1 * max1;
+        l1 += max1 * max1;
       }
       else if(min1 > 0) {
-        e1 += min1 * min1;
+        l1 += min1 * min1;
       } // else: 0
       if(max2 < 0) {
-        e2 += max2 * max2;
+        l2 += max2 * max2;
       }
       else if(min2 > 0) {
-        e2 += min2 * min2;
+        l2 += min2 * min2;
       } // else: 0
     }
     for(int k = mindim; k < dim1; k++) {
       final double min1 = v1.getMin(k), max1 = v1.getMax(k);
       if(max1 < 0.) {
-        e1 += max1 * max1;
+        l1 += max1 * max1;
       }
       else if(min1 > 0.) {
-        e1 += min1 * min1;
+        l1 += min1 * min1;
       } // else: 0
     }
     for(int k = mindim; k < dim2; k++) {
       final double min2 = v2.getMin(k), max2 = v2.getMax(k);
       if(max2 < 0.) {
-        e2 += max2 * max2;
+        l2 += max2 * max2;
       }
       else if(min2 > 0.) {
-        e2 += min2 * min2;
+        l2 += min2 * min2;
       } // else: 0
     }
-    final double s = Math.max(s1, Math.abs(s2));
-    final double a = Math.sqrt((s / e1) * (s / e2));
-    return (a > 1.) ? 1. : a;
+    final double cross = Math.max(s1, Math.abs(s2));
+    if(cross == 0.) {
+      return 0.;
+    }
+    if(l1 == 0. || l2 == 0.) {
+      return 1.;
+    }
+    final double a = Math.sqrt((cross / l1) * (cross / l2));
+    return (a < 1.) ? a : 1.;
   }
 
   /**
-   * Provides the scalar product (inner product) of this and the given
+   * Compute the scalar product (inner product) of this and the given
    * DoubleVector.
    * 
    * @param d1 the first vector to compute the scalar product for
@@ -338,7 +349,7 @@ public final class VectorUtil {
    * @return the scalar product (inner product) of this and the given
    *         DoubleVector
    */
-  public static double scalarProduct(NumberVector<?> d1, NumberVector<?> d2) {
+  public static double scalarProduct(NumberVector d1, NumberVector d2) {
     final int dim = d1.getDimensionality();
     double result = 0.;
     for(int i = 0; i < dim; i++) {
@@ -354,7 +365,7 @@ public final class VectorUtil {
    * @param sample Sample set
    * @return Medoid vector
    */
-  public static Vector computeMedoid(Relation<? extends NumberVector<?>> relation, DBIDs sample) {
+  public static Vector computeMedoid(Relation<? extends NumberVector> relation, DBIDs sample) {
     final int dim = RelationUtil.dimensionality(relation);
     ArrayModifiableDBIDs mids = DBIDUtil.newArray(sample);
     SortDBIDsBySingleDimension s = new SortDBIDsBySingleDimension(relation);
@@ -375,7 +386,7 @@ public final class VectorUtil {
    * @param v Vector
    * @return {@code mat * v}, as double array.
    */
-  public static double[] fastTimes(Matrix mat, NumberVector<?> v) {
+  public static double[] fastTimes(Matrix mat, NumberVector v) {
     final double[][] elements = mat.getArrayRef();
     final int cdim = mat.getColumnDimensionality();
     final double[] X = new double[elements.length];
@@ -407,7 +418,7 @@ public final class VectorUtil {
     /**
      * The relation to sort.
      */
-    private Relation<? extends NumberVector<?>> data;
+    private Relation<? extends NumberVector> data;
 
     /**
      * Constructor.
@@ -415,7 +426,7 @@ public final class VectorUtil {
      * @param data Vector data source
      * @param dim Dimension to sort by
      */
-    public SortDBIDsBySingleDimension(Relation<? extends NumberVector<?>> data, int dim) {
+    public SortDBIDsBySingleDimension(Relation<? extends NumberVector> data, int dim) {
       super();
       this.data = data;
       this.d = dim;
@@ -426,7 +437,7 @@ public final class VectorUtil {
      * 
      * @param data Vector data source
      */
-    public SortDBIDsBySingleDimension(Relation<? extends NumberVector<?>> data) {
+    public SortDBIDsBySingleDimension(Relation<? extends NumberVector> data) {
       super();
       this.data = data;
     };
@@ -462,7 +473,7 @@ public final class VectorUtil {
    * 
    * @apiviz.exclude
    */
-  public static class SortVectorsBySingleDimension implements Comparator<NumberVector<?>> {
+  public static class SortVectorsBySingleDimension implements Comparator<NumberVector> {
     /**
      * Dimension to sort with.
      */
@@ -504,13 +515,13 @@ public final class VectorUtil {
     }
 
     @Override
-    public int compare(NumberVector<?> o1, NumberVector<?> o2) {
+    public int compare(NumberVector o1, NumberVector o2) {
       return Double.compare(o1.doubleValue(d), o2.doubleValue(d));
     }
   }
 
   /**
-   * Provides a new NumberVector as a projection on the specified attributes.
+   * Project a number vector to the specified attributes.
    * 
    * @param v a NumberVector to project
    * @param selectedAttributes the attributes selected for projection
@@ -518,9 +529,9 @@ public final class VectorUtil {
    * @param <V> Vector type
    * @return a new NumberVector as a projection on the specified attributes
    */
-  public static <V extends NumberVector<?>> V project(V v, BitSet selectedAttributes, NumberVector.Factory<V, ?> factory) {
+  public static <V extends NumberVector> V project(V v, BitSet selectedAttributes, NumberVector.Factory<V> factory) {
     if(factory instanceof SparseNumberVector.Factory) {
-      final SparseNumberVector.Factory<?, ?> sfactory = (SparseNumberVector.Factory<?, ?>) factory;
+      final SparseNumberVector.Factory<?> sfactory = (SparseNumberVector.Factory<?>) factory;
       TIntDoubleHashMap values = new TIntDoubleHashMap(selectedAttributes.cardinality(), 1);
       for(int d = selectedAttributes.nextSetBit(0); d >= 0; d = selectedAttributes.nextSetBit(d + 1)) {
         if(v.doubleValue(d) != 0.0) {