diff options
Diffstat (limited to 'src/main/java/org/apache/commons/math3/geometry/partitioning/utilities')
4 files changed, 1089 insertions, 0 deletions
diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/utilities/AVLTree.java b/src/main/java/org/apache/commons/math3/geometry/partitioning/utilities/AVLTree.java new file mode 100644 index 0000000..00c9d3e --- /dev/null +++ b/src/main/java/org/apache/commons/math3/geometry/partitioning/utilities/AVLTree.java @@ -0,0 +1,634 @@ +/* + * 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/LICENSE-2.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; + +/** This class implements AVL trees. + * + * <p>The purpose of this class is to sort elements while allowing + * duplicate elements (i.e. such that {@code a.equals(b)} is + * true). The {@code SortedSet} interface does not allow this, so + * a specific class is needed. Null elements are not allowed.</p> + * + * <p>Since the {@code equals} method is not sufficient to + * differentiate elements, the {@link #delete delete} method is + * implemented using the equality operator.</p> + * + * <p>In order to clearly mark the methods provided here do not have + * the same semantics as the ones specified in the + * {@code SortedSet} interface, different names are used + * ({@code add} has been replaced by {@link #insert insert} and + * {@code remove} has been replaced by {@link #delete + * delete}).</p> + * + * <p>This class is based on the C implementation Georg Kraml has put + * in the public domain. Unfortunately, his <a + * href="www.purists.org/georg/avltree/index.html">page</a> seems not + * to exist any more.</p> + * + * @param <T> the type of the elements + * + * @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 AVLTree<T extends Comparable<T>> { + + /** Top level node. */ + private Node top; + + /** Build an empty tree. + */ + public AVLTree() { + top = null; + } + + /** Insert an element in the tree. + * @param element element to insert (silently ignored if null) + */ + public void insert(final T element) { + if (element != null) { + if (top == null) { + top = new Node(element, null); + } else { + top.insert(element); + } + } + } + + /** Delete an element from the tree. + * <p>The element is deleted only if there is a node {@code n} + * containing exactly the element instance specified, i.e. for which + * {@code n.getElement() == element}. This is purposely + * <em>different</em> from the specification of the + * {@code java.util.Set} {@code remove} method (in fact, + * this is the reason why a specific class has been developed).</p> + * @param element element to delete (silently ignored if null) + * @return true if the element was deleted from the tree + */ + public boolean delete(final T element) { + if (element != null) { + for (Node node = getNotSmaller(element); node != null; node = node.getNext()) { + // loop over all elements neither smaller nor larger + // than the specified one + if (node.element == element) { + node.delete(); + return true; + } else if (node.element.compareTo(element) > 0) { + // all the remaining elements are known to be larger, + // the element is not in the tree + return false; + } + } + } + return false; + } + + /** Check if the tree is empty. + * @return true if the tree is empty + */ + public boolean isEmpty() { + return top == null; + } + + + /** Get the number of elements of the tree. + * @return number of elements contained in the tree + */ + public int size() { + return (top == null) ? 0 : top.size(); + } + + /** Get the node whose element is the smallest one in the tree. + * @return the tree node containing the smallest element in the tree + * or null if the tree is empty + * @see #getLargest + * @see #getNotSmaller + * @see #getNotLarger + * @see Node#getPrevious + * @see Node#getNext + */ + public Node getSmallest() { + return (top == null) ? null : top.getSmallest(); + } + + /** Get the node whose element is the largest one in the tree. + * @return the tree node containing the largest element in the tree + * or null if the tree is empty + * @see #getSmallest + * @see #getNotSmaller + * @see #getNotLarger + * @see Node#getPrevious + * @see Node#getNext + */ + public Node getLargest() { + return (top == null) ? null : top.getLargest(); + } + + /** Get the node whose element is not smaller than the reference object. + * @param reference reference object (may not be in the tree) + * @return the tree node containing the smallest element not smaller + * than the reference object or null if either the tree is empty or + * all its elements are smaller than the reference object + * @see #getSmallest + * @see #getLargest + * @see #getNotLarger + * @see Node#getPrevious + * @see Node#getNext + */ + public Node getNotSmaller(final T reference) { + Node candidate = null; + for (Node node = top; node != null;) { + if (node.element.compareTo(reference) < 0) { + if (node.right == null) { + return candidate; + } + node = node.right; + } else { + candidate = node; + if (node.left == null) { + return candidate; + } + node = node.left; + } + } + return null; + } + + /** Get the node whose element is not larger than the reference object. + * @param reference reference object (may not be in the tree) + * @return the tree node containing the largest element not larger + * than the reference object (in which case the node is guaranteed + * not to be empty) or null if either the tree is empty or all its + * elements are larger than the reference object + * @see #getSmallest + * @see #getLargest + * @see #getNotSmaller + * @see Node#getPrevious + * @see Node#getNext + */ + public Node getNotLarger(final T reference) { + Node candidate = null; + for (Node node = top; node != null;) { + if (node.element.compareTo(reference) > 0) { + if (node.left == null) { + return candidate; + } + node = node.left; + } else { + candidate = node; + if (node.right == null) { + return candidate; + } + node = node.right; + } + } + return null; + } + + /** Enum for tree skew factor. */ + private enum Skew { + /** Code for left high trees. */ + LEFT_HIGH, + + /** Code for right high trees. */ + RIGHT_HIGH, + + /** Code for Skew.BALANCED trees. */ + BALANCED; + } + + /** This class implements AVL trees nodes. + * <p>AVL tree nodes implement all the logical structure of the + * tree. Nodes are created by the {@link AVLTree AVLTree} class.</p> + * <p>The nodes are not independant from each other but must obey + * specific balancing constraints and the tree structure is + * rearranged as elements are inserted or deleted from the tree. The + * creation, modification and tree-related navigation methods have + * therefore restricted access. Only the order-related navigation, + * reading and delete methods are public.</p> + * @see AVLTree + */ + public class Node { + + /** Element contained in the current node. */ + private T element; + + /** Left sub-tree. */ + private Node left; + + /** Right sub-tree. */ + private Node right; + + /** Parent tree. */ + private Node parent; + + /** Skew factor. */ + private Skew skew; + + /** Build a node for a specified element. + * @param element element + * @param parent parent node + */ + Node(final T element, final Node parent) { + this.element = element; + left = null; + right = null; + this.parent = parent; + skew = Skew.BALANCED; + } + + /** Get the contained element. + * @return element contained in the node + */ + public T getElement() { + return element; + } + + /** Get the number of elements of the tree rooted at this node. + * @return number of elements contained in the tree rooted at this node + */ + int size() { + return 1 + ((left == null) ? 0 : left.size()) + ((right == null) ? 0 : right.size()); + } + + /** Get the node whose element is the smallest one in the tree + * rooted at this node. + * @return the tree node containing the smallest element in the + * tree rooted at this node or null if the tree is empty + * @see #getLargest + */ + Node getSmallest() { + Node node = this; + while (node.left != null) { + node = node.left; + } + return node; + } + + /** Get the node whose element is the largest one in the tree + * rooted at this node. + * @return the tree node containing the largest element in the + * tree rooted at this node or null if the tree is empty + * @see #getSmallest + */ + Node getLargest() { + Node node = this; + while (node.right != null) { + node = node.right; + } + return node; + } + + /** Get the node containing the next smaller or equal element. + * @return node containing the next smaller or equal element or + * null if there is no smaller or equal element in the tree + * @see #getNext + */ + public Node getPrevious() { + + if (left != null) { + final Node node = left.getLargest(); + if (node != null) { + return node; + } + } + + for (Node node = this; node.parent != null; node = node.parent) { + if (node != node.parent.left) { + return node.parent; + } + } + + return null; + + } + + /** Get the node containing the next larger or equal element. + * @return node containing the next larger or equal element (in + * which case the node is guaranteed not to be empty) or null if + * there is no larger or equal element in the tree + * @see #getPrevious + */ + public Node getNext() { + + if (right != null) { + final Node node = right.getSmallest(); + if (node != null) { + return node; + } + } + + for (Node node = this; node.parent != null; node = node.parent) { + if (node != node.parent.right) { + return node.parent; + } + } + + return null; + + } + + /** Insert an element in a sub-tree. + * @param newElement element to insert + * @return true if the parent tree should be re-Skew.BALANCED + */ + boolean insert(final T newElement) { + if (newElement.compareTo(this.element) < 0) { + // the inserted element is smaller than the node + if (left == null) { + left = new Node(newElement, this); + return rebalanceLeftGrown(); + } + return left.insert(newElement) ? rebalanceLeftGrown() : false; + } + + // the inserted element is equal to or greater than the node + if (right == null) { + right = new Node(newElement, this); + return rebalanceRightGrown(); + } + return right.insert(newElement) ? rebalanceRightGrown() : false; + + } + + /** Delete the node from the tree. + */ + public void delete() { + if ((parent == null) && (left == null) && (right == null)) { + // this was the last node, the tree is now empty + element = null; + top = null; + } else { + + Node node; + Node child; + boolean leftShrunk; + if ((left == null) && (right == null)) { + node = this; + element = null; + leftShrunk = node == node.parent.left; + child = null; + } else { + node = (left != null) ? left.getLargest() : right.getSmallest(); + element = node.element; + leftShrunk = node == node.parent.left; + child = (node.left != null) ? node.left : node.right; + } + + node = node.parent; + if (leftShrunk) { + node.left = child; + } else { + node.right = child; + } + if (child != null) { + child.parent = node; + } + + while (leftShrunk ? node.rebalanceLeftShrunk() : node.rebalanceRightShrunk()) { + if (node.parent == null) { + return; + } + leftShrunk = node == node.parent.left; + node = node.parent; + } + + } + } + + /** Re-balance the instance as left sub-tree has grown. + * @return true if the parent tree should be reSkew.BALANCED too + */ + private boolean rebalanceLeftGrown() { + switch (skew) { + case LEFT_HIGH: + if (left.skew == Skew.LEFT_HIGH) { + rotateCW(); + skew = Skew.BALANCED; + right.skew = Skew.BALANCED; + } else { + final Skew s = left.right.skew; + left.rotateCCW(); + rotateCW(); + switch(s) { + case LEFT_HIGH: + left.skew = Skew.BALANCED; + right.skew = Skew.RIGHT_HIGH; + break; + case RIGHT_HIGH: + left.skew = Skew.LEFT_HIGH; + right.skew = Skew.BALANCED; + break; + default: + left.skew = Skew.BALANCED; + right.skew = Skew.BALANCED; + } + skew = Skew.BALANCED; + } + return false; + case RIGHT_HIGH: + skew = Skew.BALANCED; + return false; + default: + skew = Skew.LEFT_HIGH; + return true; + } + } + + /** Re-balance the instance as right sub-tree has grown. + * @return true if the parent tree should be reSkew.BALANCED too + */ + private boolean rebalanceRightGrown() { + switch (skew) { + case LEFT_HIGH: + skew = Skew.BALANCED; + return false; + case RIGHT_HIGH: + if (right.skew == Skew.RIGHT_HIGH) { + rotateCCW(); + skew = Skew.BALANCED; + left.skew = Skew.BALANCED; + } else { + final Skew s = right.left.skew; + right.rotateCW(); + rotateCCW(); + switch (s) { + case LEFT_HIGH: + left.skew = Skew.BALANCED; + right.skew = Skew.RIGHT_HIGH; + break; + case RIGHT_HIGH: + left.skew = Skew.LEFT_HIGH; + right.skew = Skew.BALANCED; + break; + default: + left.skew = Skew.BALANCED; + right.skew = Skew.BALANCED; + } + skew = Skew.BALANCED; + } + return false; + default: + skew = Skew.RIGHT_HIGH; + return true; + } + } + + /** Re-balance the instance as left sub-tree has shrunk. + * @return true if the parent tree should be reSkew.BALANCED too + */ + private boolean rebalanceLeftShrunk() { + switch (skew) { + case LEFT_HIGH: + skew = Skew.BALANCED; + return true; + case RIGHT_HIGH: + if (right.skew == Skew.RIGHT_HIGH) { + rotateCCW(); + skew = Skew.BALANCED; + left.skew = Skew.BALANCED; + return true; + } else if (right.skew == Skew.BALANCED) { + rotateCCW(); + skew = Skew.LEFT_HIGH; + left.skew = Skew.RIGHT_HIGH; + return false; + } else { + final Skew s = right.left.skew; + right.rotateCW(); + rotateCCW(); + switch (s) { + case LEFT_HIGH: + left.skew = Skew.BALANCED; + right.skew = Skew.RIGHT_HIGH; + break; + case RIGHT_HIGH: + left.skew = Skew.LEFT_HIGH; + right.skew = Skew.BALANCED; + break; + default: + left.skew = Skew.BALANCED; + right.skew = Skew.BALANCED; + } + skew = Skew.BALANCED; + return true; + } + default: + skew = Skew.RIGHT_HIGH; + return false; + } + } + + /** Re-balance the instance as right sub-tree has shrunk. + * @return true if the parent tree should be reSkew.BALANCED too + */ + private boolean rebalanceRightShrunk() { + switch (skew) { + case RIGHT_HIGH: + skew = Skew.BALANCED; + return true; + case LEFT_HIGH: + if (left.skew == Skew.LEFT_HIGH) { + rotateCW(); + skew = Skew.BALANCED; + right.skew = Skew.BALANCED; + return true; + } else if (left.skew == Skew.BALANCED) { + rotateCW(); + skew = Skew.RIGHT_HIGH; + right.skew = Skew.LEFT_HIGH; + return false; + } else { + final Skew s = left.right.skew; + left.rotateCCW(); + rotateCW(); + switch (s) { + case LEFT_HIGH: + left.skew = Skew.BALANCED; + right.skew = Skew.RIGHT_HIGH; + break; + case RIGHT_HIGH: + left.skew = Skew.LEFT_HIGH; + right.skew = Skew.BALANCED; + break; + default: + left.skew = Skew.BALANCED; + right.skew = Skew.BALANCED; + } + skew = Skew.BALANCED; + return true; + } + default: + skew = Skew.LEFT_HIGH; + return false; + } + } + + /** Perform a clockwise rotation rooted at the instance. + * <p>The skew factor are not updated by this method, they + * <em>must</em> be updated by the caller</p> + */ + private void rotateCW() { + + final T tmpElt = element; + element = left.element; + left.element = tmpElt; + + final Node tmpNode = left; + left = tmpNode.left; + tmpNode.left = tmpNode.right; + tmpNode.right = right; + right = tmpNode; + + if (left != null) { + left.parent = this; + } + if (right.right != null) { + right.right.parent = right; + } + + } + + /** Perform a counter-clockwise rotation rooted at the instance. + * <p>The skew factor are not updated by this method, they + * <em>must</em> be updated by the caller</p> + */ + private void rotateCCW() { + + final T tmpElt = element; + element = right.element; + right.element = tmpElt; + + final Node tmpNode = right; + right = tmpNode.right; + tmpNode.right = tmpNode.left; + tmpNode.left = left; + left = tmpNode; + + if (right != null) { + right.parent = this; + } + if (left.left != null) { + left.left.parent = left; + } + + } + + } + +} diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/utilities/OrderedTuple.java b/src/main/java/org/apache/commons/math3/geometry/partitioning/utilities/OrderedTuple.java new file mode 100644 index 0000000..2dad2d7 --- /dev/null +++ b/src/main/java/org/apache/commons/math3/geometry/partitioning/utilities/OrderedTuple.java @@ -0,0 +1,431 @@ +/* + * 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/LICENSE-2.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 T-uples. + * + * <p>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<sup>k</sup> bit of component 0 is + * followed by the 2<sup>k</sup> bit of component 1, then by the + * 2<sup>k</sup> bit of component 2 up to the 2<sup>k</sup> bit of + * component {@code t}, which is followed by the 2<sup>k-1</sup> + * bit of component 0, followed by the 2<sup>k-1</sup> bit of + * component 1 ... The binary representations are extended as needed + * to handle numbers with different scales and a suitable + * 2<sup>p</sup> 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="doc-files/OrderedTuple.png" /> + * + * <p>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.</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>T-uples 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</em> and consistent T-uples + * 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 T-uple. */ + 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 T-uple from its components. + * @param components double components of the T-uple + */ + 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 T-upple with the specified offset + encode(msb + 16); + } else { + encoding = new long[] { + 0x0L + }; + } + + } + + /** Encode the T-uple 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 T-uple 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 T-uples stay close to each other when stored + * in a sorted collection using this comparison method.</p> + + * <p>T-uples 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</em> and consistent T-uples 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 (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 T-uple 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 T-uple 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); + } + } + +} diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/utilities/doc-files/OrderedTuple.png b/src/main/java/org/apache/commons/math3/geometry/partitioning/utilities/doc-files/OrderedTuple.png Binary files differnew file mode 100644 index 0000000..4eca233 --- /dev/null +++ b/src/main/java/org/apache/commons/math3/geometry/partitioning/utilities/doc-files/OrderedTuple.png diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/utilities/package-info.java b/src/main/java/org/apache/commons/math3/geometry/partitioning/utilities/package-info.java new file mode 100644 index 0000000..31f57f1 --- /dev/null +++ b/src/main/java/org/apache/commons/math3/geometry/partitioning/utilities/package-info.java @@ -0,0 +1,24 @@ +/* + * 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/LICENSE-2.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. + */ +/** + * + * <p> + * This package provides multidimensional ordering features for partitioning. + * </p> + * + */ +package org.apache.commons.math3.geometry.partitioning.utilities; |
