partitioning/utilities/AVLTree.java

/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.commons.math3.geometry.partitioning.utilities;

/** This class implements AVL trees.
 *
 * <p>The purpose of this class is to sort elements while allowing
 * duplicate elements (i.e. such that {@code a.equals(b)} is
 * true). The {@code SortedSet} interface does not allow this, so
 * a specific class is needed. Null elements are not allowed.</p>
 *
 * <p>Since the {@code equals} method is not sufficient to
 * differentiate elements, the {@link #delete delete} method is
 * implemented using the equality operator.</p>
 *
 * <p>In order to clearly mark the methods provided here do not have
 * the same semantics as the ones specified in the
 * {@code SortedSet} interface, different names are used
 * ({@code add} has been replaced by {@link #insert insert} and
 * {@code remove} has been replaced by {@link #delete
 * delete}).</p>
 *
 * <p>This class is based on the C implementation Georg Kraml has put
 * in the public domain. Unfortunately, his <a
 * href="www.purists.org/georg/avltree/index.html">page</a> seems not
 * to exist any more.</p>
 *
 * @param <T> the type of the elements
 *
 * @since 3.0
 * @deprecated as of 3.4, this class is not used anymore and considered
 * to be out of scope of Apache Commons Math
 */
@Deprecated
public class AVLTree<T extends Comparable<T>> {

    /** Top level node. */
    private Node top;

    /** Build an empty tree.
     */
    public AVLTree() {
        top = null;
    }

    /** Insert an element in the tree.
     * @param element element to insert (silently ignored if null)
     */
    public void insert(final T element) {
        if (element != null) {
            if (top == null) {
                top = new Node(element, null);
            } else {
                top.insert(element);
            }
        }
    }

    /** Delete an element from the tree.
     * <p>The element is deleted only if there is a node {@code n}
     * containing exactly the element instance specified, i.e. for which
     * {@code n.getElement() == element}. This is purposely
     * <em>different</em> from the specification of the
     * {@code java.util.Set} {@code remove} method (in fact,
     * this is the reason why a specific class has been developed).</p>
     * @param element element to delete (silently ignored if null)
     * @return true if the element was deleted from the tree
     */
    public boolean delete(final T element) {
        if (element != null) {
            for (Node node = getNotSmaller(element); node != null; node = node.getNext()) {
                // loop over all elements neither smaller nor larger
                // than the specified one
                if (node.element == element) {
                    node.delete();
                    return true;
                } else if (node.element.compareTo(element) > 0) {
                    // all the remaining elements are known to be larger,
                    // the element is not in the tree
                    return false;
                }
            }
        }
        return false;
    }

    /** Check if the tree is empty.
     * @return true if the tree is empty
     */
    public boolean isEmpty() {
        return top == null;
    }


    /** Get the number of elements of the tree.
     * @return number of elements contained in the tree
     */
    public int size() {
        return (top == null) ? 0 : top.size();
    }

    /** Get the node whose element is the smallest one in the tree.
     * @return the tree node containing the smallest element in the tree
     * or null if the tree is empty
     * @see #getLargest
     * @see #getNotSmaller
     * @see #getNotLarger
     * @see Node#getPrevious
     * @see Node#getNext
     */
    public Node getSmallest() {
        return (top == null) ? null : top.getSmallest();
    }

    /** Get the node whose element is the largest one in the tree.
     * @return the tree node containing the largest element in the tree
     * or null if the tree is empty
     * @see #getSmallest
     * @see #getNotSmaller
     * @see #getNotLarger
     * @see Node#getPrevious
     * @see Node#getNext
     */
    public Node getLargest() {
        return (top == null) ? null : top.getLargest();
    }

    /** Get the node whose element is not smaller than the reference object.
     * @param reference reference object (may not be in the tree)
     * @return the tree node containing the smallest element not smaller
     * than the reference object or null if either the tree is empty or
     * all its elements are smaller than the reference object
     * @see #getSmallest
     * @see #getLargest
     * @see #getNotLarger
     * @see Node#getPrevious
     * @see Node#getNext
     */
    public Node getNotSmaller(final T reference) {
        Node candidate = null;
        for (Node node = top; node != null;) {
            if (node.element.compareTo(reference) < 0) {
                if (node.right == null) {
                    return candidate;
                }
                node = node.right;
            } else {
                candidate = node;
                if (node.left == null) {
                    return candidate;
                }
                node = node.left;
            }
        }
        return null;
    }

    /** Get the node whose element is not larger than the reference object.
     * @param reference reference object (may not be in the tree)
     * @return the tree node containing the largest element not larger
     * than the reference object (in which case the node is guaranteed
     * not to be empty) or null if either the tree is empty or all its
     * elements are larger than the reference object
     * @see #getSmallest
     * @see #getLargest
     * @see #getNotSmaller
     * @see Node#getPrevious
     * @see Node#getNext
     */
    public Node getNotLarger(final T reference) {
        Node candidate = null;
        for (Node node = top; node != null;) {
            if (node.element.compareTo(reference) > 0) {
                if (node.left == null) {
                    return candidate;
                }
                node = node.left;
            } else {
                candidate = node;
                if (node.right == null) {
                    return candidate;
                }
                node = node.right;
            }
        }
        return null;
    }

    /** Enum for tree skew factor. */
    private enum Skew {
        /** Code for left high trees. */
        LEFT_HIGH,

        /** Code for right high trees. */
        RIGHT_HIGH,

        /** Code for Skew.BALANCED trees. */
        BALANCED;
    }

    /** This class implements AVL trees nodes.
     * <p>AVL tree nodes implement all the logical structure of the
     * tree. Nodes are created by the {@link AVLTree AVLTree} class.</p>
     * <p>The nodes are not independant from each other but must obey
     * specific balancing constraints and the tree structure is
     * rearranged as elements are inserted or deleted from the tree. The
     * creation, modification and tree-related navigation methods have
     * therefore restricted access. Only the order-related navigation,
     * reading and delete methods are public.</p>
     * @see AVLTree
     */
    public class Node {

        /** Element contained in the current node. */
        private T element;

        /** Left sub-tree. */
        private Node left;

        /** Right sub-tree. */
        private Node right;

        /** Parent tree. */
        private Node parent;

        /** Skew factor. */
        private Skew skew;

        /** Build a node for a specified element.
         * @param element element
         * @param parent parent node
         */
        Node(final T element, final Node parent) {
            this.element = element;
            left         = null;
            right        = null;
            this.parent  = parent;
            skew         = Skew.BALANCED;
        }

        /** Get the contained element.
         * @return element contained in the node
         */
        public T getElement() {
            return element;
        }

        /** Get the number of elements of the tree rooted at this node.
         * @return number of elements contained in the tree rooted at this node
         */
        int size() {
            return 1 + ((left  == null) ? 0 : left.size()) + ((right == null) ? 0 : right.size());
        }

        /** Get the node whose element is the smallest one in the tree
         * rooted at this node.
         * @return the tree node containing the smallest element in the
         * tree rooted at this node or null if the tree is empty
         * @see #getLargest
         */
        Node getSmallest() {
            Node node = this;
            while (node.left != null) {
                node = node.left;
            }
            return node;
        }

        /** Get the node whose element is the largest one in the tree
         * rooted at this node.
         * @return the tree node containing the largest element in the
         * tree rooted at this node or null if the tree is empty
         * @see #getSmallest
         */
        Node getLargest() {
            Node node = this;
            while (node.right != null) {
                node = node.right;
            }
            return node;
        }

        /** Get the node containing the next smaller or equal element.
         * @return node containing the next smaller or equal element or
         * null if there is no smaller or equal element in the tree
         * @see #getNext
         */
        public Node getPrevious() {

            if (left != null) {
                final Node node = left.getLargest();
                if (node != null) {
                    return node;
                }
            }

            for (Node node = this; node.parent != null; node = node.parent) {
                if (node != node.parent.left) {
                    return node.parent;
                }
            }

            return null;

        }

        /** Get the node containing the next larger or equal element.
         * @return node containing the next larger or equal element (in
         * which case the node is guaranteed not to be empty) or null if
         * there is no larger or equal element in the tree
         * @see #getPrevious
         */
        public Node getNext() {

            if (right != null) {
                final Node node = right.getSmallest();
                if (node != null) {
                    return node;
                }
            }

            for (Node node = this; node.parent != null; node = node.parent) {
                if (node != node.parent.right) {
                    return node.parent;
                }
            }

            return null;

        }

        /** Insert an element in a sub-tree.
         * @param newElement element to insert
         * @return true if the parent tree should be re-Skew.BALANCED
         */
        boolean insert(final T newElement) {
            if (newElement.compareTo(this.element) < 0) {
                // the inserted element is smaller than the node
                if (left == null) {
                    left = new Node(newElement, this);
                    return rebalanceLeftGrown();
                }
                return left.insert(newElement) ? rebalanceLeftGrown() : false;
            }

            // the inserted element is equal to or greater than the node
            if (right == null) {
                right = new Node(newElement, this);
                return rebalanceRightGrown();
            }
            return right.insert(newElement) ? rebalanceRightGrown() : false;

        }

        /** Delete the node from the tree.
         */
        public void delete() {
            if ((parent == null) && (left == null) && (right == null)) {
                // this was the last node, the tree is now empty
                element = null;
                top     = null;
            } else {

                Node node;
                Node child;
                boolean leftShrunk;
                if ((left == null) && (right == null)) {
                    node       = this;
                    element    = null;
                    leftShrunk = node == node.parent.left;
                    child      = null;
                } else {
                    node       = (left != null) ? left.getLargest() : right.getSmallest();
                    element    = node.element;
                    leftShrunk = node == node.parent.left;
                    child      = (node.left != null) ? node.left : node.right;
                }

                node = node.parent;
                if (leftShrunk) {
                    node.left = child;
                } else {
                    node.right = child;
                }
                if (child != null) {
                    child.parent = node;
                }

                while (leftShrunk ? node.rebalanceLeftShrunk() : node.rebalanceRightShrunk()) {
                    if (node.parent == null) {
                        return;
                    }
                    leftShrunk = node == node.parent.left;
                    node = node.parent;
                }

            }
        }

        /** Re-balance the instance as left sub-tree has grown.
         * @return true if the parent tree should be reSkew.BALANCED too
         */
        private boolean rebalanceLeftGrown() {
            switch (skew) {
            case LEFT_HIGH:
                if (left.skew == Skew.LEFT_HIGH) {
                    rotateCW();
                    skew       = Skew.BALANCED;
                    right.skew = Skew.BALANCED;
                } else {
                    final Skew s = left.right.skew;
                    left.rotateCCW();
                    rotateCW();
                    switch(s) {
                    case LEFT_HIGH:
                        left.skew  = Skew.BALANCED;
                        right.skew = Skew.RIGHT_HIGH;
                        break;
                    case RIGHT_HIGH:
                        left.skew  = Skew.LEFT_HIGH;
                        right.skew = Skew.BALANCED;
                        break;
                    default:
                        left.skew  = Skew.BALANCED;
                        right.skew = Skew.BALANCED;
                    }
                    skew = Skew.BALANCED;
                }
                return false;
            case RIGHT_HIGH:
                skew = Skew.BALANCED;
                return false;
            default:
                skew = Skew.LEFT_HIGH;
                return true;
            }
        }

        /** Re-balance the instance as right sub-tree has grown.
         * @return true if the parent tree should be reSkew.BALANCED too
         */
        private boolean rebalanceRightGrown() {
            switch (skew) {
            case LEFT_HIGH:
                skew = Skew.BALANCED;
                return false;
            case RIGHT_HIGH:
                if (right.skew == Skew.RIGHT_HIGH) {
                    rotateCCW();
                    skew      = Skew.BALANCED;
                    left.skew = Skew.BALANCED;
                } else {
                    final Skew s = right.left.skew;
                    right.rotateCW();
                    rotateCCW();
                    switch (s) {
                    case LEFT_HIGH:
                        left.skew  = Skew.BALANCED;
                        right.skew = Skew.RIGHT_HIGH;
                        break;
                    case RIGHT_HIGH:
                        left.skew  = Skew.LEFT_HIGH;
                        right.skew = Skew.BALANCED;
                        break;
                    default:
                        left.skew  = Skew.BALANCED;
                        right.skew = Skew.BALANCED;
                    }
                    skew = Skew.BALANCED;
                }
                return false;
            default:
                skew = Skew.RIGHT_HIGH;
                return true;
            }
        }

        /** Re-balance the instance as left sub-tree has shrunk.
         * @return true if the parent tree should be reSkew.BALANCED too
         */
        private boolean rebalanceLeftShrunk() {
            switch (skew) {
            case LEFT_HIGH:
                skew = Skew.BALANCED;
                return true;
            case RIGHT_HIGH:
                if (right.skew == Skew.RIGHT_HIGH) {
                    rotateCCW();
                    skew      = Skew.BALANCED;
                    left.skew = Skew.BALANCED;
                    return true;
                } else if (right.skew == Skew.BALANCED) {
                    rotateCCW();
                    skew      = Skew.LEFT_HIGH;
                    left.skew = Skew.RIGHT_HIGH;
                    return false;
                } else {
                    final Skew s = right.left.skew;
                    right.rotateCW();
                    rotateCCW();
                    switch (s) {
                    case LEFT_HIGH:
                        left.skew  = Skew.BALANCED;
                        right.skew = Skew.RIGHT_HIGH;
                        break;
                    case RIGHT_HIGH:
                        left.skew  = Skew.LEFT_HIGH;
                        right.skew = Skew.BALANCED;
                        break;
                    default:
                        left.skew  = Skew.BALANCED;
                        right.skew = Skew.BALANCED;
                    }
                    skew = Skew.BALANCED;
                    return true;
                }
            default:
                skew = Skew.RIGHT_HIGH;
                return false;
            }
        }

        /** Re-balance the instance as right sub-tree has shrunk.
         * @return true if the parent tree should be reSkew.BALANCED too
         */
        private boolean rebalanceRightShrunk() {
            switch (skew) {
            case RIGHT_HIGH:
                skew = Skew.BALANCED;
                return true;
            case LEFT_HIGH:
                if (left.skew == Skew.LEFT_HIGH) {
                    rotateCW();
                    skew       = Skew.BALANCED;
                    right.skew = Skew.BALANCED;
                    return true;
                } else if (left.skew == Skew.BALANCED) {
                    rotateCW();
                    skew       = Skew.RIGHT_HIGH;
                    right.skew = Skew.LEFT_HIGH;
                    return false;
                } else {
                    final Skew s = left.right.skew;
                    left.rotateCCW();
                    rotateCW();
                    switch (s) {
                    case LEFT_HIGH:
                        left.skew  = Skew.BALANCED;
                        right.skew = Skew.RIGHT_HIGH;
                        break;
                    case RIGHT_HIGH:
                        left.skew  = Skew.LEFT_HIGH;
                        right.skew = Skew.BALANCED;
                        break;
                    default:
                        left.skew  = Skew.BALANCED;
                        right.skew = Skew.BALANCED;
                    }
                    skew = Skew.BALANCED;
                    return true;
                }
            default:
                skew = Skew.LEFT_HIGH;
                return false;
            }
        }

        /** Perform a clockwise rotation rooted at the instance.
         * <p>The skew factor are not updated by this method, they
         * <em>must</em> be updated by the caller</p>
         */
        private void rotateCW() {

            final T tmpElt       = element;
            element              = left.element;
            left.element         = tmpElt;

            final Node tmpNode   = left;
            left                 = tmpNode.left;
            tmpNode.left         = tmpNode.right;
            tmpNode.right        = right;
            right                = tmpNode;

            if (left != null) {
                left.parent = this;
            }
            if (right.right != null) {
                right.right.parent = right;
            }

        }

        /** Perform a counter-clockwise rotation rooted at the instance.
         * <p>The skew factor are not updated by this method, they
         * <em>must</em> be updated by the caller</p>
         */
        private void rotateCCW() {

            final T tmpElt        = element;
            element               = right.element;
            right.element         = tmpElt;

            final Node tmpNode    = right;
            right                 = tmpNode.right;
            tmpNode.right         = tmpNode.left;
            tmpNode.left          = left;
            left                  = tmpNode;

            if (right != null) {
                right.parent = this;
            }
            if (left.left != null) {
                left.left.parent = left;
            }

        }

    }

}