

Java example source code file (OrderedTuple.java)
The OrderedTuple.java Java example source code/* * Licensed to the Apache Software Foundation (ASF) under one or more * contributor license agreements. See the NOTICE file distributed with * this work for additional information regarding copyright ownership. * The ASF licenses this file to You under the Apache License, Version 2.0 * (the "License"); you may not use this file except in compliance with * the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ package org.apache.commons.math3.geometry.partitioning.utilities; import java.util.Arrays; import org.apache.commons.math3.util.FastMath; /** This class implements an ordering operation for Tuples. * * <p>Ordering is done by encoding all components of the Tuple 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 Tuple are mixed together to form a single * scalar. This means that the 2<sup>k bit of component 0 is * followed by the 2<sup>k bit of component 1, then by the * 2<sup>k bit of component 2 up to the 2^{k} bit of * component {@code t}, which is followed by the 2<sup>k1 * bit of component 0, followed by the 2<sup>k1 bit of * component 1 ... The binary representations are extended as needed * to handle numbers with different scales and a suitable * 2<sup>p offset is added to the components in order to avoid * negative numbers (this offset is adjusted as needed during the * comparison operations).</p> * * <p>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:</p> * * <img src="docfiles/OrderedTuple.png" /> * * <p>This picture shows a set of 100000 random 2D 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.</p> * * <p>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.</p> * * <p>Tuples with negative infinite or positive infinite components * are sorted logically.</p> * * <p>Since the specification of the {@code Comparator} interface * allows only {@code ClassCastException} errors, some arbitrary * choices have been made to handle specific cases. The rationale for * these choices is to keep <em>regular and consistent Tuples * together.</p> * <ul> * <li>instances with different dimensions are sorted according to * their dimension regardless of their components values</li> * <li>instances with {@code Double.NaN} components are sorted * after all other ones (even after instances with positive infinite * components</li> * <li>instances with both positive and negative infinite components * are considered as if they had {@code Double.NaN} * components</li> * </ul> * * @since 3.0 * @deprecated as of 3.4, this class is not used anymore and considered * to be out of scope of Apache Commons Math */ @Deprecated public class OrderedTuple implements Comparable<OrderedTuple> { /** Sign bit mask. */ private static final long SIGN_MASK = 0x8000000000000000L; /** Exponent bits mask. */ private static final long EXPONENT_MASK = 0x7ff0000000000000L; /** Mantissa bits mask. */ private static final long MANTISSA_MASK = 0x000fffffffffffffL; /** Implicit MSB for normalized numbers. */ private static final long IMPLICIT_ONE = 0x0010000000000000L; /** Double components of the Tuple. */ private double[] components; /** Offset scale. */ private int offset; /** Least Significant Bit scale. */ private int lsb; /** Ordering encoding of the double components. */ private long[] encoding; /** Positive infinity marker. */ private boolean posInf; /** Negative infinity marker. */ private boolean negInf; /** Not A Number marker. */ private boolean nan; /** Build an ordered Tuple from its components. * @param components double components of the Tuple */ public OrderedTuple(final double ... components) { this.components = components.clone(); int msb = Integer.MIN_VALUE; lsb = Integer.MAX_VALUE; posInf = false; negInf = false; nan = false; for (int i = 0; i < components.length; ++i) { if (Double.isInfinite(components[i])) { if (components[i] < 0) { negInf = true; } else { posInf = true; } } else if (Double.isNaN(components[i])) { nan = true; } else { final long b = Double.doubleToLongBits(components[i]); final long m = mantissa(b); if (m != 0) { final int e = exponent(b); msb = FastMath.max(msb, e + computeMSB(m)); lsb = FastMath.min(lsb, e + computeLSB(m)); } } } if (posInf && negInf) { // instance cannot be sorted logically posInf = false; negInf = false; nan = true; } if (lsb <= msb) { // encode the Tupple with the specified offset encode(msb + 16); } else { encoding = new long[] { 0x0L }; } } /** Encode the Tuple with a given offset. * @param minOffset minimal scale of the offset to add to all * components (must be greater than the MSBs of all components) */ private void encode(final int minOffset) { // choose an offset with some margins offset = minOffset + 31; offset = offset % 32; if ((encoding != null) && (encoding.length == 1) && (encoding[0] == 0x0L)) { // the components are all zeroes return; } // allocate an integer array to encode the components (we use only // 63 bits per element because there is no unsigned long in Java) final int neededBits = offset + 1  lsb; final int neededLongs = (neededBits + 62) / 63; encoding = new long[components.length * neededLongs]; // mix the bits from all components int eIndex = 0; int shift = 62; long word = 0x0L; for (int k = offset; eIndex < encoding.length; k) { for (int vIndex = 0; vIndex < components.length; ++vIndex) { if (getBit(vIndex, k) != 0) { word = 0x1L << shift; } if (shift == 0) { encoding[eIndex++] = word; word = 0x0L; shift = 62; } } } } /** Compares this ordered Tuple with the specified object. * <p>The ordering method is detailed in the general description of * the class. Its main property is to be consistent with distance: * geometrically close Tuples stay close to each other when stored * in a sorted collection using this comparison method.</p> * <p>Tuples with negative infinite, positive infinite are sorted * logically.</p> * <p>Some arbitrary choices have been made to handle specific * cases. The rationale for these choices is to keep * <em>normal and consistent Tuples together. * <ul> * <li>instances with different dimensions are sorted according to * their dimension regardless of their components values</li> * <li>instances with {@code Double.NaN} components are sorted * after all other ones (evan after instances with positive infinite * components</li> * <li>instances with both positive and negative infinite components * are considered as if they had {@code Double.NaN} * components</li> * </ul> * @param ot Tuple to compare instance with * @return 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) { if (components.length == ot.components.length) { if (nan) { return +1; } else if (ot.nan) { return 1; } else if (negInf  ot.posInf) { return 1; } else if (posInf  ot.negInf) { return +1; } else { if (offset < ot.offset) { encode(ot.offset); } else if (offset > ot.offset) { ot.encode(offset); } final int limit = FastMath.min(encoding.length, ot.encoding.length); for (int i = 0; i < limit; ++i) { if (encoding[i] < ot.encoding[i]) { return 1; } else if (encoding[i] > ot.encoding[i]) { return +1; } } if (encoding.length < ot.encoding.length) { return 1; } else if (encoding.length > ot.encoding.length) { return +1; } else { return 0; } } } return components.length  ot.components.length; } /** {@inheritDoc} */ @Override public boolean equals(final Object other) { if (this == other) { return true; } else if (other instanceof OrderedTuple) { return compareTo((OrderedTuple) other) == 0; } else { return false; } } /** {@inheritDoc} */ @Override public int hashCode() { // the following constants are arbitrary small primes final int multiplier = 37; final int trueHash = 97; final int falseHash = 71; // hash fields and combine them // (we rely on the multiplier to have different combined weights // for all int fields and all boolean fields) int hash = Arrays.hashCode(components); hash = hash * multiplier + offset; hash = hash * multiplier + lsb; hash = hash * multiplier + (posInf ? trueHash : falseHash); hash = hash * multiplier + (negInf ? trueHash : falseHash); hash = hash * multiplier + (nan ? trueHash : falseHash); return hash; } /** Get the components array. * @return array containing the Tuple components */ public double[] getComponents() { return components.clone(); } /** Extract the sign from the bits of a double. * @param bits binary representation of the double * @return sign bit (zero if positive, non zero if negative) */ private static long sign(final long bits) { return bits & SIGN_MASK; } /** Extract the exponent from the bits of a double. * @param bits binary representation of the double * @return exponent */ private static int exponent(final long bits) { return ((int) ((bits & EXPONENT_MASK) >> 52))  1075; } /** Extract the mantissa from the bits of a double. * @param bits binary representation of the double * @return mantissa */ private static long mantissa(final long bits) { return ((bits & EXPONENT_MASK) == 0) ? ((bits & MANTISSA_MASK) << 1) : // subnormal number (IMPLICIT_ONE  (bits & MANTISSA_MASK)); // normal number } /** Compute the most significant bit of a long. * @param l long from which the most significant bit is requested * @return scale of the most significant bit of {@code l}, * or 0 if {@code l} is zero * @see #computeLSB */ private static int computeMSB(final long l) { long ll = l; long mask = 0xffffffffL; int scale = 32; int msb = 0; while (scale != 0) { if ((ll & mask) != ll) { msb = scale; ll >>= scale; } scale >>= 1; mask >>= scale; } return msb; } /** Compute the least significant bit of a long. * @param l long from which the least significant bit is requested * @return scale of the least significant bit of {@code l}, * or 63 if {@code l} is zero * @see #computeMSB */ private static int computeLSB(final long l) { long ll = l; long mask = 0xffffffff00000000L; int scale = 32; int lsb = 0; while (scale != 0) { if ((ll & mask) == ll) { lsb = scale; ll >>= scale; } scale >>= 1; mask >>= scale; } return lsb; } /** Get a bit from the mantissa of a double. * @param i index of the component * @param k scale of the requested bit * @return the specified bit (either 0 or 1), after the offset has * been added to the double */ private int getBit(final int i, final int k) { final long bits = Double.doubleToLongBits(components[i]); final int e = exponent(bits); if ((k < e)  (k > offset)) { return 0; } else if (k == offset) { return (sign(bits) == 0L) ? 1 : 0; } else if (k > (e + 52)) { return (sign(bits) == 0L) ? 0 : 1; } else { final long m = (sign(bits) == 0L) ? mantissa(bits) : mantissa(bits); return (int) ((m >> (k  e)) & 0x1L); } } } Other Java examples (source code examples)Here is a short list of links related to this Java OrderedTuple.java source code file: 
Copyright 19982021 Alvin Alexander, alvinalexander.com
All Rights Reserved.
A percentage of advertising revenue from
pages under the /java/jwarehouse
URI on this website is
paid back to open source projects.