You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@mahout.apache.org by ro...@apache.org on 2009/12/28 22:30:23 UTC
svn commit: r894251 [3/3] - in /lucene/mahout/trunk:
collections-codegen-plugin/src/main/java/org/apache/mahout/collection_codegen/
math/ math/src/main/java-templates/org/apache/mahout/math/buffer/
math/src/main/java-templates/org/apache/mahout/math/fu...
Modified: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/list/ObjectArrayList.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/list/ObjectArrayList.java?rev=894251&r1=894250&r2=894251&view=diff
==============================================================================
--- lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/list/ObjectArrayList.java (original)
+++ lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/list/ObjectArrayList.java Mon Dec 28 21:30:05 2009
@@ -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
@@ -8,35 +26,24 @@
*/
package org.apache.mahout.math.list;
-import org.apache.mahout.math.Sorting;
import org.apache.mahout.math.function.ObjectProcedure;
import org.apache.mahout.math.jet.random.Uniform;
import org.apache.mahout.math.jet.random.engine.DRand;
-import java.util.ArrayList;
-import java.util.Arrays;
import java.util.Collection;
-import java.util.Comparator;
import java.util.Date;
-import java.util.Iterator;
-import java.util.List;
/**
- Resizable list holding <code>Object</code> elements; implemented with arrays.
- First see the <a href="package-summary.html">package summary</a> and javadoc <a href="package-tree.html">tree view</a> to get the broad picture.
- */
+ Resizable list holding <code>${valueType}</code> elements; implemented with arrays.
+*/
-/** @deprecated until unit tests are in place. Until this time, this class/interface is unsupported. */
-@Deprecated
-public class ObjectArrayList extends AbstractList<Object[]> {
+public class ObjectArrayList<T> extends AbstractObjectList<T> {
/**
* The array buffer into which the elements of the list are stored. The capacity of the list is the length of this
* array buffer.
*/
- protected Object[] elements;
-
- /** The size of the list. */
- protected int size;
+ private Object[] elements;
+ private int size;
/** Constructs an empty list. */
public ObjectArrayList() {
@@ -52,7 +59,7 @@
*
* @param elements the array to be backed by the the constructed list
*/
- public ObjectArrayList(Object[] elements) {
+ public ObjectArrayList(T[] elements) {
elements(elements);
}
@@ -62,9 +69,9 @@
* @param initialCapacity the number of elements the receiver can hold without auto-expanding itself by allocating new
* internal memory.
*/
+ @SuppressWarnings("unchecked")
public ObjectArrayList(int initialCapacity) {
- this(new Object[initialCapacity]);
- size = 0;
+ elements((T[])new Object[initialCapacity]);
}
/**
@@ -72,7 +79,8 @@
*
* @param element element to be appended to this list.
*/
- public void add(Object element) {
+ public void add(T element) {
+ // overridden for performance only.
if (size == elements.length) {
ensureCapacity(size + 1);
}
@@ -80,20 +88,6 @@
}
/**
- * Appends the part of the specified list between <code>from</code> (inclusive) and <code>to</code> (inclusive) to the
- * receiver.
- *
- * @param other the list to be added to the receiver.
- * @param from the index of the first element to be appended (inclusive).
- * @param to the index of the last element to be appended (inclusive).
- * @throws IndexOutOfBoundsException index is out of range (<tt>other.size()>0 && (from<0 || from>to ||
- * to>=other.size())</tt>).
- */
- public void addAllOfFromTo(ObjectArrayList other, int from, int to) {
- beforeInsertAllOfFromTo(size, other, from, to);
- }
-
- /**
* Inserts the specified element before the specified position into the receiver. Shifts the element currently at that
* position (if any) and any subsequent elements to the right.
*
@@ -101,8 +95,12 @@
* @param element element to be inserted.
* @throws IndexOutOfBoundsException index is out of range (<tt>index < 0 || index > size()</tt>).
*/
- public void beforeInsert(int index, Object element) {
+ public void beforeInsert(int index, T element) {
// overridden for performance only.
+ if (size == index) {
+ add(element);
+ return;
+ }
if (index > size || index < 0) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
@@ -112,185 +110,28 @@
size++;
}
- /**
- * Inserts the part of the specified list between <code>otherFrom</code> (inclusive) and <code>otherTo</code>
- * (inclusive) before the specified position into the receiver. Shifts the element currently at that position (if any)
- * and any subsequent elements to the right.
- *
- * @param index index before which to insert first element from the specified list (must be in [0,size])..
- * @param other list of which a part is to be inserted into the receiver.
- * @param from the index of the first element to be inserted (inclusive).
- * @param to the index of the last element to be inserted (inclusive).
- * @throws IndexOutOfBoundsException index is out of range (<tt>other.size()>0 && (from<0 || from>to ||
- * to>=other.size())</tt>).
- * @throws IndexOutOfBoundsException index is out of range (<tt>index < 0 || index > size()</tt>).
- */
- public void beforeInsertAllOfFromTo(int index, ObjectArrayList other, int from, int to) {
- int length = to - from + 1;
- this.beforeInsertDummies(index, length);
- this.replaceFromToWithFrom(index, index + length - 1, other, from);
- }
-
- /**
- * Inserts length dummies before the specified position into the receiver. Shifts the element currently at that
- * position (if any) and any subsequent elements to the right.
- *
- * @param index index before which to insert dummies (must be in [0,size])..
- * @param length number of dummies to be inserted.
- */
- @Override
- protected void beforeInsertDummies(int index, int length) {
- if (index > size || index < 0) {
- throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
- }
- if (length > 0) {
- ensureCapacity(size + length);
- System.arraycopy(elements, index, elements, index + length, size - index);
- size += length;
- }
- }
-
- /**
- * Searches the receiver for the specified value using the binary search algorithm. The receiver must be sorted into
- * ascending order according to the <i>natural ordering</i> of its elements (as by the sort method) prior to making
- * this call. If it is not sorted, the results are undefined: in particular, the call may enter an infinite loop. If
- * the receiver contains multiple elements equal to the specified object, there is no guarantee which instance will be
- * found.
- *
- * @param key the value to be searched for.
- * @return index of the search key, if it is contained in the receiver; otherwise, <tt>(-(<i>insertion point</i>) -
- * 1)</tt>. The <i>insertion point</i> is defined as the the point at which the value would be inserted into
- * the receiver: the index of the first element greater than the key, or <tt>receiver.size()</tt>, if all
- * elements in the receiver are less than the specified key. Note that this guarantees that the return value
- * will be >= 0 if and only if the key is found.
- * @see Comparable
- * @see java.util.Arrays
- */
- public int binarySearch(Object key) {
- return this.binarySearchFromTo(key, 0, size - 1);
- }
-
- /**
- * Searches the receiver for the specified value using the binary search algorithm. The receiver must be sorted into
- * ascending order according to the <i>natural ordering</i> of its elements (as by the sort method) prior to making
- * this call. If it is not sorted, the results are undefined: in particular, the call may enter an infinite loop. If
- * the receiver contains multiple elements equal to the specified object, there is no guarantee which instance will be
- * found.
- *
- * @param key the value to be searched for.
- * @param from the leftmost search position, inclusive.
- * @param to the rightmost search position, inclusive.
- * @return index of the search key, if it is contained in the receiver; otherwise, <tt>(-(<i>insertion point</i>) -
- * 1)</tt>. The <i>insertion point</i> is defined as the the point at which the value would be inserted into
- * the receiver: the index of the first element greater than the key, or <tt>receiver.size()</tt>, if all
- * elements in the receiver are less than the specified key. Note that this guarantees that the return value
- * will be >= 0 if and only if the key is found.
- * @see Comparable
- * @see java.util.Arrays
- */
- public int binarySearchFromTo(Object key, int from, int to) {
- int low = from;
- int high = to;
-
- while (low <= high) {
- int mid = (low + high) / 2;
- Object midVal = elements[mid];
- int cmp = ((Comparable<Object>) midVal).compareTo(key);
-
- if (cmp < 0) {
- low = mid + 1;
- } else if (cmp > 0) {
- high = mid - 1;
- } else {
- return mid;
- } // key found
- }
- return -(low + 1); // key not found.
- }
-
- /**
- * Searches the receiver for the specified value using the binary search algorithm. The receiver must be sorted into
- * ascending order according to the specified comparator. All elements in the range must be <i>mutually
- * comparable</i> by the specified comparator (that is, <tt>c.compare(e1, e2)</tt> must not throw a
- * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and <tt>e2</tt> in the range).<p>
- *
- * If the receiver is not sorted, the results are undefined: in particular, the call may enter an infinite loop. If
- * the receiver contains multiple elements equal to the specified object, there is no guarantee which instance will be
- * found.
- *
- * @param key the value to be searched for.
- * @param from the leftmost search position, inclusive.
- * @param to the rightmost search position, inclusive.
- * @param comparator the comparator by which the receiver is sorted.
- * @return index of the search key, if it is contained in the receiver; otherwise, <tt>(-(<i>insertion point</i>) -
- * 1)</tt>. The <i>insertion point</i> is defined as the the point at which the value would be inserted into
- * the receiver: the index of the first element greater than the key, or <tt>receiver.size()</tt>, if all
- * elements in the receiver are less than the specified key. Note that this guarantees that the return value
- * will be >= 0 if and only if the key is found.
- * @throws ClassCastException if the receiver contains elements that are not <i>mutually comparable</i> using the
- * specified comparator.
- * @see org.apache.mahout.math.Sorting
- * @see java.util.Arrays
- * @see java.util.Comparator
- */
- public int binarySearchFromTo(Object key, int from, int to, Comparator<Object> comparator) {
- return org.apache.mahout.math.Sorting.binarySearchFromTo(this.elements, key, from, to, comparator);
- }
/**
- * Returns a copy of the receiver such that the copy and the receiver <i>share</i> the same elements, but do not share
- * the same array to index them; So modifying an object in the copy modifies the object in the receiver and vice
- * versa; However, structurally modifying the copy (for example changing its size, setting other objects at indexes,
- * etc.) does not affect the receiver and vice versa.
+ * Returns a deep copy of the receiver.
*
- * @return a copy of the receiver.
+ * @return a deep copy of the receiver.
*/
+ @SuppressWarnings("unchecked")
@Override
public Object clone() {
- ObjectArrayList v = (ObjectArrayList) super.clone();
- v.elements = elements.clone();
- return v;
- }
-
- /**
- * Returns true if the receiver contains the specified element. Tests for equality or identity as specified by
- * testForEquality.
- *
- * @param elem element to search for.
- * @param testForEquality if true -> test for equality, otherwise for identity.
- */
- public boolean contains(Object elem, boolean testForEquality) {
- return indexOfFromTo(elem, 0, size - 1, testForEquality) >= 0;
- }
-
- /**
- * Returns a copy of the receiver; call <code>clone()</code> and casts the result. Returns a copy such that the copy
- * and the receiver <i>share</i> the same elements, but do not share the same array to index them; So modifying an
- * object in the copy modifies the object in the receiver and vice versa; However, structurally modifying the copy
- * (for example changing its size, setting other objects at indexes, etc.) does not affect the receiver and vice
- * versa.
- *
- * @return a copy of the receiver.
- */
- public ObjectArrayList copy() {
- return (ObjectArrayList) clone();
+ // overridden for performance only.
+ ObjectArrayList<T> clone = new ObjectArrayList<T>((T[]) elements.clone());
+ return clone;
}
/**
- * Deletes the first element from the receiver that matches the specified element. Does nothing, if no such matching
- * element is contained.
- *
- * Tests elements for equality or identity as specified by <tt>testForEquality</tt>. When testing for equality, two
- * elements <tt>e1</tt> and <tt>e2</tt> are <i>equal</i> if <tt>(e1==null ? e2==null : e1.equals(e2))</tt>.)
+ * Returns a deep copy of the receiver; uses <code>clone()</code> and casts the result.
*
- * @param testForEquality if true -> tests for equality, otherwise for identity.
- * @param element the element to be deleted.
+ * @return a deep copy of the receiver.
*/
- public void delete(Object element, boolean testForEquality) {
- int index = indexOfFromTo(element, 0, size - 1, testForEquality);
- if (index >= 0) {
- removeFromTo(index, index);
- }
+ @SuppressWarnings("unchecked")
+ public ObjectArrayList<T> copy() {
+ return (ObjectArrayList<T>) clone();
}
/**
@@ -301,8 +142,9 @@
*
* @return the elements currently stored.
*/
- public Object[] elements() {
- return elements;
+ @SuppressWarnings("unchecked")
+ public<Q> Q[] elements() {
+ return (Q[])elements;
}
/**
@@ -315,10 +157,9 @@
* @param elements the new elements to be stored.
* @return the receiver itself.
*/
- public ObjectArrayList elements(Object[] elements) {
+ public void elements(T[] elements) {
this.elements = elements;
this.size = elements.length;
- return this;
}
/**
@@ -332,32 +173,19 @@
}
/**
- * Compares the specified Object with the receiver for equality. Returns true if and only if the specified Object is
- * also an ObjectArrayList, both lists have the same size, and all corresponding pairs of elements in the two lists
- * are equal. In other words, two lists are defined to be equal if they contain the same elements in the same order.
- * Two elements <tt>e1</tt> and <tt>e2</tt> are <i>equal</i> if <tt>(e1==null ? e2==null : e1.equals(e2))</tt>.)
+ * Compares the specified Object with the receiver. Returns true if and only if the specified Object is also an
+ * ArrayList of the same type, both Lists have the same size, and all corresponding pairs of elements in the two Lists
+ * are identical. In other words, two Lists are defined to be equal if they contain the same elements in the same
+ * order.
*
* @param otherObj the Object to be compared for equality with the receiver.
* @return true if the specified Object is equal to the receiver.
*/
+ @SuppressWarnings("unchecked")
public boolean equals(Object otherObj) { //delta
- return equals(otherObj, true);
- }
-
- /**
- * Compares the specified Object with the receiver for equality. Returns true if and only if the specified Object is
- * also an ObjectArrayList, both lists have the same size, and all corresponding pairs of elements in the two lists
- * are the same. In other words, two lists are defined to be equal if they contain the same elements in the same
- * order. Tests elements for equality or identity as specified by <tt>testForEquality</tt>. When testing for equality,
- * two elements <tt>e1</tt> and <tt>e2</tt> are <i>equal</i> if <tt>(e1==null ? e2==null : e1.equals(e2))</tt>.)
- *
- * @param otherObj the Object to be compared for equality with the receiver.
- * @param testForEquality if true -> tests for equality, otherwise for identity.
- * @return true if the specified Object is equal to the receiver.
- */
- public boolean equals(Object otherObj, boolean testForEquality) { //delta
+ // overridden for performance only.
if (!(otherObj instanceof ObjectArrayList)) {
- return false;
+ return super.equals(otherObj);
}
if (this == otherObj) {
return true;
@@ -366,45 +194,18 @@
return false;
}
ObjectArrayList other = (ObjectArrayList) otherObj;
- if (elements == other.elements()) {
- return true;
- }
- if (size != other.size()) {
+ if (size() != other.size()) {
return false;
}
+ Object[] theElements = elements();
Object[] otherElements = other.elements();
- Object[] theElements = elements;
- if (!testForEquality) {
- for (int i = size; --i >= 0;) {
- if (theElements[i] != otherElements[i]) {
- return false;
- }
- }
- } else {
- for (int i = size; --i >= 0;) {
- if (!(theElements[i] == null ? otherElements[i] == null : theElements[i].equals(otherElements[i]))) {
- return false;
- }
+ for (int i = size(); --i >= 0;) {
+ if (theElements[i] != otherElements[i]) {
+ return false;
}
}
-
return true;
-
- }
-
- /**
- * Sets the specified range of elements in the specified array to the specified value.
- *
- * @param from the index of the first element (inclusive) to be filled with the specified value.
- * @param to the index of the last element (inclusive) to be filled with the specified value.
- * @param val the value to be stored in the specified elements of the receiver.
- */
- public void fillFromToWith(int from, int to, Object val) {
- checkRangeFromTo(from, to, this.size);
- for (int i = from; i <= to;) {
- setQuick(i++, val);
- }
}
/**
@@ -414,8 +215,9 @@
* continues.
* @return <tt>false</tt> if the procedure stopped before all elements where iterated over, <tt>true</tt> otherwise.
*/
- public boolean forEach(ObjectProcedure procedure) {
- Object[] theElements = elements;
+ @SuppressWarnings("unchecked")
+ public boolean forEach(ObjectProcedure<T> procedure) {
+ T[] theElements = (T[]) elements;
int theSize = size;
for (int i = 0; i < theSize;) {
@@ -432,11 +234,13 @@
* @param index index of element to return.
* @throws IndexOutOfBoundsException index is out of range (index < 0 || index >= size()).
*/
- public Object get(int index) {
+ @SuppressWarnings("unchecked")
+ public T get(int index) {
+ // overridden for performance only.
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
- return elements[index];
+ return (T) elements[index];
}
/**
@@ -447,202 +251,70 @@
*
* @param index index of element to return.
*/
- public Object getQuick(int index) {
- return elements[index];
+ @SuppressWarnings("unchecked")
+ public T getQuick(int index) {
+ return (T) elements[index];
}
/**
* Returns the index of the first occurrence of the specified element. Returns <code>-1</code> if the receiver does
- * not contain this element.
+ * not contain this element. Searches between <code>from</code>, inclusive and <code>to</code>, inclusive. Tests for
+ * identity.
*
- * Tests for equality or identity as specified by testForEquality.
- *
- * @param testForEquality if <code>true</code> -> test for equality, otherwise for identity.
- * @return the index of the first occurrence of the element in the receiver; returns <code>-1</code> if the element is
- * not found.
- */
- public int indexOf(Object element, boolean testForEquality) {
- return this.indexOfFromTo(element, 0, size - 1, testForEquality);
- }
-
- /**
- * Returns the index of the first occurrence of the specified element. Returns <code>-1</code> if the receiver does
- * not contain this element. Searches between <code>from</code>, inclusive and <code>to</code>, inclusive.
- *
- * Tests for equality or identity as specified by <code>testForEquality</code>.
- *
- * @param element element to search for.
- * @param from the leftmost search position, inclusive.
- * @param to the rightmost search position, inclusive.
- * @param testForEquality if </code>true</code> -> test for equality, otherwise for identity.
+ * @param element element to search for.
+ * @param from the leftmost search position, inclusive.
+ * @param to the rightmost search position, inclusive.
* @return the index of the first occurrence of the element in the receiver; returns <code>-1</code> if the element is
* not found.
* @throws IndexOutOfBoundsException index is out of range (<tt>size()>0 && (from<0 || from>to ||
* to>=size())</tt>).
*/
- public int indexOfFromTo(Object element, int from, int to, boolean testForEquality) {
+ public int indexOfFromTo(T element, int from, int to) {
+ // overridden for performance only.
if (size == 0) {
return -1;
}
checkRangeFromTo(from, to, size);
Object[] theElements = elements;
- if (testForEquality && element != null) {
- for (int i = from; i <= to; i++) {
- if (element.equals(theElements[i])) {
- return i;
- } //found
- }
-
- } else {
- for (int i = from; i <= to; i++) {
- if (element == theElements[i]) {
- return i;
- } //found
- }
+ for (int i = from; i <= to; i++) {
+ if (element == theElements[i]) {
+ return i;
+ } //found
}
return -1; //not found
}
/**
- * Determines whether the receiver is sorted ascending, according to the <i>natural ordering</i> of its elements. All
- * elements in this range must implement the <tt>Comparable</tt> interface. Furthermore, all elements in this range
- * must be <i>mutually comparable</i> (that is, <tt>e1.compareTo(e2)</tt> must not throw a <tt>ClassCastException</tt>
- * for any elements <tt>e1</tt> and <tt>e2</tt> in the array).<p>
- *
- * @param from the index of the first element (inclusive) to be sorted.
- * @param to the index of the last element (inclusive) to be sorted.
- * @return <tt>true</tt> if the receiver is sorted ascending, <tt>false</tt> otherwise.
- * @throws IndexOutOfBoundsException index is out of range (<tt>size()>0 && (from<0 || from>to ||
- * to>=size())</tt>).
- */
- public boolean isSortedFromTo(int from, int to) {
- if (size == 0) {
- return true;
- }
- checkRangeFromTo(from, to, size);
-
- Object[] theElements = elements;
- for (int i = from + 1; i <= to; i++) {
- if (((Comparable<Object>) theElements[i]).compareTo(theElements[i - 1]) < 0) {
- return false;
- }
- }
- return true;
- }
-
- /**
- * Returns the index of the last occurrence of the specified element. Returns <code>-1</code> if the receiver does not
- * contain this element. Tests for equality or identity as specified by <code>testForEquality</code>.
- *
- * @param element the element to be searched for.
- * @param testForEquality if <code>true</code> -> test for equality, otherwise for identity.
- * @return the index of the last occurrence of the element in the receiver; returns <code>-1</code> if the element is
- * not found.
- */
- public int lastIndexOf(Object element, boolean testForEquality) {
- return lastIndexOfFromTo(element, 0, size - 1, testForEquality);
- }
-
- /**
* Returns the index of the last occurrence of the specified element. Returns <code>-1</code> if the receiver does not
* contain this element. Searches beginning at <code>to</code>, inclusive until <code>from</code>, inclusive. Tests
- * for equality or identity as specified by <code>testForEquality</code>.
+ * for identity.
*
- * @param element element to search for.
- * @param from the leftmost search position, inclusive.
- * @param to the rightmost search position, inclusive.
- * @param testForEquality if <code>true</code> -> test for equality, otherwise for identity.
+ * @param element element to search for.
+ * @param from the leftmost search position, inclusive.
+ * @param to the rightmost search position, inclusive.
* @return the index of the last occurrence of the element in the receiver; returns <code>-1</code> if the element is
* not found.
* @throws IndexOutOfBoundsException index is out of range (<tt>size()>0 && (from<0 || from>to ||
* to>=size())</tt>).
*/
- public int lastIndexOfFromTo(Object element, int from, int to, boolean testForEquality) {
+ public int lastIndexOfFromTo(T element, int from, int to) {
+ // overridden for performance only.
if (size == 0) {
return -1;
}
checkRangeFromTo(from, to, size);
Object[] theElements = elements;
- if (testForEquality && element != null) {
- for (int i = to; i >= from; i--) {
- if (element.equals(theElements[i])) {
- return i;
- } //found
- }
-
- } else {
- for (int i = to; i >= from; i--) {
- if (element == theElements[i]) {
- return i;
- } //found
- }
+ for (int i = to; i >= from; i--) {
+ if (element == theElements[i]) {
+ return i;
+ } //found
}
return -1; //not found
}
/**
- * Sorts the specified range of the receiver into ascending order, according to the <i>natural ordering</i> of its
- * elements. All elements in this range must implement the <tt>Comparable</tt> interface. Furthermore, all elements
- * in this range must be <i>mutually comparable</i> (that is, <tt>e1.compareTo(e2)</tt> must not throw a
- * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and <tt>e2</tt> in the array).<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.
- *
- * <p><b>You should never call this method unless you are sure that this particular sorting algorithm is the right one
- * for your data set.</b> It is generally better to call <tt>sort()</tt> or <tt>sortFromTo(...)</tt> instead, because
- * those methods automatically choose the best sorting algorithm.
- *
- * @param from the index of the first element (inclusive) to be sorted.
- * @param to the index of the last element (inclusive) to be sorted.
- * @throws IndexOutOfBoundsException index is out of range (<tt>size()>0 && (from<0 || from>to ||
- * to>=size())</tt>).
- */
- @Override
- public void mergeSortFromTo(int from, int to) {
- if (size == 0) {
- return;
- }
- checkRangeFromTo(from, to, size);
- java.util.Arrays.sort(elements, from, to + 1);
- }
-
- /**
- * Sorts the receiver 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(e1, e2)</tt> must not throw a
- * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and <tt>e2</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 from the index of the first element (inclusive) to be sorted.
- * @param to the index of the last element (inclusive) to be sorted.
- * @param c the comparator to determine the order of the receiver.
- * @throws ClassCastException if the array contains elements that are not <i>mutually comparable</i> using
- * the specified comparator.
- * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
- * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or <tt>toIndex > a.length</tt>
- * @throws IndexOutOfBoundsException index is out of range (<tt>size()>0 && (from<0 || from>to ||
- * to>=size())</tt>).
- * @see Comparator
- */
- public void mergeSortFromTo(int from, int to, Comparator<Object> c) {
- if (size == 0) {
- return;
- }
- checkRangeFromTo(from, to, size);
- Arrays.sort(elements, from, to + 1, c);
- }
-
- /**
* Returns a new list of the part of the receiver between <code>from</code>, inclusive, and <code>to</code>,
* inclusive.
*
@@ -652,283 +324,23 @@
* @throws IndexOutOfBoundsException index is out of range (<tt>size()>0 && (from<0 || from>to ||
* to>=size())</tt>).
*/
- public ObjectArrayList partFromTo(int from, int to) {
+ @SuppressWarnings("unchecked")
+ public AbstractObjectList<T> partFromTo(int from, int to) {
if (size == 0) {
- return new ObjectArrayList(0);
+ return new ObjectArrayList<T>(0);
}
checkRangeFromTo(from, to, size);
Object[] part = new Object[to - from + 1];
System.arraycopy(elements, from, part, 0, to - from + 1);
- return new ObjectArrayList(part);
- }
-
- /**
- * Sorts the specified range of the receiver into ascending order, according to the <i>natural ordering</i> of its
- * elements. All elements in this range must implement the <tt>Comparable</tt> interface. Furthermore, all elements
- * in this range must be <i>mutually comparable</i> (that is, <tt>e1.compareTo(e2)</tt> must not throw a
- * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and <tt>e2</tt> in the array).<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.
- *
- * <p><b>You should never call this method unless you are sure that this particular sorting algorithm is the right one
- * for your data set.</b> It is generally better to call <tt>sort()</tt> or <tt>sortFromTo(...)</tt> instead, because
- * those methods automatically choose the best sorting algorithm.
- *
- * @param from the index of the first element (inclusive) to be sorted.
- * @param to the index of the last element (inclusive) to be sorted.
- * @throws IndexOutOfBoundsException index is out of range (<tt>size()>0 && (from<0 || from>to ||
- * to>=size())</tt>).
- */
- @Override
- public void quickSortFromTo(int from, int to) {
- if (size == 0) {
- return;
- }
- checkRangeFromTo(from, to, size);
- Sorting.quickSort(elements, from, to + 1);
- }
-
- /**
- * Sorts the receiver 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(e1, e2)</tt> must not throw a
- * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and <tt>e2</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 from the index of the first element (inclusive) to be sorted.
- * @param to the index of the last element (inclusive) to be sorted.
- * @param c the comparator to determine the order of the receiver.
- * @throws ClassCastException if the array contains elements that are not <i>mutually comparable</i> using
- * the specified comparator.
- * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
- * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or <tt>toIndex > a.length</tt>
- * @throws IndexOutOfBoundsException index is out of range (<tt>size()>0 && (from<0 || from>to ||
- * to>=size())</tt>).
- * @see Comparator
- */
- public void quickSortFromTo(int from, int to, Comparator<Object> c) {
- if (size == 0) {
- return;
- }
- checkRangeFromTo(from, to, size);
- Sorting.quickSort(elements, from, to + 1, c);
- }
-
- /**
- * Removes from the receiver all elements that are contained in the specified list. Tests for equality or identity as
- * specified by <code>testForEquality</code>.
- *
- * @param other the other list.
- * @param testForEquality if <code>true</code> -> test for equality, otherwise for identity.
- * @return <code>true</code> if the receiver changed as a result of the call.
- */
- public boolean removeAll(ObjectArrayList other, boolean testForEquality) {
- if (other.size == 0) {
- return false;
- } //nothing to do
- int limit = other.size - 1;
- int j = 0;
- Object[] theElements = elements;
- for (int i = 0; i < size; i++) {
- if (other.indexOfFromTo(theElements[i], 0, limit, testForEquality) < 0) {
- theElements[j++] = theElements[i];
- }
- }
-
- boolean modified = (j != size);
- setSize(j);
- return modified;
- }
-
- /**
- * Removes from the receiver all elements whose index is between <code>from</code>, inclusive and <code>to</code>,
- * inclusive. Shifts any succeeding elements to the left (reduces their index). This call shortens the list by
- * <tt>(to - from + 1)</tt> elements.
- *
- * @param from index of first element to be removed.
- * @param to index of last element to be removed.
- * @throws IndexOutOfBoundsException index is out of range (<tt>size()>0 && (from<0 || from>to ||
- * to>=size())</tt>).
- */
- @Override
- public void removeFromTo(int from, int to) {
- checkRangeFromTo(from, to, size);
- int numMoved = size - to - 1;
- if (numMoved >= 0) {
- System.arraycopy(elements, to + 1, elements, from, numMoved);
- fillFromToWith(from + numMoved, size - 1, null); //delta
- }
- int width = to - from + 1;
- if (width > 0) {
- size -= width;
- }
- }
-
- /**
- * Replaces a number of elements in the receiver with the same number of elements of another list. Replaces elements
- * in the receiver, between <code>from</code> (inclusive) and <code>to</code> (inclusive), with elements of
- * <code>other</code>, starting from <code>otherFrom</code> (inclusive).
- *
- * @param from the position of the first element to be replaced in the receiver
- * @param to the position of the last element to be replaced in the receiver
- * @param other list holding elements to be copied into the receiver.
- * @param otherFrom position of first element within other list to be copied.
- */
- public void replaceFromToWithFrom(int from, int to, ObjectArrayList other, int otherFrom) {
- int length = to - from + 1;
- if (length > 0) {
- checkRangeFromTo(from, to, size);
- checkRangeFromTo(otherFrom, otherFrom + length - 1, other.size);
- System.arraycopy(other.elements, otherFrom, elements, from, length);
- }
- }
-
- /**
- * Replaces the part between <code>from</code> (inclusive) and <code>to</code> (inclusive) with the other list's part
- * between <code>otherFrom</code> and <code>otherTo</code>. Powerful (and tricky) method! Both parts need not be of
- * the same size (part A can both be smaller or larger than part B). Parts may overlap. Receiver and other list may
- * (but most not) be identical. If <code>from > to</code>, then inserts other part before <code>from</code>.
- *
- * @param from the first element of the receiver (inclusive)
- * @param to the last element of the receiver (inclusive)
- * @param other the other list (may be identical with receiver)
- * @param otherFrom the first element of the other list (inclusive)
- * @param otherTo the last element of the other list (inclusive)
- *
- * <p><b>Examples:</b><pre>
- * a=[0, 1, 2, 3, 4, 5, 6, 7]
- * b=[50, 60, 70, 80, 90]
- * a.R(...)=a.replaceFromToWithFromTo(...)
- *
- * a.R(3,5,b,0,4)-->[0, 1, 2, 50, 60, 70, 80, 90,
- * 6, 7]
- * a.R(1,6,b,0,4)-->[0, 50, 60, 70, 80, 90, 7]
- * a.R(0,6,b,0,4)-->[50, 60, 70, 80, 90, 7]
- * a.R(3,5,b,1,2)-->[0, 1, 2, 60, 70, 6, 7]
- * a.R(1,6,b,1,2)-->[0, 60, 70, 7]
- * a.R(0,6,b,1,2)-->[60, 70, 7]
- * a.R(5,3,b,0,4)-->[0, 1, 2, 3, 4, 50, 60, 70,
- * 80, 90, 5, 6, 7]
- * a.R(5,0,b,0,4)-->[0, 1, 2, 3, 4, 50, 60, 70,
- * 80, 90, 5, 6, 7]
- * a.R(5,3,b,1,2)-->[0, 1, 2, 3, 4, 60, 70, 5, 6,
- * 7]
- * a.R(5,0,b,1,2)-->[0, 1, 2, 3, 4, 60, 70, 5, 6,
- * 7]
- *
- * Extreme cases:
- * a.R(5,3,b,0,0)-->[0, 1, 2, 3, 4, 50, 5, 6, 7]
- * a.R(5,3,b,4,4)-->[0, 1, 2, 3, 4, 90, 5, 6, 7]
- * a.R(3,5,a,0,1)-->[0, 1, 2, 0, 1, 6, 7]
- * a.R(3,5,a,3,5)-->[0, 1, 2, 3, 4, 5, 6, 7]
- * a.R(3,5,a,4,4)-->[0, 1, 2, 4, 6, 7]
- * a.R(5,3,a,0,4)-->[0, 1, 2, 3, 4, 0, 1, 2, 3, 4,
- * 5, 6, 7]
- * a.R(0,-1,b,0,4)-->[50, 60, 70, 80, 90, 0, 1, 2,
- * 3, 4, 5, 6, 7]
- * a.R(0,-1,a,0,4)-->[0, 1, 2, 3, 4, 0, 1, 2, 3,
- * 4, 5, 6, 7]
- * a.R(8,0,a,0,4)-->[0, 1, 2, 3, 4, 5, 6, 7, 0, 1,
- * 2, 3, 4]
- * </pre>
- */
- public void replaceFromToWithFromTo(int from, int to, ObjectArrayList other, int otherFrom, int otherTo) {
- if (otherFrom > otherTo) {
- throw new IndexOutOfBoundsException("otherFrom: " + otherFrom + ", otherTo: " + otherTo);
- }
- if (this == other && to - from != otherTo - otherFrom) { // avoid stumbling over my own feet
- replaceFromToWithFromTo(from, to, partFromTo(otherFrom, otherTo), 0, otherTo - otherFrom);
- return;
- }
-
- int length = otherTo - otherFrom + 1;
- int diff = length;
- int theLast = from - 1;
-
- //log.info("from="+from);
- //log.info("to="+to);
- //log.info("diff="+diff);
-
- if (to >= from) {
- diff -= (to - from + 1);
- theLast = to;
- }
-
- if (diff > 0) {
- beforeInsertDummies(theLast + 1, diff);
- } else {
- if (diff < 0) {
- removeFromTo(theLast + diff, theLast - 1);
- }
- }
-
- if (length > 0) {
- System.arraycopy(other.elements, otherFrom, elements, from, length);
- }
- }
-
- /**
- * Replaces the part of the receiver starting at <code>from</code> (inclusive) with all the elements of the specified
- * collection. Does not alter the size of the receiver. Replaces exactly <tt>Math.max(0,Math.min(size()-from,
- * other.size()))</tt> elements.
- *
- * @param from the index at which to copy the first element from the specified collection.
- * @param other Collection to replace part of the receiver
- * @throws IndexOutOfBoundsException index is out of range (index < 0 || index >= size()).
- */
- @Override
- public void replaceFromWith(int from, Collection<Object[]> other) {
- checkRange(from, size);
- Iterator<Object[]> e = other.iterator();
- int index = from;
- int limit = Math.min(size - from, other.size());
- for (int i = 0; i < limit; i++) {
- elements[index++] = e.next();
- } //delta
- }
-
- /**
- * Retains (keeps) only the elements in the receiver that are contained in the specified other list. In other words,
- * removes from the receiver all of its elements that are not contained in the specified other list. Tests for
- * equality or identity as specified by <code>testForEquality</code>.
- *
- * @param other the other list to test against.
- * @param testForEquality if <code>true</code> -> test for equality, otherwise for identity.
- * @return <code>true</code> if the receiver changed as a result of the call.
- */
- public boolean retainAll(ObjectArrayList other, boolean testForEquality) {
- if (other.size == 0) {
- if (size == 0) {
- return false;
- }
- setSize(0);
- return true;
- }
-
- int limit = other.size - 1;
- int j = 0;
- Object[] theElements = elements;
-
- for (int i = 0; i < size; i++) {
- if (other.indexOfFromTo(theElements[i], 0, limit, testForEquality) >= 0) {
- theElements[j++] = theElements[i];
- }
- }
-
- boolean modified = (j != size);
- setSize(j);
- return modified;
+ return new ObjectArrayList<T>((T[]) part);
}
/** Reverses the elements of the receiver. Last becomes first, second last becomes second first, and so on. */
@Override
public void reverse() {
+ // overridden for performance only.
int limit = size / 2;
int j = size - 1;
@@ -947,7 +359,8 @@
* @param element element to be stored at the specified position.
* @throws IndexOutOfBoundsException index is out of range (index < 0 || index >= size()).
*/
- public void set(int index, Object element) {
+ public void set(int index, T element) {
+ // overridden for performance only.
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
@@ -963,7 +376,7 @@
* @param index index of element to replace.
* @param element element to be stored at the specified position.
*/
- public void setQuick(int index, Object element) {
+ public void setQuick(int index, T element) {
elements[index] = element;
}
@@ -977,6 +390,7 @@
*/
@Override
public void shuffleFromTo(int from, int to) {
+ // overridden for performance only.
if (size == 0) {
return;
}
@@ -993,79 +407,45 @@
theElements[i] = tmpElement;
}
}
-
- /** Returns the number of elements contained in the receiver. */
- @Override
- public int size() {
- return size;
- }
+
+
/**
- * Returns a list which is a concatenation of <code>times</code> times the receiver.
- *
- * @param times the number of times the receiver shall be copied.
+ * Trims the capacity of the receiver to be the receiver's current size. Releases any superfluous internal memory. An
+ * application can use this operation to minimize the storage of the receiver.
*/
- public ObjectArrayList times(int times) {
- ObjectArrayList newList = new ObjectArrayList(times * size);
- for (int i = times; --i >= 0;) {
- newList.addAllOfFromTo(this, 0, size() - 1);
- }
- return newList;
+ @Override
+ public void trimToSize() {
+ elements = org.apache.mahout.math.Arrays.trimToCapacity(elements, size());
}
- /**
- * Returns an array containing all of the elements in the receiver in the correct order. The runtime type of the
- * returned array is that of the specified array. If the receiver fits in the specified array, it is returned
- * therein. Otherwise, a new array is allocated with the runtime type of the specified array and the size of the
- * receiver. <p> If the receiver fits in the specified array with room to spare (i.e., the array has more elements
- * than the receiver), the element in the array immediately following the end of the receiver is set to null. This is
- * useful in determining the length of the receiver <em>only</em> if the caller knows that the receiver does not
- * contain any null elements.
- *
- * @param array the array into which the elements of the receiver are to be stored, if it is big enough; otherwise, a
- * new array of the same runtime type is allocated for this purpose.
- * @return an array containing the elements of the receiver.
- * @throws ArrayStoreException the runtime type of <tt>array</tt> is not a supertype of the runtime type of every
- * element in the receiver.
- */
- public Object[] toArray(Object[] array) {
- if (array.length < size) {
- array = (Object[]) java.lang.reflect.Array.newInstance(array.getClass().getComponentType(), size);
- }
-
- Object[] theElements = elements;
- for (int i = size; --i >= 0;) {
- array[i] = theElements[i];
- }
+ @Override
+ public void removeFromTo(int fromIndex, int toIndex) {
+ throw new UnsupportedOperationException();
+ }
- if (array.length > size) {
- array[size] = null;
- }
+ @Override
+ public void replaceFromWith(int from, Collection<T> other) {
+ throw new UnsupportedOperationException();
+ }
- return array;
+ @Override
+ protected void beforeInsertDummies(int index, int length) {
+ throw new UnsupportedOperationException();
}
- /** Returns a <code>ArrayList</code> containing all the elements in the receiver. */
@Override
- public List<Object[]> toList() {
- int mySize = size();
- Object[] theElements = elements;
- List<Object[]> list = new ArrayList<Object[]>(mySize);
- list.addAll(Arrays.<Object[]>asList(theElements).subList(0, mySize));
- return list;
+ public void mergeSortFromTo(int from, int to) {
+ throw new UnsupportedOperationException();
}
- /** Returns a string representation of the receiver, containing the String representation of each element. */
- public String toString() {
- return org.apache.mahout.math.Arrays.toString(partFromTo(0, size() - 1).elements());
+ @Override
+ public void quickSortFromTo(int from, int to) {
+ throw new UnsupportedOperationException();
}
- /**
- * Trims the capacity of the receiver to be the receiver's current size. Releases any superfluos internal memory. An
- * application can use this operation to minimize the storage of the receiver.
- */
@Override
- public void trimToSize() {
- elements = org.apache.mahout.math.Arrays.trimToCapacity(elements, size());
+ public int size() {
+ return size;
}
}
Modified: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/list/SimpleLongArrayList.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/list/SimpleLongArrayList.java?rev=894251&r1=894250&r2=894251&view=diff
==============================================================================
--- lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/list/SimpleLongArrayList.java (original)
+++ lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/list/SimpleLongArrayList.java Mon Dec 28 21:30:05 2009
@@ -10,11 +10,7 @@
/**
Resizable list holding <code>long</code> elements; implemented with arrays; not efficient; just to demonstrate which methods you must override to implement a fully functional list.
- First see the <a href="package-summary.html">package summary</a> and javadoc <a href="package-tree.html">tree view</a> to get the broad picture.
*/
-
-/** @deprecated until unit tests are in place. Until this time, this class/interface is unsupported. */
-@Deprecated
public class SimpleLongArrayList extends AbstractLongList {
/**
@@ -23,9 +19,6 @@
*/
private long[] elements;
- /** The size of the list. */
- private int size;
-
/** Constructs an empty list. */
public SimpleLongArrayList() {
this(10);
Modified: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/map/OpenIntObjectHashMap.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/map/OpenIntObjectHashMap.java?rev=894251&r1=894250&r2=894251&view=diff
==============================================================================
--- lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/map/OpenIntObjectHashMap.java (original)
+++ lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/map/OpenIntObjectHashMap.java Mon Dec 28 21:30:05 2009
@@ -8,6 +8,8 @@
*/
package org.apache.mahout.math.map;
+import java.util.Arrays;
+
import org.apache.mahout.math.function.IntObjectProcedure;
import org.apache.mahout.math.function.IntProcedure;
import org.apache.mahout.math.list.ByteArrayList;
@@ -68,7 +70,7 @@
@Override
public void clear() {
new ByteArrayList(this.state).fillFromToWith(0, this.state.length - 1, FREE);
- new ObjectArrayList(values).fillFromToWith(0, state.length - 1, null); // delta
+ Arrays.fill(values, 0, state.length - 1, null); // delta
this.distinct = 0;
this.freeEntries = table.length; // delta
Modified: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/map/OpenLongObjectHashMap.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/map/OpenLongObjectHashMap.java?rev=894251&r1=894250&r2=894251&view=diff
==============================================================================
--- lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/map/OpenLongObjectHashMap.java (original)
+++ lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/map/OpenLongObjectHashMap.java Mon Dec 28 21:30:05 2009
@@ -8,6 +8,8 @@
*/
package org.apache.mahout.math.map;
+import java.util.Arrays;
+
import org.apache.mahout.math.function.LongObjectProcedure;
import org.apache.mahout.math.function.LongProcedure;
import org.apache.mahout.math.list.ByteArrayList;
@@ -68,7 +70,7 @@
@Override
public void clear() {
new ByteArrayList(this.state).fillFromToWith(0, this.state.length - 1, FREE);
- new ObjectArrayList(values).fillFromToWith(0, state.length - 1, null); // delta
+ Arrays.fill(values, 0, state.length - 1, null); // delta
this.distinct = 0;
this.freeEntries = table.length; // delta
Added: lucene/mahout/trunk/math/src/test/java-templates/org/apache/mahout/math/list/ValueTypeArrayListTest.java.t
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/test/java-templates/org/apache/mahout/math/list/ValueTypeArrayListTest.java.t?rev=894251&view=auto
==============================================================================
--- lucene/mahout/trunk/math/src/test/java-templates/org/apache/mahout/math/list/ValueTypeArrayListTest.java.t (added)
+++ lucene/mahout/trunk/math/src/test/java-templates/org/apache/mahout/math/list/ValueTypeArrayListTest.java.t Mon Dec 28 21:30:05 2009
@@ -0,0 +1,237 @@
+/**
+ * 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.list;
+
+import org.apache.mahout.math.function.${valueTypeCap}Procedure;
+import org.junit.Assert;
+import org.junit.Before;
+import org.junit.Test;
+
+#if ($valueTypeFloating == 'true')
+ #set ($assertEpsilon=', 0001')
+#else
+ #set ($assertEpsilon='')
+#end
+
+public class ${valueTypeCap}ArrayListTest extends Assert {
+
+ private ${valueTypeCap}ArrayList emptyList;
+ private ${valueTypeCap}ArrayList listOfFive;
+
+ @Before
+ public void before() {
+ emptyList = new ${valueTypeCap}ArrayList();
+ listOfFive = new ${valueTypeCap}ArrayList();
+ for (int x = 0; x < 5; x ++) {
+ listOfFive.add((${valueType})x);
+ }
+ }
+
+
+ @Test(expected = IndexOutOfBoundsException.class)
+ public void testGetEmpty() {
+ emptyList.get(0);
+ }
+
+ @Test(expected = IndexOutOfBoundsException.class)
+ public void setEmpty() {
+ emptyList.set(1, (${valueType})1);
+ }
+
+ @Test(expected = IndexOutOfBoundsException.class)
+ public void beforeInsertInvalidRange() {
+ emptyList.beforeInsert(1, (${valueType})0);
+ }
+
+ @Test
+ public void testAdd() {
+ emptyList.add((${valueType})12);
+ assertEquals(1, emptyList.size());
+ for (int x = 0; x < 1000; x ++) {
+ emptyList.add((${valueType})(x % ${valueObjectType}.MAX_VALUE));
+ }
+ assertEquals(1001, emptyList.size());
+ assertEquals(12, emptyList.get(0) $assertEpsilon);
+ for (int x = 0; x < 1000; x ++) {
+ assertEquals((${valueType})(x % ${valueObjectType}.MAX_VALUE), emptyList.get(x+1) $assertEpsilon);
+ }
+ }
+
+ @Test
+ public void testBinarySearch()
+ {
+ int x = listOfFive.binarySearchFromTo((${valueType})0, 2, 4);
+ assertEquals(-3, x);
+ x = listOfFive.binarySearchFromTo((${valueType})1, 0, 4);
+ assertEquals(1, x);
+ }
+
+ @Test
+ public void testClone() {
+ ${valueTypeCap}ArrayList l2 = listOfFive.copy(); // copy just calls clone.
+ assertNotSame(listOfFive, l2);
+ assertEquals(listOfFive, l2);
+ }
+
+ @Test
+ public void testElements() {
+ ${valueType}[] l = new ${valueType}[] { 12, 24, 36, 48 };
+ ${valueTypeCap}ArrayList lar = new ${valueTypeCap}ArrayList(l);
+ assertEquals(4, lar.size());
+ assertSame(l, lar.elements());
+ ${valueType}[] l2 = new ${valueType}[] { 3, 6, 9, 12 };
+ lar.elements(l2);
+ assertSame(l2, lar.elements());
+ }
+
+ @Test
+ public void testEquals() {
+ ${valueType}[] l = new ${valueType}[] { 12, 24, 36, 48 };
+ ${valueTypeCap}ArrayList lar = new ${valueTypeCap}ArrayList(l);
+ ${valueTypeCap}ArrayList lar2 = new ${valueTypeCap}ArrayList();
+ for (int x = 0; x < lar.size(); x++) {
+ lar2.add(lar.get(x));
+ }
+ assertEquals(lar, lar2);
+ assertFalse(lar.equals(this));
+ lar2.add((${valueType})55);
+ assertFalse(lar.equals(lar2));
+ }
+
+ @Test
+ public void testForEach() {
+ listOfFive.forEach(new ${valueTypeCap}Procedure() {
+ int count;
+ @Override
+ public boolean apply(${valueType} element) {
+ assertFalse(count > 2);
+ count ++;
+ return element != 1;
+ }});
+ }
+
+ @Test
+ public void testGetQuick() {
+ ${valueTypeCap}ArrayList lar = new ${valueTypeCap}ArrayList(10);
+ lar.getQuick(1); // inside capacity, outside size.
+ }
+
+ @Test
+ public void testIndexOfFromTo() {
+ int x = listOfFive.indexOfFromTo((${valueType})0, 2, 4);
+ assertEquals(-1, x);
+ x = listOfFive.indexOfFromTo((${valueType})1, 0, 4);
+ assertEquals(1, x);
+ }
+
+ @Test
+ public void testLastIndexOfFromTo() {
+ ${valueTypeCap}ArrayList lar = new ${valueTypeCap}ArrayList(10);
+ lar.add((${valueType})1);
+ lar.add((${valueType})2);
+ lar.add((${valueType})3);
+ lar.add((${valueType})2);
+ lar.add((${valueType})1);
+ assertEquals(3, lar.lastIndexOf((${valueType})2));
+ assertEquals(3, lar.lastIndexOfFromTo((${valueType})2, 2, 4));
+ assertEquals(-1, lar.lastIndexOf((${valueType})111));
+ }
+
+ @Test
+ public void testPartFromTo() {
+ Abstract${valueTypeCap}List al = listOfFive.partFromTo(1, 2);
+ assertEquals(2, al.size());
+ assertEquals(1, al.get(0) $assertEpsilon);
+ assertEquals(2, al.get(1) $assertEpsilon);
+ }
+
+ @Test(expected = IndexOutOfBoundsException.class)
+ public void testPartFromToOOB() {
+ listOfFive.partFromTo(10, 11);
+ }
+
+ @Test
+ public void testRemoveAll() {
+ ${valueTypeCap}ArrayList lar = new ${valueTypeCap}ArrayList(1000);
+ for (int x = 0; x < 128; x ++) {
+ lar.add((${valueType})x);
+ }
+ ${valueTypeCap}ArrayList larOdd = new ${valueTypeCap}ArrayList(500);
+ for (int x = 1; x < 128; x = x + 2) {
+ larOdd.add((${valueType})x);
+ }
+ lar.removeAll(larOdd);
+ assertEquals(64, lar.size());
+
+ for (int x = 0; x < lar.size(); x++) {
+ assertEquals(x*2, lar.get(x) $assertEpsilon);
+ }
+ }
+
+ @Test
+ public void testReplaceFromToWith() {
+ listOfFive.add((${valueType})5);
+ ${valueTypeCap}ArrayList lar = new ${valueTypeCap}ArrayList();
+ lar.add((${valueType})44);
+ lar.add((${valueType})55);
+ listOfFive.replaceFromToWithFromTo(2, 3, lar, 0, 1);
+ assertEquals(0, listOfFive.get(0) $assertEpsilon);
+ assertEquals(1, listOfFive.get(1) $assertEpsilon);
+ assertEquals(44, listOfFive.get(2) $assertEpsilon);
+ assertEquals(55, listOfFive.get(3) $assertEpsilon);
+ assertEquals(4, listOfFive.get(4) $assertEpsilon);
+ assertEquals(5, listOfFive.get(5) $assertEpsilon);
+ }
+
+ @Test
+ public void testRetainAllSmall() {
+ ${valueTypeCap}ArrayList lar = new ${valueTypeCap}ArrayList();
+ lar.addAllOf(listOfFive);
+ lar.addAllOf(listOfFive);
+ lar.addAllOf(listOfFive);
+ ${valueTypeCap}ArrayList lar2 = new ${valueTypeCap}ArrayList();
+ lar2.add((${valueType})3);
+ lar2.add((${valueType})4);
+ assertTrue(lar.retainAll(lar2));
+ for(int x = 0; x < lar.size(); x ++) {
+ ${valueType} l = lar.get(x);
+ assertTrue(l == 3 || l == 4);
+ }
+ assertEquals(6, lar.size());
+ }
+
+ @Test
+ public void testRetainAllSmaller() {
+ ${valueTypeCap}ArrayList lar = new ${valueTypeCap}ArrayList();
+ lar.addAllOf(listOfFive);
+ ${valueTypeCap}ArrayList lar2 = new ${valueTypeCap}ArrayList();
+ // large 'other' arg to take the other code path.
+ for (int x = 0; x < 1000; x ++) {
+ lar2.add((${valueType})3);
+ lar2.add((${valueType})4);
+ }
+ assertTrue(lar.retainAll(lar2));
+ for(int x = 0; x < lar.size(); x ++) {
+ ${valueType} l = lar.get(x);
+ assertTrue(l == 3 || l == 4);
+ }
+ }
+
+}
Added: 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=894251&view=auto
==============================================================================
--- lucene/mahout/trunk/math/src/test/java/org/apache/mahout/math/SortingTest.java (added)
+++ lucene/mahout/trunk/math/src/test/java/org/apache/mahout/math/SortingTest.java Mon Dec 28 21:30:05 2009
@@ -0,0 +1,666 @@
+/**
+ * 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.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.List;
+import java.util.Random;
+
+import org.apache.mahout.math.function.ByteComparator;
+import org.apache.mahout.math.function.CharComparator;
+import org.apache.mahout.math.function.DoubleComparator;
+import org.apache.mahout.math.function.FloatComparator;
+import org.apache.mahout.math.function.IntComparator;
+import org.apache.mahout.math.function.LongComparator;
+import org.apache.mahout.math.function.ShortComparator;
+import org.junit.Assert;
+import org.junit.Before;
+import org.junit.Test;
+
+public class SortingTest extends Assert {
+
+ private Random random;
+
+ private byte[] randomBytes() {
+ byte[] bytes = new byte[1000];
+ random.nextBytes(bytes);
+ return bytes;
+ }
+
+ private char[] randomChars() {
+ char[] chars = new char[100000];
+ for (int x = 0; x < 100000; x ++) {
+ chars[x] = (char)(random.nextInt() % Character.MAX_VALUE);
+ }
+ return chars;
+ }
+
+ private int[] randomInts() {
+ int[] ints = new int[100000];
+ for (int x = 0; x < 100000; x ++) {
+ ints[x] = random.nextInt();
+ }
+ return ints;
+ }
+
+ private short[] randomShorts() {
+ short[] shorts = new short[100000];
+ for (int x = 0; x < 100000; x ++) {
+ shorts[x] = (short)(random.nextInt() % Short.MAX_VALUE);
+ }
+ return shorts;
+ }
+
+ private long[] randomLongs() {
+ long[] longs = new long[100000];
+ for (int x = 0; x < 100000; x ++) {
+ longs[x] = random.nextLong();
+ }
+ return longs;
+ }
+
+ private float[] randomFloats() {
+ float[] floats = new float[100000];
+ for (int x = 0; x < 100000; x ++) {
+ floats[x] = random.nextFloat();
+ }
+ return floats;
+ }
+
+ private double[] randomDoubles() {
+ double[] doubles = new double[100000];
+ for (int x = 0; x < 100000; x ++) {
+ doubles[x] = random.nextDouble();
+ }
+ return doubles;
+ }
+
+ @Before
+ public void before() {
+ random = new Random();
+ }
+
+ static class ForSorting implements Comparable<ForSorting> {
+ private Integer i;
+
+ ForSorting(int i) {
+ this.i = Integer.valueOf(i);
+ }
+
+ @Override
+ public int compareTo(ForSorting o) {
+ return i.compareTo(o.i);
+ }
+
+ @Override
+ public String toString() {
+ return i.toString();
+ }
+ }
+
+ static class ReverseCompareForSorting implements Comparator<ForSorting> {
+
+ @Override
+ public int compare(ForSorting o1, ForSorting o2) {
+ return o2.compareTo(o1);
+ }
+ }
+
+ @Test
+ public void testBinarySearch() {
+ byte[] bytes = new byte[] {-5, -2, 0, 100, 103};
+ int x = Sorting.binarySearchFromTo(bytes, (byte) -6, 0, 4);
+ assertEquals(-1, x);
+ x = Sorting.binarySearchFromTo(bytes, (byte) 0, 0, 4);
+ assertEquals(2, x);
+ x = Sorting.binarySearchFromTo(bytes, (byte) 5, 0, 4);
+ assertEquals(-4, x);
+ x = Sorting.binarySearchFromTo(bytes, (byte) 0, 3, 4);
+ assertEquals(-4, x);
+
+ char[] chars = new char[] {1, 2, 5, 100, 103};
+ x = Sorting.binarySearchFromTo(chars, (char) 0, 0, 4);
+ assertEquals(-1, x);
+ x = Sorting.binarySearchFromTo(chars, (char) 1, 0, 4);
+ assertEquals(0, x);
+ x = Sorting.binarySearchFromTo(chars, (char) 6, 0, 4);
+ assertEquals(-4, x);
+ x = Sorting.binarySearchFromTo(chars, (char) 0, 3, 4);
+ assertEquals(-4, x);
+
+ short[] shorts = new short[] {-5, -2, 0, 100, 103};
+ x = Sorting.binarySearchFromTo(shorts, (short) -6, 0, 4);
+ assertEquals(-1, x);
+ x = Sorting.binarySearchFromTo(shorts, (short) 0, 0, 4);
+ assertEquals(2, x);
+ x = Sorting.binarySearchFromTo(shorts, (short) 5, 0, 4);
+ assertEquals(-4, x);
+ x = Sorting.binarySearchFromTo(shorts, (short) 0, 3, 4);
+ assertEquals(-4, x);
+
+ int[] ints = new int[] {-5, -2, 0, 100, 103};
+ x = Sorting.binarySearchFromTo(ints, (int) -6, 0, 4);
+ assertEquals(-1, x);
+ x = Sorting.binarySearchFromTo(ints, (int) 0, 0, 4);
+ assertEquals(2, x);
+ x = Sorting.binarySearchFromTo(ints, (int) 5, 0, 4);
+ assertEquals(-4, x);
+ x = Sorting.binarySearchFromTo(ints, (int) 0, 3, 4);
+ assertEquals(-4, x);
+
+ long[] longs = new long[] {-5, -2, 0, 100, 103};
+ x = Sorting.binarySearchFromTo(longs, (long) -6, 0, 4);
+ assertEquals(-1, x);
+ x = Sorting.binarySearchFromTo(longs, (long) 0, 0, 4);
+ assertEquals(2, x);
+ x = Sorting.binarySearchFromTo(longs, (long) 5, 0, 4);
+ assertEquals(-4, x);
+ x = Sorting.binarySearchFromTo(longs, (long) 0, 3, 4);
+ assertEquals(-4, x);
+
+ float[] floats = new float[] {-5, -2, 0, 100, 103};
+ x = Sorting.binarySearchFromTo(floats, (float) -6, 0, 4);
+ assertEquals(-1, x);
+ x = Sorting.binarySearchFromTo(floats, (float) 0, 0, 4);
+ assertEquals(2, x);
+ x = Sorting.binarySearchFromTo(floats, (float) 5, 0, 4);
+ assertEquals(-4, x);
+ x = Sorting.binarySearchFromTo(floats, (float) 0, 3, 4);
+ assertEquals(-4, x);
+
+ double[] doubles = new double[] {-5, -2, 0, 100, 103};
+ x = Sorting.binarySearchFromTo(doubles, (double) -6, 0, 4);
+ assertEquals(-1, x);
+ x = Sorting.binarySearchFromTo(doubles, (double) 0, 0, 4);
+ assertEquals(2, x);
+ x = Sorting.binarySearchFromTo(doubles, (double) 5, 0, 4);
+ assertEquals(-4, x);
+ x = Sorting.binarySearchFromTo(doubles, (double) 0, 3, 4);
+ assertEquals(-4, x);
+ }
+
+ @Test
+ public void testBinarySearchObjects() {
+ List<ForSorting> refList = new ArrayList<ForSorting>();
+ refList.add(new ForSorting(-5));
+ refList.add(new ForSorting(-2));
+ refList.add(new ForSorting(0));
+ refList.add(new ForSorting(100));
+ refList.add(new ForSorting(103));
+ // the compare function is reversed
+ Collections.reverse(refList);
+ ForSorting[] bsArray = refList.toArray(new ForSorting[5]);
+
+ Comparator<ForSorting> comp = new ReverseCompareForSorting();
+
+ int x = Sorting.binarySearchFromTo(bsArray, new ForSorting(-6), 0, 4, comp);
+ assertEquals(-6, x);
+ x = Sorting.binarySearchFromTo(bsArray, new ForSorting(0), 0, 4, comp);
+ assertEquals(2, x);
+ x = Sorting.binarySearchFromTo(bsArray, new ForSorting(5), 0, 4, comp);
+ assertEquals(-3, x);
+ x = Sorting.binarySearchFromTo(bsArray, new ForSorting(0), 3, 4, comp);
+ assertEquals(-4, x);
+ }
+
+ @Test
+ public void testQuickSortBytes() {
+
+ ByteComparator revComp = new ByteComparator() {
+
+ @Override
+ public int compare(byte o1, byte o2) {
+ if (o2 < o1) {
+ return -1;
+ }
+ if (o2 > o1) {
+ return 1;
+ }
+ return 0;
+ }
+ };
+
+ byte[] stuff = randomBytes();
+ Sorting.quickSort(stuff, 0, stuff.length, revComp);
+ for (int x = 0; x < (stuff.length - 1); x++) {
+ assertTrue(stuff[x] >= stuff[x + 1]);
+ }
+ stuff = randomBytes();
+ Sorting.quickSort(stuff, 100, stuff.length, revComp);
+ for (int x = 100; x < (stuff.length - 1); x++) {
+ assertTrue(stuff[x] >= stuff[x + 1]);
+ }
+ }
+
+ @Test
+ public void testQuickSortChars() {
+ char[] stuff = randomChars();
+ CharComparator revComp = new CharComparator() {
+
+ @Override
+ public int compare(char o1, char o2) {
+ if (o2 < o1) {
+ return -1;
+ }
+ if (o2 > o1) {
+ return 1;
+ }
+ return 0;
+ }
+ };
+
+ stuff = randomChars();
+ Sorting.quickSort(stuff, 0, stuff.length, revComp);
+ for (int x = 0; x < (stuff.length - 1); x++) {
+ assertTrue(stuff[x] >= stuff[x + 1]);
+ }
+ stuff = randomChars();
+ Sorting.quickSort(stuff, 100, stuff.length, revComp);
+ for (int x = 100; x < (stuff.length - 1); x++) {
+ assertTrue(stuff[x] >= stuff[x + 1]);
+ }
+ }
+
+ @Test
+ public void testQuickSortInts() {
+
+ IntComparator revComp = new IntComparator() {
+
+ @Override
+ public int compare(int o1, int o2) {
+ if (o2 < o1) {
+ return -1;
+ }
+ if (o2 > o1) {
+ return 1;
+ }
+ return 0;
+ }
+ };
+
+ int[] stuff = randomInts();
+ Sorting.quickSort(stuff, 0, stuff.length, revComp);
+ for (int x = 0; x < (stuff.length - 1); x++) {
+ assertTrue(stuff[x] >= stuff[x + 1]);
+ }
+ stuff = randomInts();
+ Sorting.quickSort(stuff, 100, stuff.length, revComp);
+ for (int x = 100; x < (stuff.length - 1); x++) {
+ assertTrue(stuff[x] >= stuff[x + 1]);
+ }
+ }
+
+ @Test
+ public void testQuickSortLongs() {
+
+ LongComparator revComp = new LongComparator() {
+
+ @Override
+ public int compare(long o1, long o2) {
+ if (o2 < o1) {
+ return -1;
+ }
+ if (o2 > o1) {
+ return 1;
+ }
+ return 0;
+ }
+ };
+
+ long[] stuff = randomLongs();
+ Sorting.quickSort(stuff, 0, stuff.length, revComp);
+ for (int x = 0; x < (stuff.length - 1); x++) {
+ assertTrue(stuff[x] >= stuff[x + 1]);
+ }
+ }
+
+ @Test
+ public void testQuickSortShorts() {
+ ShortComparator revComp = new ShortComparator() {
+
+ @Override
+ public int compare(short o1, short o2) {
+ if (o2 < o1) {
+ return -1;
+ }
+ if (o2 > o1) {
+ return 1;
+ }
+ return 0;
+ }
+ };
+
+ short[] stuff = randomShorts();
+ Sorting.quickSort(stuff, 0, stuff.length, revComp);
+ for (int x = 0; x < (stuff.length - 1); x++) {
+ assertTrue(stuff[x] >= stuff[x + 1]);
+ }
+ stuff = randomShorts();
+ Sorting.quickSort(stuff, 100, stuff.length, revComp);
+ for (int x = 100; x < (stuff.length - 1); x++) {
+ assertTrue(stuff[x] >= stuff[x + 1]);
+ }
+ }
+
+ @Test
+ public void testQuickSortFloats() {
+ FloatComparator revComp = new FloatComparator() {
+
+ @Override
+ public int compare(float o1, float o2) {
+ if (o2 < o1) {
+ return -1;
+ }
+ if (o2 > o1) {
+ return 1;
+ }
+ return 0;
+ }
+ };
+
+ float[] stuff = randomFloats();
+ Sorting.quickSort(stuff, 0, stuff.length, revComp);
+ for (int x = 0; x < (stuff.length - 1); x++) {
+ assertTrue(stuff[x] >= stuff[x + 1]);
+ }
+ stuff = randomFloats();
+ Sorting.quickSort(stuff, 100, stuff.length, revComp);
+ for (int x = 100; x < (stuff.length - 1); x++) {
+ assertTrue(stuff[x] >= stuff[x + 1]);
+ }
+ }
+
+ @Test
+ public void testQuickSortDoubles() {
+ DoubleComparator revComp = new DoubleComparator() {
+
+ @Override
+ public int compare(double o1, double o2) {
+ if (o2 < o1) {
+ return -1;
+ }
+ if (o2 > o1) {
+ return 1;
+ }
+ return 0;
+ }
+ };
+
+ double[] stuff = randomDoubles();
+ Sorting.quickSort(stuff, 0, stuff.length, revComp);
+ for (int x = 0; x < (stuff.length - 1); x++) {
+ assertTrue(stuff[x] >= stuff[x + 1]);
+ }
+ stuff = randomDoubles();
+ Sorting.quickSort(stuff, 100, stuff.length, revComp);
+ for (int x = 100; x < (stuff.length - 1); x++) {
+ assertTrue(stuff[x] >= stuff[x + 1]);
+ }
+ }
+
+ @Test
+ public void testMergeSortBytes() {
+ byte[] stuff = randomBytes();
+ Sorting.mergeSort(stuff, 0, stuff.length);
+ for (int x = 0; x < (stuff.length - 1); x++) {
+ assertTrue(stuff[x] <= stuff[x + 1]);
+ }
+
+ stuff = randomBytes();
+ Sorting.mergeSort(stuff, 100, stuff.length);
+ for (int x = 100; x < (stuff.length - 1); x++) {
+ assertTrue(stuff[x] <= stuff[x + 1]);
+ }
+
+ ByteComparator revComp = new ByteComparator() {
+
+ @Override
+ public int compare(byte o1, byte o2) {
+ if (o2 < o1) {
+ return -1;
+ }
+ if (o2 > o1) {
+ return 1;
+ }
+ return 0;
+ }
+ };
+
+ stuff = randomBytes();
+ Sorting.mergeSort(stuff, 0, stuff.length, revComp);
+ for (int x = 0; x < (stuff.length - 1); x++) {
+ assertTrue(stuff[x] >= stuff[x + 1]);
+ }
+ }
+
+ @Test
+ public void testMergeSortChars() {
+ char[] stuff = randomChars();
+ Sorting.mergeSort(stuff, 0, stuff.length);
+ for (int x = 0; x < (stuff.length - 1); x++) {
+ assertTrue(stuff[x] <= stuff[x + 1]);
+ }
+
+ stuff = randomChars();
+ Sorting.mergeSort(stuff, 100, stuff.length);
+ for (int x = 100; x < (stuff.length - 1); x++) {
+ assertTrue(stuff[x] <= stuff[x + 1]);
+ }
+
+ CharComparator revComp = new CharComparator() {
+
+ @Override
+ public int compare(char o1, char o2) {
+ if (o2 < o1) {
+ return -1;
+ }
+ if (o2 > o1) {
+ return 1;
+ }
+ return 0;
+ }
+ };
+
+ stuff = randomChars();
+ Sorting.mergeSort(stuff, 0, stuff.length, revComp);
+ for (int x = 0; x < (stuff.length - 1); x++) {
+ assertTrue(stuff[x] >= stuff[x + 1]);
+ }
+ }
+
+ @Test
+ public void testMergeSortInts() {
+ int[] stuff = randomInts();
+ Sorting.mergeSort(stuff, 0, stuff.length);
+ for (int x = 0; x < (stuff.length - 1); x++) {
+ assertTrue(stuff[x] <= stuff[x + 1]);
+ }
+
+ stuff = randomInts();
+ Sorting.mergeSort(stuff, 100, stuff.length);
+ for (int x = 100; x < (stuff.length - 1); x++) {
+ assertTrue(stuff[x] <= stuff[x + 1]);
+ }
+
+ IntComparator revComp = new IntComparator() {
+
+ @Override
+ public int compare(int o1, int o2) {
+ if (o2 < o1) {
+ return -1;
+ }
+ if (o2 > o1) {
+ return 1;
+ }
+ return 0;
+ }
+ };
+
+ stuff = randomInts();
+ Sorting.mergeSort(stuff, 0, stuff.length, revComp);
+ for (int x = 0; x < (stuff.length - 1); x++) {
+ assertTrue(stuff[x] >= stuff[x + 1]);
+ }
+ }
+
+ @Test
+ public void testMergeSortLongs() {
+ long[] stuff = randomLongs();
+ Sorting.mergeSort(stuff, 0, stuff.length);
+ for (int x = 0; x < (stuff.length - 1); x++) {
+ assertTrue(stuff[x] <= stuff[x + 1]);
+ }
+
+ stuff = randomLongs();
+ Sorting.mergeSort(stuff, 100, stuff.length);
+ for (int x = 100; x < (stuff.length - 1); x++) {
+ assertTrue(stuff[x] <= stuff[x + 1]);
+ }
+
+ LongComparator revComp = new LongComparator() {
+
+ @Override
+ public int compare(long o1, long o2) {
+ if (o2 < o1) {
+ return -1;
+ }
+ if (o2 > o1) {
+ return 1;
+ }
+ return 0;
+ }
+ };
+
+ stuff = randomLongs();
+ Sorting.mergeSort(stuff, 0, stuff.length, revComp);
+ for (int x = 0; x < (stuff.length - 1); x++) {
+ assertTrue(stuff[x] >= stuff[x + 1]);
+ }
+ }
+
+ @Test
+ public void testMergeSortShorts() {
+ short[] stuff = randomShorts();
+ Sorting.mergeSort(stuff, 0, stuff.length);
+ for (int x = 0; x < (stuff.length - 1); x++) {
+ assertTrue(stuff[x] <= stuff[x + 1]);
+ }
+
+ stuff = randomShorts();
+ Sorting.mergeSort(stuff, 100, stuff.length);
+ for (int x = 100; x < (stuff.length - 1); x++) {
+ assertTrue(stuff[x] <= stuff[x + 1]);
+ }
+
+ ShortComparator revComp = new ShortComparator() {
+
+ @Override
+ public int compare(short o1, short o2) {
+ if (o2 < o1) {
+ return -1;
+ }
+ if (o2 > o1) {
+ return 1;
+ }
+ return 0;
+ }
+ };
+
+ stuff = randomShorts();
+ Sorting.mergeSort(stuff, 0, stuff.length, revComp);
+ for (int x = 0; x < (stuff.length - 1); x++) {
+ assertTrue(stuff[x] >= stuff[x + 1]);
+ }
+ }
+
+ @Test
+ public void testMergeSortFloats() {
+ float[] stuff = randomFloats();
+ Sorting.mergeSort(stuff, 0, stuff.length);
+ for (int x = 0; x < (stuff.length - 1); x++) {
+ assertTrue(stuff[x] <= stuff[x + 1]);
+ }
+
+ stuff = randomFloats();
+ Sorting.mergeSort(stuff, 100, stuff.length);
+ for (int x = 100; x < (stuff.length - 1); x++) {
+ assertTrue(stuff[x] <= stuff[x + 1]);
+ }
+
+ FloatComparator revComp = new FloatComparator() {
+
+ @Override
+ public int compare(float o1, float o2) {
+ if (o2 < o1) {
+ return -1;
+ }
+ if (o2 > o1) {
+ return 1;
+ }
+ return 0;
+ }
+ };
+
+ stuff = randomFloats();
+ Sorting.mergeSort(stuff, 0, stuff.length, revComp);
+ for (int x = 0; x < (stuff.length - 1); x++) {
+ assertTrue(stuff[x] >= stuff[x + 1]);
+ }
+ }
+
+ @Test
+ public void testMergeSortDoubles() {
+ double[] stuff = randomDoubles();
+ Sorting.mergeSort(stuff, 0, stuff.length);
+ for (int x = 0; x < (stuff.length - 1); x++) {
+ assertTrue(stuff[x] <= stuff[x + 1]);
+ }
+
+ stuff = randomDoubles();
+ Sorting.mergeSort(stuff, 100, stuff.length);
+ for (int x = 100; x < (stuff.length - 1); x++) {
+ assertTrue(stuff[x] <= stuff[x + 1]);
+ }
+
+ DoubleComparator revComp = new DoubleComparator() {
+
+ @Override
+ public int compare(double o1, double o2) {
+ if (o2 < o1) {
+ return -1;
+ }
+ if (o2 > o1) {
+ return 1;
+ }
+ return 0;
+ }
+ };
+
+ stuff = randomDoubles();
+ Sorting.mergeSort(stuff, 0, stuff.length, revComp);
+ for (int x = 0; x < (stuff.length - 1); x++) {
+ assertTrue(stuff[x] >= stuff[x + 1]);
+ }
+ }
+
+}
+