http://git-wip-us.apache.org/repos/asf/mahout/blob/e0573de3/math/src/main/java-templates/org/apache/mahout/math/list/AbstractValueTypeList.java.t ---------------------------------------------------------------------- diff --git a/math/src/main/java-templates/org/apache/mahout/math/list/AbstractValueTypeList.java.t b/math/src/main/java-templates/org/apache/mahout/math/list/AbstractValueTypeList.java.t deleted file mode 100644 index 343472a..0000000 --- a/math/src/main/java-templates/org/apache/mahout/math/list/AbstractValueTypeList.java.t +++ /dev/null @@ -1,851 +0,0 @@ -/** - * 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; -//CHECKSTYLE:OFF -import org.apache.mahout.math.Sorting; -import org.apache.mahout.math.buffer.${valueTypeCap}BufferConsumer; -import org.apache.mahout.math.function.${valueTypeCap}Comparator; -import org.apache.mahout.math.function.${valueTypeCap}Procedure; -//CHECKSTYLE:ON - -import java.util.ArrayList; -import java.util.List; - -/** - Abstract base class for resizable lists holding <code>${valueType}</code> elements; abstract. -*/ -public abstract class Abstract${valueTypeCap}List extends AbstractList implements ${valueTypeCap}BufferConsumer { - - /** - * The size of the list. This is a READ_ONLY variable for all methods but setSizeRaw(int newSize) !!! If you violate - * this principle in subclasses, you should exactly know what you are doing. - */ - protected int size; - - /** - * Appends the specified element to the end of this list. - * - * @param element element to be appended to this list. - */ - public void add(${valueType} element) { - beforeInsert(size, element); - } - - /** - * Appends all elements of the specified list to the receiver. - * - * @param other the list of which all elements shall be appended. - */ - public void addAllOf(Abstract${valueTypeCap}List other) { - addAllOfFromTo(other, 0, other.size() - 1); - } - - /** - * 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(Abstract${valueTypeCap}List other, int from, int to) { - beforeInsertAllOfFromTo(size, other, from, to); - } - - /** - * Appends the specified list to the end of this list. - * @param other the list to be appended. - **/ - @Override - public void addAllOf(${valueTypeCap}ArrayList other) { - addAllOfFromTo(other, 0, other.size() - 1); - } - - /** - * 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) { - beforeInsertDummies(index, 1); - set(index, element); - } - - /** - * 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, Abstract${valueTypeCap}List other, int from, int to) { - int length = to - from + 1; - this.beforeInsertDummies(index, length); - this.replaceFromToWithFrom(index, index + length - 1, other, from); - } - - /** - * Inserts <tt>length</tt> dummy elements before the specified position into the receiver. Shifts the element - * currently at that position (if any) and any subsequent elements to the right. <b>This method must set the new size - * to be <tt>size()+length</tt>. - * - * @param index index before which to insert dummy elements (must be in [0,size]).. - * @param length number of dummy elements to be inserted. - * @throws IndexOutOfBoundsException if <tt>index < 0 || index > size()</tt>. - */ - @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); - setSizeRaw(size + length); - replaceFromToWithFrom(index + length, size - 1, this, index); - } - } - - /** - * 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. - * @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 java.util.Arrays - */ - public int binarySearch(${valueType} key) { - return this.binarySearchFromTo(key, 0, size - 1); - } - - /** - * 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 java.util.Arrays - */ - public int binarySearchFromTo(${valueType} key, int from, int to) { - int low = from; - int high = to; - while (low <= high) { - int mid = (low + high) / 2; - ${valueType} midVal = get(mid); - - if (midVal < key) { - low = mid + 1; - } else if (midVal > key) { - high = mid - 1; - } else { - return mid; - } // key found - } - return -(low + 1); // key not found. - } - - /** - * Returns a deep copy of the receiver. - * - * @return a deep copy of the receiver. - */ - @Override - public Object clone() { - return partFromTo(0, size - 1); - } - - /** - * Returns true if the receiver contains the specified element. - * - * @param elem element whose presence in the receiver is to be tested. - */ - public boolean contains(${valueType} elem) { - return indexOfFromTo(elem, 0, size - 1) >= 0; - } - - /** - * Deletes the first element from the receiver that is identical to the specified element. Does nothing, if no such - * matching element is contained. - * - * @param element the element to be deleted. - */ - public void delete(${valueType} element) { - int index = indexOfFromTo(element, 0, size - 1); - if (index >= 0) { - remove(index); - } - } - - /** - * Returns the elements currently stored, possibly including invalid elements between size and capacity. - * - * <b>WARNING:</b> For efficiency reasons and to keep memory usage low, this method may decide <b>not to copy the - * array</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() { - ${valueType}[] myElements = new ${valueType}[size]; - for (int i = size; --i >= 0;) { - myElements[i] = getQuick(i); - } - return myElements; - } - - /** - * Sets the receiver's elements to be the specified array. 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, this method may decide <b>not to copy - * the array</b>. So if subsequently you modify the returned 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 Abstract${valueTypeCap}List elements(${valueType}[] elements) { - clear(); - addAllOfFromTo(new ${valueTypeCap}ArrayList(elements), 0, elements.length - 1); - 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 abstract void ensureCapacity(int 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; - } - if (!(otherObj instanceof Abstract${valueTypeCap}List)) { - return false; - } - if (this == otherObj) { - return true; - } - Abstract${valueTypeCap}List other = (Abstract${valueTypeCap}List) otherObj; - if (size() != other.size()) { - return false; - } - - for (int i = size(); --i >= 0;) { - if (getQuick(i) != other.getQuick(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, ${valueType} val) { - checkRangeFromTo(from, to, this.size); - for (int i = from; i <= to;) { - setQuick(i++, val); - } - } - - /** - * 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) { - for (int i = 0; i < size;) { - if (!procedure.apply(get(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) { - if (index >= size || index < 0) { - throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); - } - return getQuick(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>. - * - * This method is normally only used internally in large loops where bounds are explicitly checked before the loop and - * need no be rechecked within the loop. However, when desperately, you can give this method <tt>public</tt> - * visibility in subclasses. - * - * @param index index of element to return. - */ - protected abstract ${valueType} getQuick(int index); - - /** - * Returns the index of the first occurrence of the specified element. Returns <code>-1</code> if the receiver does - * not contain this element. - * - * @param element the element to be searched for. - * @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(${valueType} element) { //delta - return indexOfFromTo(element, 0, size - 1); - } - - /** - * 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>). - */ - public int indexOfFromTo(${valueType} element, int from, int to) { - checkRangeFromTo(from, to, size); - - for (int i = from; i <= to; i++) { - if (element == getQuick(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. - * - * @param element the element to be searched for. - * @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(${valueType} element) { - return lastIndexOfFromTo(element, 0, size - 1); - } - - /** - * 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>). - */ - public int lastIndexOfFromTo(${valueType} element, int from, int to) { - checkRangeFromTo(from, to, size()); - - for (int i = to; i >= from; i--) { - if (element == getQuick(i)) { - return i; - } //found - } - return -1; //not found - } - - /** - * Sorts the specified range of the receiver into ascending order. - * - * 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) { - int mySize = size(); - checkRangeFromTo(from, to, mySize); - - ${valueType}[] myElements = elements(); - Sorting.mergeSort(myElements, from, to + 1); - elements(myElements); - setSizeRaw(mySize); - } - - /** - * 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>). - */ - public void mergeSortFromTo(int from, int to, ${valueTypeCap}Comparator c) { - int mySize = size(); - checkRangeFromTo(from, to, mySize); - - ${valueType}[] myElements = elements(); - Sorting.mergeSort(myElements, from, to + 1, c); - elements(myElements); - setSizeRaw(mySize); - } - - /** - * 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>). - */ - public Abstract${valueTypeCap}List partFromTo(int from, int to) { - checkRangeFromTo(from, to, size); - - int length = to - from + 1; - ${valueTypeCap}ArrayList part = new ${valueTypeCap}ArrayList(length); - part.addAllOfFromTo(this, from, to); - return part; - } - - /** - * Sorts the specified range of the receiver into ascending numerical order. 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) { - int mySize = size(); - checkRangeFromTo(from, to, mySize); - - ${valueType}[] myElements = elements(); - java.util.Arrays.sort(myElements, from, to + 1); - elements(myElements); - setSizeRaw(mySize); - } - - /** - * 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>). - */ - public void quickSortFromTo(int from, int to, ${valueTypeCap}Comparator c) { - int mySize = size(); - checkRangeFromTo(from, to, mySize); - - ${valueType}[] myElements = elements(); - Sorting.quickSort(myElements, from, to + 1, c); - elements(myElements); - setSizeRaw(mySize); - } - - /** - * 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. - */ - public boolean removeAll(Abstract${valueTypeCap}List other) { - if (other.isEmpty()) { - return false; - } //nothing to do - int limit = other.size() - 1; - int j = 0; - - for (int i = 0; i < size; i++) { - if (other.indexOfFromTo(getQuick(i), 0, limit) < 0) { - setQuick(j++, getQuick(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) { - replaceFromToWithFrom(from, from - 1 + numMoved, this, to + 1); - //fillFromToWith(from+numMoved, size-1, 0.0f); //delta - } - int width = to - from + 1; - if (width > 0) { - setSizeRaw(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, Abstract${valueTypeCap}List other, int otherFrom) { - int length = to - from + 1; - if (length > 0) { - checkRangeFromTo(from, to, size()); - checkRangeFromTo(otherFrom, otherFrom + length - 1, other.size()); - - // unambiguous copy (it may hold other==this) - if (from <= otherFrom) { - while (--length >= 0) { - setQuick(from++, other.getQuick(otherFrom++)); - } - } else { - int otherTo = otherFrom + length - 1; - while (--length >= 0) { - setQuick(to--, other.getQuick(otherTo--)); - } - } - } - } - - /** - * 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, Abstract${valueTypeCap}List 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; - - 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) { - replaceFromToWithFrom(from, from + length - 1, other, otherFrom); - } - } - - /** - * 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. - */ - public boolean retainAll(Abstract${valueTypeCap}List other) { - if (other.isEmpty()) { - if (size == 0) { - return false; - } - setSize(0); - return true; - } - - int limit = other.size() - 1; - int j = 0; - for (int i = 0; i < size; i++) { - if (other.indexOfFromTo(getQuick(i), 0, limit) >= 0) { - setQuick(j++, getQuick(i)); - } - } - - boolean modified = (j != size); - 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() { - int limit = size() / 2; - int j = size() - 1; - - for (int i = 0; i < limit;) { //swap - ${valueType} tmp = getQuick(i); - setQuick(i++, getQuick(j)); - setQuick(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 if <tt>index < 0 || index >= size()</tt>. - */ - public void set(int index, ${valueType} element) { - if (index >= size || index < 0) { - throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); - } - setQuick(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>. - * - * This method is normally only used internally in large loops where bounds are explicitly checked before the loop and - * need no be rechecked within the loop. However, when desperately, you can give this method <tt>public</tt> - * visibility in subclasses. - * - * @param index index of element to replace. - * @param element element to be stored at the specified position. - */ - protected abstract void setQuick(int index, ${valueType} element); - - /** - * Sets the size of the receiver without modifying it otherwise. This method should not release or allocate new memory - * but simply set some instance variable like <tt>size</tt>. - * - * If your subclass overrides and delegates size changing methods to some other object, you must make sure that those - * overriding methods not only update the size of the delegate but also of this class. For example: public - * DatabaseList extends Abstract${valueTypeCap}List { ... public void removeFromTo(int from,int to) { - * myDatabase.removeFromTo(from,to); this.setSizeRaw(size-(to-from+1)); } } - */ - protected void setSizeRaw(int newSize) { - size = newSize; - } - - /** 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. - */ - public Abstract${valueTypeCap}List times(int times) { - Abstract${valueTypeCap}List newList = new ${valueTypeCap}ArrayList(times * size()); - for (int i = times; --i >= 0;) { - newList.addAllOfFromTo(this, 0, size() - 1); - } - return newList; - } - - /** Returns a <code>ArrayList</code> containing all the elements in the receiver. */ - public List<${valueObjectType}> toList() { - int mySize = size(); - List<${valueObjectType}> list = new ArrayList<${valueObjectType}>(mySize); - for (int i = 0; i < mySize; i++) { - list.add(get(i)); - } - return list; - } - - public ${valueType}[] toArray(${valueType}[] values) { - int mySize = size(); - ${valueType}[] myElements; - if (values.length >= mySize) { - myElements = values; - } else { - myElements = new ${valueType}[mySize]; - } - for (int i = size; --i >= 0;) { - myElements[i] = getQuick(i); - } - return myElements; - } - - /** 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()); - } -}
http://git-wip-us.apache.org/repos/asf/mahout/blob/e0573de3/math/src/main/java-templates/org/apache/mahout/math/list/ValueTypeArrayList.java.t ---------------------------------------------------------------------- diff --git a/math/src/main/java-templates/org/apache/mahout/math/list/ValueTypeArrayList.java.t b/math/src/main/java-templates/org/apache/mahout/math/list/ValueTypeArrayList.java.t deleted file mode 100644 index af14c0f..0000000 --- a/math/src/main/java-templates/org/apache/mahout/math/list/ValueTypeArrayList.java.t +++ /dev/null @@ -1,659 +0,0 @@ -/** - * 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/e0573de3/math/src/main/java-templates/org/apache/mahout/math/map/AbstractKeyTypeObjectMap.java.t ---------------------------------------------------------------------- diff --git a/math/src/main/java-templates/org/apache/mahout/math/map/AbstractKeyTypeObjectMap.java.t b/math/src/main/java-templates/org/apache/mahout/math/map/AbstractKeyTypeObjectMap.java.t deleted file mode 100644 index 4ffbe3a..0000000 --- a/math/src/main/java-templates/org/apache/mahout/math/map/AbstractKeyTypeObjectMap.java.t +++ /dev/null @@ -1,467 +0,0 @@ -/** - * 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; - } - } - ); - } -}
