diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/math/spacefillingcurves')
7 files changed, 82 insertions, 73 deletions
diff --git a/src/de/lmu/ifi/dbs/elki/math/spacefillingcurves/AbstractSpatialSorter.java b/src/de/lmu/ifi/dbs/elki/math/spacefillingcurves/AbstractSpatialSorter.java index 942fe64b..7c1265dd 100644 --- a/src/de/lmu/ifi/dbs/elki/math/spacefillingcurves/AbstractSpatialSorter.java +++ b/src/de/lmu/ifi/dbs/elki/math/spacefillingcurves/AbstractSpatialSorter.java @@ -59,37 +59,37 @@ public abstract class AbstractSpatialSorter implements SpatialSorter { * @param dim Dimension to sort by * @param threshold Threshold value * @param desc Inversion flag + * @param <T> Object type * @return Pivot position */ protected <T extends SpatialComparable> int pivotizeList1D(List<T> objs, int start, int end, int dim, double threshold, boolean desc) { threshold = 2 * threshold; // faster int s = start, e = end; - while(s < e) { - if(!desc) { + while (s < e) { + if (!desc) { double sminmax = getMinPlusMaxObject(objs, s, dim); - while((sminmax < threshold) && s + 1 <= e && s + 1 < end) { + while ((sminmax < threshold) && s + 1 <= e && s + 1 < end) { s++; sminmax = getMinPlusMaxObject(objs, s, dim); } double eminmax = getMinPlusMaxObject(objs, e - 1, dim); - while((eminmax >= threshold) && s < e - 1 && start < e - 1) { + while ((eminmax >= threshold) && s < e - 1 && start < e - 1) { e--; eminmax = getMinPlusMaxObject(objs, e - 1, dim); } - } - else { + } else { double sminmax = getMinPlusMaxObject(objs, s, dim); - while((sminmax > threshold) && s + 1 <= e && s + 1 < end) { + while ((sminmax > threshold) && s + 1 <= e && s + 1 < end) { s++; sminmax = getMinPlusMaxObject(objs, s, dim); } double eminmax = getMinPlusMaxObject(objs, e - 1, dim); - while((eminmax <= threshold) && s < e - 1 && start < e - 1) { + while ((eminmax <= threshold) && s < e - 1 && start < e - 1) { e--; eminmax = getMinPlusMaxObject(objs, e - 1, dim); } } - if(s >= e) { + if (s >= e) { assert (s == e); break; } @@ -102,7 +102,7 @@ public abstract class AbstractSpatialSorter implements SpatialSorter { } /** - * Compute getMin(dim) + getMax(dim) for the spatial object + * Compute getMin(dim) + getMax(dim) for the spatial object. * * @param objs Objects * @param s index @@ -120,25 +120,25 @@ public abstract class AbstractSpatialSorter implements SpatialSorter { * @param objs Objects * @return Array of min, max pairs (length = 2 * dim) */ - public static <T extends SpatialComparable> double[] computeMinMax(List<T> objs) { + public static double[] computeMinMax(List<? extends SpatialComparable> objs) { final int dim = objs.get(0).getDimensionality(); // Compute min and max for each dimension: - double[] mm = new double[dim * 2]; + double[] mm = new double[dim << 1]; { - for(int d = 0; d < dim; d++) { - mm[d * 2] = Double.POSITIVE_INFINITY; - mm[d * 2 + 1] = Double.NEGATIVE_INFINITY; + for (int d = 0; d < dim; d++) { + mm[d << 1] = Double.POSITIVE_INFINITY; + mm[(d << 1) + 1] = Double.NEGATIVE_INFINITY; } - for(SpatialComparable obj : objs) { - for(int d = 0; d < dim; d++) { - mm[2 * d] = Math.min(mm[2 * d], obj.getMin(d + 1)); - mm[2 * d + 1] = Math.max(mm[2 * d + 1], obj.getMax(d + 1)); + for (SpatialComparable obj : objs) { + for (int d = 0; d < dim; d++) { + mm[d << 1] = Math.min(mm[d << 1], obj.getMin(d)); + mm[(d << 1) + 1] = Math.max(mm[(d << 1) + 1], obj.getMax(d)); } } - for(int d = 0; d < dim; d++) { - assert (mm[2 * d] <= mm[2 * d + 1]); + for (int d = 0; d < dim; d++) { + assert (mm[d << 1] <= mm[(d << 1) + 1]); } } return mm; } -}
\ No newline at end of file +} diff --git a/src/de/lmu/ifi/dbs/elki/math/spacefillingcurves/BinarySplitSpatialSorter.java b/src/de/lmu/ifi/dbs/elki/math/spacefillingcurves/BinarySplitSpatialSorter.java index 0b45022c..1ba58511 100644 --- a/src/de/lmu/ifi/dbs/elki/math/spacefillingcurves/BinarySplitSpatialSorter.java +++ b/src/de/lmu/ifi/dbs/elki/math/spacefillingcurves/BinarySplitSpatialSorter.java @@ -73,6 +73,7 @@ public class BinarySplitSpatialSorter extends AbstractSpatialSorter { * @param curdim Current dimension * @param dims Number of dimensions * @param comp Comparator to use + * @param <T> Object type */ private <T extends SpatialComparable> void binarySplitSort(List<T> objs, final int start, final int end, int curdim, final int dims, DimC comp) { final int mid = start + ((end - start) >>> 1); @@ -80,7 +81,7 @@ public class BinarySplitSpatialSorter extends AbstractSpatialSorter { comp.dim = curdim; QuickSelect.quickSelect(objs, comp, start, end, mid); // Recurse - final int nextdim = (curdim % dims) + 1; + final int nextdim = (curdim + 1) % dims; if(start < mid - 1) { binarySplitSort(objs, start, mid, nextdim, dims, comp); } @@ -100,6 +101,9 @@ public class BinarySplitSpatialSorter extends AbstractSpatialSorter { * @apiviz.exclude */ private static class DimC implements Comparator<SpatialComparable> { + /** + * Dimension. + */ public int dim = -1; @Override diff --git a/src/de/lmu/ifi/dbs/elki/math/spacefillingcurves/HilbertSpatialSorter.java b/src/de/lmu/ifi/dbs/elki/math/spacefillingcurves/HilbertSpatialSorter.java index 9b4af341..317e47c1 100644 --- a/src/de/lmu/ifi/dbs/elki/math/spacefillingcurves/HilbertSpatialSorter.java +++ b/src/de/lmu/ifi/dbs/elki/math/spacefillingcurves/HilbertSpatialSorter.java @@ -61,19 +61,19 @@ public class HilbertSpatialSorter extends AbstractSpatialSorter { final int dim = minmax.length >> 1; List<HilbertRef<T>> tmp = new ArrayList<HilbertRef<T>>(end - start); int[] buf = new int[dim]; - for(int i = start; i < end; i++) { + for (int i = start; i < end; i++) { T v = objs.get(i); // Convert into integers - for(int d = 0; d < dim; d++) { - double val = (v.getMin(d + 1) + v.getMax(d + 1)) / 2; - val = Integer.MAX_VALUE * ((val - minmax[2 * d]) / (minmax[2 * d + 1] - minmax[2 * d])); + for (int d = 0, d2 = 0; d < dim; d++, d2 += 2) { + double val = (v.getMin(d) + v.getMax(d)) * .5; + val = Integer.MAX_VALUE * ((val - minmax[d2]) / (minmax[d2 + 1] - minmax[d2])); buf[d] = (int) val; } tmp.add(new HilbertRef<T>(v, coordinatesToHilbert(buf, Integer.SIZE - 1, 1))); } // Sort and copy back Collections.sort(tmp); - for(int i = start; i < end; i++) { + for (int i = start; i < end; i++) { objs.set(i, tmp.get(i - start).vec); } } @@ -86,19 +86,20 @@ public class HilbertSpatialSorter extends AbstractSpatialSorter { */ private static class HilbertRef<T extends SpatialComparable> implements Comparable<HilbertRef<T>> { /** - * The referenced object + * The referenced object. */ protected T vec; /** - * Hilbert representation + * Hilbert representation. */ protected long[] bits; /** * Constructor. * - * @param vec + * @param vec Vector + * @param bits Bit representation */ protected HilbertRef(T vec, long[] bits) { super(); @@ -118,6 +119,7 @@ public class HilbertSpatialSorter extends AbstractSpatialSorter { * * @param coords Original coordinates * @param bitsperdim Number of bits to use. + * @param offset offset * @return Hilbert address */ public static long[] coordinatesToHilbert(long[] coords, int bitsperdim, int offset) { @@ -127,7 +129,7 @@ public class HilbertSpatialSorter extends AbstractSpatialSorter { int rotation = 0; long[] refl = BitsUtil.zero(numdim); - for(int i = 0; i < bitsperdim; i++) { + for (int i = 0; i < bitsperdim; i++) { final long[] hist = interleaveBits(coords, i + offset); // System.err.println(BitsUtil.toString(hist, // numdim)+" rot:"+rotation+" refl: "+BitsUtil.toString(refl, numdim)); @@ -141,7 +143,7 @@ public class HilbertSpatialSorter extends AbstractSpatialSorter { // numbits)+" bits: "+BitsUtil.toString(bits, numdim)); refl = hist; BitsUtil.flipI(refl, rotation); - if(!BitsUtil.get(bits, 0)) { + if (!BitsUtil.get(bits, 0)) { BitsUtil.flipI(refl, (nextrot - 1 + numdim) % numdim); } rotation = nextrot; @@ -151,11 +153,12 @@ public class HilbertSpatialSorter extends AbstractSpatialSorter { } /** - * Interleave one int per dimension (using the "bitsperdim" highest bits) to - * a hilbert address. + * Interleave one int per dimension (using the "bitsperdim" highest bits) to a + * hilbert address. * * @param coords Original coordinates * @param bitsperdim Number of bits to use. + * @param offset offset * @return Hilbert address */ public static long[] coordinatesToHilbert(int[] coords, int bitsperdim, int offset) { @@ -165,7 +168,7 @@ public class HilbertSpatialSorter extends AbstractSpatialSorter { int rotation = 0; long[] refl = BitsUtil.zero(numdim); - for(int i = 0; i < bitsperdim; i++) { + for (int i = 0; i < bitsperdim; i++) { final long[] hist = interleaveBits(coords, i + offset); // System.err.println(BitsUtil.toString(hist, // numdim)+" rot:"+rotation+" refl: "+BitsUtil.toString(refl, numdim)); @@ -179,7 +182,7 @@ public class HilbertSpatialSorter extends AbstractSpatialSorter { // numbits)+" bits: "+BitsUtil.toString(bits, numdim)); refl = hist; BitsUtil.flipI(refl, rotation); - if(!BitsUtil.get(bits, 0)) { + if (!BitsUtil.get(bits, 0)) { BitsUtil.flipI(refl, (nextrot - 1 + numdim) % numdim); } rotation = nextrot; @@ -194,6 +197,7 @@ public class HilbertSpatialSorter extends AbstractSpatialSorter { * * @param coords Original coordinates * @param bitsperdim Number of bits to use. + * @param offset offset * @return Hilbert address */ public static long[] coordinatesToHilbert(short[] coords, int bitsperdim, int offset) { @@ -203,7 +207,7 @@ public class HilbertSpatialSorter extends AbstractSpatialSorter { int rotation = 0; long[] refl = BitsUtil.zero(numdim); - for(int i = 0; i < bitsperdim; i++) { + for (int i = 0; i < bitsperdim; i++) { final long[] hist = interleaveBits(coords, i + offset); // System.err.println(BitsUtil.toString(hist, // numdim)+" rot:"+rotation+" refl: "+BitsUtil.toString(refl, numdim)); @@ -217,7 +221,7 @@ public class HilbertSpatialSorter extends AbstractSpatialSorter { // numbits)+" bits: "+BitsUtil.toString(bits, numdim)); refl = hist; BitsUtil.flipI(refl, rotation); - if(!BitsUtil.get(bits, 0)) { + if (!BitsUtil.get(bits, 0)) { BitsUtil.flipI(refl, (nextrot - 1 + numdim) % numdim); } rotation = nextrot; @@ -232,16 +236,17 @@ public class HilbertSpatialSorter extends AbstractSpatialSorter { * * @param coords Original coordinates * @param bitsperdim Number of bits to use. + * @param offset offset * @return Hilbert address */ public static long[] coordinatesToHilbert(byte[] coords, int bitsperdim, int offset) { final int numdim = coords.length; final int numbits = numdim * bitsperdim; final long[] output = BitsUtil.zero(numbits); - + int rotation = 0; long[] refl = BitsUtil.zero(numdim); - for(int i = 0; i < bitsperdim; i++) { + for (int i = 0; i < bitsperdim; i++) { final long[] hist = interleaveBits(coords, i + offset); // System.err.println(BitsUtil.toString(hist, // numdim)+" rot:"+rotation+" refl: "+BitsUtil.toString(refl, numdim)); @@ -255,12 +260,12 @@ public class HilbertSpatialSorter extends AbstractSpatialSorter { // numbits)+" bits: "+BitsUtil.toString(bits, numdim)); refl = hist; BitsUtil.flipI(refl, rotation); - if(!BitsUtil.get(bits, 0)) { + if (!BitsUtil.get(bits, 0)) { BitsUtil.flipI(refl, (nextrot - 1 + numdim) % numdim); } rotation = nextrot; } - + return output; } @@ -276,8 +281,8 @@ public class HilbertSpatialSorter extends AbstractSpatialSorter { final long[] bitset = BitsUtil.zero(numdim); // convert longValues into zValues final long mask = 1L << 63 - iter; - for(int dim = 0; dim < numdim; dim++) { - if((coords[dim] & mask) != 0) { + for (int dim = 0; dim < numdim; dim++) { + if ((coords[dim] & mask) != 0) { BitsUtil.setI(bitset, dim); } } @@ -296,8 +301,8 @@ public class HilbertSpatialSorter extends AbstractSpatialSorter { final long[] bitset = BitsUtil.zero(numdim); // convert longValues into zValues final long mask = 1L << 31 - iter; - for(int dim = 0; dim < numdim; dim++) { - if((coords[dim] & mask) != 0) { + for (int dim = 0; dim < numdim; dim++) { + if ((coords[dim] & mask) != 0) { BitsUtil.setI(bitset, dim); } } @@ -316,8 +321,8 @@ public class HilbertSpatialSorter extends AbstractSpatialSorter { final long[] bitset = BitsUtil.zero(numdim); // convert longValues into zValues final long mask = 1L << 15 - iter; - for(int dim = 0; dim < numdim; dim++) { - if((coords[dim] & mask) != 0) { + for (int dim = 0; dim < numdim; dim++) { + if ((coords[dim] & mask) != 0) { BitsUtil.setI(bitset, dim); } } @@ -336,11 +341,11 @@ public class HilbertSpatialSorter extends AbstractSpatialSorter { final long[] bitset = BitsUtil.zero(numdim); // convert longValues into zValues final long mask = 1L << 7 - iter; - for(int dim = 0; dim < numdim; dim++) { - if((coords[dim] & mask) != 0) { + for (int dim = 0; dim < numdim; dim++) { + if ((coords[dim] & mask) != 0) { BitsUtil.setI(bitset, dim); } } return bitset; } -}
\ No newline at end of file +} diff --git a/src/de/lmu/ifi/dbs/elki/math/spacefillingcurves/PeanoSpatialSorter.java b/src/de/lmu/ifi/dbs/elki/math/spacefillingcurves/PeanoSpatialSorter.java index 50cf1946..865197ae 100644 --- a/src/de/lmu/ifi/dbs/elki/math/spacefillingcurves/PeanoSpatialSorter.java +++ b/src/de/lmu/ifi/dbs/elki/math/spacefillingcurves/PeanoSpatialSorter.java @@ -95,6 +95,7 @@ public class PeanoSpatialSorter extends AbstractSpatialSorter { * @param desc Current ordering */ protected <T extends SpatialComparable> void peanoSort(List<T> objs, int start, int end, double[] mms, int dim, BitSet bits, boolean desc) { + final int dims = mms.length >> 1; // Find the splitting points. final double min = mms[2 * dim], max = mms[2 * dim + 1]; final double tfirst = (min + min + max) / 3.; @@ -116,14 +117,14 @@ public class PeanoSpatialSorter extends AbstractSpatialSorter { // Split the data set into three parts int fsplit, ssplit; if(!inv) { - fsplit = pivotizeList1D(objs, start, end, dim + 1, tfirst, false); - ssplit = (fsplit < end - 1) ? pivotizeList1D(objs, fsplit, end, dim + 1, tsecond, false) : fsplit; + fsplit = pivotizeList1D(objs, start, end, dim, tfirst, false); + ssplit = (fsplit < end - 1) ? pivotizeList1D(objs, fsplit, end, dim, tsecond, false) : fsplit; } else { - fsplit = pivotizeList1D(objs, start, end, dim + 1, tsecond, true); - ssplit = (fsplit < end - 1) ? pivotizeList1D(objs, fsplit, end, dim + 1, tfirst, true) : fsplit; + fsplit = pivotizeList1D(objs, start, end, dim, tsecond, true); + ssplit = (fsplit < end - 1) ? pivotizeList1D(objs, fsplit, end, dim, tfirst, true) : fsplit; } - int nextdim = (dim + 1) % objs.get(0).getDimensionality(); + int nextdim = (dim + 1) % dims; // Do we need to update the min/max values? if(start < fsplit - 1) { mms[2 * dim] = !inv ? min : tsecond; diff --git a/src/de/lmu/ifi/dbs/elki/math/spacefillingcurves/SpatialSorter.java b/src/de/lmu/ifi/dbs/elki/math/spacefillingcurves/SpatialSorter.java index 2473dff5..fe23a854 100644 --- a/src/de/lmu/ifi/dbs/elki/math/spacefillingcurves/SpatialSorter.java +++ b/src/de/lmu/ifi/dbs/elki/math/spacefillingcurves/SpatialSorter.java @@ -39,7 +39,7 @@ public interface SpatialSorter { * @param <T> actual type we sort * @param objs the spatial objects to be sorted */ - public <T extends SpatialComparable> void sort(List<T> objs); + <T extends SpatialComparable> void sort(List<T> objs); /** * Sort part of the list (start to end). @@ -50,5 +50,5 @@ public interface SpatialSorter { * @param end End of range (e.g. <code>site()</code>) * @param minmax Array with dim pairs of (min, max) of value ranges */ - public <T extends SpatialComparable> void sort(List<T> objs, int start, int end, double[] minmax); -} + <T extends SpatialComparable> void sort(List<T> objs, int start, int end, double[] minmax); +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/math/spacefillingcurves/ZCurveSpatialSorter.java b/src/de/lmu/ifi/dbs/elki/math/spacefillingcurves/ZCurveSpatialSorter.java index b8fc63bd..c5a91699 100644 --- a/src/de/lmu/ifi/dbs/elki/math/spacefillingcurves/ZCurveSpatialSorter.java +++ b/src/de/lmu/ifi/dbs/elki/math/spacefillingcurves/ZCurveSpatialSorter.java @@ -68,7 +68,7 @@ public class ZCurveSpatialSorter extends AbstractSpatialSorter { return; } } - int split = pivotizeList1D(objs, start, end, dim + 1, spos, false); + int split = pivotizeList1D(objs, start, end, dim, spos, false); assert (start <= split && split <= end); int nextdim = (dim + 1) % objs.get(0).getDimensionality(); // LoggingUtil.warning("dim: " + dim + " min: " + min + " split: " + spos + diff --git a/src/de/lmu/ifi/dbs/elki/math/spacefillingcurves/ZCurveTransformer.java b/src/de/lmu/ifi/dbs/elki/math/spacefillingcurves/ZCurveTransformer.java index 108721eb..26137cb3 100644 --- a/src/de/lmu/ifi/dbs/elki/math/spacefillingcurves/ZCurveTransformer.java +++ b/src/de/lmu/ifi/dbs/elki/math/spacefillingcurves/ZCurveTransformer.java @@ -30,7 +30,7 @@ import de.lmu.ifi.dbs.elki.data.NumberVector; import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.relation.Relation; -import de.lmu.ifi.dbs.elki.utilities.DatabaseUtil; +import de.lmu.ifi.dbs.elki.database.relation.RelationUtil; /** * Class to transform a relation to its Z coordinates. @@ -39,17 +39,17 @@ import de.lmu.ifi.dbs.elki.utilities.DatabaseUtil; */ public class ZCurveTransformer { /** - * Maximum values in each dimension + * Maximum values in each dimension. */ private final double[] maxValues; /** - * Minimum values in each dimension + * Minimum values in each dimension. */ private final double[] minValues; /** - * Dimensionality + * Dimensionality. */ private final int dimensionality; @@ -59,8 +59,8 @@ public class ZCurveTransformer { * @param relation Relation to transform * @param ids IDs subset to process */ - public ZCurveTransformer(Relation<? extends NumberVector<?, ?>> relation, DBIDs ids) { - this.dimensionality = DatabaseUtil.dimensionality(relation); + public ZCurveTransformer(Relation<? extends NumberVector<?>> relation, DBIDs ids) { + this.dimensionality = RelationUtil.dimensionality(relation); this.minValues = new double[dimensionality]; this.maxValues = new double[dimensionality]; @@ -68,9 +68,9 @@ public class ZCurveTransformer { Arrays.fill(minValues, Double.POSITIVE_INFINITY); Arrays.fill(maxValues, Double.NEGATIVE_INFINITY); for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - NumberVector<?, ?> vector = relation.get(iter); + NumberVector<?> vector = relation.get(iter); for(int dim = 0; dim < dimensionality; ++dim) { - double dimValue = vector.doubleValue(dim + 1); + double dimValue = vector.doubleValue(dim); minValues[dim] = Math.min(minValues[dim], dimValue); maxValues[dim] = Math.max(maxValues[dim], dimValue); } @@ -84,7 +84,7 @@ public class ZCurveTransformer { * @return Z curve value as bigint */ @Deprecated - public BigInteger asBigInteger(NumberVector<?, ?> vector) { + public BigInteger asBigInteger(NumberVector<?> vector) { return new BigInteger(asByteArray(vector)); } @@ -94,13 +94,13 @@ public class ZCurveTransformer { * @param vector Vector to transform * @return Z curve value as byte array */ - public byte[] asByteArray(NumberVector<?, ?> vector) { + public byte[] asByteArray(NumberVector<?> vector) { final long[] longValueList = new long[dimensionality]; for(int dim = 0; dim < dimensionality; ++dim) { final double minValue = minValues[dim]; final double maxValue = maxValues[dim]; - double dimValue = vector.doubleValue(dim + 1); + double dimValue = vector.doubleValue(dim); dimValue = (dimValue - minValue) / (maxValue - minValue); longValueList[dim] = (long) (dimValue * (Long.MAX_VALUE)); @@ -120,5 +120,4 @@ public class ZCurveTransformer { } return bytes; } - }
\ No newline at end of file |