package de.lmu.ifi.dbs.elki.utilities;
/*
This file is part of ELKI:
Environment for Developing KDD-Applications Supported by Index-Structures
Copyright (C) 2011
Ludwig-Maximilians-Universität München
Lehr- und Forschungseinheit für Datenbanksysteme
ELKI Development Team
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU Affero General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU Affero General Public License for more details.
You should have received a copy of the GNU Affero General Public License
along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
import java.io.PrintStream;
import java.util.AbstractCollection;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;
import java.util.StringTokenizer;
import de.lmu.ifi.dbs.elki.data.DoubleVector;
import de.lmu.ifi.dbs.elki.data.SparseFloatVector;
/**
* This class collects various static helper methods.
*
* For helper methods related to special application fields see other utilities
* classes.
*
*
* @see de.lmu.ifi.dbs.elki.utilities
*/
public final class Util {
/**
* Returns the prefix of the specified fileName (i.e. the name of the file
* without extension).
*
* @param fileName the name of the file
* @return the prefix of the specified fileName
*/
public static String getFilePrefix(final String fileName) {
final int index = fileName.lastIndexOf(Character.getNumericValue('.'));
if(index < 0) {
return fileName;
}
return fileName.substring(0, index);
}
/**
* Returns a new String array containing the same objects as are contained in
* the given array.
*
* @param array an array to copy
* @return the copied array
*/
public static String[] copy(String[] array) {
String[] copy = new String[array.length];
System.arraycopy(array, 0, copy, 0, array.length);
return copy;
}
/**
* Returns a new double array containing the same objects as are contained in
* the given array.
*
* @param array an array to copy
* @return the copied array
*/
public static double[] copy(double[] array) {
double[] copy = new double[array.length];
System.arraycopy(array, 0, copy, 0, array.length);
return copy;
}
/**
* Returns the unboxed double array of the given Object Double array.
*
* @param array the array to be unboxed
* @return the unboxed double array
*/
public static double[] unbox(Double[] array) {
double[] unboxed = new double[array.length];
// noinspection ManualArrayCopy
for(int i = 0; i < unboxed.length; i++) {
unboxed[i] = array[i];
}
return unboxed;
}
/**
* Returns the unboxed double array of the given Object Number array.
*
* @param array the array to be unboxed
* @return the unboxed double array
*/
public static double[] unbox(Number[] array) {
double[] unboxed = new double[array.length];
for(int i = 0; i < unboxed.length; i++) {
unboxed[i] = array[i].doubleValue();
}
return unboxed;
}
/**
* Returns the unboxed float array of the given Object Number array.
*
* @param array the array to be unboxed
* @return the unboxed float array
*/
public static float[] unboxToFloat(Number[] array) {
float[] unboxed = new float[array.length];
for(int i = 0; i < unboxed.length; i++) {
unboxed[i] = array[i].floatValue();
}
return unboxed;
}
/**
* Returns a new <code>Double</code> array initialized to the values
* represented by the specified <code>String</code> and separated by comma, as
* performed by the <code>valueOf</code> method of class <code>Double</code>.
*
* @param s the string to be parsed.
* @return a new <code>Double</code> array represented by s
*/
public static double[] parseDoubles(String s) {
List<Double> result = new ArrayList<Double>();
StringTokenizer tokenizer = new StringTokenizer(s, ",");
while(tokenizer.hasMoreTokens()) {
String d = tokenizer.nextToken();
result.add(Double.parseDouble(d));
}
return unbox(result.toArray(new Double[result.size()]));
}
/**
* Returns a new <code>Float</code> array initialized to the values
* represented by the specified <code>String</code> and separated by comma, as
* performed by the <code>valueOf</code> method of class <code>Float</code>.
*
* @param s the string to be parsed.
* @return a new <code>Float</code> array represented by s
*/
public static float[] parseFloats(String s) {
List<Float> result = new ArrayList<Float>();
StringTokenizer tokenizer = new StringTokenizer(s, ",");
while(tokenizer.hasMoreTokens()) {
String d = tokenizer.nextToken();
result.add(Float.parseFloat(d));
}
return unboxToFloat(result.toArray(new Float[result.size()]));
}
/**
* Converts the specified list of double objects to a list of float objects.
*
* @param values the list of double objects to be converted
* @return the converted list of float objects
*/
public static List<Float> convertToFloat(List<Double> values) {
List<Float> result = new ArrayList<Float>(values.size());
for(Double value : values) {
result.add(new Float(value));
}
return result;
}
/**
* Converts the specified array of doubles to an array of floats.
*
* @param values the array of doubles to be converted
* @return the converted array of floats
*/
public static float[] convertToFloat(double[] values) {
float[] result = new float[values.length];
for(int i = 0; i < values.length; i++) {
result[i] = (float) values[i];
}
return result;
}
/**
* Converts the specified array of doubles to an array of floats.
*
* @param values the array of doubles to be converted
* @return the converted array of floats
*/
public static double[] convertToDoubles(float[] values) {
double[] result = new double[values.length];
for(int i = 0; i < values.length; i++) {
result[i] = values[i];
}
return result;
}
/**
* Converts the specified list of Double objects to an array of doubles.
*
* @param values the list of Double objects to be converted
* @return the converted array of doubles
*/
public static double[] convertToDoubles(List<Double> values) {
double[] result = new double[values.size()];
for(int i = 0; i < result.length; i++) {
result[i] = values.get(i);
}
return result;
}
/**
* Prints the given list to the specified PrintStream. The list entries are
* separated by the specified separator. The last entry is not followed by a
* separator. Thus, if a newline is used as separator, it might make sense to
* print a newline to the PrintStream after calling this method.
*
* @param <O> object class
* @param list the list to be printed
* @param separator the separator to separate entries of the list
* @param out the target PrintStream
*/
public static <O> void print(List<O> list, String separator, PrintStream out) {
for(Iterator<O> iter = list.iterator(); iter.hasNext();) {
out.print(iter.next());
if(iter.hasNext()) {
out.print(separator);
}
}
}
/**
* Returns the index of the maximum of the given values. If no value is bigger
* than the first, the index of the first entry is returned.
*
* @param values the values to find the index of the maximum
* @return the index of the maximum in the given values
* @throws ArrayIndexOutOfBoundsException if <code>values.length==0</code>
*/
public static int getIndexOfMaximum(double[] values) throws ArrayIndexOutOfBoundsException {
int index = 0;
double max = values[index];
for(int i = 0; i < values.length; i++) {
if(values[i] > max) {
max = values[i];
index = i;
}
}
return index;
}
/**
* Returns a new <code>BitSet</code> initialized to the values represented by
* the specified <code>String</code> only containing 0 and 1 values.
*
* @param s the string to be parsed.
* @return a new <code>BitSet</code> represented by s
*/
public static BitSet parseBitSet(String s) {
try {
return parseBitSet(s.toCharArray());
}
catch(IllegalArgumentException e) {
throw new IllegalArgumentException("The specified String does not represent a bit set " + "containing only 0 and 1 values: " + s);
}
}
/**
* Returns a new <code>BitSet</code> initialized to the values represented by
* the specified <code>char</code> array only containing '0' and '1' values.
*
* @param s the char array to be parsed.
* @return a new <code>BitSet</code> represented by s
*/
public static BitSet parseBitSet(char[] s) {
BitSet result = new BitSet();
for(int i = 0; i < s.length; i++) {
if(s[i] == '1') {
result.set(i);
}
else if(s[i] != '0') {
throw new IllegalArgumentException("The specified String does not represent a bit set " + "containing only 0 and 1 values: " + String.valueOf(s));
}
}
return result;
}
/**
* Returns a string that represents the selected bits of the specified
* <code>BitSet</code>, while the first bit starts with 1. The selected bits
* are separated by the specified separator <code>sep</code>.
*
* If <code>sep</code> is ",", the result is suitable as a parameter
* for an IntListParameter.
*
* @param b the bit set to be parsed
* @param sep the separator
* @return a string representing the selected bits of the specified
* <code>BitSet</code>
*/
public static String parseSelectedBits(BitSet b, String sep) {
StringBuffer result = new StringBuffer();
for(int i = b.nextSetBit(0); i >= 0; i = b.nextSetBit(i + 1)) {
if(result.length() != 0) {
result.append(sep).append(i + 1);
}
else {
result.append((i + 1));
}
}
return result.toString();
}
/**
* Convert a bit set to a list of integers, representing bits that are set
*
* @param b Bitset
* @param off Offset, set to 0 to start counting at 0, 1 to start counting at
* 1.
* @return List
*/
public static List<Integer> convertBitSetToListInt(BitSet b, int off) {
List<Integer> list = new ArrayList<Integer>();
for(int i = b.nextSetBit(0); i >= 0; i = b.nextSetBit(i + 1)) {
list.add(i + off);
}
return list;
}
/**
* Creates a new BitSet of fixed cardinality with randomly set bits.
*
* @param cardinality the cardinality of the BitSet to create
* @param capacity the capacity of the BitSet to create - the randomly
* generated indices of the bits set to true will be uniformly
* distributed between 0 (inclusive) and capacity (exclusive)
* @param random a Random Object to create the sequence of indices set to true
* - the same number occurring twice or more is ignored but the already
* selected bit remains true
* @return a new BitSet with randomly set bits
*/
public static BitSet randomBitSet(int cardinality, int capacity, Random random) {
BitSet bitset = new BitSet(capacity);
while(bitset.cardinality() < cardinality) {
bitset.set(random.nextInt(capacity));
}
return bitset;
}
/**
* Provides a new DoubleVector as a projection on the specified attributes.
*
* If the given DoubleVector has already an ID not <code>null</code>, the same
* ID is set in the returned new DoubleVector. Nevertheless, the returned
* DoubleVector is not backed by the given DoubleVector, i.e., any changes
* affecting <code>v</code> after calling this method will not affect the
* newly returned DoubleVector.
*
* @param v a DoubleVector to project
* @param selectedAttributes the attributes selected for projection
* @return a new DoubleVector as a projection on the specified attributes
* @throws IllegalArgumentException if the given selected attributes specify
* an attribute as selected which is out of range for the given
* DoubleVector.
* @see DoubleVector#doubleValue(int)
*/
public static DoubleVector project(DoubleVector v, BitSet selectedAttributes) {
double[] newAttributes = new double[selectedAttributes.cardinality()];
int i = 0;
for(int d = selectedAttributes.nextSetBit(0); d >= 0; d = selectedAttributes.nextSetBit(d + 1)) {
newAttributes[i] = v.doubleValue(d + 1);
i++;
}
DoubleVector projectedVector = new DoubleVector(newAttributes);
return projectedVector;
}
/**
* Provides a new SparseFloatVector as a projection on the specified
* attributes.
*
* If the given SparseFloatVector has already an ID not <code>null</code>, the
* same ID is set in the returned new SparseFloatVector. Nevertheless, the
* returned SparseFloatVector is not backed by the given SparseFloatVector,
* i.e., any changes affecting <code>v</code> after calling this method will
* not affect the newly returned SparseFloatVector.
*
* @param v a SparseFloatVector to project
* @param selectedAttributes the attributes selected for projection
* @return a new SparseFloatVector as a projection on the specified attributes
* @throws IllegalArgumentException if the given selected attributes specify
* an attribute as selected which is out of range for the given
* SparseFloatVector.
*/
public static SparseFloatVector project(SparseFloatVector v, BitSet selectedAttributes) {
Map<Integer, Float> values = new HashMap<Integer, Float>(selectedAttributes.cardinality(), 1);
for(int d = selectedAttributes.nextSetBit(0); d >= 0; d = selectedAttributes.nextSetBit(d + 1)) {
if(v.getValue(d + 1) != 0.0f) {
values.put(d, v.getValue(d + 1));
}
}
SparseFloatVector projectedVector = new SparseFloatVector(values, selectedAttributes.cardinality());
return projectedVector;
}
/**
* Returns the index of the n<sup>th</sup> set bit in the given BitSet. For
* the parameter <code>nthSetBit</code>, following condition is assumed:
* <code>1 ≤ nthSetBit ≤ bitset.cardinality()</code>. Otherwise, i.e.,
* if the Bitset contains less than <code>nthSetBit</code> set bits or
* <code>nthSetBit</code> is not a positive number, the method throws an
* IllegalArgumentException.
*
* The worstcase runtime complexity of this method is in <i>O(
* <code>bitset.cardinality()</code>)</i>.
*
* @param bitset the BitSet to derive the index of the n<sup>th</sup> set bit
* in
* @param nthSetBit which set bit to derive the index of
* @return the index of the n<sup>th</sup> set bit in the given BitSet
* @throws IllegalArgumentException if the Bitset contains less than
* <code>nthSetBit</code> set bits or <code>nthSetBit</code> is not a
* positive number
*/
public static int indexOfNthSetBit(BitSet bitset, int nthSetBit) throws IllegalArgumentException {
if(nthSetBit < 1 || nthSetBit > bitset.cardinality()) {
throw new IllegalArgumentException("Parameter nthSetBit out of range: nthSetBit=" + nthSetBit + ", bitset.cardinality=" + bitset.cardinality());
}
int i = 0;
int index = -1;
for(int d = bitset.nextSetBit(0); d >= 0 && i < nthSetBit; d = bitset.nextSetBit(d + 1)) {
i++;
index = d;
}
return index;
}
/**
* Provides the intersection of the two specified sets in the given result
* set.
*
* @param <O> object class
* @param s1 the first set
* @param s2 the second set
* @param result the result set
*/
public static <O> void intersection(Set<O> s1, Set<O> s2, Set<O> result) {
for(O object : s1) {
if(s2.contains(object)) {
result.add(object);
}
}
}
/**
* Converts the specified positive integer value into a bit representation,
* where bit 0 denotes 2<sup>0</sup>, bit 1 denotes 2<sup>1</sup> etc.
*
* @param n the positive integer value to be converted
* @return the specified integer value into a bit representation
*/
public static BitSet int2Bit(int n) {
if(n < 0) {
throw new IllegalArgumentException("Parameter n hast to be greater than or equal to zero!");
}
BitSet result = new BitSet();
int i = 0;
while(n > 0) {
boolean rest = (n % 2 == 1);
if(rest) {
result.set(i);
}
n = n / 2;
i++;
}
return result;
}
/**
* Joins the specified arrays.
*
* @param array1 the first array
* @param array2 the second array
* @return a new array containing the entries of <code>array1</code> and the
* <code>array2</code>.
*/
public static String[] joinArray(String[] array1, String[] array2) {
String[] newArray = new String[array1.length + array2.length];
System.arraycopy(array1, 0, newArray, 0, array1.length);
System.arraycopy(array2, 0, newArray, array1.length, array2.length);
return newArray;
}
/**
* Adds the entries of the specified array to the end of the given list.
*
* @param <O> object class
* @param list the list
* @param array the array containing the objects to be added to the list
*/
public static <O> void addToList(List<O> list, O[] array) {
for(O object : array) {
list.add(object);
}
}
/**
* Search an (unsorted) array linearly for an object.
*
* @param arr Array to search
* @param ref Object to search for
* @return Index of object or -1 if not found.
*/
public static int arrayFind(String[] arr, Object ref) {
for(int index = 0; index < arr.length; index++) {
if(ref.equals(arr[index])) {
return index;
}
}
return -1;
}
/**
* Mix multiple hashcodes into one.
*
* @param hash Hashcodes to mix
* @return Mixed hash code
*/
public static final int mixHashCodes(int... hash) {
final long prime = 2654435761L;
if(hash.length == 0) {
return 0;
}
long result = hash[0];
for (int i = 1; i < hash.length; i++) {
result = result * prime + hash[i];
}
return (int) result;
}
/**
* This class is a virtual collection based on masking an array list using a
* bit mask.
*
* @author Erich Schubert
*
* @apiviz.stereotype decorator
* @apiviz.composedOf java.util.ArrayList
* @apiviz.composedOf java.util.BitSet
*
* @param <T> Object type
*/
public static class MaskedArrayList<T> extends AbstractCollection<T> implements Collection<T> {
/**
* Data storage
*/
protected ArrayList<T> data;
/**
* The bitmask used for masking
*/
protected BitSet bits;
/**
* Flag whether to iterator over set or unset values.
*/
protected boolean inverse = false;
/**
* Constructor.
*
* @param data Data
* @param bits Bitset to use as mask
* @param inverse Flag to inverse the masking rule
*/
public MaskedArrayList(ArrayList<T> data, BitSet bits, boolean inverse) {
super();
this.data = data;
this.bits = bits;
this.inverse = inverse;
}
@Override
public boolean add(T e) {
throw new UnsupportedOperationException();
}
@Override
public Iterator<T> iterator() {
if(inverse) {
return new InvItr();
}
else {
return new Itr();
}
}
@Override
public int size() {
if(inverse) {
return data.size() - bits.cardinality();
}
else {
return bits.cardinality();
}
}
/**
* Iterator over set bits
*
* @author Erich Schubert
*
* @apiviz.exclude
*/
protected class Itr implements Iterator<T> {
/**
* Next position.
*/
private int pos;
/**
* Constructor
*/
protected Itr() {
this.pos = bits.nextSetBit(0);
}
@Override
public boolean hasNext() {
return (pos >= 0) && (pos < data.size());
}
@Override
public T next() {
T cur = data.get(pos);
pos = bits.nextSetBit(pos + 1);
return cur;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
/**
* Iterator over unset elements.
*
* @author Erich Schubert
*
* @apiviz.exclude
*/
protected class InvItr implements Iterator<T> {
/**
* Next unset position.
*/
private int pos;
/**
* Constructor
*/
protected InvItr() {
this.pos = bits.nextClearBit(0);
}
@Override
public boolean hasNext() {
return (pos >= 0) && (pos < data.size());
}
@Override
public T next() {
T cur = data.get(pos);
pos = bits.nextClearBit(pos + 1);
return cur;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
}
}