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

Class AbstractSpatialSorter

java.lang.Object

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

All Implemented Interfaces:

SpatialSorter

Direct Known Subclasses:

BinarySplitSpatialSorter, HilbertSpatialSorter, PeanoSpatialSorter, ZCurveSpatialSorter

public abstract class AbstractSpatialSorter
extends Object
implements SpatialSorter

Abstract base class for spatial sorters, offering shared functionality.

Author:

Erich Schubert

Constructor Summary

Constructors

Constructor and Description
AbstractSpatialSorter() Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
static double[]	computeMinMax(List<? extends SpatialComparable> objs) Compute the minimum and maximum for each dimension.
private double	getMinPlusMaxObject(List<? extends SpatialComparable> objs, int s, int dim) Compute getMin(dim) + getMax(dim) for the spatial object.
protected <T extends SpatialComparable> int	pivotizeList1D(List<T> 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.
<T extends SpatialComparable> void	sort(List<T> objs) Partitions the specified feature vectors

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

sort

Constructor Detail

AbstractSpatialSorter

public AbstractSpatialSorter()

Constructor.

Method Detail

sort

public <T extends SpatialComparable> void sort(List<T> objs)

Description copied from interface: SpatialSorter

Partitions the specified feature vectors

Specified by:

sort in interface SpatialSorter

Type Parameters:

T - actual type we sort

Parameters:

objs - the spatial objects to be sorted

pivotizeList1D

protected <T extends SpatialComparable> int pivotizeList1D(List<T> 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 elments in the interval [start: end[ are sorted!

Type Parameters:

T - Object type

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 double getMinPlusMaxObject(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

computeMinMax

public static double[] computeMinMax(List<? extends SpatialComparable> objs)

Compute the minimum and maximum for each dimension.

Parameters:

objs - Objects

Returns:

Array of min, max pairs (length = 2 * dim)