de.lmu.ifi.dbs.elki.math.spacefillingcurves

Class ZCurveSpatialSorter

java.lang.Object

de.lmu.ifi.dbs.elki.math.spacefillingcurves.ZCurveSpatialSorter

All Implemented Interfaces:

SpatialSorter

public class ZCurveSpatialSorter
extends java.lang.Object
implements SpatialSorter

Class to sort the data set by their Z-index, without doing a full materialization of the Z indexes.

Since:

0.5.0

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	ZCurveSpatialSorter.Parameterizer Parameterization class.

Field Summary

Fields

Modifier and Type	Field and Description
static ZCurveSpatialSorter	STATIC Static instance.
private static double	STOPVAL Stopping threshold.

Constructor Summary

Constructors

Constructor and Description
ZCurveSpatialSorter() Constructor, use STATIC instead.

Method Summary

Modifier and Type	Method and Description
private static double	getMinPlusMaxObject(java.util.List<? extends SpatialComparable> objs, int s, int dim) Compute getMin(dim) + getMax(dim) for the spatial object.
protected static int	pivotizeList1D(java.util.List<? extends SpatialComparable> objs, int start, int end, int dim, double threshold, boolean desc) "Pivotize" the list, such that all elements before the given position are less than, all elements after the position are larger than the threshold value in the given dimension.
void	sort(java.util.List<? extends SpatialComparable> objs, int start, int end, double[] minmax, int[] dims) Sort part of the list (start to end).
protected void	zSort(java.util.List<? extends SpatialComparable> objs, int start, int end, double[] mms, int[] dims, int depth) The actual Z sorting function

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface de.lmu.ifi.dbs.elki.math.spacefillingcurves.SpatialSorter

computeMinMax, sort

Field Detail

STATIC

public static final ZCurveSpatialSorter STATIC

Static instance.

STOPVAL

private static final double STOPVAL

Stopping threshold.

See Also:

Constant Field Values

Constructor Detail

ZCurveSpatialSorter

public ZCurveSpatialSorter()

Constructor, use STATIC instead.

Method Detail

sort

public void sort(java.util.List<? extends SpatialComparable> objs,
                 int start,
                 int end,
                 double[] minmax,
                 int[] dims)

Description copied from interface: SpatialSorter

Sort part of the list (start to end).

Specified by:

sort in interface SpatialSorter

Parameters:

objs - the spatial objects to be sorted

start - First index to sort (e.g. 0)

end - End of range (e.g. site())

minmax - Array with dim pairs of (min, max) of value ranges

dims - Dimensions to sort by, for indexing vectors and minmax.

zSort

protected void zSort(java.util.List<? extends SpatialComparable> objs,
                     int start,
                     int end,
                     double[] mms,
                     int[] dims,
                     int depth)

The actual Z sorting function

Parameters:

objs - Objects to sort

start - Start

end - End

mms - Min-Max value ranges

dims - Dimensions to process

depth - Current dimension

pivotizeList1D

protected static int pivotizeList1D(java.util.List<? extends SpatialComparable> objs,
                                    int start,
                                    int end,
                                    int dim,
                                    double threshold,
                                    boolean desc)

"Pivotize" the list, such that all elements before the given position are less than, all elements after the position are larger than the threshold value in the given dimension. (desc inverts the sorting!) Only the elements in the interval [start: end[ are sorted!

Parameters:

objs - List of objects

start - Start of sorting range

end - End of sorting range

dim - Dimension to sort by

threshold - Threshold value

desc - Inversion flag

Returns:

Pivot position

getMinPlusMaxObject

private static double getMinPlusMaxObject(java.util.List<? extends SpatialComparable> objs,
                                          int s,
                                          int dim)

Compute getMin(dim) + getMax(dim) for the spatial object.

Parameters:

objs - Objects

s - index

dim - Dimensionality

Returns:

Min+Max