commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From l..@apache.org
Subject svn commit: r1066664 [5/6] - in /commons/sandbox/bsp: branches/ tags/ trunk/ trunk/src/ trunk/src/main/ trunk/src/main/java/ trunk/src/main/java/org/ trunk/src/main/java/org/apache/ trunk/src/main/java/org/apache/commons/ trunk/src/main/java/org/apache...
Date Wed, 02 Feb 2011 22:21:07 GMT
Added: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/utilities/AVLTree.java
URL: http://svn.apache.org/viewvc/commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/utilities/AVLTree.java?rev=1066664&view=auto
==============================================================================
--- commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/utilities/AVLTree.java (added)
+++ commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/utilities/AVLTree.java Wed Feb  2 22:21:05 2011
@@ -0,0 +1,631 @@
+/*
+ * 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.bsp.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
+
+ * @version $Revision$ $Date$
+ */
+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;
+            }
+
+        }
+
+    }
+
+}

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/utilities/AVLTree.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/utilities/AVLTree.java
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision

Added: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/utilities/OrderedTuple.java
URL: http://svn.apache.org/viewvc/commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/utilities/OrderedTuple.java?rev=1066664&view=auto
==============================================================================
--- commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/utilities/OrderedTuple.java (added)
+++ commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/utilities/OrderedTuple.java Wed Feb  2 22:21:05 2011
@@ -0,0 +1,417 @@
+/*
+ * 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.bsp.utilities;
+
+import java.util.Arrays;
+
+import org.apache.commons.math.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
+ * picure:</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>
+
+ * @version $Revision$ $Date$
+ */
+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() {
+        return Arrays.hashCode(components)   ^
+               ((Integer) offset).hashCode() ^
+               ((Integer) lsb).hashCode()    ^
+               ((Boolean) posInf).hashCode() ^
+               ((Boolean) negInf).hashCode() ^
+               ((Boolean) nan).hashCode();
+    }
+
+    /** 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 = ll >> scale;
+            }
+            scale = scale >> 1;
+            mask  = 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 = ll >> scale;
+            }
+            scale = scale >> 1;
+            mask  = 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);
+        }
+    }
+
+}

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/utilities/OrderedTuple.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/utilities/OrderedTuple.java
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision

Added: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/utilities/doc-files/OrderedTuple.png
URL: http://svn.apache.org/viewvc/commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/utilities/doc-files/OrderedTuple.png?rev=1066664&view=auto
==============================================================================
Binary file - no diff available.

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/utilities/doc-files/OrderedTuple.png
------------------------------------------------------------------------------
    svn:mime-type = image/png

Added: commons/sandbox/bsp/trunk/src/main/resources/META-INF/localization/BSPMessages_en.properties
URL: http://svn.apache.org/viewvc/commons/sandbox/bsp/trunk/src/main/resources/META-INF/localization/BSPMessages_en.properties?rev=1066664&view=auto
==============================================================================
--- commons/sandbox/bsp/trunk/src/main/resources/META-INF/localization/BSPMessages_en.properties (added)
+++ commons/sandbox/bsp/trunk/src/main/resources/META-INF/localization/BSPMessages_en.properties Wed Feb  2 22:21:05 2011
@@ -0,0 +1,26 @@
+# 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.
+
+# method not supported in dimension {0}
+NOT_SUPPORTED_IN_DIMENSION_N = method not supported in dimension {0}
+
+# an outline boundary loop is open
+OUTLINE_BOUNDARY_LOOP_OPEN = an outline boundary loop is open
+
+# some outline boundary loops cross each other
+CROSSING_BOUNDARY_LOOPS = some outline boundary loops cross each other
+
+# non-invertible affine transform collapses some lines into single points
+NON_INVERTIBLE_TRANSFORM = non-invertible affine transform collapses some lines into single points

Propchange: commons/sandbox/bsp/trunk/src/main/resources/META-INF/localization/BSPMessages_en.properties
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/bsp/trunk/src/main/resources/META-INF/localization/BSPMessages_en.properties
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision

Added: commons/sandbox/bsp/trunk/src/main/resources/META-INF/localization/BSPMessages_fr.properties
URL: http://svn.apache.org/viewvc/commons/sandbox/bsp/trunk/src/main/resources/META-INF/localization/BSPMessages_fr.properties?rev=1066664&view=auto
==============================================================================
--- commons/sandbox/bsp/trunk/src/main/resources/META-INF/localization/BSPMessages_fr.properties (added)
+++ commons/sandbox/bsp/trunk/src/main/resources/META-INF/localization/BSPMessages_fr.properties Wed Feb  2 22:21:05 2011
@@ -0,0 +1,26 @@
+# 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.
+
+# method not supported in dimension {0}
+NOT_SUPPORTED_IN_DIMENSION_N = m\u00e9thode non mise en \u0153uvre en dimension {0}
+
+# an outline boundary loop is open
+OUTLINE_BOUNDARY_LOOP_OPEN = une boucle de fronti\u00e8re n''est pas ferm\u00e9e
+
+# some outline boundary loops cross each other
+CROSSING_BOUNDARY_LOOPS = des boucles de fronti\u00e8res se chevauchent
+
+# non-invertible affine transform collapses some lines into single points
+NON_INVERTIBLE_TRANSFORM = transformation non inversible d\u00e9g\u00e9n\u00e9rant des lignes en simples points

Propchange: commons/sandbox/bsp/trunk/src/main/resources/META-INF/localization/BSPMessages_fr.properties
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/bsp/trunk/src/main/resources/META-INF/localization/BSPMessages_fr.properties
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision

Added: commons/sandbox/bsp/trunk/src/test/java/org/apache/commons/bsp/euclidean/oneD/IntervalsSetTest.java
URL: http://svn.apache.org/viewvc/commons/sandbox/bsp/trunk/src/test/java/org/apache/commons/bsp/euclidean/oneD/IntervalsSetTest.java?rev=1066664&view=auto
==============================================================================
--- commons/sandbox/bsp/trunk/src/test/java/org/apache/commons/bsp/euclidean/oneD/IntervalsSetTest.java (added)
+++ commons/sandbox/bsp/trunk/src/test/java/org/apache/commons/bsp/euclidean/oneD/IntervalsSetTest.java Wed Feb  2 22:21:05 2011
@@ -0,0 +1,96 @@
+/*
+ * 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.bsp.euclidean.oneD;
+
+import java.util.List;
+
+import org.apache.commons.bsp.euclidean.oneD.Interval;
+import org.apache.commons.bsp.euclidean.oneD.IntervalsSet;
+import org.apache.commons.bsp.euclidean.oneD.Point1D;
+import org.apache.commons.bsp.partitioning.Region;
+import org.apache.commons.math.util.FastMath;
+import org.junit.Assert;
+import org.junit.Test;
+
+public class IntervalsSetTest {
+
+    @Test
+    public void testInterval() {
+        IntervalsSet set = new IntervalsSet(2.3, 5.7);
+        Assert.assertEquals(3.4, set.getSize(), 1.0e-10);
+        Assert.assertEquals(4.0, ((Point1D) set.getBarycenter()).getAbscissa(), 1.0e-10);
+        Assert.assertEquals(Region.Location.BOUNDARY, set.checkPoint(new Point1D(2.3)));
+        Assert.assertEquals(Region.Location.BOUNDARY, set.checkPoint(new Point1D(5.7)));
+        Assert.assertEquals(Region.Location.OUTSIDE,  set.checkPoint(new Point1D(1.2)));
+        Assert.assertEquals(Region.Location.OUTSIDE,  set.checkPoint(new Point1D(8.7)));
+        Assert.assertEquals(Region.Location.INSIDE,   set.checkPoint(new Point1D(3.0)));
+        Assert.assertEquals(2.3, set.getInf(), 1.0e-10);
+        Assert.assertEquals(5.7, set.getSup(), 1.0e-10);
+    }
+
+    @Test
+    public void testInfinite() {
+        IntervalsSet set = new IntervalsSet(9.0, Double.POSITIVE_INFINITY);
+        Assert.assertEquals(Region.Location.BOUNDARY, set.checkPoint(new Point1D(9.0)));
+        Assert.assertEquals(Region.Location.OUTSIDE,  set.checkPoint(new Point1D(8.4)));
+        for (double e = 1.0; e <= 6.0; e += 1.0) {
+            Assert.assertEquals(Region.Location.INSIDE,
+                                set.checkPoint(new Point1D(FastMath.pow(10.0, e))));
+        }
+        Assert.assertTrue(Double.isInfinite(set.getSize()));
+        Assert.assertEquals(9.0, set.getInf(), 1.0e-10);
+        Assert.assertTrue(Double.isInfinite(set.getSup()));
+
+        set = (IntervalsSet) set.getComplement();
+        Assert.assertEquals(9.0, set.getSup(), 1.0e-10);
+        Assert.assertTrue(Double.isInfinite(set.getInf()));
+
+    }
+
+    @Test
+    public void testMultiple() {
+        IntervalsSet set = (IntervalsSet)
+        Region.intersection(Region.union(Region.difference(new IntervalsSet(1.0, 6.0),
+                                                           new IntervalsSet(3.0, 5.0)),
+                                                           new IntervalsSet(9.0, Double.POSITIVE_INFINITY)),
+                                                           new IntervalsSet(Double.NEGATIVE_INFINITY, 11.0));
+        Assert.assertEquals(5.0, set.getSize(), 1.0e-10);
+        Assert.assertEquals(5.9, ((Point1D) set.getBarycenter()).getAbscissa(), 1.0e-10);
+        Assert.assertEquals(Region.Location.OUTSIDE,  set.checkPoint(new Point1D(0.0)));
+        Assert.assertEquals(Region.Location.OUTSIDE,  set.checkPoint(new Point1D(4.0)));
+        Assert.assertEquals(Region.Location.OUTSIDE,  set.checkPoint(new Point1D(8.0)));
+        Assert.assertEquals(Region.Location.OUTSIDE,  set.checkPoint(new Point1D(12.0)));
+        Assert.assertEquals(Region.Location.INSIDE,   set.checkPoint(new Point1D(1.2)));
+        Assert.assertEquals(Region.Location.INSIDE,   set.checkPoint(new Point1D(5.9)));
+        Assert.assertEquals(Region.Location.INSIDE,   set.checkPoint(new Point1D(9.01)));
+        Assert.assertEquals(Region.Location.BOUNDARY, set.checkPoint(new Point1D(5.0)));
+        Assert.assertEquals(Region.Location.BOUNDARY, set.checkPoint(new Point1D(11.0)));
+        Assert.assertEquals( 1.0, set.getInf(), 1.0e-10);
+        Assert.assertEquals(11.0, set.getSup(), 1.0e-10);
+
+        List<Interval> list = set.asList();
+        Assert.assertEquals(3, list.size());
+        Assert.assertEquals( 1.0, list.get(0).getLower(), 1.0e-10);
+        Assert.assertEquals( 3.0, list.get(0).getUpper(), 1.0e-10);
+        Assert.assertEquals( 5.0, list.get(1).getLower(), 1.0e-10);
+        Assert.assertEquals( 6.0, list.get(1).getUpper(), 1.0e-10);
+        Assert.assertEquals( 9.0, list.get(2).getLower(), 1.0e-10);
+        Assert.assertEquals(11.0, list.get(2).getUpper(), 1.0e-10);
+
+    }
+
+}

Propchange: commons/sandbox/bsp/trunk/src/test/java/org/apache/commons/bsp/euclidean/oneD/IntervalsSetTest.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/bsp/trunk/src/test/java/org/apache/commons/bsp/euclidean/oneD/IntervalsSetTest.java
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision

Added: commons/sandbox/bsp/trunk/src/test/java/org/apache/commons/bsp/euclidean/threeD/LineTest.java
URL: http://svn.apache.org/viewvc/commons/sandbox/bsp/trunk/src/test/java/org/apache/commons/bsp/euclidean/threeD/LineTest.java?rev=1066664&view=auto
==============================================================================
--- commons/sandbox/bsp/trunk/src/test/java/org/apache/commons/bsp/euclidean/threeD/LineTest.java (added)
+++ commons/sandbox/bsp/trunk/src/test/java/org/apache/commons/bsp/euclidean/threeD/LineTest.java Wed Feb  2 22:21:05 2011
@@ -0,0 +1,75 @@
+/*
+ * 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.bsp.euclidean.threeD;
+
+import org.apache.commons.bsp.euclidean.threeD.Line;
+import org.apache.commons.math.geometry.Vector3D;
+import org.apache.commons.math.util.FastMath;
+import org.junit.Assert;
+import org.junit.Test;
+
+public class LineTest {
+
+    @Test
+    public void testContains() {
+        Vector3D p1 = new Vector3D(0, 0, 1);
+        Line l = new Line(p1, new Vector3D(0, 0, 1));
+        Assert.assertTrue(l.contains(p1));
+        Assert.assertTrue(l.contains(new Vector3D(1.0, p1, 0.3, l.getDirection())));
+        Vector3D u = l.getDirection().orthogonal();
+        Vector3D v = Vector3D.crossProduct(l.getDirection(), u);
+        for (double alpha = 0; alpha < 2 * FastMath.PI; alpha += 0.3) {
+            Assert.assertTrue(! l.contains(p1.add(new Vector3D(FastMath.cos(alpha), u,
+                                                               FastMath.sin(alpha), v))));
+        }
+    }
+
+    @Test
+    public void testSimilar() {
+        Vector3D p1  = new Vector3D (1.2, 3.4, -5.8);
+        Vector3D p2  = new Vector3D (3.4, -5.8, 1.2);
+        Line     lA  = new Line(p1, p2.subtract(p1));
+        Line     lB  = new Line(p2, p1.subtract(p2));
+        Assert.assertTrue(lA.isSimilarTo(lB));
+        Assert.assertTrue(! lA.isSimilarTo(new Line(p1, lA.getDirection().orthogonal())));
+    }
+
+    @Test
+    public void testPointDistance() {
+        Line l = new Line(new Vector3D(0, 1, 1), new Vector3D(0, 1, 1));
+        Assert.assertEquals(FastMath.sqrt(3.0 / 2.0), l.distance(new Vector3D(1, 0, 1)), 1.0e-10);
+        Assert.assertEquals(0, l.distance(new Vector3D(0, -4, -4)), 1.0e-10);
+    }
+
+    @Test
+    public void testLineDistance() {
+        Line l = new Line(new Vector3D(0, 1, 1), new Vector3D(0, 1, 1));
+        Assert.assertEquals(1.0,
+                            l.distance(new Line(new Vector3D(1, 0, 1), Vector3D.PLUS_K)),
+                            1.0e-10);
+        Assert.assertEquals(0.5,
+                            l.distance(new Line(new Vector3D(-0.5, 0, 0), new Vector3D(0, -1, -1))),
+                            1.0e-10);
+        Assert.assertEquals(0.0,
+                            l.distance(l),
+                            1.0e-10);
+        Assert.assertEquals(0.0,
+                            l.distance(new Line(new Vector3D(0, -4, -4), new Vector3D(0, -1, -1))),
+                            1.0e-10);
+    }
+
+}

Propchange: commons/sandbox/bsp/trunk/src/test/java/org/apache/commons/bsp/euclidean/threeD/LineTest.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/bsp/trunk/src/test/java/org/apache/commons/bsp/euclidean/threeD/LineTest.java
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision

Added: commons/sandbox/bsp/trunk/src/test/java/org/apache/commons/bsp/euclidean/threeD/PlaneTest.java
URL: http://svn.apache.org/viewvc/commons/sandbox/bsp/trunk/src/test/java/org/apache/commons/bsp/euclidean/threeD/PlaneTest.java?rev=1066664&view=auto
==============================================================================
--- commons/sandbox/bsp/trunk/src/test/java/org/apache/commons/bsp/euclidean/threeD/PlaneTest.java (added)
+++ commons/sandbox/bsp/trunk/src/test/java/org/apache/commons/bsp/euclidean/threeD/PlaneTest.java Wed Feb  2 22:21:05 2011
@@ -0,0 +1,168 @@
+/*
+ * 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.bsp.euclidean.threeD;
+
+import org.apache.commons.bsp.euclidean.threeD.Line;
+import org.apache.commons.bsp.euclidean.threeD.Plane;
+import org.apache.commons.bsp.euclidean.threeD.Point3D;
+import org.apache.commons.math.geometry.Rotation;
+import org.apache.commons.math.geometry.Vector3D;
+import org.junit.Assert;
+import org.junit.Test;
+
+public class PlaneTest {
+
+    @Test
+    public void testContains() {
+        Plane p = new Plane(new Vector3D(0, 0, 1), new Vector3D(0, 0, 1));
+        Assert.assertTrue(p.contains(new Point3D(0, 0, 1)));
+        Assert.assertTrue(p.contains(new Point3D(17, -32, 1)));
+        Assert.assertTrue(! p.contains(new Point3D(17, -32, 1.001)));
+    }
+
+    @Test
+    public void testOffset() {
+        Vector3D p1 = new Vector3D(1, 1, 1);
+        Plane p = new Plane(p1, new Vector3D(0.2, 0, 0));
+        Assert.assertEquals(-5.0, p.getOffset(new Point3D(-4, 0, 0)), 1.0e-10);
+        Assert.assertEquals(+5.0, p.getOffset(new Point3D(6, 10, -12)), 1.0e-10);
+        Assert.assertEquals(0.3,
+                            p.getOffset(new Point3D(1.0, p1, 0.3, p.getNormal())),
+                            1.0e-10);
+        Assert.assertEquals(-0.3,
+                            p.getOffset(new Point3D(1.0, p1, -0.3, p.getNormal())),
+                            1.0e-10);
+    }
+
+    @Test
+    public void testPoint() {
+        Plane p = new Plane(new Vector3D(2, -3, 1), new Vector3D(1, 4, 9));
+        Assert.assertTrue(p.contains(p.getOrigin()));
+    }
+
+    @Test
+    public void testThreePoints() {
+        Point3D p1 = new Point3D(1.2, 3.4, -5.8);
+        Point3D p2 = new Point3D(3.4, -5.8, 1.2);
+        Point3D p3 = new Point3D(-2.0, 4.3, 0.7);
+        Plane    p  = new Plane(p1, p2, p3);
+        Assert.assertTrue(p.contains(p1));
+        Assert.assertTrue(p.contains(p2));
+        Assert.assertTrue(p.contains(p3));
+    }
+
+    @Test
+    public void testRotate() {
+        Point3D p1 = new Point3D(1.2, 3.4, -5.8);
+        Point3D p2 = new Point3D(3.4, -5.8, 1.2);
+        Point3D p3 = new Point3D(-2.0, 4.3, 0.7);
+        Plane    p  = new Plane(p1, p2, p3);
+        Vector3D oldNormal = p.getNormal();
+
+        p = p.rotate(p2, new Rotation(p2.subtract(p1), 1.7));
+        Assert.assertTrue(p.contains(p1));
+        Assert.assertTrue(p.contains(p2));
+        Assert.assertTrue(! p.contains(p3));
+
+        p = p.rotate(p2, new Rotation(oldNormal, 0.1));
+        Assert.assertTrue(! p.contains(p1));
+        Assert.assertTrue(p.contains(p2));
+        Assert.assertTrue(! p.contains(p3));
+
+        p = p.rotate(p1, new Rotation(oldNormal, 0.1));
+        Assert.assertTrue(! p.contains(p1));
+        Assert.assertTrue(! p.contains(p2));
+        Assert.assertTrue(! p.contains(p3));
+
+    }
+
+    @Test
+    public void testTranslate() {
+        Point3D p1 = new Point3D(1.2, 3.4, -5.8);
+        Point3D p2 = new Point3D(3.4, -5.8, 1.2);
+        Point3D p3 = new Point3D(-2.0, 4.3, 0.7);
+        Plane    p  = new Plane(p1, p2, p3);
+
+        p = p.translate(new Vector3D(2.0, p.getU(), -1.5, p.getV()));
+        Assert.assertTrue(p.contains(p1));
+        Assert.assertTrue(p.contains(p2));
+        Assert.assertTrue(p.contains(p3));
+
+        p = p.translate(new Vector3D(-1.2, p.getNormal()));
+        Assert.assertTrue(! p.contains(p1));
+        Assert.assertTrue(! p.contains(p2));
+        Assert.assertTrue(! p.contains(p3));
+
+        p = p.translate(new Vector3D(+1.2, p.getNormal()));
+        Assert.assertTrue(p.contains(p1));
+        Assert.assertTrue(p.contains(p2));
+        Assert.assertTrue(p.contains(p3));
+
+    }
+
+    @Test
+    public void testIntersection() {
+        Plane p = new Plane(new Vector3D(1, 2, 3), new Vector3D(-4, 1, -5));
+        Line  l = new Line(new Vector3D(0.2, -3.5, 0.7), new Vector3D(1, 1, -1));
+        Point3D point = p.intersection(l);
+        Assert.assertTrue(p.contains(point));
+        Assert.assertTrue(l.contains(point));
+        Assert.assertNull(p.intersection(new Line(new Vector3D(10, 10, 10),
+                                                  p.getNormal().orthogonal())));
+    }
+
+    @Test
+    public void testIntersection2() {
+        Vector3D p1  = new Vector3D (1.2, 3.4, -5.8);
+        Vector3D p2  = new Vector3D (3.4, -5.8, 1.2);
+        Plane    pA  = new Plane(p1, p2, new Vector3D (-2.0, 4.3, 0.7));
+        Plane    pB  = new Plane(p1, new Vector3D (11.4, -3.8, 5.1), p2);
+        Line     l   = (Line) pA.intersection(pB);
+        Assert.assertTrue(l.contains(p1));
+        Assert.assertTrue(l.contains(p2));
+        Assert.assertNull(pA.intersection(pA));
+    }
+
+    @Test
+    public void testIntersection3() {
+        Vector3D reference = new Vector3D (1.2, 3.4, -5.8);
+        Plane p1 = new Plane(reference, new Vector3D(1, 3, 3));
+        Plane p2 = new Plane(reference, new Vector3D(-2, 4, 0));
+        Plane p3 = new Plane(reference, new Vector3D(7, 0, -4));
+        Vector3D p = Plane.intersection(p1, p2, p3);
+        Assert.assertEquals(reference.getX(), p.getX(), 1.0e-10);
+        Assert.assertEquals(reference.getY(), p.getY(), 1.0e-10);
+        Assert.assertEquals(reference.getZ(), p.getZ(), 1.0e-10);
+    }
+
+    @Test
+    public void testSimilar() {
+        Vector3D p1  = new Vector3D (1.2, 3.4, -5.8);
+        Vector3D p2  = new Vector3D (3.4, -5.8, 1.2);
+        Vector3D p3  = new Vector3D (-2.0, 4.3, 0.7);
+        Plane    pA  = new Plane(p1, p2, p3);
+        Plane    pB  = new Plane(p1, new Vector3D (11.4, -3.8, 5.1), p2);
+        Assert.assertTrue(! pA.isSimilarTo(pB));
+        Assert.assertTrue(pA.isSimilarTo(pA));
+        Assert.assertTrue(pA.isSimilarTo(new Plane(p1, p3, p2)));
+        Vector3D shift = new Vector3D(0.3, pA.getNormal());
+        Assert.assertTrue(! pA.isSimilarTo(new Plane(p1.add(shift),
+                                                     p3.add(shift),
+                                                     p2.add(shift))));
+    }
+
+}

Propchange: commons/sandbox/bsp/trunk/src/test/java/org/apache/commons/bsp/euclidean/threeD/PlaneTest.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/bsp/trunk/src/test/java/org/apache/commons/bsp/euclidean/threeD/PlaneTest.java
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision

Added: commons/sandbox/bsp/trunk/src/test/java/org/apache/commons/bsp/euclidean/threeD/PolyhedronsSetTest.java
URL: http://svn.apache.org/viewvc/commons/sandbox/bsp/trunk/src/test/java/org/apache/commons/bsp/euclidean/threeD/PolyhedronsSetTest.java?rev=1066664&view=auto
==============================================================================
--- commons/sandbox/bsp/trunk/src/test/java/org/apache/commons/bsp/euclidean/threeD/PolyhedronsSetTest.java (added)
+++ commons/sandbox/bsp/trunk/src/test/java/org/apache/commons/bsp/euclidean/threeD/PolyhedronsSetTest.java Wed Feb  2 22:21:05 2011
@@ -0,0 +1,243 @@
+/*
+ * 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.bsp.euclidean.threeD;
+
+import java.util.Arrays;
+
+import org.apache.commons.bsp.euclidean.threeD.Plane;
+import org.apache.commons.bsp.euclidean.threeD.Point3D;
+import org.apache.commons.bsp.euclidean.threeD.PolyhedronsSet;
+import org.apache.commons.bsp.euclidean.twoD.Point2D;
+import org.apache.commons.bsp.euclidean.twoD.PolygonsSet;
+import org.apache.commons.bsp.partitioning.BSPTree;
+import org.apache.commons.bsp.partitioning.BSPTreeVisitor;
+import org.apache.commons.bsp.partitioning.Hyperplane;
+import org.apache.commons.bsp.partitioning.Region;
+import org.apache.commons.bsp.partitioning.SubHyperplane;
+import org.apache.commons.math.geometry.Rotation;
+import org.apache.commons.math.geometry.Vector3D;
+import org.apache.commons.math.util.FastMath;
+import org.junit.Assert;
+import org.junit.Test;
+
+public class PolyhedronsSetTest {
+
+    @Test
+    public void testBox() {
+        PolyhedronsSet tree = new PolyhedronsSet(0, 1, 0, 1, 0, 1);
+        Assert.assertEquals(1.0, tree.getSize(), 1.0e-10);
+        Assert.assertEquals(6.0, tree.getBoundarySize(), 1.0e-10);
+        Vector3D barycenter = (Vector3D) tree.getBarycenter();
+        Assert.assertEquals(0.5, barycenter.getX(), 1.0e-10);
+        Assert.assertEquals(0.5, barycenter.getY(), 1.0e-10);
+        Assert.assertEquals(0.5, barycenter.getZ(), 1.0e-10);
+        for (double x = -0.25; x < 1.25; x += 0.1) {
+            boolean xOK = (x >= 0.0) && (x <= 1.0);
+            for (double y = -0.25; y < 1.25; y += 0.1) {
+                boolean yOK = (y >= 0.0) && (y <= 1.0);
+                for (double z = -0.25; z < 1.25; z += 0.1) {
+                    boolean zOK = (z >= 0.0) && (z <= 1.0);
+                    Region.Location expected =
+                        (xOK && yOK && zOK) ? Region.Location.INSIDE : Region.Location.OUTSIDE;
+                    Assert.assertEquals(expected, tree.checkPoint(new Point3D(x, y, z)));
+                }
+            }
+        }
+        checkPoints(Region.Location.BOUNDARY, tree, new Point3D[] {
+            new Point3D(0.0, 0.5, 0.5),
+            new Point3D(1.0, 0.5, 0.5),
+            new Point3D(0.5, 0.0, 0.5),
+            new Point3D(0.5, 1.0, 0.5),
+            new Point3D(0.5, 0.5, 0.0),
+            new Point3D(0.5, 0.5, 1.0)
+        });
+        checkPoints(Region.Location.OUTSIDE, tree, new Point3D[] {
+            new Point3D(0.0, 1.2, 1.2),
+            new Point3D(1.0, 1.2, 1.2),
+            new Point3D(1.2, 0.0, 1.2),
+            new Point3D(1.2, 1.0, 1.2),
+            new Point3D(1.2, 1.2, 0.0),
+            new Point3D(1.2, 1.2, 1.0)
+        });
+    }
+
+    @Test
+    public void testTetrahedron() {
+        Point3D vertex1 = new Point3D(1, 2, 3);
+        Point3D vertex2 = new Point3D(2, 2, 4);
+        Point3D vertex3 = new Point3D(2, 3, 3);
+        Point3D vertex4 = new Point3D(1, 3, 4);
+        PolyhedronsSet tree =
+            (PolyhedronsSet) Region.buildConvex(Arrays.asList(new Hyperplane[] {
+                new Plane(vertex3, vertex2, vertex1),
+                new Plane(vertex2, vertex3, vertex4),
+                new Plane(vertex4, vertex3, vertex1),
+                new Plane(vertex1, vertex2, vertex4)
+            }));
+        Assert.assertEquals(1.0 / 3.0, tree.getSize(), 1.0e-10);
+        Assert.assertEquals(2.0 * FastMath.sqrt(3.0), tree.getBoundarySize(), 1.0e-10);
+        Vector3D barycenter = (Vector3D) tree.getBarycenter();
+        Assert.assertEquals(1.5, barycenter.getX(), 1.0e-10);
+        Assert.assertEquals(2.5, barycenter.getY(), 1.0e-10);
+        Assert.assertEquals(3.5, barycenter.getZ(), 1.0e-10);
+        double third = 1.0 / 3.0;
+        checkPoints(Region.Location.BOUNDARY, tree, new Point3D[] {
+            vertex1, vertex2, vertex3, vertex4,
+            new Point3D(third, vertex1, third, vertex2, third, vertex3),
+            new Point3D(third, vertex2, third, vertex3, third, vertex4),
+            new Point3D(third, vertex3, third, vertex4, third, vertex1),
+            new Point3D(third, vertex4, third, vertex1, third, vertex2)
+        });
+        checkPoints(Region.Location.OUTSIDE, tree, new Point3D[] {
+            new Point3D(1, 2, 4),
+            new Point3D(2, 2, 3),
+            new Point3D(2, 3, 4),
+            new Point3D(1, 3, 3)
+        });
+    }
+
+    @Test
+    public void testIsometry() {
+        Vector3D vertex1 = new Vector3D(1.1, 2.2, 3.3);
+        Vector3D vertex2 = new Vector3D(2.0, 2.4, 4.2);
+        Vector3D vertex3 = new Vector3D(2.8, 3.3, 3.7);
+        Vector3D vertex4 = new Vector3D(1.0, 3.6, 4.5);
+        PolyhedronsSet tree =
+            (PolyhedronsSet) Region.buildConvex(Arrays.asList(new Hyperplane[] {
+                new Plane(vertex3, vertex2, vertex1),
+                new Plane(vertex2, vertex3, vertex4),
+                new Plane(vertex4, vertex3, vertex1),
+                new Plane(vertex1, vertex2, vertex4)
+            }));
+        Vector3D barycenter = (Vector3D) tree.getBarycenter();
+        Vector3D s = new Vector3D(10.2, 4.3, -6.7);
+        Vector3D c = new Vector3D(-0.2, 2.1, -3.2);
+        Rotation r = new Rotation(new Vector3D(6.2, -4.4, 2.1), 0.12);
+
+        tree = tree.rotate(c, r).translate(s);
+
+        Vector3D newB =
+            new Vector3D(1.0, s,
+                         1.0, c,
+                         1.0, r.applyTo(barycenter.subtract(c)));
+        Assert.assertEquals(0.0,
+                            newB.subtract((Vector3D) tree.getBarycenter()).getNorm(),
+                            1.0e-10);
+
+        final Vector3D[] expectedV = new Vector3D[] {
+            new Vector3D(1.0, s,
+                         1.0, c,
+                         1.0, r.applyTo(vertex1.subtract(c))),
+                         new Vector3D(1.0, s,
+                                      1.0, c,
+                                      1.0, r.applyTo(vertex2.subtract(c))),
+                                      new Vector3D(1.0, s,
+                                                   1.0, c,
+                                                   1.0, r.applyTo(vertex3.subtract(c))),
+                                                   new Vector3D(1.0, s,
+                                                                1.0, c,
+                                                                1.0, r.applyTo(vertex4.subtract(c)))
+        };
+        tree.getTree(true).visit(new BSPTreeVisitor() {
+
+            public Order visitOrder(BSPTree node) {
+                return Order.MINUS_SUB_PLUS;
+            }
+
+            public void visitInternalNode(BSPTree node) {
+                Region.BoundaryAttribute attribute =
+                    (Region.BoundaryAttribute) node.getAttribute();
+                if (attribute.getPlusOutside() != null) {
+                    checkFacet(attribute.getPlusOutside());
+                }
+                if (attribute.getPlusInside() != null) {
+                    checkFacet(attribute.getPlusInside());
+                }
+            }
+
+            public void visitLeafNode(BSPTree node) {
+            }
+
+            private void checkFacet(SubHyperplane facet) {
+                Plane plane = (Plane) facet.getHyperplane();
+                Point2D[][] vertices =
+                    ((PolygonsSet) facet.getRemainingRegion()).getVertices();
+                Assert.assertEquals(1, vertices.length);
+                for (int i = 0; i < vertices[0].length; ++i) {
+                    Vector3D v = (Vector3D) plane.toSpace(vertices[0][i]);
+                    double d = Double.POSITIVE_INFINITY;
+                    for (int k = 0; k < expectedV.length; ++k) {
+                        d = FastMath.min(d, v.subtract(expectedV[k]).getNorm());
+                    }
+                    Assert.assertEquals(0, d, 1.0e-10);
+                }
+            }
+
+        });
+
+    }
+
+    @Test
+    public void testBuildBox() {
+        double x = 1.0;
+        double y = 2.0;
+        double z = 3.0;
+        double w = 0.1;
+        double l = 1.0;
+        PolyhedronsSet tree =
+            new PolyhedronsSet(x - l, x + l, y - w, y + w, z - w, z + w);
+        Vector3D barycenter = (Vector3D) tree.getBarycenter();
+        Assert.assertEquals(x, barycenter.getX(), 1.0e-10);
+        Assert.assertEquals(y, barycenter.getY(), 1.0e-10);
+        Assert.assertEquals(z, barycenter.getZ(), 1.0e-10);
+        Assert.assertEquals(8 * l * w * w, tree.getSize(), 1.0e-10);
+        Assert.assertEquals(8 * w * (2 * l + w), tree.getBoundarySize(), 1.0e-10);
+    }
+
+    @Test
+    public void testCross() {
+
+        double x = 1.0;
+        double y = 2.0;
+        double z = 3.0;
+        double w = 0.1;
+        double l = 1.0;
+        PolyhedronsSet xBeam =
+            new PolyhedronsSet(x - l, x + l, y - w, y + w, z - w, z + w);
+        PolyhedronsSet yBeam =
+            new PolyhedronsSet(x - w, x + w, y - l, y + l, z - w, z + w);
+        PolyhedronsSet zBeam =
+            new PolyhedronsSet(x - w, x + w, y - w, y + w, z - l, z + l);
+        PolyhedronsSet tree =
+            (PolyhedronsSet) Region.union(xBeam, Region.union(yBeam, zBeam));
+        Vector3D barycenter = (Vector3D) tree.getBarycenter();
+
+        Assert.assertEquals(x, barycenter.getX(), 1.0e-10);
+        Assert.assertEquals(y, barycenter.getY(), 1.0e-10);
+        Assert.assertEquals(z, barycenter.getZ(), 1.0e-10);
+        Assert.assertEquals(8 * w * w * (3 * l - 2 * w), tree.getSize(), 1.0e-10);
+        Assert.assertEquals(24 * w * (2 * l - w), tree.getBoundarySize(), 1.0e-10);
+
+    }
+
+    private void checkPoints(Region.Location expected, PolyhedronsSet tree, Point3D[] points) {
+        for (int i = 0; i < points.length; ++i) {
+            Assert.assertEquals(expected, tree.checkPoint(points[i]));
+        }
+    }
+
+}

Propchange: commons/sandbox/bsp/trunk/src/test/java/org/apache/commons/bsp/euclidean/threeD/PolyhedronsSetTest.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/bsp/trunk/src/test/java/org/apache/commons/bsp/euclidean/threeD/PolyhedronsSetTest.java
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision

Added: commons/sandbox/bsp/trunk/src/test/java/org/apache/commons/bsp/euclidean/twoD/EdgeTest.java
URL: http://svn.apache.org/viewvc/commons/sandbox/bsp/trunk/src/test/java/org/apache/commons/bsp/euclidean/twoD/EdgeTest.java?rev=1066664&view=auto
==============================================================================
--- commons/sandbox/bsp/trunk/src/test/java/org/apache/commons/bsp/euclidean/twoD/EdgeTest.java (added)
+++ commons/sandbox/bsp/trunk/src/test/java/org/apache/commons/bsp/euclidean/twoD/EdgeTest.java Wed Feb  2 22:21:05 2011
@@ -0,0 +1,111 @@
+/*
+ * 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.bsp.euclidean.twoD;
+
+import org.apache.commons.bsp.euclidean.twoD.Edge;
+import org.apache.commons.bsp.euclidean.twoD.Vertex;
+import org.apache.commons.math.util.FastMath;
+import org.junit.Assert;
+import org.junit.Test;
+
+public class EdgeTest {
+
+    @Test
+    public void testLength() {
+        Edge e = new Edge(new Vertex(0, 1),new Vertex(1, 2));
+        Assert.assertEquals(FastMath.sqrt(2), e.getLength(), 1.0e-10);
+    }
+
+    @Test
+    public void testParallelEdgeOffsetFactors() {
+        Vertex v1  = new Vertex( 2, -1);
+        Vertex v2  = new Vertex(-2,  0);
+        Vertex v3  = new Vertex( 0,  3);
+        Vertex v4  = new Vertex( 4,  2);
+        Edge   e23 = new Edge(v2, v3);
+        Edge   e34 = new Edge(v3, v4);
+        Edge   e41 = new Edge(v4, v1);
+        double offset = e41.getLine().getOffset(e23.getLine());
+        double coeffs[] = e41.parallelEdgeOffsetFactors(e23);
+        Assert.assertEquals(coeffs[0], 1, 1.0e-10);
+        Assert.assertEquals(coeffs[1], 1, 1.0e-10);
+        e23.getLine().setOriginOffset(e23.getLine().getOriginOffset() + 0.12);
+        e34.getLine().setOriginOffset(e34.getLine().getOriginOffset() + 0.27);
+        e41.getLine().setOriginOffset(e41.getLine().getOriginOffset() - 0.8);
+        v1.update();
+        v2.update();
+        v3.update();
+        v4.update();
+        Assert.assertEquals(offset - 0.68,
+                            e41.getLine().getOffset(e23.getLine()),
+                            1.0e-10);
+    }
+
+    @Test
+    public void testVertexOffsetFactors() {
+        Vertex v1 = new Vertex(-2, -2);
+        Vertex v2 = new Vertex( 2,  1);
+        Vertex v3 = new Vertex( 5, -3);
+        Edge   e0 = new Edge(v1, v2);
+        Edge   ei = new Edge(v2, v3);
+        Edge   el = new Edge(v3, v1);
+        double coeffs[] = e0.vertexOffsetFactors(v3);
+        double offset = e0.getLine().getOffset(v3);
+        Assert.assertEquals(5.0, offset, 1.0e-10);
+        Assert.assertEquals(offset,
+                            coeffs [0] * e0.getLine().getOriginOffset()
+                            + coeffs [1] * ei.getLine().getOriginOffset()
+                            + coeffs [2] * el.getLine().getOriginOffset(),
+                            1.0e-10);
+        e0.getLine().setOriginOffset(e0.getLine().getOriginOffset() + 0.1);
+        ei.getLine().setOriginOffset(ei.getLine().getOriginOffset() + 0.2);
+        el.getLine().setOriginOffset(el.getLine().getOriginOffset() + 0.8);
+        v1.update();
+        v2.update();
+        v3.update();
+        Assert.assertEquals(offset + 0.1 * coeffs[0] + 0.2 * coeffs[1] + 0.8 * coeffs[2],
+                            e0.getLine().getOffset(v3),
+                            1.0e-10);
+    }
+
+    @Test
+    public void testLengthFactors() {
+        Vertex v1 = new Vertex(-2, -2);
+        Vertex v2 = new Vertex( 2,  1);
+        Vertex v3 = new Vertex( 5, -3);
+        Edge   es = new Edge(v1, v2);
+        Edge   e0 = new Edge(v2, v3);
+        Edge   ee = new Edge(v3, v1);
+        double coeffs[] = e0.lengthFactors();
+        double length = e0.getLength();
+        Assert.assertEquals(length,
+                            coeffs [0] * es.getLine().getOriginOffset()
+                            + coeffs [1] * e0.getLine().getOriginOffset()
+                            + coeffs [2] * ee.getLine().getOriginOffset(),
+                            1.0e-10);
+        es.getLine().setOriginOffset(es.getLine().getOriginOffset() + 0.1);
+        e0.getLine().setOriginOffset(e0.getLine().getOriginOffset() + 0.2);
+        ee.getLine().setOriginOffset(ee.getLine().getOriginOffset() + 0.8);
+        v1.update();
+        v2.update();
+        v3.update();
+        Assert.assertEquals(length + 0.1 * coeffs[0] + 0.2 * coeffs[1] + 0.8 * coeffs[2],
+                            e0.getLength(),
+                            1.0e-10);
+    }
+
+}

Propchange: commons/sandbox/bsp/trunk/src/test/java/org/apache/commons/bsp/euclidean/twoD/EdgeTest.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/bsp/trunk/src/test/java/org/apache/commons/bsp/euclidean/twoD/EdgeTest.java
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision

Added: commons/sandbox/bsp/trunk/src/test/java/org/apache/commons/bsp/euclidean/twoD/LineTest.java
URL: http://svn.apache.org/viewvc/commons/sandbox/bsp/trunk/src/test/java/org/apache/commons/bsp/euclidean/twoD/LineTest.java?rev=1066664&view=auto
==============================================================================
--- commons/sandbox/bsp/trunk/src/test/java/org/apache/commons/bsp/euclidean/twoD/LineTest.java (added)
+++ commons/sandbox/bsp/trunk/src/test/java/org/apache/commons/bsp/euclidean/twoD/LineTest.java Wed Feb  2 22:21:05 2011
@@ -0,0 +1,129 @@
+/*
+ * 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.bsp.euclidean.twoD;
+
+import org.apache.commons.bsp.euclidean.oneD.Point1D;
+import org.apache.commons.bsp.euclidean.twoD.Line;
+import org.apache.commons.bsp.euclidean.twoD.Point2D;
+import org.apache.commons.bsp.partitioning.Transform;
+import org.apache.commons.math.util.FastMath;
+import org.junit.Assert;
+import org.junit.Test;
+
+import java.awt.geom.AffineTransform;
+
+public class LineTest {
+
+    @Test
+    public void testContains() {
+        Line l = new Line(new Point2D(0, 1), new Point2D(1, 2));
+        Assert.assertTrue(l.contains(new Point2D(0, 1)));
+        Assert.assertTrue(l.contains(new Point2D(1, 2)));
+        Assert.assertTrue(l.contains(new Point2D(7, 8)));
+        Assert.assertTrue(! l.contains(new Point2D(8, 7)));
+    }
+
+    @Test
+    public void testAbscissa() {
+        Line l = new Line(new Point2D(2, 1), new Point2D(-2, -2));
+        Assert.assertEquals(0.0,
+                            ((Point1D) l.toSubSpace(new Point2D(-3,  4))).getAbscissa(),
+                            1.0e-10);
+        Assert.assertEquals(0.0,
+                            ((Point1D) l.toSubSpace(new Point2D( 3, -4))).getAbscissa(),
+                            1.0e-10);
+        Assert.assertEquals(-5.0,
+                            ((Point1D) l.toSubSpace(new Point2D( 7, -1))).getAbscissa(),
+                            1.0e-10);
+        Assert.assertEquals( 5.0,
+                             ((Point1D) l.toSubSpace(new Point2D(-1, -7))).getAbscissa(),
+                             1.0e-10);
+    }
+
+    @Test
+    public void testOffset() {
+        Line l = new Line(new Point2D(2, 1), new Point2D(-2, -2));
+        Assert.assertEquals(-5.0, l.getOffset(new Point2D(5, -3)), 1.0e-10);
+        Assert.assertEquals(+5.0, l.getOffset(new Point2D(-5, 2)), 1.0e-10);
+    }
+
+    @Test
+    public void testPointAt() {
+        Line l = new Line(new Point2D(2, 1), new Point2D(-2, -2));
+        for (double a = -2.0; a < 2.0; a += 0.2) {
+            Point1D pA = new Point1D(a);
+            Point2D point = (Point2D) l.toSpace(pA);
+            Assert.assertEquals(a, ((Point1D) l.toSubSpace(point)).getAbscissa(), 1.0e-10);
+            Assert.assertEquals(0.0, l.getOffset(point),   1.0e-10);
+            for (double o = -2.0; o < 2.0; o += 0.2) {
+                point = l.getPointAt(pA, o);
+                Assert.assertEquals(a, ((Point1D) l.toSubSpace(point)).getAbscissa(), 1.0e-10);
+                Assert.assertEquals(o, l.getOffset(point),   1.0e-10);
+            }
+        }
+    }
+
+    @Test
+    public void testOriginOffset() {
+        Line l1 = new Line(new Point2D(0, 1), new Point2D(1, 2));
+        Assert.assertEquals(FastMath.sqrt(0.5), l1.getOriginOffset(), 1.0e-10);
+        Line l2 = new Line(new Point2D(1, 2), new Point2D(0, 1));
+        Assert.assertEquals(-FastMath.sqrt(0.5), l2.getOriginOffset(), 1.0e-10);
+    }
+
+    @Test
+    public void testParallel() {
+        Line l1 = new Line(new Point2D(0, 1), new Point2D(1, 2));
+        Line l2 = new Line(new Point2D(2, 2), new Point2D(3, 3));
+        Assert.assertTrue(l1.isParallelTo(l2));
+        Line l3 = new Line(new Point2D(1, 0), new Point2D(0.5, -0.5));
+        Assert.assertTrue(l1.isParallelTo(l3));
+        Line l4 = new Line(new Point2D(1, 0), new Point2D(0.5, -0.51));
+        Assert.assertTrue(! l1.isParallelTo(l4));
+    }
+
+    @Test
+    public void testTransform() {
+
+        Line l1 = new Line(new Point2D(1.0 ,1.0), new Point2D(4.0 ,1.0));
+        Transform t1 = Line.getTransform(new AffineTransform(0.0, 0.5,
+                                                             -1.0, 0.0,
+                                                             1.0, 1.5));
+        Assert.assertEquals(0.5 * FastMath.PI,
+                            ((Line) t1.apply(l1)).getAngle(),
+                            1.0e-10);
+
+        Line l2 = new Line(new Point2D(0.0, 0.0), new Point2D(1.0, 1.0));
+        Transform t2 = Line.getTransform(new AffineTransform(0.0, 0.5,
+                                                             -1.0, 0.0,
+                                                             1.0, 1.5));
+        Assert.assertEquals(FastMath.atan2(1.0, -2.0),
+                            ((Line) t2.apply(l2)).getAngle(),
+                            1.0e-10);
+
+    }
+
+    @Test
+    public void testIntersection() {
+        Line    l1 = new Line(new Point2D( 0, 1), new Point2D(1, 2));
+        Line    l2 = new Line(new Point2D(-1, 2), new Point2D(2, 1));
+        Point2D p  = (Point2D) l1.intersection(l2);
+        Assert.assertEquals(0.5, p.x, 1.0e-10);
+        Assert.assertEquals(1.5, p.y, 1.0e-10);
+    }
+
+}

Propchange: commons/sandbox/bsp/trunk/src/test/java/org/apache/commons/bsp/euclidean/twoD/LineTest.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/bsp/trunk/src/test/java/org/apache/commons/bsp/euclidean/twoD/LineTest.java
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision



Mime
View raw message