Package org.h2.tools

Class MultiDimension

java.lang.Object

org.h2.tools.MultiDimension

All Implemented Interfaces:

java.util.Comparator<long[]>

public class MultiDimension
extends java.lang.Object
implements java.util.Comparator<long[]>

A tool to help an application execute multi-dimensional range queries. The algorithm used is database independent, the only requirement is that the engine supports a range index (for example b-tree).

Field Summary

Fields

Modifier and Type	Field	Description
private static MultiDimension	INSTANCE

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	MultiDimension()

Method Summary

Modifier and Type	Method	Description
private void	addMortonRanges(java.util.ArrayList<long[]> list, int[] min, int[] max, int len, int level)
private void	combineEntries(java.util.ArrayList<long[]> list, int total)	Combine entries if the size of the list is too large.
int	compare(long[] a, long[] b)
int	deinterleave(int dimensions, long scalar, int dim)	Gets one of the original multi-dimensional values from a scalar value.
private static int	findMiddle(int a, int b)
java.lang.String	generatePreparedQuery(java.lang.String table, java.lang.String scalarColumn, java.lang.String[] columns)	Generates an optimized multi-dimensional range query.
private static int	getBitsPerValue(int dimensions)
static MultiDimension	getInstance()	Get the singleton.
int	getMaxValue(int dimensions)	Get the maximum value for the given dimension count.
private long[][]	getMortonRanges(int[] min, int[] max)	Gets a list of ranges to be searched for a multi-dimensional range query where min <= value <= max.
java.sql.ResultSet	getResult(java.sql.PreparedStatement prep, int[] min, int[] max)	Executes a prepared query that was generated using generatePreparedQuery.
private static int	getSize(int[] min, int[] max, int len)
long	interleave(int... values)	Convert the multi-dimensional value into a one-dimensional (scalar) value.
long	interleave(int x, int y)	Convert the two-dimensional value into a one-dimensional (scalar) value.
int	normalize(int dimensions, double value, double min, double max)	Normalize a value so that it is between the minimum and maximum for the given number of dimensions.
private static int	roundUp(int x, int blockSizePowerOf2)

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.Comparator

equals, reversed, thenComparing, thenComparing, thenComparing, thenComparingDouble, thenComparingInt, thenComparingLong

Field Detail

INSTANCE

private static final MultiDimension INSTANCE

Constructor Detail

MultiDimension

protected MultiDimension()

Method Detail

getInstance

public static MultiDimension getInstance()

Get the singleton.

Returns:

the singleton

normalize

public int normalize(int dimensions,
                     double value,
                     double min,
                     double max)

Normalize a value so that it is between the minimum and maximum for the given number of dimensions.

Parameters:

dimensions - the number of dimensions

value - the value (must be in the range min..max)

min - the minimum value

max - the maximum value (must be larger than min)

Returns:

the normalized value in the range 0..getMaxValue(dimensions)

getMaxValue

public int getMaxValue(int dimensions)

Get the maximum value for the given dimension count. For two dimensions, each value must contain at most 32 bit, for 3: 21 bit, 4: 16 bit, 5: 12 bit, 6: 10 bit, 7: 9 bit, 8: 8 bit.

Parameters:

dimensions - the number of dimensions

Returns:

the maximum value

getBitsPerValue

private static int getBitsPerValue(int dimensions)

interleave

public long interleave(int... values)

Convert the multi-dimensional value into a one-dimensional (scalar) value. This is done by interleaving the bits of the values. Each values must be between 0 (including) and the maximum value for the given number of dimensions (getMaxValue, excluding). To normalize values to this range, use the normalize function.

Parameters:

values - the multi-dimensional value

Returns:

the scalar value

interleave

public long interleave(int x,
                       int y)

Convert the two-dimensional value into a one-dimensional (scalar) value. This is done by interleaving the bits of the values. Each values must be between 0 (including) and the maximum value for the given number of dimensions (getMaxValue, excluding). To normalize values to this range, use the normalize function.

Parameters:

x - the value of the first dimension, normalized

y - the value of the second dimension, normalized

Returns:

the scalar value

deinterleave

public int deinterleave(int dimensions,
                        long scalar,
                        int dim)

Gets one of the original multi-dimensional values from a scalar value.

Parameters:

dimensions - the number of dimensions

scalar - the scalar value

dim - the dimension of the returned value (starting from 0)

Returns:

the value

generatePreparedQuery

public java.lang.String generatePreparedQuery(java.lang.String table,
                                              java.lang.String scalarColumn,
                                              java.lang.String[] columns)

Generates an optimized multi-dimensional range query. The query contains parameters. It can only be used with the H2 database.

Parameters:

table - the table name

columns - the list of columns

scalarColumn - the column name of the computed scalar column

Returns:

the query

getResult

public java.sql.ResultSet getResult(java.sql.PreparedStatement prep,
                                    int[] min,
                                    int[] max)
                             throws java.sql.SQLException

Executes a prepared query that was generated using generatePreparedQuery.

Parameters:

prep - the prepared statement

min - the lower values

max - the upper values

Returns:

the result set

Throws:

java.sql.SQLException - on failure

getMortonRanges

private long[][] getMortonRanges(int[] min,
                                 int[] max)

Gets a list of ranges to be searched for a multi-dimensional range query where min <= value <= max. In most cases, the ranges will be larger than required in order to combine smaller ranges into one. Usually, about double as many points will be included in the resulting range.

Parameters:

min - the minimum value

max - the maximum value

Returns:

the list of ranges (low, high pairs)

getSize

private static int getSize(int[] min,
                           int[] max,
                           int len)

combineEntries

private void combineEntries(java.util.ArrayList<long[]> list,
                            int total)

Combine entries if the size of the list is too large.

Parameters:

list - list of pairs(low, high)

total - product of the gap lengths

compare

public int compare(long[] a,
                   long[] b)

Specified by:

compare in interface java.util.Comparator<long[]>

addMortonRanges

private void addMortonRanges(java.util.ArrayList<long[]> list,
                             int[] min,
                             int[] max,
                             int len,
                             int level)

roundUp

private static int roundUp(int x,
                           int blockSizePowerOf2)

findMiddle

private static int findMiddle(int a,
                              int b)