http://git-wip-us.apache.org/repos/asf/mahout/blob/49ad8cb4/core/src/main/java-templates/org/apache/mahout/math/list/ValueTypeArrayList.java.t ---------------------------------------------------------------------- diff --git a/core/src/main/java-templates/org/apache/mahout/math/list/ValueTypeArrayList.java.t b/core/src/main/java-templates/org/apache/mahout/math/list/ValueTypeArrayList.java.t new file mode 100644 index 0000000..af14c0f --- /dev/null +++ b/core/src/main/java-templates/org/apache/mahout/math/list/ValueTypeArrayList.java.t @@ -0,0 +1,659 @@ +/** + * 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.list; + +import org.apache.mahout.math.function.${valueTypeCap}Procedure; + +/** + Resizable list holding <code>${valueType}</code> elements; implemented with arrays. +*/ + +public class ${valueTypeCap}ArrayList extends Abstract${valueTypeCap}List implements Cloneable { + + /** + * The array buffer into which the elements of the list are stored. The capacity of the list is the length of this + * array buffer. + */ + private ${valueType}[] elements; + + /** Constructs an empty list. */ + public ${valueTypeCap}ArrayList() { + this(10); + } + + /** + * Constructs a list containing the specified elements. The initial size and capacity of the list is the length of the + * array. + * + * <b>WARNING:</b> For efficiency reasons and to keep memory usage low, <b>the array is not copied</b>. So if + * subsequently you modify the specified array directly via the [] operator, be sure you know what you're doing. + * + * @param elements the array to be backed by the the constructed list + */ + public ${valueTypeCap}ArrayList(${valueType}[] elements) { + elements(elements); + } + + /** + * Constructs an empty list with the specified initial capacity. + * + * @param initialCapacity the number of elements the receiver can hold without auto-expanding itself by allocating new + * internal memory. + */ + public ${valueTypeCap}ArrayList(int initialCapacity) { + this(new ${valueType}[initialCapacity]); + setSizeRaw(0); + } + + /** + * Appends the specified element to the end of this list. + * + * @param element element to be appended to this list. + */ + public void add(${valueType} element) { + // overridden for performance only. + if (size == elements.length) { + ensureCapacity(size + 1); + } + elements[size++] = element; + } + + /** + * 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. + * + * @param index index before which the specified element is to be inserted (must be in [0,size]). + * @param element element to be inserted. + * @throws IndexOutOfBoundsException index is out of range (<tt>index < 0 || index > size()</tt>). + */ + public void beforeInsert(int index, ${valueType} element) { + // overridden for performance only. + if (size == index) { + add(element); + return; + } + if (index > size || index < 0) { + throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); + } + ensureCapacity(size + 1); + System.arraycopy(elements, index, elements, index + 1, size - index); + elements[index] = element; + size++; + } + + /** + * Searches the receiver for the specified value using the binary search algorithm. The receiver must + * <strong>must</strong> be sorted (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 org.apache.mahout.math.BinarySearch + * @see java.util.Arrays + */ + @Override + public int binarySearchFromTo(${valueType} key, int from, int to) { + return org.apache.mahout.math.BinarySearch.binarySearchFromTo(elements, key, from, to); + } + + /** + * Returns a deep copy of the receiver. + * + * @return a deep copy of the receiver. + */ + @Override + public Object clone() { + // overridden for performance only. + ${valueTypeCap}ArrayList clone = new ${valueTypeCap}ArrayList(elements.clone()); + clone.setSizeRaw(size); + return clone; + } + + /** + * Returns a deep copy of the receiver; uses <code>clone()</code> and casts the result. + * + * @return a deep copy of the receiver. + */ + public ${valueTypeCap}ArrayList copy() { + return (${valueTypeCap}ArrayList) clone(); + } + + #if ($valueType != 'float' && $valueType != 'double' && $valueType != 'long') + /** + * Sorts the specified range of the receiver into ascending numerical order. + * + * The sorting algorithm is a count sort. This algorithm offers guaranteed <dt>Performance: O(Max(n,max-min+1)). + * <dt>Space requirements: int[max-min+1] buffer. <p>This algorithm is only applicable if max-min+1 is not large! But + * if applicable, it usually outperforms quicksort by a factor of 3-4. + * + * @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 min the smallest element contained in the range. + * @param max the largest element contained in the range. + */ + protected void countSortFromTo(int from, int to, ${valueType} min, ${valueType} max) { + if (size == 0) { + return; + } + checkRangeFromTo(from, to, size); + + ${valueType} width = (${valueType})(max - min + 1); + + int[] counts = new int[width]; + ${valueType}[] theElements = elements; + for (int i = from; i <= to;) { + counts[(theElements[i++] - min)]++; + } + + int fromIndex = from; + ${valueType} val = min; + for (int i = 0; i < width; i++, val++) { + int c = counts[i]; + if (c > 0) { + if (c == 1) { + theElements[fromIndex++] = val; + } else { + int toIndex = fromIndex + c - 1; + fillFromToWith(fromIndex, toIndex, val); + fromIndex = toIndex + 1; + } + } + } + } + #end + + /** + * Returns the elements currently stored, including invalid elements between size and capacity, if any. + * + * <b>WARNING:</b> For efficiency reasons and to keep memory usage low, <b>the array is not copied</b>. So if + * subsequently you modify the returned array directly via the [] operator, be sure you know what you're doing. + * + * @return the elements currently stored. + */ + public ${valueType}[] elements() { + return elements; + } + + /** + * Sets the receiver's elements to be the specified array (not a copy of it). + * + * The size and capacity of the list is the length of the array. <b>WARNING:</b> For efficiency reasons and to keep + * memory usage low, <b>the array is not copied</b>. So if subsequently you modify the specified array directly via + * the [] operator, be sure you know what you're doing. + * + * @param elements the new elements to be stored. + * @return the receiver itself. + */ + public final Abstract${valueTypeCap}List elements(${valueType}[] elements) { + this.elements = elements; + this.size = elements.length; + return this; + } + + /** + * Ensures that the receiver can hold at least the specified number of elements without needing to allocate new + * internal memory. If necessary, allocates new internal memory and increases the capacity of the receiver. + * + * @param minCapacity the desired minimum capacity. + */ + public void ensureCapacity(int minCapacity) { + elements = org.apache.mahout.math.Arrays.ensureCapacity(elements, minCapacity); + } + + /** + * 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. + */ + public boolean equals(Object otherObj) { //delta + if (otherObj == null) { + return false; + } + // overridden for performance only. + if (!(otherObj instanceof ${valueTypeCap}ArrayList)) { + return super.equals(otherObj); + } + if (this == otherObj) { + return true; + } + ${valueTypeCap}ArrayList other = (${valueTypeCap}ArrayList) otherObj; + if (size() != other.size()) { + return false; + } + + ${valueType}[] theElements = elements(); + ${valueType}[] otherElements = other.elements(); + for (int i = size(); --i >= 0;) { + if (theElements[i] != otherElements[i]) { + return false; + } + } + return true; + } + + /** + * Applies a procedure to each element of the receiver, if any. Starts at index 0, moving rightwards. + * + * @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 elements where iterated over, <tt>true</tt> otherwise. + */ + public boolean forEach(${valueTypeCap}Procedure procedure) { + // overridden for performance only. + ${valueType}[] theElements = elements; + int theSize = size; + + for (int i = 0; i < theSize;) { + if (!procedure.apply(theElements[i++])) { + return false; + } + } + return true; + } + + /** + * Returns the element at the specified position in the receiver. + * + * @param index index of element to return. + * @throws IndexOutOfBoundsException index is out of range (index < 0 || index >= size()). + */ + public ${valueType} get(int index) { + // overridden for performance only. + if (index >= size || index < 0) { + throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); + } + return elements[index]; + } + + /** + * Returns the element at the specified position in the receiver; <b>WARNING:</b> Does not check preconditions. + * Provided with invalid parameters this method may return invalid elements without throwing any exception! <b>You + * should only use this method when you are absolutely sure that the index is within bounds.</b> Precondition + * (unchecked): <tt>index >= 0 && index < size()</tt>. + * + * @param index index of element to return. + */ + @Override + public ${valueType} getQuick(int index) { + return 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. Searches between <code>from</code>, inclusive and <code>to</code>, inclusive. Tests 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>). + */ + @Override + public int indexOfFromTo(${valueType} element, int from, int to) { + // overridden for performance only. + if (size == 0) { + return -1; + } + checkRangeFromTo(from, to, size); + + ${valueType}[] theElements = elements; + for (int i = from; i <= to; i++) { + if (element == theElements[i]) { + return i; + } //found + } + return -1; //not found + } + + /** + * 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 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>). + */ + @Override + public int lastIndexOfFromTo(${valueType} element, int from, int to) { + // overridden for performance only. + if (size == 0) { + return -1; + } + checkRangeFromTo(from, to, size); + + ${valueType}[] theElements = elements; + for (int i = to; i >= from; i--) { + if (element == theElements[i]) { + return i; + } //found + } + return -1; //not found + } + + /** + * Returns a new list of the part of the receiver between <code>from</code>, inclusive, and <code>to</code>, + * inclusive. + * + * @param from the index of the first element (inclusive). + * @param to the index of the last element (inclusive). + * @return a new list + * @throws IndexOutOfBoundsException index is out of range (<tt>size()>0 && (from<0 || from>to || + * to>=size())</tt>). + */ + @Override + public Abstract${valueTypeCap}List partFromTo(int from, int to) { + if (size == 0) { + return new ${valueTypeCap}ArrayList(0); + } + + checkRangeFromTo(from, to, size); + + ${valueType}[] part = new ${valueType}[to - from + 1]; + System.arraycopy(elements, from, part, 0, to - from + 1); + return new ${valueTypeCap}ArrayList(part); + } + + /** + * Removes from the receiver all elements that are contained in the specified list. Tests for identity. + * + * @param other the other list. + * @return <code>true</code> if the receiver changed as a result of the call. + */ + @Override + public boolean removeAll(Abstract${valueTypeCap}List other) { + // overridden for performance only. + if (!(other instanceof ${valueTypeCap}ArrayList)) { + return super.removeAll(other); + } + + /* There are two possibilities to do the thing + a) use other.indexOf(...) + b) sort other, then use other.binarySearch(...) + + Let's try to figure out which one is faster. Let M=size, N=other.size, then + a) takes O(M*N) steps + b) takes O(N*logN + M*logN) steps (sorting is O(N*logN) and binarySearch is O(logN)) + + Hence, if N*logN + M*logN < M*N, we use b) otherwise we use a). + */ + if (other.isEmpty()) { + return false; + } //nothing to do + int limit = other.size() - 1; + int j = 0; + ${valueType}[] theElements = elements; + int mySize = size(); + + double N = (double) other.size(); + double M = (double) mySize; + if ((N + M) * org.apache.mahout.collections.Arithmetic.log2(N) < M * N) { + // it is faster to sort other before searching in it + ${valueTypeCap}ArrayList sortedList = (${valueTypeCap}ArrayList) other.clone(); + sortedList.quickSort(); + + for (int i = 0; i < mySize; i++) { + if (sortedList.binarySearchFromTo(theElements[i], 0, limit) < 0) { + theElements[j++] = theElements[i]; + } + } + } else { + // it is faster to search in other without sorting + for (int i = 0; i < mySize; i++) { + if (other.indexOfFromTo(theElements[i], 0, limit) < 0) { + theElements[j++] = theElements[i]; + } + } + } + + boolean modified = (j != mySize); + setSize(j); + return modified; + } + + /** + * 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. + */ + @Override + public void replaceFromToWithFrom(int from, int to, Abstract${valueTypeCap}List other, int otherFrom) { + // overridden for performance only. + if (!(other instanceof ${valueTypeCap}ArrayList)) { + // slower + super.replaceFromToWithFrom(from, to, other, otherFrom); + return; + } + int length = to - from + 1; + if (length > 0) { + checkRangeFromTo(from, to, size()); + checkRangeFromTo(otherFrom, otherFrom + length - 1, other.size()); + System.arraycopy(((${valueTypeCap}ArrayList) other).elements, otherFrom, elements, from, length); + } + } + + /** + * 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. + * + * @param other the other list to test against. + * @return <code>true</code> if the receiver changed as a result of the call. + */ + @Override + public boolean retainAll(Abstract${valueTypeCap}List other) { + // overridden for performance only. + if (!(other instanceof ${valueTypeCap}ArrayList)) { + return super.retainAll(other); + } + + /* There are two possibilities to do the thing + a) use other.indexOf(...) + b) sort other, then use other.binarySearch(...) + + Let's try to figure out which one is faster. Let M=size, N=other.size, then + a) takes O(M*N) steps + b) takes O(N*logN + M*logN) steps (sorting is O(N*logN) and binarySearch is O(logN)) + + Hence, if N*logN + M*logN < M*N, we use b) otherwise we use a). + */ + int limit = other.size() - 1; + int j = 0; + ${valueType}[] theElements = elements; + int mySize = size(); + + double N = (double) other.size(); + double M = (double) mySize; + if ((N + M) * org.apache.mahout.collections.Arithmetic.log2(N) < M * N) { + // it is faster to sort other before searching in it + ${valueTypeCap}ArrayList sortedList = (${valueTypeCap}ArrayList) other.clone(); + sortedList.quickSort(); + + for (int i = 0; i < mySize; i++) { + if (sortedList.binarySearchFromTo(theElements[i], 0, limit) >= 0) { + theElements[j++] = theElements[i]; + } + } + } else { + // it is faster to search in other without sorting + for (int i = 0; i < mySize; i++) { + if (other.indexOfFromTo(theElements[i], 0, limit) >= 0) { + theElements[j++] = theElements[i]; + } + } + } + + boolean modified = (j != mySize); + setSize(j); + return modified; + } + + /** 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; + + ${valueType}[] theElements = elements; + for (int i = 0; i < limit;) { //swap + ${valueType} tmp = theElements[i]; + theElements[i++] = theElements[j]; + theElements[j--] = tmp; + } + } + + /** + * Replaces the element at the specified position in the receiver with the specified element. + * + * @param index index of element to replace. + * @param element element to be stored at the specified position. + * @throws IndexOutOfBoundsException index is out of range (index < 0 || index >= size()). + */ + @Override + public void set(int index, ${valueType} element) { + // overridden for performance only. + if (index >= size || index < 0) { + throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); + } + elements[index] = element; + } + + /** + * Replaces the element at the specified position in the receiver with the specified element; <b>WARNING:</b> Does not + * check preconditions. Provided with invalid parameters this method may access invalid indexes without throwing any + * exception! <b>You should only use this method when you are absolutely sure that the index is within bounds.</b> + * Precondition (unchecked): <tt>index >= 0 && index < size()</tt>. + * + * @param index index of element to replace. + * @param element element to be stored at the specified position. + */ + @Override + public void setQuick(int index, ${valueType} element) { + elements[index] = element; + } + + /** + * Randomly permutes the part of the receiver between <code>from</code> (inclusive) and <code>to</code> (inclusive). + * + * @param from the index of the first element (inclusive) to be permuted. + * @param to the index of the last element (inclusive) to be permuted. + * @throws IndexOutOfBoundsException index is out of range (<tt>size()>0 && (from<0 || from>to || + * to>=size())</tt>). + */ + + /** + * Sorts the specified range of the receiver into ascending order. + * + * The sorting algorithm is dynamically chosen according to the characteristics of the data set. Currently quicksort + * and countsort are considered. Countsort is not always applicable, but if applicable, it usually outperforms + * quicksort by a factor of 3-4. + * + * <p>Best case performance: O(N). <dt>Worst case performance: O(N^2) (a degenerated quicksort). <dt>Best case space + * requirements: 0 KB. <dt>Worst case space requirements: 40 KB. + * + * @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 sortFromTo(int from, int to) { + /* + * Computes min and max and decides on this basis. + * In practice the additional overhead is very small compared to the potential gains. + */ + + if (size == 0) { + return; + } + checkRangeFromTo(from, to, size); + + // determine minimum and maximum. + ${valueType} min = elements[from]; + ${valueType} max = elements[from]; + + ${valueType}[] theElements = elements; + for (int i = from + 1; i <= to;) { + ${valueType} elem = theElements[i++]; + if (elem > max) { + max = elem; + } else if (elem < min) { + min = elem; + } + } + + #if ($valueType == 'byte' || $valueType == 'char' || $valueType == 'int') + // try to figure out which option is fastest. + double N = (double) to - (double) from + 1.0; + double quickSortEstimate = N * Math.log(N) / 0.6931471805599453; // O(N*log(N,base=2)) ; ln(2)=0.6931471805599453 + + double width = (double) max - (double) min + 1.0; + double countSortEstimate = Math.max(width, N); // O(Max(width,N)) + + int widthThreshold = 10000; // never consider options resulting in outrageous memory allocations. + if (width < widthThreshold && countSortEstimate < quickSortEstimate) { + countSortFromTo(from, to, min, max); + } else { + quickSortFromTo(from, to); + } + #else + quickSortFromTo(from, to); + #end + } + + /** + * 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. + */ + @Override + public void trimToSize() { + elements = org.apache.mahout.math.Arrays.trimToCapacity(elements, size()); + } +}
http://git-wip-us.apache.org/repos/asf/mahout/blob/49ad8cb4/core/src/main/java-templates/org/apache/mahout/math/map/AbstractKeyTypeObjectMap.java.t ---------------------------------------------------------------------- diff --git a/core/src/main/java-templates/org/apache/mahout/math/map/AbstractKeyTypeObjectMap.java.t b/core/src/main/java-templates/org/apache/mahout/math/map/AbstractKeyTypeObjectMap.java.t new file mode 100644 index 0000000..4ffbe3a --- /dev/null +++ b/core/src/main/java-templates/org/apache/mahout/math/map/AbstractKeyTypeObjectMap.java.t @@ -0,0 +1,467 @@ +/** + * 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 java.util.ArrayList; +import java.util.List; +import java.nio.IntBuffer; +import java.util.Arrays; + +import org.apache.mahout.math.Sorting; +import org.apache.mahout.math.Swapper; +import org.apache.mahout.math.set.HashUtils; +import org.apache.mahout.math.function.IntComparator; + +import org.apache.mahout.math.function.${keyTypeCap}ObjectProcedure; +import org.apache.mahout.math.function.${keyTypeCap}Procedure; +import org.apache.mahout.math.list.${keyTypeCap}ArrayList; +import org.apache.mahout.math.set.AbstractSet; + +public abstract class Abstract${keyTypeCap}ObjectMap<T> extends AbstractSet { + + /** + * 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. Tests for identity. + * + * @return <tt>true</tt> if the receiver contains the specified value. + */ + public boolean containsValue(final T value) { + return !forEachPair( + new ${keyTypeCap}ObjectProcedure<T>() { + @Override + public boolean apply(${keyType} iterKey, Object 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. + */ + @SuppressWarnings("unchecked") // seemingly unavoidable. + public Abstract${keyTypeCap}ObjectMap<T> copy() { + return this.getClass().cast(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}ObjectProcedure() { + * public boolean apply(${keyType} key, Object value) { + * return m2.containsKey(key) && m2.get(key) == value; + * } + * } + * ) + * && + * m2.forEachPair( + * new ${keyTypeCap}ObjectProcedure() { + * public boolean apply(${keyType} key, Object 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. + */ + @SuppressWarnings("unchecked") // incompressible + public boolean equals(Object obj) { + if (obj == this) { + return true; + } + + if (!(obj instanceof Abstract${keyTypeCap}ObjectMap)) { + return false; + } + final Abstract${keyTypeCap}ObjectMap other = (Abstract${keyTypeCap}ObjectMap) obj; + if (other.size() != size()) { + return false; + } + + return + forEachPair( + new ${keyTypeCap}ObjectProcedure() { + @Override + public boolean apply(${keyType} key, Object value) { + return other.containsKey(key) && other.get(key) == value; + } + } + ) + && + other.forEachPair( + new ${keyTypeCap}ObjectProcedure() { + @Override + public boolean apply(${keyType} key, Object value) { + return containsKey(key) && get(key) == value; + } + } + ); + } + + public int hashCode() { + final int[] buf = new int[size()]; + forEachPair( + new ${keyTypeCap}ObjectProcedure() { + int i = 0; + + @Override + public boolean apply(${keyType} key, Object value) { + buf[i++] = HashUtils.hash(key) ^ value.hashCode(); + return true; + } + } + ); + Arrays.sort(buf); + return IntBuffer.wrap(buf).hashCode(); + } + + + + /** + * 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(${keyTypeCap}Procedure)}. + * + * @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}ObjectProcedure<T> 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(${keyType})} 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>null</tt> if no such key is present. + */ + public abstract T get(${keyType} key); + + /** + * 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(${keyTypeCap}Procedure)}. <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(${keyTypeCap}Procedure)}. <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 ArrayList<T>(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(${keyTypeCap}Procedure)}. + * <p> <b>Example:</b> <br> + * <pre> + * ${keyTypeCap}ObjectProcedure condition = new ${keyTypeCap}ObjectProcedure() { // match even keys only + * public boolean apply(${keyType} key, Object 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}ObjectProcedure<T> condition, + final ${keyTypeCap}ArrayList keyList, + final List<T> valueList) { + keyList.clear(); + valueList.clear(); + + forEachPair( + new ${keyTypeCap}ObjectProcedure<T>() { + @Override + public boolean apply(${keyType} key, T 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. + */ + @SuppressWarnings("unchecked") + public void pairsSortedByKey(${keyTypeCap}ArrayList keyList, List<T> valueList) { + keys(keyList); + keyList.sort(); + // the following is straightforward if not the most space-efficient possibility + Object[] tempValueList = new Object[keyList.size()]; + + for (int i = keyList.size(); --i >= 0;) { + tempValueList[i] = get(keyList.getQuick(i)); + } + valueList.clear(); + for (Object value : tempValueList) { + valueList.add((T) value); + } + + } + + /** + * Fills all keys and values <i>sorted ascending by value according to natural ordering</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. + */ + @SuppressWarnings("unchecked") + public void pairsSortedByValue(${keyTypeCap}ArrayList keyList, List<T> valueList) { + keys(keyList); + values(valueList); + + if (!valueList.isEmpty() && !(valueList.get(0) instanceof Comparable)) { + throw new UnsupportedOperationException("Cannot sort the values; " + + valueList.get(0).getClass() + + " does not implement Comparable"); + } + + final ${keyType}[] k = keyList.elements(); + final List<T> valueRef = valueList; + Swapper swapper = new Swapper() { + @Override + public void swap(int a, int b) { + T t1 = valueRef.get(a); + valueRef.set(a, valueRef.get(b)); + valueRef.set(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) { + int ab = ((Comparable)valueRef.get(a)).compareTo(valueRef.get(b)); + return ab < 0 ? -1 : ab > 0 ? 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, T 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, according to natural ordering. + */ + 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(${keyTypeCap}Procedure)}. <p> This method can be used to iterate over the values of the receiver. + * + * @return the values. + */ + public List<T> values() { + List<T> list = new ArrayList<T>(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(${keyTypeCap}Procedure)}. <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 List<T> list) { + list.clear(); + forEachKey( + new ${keyTypeCap}Procedure() { + @Override + public boolean apply(${keyType} key) { + list.add(get(key)); + return true; + } + } + ); + } +} http://git-wip-us.apache.org/repos/asf/mahout/blob/49ad8cb4/core/src/main/java-templates/org/apache/mahout/math/map/AbstractKeyTypeValueTypeMap.java.t ---------------------------------------------------------------------- diff --git a/core/src/main/java-templates/org/apache/mahout/math/map/AbstractKeyTypeValueTypeMap.java.t b/core/src/main/java-templates/org/apache/mahout/math/map/AbstractKeyTypeValueTypeMap.java.t new file mode 100644 index 0000000..16297cc --- /dev/null +++ b/core/src/main/java-templates/org/apache/mahout/math/map/AbstractKeyTypeValueTypeMap.java.t @@ -0,0 +1,509 @@ +/** + * 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 java.nio.IntBuffer; +import java.util.Arrays; + +import org.apache.mahout.math.Sorting; +import org.apache.mahout.math.Swapper; +import org.apache.mahout.math.set.HashUtils; +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.list.${valueTypeCap}ArrayList; +#end +import org.apache.mahout.math.function.IntComparator; +#if (${valueTypeFloating} == 'true') +import org.apache.mahout.math.function.${valueTypeCap}Function; +#end + +import org.apache.mahout.math.set.AbstractSet; + +public abstract class Abstract${keyTypeCap}${valueTypeCap}Map extends AbstractSet { + + /** + * 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; + } + } + ); + } + + public int hashCode() { + final int[] buf = new int[size()]; + forEachPair( + new ${keyTypeCap}${valueTypeCap}Procedure() { + int i = 0; + + @Override + public boolean apply(${keyType} key, ${valueType} value) { + buf[i++] = HashUtils.hash(key) ^ HashUtils.hash(value); + return true; + } + } + ); + Arrays.sort(buf); + return IntBuffer.wrap(buf).hashCode(); + } + + /** + * 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(${keyTypeCap}Procedure)}. + * + * @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(${keyType})} 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 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(${keyTypeCap}Procedure)}. <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(${keyTypeCap}Procedure)}. <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(${keyTypeCap}Procedure)}. + * <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(${keyTypeCap}Procedure)}. <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(${keyTypeCap}Procedure)}. + * <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 + + /** + * Check the map for a key. If present, add an increment to the value. If absent, + * store a specified value. + * @param key the key. + * @param newValue the value to store if the key is not currently in the map. + * @param incrValue the value to be added to the current value in the map. + **/ + public ${valueType} adjustOrPutValue(${keyType} key, ${valueType} newValue, ${valueType} incrValue) { + boolean present = containsKey(key); + if (present) { + newValue = (${valueType})(get(key) + incrValue); + put(key, newValue); + } else { + put(key, newValue); + } + return newValue; + } +} http://git-wip-us.apache.org/repos/asf/mahout/blob/49ad8cb4/core/src/main/java-templates/org/apache/mahout/math/map/AbstractObjectValueTypeMap.java.t ---------------------------------------------------------------------- diff --git a/core/src/main/java-templates/org/apache/mahout/math/map/AbstractObjectValueTypeMap.java.t b/core/src/main/java-templates/org/apache/mahout/math/map/AbstractObjectValueTypeMap.java.t new file mode 100644 index 0000000..15778be --- /dev/null +++ b/core/src/main/java-templates/org/apache/mahout/math/map/AbstractObjectValueTypeMap.java.t @@ -0,0 +1,516 @@ +/** + * 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 java.util.ArrayList; +import java.util.Collections; +import java.util.List; +import java.nio.IntBuffer; +import java.util.Arrays; + +import org.apache.mahout.math.set.HashUtils; +import org.apache.mahout.math.Sorting; +import org.apache.mahout.math.Swapper; +import org.apache.mahout.math.function.Object${valueTypeCap}Procedure; +import org.apache.mahout.math.function.ObjectProcedure; +import org.apache.mahout.math.list.${valueTypeCap}ArrayList; +import org.apache.mahout.math.function.IntComparator; +#if (${valueTypeFloating} == 'true') +import org.apache.mahout.math.function.${valueTypeCap}Function; +#end +import org.apache.mahout.math.set.AbstractSet; + +public abstract class AbstractObject${valueTypeCap}Map<T> extends AbstractSet { + + /** + * 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 T key) { + return !forEachKey( + new ObjectProcedure<T>() { + @Override + public boolean apply(T 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 Object${valueTypeCap}Procedure<T>() { + @Override + public boolean apply(T 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. + */ + @SuppressWarnings("unchecked") // seemingly unavoidable. + public AbstractObject${valueTypeCap}Map<T> copy() { + return (AbstractObject${valueTypeCap}Map<T>) 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 Object${valueTypeCap}Procedure<T>() { + * public boolean apply(T key, ${valueType} value) { + * return m2.containsKey(key) && m2.get(key) == value; + * } + * } + * ) + * && + * m2.forEachPair( + * new Object${valueTypeCap}Procedure<T>() { + * public boolean apply(T 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. + */ + @SuppressWarnings("unchecked") + public boolean equals(Object obj) { + if (obj == this) { + return true; + } + + if (!(obj instanceof AbstractObject${valueTypeCap}Map)) { + return false; + } + final AbstractObject${valueTypeCap}Map other = (AbstractObject${valueTypeCap}Map) obj; + if (other.size() != size()) { + return false; + } + + return + forEachPair( + new Object${valueTypeCap}Procedure<T>() { + @Override + public boolean apply(T key, ${valueType} value) { + return other.containsKey(key) && other.get(key) == value; + } + } + ) + && + other.forEachPair( + new Object${valueTypeCap}Procedure<T>() { + @Override + public boolean apply(T key, ${valueType} value) { + return containsKey(key) && get(key) == value; + } + } + ); + } + + public int hashCode() { + final int[] buf = new int[size()]; + forEachPair( + new Object${valueTypeCap}Procedure<T>() { + int i = 0; + + @Override + public boolean apply(Object key, ${valueType} value) { + buf[i++] = key.hashCode() ^ HashUtils.hash(value); + return true; + } + } + ); + Arrays.sort(buf); + return IntBuffer.wrap(buf).hashCode(); + } + + /** + * 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(ObjectProcedure<T> 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(ObjectProcedure)}. + * + * @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 Object${valueTypeCap}Procedure<T> procedure) { + return forEachKey( + new ObjectProcedure<T>() { + @Override + public boolean apply(T 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(Object)} 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(T key); + + /** + * 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(ObjectProcedure)}. <p> This method can be used to iterate over the keys of the receiver. + * + * @return the keys. + */ + public List<T> keys() { + List<T> list = new ArrayList<T>(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(ObjectProcedure)}. <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 List<T> list) { + list.clear(); + forEachKey( + new ObjectProcedure<T>() { + @Override + public boolean apply(T 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(List<T> 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(ObjectProcedure)}. + * <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 Object${valueTypeCap}Procedure<T> condition, + final List<T> keyList, + final ${valueTypeCap}ArrayList valueList) { + keyList.clear(); + valueList.clear(); + + forEachPair( + new Object${valueTypeCap}Procedure<T>() { + @Override + public boolean apply(T 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. + */ + @SuppressWarnings("unchecked") + public void pairsSortedByKey(List<T> keyList, ${valueTypeCap}ArrayList valueList) { + keys(keyList); + if (keyList.isEmpty()) { + return; + } + T k = keyList.get(0); + // some people would demand a more complex type hierarchy here ... + if (!(k instanceof Comparable)) { + throw new UnsupportedOperationException("The key type for this map does not implement comparable"); + } + Collections.sort((List) keyList); + valueList.setSize(keyList.size()); + for (int i = keyList.size(); --i >= 0;) { + valueList.setQuick(i, get(keyList.get(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(final List<T> keyList, ${valueTypeCap}ArrayList valueList) { + keys(keyList); + values(valueList); + + 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; + T t2 = keyList.get(a); + keyList.set(a, keyList.get(b)); + keyList.set(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 : 0; + } + }; + + 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(T 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(T key); + + /** + * Returns a string representation of the receiver, containing the String representation of each key-value pair, + * sorted ascending by key. + */ + public String toString() { + List<T> theKeys = keys(); + + StringBuilder buf = new StringBuilder(); + buf.append('['); + int maxIndex = theKeys.size() - 1; + for (int i = 0; i <= maxIndex; i++) { + T 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() { + List<T> theKeys = new ArrayList<T>(); + keysSortedByValue(theKeys); + + StringBuilder buf = new StringBuilder(); + buf.append('['); + int maxIndex = theKeys.size() - 1; + for (int i = 0; i <= maxIndex; i++) { + T 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(ObjectProcedure)}. <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(ObjectProcedure)}. <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 ObjectProcedure<T>() { + @Override + public boolean apply(T 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 Object${valueTypeCap}Procedure<T>() { + @Override + public boolean apply(T 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(AbstractObject${valueTypeCap}Map<T> other) { + clear(); + other.forEachPair( + new Object${valueTypeCap}Procedure<T>() { + @Override + public boolean apply(T key, ${valueType} value) { + put(key, value); + return true; + } + } + ); + } + #end + + /** + * Check the map for a key. If present, add an increment to the value. If absent, + * store a specified value. + * @param key the key. + * @param newValue the value to store if the key is not currently in the map. + * @param incrValue the value to be added to the current value in the map. + **/ + public ${valueType} adjustOrPutValue(T key, ${valueType} newValue, ${valueType} incrValue) { + boolean present = containsKey(key); + if (present) { + newValue = (${valueType})(get(key) + incrValue); + put(key, newValue); + } else { + put(key, newValue); + } + return newValue; + } +}
