Apache Commons Math 3.6.1 · org.apache.commons.math3.geometry.partitioning.utilities.OrderedTuple

This class implements an ordering operation for T-uples.

Ordering is done by encoding all components of the T-uple into a single scalar value and using this value as the sorting key. Encoding is performed using the method invented by Georg Cantor in 1877 when he proved it was possible to establish a bijection between a line and a plane. The binary representations of the components of the T-uple are mixed together to form a single scalar. This means that the 2^k bit of component 0 is followed by the 2^k bit of component 1, then by the 2^k bit of component 2 up to the 2^k bit of component t, which is followed by the 2^k-1 bit of component 0, followed by the 2^k-1 bit of component 1 ... The binary representations are extended as needed to handle numbers with different scales and a suitable 2^p offset is added to the components in order to avoid negative numbers (this offset is adjusted as needed during the comparison operations).

The more interesting property of the encoding method for our purpose is that it allows to select all the points that are in a given range. This is depicted in dimension 2 by the following picture:

This picture shows a set of 100000 random 2-D pairs having their first component between -50 and +150 and their second component between -350 and +50. We wanted to extract all pairs having their first component between +30 and +70 and their second component between -120 and -30. We built the lower left point at coordinates (30, -120) and the upper right point at coordinates (70, -30). All points smaller than the lower left point are drawn in red and all points larger than the upper right point are drawn in blue. The green points are between the two limits. This picture shows that all the desired points are selected, along with spurious points. In this case, we get 15790 points, 4420 of which really belonging to the desired rectangle. It is possible to extract very small subsets. As an example extracting from the same 100000 points set the points having their first component between +30 and +31 and their second component between -91 and -90, we get a subset of 11 points, 2 of which really belonging to the desired rectangle.

the previous selection technique can be applied in all dimensions, still using two points to define the interval. The first point will have all its components set to their lower bounds while the second point will have all its components set to their upper bounds.

T-uples with negative infinite or positive infinite components are sorted logically.

Since the specification of the Comparator interface allows only ClassCastException errors, some arbitrary choices have been made to handle specific cases. The rationale for these choices is to keep regular and consistent T-uples together.

instances with different dimensions are sorted according to their dimension regardless of their components values
instances with Double.NaN components are sorted after all other ones (even after instances with positive infinite components
instances with both positive and negative infinite components are considered as if they had Double.NaN components

Field Summary

Modifier and Type	Field and Description
private double[]	components Double components of the T-uple.
private long[]	encoding Ordering encoding of the double components.
private static final long	EXPONENT_MASK Exponent bits mask.
private static final long	IMPLICIT_ONE Implicit MSB for normalized numbers.
private int	lsb Least Significant Bit scale.
private static final long	MANTISSA_MASK Mantissa bits mask.
private boolean	nan Not A Number marker.
private boolean	negInf Negative infinity marker.
private int	offset Offset scale.
private boolean	posInf Positive infinity marker.
private static final long	SIGN_MASK Sign bit mask.

Constructor Summary

Access	Constructor and Description
public	OrderedTuple(final double... double components of the T-uple components) Build an ordered T-uple from its components.

Method Summary

Modifier and Type	Method and Description
public int	Returns: a negative integer if the instance is less than the object, zero if they are equal, or a positive integer if the instance is greater than the object compareTo(final OrderedTuple T-uple to compare instance with ot) Implements java.lang.Comparable.compareTo. Deprecated as a consequence of `OrderedTuple` being deprecated. Compares this ordered T-uple with the specified object.
private static int	Returns: scale of the least significant bit of `l`, or 63 if `l` is zero computeLSB(final long long from which the least significant bit is requested l) Compute the least significant bit of a long.
private static int	Returns: scale of the most significant bit of `l`, or 0 if `l` is zero computeMSB(final long long from which the most significant bit is requested l) Compute the most significant bit of a long.
private void	encode(final int minimal scale of the offset to add to all components (must be greater than the MSBs of all components) minOffset) Encode the T-uple with a given offset.
public boolean	equals(final Object the reference object with which to compare. other) Overrides java.lang.Object.equals. Indicates whether some other object is "equal to" this one.
private static int	Returns: exponent exponent(final long binary representation of the double bits) Extract the exponent from the bits of a double.
private int	Returns: the specified bit (either 0 or 1), after the offset has been added to the double getBit(final int index of the component i, final int scale of the requested bit k) Get a bit from the mantissa of a double.
public double[]	Returns: array containing the T-uple components getComponents() Get the components array.
public int	hashCode() Overrides java.lang.Object.hashCode. Returns a hash code value for this object.
private static long	Returns: mantissa mantissa(final long binary representation of the double bits) Extract the mantissa from the bits of a double.
private static long	Returns: sign bit (zero if positive, non zero if negative) sign(final long binary representation of the double bits) Extract the sign from the bits of a double.

Inherited from java.lang.Object:: clone finalize getClass notify notifyAll toString wait wait wait

Field Detail

components	back to summary
private double[] components Double components of the T-uple.

encoding	back to summary
private long[] encoding Ordering encoding of the double components.

EXPONENT_MASK	back to summary
private static final long EXPONENT_MASK Exponent bits mask.

IMPLICIT_ONE	back to summary
private static final long IMPLICIT_ONE Implicit MSB for normalized numbers.

lsb	back to summary
private int lsb Least Significant Bit scale.

MANTISSA_MASK	back to summary
private static final long MANTISSA_MASK Mantissa bits mask.

nan	back to summary
private boolean nan Not A Number marker.

negInf	back to summary
private boolean negInf Negative infinity marker.

offset	back to summary
private int offset Offset scale.

posInf	back to summary
private boolean posInf Positive infinity marker.

SIGN_MASK	back to summary
private static final long SIGN_MASK Sign bit mask.

Constructor Detail

OrderedTuple	back to summary
public OrderedTuple(final double... components) Build an ordered T-uple from its components. Parameters components:double[] double components of the T-uple

OrderedTuple

back to summary

public OrderedTuple(final double... components)

Build an ordered T-uple from its components.

Parameters

components:double[]: double components of the T-uple

Method Detail

compareTo back to summary

compareTo	back to summary
public int compareTo(final OrderedTuple ot) Implements java.lang.Comparable.compareTo. Deprecated as a consequence of `OrderedTuple` being deprecated. See corresponding docs for further information. Compares this ordered T-uple with the specified object. The ordering method is detailed in the general description of the class. Its main property is to be consistent with distance: geometrically close T-uples stay close to each other when stored in a sorted collection using this comparison method. T-uples with negative infinite, positive infinite are sorted logically. Some arbitrary choices have been made to handle specific cases. The rationale for these choices is to keep normal and consistent T-uples together. instances with different dimensions are sorted according to their dimension regardless of their components values instances with `Double.NaN` components are sorted after all other ones (evan after instances with positive infinite components instances with both positive and negative infinite components are considered as if they had `Double.NaN` components Parameters ot:OrderedTuple T-uple to compare instance with Returns:int a negative integer if the instance is less than the object, zero if they are equal, or a positive integer if the instance is greater than the object

public int compareTo(final OrderedTuple ot)

Implements java.lang.Comparable.compareTo.

Deprecated

as a consequence of OrderedTuple being deprecated. See corresponding docs for further information.

Compares this ordered T-uple with the specified object.

The ordering method is detailed in the general description of the class. Its main property is to be consistent with distance: geometrically close T-uples stay close to each other when stored in a sorted collection using this comparison method.

T-uples with negative infinite, positive infinite are sorted logically.

Some arbitrary choices have been made to handle specific cases. The rationale for these choices is to keep normal and consistent T-uples together.

instances with different dimensions are sorted according to their dimension regardless of their components values
instances with Double.NaN components are sorted after all other ones (evan after instances with positive infinite components
instances with both positive and negative infinite components are considered as if they had Double.NaN components

Parameters

ot:OrderedTuple: T-uple to compare instance with

Returns:int

a negative integer if the instance is less than the object, zero if they are equal, or a positive integer if the instance is greater than the object

computeLSB back to summary

computeLSB	back to summary
private static int computeLSB(final long l) Compute the least significant bit of a long. Parameters l:long long from which the least significant bit is requested Returns:int scale of the least significant bit of `l`, or 63 if `l` is zero See Also `computeMSB`

private static int computeLSB(final long l)

Compute the least significant bit of a long.

Parameters

l:long: long from which the least significant bit is requested

Returns:int

scale of the least significant bit of l, or 63 if l is zero

See Also

computeMSB

computeMSB back to summary

computeMSB	back to summary
private static int computeMSB(final long l) Compute the most significant bit of a long. Parameters l:long long from which the most significant bit is requested Returns:int scale of the most significant bit of `l`, or 0 if `l` is zero See Also `computeLSB`

private static int computeMSB(final long l)

Compute the most significant bit of a long.

Parameters

l:long: long from which the most significant bit is requested

Returns:int

scale of the most significant bit of l, or 0 if l is zero

See Also

computeLSB

encode	back to summary
private void encode(final int minOffset) Encode the T-uple with a given offset. Parameters minOffset:int minimal scale of the offset to add to all components (must be greater than the MSBs of all components)

encode

back to summary

private void encode(final int minOffset)

Encode the T-uple with a given offset.

Parameters

minOffset:int: minimal scale of the offset to add to all components (must be greater than the MSBs of all components)

equals back to summary

equals	back to summary
public boolean equals(final Object other) Overrides java.lang.Object.equals. Doc from java.lang.Object.equals. Indicates whether some other object is "equal to" this one. The `equals` method implements an equivalence relation on non-null object references: It is reflexive: for any non-null reference value `x`, `x.equals(x)` should return `true`. It is symmetric: for any non-null reference values `x` and `y`, `x.equals(y)` should return `true` if and only if `y.equals(x)` returns `true`. It is transitive: for any non-null reference values `x`, `y`, and `z`, if `x.equals(y)` returns `true` and `y.equals(z)` returns `true`, then `x.equals(z)` should return `true`. It is consistent: for any non-null reference values `x` and `y`, multiple invocations of `x.equals(y)` consistently return `true` or consistently return `false`, provided no information used in `equals` comparisons on the objects is modified. For any non-null reference value `x`, `x.equals(null)` should return `false`. An equivalence relation partitions the elements it operates on into equivalence classes; all the members of an equivalence class are equal to each other. Members of an equivalence class are substitutable for each other, at least for some purposes. Parameters other:Object the reference object with which to compare. Returns:boolean `true` if this object is the same as the obj argument; `false` otherwise. Annotations @Override

public boolean equals(final Object other)

Overrides java.lang.Object.equals.

Doc from java.lang.Object.equals.

Indicates whether some other object is "equal to" this one.

The equals method implements an equivalence relation on non-null object references:

It is reflexive: for any non-null reference value x, x.equals(x) should return true.
It is symmetric: for any non-null reference values x and y, x.equals(y) should return true if and only if y.equals(x) returns true.
It is transitive: for any non-null reference values x, y, and z, if x.equals(y) returns true and y.equals(z) returns true, then x.equals(z) should return true.
It is consistent: for any non-null reference values x and y, multiple invocations of x.equals(y) consistently return true or consistently return false, provided no information used in equals comparisons on the objects is modified.
For any non-null reference value x, x.equals(null) should return false.

An equivalence relation partitions the elements it operates on into equivalence classes; all the members of an equivalence class are equal to each other. Members of an equivalence class are substitutable for each other, at least for some purposes.

Parameters

other:Object: the reference object with which to compare.

Returns:boolean

true if this object is the same as the obj argument; false otherwise.

Annotations

@Override

exponent	back to summary
private static int exponent(final long bits) Extract the exponent from the bits of a double. Parameters bits:long binary representation of the double Returns:int exponent

exponent

back to summary

private static int exponent(final long bits)

Extract the exponent from the bits of a double.

Parameters

bits:long: binary representation of the double

Returns:int

exponent

getBit	back to summary
private int getBit(final int i, final int k) Get a bit from the mantissa of a double. Parameters i:int index of the component k:int scale of the requested bit Returns:int the specified bit (either 0 or 1), after the offset has been added to the double

getBit

back to summary

private int getBit(final int i, final int k)

Get a bit from the mantissa of a double.

Parameters

i:int: index of the component
k:int: scale of the requested bit

Returns:int

the specified bit (either 0 or 1), after the offset has been added to the double

getComponents	back to summary
public double[] getComponents() Get the components array. Returns:double[] array containing the T-uple components

getComponents

back to summary

public double[] getComponents()

Get the components array.

Returns:double[]: array containing the T-uple components

hashCode back to summary

hashCode	back to summary
public int hashCode() Overrides java.lang.Object.hashCode. Doc from java.lang.Object.hashCode. Returns a hash code value for this object. This method is supported for the benefit of hash tables such as those provided by `java.util.HashMap`. The general contract of `hashCode` is: Whenever it is invoked on the same object more than once during an execution of a Java application, the `hashCode` method must consistently return the same integer, provided no information used in `equals` comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application. If two objects are equal according to the `equals` method, then calling the `hashCode` method on each of the two objects must produce the same integer result. It is not required that if two objects are unequal according to the `equals` method, then calling the `hashCode` method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hash tables. Returns:int a hash code value for this object Annotations @Override

public int hashCode()

Overrides java.lang.Object.hashCode.

Doc from java.lang.Object.hashCode.

Returns a hash code value for this object. This method is supported for the benefit of hash tables such as those provided by java.util.HashMap.

The general contract of hashCode is:

Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.
If two objects are equal according to the equals method, then calling the hashCode method on each of the two objects must produce the same integer result.
It is not required that if two objects are unequal according to the equals method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hash tables.

Returns:int

a hash code value for this object

Annotations

@Override

mantissa	back to summary
private static long mantissa(final long bits) Extract the mantissa from the bits of a double. Parameters bits:long binary representation of the double Returns:long mantissa

mantissa

back to summary

private static long mantissa(final long bits)

Extract the mantissa from the bits of a double.

Parameters

bits:long: binary representation of the double

Returns:long

mantissa

sign	back to summary
private static long sign(final long bits) Extract the sign from the bits of a double. Parameters bits:long binary representation of the double Returns:long sign bit (zero if positive, non zero if negative)

sign

back to summary

private static long sign(final long bits)

Extract the sign from the bits of a double.

Parameters

bits:long: binary representation of the double

Returns:long

sign bit (zero if positive, non zero if negative)

public Class OrderedTuple

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail