Mailing-List: contact mahout-commits-help@lucene.apache.org; run by ezmlm
Precedence: bulk
Reply-To: mahout-dev@lucene.apache.org
Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit
Subject: svn commit: r891983 [3/47] - in /lucene/mahout/trunk: ./ core/
 core/src/main/java/org/apache/mahout/cf/taste/hadoop/item/
 core/src/main/java/org/apache/mahout/clustering/
 core/src/main/java/org/apache/mahout/clustering/canopy/
 core/src/main/java/org/ap...
Date: Thu, 17 Dec 2009 23:22:41 -0000
To: mahout-commits@lucene.apache.org
From: gsingers@apache.org
Message-Id: <20091217232310.18E332388AC8@eris.apache.org>

Added: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/AbstractVector.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/AbstractVector.java?rev=891983&view=auto
==============================================================================
--- lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/AbstractVector.java (added)
+++ lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/AbstractVector.java Thu Dec 17 23:22:16 2009
@@ -0,0 +1,545 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.mahout.math;
+
+import com.google.gson.Gson;
+import com.google.gson.GsonBuilder;
+import com.google.gson.reflect.TypeToken;
+import org.apache.hadoop.io.WritableComparable;
+
+import java.io.DataInput;
+import java.io.DataOutput;
+import java.io.IOException;
+import java.lang.reflect.Type;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.Map;
+
+/** Implementations of generic capabilities like sum of elements and dot products */
+public abstract class AbstractVector implements Vector {
+
+  /**
+   * User-settable mapping between String labels and Integer indices. Marked transient so that it will not be serialized
+   * with each vector instance.
+   */
+  private transient Map<String, Integer> bindings;
+
+  private String name;
+
+  protected AbstractVector() {
+  }
+
+  protected AbstractVector(String name) {
+    this.name = name;
+  }
+
+  /**
+   * Subclasses must override to return an appropriately sparse or dense result
+   *
+   * @param rows    the row cardinality
+   * @param columns the column cardinality
+   * @return a Matrix
+   */
+  protected abstract Matrix matrixLike(int rows, int columns);
+
+
+  @Override
+  public Vector clone() {
+    AbstractVector clone;
+    try {
+      clone = (AbstractVector) super.clone();
+    } catch (CloneNotSupportedException cnse) {
+      throw new IllegalStateException(cnse); // Can't happen
+    }
+    if (bindings != null) {
+      clone.bindings = (Map<String, Integer>) ((HashMap<String, Integer>) bindings).clone();
+    }
+    // name is OK
+    return clone;
+  }
+
+  @Override
+  public Vector divide(double x) {
+    Vector result = clone();
+    Iterator<Element> iter = result.iterateNonZero();
+    while (iter.hasNext()) {
+      Element element = iter.next();
+      int index = element.index();
+      result.setQuick(index, element.get() / x);
+    }
+
+    return result;
+  }
+
+  @Override
+  public double dot(Vector x) {
+    if (size() != x.size()) {
+      throw new CardinalityException();
+    }
+    double result = 0;
+    Iterator<Element> iter = iterateNonZero();
+    while (iter.hasNext()) {
+      Element element = iter.next();
+      result += element.get() * x.getQuick(element.index());
+    }
+
+    return result;
+  }
+
+  @Override
+  public double get(int index) {
+    if (index >= 0 && index < size()) {
+      return getQuick(index);
+    } else {
+      throw new IndexException();
+    }
+  }
+
+  @Override
+  public Vector minus(Vector x) {
+    if (size() != x.size()) {
+      throw new CardinalityException();
+    }
+    Vector result = clone();
+    Iterator<Element> iter = x.iterateNonZero();
+    while (iter.hasNext()) {
+      Element e = iter.next();
+      result.setQuick(e.index(), getQuick(e.index()) - e.get());
+    }
+    return result;
+  }
+
+  @Override
+  public Vector normalize() {
+    return divide(Math.sqrt(dot(this)));
+  }
+
+  @Override
+  public Vector normalize(double power) {
+    return divide(norm(power));
+  }
+
+  @Override
+  public double norm(double power) {
+    if (power < 0.0) {
+      throw new IllegalArgumentException("Power must be >= 0");
+    }
+    // we can special case certain powers
+    if (Double.isInfinite(power)) {
+      return maxValue();
+    } else if (power == 2.0) {
+      return Math.sqrt(dot(this));
+    } else if (power == 1.0) {
+      return zSum();
+    } else if (power == 0.0) {
+      // this is the number of non-zero elements
+      double val = 0.0;
+      Iterator<Element> iter = this.iterateNonZero();
+      while (iter.hasNext()) {
+        val += iter.next().get() == 0 ? 0 : 1;
+      }
+      return val;
+    } else {
+      double val = 0.0;
+      Iterator<Element> iter = this.iterateNonZero();
+      while (iter.hasNext()) {
+        Element element = iter.next();
+        val += Math.pow(element.get(), power);
+      }
+      return Math.pow(val, 1.0 / power);
+    }
+  }
+
+  @Override
+  public double maxValue() {
+    double result = Double.MIN_VALUE;
+    for (int i = 0; i < size(); i++) {
+      result = Math.max(result, getQuick(i));
+    }
+    return result;
+  }
+
+  @Override
+  public int maxValueIndex() {
+    int result = -1;
+    double max = Double.MIN_VALUE;
+    for (int i = 0; i < size(); i++) {
+      double tmp = getQuick(i);
+      if (tmp > max) {
+        max = tmp;
+        result = i;
+      }
+    }
+    return result;
+  }
+
+  @Override
+  public Vector plus(double x) {
+    Vector result = clone();
+    for (int i = 0; i < result.size(); i++) {
+      result.setQuick(i, getQuick(i) + x);
+    }
+    return result;
+  }
+
+  @Override
+  public Vector plus(Vector x) {
+    if (size() != x.size()) {
+      throw new CardinalityException();
+    }
+    //TODO: get smarter about this, if we are adding a dense to a sparse, then we should return a dense
+    Vector result = clone();
+    Iterator<Element> iter = x.iterateNonZero();
+    while (iter.hasNext()) {
+      Element e = iter.next();
+      result.setQuick(e.index(), getQuick(e.index()) + e.get());
+    }
+
+    /*for (int i = 0; i < result.size(); i++)
+      result.setQuick(i, getQuick(i) + x.getQuick(i));*/
+    return result;
+  }
+
+  @Override
+  public void set(int index, double value) {
+    if (index >= 0 && index < size()) {
+      setQuick(index, value);
+    } else {
+      throw new IndexException();
+    }
+  }
+
+  @Override
+  public Vector times(double x) {
+    Vector result = clone();
+    Iterator<Element> iter = iterateNonZero();
+    while (iter.hasNext()) {
+      Element element = iter.next();
+      int index = element.index();
+      result.setQuick(index, element.get() * x);
+    }
+
+    return result;
+  }
+
+  @Override
+  public Vector times(Vector x) {
+    if (size() != x.size()) {
+      throw new CardinalityException();
+    }
+    Vector result = clone();
+    Iterator<Element> iter = result.iterateNonZero();
+    while (iter.hasNext()) {
+      Element element = iter.next();
+      int index = element.index();
+      result.setQuick(index, element.get() * x.getQuick(index));
+    }
+
+    return result;
+  }
+
+  @Override
+  public double zSum() {
+    double result = 0;
+    Iterator<Element> iter = iterateNonZero();
+    while (iter.hasNext()) {
+      Element element = iter.next();
+      result += element.get();
+    }
+
+    return result;
+  }
+
+  @Override
+  public Vector assign(double value) {
+    for (int i = 0; i < size(); i++) {
+      setQuick(i, value);
+    }
+    return this;
+  }
+
+  @Override
+  public Vector assign(double[] values) {
+    if (values.length != size()) {
+      throw new CardinalityException();
+    }
+    for (int i = 0; i < size(); i++) {
+      setQuick(i, values[i]);
+    }
+    return this;
+  }
+
+  @Override
+  public Vector assign(Vector other) {
+    if (other.size() != size()) {
+      throw new CardinalityException();
+    }
+    for (int i = 0; i < size(); i++) {
+      setQuick(i, other.getQuick(i));
+    }
+    return this;
+  }
+
+  @Override
+  public Vector assign(BinaryFunction f, double y) {
+    for (int i = 0; i < size(); i++) {
+      setQuick(i, f.apply(getQuick(i), y));
+    }
+    return this;
+  }
+
+  @Override
+  public Vector assign(UnaryFunction function) {
+    for (int i = 0; i < size(); i++) {
+      setQuick(i, function.apply(getQuick(i)));
+    }
+    return this;
+  }
+
+  @Override
+  public Vector assign(Vector other, BinaryFunction function) {
+    if (other.size() != size()) {
+      throw new CardinalityException();
+    }
+    for (int i = 0; i < size(); i++) {
+      setQuick(i, function.apply(getQuick(i), other.getQuick(i)));
+    }
+    return this;
+  }
+
+  @Override
+  public Matrix cross(Vector other) {
+    Matrix result = matrixLike(size(), other.size());
+    for (int row = 0; row < size(); row++) {
+      result.assignRow(row, other.times(getQuick(row)));
+    }
+    return result;
+  }
+
+  /**
+   * Decodes a point from its WritableComparable<?> representation.
+   *
+   * @param writableComparable a WritableComparable<?> produced by asWritableComparable. Note the payload remainder: it
+   *                           is optional, but can be present.
+   * @return the n-dimensional point
+   */
+  public static Vector decodeVector(WritableComparable<?> writableComparable) {
+    return decodeVector(writableComparable.toString());
+  }
+
+  /**
+   * Decodes a point from its string representation.
+   *
+   * @param formattedString a formatted String produced by asFormatString. Note the payload remainder: it is optional,
+   *                        but can be present.
+   * @return the n-dimensional point
+   */
+  public static Vector decodeVector(String formattedString) {
+    Type vectorType = new TypeToken<Vector>() {
+    }.getType();
+    GsonBuilder builder = new GsonBuilder();
+    builder.registerTypeAdapter(vectorType, new JsonVectorAdapter());
+    Gson gson = builder.create();
+    return gson.fromJson(formattedString, vectorType);
+  }
+
+  @Override
+  public String getName() {
+    return name;
+  }
+
+  @Override
+  public void setName(String name) {
+    this.name = name;
+  }
+
+  @Override
+  public String asFormatString() {
+    Type vectorType = new TypeToken<Vector>() {
+    }.getType();
+    GsonBuilder builder = new GsonBuilder();
+    builder.registerTypeAdapter(vectorType, new JsonVectorAdapter());
+    Gson gson = builder.create();
+    return gson.toJson(this, vectorType);
+  }
+
+  /**
+   * Compare whether two Vector implementations have the same elements, regardless of the implementation and name. Two
+   * Vectors are equivalent if they have the same cardinality and all of their values are the same. <p/> Does not
+   * compare {@link Vector#getName()}.
+   *
+   * @param left  The left hand Vector to compare
+   * @param right The right hand Vector
+   * @return true if the two Vectors have the same cardinality and the same values
+   * @see #strictEquivalence(Vector, Vector)
+   * @see Vector#equals(Object)
+   */
+  public static boolean equivalent(Vector left, Vector right) {
+    if (left == right) {
+      return true;
+    }
+    int leftCardinality = left.size();
+    if (leftCardinality == right.size()) {
+      for (int i = 0; i < leftCardinality; i++) {
+        if (left.getQuick(i) != right.getQuick(i)) {
+          return false;
+        }
+
+      }
+    } else {
+      return false;
+    }
+    return true;
+  }
+
+  /**
+   * Compare whether two Vector implementations are the same, including the underlying implementation. Two Vectors are
+   * the same if they have the same cardinality, same name and all of their values are the same.
+   *
+   * @param left  The left hand Vector to compare
+   * @param right The right hand Vector
+   * @return true if the two Vectors have the same cardinality and the same values
+   */
+  public static boolean strictEquivalence(Vector left, Vector right) {
+    if (left == right) {
+      return true;
+    }
+    if (!(left.getClass().equals(right.getClass()))) {
+      return false;
+    }
+    String leftName = left.getName();
+    String rightName = right.getName();
+    if (leftName != null && rightName != null && !leftName.equals(rightName)) {
+      return false;
+    } else if ((leftName != null && rightName == null)
+        || (rightName != null && leftName == null)) {
+      return false;
+    }
+
+    int leftCardinality = left.size();
+    if (leftCardinality == right.size()) {
+      for (int i = 0; i < leftCardinality; i++) {
+        if (left.getQuick(i) != right.getQuick(i)) {
+          return false;
+        }
+
+      }
+    } else {
+      return false;
+    }
+    return true;
+  }
+
+  @Override
+  public int hashCode() {
+    int prime = 31;
+    int result = prime + ((name == null) ? 0 : name.hashCode());
+    result = prime * result + size();
+    Iterator<Element> iter = iterateNonZero(true);
+    while (iter.hasNext()) {
+      Element ele = iter.next();
+      result = prime * result + ele.index();
+      long v = Double.doubleToLongBits(ele.get());
+      result = prime * result + (int) (v ^ (v >> 32));
+    }
+
+    return result;
+  }
+
+
+  @Override
+  public double get(String label) throws IndexException, UnboundLabelException {
+    if (bindings == null) {
+      throw new UnboundLabelException();
+    }
+    Integer index = bindings.get(label);
+    if (index == null) {
+      throw new UnboundLabelException();
+    }
+    return get(index);
+  }
+
+  @Override
+  public Map<String, Integer> getLabelBindings() {
+    return bindings;
+  }
+
+  @Override
+  public void set(String label, double value) throws IndexException,
+      UnboundLabelException {
+    if (bindings == null) {
+      throw new UnboundLabelException();
+    }
+    Integer index = bindings.get(label);
+    if (index == null) {
+      throw new UnboundLabelException();
+    }
+    set(index, value);
+  }
+
+  @Override
+  public void setLabelBindings(Map<String, Integer> bindings) {
+    this.bindings = bindings;
+  }
+
+  @Override
+  public void set(String label, int index, double value) throws IndexException {
+    if (bindings == null) {
+      bindings = new HashMap<String, Integer>();
+    }
+    bindings.put(label, index);
+    set(index, value);
+  }
+
+  // cache most recent vector instance class name
+  private static String instanceClassName;
+
+  // cache most recent vector instance class
+  private static Class<? extends Vector> instanceClass;
+
+  /** Read and return a vector from the input */
+  public static Vector readVector(DataInput in) throws IOException {
+    String vectorClassName = in.readUTF();
+    Vector vector;
+    try {
+      if (!vectorClassName.equals(instanceClassName)) {
+        instanceClassName = vectorClassName;
+        instanceClass = Class.forName(vectorClassName).asSubclass(Vector.class);
+      }
+      vector = instanceClass.newInstance();
+    } catch (ClassNotFoundException e) {
+      throw new IllegalStateException(e);
+    } catch (IllegalAccessException e) {
+      throw new IllegalStateException(e);
+    } catch (InstantiationException e) {
+      throw new IllegalStateException(e);
+    }
+    vector.readFields(in);
+    return vector;
+  }
+
+  /** Write the vector to the output */
+  public static void writeVector(DataOutput out, Vector vector)
+      throws IOException {
+    String vectorClassName = vector.getClass().getName();
+    out.writeUTF(vectorClassName);
+    vector.write(out);
+
+  }
+
+}

Propchange: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/AbstractVector.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/Arrays.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/Arrays.java?rev=891983&view=auto
==============================================================================
--- lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/Arrays.java (added)
+++ lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/Arrays.java Thu Dec 17 23:22:16 2009
@@ -0,0 +1,603 @@
+/*
+Copyright 1999 CERN - European Organization for Nuclear Research.
+Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose 
+is hereby granted without fee, provided that the above copyright notice appear in all copies and 
+that both that copyright notice and this permission notice appear in supporting documentation. 
+CERN makes no representations about the suitability of this software for any purpose. 
+It is provided "as is" without expressed or implied warranty.
+*/
+package org.apache.mahout.math;
+
+/**
+ * Array manipulations; complements <tt>java.util.Arrays</tt>.
+ *
+ * @see java.util.Arrays
+ * @see org.apache.mahout.math.Sorting
+ *
+ */
+
+/** @deprecated until unit tests are in place.  Until this time, this class/interface is unsupported. */
+@Deprecated
+public class Arrays {
+
+  /** Makes this class non instantiable, but still let's others inherit from it. */
+  private Arrays() {
+  }
+
+  /**
+   * Ensures that a given array can hold up to <tt>minCapacity</tt> elements.
+   *
+   * Returns the identical array if it can hold at least the number of elements specified. Otherwise, returns a new
+   * array with increased capacity containing the same elements, ensuring that it can hold at least the number of
+   * elements specified by the minimum capacity argument.
+   *
+   * @param minCapacity the desired minimum capacity.
+   */
+  public static byte[] ensureCapacity(byte[] array, int minCapacity) {
+    int oldCapacity = array.length;
+    byte[] newArray;
+    if (minCapacity > oldCapacity) {
+      int newCapacity = (oldCapacity * 3) / 2 + 1;
+      if (newCapacity < minCapacity) {
+        newCapacity = minCapacity;
+      }
+
+      newArray = new byte[newCapacity];
+      System.arraycopy(array, 0, newArray, 0, oldCapacity);
+    } else {
+      newArray = array;
+    }
+    return newArray;
+  }
+
+  /**
+   * Ensures that a given array can hold up to <tt>minCapacity</tt> elements.
+   *
+   * Returns the identical array if it can hold at least the number of elements specified. Otherwise, returns a new
+   * array with increased capacity containing the same elements, ensuring that it can hold at least the number of
+   * elements specified by the minimum capacity argument.
+   *
+   * @param minCapacity the desired minimum capacity.
+   */
+  public static char[] ensureCapacity(char[] array, int minCapacity) {
+    int oldCapacity = array.length;
+    char[] newArray;
+    if (minCapacity > oldCapacity) {
+      int newCapacity = (oldCapacity * 3) / 2 + 1;
+      if (newCapacity < minCapacity) {
+        newCapacity = minCapacity;
+      }
+
+      newArray = new char[newCapacity];
+      System.arraycopy(array, 0, newArray, 0, oldCapacity);
+    } else {
+      newArray = array;
+    }
+    return newArray;
+  }
+
+  /**
+   * Ensures that a given array can hold up to <tt>minCapacity</tt> elements.
+   *
+   * Returns the identical array if it can hold at least the number of elements specified. Otherwise, returns a new
+   * array with increased capacity containing the same elements, ensuring that it can hold at least the number of
+   * elements specified by the minimum capacity argument.
+   *
+   * @param minCapacity the desired minimum capacity.
+   */
+  public static double[] ensureCapacity(double[] array, int minCapacity) {
+    int oldCapacity = array.length;
+    double[] newArray;
+    if (minCapacity > oldCapacity) {
+      int newCapacity = (oldCapacity * 3) / 2 + 1;
+      if (newCapacity < minCapacity) {
+        newCapacity = minCapacity;
+      }
+
+      newArray = new double[newCapacity];
+      //for (int i = oldCapacity; --i >= 0; ) newArray[i] = array[i];
+      System.arraycopy(array, 0, newArray, 0, oldCapacity);
+    } else {
+      newArray = array;
+    }
+    return newArray;
+  }
+
+  /**
+   * Ensures that a given array can hold up to <tt>minCapacity</tt> elements.
+   *
+   * Returns the identical array if it can hold at least the number of elements specified. Otherwise, returns a new
+   * array with increased capacity containing the same elements, ensuring that it can hold at least the number of
+   * elements specified by the minimum capacity argument.
+   *
+   * @param minCapacity the desired minimum capacity.
+   */
+  public static float[] ensureCapacity(float[] array, int minCapacity) {
+    int oldCapacity = array.length;
+    float[] newArray;
+    if (minCapacity > oldCapacity) {
+      int newCapacity = (oldCapacity * 3) / 2 + 1;
+      if (newCapacity < minCapacity) {
+        newCapacity = minCapacity;
+      }
+
+      newArray = new float[newCapacity];
+      System.arraycopy(array, 0, newArray, 0, oldCapacity);
+    } else {
+      newArray = array;
+    }
+    return newArray;
+  }
+
+  /**
+   * Ensures that a given array can hold up to <tt>minCapacity</tt> elements.
+   *
+   * Returns the identical array if it can hold at least the number of elements specified. Otherwise, returns a new
+   * array with increased capacity containing the same elements, ensuring that it can hold at least the number of
+   * elements specified by the minimum capacity argument.
+   *
+   * @param minCapacity the desired minimum capacity.
+   */
+  public static int[] ensureCapacity(int[] array, int minCapacity) {
+    int oldCapacity = array.length;
+    int[] newArray;
+    if (minCapacity > oldCapacity) {
+      int newCapacity = (oldCapacity * 3) / 2 + 1;
+      if (newCapacity < minCapacity) {
+        newCapacity = minCapacity;
+      }
+
+      newArray = new int[newCapacity];
+      System.arraycopy(array, 0, newArray, 0, oldCapacity);
+    } else {
+      newArray = array;
+    }
+    return newArray;
+  }
+
+  /**
+   * Ensures that a given array can hold up to <tt>minCapacity</tt> elements.
+   *
+   * Returns the identical array if it can hold at least the number of elements specified. Otherwise, returns a new
+   * array with increased capacity containing the same elements, ensuring that it can hold at least the number of
+   * elements specified by the minimum capacity argument.
+   *
+   * @param minCapacity the desired minimum capacity.
+   */
+  public static long[] ensureCapacity(long[] array, int minCapacity) {
+    int oldCapacity = array.length;
+    long[] newArray;
+    if (minCapacity > oldCapacity) {
+      int newCapacity = (oldCapacity * 3) / 2 + 1;
+      if (newCapacity < minCapacity) {
+        newCapacity = minCapacity;
+      }
+
+      newArray = new long[newCapacity];
+      System.arraycopy(array, 0, newArray, 0, oldCapacity);
+    } else {
+      newArray = array;
+    }
+    return newArray;
+  }
+
+  /**
+   * Ensures that a given array can hold up to <tt>minCapacity</tt> elements.
+   *
+   * Returns the identical array if it can hold at least the number of elements specified. Otherwise, returns a new
+   * array with increased capacity containing the same elements, ensuring that it can hold at least the number of
+   * elements specified by the minimum capacity argument.
+   *
+   * @param minCapacity the desired minimum capacity.
+   */
+  public static Object[] ensureCapacity(Object[] array, int minCapacity) {
+    int oldCapacity = array.length;
+    Object[] newArray;
+    if (minCapacity > oldCapacity) {
+      int newCapacity = (oldCapacity * 3) / 2 + 1;
+      if (newCapacity < minCapacity) {
+        newCapacity = minCapacity;
+      }
+
+      newArray = new Object[newCapacity];
+      System.arraycopy(array, 0, newArray, 0, oldCapacity);
+    } else {
+      newArray = array;
+    }
+    return newArray;
+  }
+
+  /**
+   * Ensures that a given array can hold up to <tt>minCapacity</tt> elements.
+   *
+   * Returns the identical array if it can hold at least the number of elements specified. Otherwise, returns a new
+   * array with increased capacity containing the same elements, ensuring that it can hold at least the number of
+   * elements specified by the minimum capacity argument.
+   *
+   * @param minCapacity the desired minimum capacity.
+   */
+  public static short[] ensureCapacity(short[] array, int minCapacity) {
+    int oldCapacity = array.length;
+    short[] newArray;
+    if (minCapacity > oldCapacity) {
+      int newCapacity = (oldCapacity * 3) / 2 + 1;
+      if (newCapacity < minCapacity) {
+        newCapacity = minCapacity;
+      }
+
+      newArray = new short[newCapacity];
+      System.arraycopy(array, 0, newArray, 0, oldCapacity);
+    } else {
+      newArray = array;
+    }
+    return newArray;
+  }
+
+  /**
+   * Ensures that a given array can hold up to <tt>minCapacity</tt> elements.
+   *
+   * Returns the identical array if it can hold at least the number of elements specified. Otherwise, returns a new
+   * array with increased capacity containing the same elements, ensuring that it can hold at least the number of
+   * elements specified by the minimum capacity argument.
+   *
+   * @param minCapacity the desired minimum capacity.
+   */
+  public static boolean[] ensureCapacity(boolean[] array, int minCapacity) {
+    int oldCapacity = array.length;
+    boolean[] newArray;
+    if (minCapacity > oldCapacity) {
+      int newCapacity = (oldCapacity * 3) / 2 + 1;
+      if (newCapacity < minCapacity) {
+        newCapacity = minCapacity;
+      }
+
+      newArray = new boolean[newCapacity];
+      System.arraycopy(array, 0, newArray, 0, oldCapacity);
+    } else {
+      newArray = array;
+    }
+    return newArray;
+  }
+
+  /**
+   * Returns a string representation of the specified array.  The string representation consists of a list of the
+   * arrays's elements, enclosed in square brackets (<tt>"[]"</tt>).  Adjacent elements are separated by the characters
+   * <tt>", "</tt> (comma and space).
+   *
+   * @return a string representation of the specified array.
+   */
+  public static String toString(byte[] array) {
+    StringBuilder buf = new StringBuilder();
+    buf.append('[');
+    int maxIndex = array.length - 1;
+    for (int i = 0; i <= maxIndex; i++) {
+      buf.append(array[i]);
+      if (i < maxIndex) {
+        buf.append(", ");
+      }
+    }
+    buf.append(']');
+    return buf.toString();
+  }
+
+  /**
+   * Returns a string representation of the specified array.  The string representation consists of a list of the
+   * arrays's elements, enclosed in square brackets (<tt>"[]"</tt>).  Adjacent elements are separated by the characters
+   * <tt>", "</tt> (comma and space).
+   *
+   * @return a string representation of the specified array.
+   */
+  public static String toString(char[] array) {
+    StringBuilder buf = new StringBuilder();
+    buf.append('[');
+    int maxIndex = array.length - 1;
+    for (int i = 0; i <= maxIndex; i++) {
+      buf.append(array[i]);
+      if (i < maxIndex) {
+        buf.append(", ");
+      }
+    }
+    buf.append(']');
+    return buf.toString();
+  }
+
+  /**
+   * Returns a string representation of the specified array.  The string representation consists of a list of the
+   * arrays's elements, enclosed in square brackets (<tt>"[]"</tt>).  Adjacent elements are separated by the characters
+   * <tt>", "</tt> (comma and space).
+   *
+   * @return a string representation of the specified array.
+   */
+  public static String toString(double[] array) {
+    StringBuilder buf = new StringBuilder();
+    buf.append('[');
+    int maxIndex = array.length - 1;
+    for (int i = 0; i <= maxIndex; i++) {
+      buf.append(array[i]);
+      if (i < maxIndex) {
+        buf.append(", ");
+      }
+    }
+    buf.append(']');
+    return buf.toString();
+  }
+
+  /**
+   * Returns a string representation of the specified array.  The string representation consists of a list of the
+   * arrays's elements, enclosed in square brackets (<tt>"[]"</tt>).  Adjacent elements are separated by the characters
+   * <tt>", "</tt> (comma and space).
+   *
+   * @return a string representation of the specified array.
+   */
+  public static String toString(float[] array) {
+    StringBuilder buf = new StringBuilder();
+    buf.append('[');
+    int maxIndex = array.length - 1;
+    for (int i = 0; i <= maxIndex; i++) {
+      buf.append(array[i]);
+      if (i < maxIndex) {
+        buf.append(", ");
+      }
+    }
+    buf.append(']');
+    return buf.toString();
+  }
+
+  /**
+   * Returns a string representation of the specified array.  The string representation consists of a list of the
+   * arrays's elements, enclosed in square brackets (<tt>"[]"</tt>).  Adjacent elements are separated by the characters
+   * <tt>", "</tt> (comma and space).
+   *
+   * @return a string representation of the specified array.
+   */
+  public static String toString(int[] array) {
+    StringBuilder buf = new StringBuilder();
+    buf.append('[');
+    int maxIndex = array.length - 1;
+    for (int i = 0; i <= maxIndex; i++) {
+      buf.append(array[i]);
+      if (i < maxIndex) {
+        buf.append(", ");
+      }
+    }
+    buf.append(']');
+    return buf.toString();
+  }
+
+  /**
+   * Returns a string representation of the specified array.  The string representation consists of a list of the
+   * arrays's elements, enclosed in square brackets (<tt>"[]"</tt>).  Adjacent elements are separated by the characters
+   * <tt>", "</tt> (comma and space).
+   *
+   * @return a string representation of the specified array.
+   */
+  public static String toString(long[] array) {
+    StringBuilder buf = new StringBuilder();
+    buf.append('[');
+    int maxIndex = array.length - 1;
+    for (int i = 0; i <= maxIndex; i++) {
+      buf.append(array[i]);
+      if (i < maxIndex) {
+        buf.append(", ");
+      }
+    }
+    buf.append(']');
+    return buf.toString();
+  }
+
+  /**
+   * Returns a string representation of the specified array.  The string representation consists of a list of the
+   * arrays's elements, enclosed in square brackets (<tt>"[]"</tt>).  Adjacent elements are separated by the characters
+   * <tt>", "</tt> (comma and space).
+   *
+   * @return a string representation of the specified array.
+   */
+  public static String toString(Object[] array) {
+    StringBuilder buf = new StringBuilder();
+    buf.append('[');
+    int maxIndex = array.length - 1;
+    for (int i = 0; i <= maxIndex; i++) {
+      buf.append(array[i]);
+      if (i < maxIndex) {
+        buf.append(", ");
+      }
+    }
+    buf.append(']');
+    return buf.toString();
+  }
+
+  /**
+   * Returns a string representation of the specified array.  The string representation consists of a list of the
+   * arrays's elements, enclosed in square brackets (<tt>"[]"</tt>).  Adjacent elements are separated by the characters
+   * <tt>", "</tt> (comma and space).
+   *
+   * @return a string representation of the specified array.
+   */
+  public static String toString(short[] array) {
+    StringBuilder buf = new StringBuilder();
+    buf.append('[');
+    int maxIndex = array.length - 1;
+    for (int i = 0; i <= maxIndex; i++) {
+      buf.append(array[i]);
+      if (i < maxIndex) {
+        buf.append(", ");
+      }
+    }
+    buf.append(']');
+    return buf.toString();
+  }
+
+  /**
+   * Returns a string representation of the specified array.  The string representation consists of a list of the
+   * arrays's elements, enclosed in square brackets (<tt>"[]"</tt>).  Adjacent elements are separated by the characters
+   * <tt>", "</tt> (comma and space).
+   *
+   * @return a string representation of the specified array.
+   */
+  public static String toString(boolean[] array) {
+    StringBuilder buf = new StringBuilder();
+    buf.append('[');
+    int maxIndex = array.length - 1;
+    for (int i = 0; i <= maxIndex; i++) {
+      buf.append(array[i]);
+      if (i < maxIndex) {
+        buf.append(", ");
+      }
+    }
+    buf.append(']');
+    return buf.toString();
+  }
+
+  /**
+   * Ensures that the specified array cannot hold more than <tt>maxCapacity</tt> elements. An application can use this
+   * operation to minimize array storage. <p> Returns the identical array if <tt>array.length &lt;= maxCapacity</tt>.
+   * Otherwise, returns a new array with a length of <tt>maxCapacity</tt> containing the first <tt>maxCapacity</tt>
+   * elements of <tt>array</tt>.
+   *
+   * @param maxCapacity the desired maximum capacity.
+   */
+  public static byte[] trimToCapacity(byte[] array, int maxCapacity) {
+    if (array.length > maxCapacity) {
+      byte[] oldArray = array;
+      array = new byte[maxCapacity];
+      System.arraycopy(oldArray, 0, array, 0, maxCapacity);
+    }
+    return array;
+  }
+
+  /**
+   * Ensures that the specified array cannot hold more than <tt>maxCapacity</tt> elements. An application can use this
+   * operation to minimize array storage. <p> Returns the identical array if <tt>array.length &lt;= maxCapacity</tt>.
+   * Otherwise, returns a new array with a length of <tt>maxCapacity</tt> containing the first <tt>maxCapacity</tt>
+   * elements of <tt>array</tt>.
+   *
+   * @param maxCapacity the desired maximum capacity.
+   */
+  public static char[] trimToCapacity(char[] array, int maxCapacity) {
+    if (array.length > maxCapacity) {
+      char[] oldArray = array;
+      array = new char[maxCapacity];
+      System.arraycopy(oldArray, 0, array, 0, maxCapacity);
+    }
+    return array;
+  }
+
+  /**
+   * Ensures that the specified array cannot hold more than <tt>maxCapacity</tt> elements. An application can use this
+   * operation to minimize array storage. <p> Returns the identical array if <tt>array.length &lt;= maxCapacity</tt>.
+   * Otherwise, returns a new array with a length of <tt>maxCapacity</tt> containing the first <tt>maxCapacity</tt>
+   * elements of <tt>array</tt>.
+   *
+   * @param maxCapacity the desired maximum capacity.
+   */
+  public static double[] trimToCapacity(double[] array, int maxCapacity) {
+    if (array.length > maxCapacity) {
+      double[] oldArray = array;
+      array = new double[maxCapacity];
+      System.arraycopy(oldArray, 0, array, 0, maxCapacity);
+    }
+    return array;
+  }
+
+  /**
+   * Ensures that the specified array cannot hold more than <tt>maxCapacity</tt> elements. An application can use this
+   * operation to minimize array storage. <p> Returns the identical array if <tt>array.length &lt;= maxCapacity</tt>.
+   * Otherwise, returns a new array with a length of <tt>maxCapacity</tt> containing the first <tt>maxCapacity</tt>
+   * elements of <tt>array</tt>.
+   *
+   * @param maxCapacity the desired maximum capacity.
+   */
+  public static float[] trimToCapacity(float[] array, int maxCapacity) {
+    if (array.length > maxCapacity) {
+      float[] oldArray = array;
+      array = new float[maxCapacity];
+      System.arraycopy(oldArray, 0, array, 0, maxCapacity);
+    }
+    return array;
+  }
+
+  /**
+   * Ensures that the specified array cannot hold more than <tt>maxCapacity</tt> elements. An application can use this
+   * operation to minimize array storage. <p> Returns the identical array if <tt>array.length &lt;= maxCapacity</tt>.
+   * Otherwise, returns a new array with a length of <tt>maxCapacity</tt> containing the first <tt>maxCapacity</tt>
+   * elements of <tt>array</tt>.
+   *
+   * @param maxCapacity the desired maximum capacity.
+   */
+  public static int[] trimToCapacity(int[] array, int maxCapacity) {
+    if (array.length > maxCapacity) {
+      int[] oldArray = array;
+      array = new int[maxCapacity];
+      System.arraycopy(oldArray, 0, array, 0, maxCapacity);
+    }
+    return array;
+  }
+
+  /**
+   * Ensures that the specified array cannot hold more than <tt>maxCapacity</tt> elements. An application can use this
+   * operation to minimize array storage. <p> Returns the identical array if <tt>array.length &lt;= maxCapacity</tt>.
+   * Otherwise, returns a new array with a length of <tt>maxCapacity</tt> containing the first <tt>maxCapacity</tt>
+   * elements of <tt>array</tt>.
+   *
+   * @param maxCapacity the desired maximum capacity.
+   */
+  public static long[] trimToCapacity(long[] array, int maxCapacity) {
+    if (array.length > maxCapacity) {
+      long[] oldArray = array;
+      array = new long[maxCapacity];
+      System.arraycopy(oldArray, 0, array, 0, maxCapacity);
+    }
+    return array;
+  }
+
+  /**
+   * Ensures that the specified array cannot hold more than <tt>maxCapacity</tt> elements. An application can use this
+   * operation to minimize array storage. <p> Returns the identical array if <tt>array.length &lt;= maxCapacity</tt>.
+   * Otherwise, returns a new array with a length of <tt>maxCapacity</tt> containing the first <tt>maxCapacity</tt>
+   * elements of <tt>array</tt>.
+   *
+   * @param maxCapacity the desired maximum capacity.
+   */
+  public static Object[] trimToCapacity(Object[] array, int maxCapacity) {
+    if (array.length > maxCapacity) {
+      Object[] oldArray = array;
+      array = new Object[maxCapacity];
+      System.arraycopy(oldArray, 0, array, 0, maxCapacity);
+    }
+    return array;
+  }
+
+  /**
+   * Ensures that the specified array cannot hold more than <tt>maxCapacity</tt> elements. An application can use this
+   * operation to minimize array storage. <p> Returns the identical array if <tt>array.length &lt;= maxCapacity</tt>.
+   * Otherwise, returns a new array with a length of <tt>maxCapacity</tt> containing the first <tt>maxCapacity</tt>
+   * elements of <tt>array</tt>.
+   *
+   * @param maxCapacity the desired maximum capacity.
+   */
+  public static short[] trimToCapacity(short[] array, int maxCapacity) {
+    if (array.length > maxCapacity) {
+      short[] oldArray = array;
+      array = new short[maxCapacity];
+      System.arraycopy(oldArray, 0, array, 0, maxCapacity);
+    }
+    return array;
+  }
+
+  /**
+   * Ensures that the specified array cannot hold more than <tt>maxCapacity</tt> elements. An application can use this
+   * operation to minimize array storage. <p> Returns the identical array if <tt>array.length &lt;= maxCapacity</tt>.
+   * Otherwise, returns a new array with a length of <tt>maxCapacity</tt> containing the first <tt>maxCapacity</tt>
+   * elements of <tt>array</tt>.
+   *
+   * @param maxCapacity the desired maximum capacity.
+   */
+  public static boolean[] trimToCapacity(boolean[] array, int maxCapacity) {
+    if (array.length > maxCapacity) {
+      boolean[] oldArray = array;
+      array = new boolean[maxCapacity];
+      System.arraycopy(oldArray, 0, array, 0, maxCapacity);
+    }
+    return array;
+  }
+}

Propchange: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/Arrays.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/BinaryFunction.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/BinaryFunction.java?rev=891983&view=auto
==============================================================================
--- lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/BinaryFunction.java (added)
+++ lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/BinaryFunction.java Thu Dec 17 23:22:16 2009
@@ -0,0 +1,38 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.mahout.math;
+
+/**
+ * This interface allows the formulation of binary functions to be applied to matrices inside the inner loops of their
+ * implementations.
+ */
+public interface BinaryFunction {
+
+  BinaryFunction plus = new PlusFunction();
+  BinaryFunction times = new TimesFunction();
+
+  /**
+   * Apply the function to the arguments and return the result
+   *
+   * @param arg1 a double for the first argument
+   * @param arg2 a double for the second argument
+   * @return the result of applying the function
+   */
+  double apply(double arg1, double arg2);
+
+}

Propchange: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/BinaryFunction.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/CardinalityException.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/CardinalityException.java?rev=891983&view=auto
==============================================================================
--- lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/CardinalityException.java (added)
+++ lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/CardinalityException.java Thu Dec 17 23:22:16 2009
@@ -0,0 +1,23 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.mahout.math;
+
+/** Exception thrown when there is a cardinality mismatch in matrix operations */
+public class CardinalityException extends RuntimeException {
+
+}

Propchange: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/CardinalityException.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/DenseMatrix.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/DenseMatrix.java?rev=891983&view=auto
==============================================================================
--- lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/DenseMatrix.java (added)
+++ lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/DenseMatrix.java Thu Dec 17 23:22:16 2009
@@ -0,0 +1,191 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.mahout.math;
+
+import java.io.DataInput;
+import java.io.DataOutput;
+import java.io.IOException;
+
+/** Matrix of doubles implemented using a 2-d array */
+public class DenseMatrix extends AbstractMatrix {
+
+  private double[][] values;
+
+  public DenseMatrix() {
+    super();
+  }
+
+  private int columnSize() {
+    return values[0].length;
+  }
+
+  private int rowSize() {
+    return values.length;
+  }
+
+  /**
+   * Construct a matrix from the given values
+   *
+   * @param values a double[][]
+   */
+  public DenseMatrix(double[][] values) {
+    // clone the rows
+    this.values = new double[values.length][];
+    // be careful, need to clone the columns too
+    for (int i = 0; i < values.length; i++) {
+      this.values[i] = values[i].clone();
+    }
+  }
+
+  /** Construct an empty matrix of the given size */
+  public DenseMatrix(int rows, int columns) {
+    this.values = new double[rows][columns];
+  }
+
+  @Override
+  public int[] size() {
+    int[] result = new int[2];
+    result[ROW] = rowSize();
+    result[COL] = columnSize();
+    return result;
+  }
+
+  @Override
+  public Matrix clone() {
+    DenseMatrix clone = (DenseMatrix) super.clone();
+    clone.values = new double[values.length][];
+    for (int i = 0; i < values.length; i++) {
+      clone.values[i] = values[i].clone();
+    }
+    return clone;
+  }
+
+  @Override
+  public double getQuick(int row, int column) {
+    return values[row][column];
+  }
+
+  @Override
+  public boolean haveSharedCells(Matrix other) {
+    if (other instanceof DenseMatrix) {
+      return other == this;
+    } else {
+      return other.haveSharedCells(this);
+    }
+  }
+
+  @Override
+  public Matrix like() {
+    return like(rowSize(), columnSize());
+  }
+
+  @Override
+  public Matrix like(int rows, int columns) {
+    return new DenseMatrix(rows, columns);
+  }
+
+  @Override
+  public void setQuick(int row, int column, double value) {
+    values[row][column] = value;
+  }
+
+  @Override
+  public int[] getNumNondefaultElements() {
+    return size();
+  }
+
+  @Override
+  public Matrix viewPart(int[] offset, int[] size) {
+    if (size[ROW] > rowSize() || size[COL] > columnSize()) {
+      throw new CardinalityException();
+    }
+    if (offset[ROW] < 0 || offset[ROW] + size[ROW] > rowSize()
+        || offset[COL] < 0 || offset[COL] + size[COL] > columnSize()) {
+      throw new IndexException();
+    }
+    return new MatrixView(this, offset, size);
+  }
+
+  @Override
+  public Matrix assignColumn(int column, Vector other) {
+    if (other.size() != rowSize() || column >= columnSize()) {
+      throw new CardinalityException();
+    }
+    for (int row = 0; row < rowSize(); row++) {
+      values[row][column] = other.getQuick(row);
+    }
+    return this;
+  }
+
+  @Override
+  public Matrix assignRow(int row, Vector other) {
+    if (row >= rowSize() || other.size() != columnSize()) {
+      throw new CardinalityException();
+    }
+    for (int col = 0; col < columnSize(); col++) {
+      values[row][col] = other.getQuick(col);
+    }
+    return this;
+  }
+
+  @Override
+  public Vector getColumn(int column) {
+    if (column < 0 || column >= columnSize()) {
+      throw new IndexException();
+    }
+    double[] col = new double[rowSize()];
+    for (int row = 0; row < rowSize(); row++) {
+      col[row] = values[row][column];
+    }
+    return new DenseVector(col);
+  }
+
+  @Override
+  public Vector getRow(int row) {
+    if (row < 0 || row >= rowSize()) {
+      throw new IndexException();
+    }
+    return new DenseVector(values[row]);
+  }
+
+  @Override
+  public void readFields(DataInput in) throws IOException {
+    super.readFields(in);
+    int rows = in.readInt();
+    int columns = in.readInt();
+    this.values = new double[rows][columns];
+    for (int row = 0; row < rows; row++) {
+      for (int column = 0; column < columns; column++) {
+        this.values[row][column] = in.readDouble();
+      }
+    }
+  }
+
+  @Override
+  public void write(DataOutput out) throws IOException {
+    super.write(out);
+    out.writeInt(rowSize());
+    out.writeInt(columnSize());
+    for (double[] row : values) {
+      for (double value : row) {
+        out.writeDouble(value);
+      }
+    }
+  }
+
+}

Propchange: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/DenseMatrix.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/DenseVector.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/DenseVector.java?rev=891983&view=auto
==============================================================================
--- lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/DenseVector.java (added)
+++ lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/DenseVector.java Thu Dec 17 23:22:16 2009
@@ -0,0 +1,335 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.mahout.math;
+
+import java.io.DataInput;
+import java.io.DataOutput;
+import java.io.IOException;
+import java.util.Arrays;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
+/** Implements vector as an array of doubles */
+public class DenseVector extends AbstractVector {
+
+  private double[] values;
+  private double lengthSquared = -1.0;
+
+  /** For serialization purposes only */
+  public DenseVector() {
+  }
+
+  public DenseVector(String name) {
+    super(name);
+  }
+
+  /** Construct a new instance using provided values */
+  public DenseVector(double[] values) {
+    this.values = values.clone();
+  }
+
+  public DenseVector(String name, double[] values) {
+    super(name);
+    this.values = values.clone();
+  }
+
+  /** Construct a new instance of the given cardinality */
+  public DenseVector(int cardinality) {
+    this(null, cardinality);
+  }
+
+  public DenseVector(String name, int cardinality) {
+    super(name);
+    this.values = new double[cardinality];
+  }
+
+  @Override
+  protected Matrix matrixLike(int rows, int columns) {
+    return new DenseMatrix(rows, columns);
+  }
+
+  @Override
+  public int size() {
+    return values.length;
+  }
+
+  @Override
+  public DenseVector clone() {
+    DenseVector clone = (DenseVector) super.clone();
+    clone.values = values.clone();
+    return clone;
+  }
+
+  @Override
+  public double getQuick(int index) {
+    return values[index];
+  }
+
+  @Override
+  public DenseVector like() {
+    DenseVector denseVector = new DenseVector(size());
+    denseVector.setLabelBindings(getLabelBindings());
+    return denseVector;
+  }
+
+  @Override
+  public Vector like(int cardinality) {
+    DenseVector denseVector = new DenseVector(cardinality);
+    denseVector.setLabelBindings(getLabelBindings());
+    return denseVector;
+  }
+
+  @Override
+  public void setQuick(int index, double value) {
+    lengthSquared = -1.0;
+    values[index] = value;
+  }
+
+  @Override
+  public int getNumNondefaultElements() {
+    return values.length;
+  }
+
+  @Override
+  public Vector viewPart(int offset, int length) {
+    if (length > values.length) {
+      throw new CardinalityException();
+    }
+    if (offset < 0 || offset + length > values.length) {
+      throw new IndexException();
+    }
+    return new VectorView(this, offset, length);
+  }
+
+  @Override
+  public boolean haveSharedCells(Vector other) {
+    if (other instanceof DenseVector) {
+      return other == this;
+    } else {
+      return other.haveSharedCells(this);
+    }
+  }
+
+  /**
+   * Returns an iterator that traverses this Vector from 0 to cardinality-1, in that order.
+   *
+   * @see java.lang.Iterable#iterator
+   */
+  @Override
+  public Iterator<Vector.Element> iterateNonZero() {
+    return new NonZeroIterator();
+  }
+
+  @Override
+  public Iterator<Vector.Element> iterateNonZero(boolean sorted) {
+    return new NonZeroIterator();
+  }
+
+  @Override
+  public Iterator<Vector.Element> iterateAll() {
+    return new AllIterator();
+  }
+
+  private class NonZeroIterator implements Iterator<Vector.Element> {
+
+    private final Element element = new Element(0);
+    private int offset;
+
+    private NonZeroIterator() {
+      goToNext();
+    }
+
+    private void goToNext() {
+      while (offset < values.length && values[offset] == 0) {
+        offset++;
+      }
+    }
+
+    @Override
+    public boolean hasNext() {
+      return offset < values.length;
+    }
+
+    @Override
+    public Vector.Element next() {
+      if (offset >= values.length) {
+        throw new NoSuchElementException();
+      }
+      element.ind = offset;
+      offset++;
+      goToNext();
+      return element;
+    }
+
+    @Override
+    public void remove() {
+      throw new UnsupportedOperationException();
+    }
+  }
+
+  private class AllIterator implements Iterator<Vector.Element> {
+
+    private final Element element = new Element(-1);
+
+    @Override
+    public boolean hasNext() {
+      return element.ind + 1 < values.length;
+    }
+
+    @Override
+    public Vector.Element next() {
+      if (!hasNext()) {
+        throw new NoSuchElementException();
+      }
+      element.ind++;
+      return element;
+    }
+
+    @Override
+    public void remove() {
+      throw new UnsupportedOperationException();
+    }
+  }
+
+  public class Element implements Vector.Element {
+
+    private int ind;
+
+    public Element(int ind) {
+      this.ind = ind;
+    }
+
+    @Override
+    public double get() {
+      return values[ind];
+    }
+
+    @Override
+    public int index() {
+      return ind;
+    }
+
+    @Override
+    public void set(double value) {
+      lengthSquared = -1.0;
+      values[ind] = value;
+    }
+  }
+
+  @Override
+  public Vector.Element getElement(int index) {
+    return new Element(index);
+  }
+
+  @Override
+  public void write(DataOutput dataOutput) throws IOException {
+    dataOutput.writeUTF(this.getName() == null ? "" : this.getName());
+    dataOutput.writeInt(size());
+    Iterator<Vector.Element> iter = iterateAll();
+    while (iter.hasNext()) {
+      Vector.Element element = iter.next();
+      dataOutput.writeDouble(element.get());
+    }
+  }
+
+  @Override
+  public void readFields(DataInput dataInput) throws IOException {
+    this.setName(dataInput.readUTF());
+    double[] values = new double[dataInput.readInt()];
+    for (int i = 0; i < values.length; i++) {
+      values[i] = dataInput.readDouble();
+    }
+    this.values = values;
+    lengthSquared = -1.0;
+  }
+
+  /**
+   * Indicate whether the two objects are the same or not. Two {@link org.apache.mahout.math.Vector}s can be equal
+   * even if the underlying implementation is not equal.
+   *
+   * @param o The object to compare
+   * @return true if the objects have the same cell values and same name, false otherwise.
+   * @see AbstractVector#strictEquivalence(Vector, Vector)
+   * @see AbstractVector#equivalent(Vector, Vector)
+   */
+  @Override
+  public boolean equals(Object o) {
+    if (this == o) {
+      return true;
+    }
+    if (!(o instanceof Vector)) {
+      return false;
+    }
+
+    Vector that = (Vector) o;
+    String thisName = getName();
+    String thatName = that.getName();
+    if (this.size() != that.size()) {
+      return false;
+    }
+    if (thisName != null && thatName != null && !thisName.equals(thatName)) {
+      return false;
+    } else if ((thisName != null && thatName == null)
+        || (thatName != null && thisName == null)) {
+      return false;
+    }
+
+    if (that instanceof DenseVector) {
+      if (!Arrays.equals(values, ((DenseVector) that).values)) {
+        return false;
+      }
+    } else {
+      return equivalent(this, that);
+    }
+
+    return true;
+  }
+
+
+  @Override
+  public double getLengthSquared() {
+    if (lengthSquared >= 0.0) {
+      return lengthSquared;
+    }
+
+    double result = 0.0;
+    for (double value : values) {
+      result += value * value;
+
+    }
+    lengthSquared = result;
+    return result;
+  }
+
+  @Override
+  public double getDistanceSquared(Vector v) {
+    double result = 0.0;
+    for (int i = 0; i < values.length; i++) {
+      double delta = values[i] - v.getQuick(i);
+      result += delta * delta;
+    }
+    return result;
+  }
+
+  @Override
+  public void addTo(Vector v) {
+    for (int i = 0; i < size(); i++) {
+      v.setQuick(i, get(i) + v.get(i));
+    }
+  }
+}

Propchange: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/DenseVector.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/GenericPermuting.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/GenericPermuting.java?rev=891983&view=auto
==============================================================================
--- lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/GenericPermuting.java (added)
+++ lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/GenericPermuting.java Thu Dec 17 23:22:16 2009
@@ -0,0 +1,312 @@
+/*
+Copyright ï¿½ 1999 CERN - European Organization for Nuclear Research.
+Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose 
+is hereby granted without fee, provided that the above copyright notice appear in all copies and 
+that both that copyright notice and this permission notice appear in supporting documentation. 
+CERN makes no representations about the suitability of this software for any purpose. 
+It is provided "as is" without expressed or implied warranty.
+*/
+package org.apache.mahout.math;
+
+import org.apache.mahout.math.jet.random.Uniform;
+import org.apache.mahout.math.jet.random.engine.MersenneTwister;
+
+/**
+ Generically reorders (permutes) arbitrary shaped data (for example, an array, three arrays, a 2-d matrix, two linked lists) using an <i>in-place</i> swapping algorithm.
+ Imagine having a couple of apples. For some reason you decide to reorder them. The green one before the red one. The pale one after the shiny one, etc. This class helps to do the job.
+ <p>
+ This class swaps elements around, in a way that avoids stumbling over its own feet:
+ Let <tt>before</tt> be the generic data before calling the reordering method.
+ Let <tt>after</tt> be the generic data after calling the reordering method.
+ Then there holds <tt>after[i] == before[indexes[i]]</tt>.
+ <p>
+ Similar to {@link GenericSorting}, this class has no idea what kind of data it is reordering.
+ It can decide to swap the data at index <tt>a</tt> with the data at index <tt>b</tt>.
+ It calls a user provided {@link org.apache.mahout.math.Swapper} object that knows how to swap the data of these indexes.
+ <p>
+ For convenience, some non-generic variants are also provided.
+ Further a method to generate the p-th lexicographical permutation indexes.
+ <p>
+ <b>Example:</b>
+ <table>
+ <td class="PRE">
+ <pre>
+ Reordering
+ [A,B,C,D,E] with indexes [0,4,2,3,1] yields
+ [A,E,C,D,B]
+ In other words, in the reordered list, we first have the element at old index 0, then the one at old index 4, then the ones at old indexes 2,3,1.
+ g[0]<--g[0], g[1]<--g[4], g[2]<--g[2], g[3]<--g[3], g[4]<--g[1].
+
+ Reordering
+ [A,B,C,D,E] with indexes [0,4,1,2,3] yields
+ [A,E,B,C,D]
+ In other words g[0]<--g[0], g[1]<--g[4], g[2]<--g[1], g[3]<--g[2], g[4]<--g[3].
+ </pre>
+ </td>
+ </table>
+ <p>
+ Here are some example swappers:
+ <table>
+ <td class="PRE">
+ <pre>
+ // a swapper knows how to swap two indexes (a,b)
+
+ // reordering an array
+ Swapper swapper = new Swapper() {
+ &nbsp;&nbsp;&nbsp;public void swap(int a, int b) {
+ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;String tmp; // reordering String[]
+ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;// int tmp; // reordering int[]
+ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;tmp = array[a]; array[a] = array[b]; array[b] = tmp;
+ &nbsp;&nbsp;&nbsp;}
+ };
+
+ // reordering a list
+ Swapper swapper = new Swapper() {
+ &nbsp;&nbsp;&nbsp;public void swap(int a, int b) {
+ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Object tmp;
+ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;tmp = list.get(a);
+ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;list.set(a, list.get(b));
+ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;list.set(b, tmp);
+ &nbsp;&nbsp;&nbsp;}
+ };
+
+ // reordering the rows of a 2-d matrix (see {@link org.apache.mahout.math.matrix})
+ Swapper swapper = new Swapper() {
+ &nbsp;&nbsp;&nbsp;public void swap(int a, int b) {
+ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;matrix.viewRow(a).swap(matrix.viewRow(b));
+ &nbsp;&nbsp;&nbsp;}
+ };
+
+ // reordering the columns of a 2-d matrix
+ Swapper swapper = new Swapper() {
+ &nbsp;&nbsp;&nbsp;public void swap(int a, int b) {
+ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;matrix.viewColumn(a).swap(matrix.viewColumn(b));
+ &nbsp;&nbsp;&nbsp;}
+ };
+ </pre>
+ </td>
+ </table>
+
+ @see org.apache.mahout.math.Swapper
+ @see org.apache.mahout.math.GenericSorting
+
+ @author wolfgang.hoschek@cern.ch
+ @version 1.0, 10-Oct-99
+ */
+
+/** @deprecated until unit tests are in place.  Until this time, this class/interface is unsupported. */
+@Deprecated
+public class GenericPermuting {
+
+  /** Makes this class non instantiable, but still let's others inherit from it. */
+  private GenericPermuting() {
+  }
+
+  /**
+   * Returns the <tt>p</tt>-th permutation of the sequence <tt>[0,1,...,N-1]</tt>. A small but smart and efficient
+   * routine, ported from <A HREF="http://www.hep.net/wwwmirrors/cernlib/CNASDOC/shortwrups_html3/node255.html">
+   * Cernlib</A>. The <A HREF="ftp://asisftp.cern.ch/cernlib/share/pro/src/mathlib/gen/v/permu.F"> Fortran source</A>. A
+   * sequence of <tt>N</tt> distinct elements has <tt>N!</tt> permutations, which are enumerated in lexicographical
+   * order <tt>1 .. N!</tt>. <p> This is, for example, useful for Monte-Carlo-tests where one might want to compute
+   * <tt>k</tt> distinct and random permutations of a sequence, obtaining <tt>p</tt> from {@link
+   * org.apache.mahout.math.jet.random.sampling} without replacement or a random engine like {@link
+   * org.apache.mahout.math.jet.random.engine.MersenneTwister}. <br> Note: When <tt>N!</tt> exceeds the 64-bit range (i.e.
+   * for <tt>N > 20</tt>), this method has <i>different</i> behaviour: it makes a sequence <tt>[0,1,...,N-1]</tt> and
+   * randomizes it, seeded with parameter <tt>p</tt>. <p> <b>Examples:</b>
+   * <pre>
+   * http://www.hep.net/wwwmirrors/cernlib/CNASDOC/shortwrups_html3/node255.html
+   * // exactly lexicographically enumerated (ascending)
+   * permutation(1,3) --> [ 0,1,2 ]
+   * permutation(2,3) --> [ 0,2,1 ]
+   * permutation(3,3) --> [ 1,0,2 ]
+   * permutation(4,3) --> [ 1,2,0 ]
+   * permutation(5,3) --> [ 2,0,1 ]
+   * permutation(6,3) --> [ 2,1,0 ]
+   * permutation(1      ,20) --> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
+   * permutation(2      ,20) --> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 18]
+   * permutation(1000000,20) --> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 17, 18, 13, 19, 11, 15, 14, 16, 10]
+   * permutation(20! -2 ,20) --> [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 1, 2, 0]
+   * permutation(20! -1 ,20) --> [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 0, 1]
+   * permutation(20!    ,20) --> [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
+   * <br>
+   * // not exactly enumerated, rather randomly shuffled
+   * permutation(1,21) --> [18, 20, 11, 0, 15, 1, 19, 13, 3, 6, 16, 17, 9, 5, 12, 4, 7, 14, 8, 10, 2]
+   * permutation(2,21) --> [1, 9, 4, 16, 14, 13, 11, 20, 10, 8, 18, 0, 15, 3, 17, 5, 12, 2, 6, 7, 19]
+   * permutation(3,21) --> [12, 0, 19, 1, 20, 5, 8, 16, 6, 14, 2, 4, 3, 17, 11, 13, 9, 10, 15, 18, 7]
+   * </pre>
+   *
+   * @param p the lexicographical ordinal number of the permutation to be computed.
+   * @param N the length of the sequence to be generated.
+   * @return the <tt>p</tt>-th permutation.
+   * @throws IllegalArgumentException if <tt>p < 1 || N < 0 || p > N!</tt>.
+   */
+  public static int[] permutation(long p, int N) {
+    if (p < 1) {
+      throw new IllegalArgumentException("Permutations are enumerated 1 .. N!");
+    }
+    if (N < 0) {
+      throw new IllegalArgumentException("Must satisfy N >= 0");
+    }
+
+    int[] permutation = new int[N];
+
+    if (N > 20) { // factorial(21) would overflow 64-bit long)
+      // Simply make a list (0,1,..N-1) and randomize it, seeded with "p".
+      // Note that this is perhaps not what you want...
+      for (int i = N; --i >= 0;) {
+        permutation[i] = i;
+      }
+      Uniform gen = new Uniform(new MersenneTwister((int) p));
+      for (int i = 0; i < N - 1; i++) {
+        int random = gen.nextIntFromTo(i, N - 1);
+
+        //swap(i, random)
+        int tmp = permutation[random];
+        permutation[random] = permutation[i];
+        permutation[i] = tmp;
+      }
+
+      return permutation;
+    }
+
+    // the normal case - exact enumeration
+    if (p > org.apache.mahout.math.jet.math.Arithmetic.longFactorial(N)) {
+      throw new IllegalArgumentException("N too large (a sequence of N elements only has N! permutations).");
+    }
+
+    int[] tmp = new int[N];
+    for (int i = 1; i <= N; i++) {
+      tmp[i - 1] = i;
+    }
+
+    long io = p - 1;
+    for (int M = N - 1; M >= 1; M--) {
+      long fac = org.apache.mahout.math.jet.math.Arithmetic.longFactorial(M);
+      int in = ((int) (io / fac)) + 1;
+      io %= fac;
+      permutation[N - M - 1] = tmp[in - 1];
+
+      for (int j = in; j <= M; j++) {
+        tmp[j - 1] = tmp[j];
+      }
+    }
+    if (N > 0) {
+      permutation[N - 1] = tmp[0];
+    }
+
+    for (int i = N; --i >= 0;) {
+      permutation[i] -= 1;
+    }
+    return permutation;
+  }
+
+  /**
+   * A non-generic variant of reordering, specialized for <tt>int[]</tt>, same semantics. Quicker than generic
+   * reordering. Also for convenience (forget about the Swapper object).
+   */
+  public static void permute(int[] list, int[] indexes) {
+    int[] copy = list.clone();
+    for (int i = list.length; --i >= 0;) {
+      list[i] = copy[indexes[i]];
+    }
+  }
+
+  /**
+   * Deprecated. Generically reorders arbitrary shaped generic data <tt>g</tt> such that <tt>g[i] == g[indexes[i]]</tt>.
+   * (The generic data may be one array, a 2-d matrix, two linked lists or whatever). This class swaps elements around,
+   * in a way that avoids stumbling over its own feet. <p> <b>Example:</b>
+   * <pre>
+   * Reordering
+   * [A,B,C,D,E] with indexes [0,4,2,3,1] yields
+   * [A,E,C,D,B]
+   * In other words g[0]<--g[0], g[1]<--g[4], g[2]<--g[2], g[3]<--g[3], g[4]<--g[1].
+   *
+   * Reordering
+   * [A,B,C,D,E] with indexes [0,4,1,2,3] yields
+   * [A,E,B,C,D]
+   * In other words g[0]<--g[0], g[1]<--g[4], g[2]<--g[1], g[3]<--g[2], g[4]<--g[3].
+   * </pre>
+   * <p>
+   *
+   * @param indexes the permutation indexes.
+   * @param swapper an object that knows how to swap two indexes a,b.
+   * @param work    the working storage, must satisfy <tt>work.length >= indexes.length</tt>; set <tt>work==null</tt> if
+   *                you don't care about performance.
+   * @deprecated
+   */
+  @Deprecated
+  public static void permute(int[] indexes, org.apache.mahout.math.Swapper swapper, int[] work) {
+    permute(indexes, swapper, work, null);
+  }
+
+  /**
+   * Generically reorders arbitrary shaped generic data <tt>g</tt> such that <tt>g[i] == g[indexes[i]]</tt>. (The
+   * generic data may be one array, a 2-d matrix, two linked lists or whatever). This class swaps elements around, in a
+   * way that avoids stumbling over its own feet. <p> <b>Example:</b>
+   * <pre>
+   * Reordering
+   * [A,B,C,D,E] with indexes [0,4,2,3,1] yields
+   * [A,E,C,D,B]
+   * In other words g[0]<--g[0], g[1]<--g[4], g[2]<--g[2], g[3]<--g[3], g[4]<--g[1].
+   *
+   * Reordering
+   * [A,B,C,D,E] with indexes [0,4,1,2,3] yields
+   * [A,E,B,C,D]
+   * In other words g[0]<--g[0], g[1]<--g[4], g[2]<--g[1], g[3]<--g[2], g[4]<--g[3].
+   * </pre>
+   * <p>
+   *
+   * @param indexes the permutation indexes.
+   * @param swapper an object that knows how to swap two indexes a,b.
+   * @param work1   some working storage, must satisfy <tt>work1.length >= indexes.length</tt>; set <tt>work1==null</tt>
+   *                if you don't care about performance.
+   * @param work2   some working storage, must satisfy <tt>work2.length >= indexes.length</tt>; set <tt>work2==null</tt>
+   *                if you don't care about performance.
+   */
+  public static void permute(int[] indexes, org.apache.mahout.math.Swapper swapper, int[] work1, int[] work2) {
+    // "tracks" and "pos" keeps track of the current indexes of the elements
+    // Example: We have a list==[A,B,C,D,E], indexes==[0,4,1,2,3] and swap B and E we need to know that the element formlerly at index 1 is now at index 4, and the one formerly at index 4 is now at index 1.
+    // Otherwise we stumble over our own feet and produce nonsense.
+    // Initially index i really is at index i, but this will change due to swapping.
+
+    // work1, work2 to avoid high frequency memalloc's
+    int s = indexes.length;
+    int[] tracks = work1;
+    int[] pos = work2;
+    if (tracks == null || tracks.length < s) {
+      tracks = new int[s];
+    }
+    if (pos == null || pos.length < s) {
+      pos = new int[s];
+    }
+    for (int i = s; --i >= 0;) {
+      tracks[i] = i;
+      pos[i] = i;
+    }
+
+    for (int i = 0; i < s; i++) {
+      int index = indexes[i];
+      int track = tracks[index];
+
+      if (i != track) {
+        swapper.swap(i, track);
+        tracks[index] = i;
+        tracks[pos[i]] = track;
+        int tmp = pos[i];
+        pos[i] = pos[track];
+        pos[track] = tmp;
+      }
+    }
+  }
+
+  /**
+   * A non-generic variant of reordering, specialized for <tt>Object[]</tt>, same semantics. Quicker than generic
+   * reordering. Also for convenience (forget about the Swapper object).
+   */
+  public static void permute(Object[] list, int[] indexes) {
+    Object[] copy = list.clone();
+    for (int i = list.length; --i >= 0;) {
+      list[i] = copy[indexes[i]];
+    }
+  }
+}

Propchange: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/GenericPermuting.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/GenericSorting.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/GenericSorting.java?rev=891983&view=auto
==============================================================================
--- lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/GenericSorting.java (added)
+++ lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/GenericSorting.java Thu Dec 17 23:22:16 2009
@@ -0,0 +1,336 @@
+/*
+Copyright ï¿½ 1999 CERN - European Organization for Nuclear Research.
+Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose 
+is hereby granted without fee, provided that the above copyright notice appear in all copies and 
+that both that copyright notice and this permission notice appear in supporting documentation. 
+CERN makes no representations about the suitability of this software for any purpose. 
+It is provided "as is" without expressed or implied warranty.
+*/
+package org.apache.mahout.math;
+
+import org.apache.mahout.math.function.IntComparator;
+
+/** @deprecated until unit tests are in place.  Until this time, this class/interface is unsupported. */
+@Deprecated
+public class GenericSorting {
+
+  private static final int SMALL = 7;
+  private static final int MEDIUM = 40;
+
+  /** Makes this class non instantiable, but still let's others inherit from it. */
+  private GenericSorting() {
+  }
+
+  /**
+   * Transforms two consecutive sorted ranges into a single sorted range.  The initial ranges are <code>[first,
+   * middle)</code> and <code>[middle, last)</code>, and the resulting range is <code>[first, last)</code>. Elements in
+   * the first input range will precede equal elements in the second.
+   */
+  private static void inplace_merge(int first, int middle, int last, IntComparator comp, Swapper swapper) {
+    if (first >= middle || middle >= last) {
+      return;
+    }
+    if (last - first == 2) {
+      if (comp.compare(middle, first) < 0) {
+        swapper.swap(first, middle);
+      }
+      return;
+    }
+    int firstCut;
+    int secondCut;
+    if (middle - first > last - middle) {
+      firstCut = first + (middle - first) / 2;
+      secondCut = lower_bound(middle, last, firstCut, comp);
+    } else {
+      secondCut = middle + (last - middle) / 2;
+      firstCut = upper_bound(first, middle, secondCut, comp);
+    }
+
+    // rotate(firstCut, middle, secondCut, swapper);
+    // is manually inlined for speed (jitter inlining seems to work only for small call depths, even if methods are "static private")
+    // speedup = 1.7
+    // begin inline
+    int first2 = firstCut;
+    int middle2 = middle;
+    int last2 = secondCut;
+    if (middle2 != first2 && middle2 != last2) {
+      int first1 = first2;
+      int last1 = middle2;
+      while (first1 < --last1) {
+        swapper.swap(first1++, last1);
+      }
+      first1 = middle2;
+      last1 = last2;
+      while (first1 < --last1) {
+        swapper.swap(first1++, last1);
+      }
+      first1 = first2;
+      last1 = last2;
+      while (first1 < --last1) {
+        swapper.swap(first1++, last1);
+      }
+    }
+    // end inline
+
+    middle = firstCut + (secondCut - middle);
+    inplace_merge(first, firstCut, middle, comp, swapper);
+    inplace_merge(middle, secondCut, last, comp, swapper);
+  }
+
+  /**
+   * Performs a binary search on an already-sorted range: finds the first position where an element can be inserted
+   * without violating the ordering. Sorting is by a user-supplied comparison function.
+   *
+   * @param first Beginning of the range.
+   * @param last  One past the end of the range.
+   * @param x     Element to be searched for.
+   * @param comp  Comparison function.
+   * @return The largest index i such that, for every j in the range <code>[first, i)</code>, <code>comp.apply(array[j],
+   *         x)</code> is <code>true</code>.
+   * @see Sorting#upper_bound
+   */
+  private static int lower_bound(int first, int last, int x, IntComparator comp) {
+    //if (comp==null) throw new NullPointerException();
+    int len = last - first;
+    while (len > 0) {
+      int half = len / 2;
+      int middle = first + half;
+      if (comp.compare(middle, x) < 0) {
+        first = middle + 1;
+        len -= half + 1;
+      } else {
+        len = half;
+      }
+    }
+    return first;
+  }
+
+  /** Returns the index of the median of the three indexed chars. */
+  private static int med3(int a, int b, int c, IntComparator comp) {
+    int ab = comp.compare(a, b);
+    int ac = comp.compare(a, c);
+    int bc = comp.compare(b, c);
+    return (ab < 0 ?
+        (bc < 0 ? b : ac < 0 ? c : a) :
+        (bc > 0 ? b : ac > 0 ? c : a));
+  }
+
+  /**
+   * Sorts the specified range of elements according to the order induced by the specified comparator.  All elements in
+   * the range must be <i>mutually comparable</i> by the specified comparator (that is, <tt>c.compare(a, b)</tt> must
+   * not throw an exception for any indexes <tt>a</tt> and <tt>b</tt> in the range).<p>
+   *
+   * This sort is guaranteed to be <i>stable</i>:  equal elements will not be reordered as a result of the sort.<p>
+   *
+   * The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low
+   * sublist is less than the lowest element in the high sublist).  This algorithm offers guaranteed n*log(n)
+   * performance, and can approach linear performance on nearly sorted lists.
+   *
+   * @param fromIndex the index of the first element (inclusive) to be sorted.
+   * @param toIndex   the index of the last element (exclusive) to be sorted.
+   * @param c         the comparator to determine the order of the generic data.
+   * @param swapper   an object that knows how to swap the elements at any two indexes (a,b).
+   * @see IntComparator
+   * @see Swapper
+   */
+  public static void mergeSort(int fromIndex, int toIndex, IntComparator c, Swapper swapper) {
+    /*
+      We retain the same method signature as quickSort.
+      Given only a comparator and swapper we do not know how to copy and move elements from/to temporary arrays.
+      Hence, in contrast to the JDK mergesorts this is an "in-place" mergesort, i.e. does not allocate any temporary arrays.
+      A non-inplace mergesort would perhaps be faster in most cases, but would require non-intuitive delegate objects...
+    */
+    int length = toIndex - fromIndex;
+
+    // Insertion sort on smallest arrays
+    if (length < SMALL) {
+      for (int i = fromIndex; i < toIndex; i++) {
+        for (int j = i; j > fromIndex && (c.compare(j - 1, j) > 0); j--) {
+          swapper.swap(j, j - 1);
+        }
+      }
+      return;
+    }
+
+    // Recursively sort halves
+    int mid = (fromIndex + toIndex) / 2;
+    mergeSort(fromIndex, mid, c, swapper);
+    mergeSort(mid, toIndex, c, swapper);
+
+    // If list is already sorted, nothing left to do.  This is an
+    // optimization that results in faster sorts for nearly ordered lists.
+    if (c.compare(mid - 1, mid) <= 0) {
+      return;
+    }
+
+    // Merge sorted halves
+    inplace_merge(fromIndex, mid, toIndex, c, swapper);
+  }
+
+  /**
+   * Sorts the specified range of elements according to the order induced by the specified comparator.  All elements in
+   * the range must be <i>mutually comparable</i> by the specified comparator (that is, <tt>c.compare(a, b)</tt> must
+   * not throw an exception for any indexes <tt>a</tt> and <tt>b</tt> in the range).<p>
+   *
+   * The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a
+   * Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993).  This algorithm offers
+   * n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.
+   *
+   * @param fromIndex the index of the first element (inclusive) to be sorted.
+   * @param toIndex   the index of the last element (exclusive) to be sorted.
+   * @param c         the comparator to determine the order of the generic data.
+   * @param swapper   an object that knows how to swap the elements at any two indexes (a,b).
+   * @see IntComparator
+   * @see Swapper
+   */
+  public static void quickSort(int fromIndex, int toIndex, IntComparator c, Swapper swapper) {
+    quickSort1(fromIndex, toIndex - fromIndex, c, swapper);
+  }
+
+  /** Sorts the specified sub-array into ascending order. */
+  private static void quickSort1(int off, int len, IntComparator comp, Swapper swapper) {
+    // Insertion sort on smallest arrays
+    if (len < SMALL) {
+      for (int i = off; i < len + off; i++) {
+        for (int j = i; j > off && (comp.compare(j - 1, j) > 0); j--) {
+          swapper.swap(j, j - 1);
+        }
+      }
+      return;
+    }
+
+    // Choose a partition element, v
+    int m = off + len / 2;       // Small arrays, middle element
+    if (len > SMALL) {
+      int l = off;
+      int n = off + len - 1;
+      if (len > MEDIUM) {        // Big arrays, pseudomedian of 9
+        int s = len / 8;
+        l = med3(l, l + s, l + 2 * s, comp);
+        m = med3(m - s, m, m + s, comp);
+        n = med3(n - 2 * s, n - s, n, comp);
+      }
+      m = med3(l, m, n, comp); // Mid-size, med of 3
+    }
+    //long v = x[m];
+
+    // Establish Invariant: v* (<v)* (>v)* v*
+    int a = off, b = a, c = off + len - 1, d = c;
+    while (true) {
+      int comparison;
+      while (b <= c && ((comparison = comp.compare(b, m)) <= 0)) {
+        if (comparison == 0) {
+          if (a == m) {
+            m = b; // moving target; DELTA to JDK !!!
+          } else if (b == m) {
+            m = a;
+          } // moving target; DELTA to JDK !!!
+          swapper.swap(a++, b);
+        }
+        b++;
+      }
+      while (c >= b && ((comparison = comp.compare(c, m)) >= 0)) {
+        if (comparison == 0) {
+          if (c == m) {
+            m = d; // moving target; DELTA to JDK !!!
+          } else if (d == m) {
+            m = c;
+          } // moving target; DELTA to JDK !!!
+          swapper.swap(c, d--);
+        }
+        c--;
+      }
+      if (b > c) {
+        break;
+      }
+      if (b == m) {
+        m = d; // moving target; DELTA to JDK !!!
+      } else if (c == m) {
+        m = c;
+      } // moving target; DELTA to JDK !!!
+      swapper.swap(b++, c--);
+    }
+
+    // Swap partition elements back to middle
+    int n = off + len;
+    int s = Math.min(a - off, b - a);
+    vecswap(swapper, off, b - s, s);
+    s = Math.min(d - c, n - d - 1);
+    vecswap(swapper, b, n - s, s);
+
+    // Recursively sort non-partition-elements
+    if ((s = b - a) > 1) {
+      quickSort1(off, s, comp, swapper);
+    }
+    if ((s = d - c) > 1) {
+      quickSort1(n - s, s, comp, swapper);
+    }
+  }
+
+  /**
+   * Reverses a sequence of elements.
+   *
+   * @param first Beginning of the range
+   * @param last  One past the end of the range
+   * @throws ArrayIndexOutOfBoundsException If the range is invalid.
+   */
+  private static void reverse(int first, int last, Swapper swapper) {
+    // no more needed since manually inlined
+    while (first < --last) {
+      swapper.swap(first++, last);
+    }
+  }
+
+  /**
+   * Rotate a range in place: <code>array[middle]</code> is put in <code>array[first]</code>,
+   * <code>array[middle+1]</code> is put in <code>array[first+1]</code>, etc.  Generally, the element in position
+   * <code>i</code> is put into position <code>(i + (last-middle)) % (last-first)</code>.
+   *
+   * @param first  Beginning of the range
+   * @param middle Index of the element that will be put in <code>array[first]</code>
+   * @param last   One past the end of the range
+   */
+  private static void rotate(int first, int middle, int last, Swapper swapper) {
+    // no more needed since manually inlined
+    if (middle != first && middle != last) {
+      reverse(first, middle, swapper);
+      reverse(middle, last, swapper);
+      reverse(first, last, swapper);
+    }
+  }
+
+  /**
+   * Performs a binary search on an already-sorted range: finds the last position where an element can be inserted
+   * without violating the ordering. Sorting is by a user-supplied comparison function.
+   *
+   * @param first Beginning of the range.
+   * @param last  One past the end of the range.
+   * @param x     Element to be searched for.
+   * @param comp  Comparison function.
+   * @return The largest index i such that, for every j in the range <code>[first, i)</code>, <code>comp.apply(x,
+   *         array[j])</code> is <code>false</code>.
+   * @see Sorting#lower_bound
+   */
+  private static int upper_bound(int first, int last, int x, IntComparator comp) {
+    //if (comp==null) throw new NullPointerException();
+    int len = last - first;
+    while (len > 0) {
+      int half = len / 2;
+      int middle = first + half;
+      if (comp.compare(x, middle) < 0) {
+        len = half;
+      } else {
+        first = middle + 1;
+        len -= half + 1;
+      }
+    }
+    return first;
+  }
+
+  /** Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)]. */
+  private static void vecswap(Swapper swapper, int a, int b, int n) {
+    for (int i = 0; i < n; i++, a++, b++) {
+      swapper.swap(a, b);
+    }
+  }
+}

Propchange: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/GenericSorting.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/IndexException.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/IndexException.java?rev=891983&view=auto
==============================================================================
--- lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/IndexException.java (added)
+++ lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/IndexException.java Thu Dec 17 23:22:16 2009
@@ -0,0 +1,23 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.mahout.math;
+
+/** Exception thrown when there is an index outside of [0, cardinality) */
+public class IndexException extends RuntimeException {
+
+}

Propchange: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/IndexException.java
------------------------------------------------------------------------------
    svn:eol-style = native