You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@mahout.apache.org by sr...@apache.org on 2010/01/05 20:46:27 UTC
svn commit: r896192 - in /lucene/mahout/trunk/math/src:
main/java-templates/org/apache/mahout/math/map/
main/java/org/apache/mahout/math/ main/java/org/apache/mahout/math/function/
main/java/org/apache/mahout/math/map/ main/java/org/apache/mahout/math/...
Author: srowen
Date: Tue Jan 5 19:46:26 2010
New Revision: 896192
URL: http://svn.apache.org/viewvc?rev=896192&view=rev
Log:
MAHOUT-235 on Benson's behalf
Added:
lucene/mahout/trunk/math/src/main/java-templates/org/apache/mahout/math/map/
lucene/mahout/trunk/math/src/main/java-templates/org/apache/mahout/math/map/AbstractKeyTypeValueTypeMap.java.t
lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/function/FloatFunction.java
Removed:
lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/map/AbstractDoubleIntMap.java
lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/map/AbstractIntDoubleMap.java
lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/map/AbstractIntIntMap.java
Modified:
lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/GenericSorting.java
lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/Sorting.java
lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/Swapper.java
lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/map/AbstractIntObjectMap.java
lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/map/AbstractLongObjectMap.java
lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/doublealgo/Sorting.java
lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/linalg/Algebra.java
lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/linalg/Property.java
lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/objectalgo/Sorting.java
lucene/mahout/trunk/math/src/test/java/org/apache/mahout/math/GenericSortingTest.java
lucene/mahout/trunk/math/src/test/java/org/apache/mahout/math/SortingTest.java
Added: lucene/mahout/trunk/math/src/main/java-templates/org/apache/mahout/math/map/AbstractKeyTypeValueTypeMap.java.t
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/main/java-templates/org/apache/mahout/math/map/AbstractKeyTypeValueTypeMap.java.t?rev=896192&view=auto
==============================================================================
--- lucene/mahout/trunk/math/src/main/java-templates/org/apache/mahout/math/map/AbstractKeyTypeValueTypeMap.java.t (added)
+++ lucene/mahout/trunk/math/src/main/java-templates/org/apache/mahout/math/map/AbstractKeyTypeValueTypeMap.java.t Tue Jan 5 19:46:26 2010
@@ -0,0 +1,499 @@
+/**
+ * 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.
+ */
+
+/*
+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.map;
+
+import org.apache.mahout.math.Sorting;
+import org.apache.mahout.math.Swapper;
+import org.apache.mahout.math.function.${keyTypeCap}Comparator;
+import org.apache.mahout.math.function.${keyTypeCap}${valueTypeCap}Procedure;
+import org.apache.mahout.math.function.${keyTypeCap}Procedure;
+import org.apache.mahout.math.list.${keyTypeCap}ArrayList;
+#if (${keyType} != ${valueType})
+import org.apache.mahout.math.function.${valueTypeCap}Procedure;
+import org.apache.mahout.math.list.${valueTypeCap}ArrayList;
+#end
+#if (${keyType} != 'int')
+import org.apache.mahout.math.function.IntComparator;
+#end
+#if (${valueTypeFloating} == 'true')
+import org.apache.mahout.math.function.${valueTypeCap}Function;
+#end
+
+public abstract class Abstract${keyTypeCap}${valueTypeCap}Map extends AbstractMap {
+
+ /**
+ * Returns <tt>true</tt> if the receiver contains the specified key.
+ *
+ * @return <tt>true</tt> if the receiver contains the specified key.
+ */
+ public boolean containsKey(final ${keyType} key) {
+ return !forEachKey(
+ new ${keyTypeCap}Procedure() {
+ @Override
+ public boolean apply(${keyType} iterKey) {
+ return (key != iterKey);
+ }
+ }
+ );
+ }
+
+ /**
+ * Returns <tt>true</tt> if the receiver contains the specified value.
+ *
+ * @return <tt>true</tt> if the receiver contains the specified value.
+ */
+ public boolean containsValue(final ${valueType} value) {
+ return !forEachPair(
+ new ${keyTypeCap}${valueTypeCap}Procedure() {
+ @Override
+ public boolean apply(${keyType} iterKey, ${valueType} iterValue) {
+ return (value != iterValue);
+ }
+ }
+ );
+ }
+
+ /**
+ * Returns a deep copy of the receiver; uses <code>clone()</code> and casts the result.
+ *
+ * @return a deep copy of the receiver.
+ */
+ public Abstract${keyTypeCap}${valueTypeCap}Map copy() {
+ return (Abstract${keyTypeCap}${valueTypeCap}Map) clone();
+ }
+
+ /**
+ * Compares the specified object with this map for equality. Returns <tt>true</tt> if the given object is also a map
+ * and the two maps represent the same mappings. More formally, two maps <tt>m1</tt> and <tt>m2</tt> represent the
+ * same mappings iff
+ * <pre>
+ * m1.forEachPair(
+ * new ${keyTypeCap}${valueTypeCap}Procedure() {
+ * public boolean apply(${keyType} key, ${valueType} value) {
+ * return m2.containsKey(key) && m2.get(key) == value;
+ * }
+ * }
+ * )
+ * &&
+ * m2.forEachPair(
+ * new ${keyTypeCap}${valueTypeCap}Procedure() {
+ * public boolean apply(${keyType} key, ${valueType} value) {
+ * return m1.containsKey(key) && m1.get(key) == value;
+ * }
+ * }
+ * );
+ * </pre>
+ *
+ * This implementation first checks if the specified object is this map; if so it returns <tt>true</tt>. Then, it
+ * checks if the specified object is a map whose size is identical to the size of this set; if not, it it returns
+ * <tt>false</tt>. If so, it applies the iteration as described above.
+ *
+ * @param obj object to be compared for equality with this map.
+ * @return <tt>true</tt> if the specified object is equal to this map.
+ */
+ public boolean equals(Object obj) {
+ if (obj == this) {
+ return true;
+ }
+
+ if (!(obj instanceof Abstract${keyTypeCap}${valueTypeCap}Map)) {
+ return false;
+ }
+ final Abstract${keyTypeCap}${valueTypeCap}Map other = (Abstract${keyTypeCap}${valueTypeCap}Map) obj;
+ if (other.size() != size()) {
+ return false;
+ }
+
+ return
+ forEachPair(
+ new ${keyTypeCap}${valueTypeCap}Procedure() {
+ @Override
+ public boolean apply(${keyType} key, ${valueType} value) {
+ return other.containsKey(key) && other.get(key) == value;
+ }
+ }
+ )
+ &&
+ other.forEachPair(
+ new ${keyTypeCap}${valueTypeCap}Procedure() {
+ @Override
+ public boolean apply(${keyType} key, ${valueType} value) {
+ return containsKey(key) && get(key) == value;
+ }
+ }
+ );
+ }
+
+ /**
+ * Applies a procedure to each key of the receiver, if any. Note: Iterates over the keys in no particular order.
+ * Subclasses can define a particular order, for example, "sorted by key". All methods which <i>can</i> be expressed
+ * in terms of this method (most methods can) <i>must guarantee</i> to use the <i>same</i> order defined by this
+ * method, even if it is no particular order. This is necessary so that, for example, methods <tt>keys</tt> and
+ * <tt>values</tt> will yield association pairs, not two uncorrelated lists.
+ *
+ * @param procedure the procedure to be applied. Stops iteration if the procedure returns <tt>false</tt>, otherwise
+ * continues.
+ * @return <tt>false</tt> if the procedure stopped before all keys where iterated over, <tt>true</tt> otherwise.
+ */
+ public abstract boolean forEachKey(${keyTypeCap}Procedure procedure);
+
+ /**
+ * Applies a procedure to each (key,value) pair of the receiver, if any. Iteration order is guaranteed to be
+ * <i>identical</i> to the order used by method {@link #forEachKey(IntProcedure)}.
+ *
+ * @param procedure the procedure to be applied. Stops iteration if the procedure returns <tt>false</tt>, otherwise
+ * continues.
+ * @return <tt>false</tt> if the procedure stopped before all keys where iterated over, <tt>true</tt> otherwise.
+ */
+ public boolean forEachPair(final ${keyTypeCap}${valueTypeCap}Procedure procedure) {
+ return forEachKey(
+ new ${keyTypeCap}Procedure() {
+ @Override
+ public boolean apply(${keyType} key) {
+ return procedure.apply(key, get(key));
+ }
+ }
+ );
+ }
+
+ /**
+ * Returns the value associated with the specified key. It is often a good idea to first check with {@link
+ * #containsKey(int)} whether the given key has a value associated or not, i.e. whether there exists an association
+ * for the given key or not.
+ *
+ * @param key the key to be searched for.
+ * @return the value associated with the specified key; <tt>0</tt> if no such key is present.
+ */
+ public abstract ${valueType} get(${keyType} key);
+
+ /**
+ * Returns the first key the given value is associated with. It is often a good idea to first check with {@link
+ * #containsValue(int)} whether there exists an association from a key to this value. Search order is guaranteed to be
+ * <i>identical</i> to the order used by method {@link #forEachKey(IntProcedure)}.
+ *
+ * @param value the value to search for.
+ * @return the first key for which holds <tt>get(key) == value</tt>; returns <tt>${keyObjectType}.MIN_VALUE</tt> if no such key
+ * exists.
+ */
+ public ${keyType} keyOf(final ${valueType} value) {
+ final ${keyType}[] foundKey = new ${keyType}[1];
+ boolean notFound = forEachPair(
+ new ${keyTypeCap}${valueTypeCap}Procedure() {
+ @Override
+ public boolean apply(${keyType} iterKey, ${valueType} iterValue) {
+ boolean found = value == iterValue;
+ if (found) {
+ foundKey[0] = iterKey;
+ }
+ return !found;
+ }
+ }
+ );
+ if (notFound) {
+ return ${keyObjectType}.MIN_VALUE;
+ }
+ return foundKey[0];
+ }
+
+ /**
+ * Returns a list filled with all keys contained in the receiver. The returned list has a size that equals
+ * <tt>this.size()</tt>. Iteration order is guaranteed to be <i>identical</i> to the order used by method {@link
+ * #forEachKey(IntProcedure)}. <p> This method can be used to iterate over the keys of the receiver.
+ *
+ * @return the keys.
+ */
+ public ${keyTypeCap}ArrayList keys() {
+ ${keyTypeCap}ArrayList list = new ${keyTypeCap}ArrayList(size());
+ keys(list);
+ return list;
+ }
+
+ /**
+ * Fills all keys contained in the receiver into the specified list. Fills the list, starting at index 0. After this
+ * call returns the specified list has a new size that equals <tt>this.size()</tt>. Iteration order is guaranteed to
+ * be <i>identical</i> to the order used by method {@link #forEachKey(IntProcedure)}. <p> This method can be used to
+ * iterate over the keys of the receiver.
+ *
+ * @param list the list to be filled, can have any size.
+ */
+ public void keys(final ${keyTypeCap}ArrayList list) {
+ list.clear();
+ forEachKey(
+ new ${keyTypeCap}Procedure() {
+ @Override
+ public boolean apply(${keyType} key) {
+ list.add(key);
+ return true;
+ }
+ }
+ );
+ }
+
+ /**
+ * Fills all keys <i>sorted ascending by their associated value</i> into the specified list. Fills into the list,
+ * starting at index 0. After this call returns the specified list has a new size that equals <tt>this.size()</tt>.
+ * Primary sort criterium is "value", secondary sort criterium is "key". This means that if any two values are equal,
+ * the smaller key comes first. <p> <b>Example:</b> <br> <tt>keys = (8,7,6), values = (1,2,2) --> keyList =
+ * (8,6,7)</tt>
+ *
+ * @param keyList the list to be filled, can have any size.
+ */
+ public void keysSortedByValue(${keyTypeCap}ArrayList keyList) {
+ pairsSortedByValue(keyList, new ${valueTypeCap}ArrayList(size()));
+ }
+
+ /**
+ * Fills all pairs satisfying a given condition into the specified lists. Fills into the lists, starting at index 0.
+ * After this call returns the specified lists both have a new size, the number of pairs satisfying the condition.
+ * Iteration order is guaranteed to be <i>identical</i> to the order used by method {@link #forEachKey(IntProcedure)}.
+ * <p> <b>Example:</b> <br>
+ * <pre>
+ * IntIntProcedure condition = new IntIntProcedure() { // match even keys only
+ * public boolean apply(int key, int value) { return key%2==0; }
+ * }
+ * keys = (8,7,6), values = (1,2,2) --> keyList = (6,8), valueList = (2,1)</tt>
+ * </pre>
+ *
+ * @param condition the condition to be matched. Takes the current key as first and the current value as second
+ * argument.
+ * @param keyList the list to be filled with keys, can have any size.
+ * @param valueList the list to be filled with values, can have any size.
+ */
+ public void pairsMatching(final ${keyTypeCap}${valueTypeCap}Procedure condition,
+ final ${keyTypeCap}ArrayList keyList,
+ final ${valueTypeCap}ArrayList valueList) {
+ keyList.clear();
+ valueList.clear();
+
+ forEachPair(
+ new ${keyTypeCap}${valueTypeCap}Procedure() {
+ @Override
+ public boolean apply(${keyType} key, ${valueType} value) {
+ if (condition.apply(key, value)) {
+ keyList.add(key);
+ valueList.add(value);
+ }
+ return true;
+ }
+ }
+ );
+ }
+
+ /**
+ * Fills all keys and values <i>sorted ascending by key</i> into the specified lists. Fills into the lists, starting
+ * at index 0. After this call returns the specified lists both have a new size that equals <tt>this.size()</tt>. <p>
+ * <b>Example:</b> <br> <tt>keys = (8,7,6), values = (1,2,2) --> keyList = (6,7,8), valueList = (2,2,1)</tt>
+ *
+ * @param keyList the list to be filled with keys, can have any size.
+ * @param valueList the list to be filled with values, can have any size.
+ */
+ public void pairsSortedByKey(${keyTypeCap}ArrayList keyList, ${valueTypeCap}ArrayList valueList) {
+ keys(keyList);
+ keyList.sort();
+ valueList.setSize(keyList.size());
+ for (int i = keyList.size(); --i >= 0;) {
+ valueList.setQuick(i, get(keyList.getQuick(i)));
+ }
+ }
+
+ /**
+ * Fills all keys and values <i>sorted ascending by value</i> into the specified lists. Fills into the lists, starting
+ * at index 0. After this call returns the specified lists both have a new size that equals <tt>this.size()</tt>.
+ * Primary sort criterium is "value", secondary sort criterium is "key". This means that if any two values are equal,
+ * the smaller key comes first. <p> <b>Example:</b> <br> <tt>keys = (8,7,6), values = (1,2,2) --> keyList = (8,6,7),
+ * valueList = (1,2,2)</tt>
+ *
+ * @param keyList the list to be filled with keys, can have any size.
+ * @param valueList the list to be filled with values, can have any size.
+ */
+ public void pairsSortedByValue(${keyTypeCap}ArrayList keyList, ${valueTypeCap}ArrayList valueList) {
+ keys(keyList);
+ values(valueList);
+
+ final ${keyType}[] k = keyList.elements();
+ final ${valueType}[] v = valueList.elements();
+ Swapper swapper = new Swapper() {
+ @Override
+ public void swap(int a, int b) {
+ ${valueType} t1 = v[a];
+ v[a] = v[b];
+ v[b] = t1;
+ ${keyType} t2 = k[a];
+ k[a] = k[b];
+ k[b] = t2;
+ }
+ };
+
+ IntComparator comp = new IntComparator() {
+ @Override
+ public int compare(int a, int b) {
+ return v[a] < v[b] ? -1 : v[a] > v[b] ? 1 : (k[a] < k[b] ? -1 : (k[a] == k[b] ? 0 : 1));
+ }
+ };
+
+ Sorting.quickSort(0, keyList.size(), comp, swapper);
+ }
+
+ /**
+ * Associates the given key with the given value. Replaces any old <tt>(key,someOtherValue)</tt> association, if
+ * existing.
+ *
+ * @param key the key the value shall be associated with.
+ * @param value the value to be associated.
+ * @return <tt>true</tt> if the receiver did not already contain such a key; <tt>false</tt> if the receiver did
+ * already contain such a key - the new value has now replaced the formerly associated value.
+ */
+ public abstract boolean put(${keyType} key, ${valueType} value);
+
+ /**
+ * Removes the given key with its associated element from the receiver, if present.
+ *
+ * @param key the key to be removed from the receiver.
+ * @return <tt>true</tt> if the receiver contained the specified key, <tt>false</tt> otherwise.
+ */
+ public abstract boolean removeKey(${keyType} key);
+
+ /**
+ * Returns a string representation of the receiver, containing the String representation of each key-value pair,
+ * sorted ascending by key.
+ */
+ public String toString() {
+ ${keyTypeCap}ArrayList theKeys = keys();
+ //theKeys.sort();
+
+ StringBuilder buf = new StringBuilder();
+ buf.append('[');
+ int maxIndex = theKeys.size() - 1;
+ for (int i = 0; i <= maxIndex; i++) {
+ ${keyType} key = theKeys.get(i);
+ buf.append(String.valueOf(key));
+ buf.append("->");
+ buf.append(String.valueOf(get(key)));
+ if (i < maxIndex) {
+ buf.append(", ");
+ }
+ }
+ buf.append(']');
+ return buf.toString();
+ }
+
+ /**
+ * Returns a string representation of the receiver, containing the String representation of each key-value pair,
+ * sorted ascending by value.
+ */
+ public String toStringByValue() {
+ ${keyTypeCap}ArrayList theKeys = new ${keyTypeCap}ArrayList();
+ keysSortedByValue(theKeys);
+
+ StringBuilder buf = new StringBuilder();
+ buf.append('[');
+ int maxIndex = theKeys.size() - 1;
+ for (int i = 0; i <= maxIndex; i++) {
+ ${keyType} key = theKeys.get(i);
+ buf.append(String.valueOf(key));
+ buf.append("->");
+ buf.append(String.valueOf(get(key)));
+ if (i < maxIndex) {
+ buf.append(", ");
+ }
+ }
+ buf.append(']');
+ return buf.toString();
+ }
+
+ /**
+ * Returns a list filled with all values contained in the receiver. The returned list has a size that equals
+ * <tt>this.size()</tt>. Iteration order is guaranteed to be <i>identical</i> to the order used by method {@link
+ * #forEachKey(IntProcedure)}. <p> This method can be used to iterate over the values of the receiver.
+ *
+ * @return the values.
+ */
+ public ${valueTypeCap}ArrayList values() {
+ ${valueTypeCap}ArrayList list = new ${valueTypeCap}ArrayList(size());
+ values(list);
+ return list;
+ }
+
+ /**
+ * Fills all values contained in the receiver into the specified list. Fills the list, starting at index 0. After this
+ * call returns the specified list has a new size that equals <tt>this.size()</tt>. Iteration order is guaranteed to
+ * be <i>identical</i> to the order used by method {@link #forEachKey(IntProcedure)}. <p> This method can be used to
+ * iterate over the values of the receiver.
+ *
+ * @param list the list to be filled, can have any size.
+ */
+ public void values(final ${valueTypeCap}ArrayList list) {
+ list.clear();
+ forEachKey(
+ new ${keyTypeCap}Procedure() {
+ @Override
+ public boolean apply(${keyType} key) {
+ list.add(get(key));
+ return true;
+ }
+ }
+ );
+ }
+
+ #if (${valueTypeFloating} == 'true')
+ /**
+ * Assigns the result of a function to each value; <tt>v[i] = function(v[i])</tt>.
+ *
+ * @param function a function object taking as argument the current association's value.
+ */
+ public void assign(final ${valueTypeCap}Function function) {
+ copy().forEachPair(
+ new ${keyTypeCap}${valueTypeCap}Procedure() {
+ @Override
+ public boolean apply(${keyType} key, ${valueType} value) {
+ put(key, function.apply(value));
+ return true;
+ }
+ }
+ );
+ }
+
+ /**
+ * Clears the receiver, then adds all (key,value) pairs of <tt>other</tt>values to it.
+ *
+ * @param other the other map to be copied into the receiver.
+ */
+ public void assign(Abstract${keyTypeCap}${valueTypeCap}Map other) {
+ clear();
+ other.forEachPair(
+ new ${keyTypeCap}${valueTypeCap}Procedure() {
+ @Override
+ public boolean apply(${keyType} key, ${valueType} value) {
+ put(key, value);
+ return true;
+ }
+ }
+ );
+ }
+ #end
+}
Modified: 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=896192&r1=896191&r2=896192&view=diff
==============================================================================
--- lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/GenericSorting.java (original)
+++ lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/GenericSorting.java Tue Jan 5 19:46:26 2010
@@ -1,3 +1,21 @@
+/**
+ * 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.
+ */
/*
Copyright � 1999 CERN - European Organization for Nuclear Research.
Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose
@@ -10,14 +28,10 @@
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() {
}
@@ -105,16 +119,6 @@
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
@@ -168,138 +172,6 @@
}
/**
- * 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.
*
@@ -326,11 +198,4 @@
}
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);
- }
- }
}
Modified: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/Sorting.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/Sorting.java?rev=896192&r1=896191&r2=896192&view=diff
==============================================================================
--- lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/Sorting.java (original)
+++ lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/Sorting.java Tue Jan 5 19:46:26 2010
@@ -17,15 +17,6 @@
* under the License.
*/
-/*
-
-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 java.util.Comparator;
@@ -38,10 +29,8 @@
import org.apache.mahout.math.function.LongComparator;
import org.apache.mahout.math.function.ShortComparator;
-
public final class Sorting {
-
/* Specifies when to switch to insertion sort */
private static final int SIMPLE_LENGTH = 7;
@@ -491,6 +480,25 @@
: (comparisonxz > 0 ? c : a));
}
+ /**
+ * This is used for 'external' sorting. The comparator takes <em>indices</em>,
+ * not values, and compares the external values found at those indices.
+ * @param a
+ * @param b
+ * @param c
+ * @param comp
+ * @return
+ */
+ private static int med3(int a, int b, int c, IntComparator comp) {
+ int x = a, y = b, z = c;
+ int comparisonxy = comp.compare(x, y);
+ int comparisonxz = comp.compare(x, z);
+ int comparisonyz = comp.compare(y, z);
+ return comparisonxy < 0 ? (comparisonyz < 0 ? b
+ : (comparisonxz < 0 ? c : a)) : (comparisonyz > 0 ? b
+ : (comparisonxz > 0 ? c : a));
+ }
+
private static int med3(long[] array, int a, int b, int c, LongComparator comp) {
long x = array[a], y = array[b], z = array[c];
int comparisonxy = comp.compare(x, y);
@@ -632,8 +640,161 @@
quickSort0(end - length, end, array, comp);
}
}
+
/**
+ * Sorts some external data with QuickSort.
+ *
+ * @param start
+ * the start index to sort.
+ * @param end
+ * the last + 1 index to sort.
+ * @param comp
+ * the comparator.
+ * @param swap an object that can exchange the positions of two items.
+ * @throws IllegalArgumentException
+ * if {@code start > end}.
+ * @throws ArrayIndexOutOfBoundsException
+ * if {@code start < 0} or {@code end > array.length}.
+ */
+ public static void quickSort(int start, int end, IntComparator comp, Swapper swap) {
+ checkBounds(end+1, start, end);
+ quickSort0(start, end, comp, swap);
+ }
+
+ private static void quickSort0(int start, int end, IntComparator comp, Swapper swap) {
+ int length = end - start;
+ if (length < 7) {
+ insertionSort(start, end, comp, swap);
+ return;
+ }
+ int middle = (start + end) / 2;
+ if (length > 7) {
+ int bottom = start;
+ int top = end - 1;
+ if (length > 40) {
+ // for lots of data, bottom, middle and top are medians near the beginning, middle or end of the data
+ int skosh = length / 8;
+ bottom = med3(bottom, bottom + skosh, bottom + (2 * skosh), comp);
+ middle = med3(middle - skosh, middle, middle + skosh, comp);
+ top = med3(top - (2 * skosh), top - skosh, top, comp);
+ }
+ middle = med3(bottom, middle, top, comp);
+ }
+
+ int partitionIndex = middle; // an index, not a value.
+
+ // regions from a to b and from c to d are what we will recursively sort
+ int a, b, c, d;
+ a = b = start;
+ c = d = end - 1;
+ while (b <= c) {
+ // copy all values equal to the partition value to before a..b. In the process, advance b
+ // as long as values less than the partition or equal are found, also stop when a..b collides with c..d
+ int comparison = comp.compare(b, partitionIndex);
+ while (b <= c && comparison <= 0) {
+ if (comparison == 0) {
+ if (a == partitionIndex) {
+ partitionIndex = b;
+ }
+ else if (b == partitionIndex) {
+ partitionIndex = a;
+ }
+ swap.swap(a, b);
+ a++;
+ }
+ b++;
+ comparison = comp.compare(b, partitionIndex);
+ }
+ // at this point [start..a) has partition values, [a..b) has values < partition
+ // also, either b>c or v[b] > partition value
+
+ comparison = comp.compare(c, partitionIndex);
+ while (c >= b && comparison >= 0) {
+ if (comparison == 0) {
+ if (c == partitionIndex) {
+ partitionIndex = d;
+ } else if (d == partitionIndex) {
+ partitionIndex = c;
+ }
+ swap.swap(c, d);
+
+ d--;
+ }
+ c--;
+ comparison = comp.compare(c, partitionIndex);
+ }
+ // now we also know that [d..end] contains partition values,
+ // [c..d) contains values > partition value
+ // also, either b>c or (v[b] > partition OR v[c] < partition)
+
+ if (b <= c) {
+ // v[b] > partition OR v[c] < partition
+ // swapping will let us continue to grow the two regions
+ if (c == partitionIndex) {
+ partitionIndex = b;
+ } else if (b == partitionIndex) {
+ partitionIndex = d;
+ }
+ swap.swap(b, c);
+ b++;
+ c--;
+ }
+ }
+ // now we know
+ // b = c+1
+ // [start..a) and [d..end) contain partition value
+ // all of [a..b) are less than partition
+ // all of [c..d) are greater than partition
+
+ // shift [a..b) to beginning
+ length = Math.min(a - start, b - a);
+ int l = start;
+ int h = b - length;
+ while (length-- > 0) {
+ swap.swap(l, h);
+ l++;
+ h++;
+ }
+
+ // shift [c..d) to end
+ length = Math.min(d - c, end - 1 - d);
+ l = b;
+ h = end - length;
+ while (length-- > 0) {
+ swap.swap(l, h);
+ l++;
+ h++;
+ }
+
+ // recurse left and right
+ length = b - a;
+ if (length > 0) {
+ quickSort0(start, start + length, comp, swap);
+ }
+
+ length = d - c;
+ if (length > 0) {
+ quickSort0(end - length, end, comp, swap);
+ }
+ }
+
+ /**
+ * In-place insertion sort that is fast for pre-sorted data.
+ *
+ * @param start Where to start sorting (inclusive)
+ * @param end Where to stop (exclusive)
+ * @param comp Sort order.
+ * @param swap How to swap items.
+ */
+ private static void insertionSort(int start, int end, IntComparator comp, Swapper swap) {
+ for (int i = start + 1; i < end; i++) {
+ for (int j = i; j > start && comp.compare(j - 1, j) > 0; j--) {
+ swap.swap(j - 1, j);
+ }
+ }
+ }
+ /**
* Sorts the specified range in the array in a specified order.
*
* @param array
@@ -2014,6 +2175,7 @@
return l - 1;
}
+
private final static LongComparator naturalLongComparison = new LongComparator() {
@Override
public int compare(long o1, long o2) {
@@ -2366,4 +2528,4 @@
return l - 1;
}
-}
\ No newline at end of file
+}
Modified: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/Swapper.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/Swapper.java?rev=896192&r1=896191&r2=896192&view=diff
==============================================================================
--- lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/Swapper.java (original)
+++ lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/Swapper.java Tue Jan 5 19:46:26 2010
@@ -14,9 +14,6 @@
* @see org.apache.mahout.math.GenericSorting
*
*/
-
-/** @deprecated until unit tests are in place. Until this time, this class/interface is unsupported. */
-@Deprecated
public interface Swapper {
/** Swaps the generic data g[a] with g[b]. */
Added: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/function/FloatFunction.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/function/FloatFunction.java?rev=896192&view=auto
==============================================================================
--- lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/function/FloatFunction.java (added)
+++ lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/function/FloatFunction.java Tue Jan 5 19:46:26 2010
@@ -0,0 +1,36 @@
+/**
+ * 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.function;
+
+
+/**
+ * Interface that represents a function object: a function that takes a single argument and returns a single value.
+ *
+ */
+public interface FloatFunction {
+
+ /**
+ * Applies a function to an argument.
+ *
+ * @param argument argument passed to the function.
+ * @return the result of the function.
+ */
+ float apply(float argument);
+}
Modified: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/map/AbstractIntObjectMap.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/map/AbstractIntObjectMap.java?rev=896192&r1=896191&r2=896192&view=diff
==============================================================================
--- lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/map/AbstractIntObjectMap.java (original)
+++ lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/map/AbstractIntObjectMap.java Tue Jan 5 19:46:26 2010
@@ -1,3 +1,21 @@
+/**
+ * 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.
+ */
/*
Copyright � 1999 CERN - European Organization for Nuclear Research.
Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose
@@ -336,7 +354,7 @@
}
};
- GenericSorting.quickSort(0, keyList.size(), comp, swapper);
+ org.apache.mahout.math.Sorting.quickSort(0, keyList.size(), comp, swapper);
}
/**
Modified: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/map/AbstractLongObjectMap.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/map/AbstractLongObjectMap.java?rev=896192&r1=896191&r2=896192&view=diff
==============================================================================
--- lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/map/AbstractLongObjectMap.java (original)
+++ lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/map/AbstractLongObjectMap.java Tue Jan 5 19:46:26 2010
@@ -1,3 +1,21 @@
+/**
+ * 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.
+ */
/*
Copyright � 1999 CERN - European Organization for Nuclear Research.
Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose
@@ -9,6 +27,7 @@
package org.apache.mahout.math.map;
import org.apache.mahout.math.GenericSorting;
+import org.apache.mahout.math.Sorting;
import org.apache.mahout.math.Swapper;
import org.apache.mahout.math.function.IntComparator;
import org.apache.mahout.math.function.LongObjectProcedure;
@@ -336,7 +355,7 @@
}
};
- GenericSorting.quickSort(0, keyList.size(), comp, swapper);
+ Sorting.quickSort(0, keyList.size(), comp, swapper);
}
/**
Modified: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/doublealgo/Sorting.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/doublealgo/Sorting.java?rev=896192&r1=896191&r2=896192&view=diff
==============================================================================
--- lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/doublealgo/Sorting.java (original)
+++ lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/doublealgo/Sorting.java Tue Jan 5 19:46:26 2010
@@ -1,3 +1,21 @@
+/**
+ * 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.
+ */
/*
Copyright � 1999 CERN - European Organization for Nuclear Research.
Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose
@@ -59,7 +77,7 @@
}
protected void runSort(int fromIndex, int toIndex, IntComparator c, org.apache.mahout.math.Swapper swapper) {
- GenericSorting.quickSort(fromIndex, toIndex, c, swapper);
+ org.apache.mahout.math.Sorting.quickSort(fromIndex, toIndex, c, swapper);
}
/**
Modified: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/linalg/Algebra.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/linalg/Algebra.java?rev=896192&r1=896191&r2=896192&view=diff
==============================================================================
--- lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/linalg/Algebra.java (original)
+++ lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/linalg/Algebra.java Tue Jan 5 19:46:26 2010
@@ -11,6 +11,7 @@
import org.apache.mahout.math.GenericPermuting;
import org.apache.mahout.math.GenericSorting;
import org.apache.mahout.math.PersistentObject;
+import org.apache.mahout.math.Sorting;
import org.apache.mahout.math.Swapper;
import org.apache.mahout.math.bitvector.QuickBitVector;
import org.apache.mahout.math.function.DoubleDoubleFunction;
@@ -739,7 +740,7 @@
values.set(b, tmp);
}
};
- GenericSorting.quickSort(0, names.size(), comp, swapper);
+ Sorting.quickSort(0, names.size(), comp, swapper);
// determine padding for nice formatting
int maxLength = 0;
Modified: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/linalg/Property.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/linalg/Property.java?rev=896192&r1=896191&r2=896192&view=diff
==============================================================================
--- lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/linalg/Property.java (original)
+++ lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/linalg/Property.java Tue Jan 5 19:46:26 2010
@@ -10,6 +10,7 @@
import org.apache.mahout.math.GenericSorting;
import org.apache.mahout.math.PersistentObject;
+import org.apache.mahout.math.Sorting;
import org.apache.mahout.math.Swapper;
import org.apache.mahout.math.function.IntComparator;
import org.apache.mahout.math.jet.math.Functions;
@@ -1067,7 +1068,7 @@
values.set(b, tmp);
}
};
- GenericSorting.quickSort(0, names.size(), comp, swapper);
+ Sorting.quickSort(0, names.size(), comp, swapper);
// determine padding for nice formatting
int maxLength = 0;
Modified: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/objectalgo/Sorting.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/objectalgo/Sorting.java?rev=896192&r1=896191&r2=896192&view=diff
==============================================================================
--- lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/objectalgo/Sorting.java (original)
+++ lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/objectalgo/Sorting.java Tue Jan 5 19:46:26 2010
@@ -1,3 +1,21 @@
+/**
+ * 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.
+ */
/*
Copyright � 1999 CERN - European Organization for Nuclear Research.
Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose
@@ -72,7 +90,7 @@
}
protected void runSort(int fromIndex, int toIndex, IntComparator c, org.apache.mahout.math.Swapper swapper) {
- GenericSorting.quickSort(fromIndex, toIndex, c, swapper);
+ org.apache.mahout.math.Sorting.quickSort(fromIndex, toIndex, c, swapper);
}
/**
Modified: lucene/mahout/trunk/math/src/test/java/org/apache/mahout/math/GenericSortingTest.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/test/java/org/apache/mahout/math/GenericSortingTest.java?rev=896192&r1=896191&r2=896192&view=diff
==============================================================================
--- lucene/mahout/trunk/math/src/test/java/org/apache/mahout/math/GenericSortingTest.java (original)
+++ lucene/mahout/trunk/math/src/test/java/org/apache/mahout/math/GenericSortingTest.java Tue Jan 5 19:46:26 2010
@@ -58,7 +58,7 @@
td[x] = 20 - x;
}
SomethingToSort sts = new SomethingToSort(td);
- GenericSorting.quickSort(0, 20, sts, sts);
+ Sorting.quickSort(0, 20, sts, sts);
for (int x = 0; x < 20; x ++) {
assertEquals(x+1, td[x]);
}
Modified: lucene/mahout/trunk/math/src/test/java/org/apache/mahout/math/SortingTest.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/test/java/org/apache/mahout/math/SortingTest.java?rev=896192&r1=896191&r2=896192&view=diff
==============================================================================
--- lucene/mahout/trunk/math/src/test/java/org/apache/mahout/math/SortingTest.java (original)
+++ lucene/mahout/trunk/math/src/test/java/org/apache/mahout/math/SortingTest.java Tue Jan 5 19:46:26 2010
@@ -96,7 +96,7 @@
@Before
public void before() {
- random = new Random();
+ random = new Random(0);
}
static class ForSorting implements Comparable<ForSorting> {
@@ -310,6 +310,36 @@
}
@Test
+ public void testQuickSortExternals() {
+ int stuff[] = randomInts();
+ final Integer[] bigInts = new Integer[stuff.length];
+ for (int x = 0; x < stuff.length; x ++) {
+ bigInts[x] = Integer.valueOf(stuff[x]);
+ }
+
+ Sorting.quickSort(0, stuff.length, new IntComparator() {
+
+ @Override
+ public int compare(int o1, int o2) {
+ return bigInts[o1].compareTo(bigInts[o2]);
+ }},
+
+ new Swapper() {
+
+ @Override
+ public void swap(int a, int b) {
+ Integer temp = bigInts[a];
+ bigInts[a] = bigInts[b];
+ bigInts[b] = temp;
+ }});
+
+ for (int x = 0; x < (stuff.length - 1); x++) {
+ assertTrue("problem at index " + x, bigInts[x].compareTo(bigInts[x + 1]) <= 0);
+ }
+
+ }
+
+ @Test
public void testQuickSortLongs() {
LongComparator revComp = new LongComparator() {