commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From t.@apache.org
Subject [7/7] [math] Remove deprecated classes in package geometry.partitioning.utilities.
Date Thu, 19 Feb 2015 09:01:57 GMT
Remove deprecated classes in package geometry.partitioning.utilities.


Project: http://git-wip-us.apache.org/repos/asf/commons-math/repo
Commit: http://git-wip-us.apache.org/repos/asf/commons-math/commit/6d50174b
Tree: http://git-wip-us.apache.org/repos/asf/commons-math/tree/6d50174b
Diff: http://git-wip-us.apache.org/repos/asf/commons-math/diff/6d50174b

Branch: refs/heads/master
Commit: 6d50174baa3fa3c21ad8d20fa6f3c0a62cf74394
Parents: d0c62a8
Author: tn <thomas.neidhart@gmail.com>
Authored: Thu Feb 19 10:01:34 2015 +0100
Committer: tn <thomas.neidhart@gmail.com>
Committed: Thu Feb 19 10:01:34 2015 +0100

----------------------------------------------------------------------
 .../partitioning/utilities/AVLTree.java         | 634 -------------------
 .../partitioning/utilities/OrderedTuple.java    | 431 -------------
 .../utilities/doc-files/OrderedTuple.png        | Bin 28882 -> 0 bytes
 .../partitioning/utilities/package-info.java    |  24 -
 .../partitioning/utilities/AVLTreeTest.java     | 176 -----
 5 files changed, 1265 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/commons-math/blob/6d50174b/src/main/java/org/apache/commons/math4/geometry/partitioning/utilities/AVLTree.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/math4/geometry/partitioning/utilities/AVLTree.java b/src/main/java/org/apache/commons/math4/geometry/partitioning/utilities/AVLTree.java
deleted file mode 100644
index f995cd3..0000000
--- a/src/main/java/org/apache/commons/math4/geometry/partitioning/utilities/AVLTree.java
+++ /dev/null
@@ -1,634 +0,0 @@
-/*
- * 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.math4.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 static 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;
-            }
-
-        }
-
-    }
-
-}

http://git-wip-us.apache.org/repos/asf/commons-math/blob/6d50174b/src/main/java/org/apache/commons/math4/geometry/partitioning/utilities/OrderedTuple.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/math4/geometry/partitioning/utilities/OrderedTuple.java b/src/main/java/org/apache/commons/math4/geometry/partitioning/utilities/OrderedTuple.java
deleted file mode 100644
index 490c80c..0000000
--- a/src/main/java/org/apache/commons/math4/geometry/partitioning/utilities/OrderedTuple.java
+++ /dev/null
@@ -1,431 +0,0 @@
-/*
- * 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.math4.geometry.partitioning.utilities;
-
-import java.util.Arrays;
-
-import org.apache.commons.math4.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);
-        }
-    }
-
-}

http://git-wip-us.apache.org/repos/asf/commons-math/blob/6d50174b/src/main/java/org/apache/commons/math4/geometry/partitioning/utilities/doc-files/OrderedTuple.png
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/math4/geometry/partitioning/utilities/doc-files/OrderedTuple.png b/src/main/java/org/apache/commons/math4/geometry/partitioning/utilities/doc-files/OrderedTuple.png
deleted file mode 100644
index 4eca233..0000000
Binary files a/src/main/java/org/apache/commons/math4/geometry/partitioning/utilities/doc-files/OrderedTuple.png and /dev/null differ

http://git-wip-us.apache.org/repos/asf/commons-math/blob/6d50174b/src/main/java/org/apache/commons/math4/geometry/partitioning/utilities/package-info.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/math4/geometry/partitioning/utilities/package-info.java b/src/main/java/org/apache/commons/math4/geometry/partitioning/utilities/package-info.java
deleted file mode 100644
index 9cf8725..0000000
--- a/src/main/java/org/apache/commons/math4/geometry/partitioning/utilities/package-info.java
+++ /dev/null
@@ -1,24 +0,0 @@
-/*
- * 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.math4.geometry.partitioning.utilities;

http://git-wip-us.apache.org/repos/asf/commons-math/blob/6d50174b/src/test/java/org/apache/commons/math4/geometry/partitioning/utilities/AVLTreeTest.java
----------------------------------------------------------------------
diff --git a/src/test/java/org/apache/commons/math4/geometry/partitioning/utilities/AVLTreeTest.java b/src/test/java/org/apache/commons/math4/geometry/partitioning/utilities/AVLTreeTest.java
deleted file mode 100644
index 2174cd5..0000000
--- a/src/test/java/org/apache/commons/math4/geometry/partitioning/utilities/AVLTreeTest.java
+++ /dev/null
@@ -1,176 +0,0 @@
-/*
- * 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.math4.geometry.partitioning.utilities;
-
-import org.apache.commons.math4.geometry.partitioning.utilities.AVLTree;
-import org.junit.Assert;
-import org.junit.Test;
-
-@Deprecated
-public class AVLTreeTest {
-
-    @Test
-    public void testInsert() {
-        // this array in this order allows to pass in all branches
-        // of the insertion algorithm
-        int[] array = { 16, 13, 15, 14,  2,  0, 12,  9,  8,  5,
-            11, 18, 19, 17,  4,  7,  1,  3,  6, 10 };
-        AVLTree<Integer> tree = buildTree(array);
-
-        Assert.assertEquals(array.length, tree.size());
-
-        for (int i = 0; i < array.length; ++i) {
-            Assert.assertEquals(array[i], value(tree.getNotSmaller(new Integer(array[i]))));
-        }
-
-        checkOrder(tree);
-
-    }
-
-    @Test
-    public void testDelete1() {
-        int[][][] arrays = {
-            { { 16, 13, 15, 14, 2, 0, 12, 9, 8, 5, 11, 18, 19, 17, 4, 7, 1, 3, 6, 10 },
-                { 11, 10, 9, 12, 16, 15, 13, 18, 5, 0, 3, 2, 14, 6, 19, 17, 8, 4, 7, 1 } },
-                { { 16, 13, 15, 14, 2, 0, 12, 9, 8, 5, 11, 18, 19, 17, 4, 7, 1, 3, 6, 10 },
-                    { 0, 17, 14, 15, 16, 18,  6 } },
-                    { { 6, 2, 7, 8, 1, 4, 3, 5 }, { 8 } },
-                    { { 6, 2, 7, 8, 1, 4, 5 }, { 8 } },
-                    { { 3, 7, 2, 1, 5, 8, 4 }, { 1 } },
-                    { { 3, 7, 2, 1, 5, 8, 6 }, { 1 } }
-        };
-        for (int i = 0; i < arrays.length; ++i) {
-            AVLTree<Integer> tree = buildTree(arrays[i][0]);
-            Assert.assertTrue(! tree.delete(new Integer(-2000)));
-            for (int j = 0; j < arrays[i][1].length; ++j) {
-                Assert.assertTrue(tree.delete(tree.getNotSmaller(new Integer(arrays[i][1][j])).getElement()));
-                Assert.assertEquals(arrays[i][0].length - j - 1, tree.size());
-            }
-        }
-    }
-
-    @Test
-    public void testNavigation() {
-        int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
-        AVLTree<Integer> tree = buildTree(array);
-
-        AVLTree<Integer>.Node node = tree.getSmallest();
-        Assert.assertEquals(array[0], value(node));
-        for (int i = 0; i < array.length; ++i) {
-            Assert.assertEquals(array[i], value(node));
-            node = node.getNext();
-        }
-        Assert.assertNull(node);
-
-        node = tree.getLargest();
-        Assert.assertEquals(array[array.length - 1], value(node));
-        for (int i = array.length - 1; i >= 0; --i) {
-            Assert.assertEquals(array[i], value(node));
-            node = node.getPrevious();
-        }
-        Assert.assertNull(node);
-
-        checkOrder(tree);
-
-    }
-
-    @Test
-    public void testSearch() {
-        int[] array = { 2, 4, 6, 8, 10, 12, 14 };
-        AVLTree<Integer> tree = buildTree(array);
-
-        Assert.assertNull(tree.getNotLarger(new Integer(array[0] - 1)));
-        Assert.assertNull(tree.getNotSmaller(new Integer(array[array.length - 1] + 1)));
-
-        for (int i = 0; i < array.length; ++i) {
-            Assert.assertEquals(array[i],
-                                value(tree.getNotSmaller(new Integer(array[i] - 1))));
-            Assert.assertEquals(array[i],
-                                value(tree.getNotLarger(new Integer(array[i] + 1))));
-        }
-
-        checkOrder(tree);
-
-    }
-
-    @Test
-    public void testRepetition() {
-        int[] array = { 1, 1, 3, 3, 4, 5, 6, 7, 7, 7, 7, 7 };
-        AVLTree<Integer> tree = buildTree(array);
-        Assert.assertEquals(array.length, tree.size());
-
-        AVLTree<Integer>.Node node = tree.getNotSmaller(new Integer(3));
-        Assert.assertEquals(3, value(node));
-        Assert.assertEquals(1, value(node.getPrevious()));
-        Assert.assertEquals(3, value(node.getNext()));
-        Assert.assertEquals(4, value(node.getNext().getNext()));
-
-        node = tree.getNotLarger(new Integer(2));
-        Assert.assertEquals(1, value(node));
-        Assert.assertEquals(1, value(node.getPrevious()));
-        Assert.assertEquals(3, value(node.getNext()));
-        Assert.assertNull(node.getPrevious().getPrevious());
-
-        AVLTree<Integer>.Node otherNode = tree.getNotSmaller(new Integer(1));
-        Assert.assertTrue(node != otherNode);
-        Assert.assertEquals(1, value(otherNode));
-        Assert.assertNull(otherNode.getPrevious());
-
-        node = tree.getNotLarger(new Integer(10));
-        Assert.assertEquals(7, value(node));
-        Assert.assertNull(node.getNext());
-        node = node.getPrevious();
-        Assert.assertEquals(7, value(node));
-        node = node.getPrevious();
-        Assert.assertEquals(7, value(node));
-        node = node.getPrevious();
-        Assert.assertEquals(7, value(node));
-        node = node.getPrevious();
-        Assert.assertEquals(7, value(node));
-        node = node.getPrevious();
-        Assert.assertEquals(6, value(node));
-
-        checkOrder(tree);
-
-    }
-
-    private AVLTree<Integer> buildTree(int[] array) {
-        AVLTree<Integer> tree = new AVLTree<Integer>();
-        for (int i = 0; i < array.length; ++i) {
-            tree.insert(new Integer(array[i]));
-            tree.insert(null);
-        }
-        return tree;
-    }
-
-    private int value(AVLTree<Integer>.Node node) {
-        return node.getElement().intValue();
-    }
-
-    private void checkOrder(AVLTree<Integer> tree) {
-        AVLTree<Integer>.Node next = null;
-        for (AVLTree<Integer>.Node node = tree.getSmallest();
-        node != null;
-        node = next) {
-            next = node.getNext();
-            if (next != null) {
-                Assert.assertTrue(node.getElement().compareTo(next.getElement()) <= 0);
-            }
-        }
-    }
-
-}


Mime
View raw message