    001    /*
    002     * Licensed to the Apache Software Foundation (ASF) under one or more
    003     * contributor license agreements.  See the NOTICE file distributed with
    004     * this work for additional information regarding copyright ownership.
    005     * The ASF licenses this file to You under the Apache License, Version 2.0
    006     * (the "License"); you may not use this file except in compliance with
    007     * the License.  You may obtain a copy of the License at
    008     *
    009     *      http://www.apache.org/licenses/LICENSE-2.0
    010     *
    011     * Unless required by applicable law or agreed to in writing, software
    012     * distributed under the License is distributed on an "AS IS" BASIS,
    013     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    014     * See the License for the specific language governing permissions and
    015     * limitations under the License.
    016     */
    017    package org.apache.commons.math3.geometry.partitioning.utilities;
    018
    019    /** This class implements AVL trees.
    020     *
    021     * <p>The purpose of this class is to sort elements while allowing
    022     * duplicate elements (i.e. such that {@code a.equals(b)} is
    023     * true). The {@code SortedSet} interface does not allow this, so
    024     * a specific class is needed. Null elements are not allowed.</p>
    025     *
    026     * <p>Since the {@code equals} method is not sufficient to
    027     * differentiate elements, the {@link #delete delete} method is
    028     * implemented using the equality operator.</p>
    029     *
    030     * <p>In order to clearly mark the methods provided here do not have
    031     * the same semantics as the ones specified in the
    032     * {@code SortedSet} interface, different names are used
    033     * ({@code add} has been replaced by {@link #insert insert} and
    034     * {@code remove} has been replaced by {@link #delete
    035     * delete}).</p>
    036     *
    037     * <p>This class is based on the C implementation Georg Kraml has put
    038     * in the public domain. Unfortunately, his <a
    039     * href="www.purists.org/georg/avltree/index.html">page</a> seems not
    040     * to exist any more.</p>
    041     *
    042     * @param <T> the type of the elements
    043     *
    044     * @version $Id: AVLTree.java 1416643 2012-12-03 19:37:14Z tn $
    045     * @since 3.0
    046     */
    047    public class AVLTree<T extends Comparable<T>> {
    048
    049        /** Top level node. */
    050        private Node top;
    051
    052        /** Build an empty tree.
    053         */
    054        public AVLTree() {
    055            top = null;
    056        }
    057
    058        /** Insert an element in the tree.
    059         * @param element element to insert (silently ignored if null)
    060         */
    061        public void insert(final T element) {
    062            if (element != null) {
    063                if (top == null) {
    064                    top = new Node(element, null);
    065                } else {
    066                    top.insert(element);
    067                }
    068            }
    069        }
    070
    071        /** Delete an element from the tree.
    072         * <p>The element is deleted only if there is a node {@code n}
    073         * containing exactly the element instance specified, i.e. for which
    074         * {@code n.getElement() == element}. This is purposely
    075         * <em>different</em> from the specification of the
    076         * {@code java.util.Set} {@code remove} method (in fact,
    077         * this is the reason why a specific class has been developed).</p>
    078         * @param element element to delete (silently ignored if null)
    079         * @return true if the element was deleted from the tree
    080         */
    081        public boolean delete(final T element) {
    082            if (element != null) {
    083                for (Node node = getNotSmaller(element); node != null; node = node.getNext()) {
    084                    // loop over all elements neither smaller nor larger
    085                    // than the specified one
    086                    if (node.element == element) {
    087                        node.delete();
    088                        return true;
    089                    } else if (node.element.compareTo(element) > 0) {
    090                        // all the remaining elements are known to be larger,
    091                        // the element is not in the tree
    092                        return false;
    093                    }
    094                }
    095            }
    096            return false;
    097        }
    098
    099        /** Check if the tree is empty.
    100         * @return true if the tree is empty
    101         */
    102        public boolean isEmpty() {
    103            return top == null;
    104        }
    105
    106
    107        /** Get the number of elements of the tree.
    108         * @return number of elements contained in the tree
    109         */
    110        public int size() {
    111            return (top == null) ? 0 : top.size();
    112        }
    113
    114        /** Get the node whose element is the smallest one in the tree.
    115         * @return the tree node containing the smallest element in the tree
    116         * or null if the tree is empty
    117         * @see #getLargest
    118         * @see #getNotSmaller
    119         * @see #getNotLarger
    120         * @see Node#getPrevious
    121         * @see Node#getNext
    122         */
    123        public Node getSmallest() {
    124            return (top == null) ? null : top.getSmallest();
    125        }
    126
    127        /** Get the node whose element is the largest one in the tree.
    128         * @return the tree node containing the largest element in the tree
    129         * or null if the tree is empty
    130         * @see #getSmallest
    131         * @see #getNotSmaller
    132         * @see #getNotLarger
    133         * @see Node#getPrevious
    134         * @see Node#getNext
    135         */
    136        public Node getLargest() {
    137            return (top == null) ? null : top.getLargest();
    138        }
    139
    140        /** Get the node whose element is not smaller than the reference object.
    141         * @param reference reference object (may not be in the tree)
    142         * @return the tree node containing the smallest element not smaller
    143         * than the reference object or null if either the tree is empty or
    144         * all its elements are smaller than the reference object
    145         * @see #getSmallest
    146         * @see #getLargest
    147         * @see #getNotLarger
    148         * @see Node#getPrevious
    149         * @see Node#getNext
    150         */
    151        public Node getNotSmaller(final T reference) {
    152            Node candidate = null;
    153            for (Node node = top; node != null;) {
    154                if (node.element.compareTo(reference) < 0) {
    155                    if (node.right == null) {
    156                        return candidate;
    157                    }
    158                    node = node.right;
    159                } else {
    160                    candidate = node;
    161                    if (node.left == null) {
    162                        return candidate;
    163                    }
    164                    node = node.left;
    165                }
    166            }
    167            return null;
    168        }
    169
    170        /** Get the node whose element is not larger than the reference object.
    171         * @param reference reference object (may not be in the tree)
    172         * @return the tree node containing the largest element not larger
    173         * than the reference object (in which case the node is guaranteed
    174         * not to be empty) or null if either the tree is empty or all its
    175         * elements are larger than the reference object
    176         * @see #getSmallest
    177         * @see #getLargest
    178         * @see #getNotSmaller
    179         * @see Node#getPrevious
    180         * @see Node#getNext
    181         */
    182        public Node getNotLarger(final T reference) {
    183            Node candidate = null;
    184            for (Node node = top; node != null;) {
    185                if (node.element.compareTo(reference) > 0) {
    186                    if (node.left == null) {
    187                        return candidate;
    188                    }
    189                    node = node.left;
    190                } else {
    191                    candidate = node;
    192                    if (node.right == null) {
    193                        return candidate;
    194                    }
    195                    node = node.right;
    196                }
    197            }
    198            return null;
    199        }
    200
    201        /** Enum for tree skew factor. */
    202        private static enum Skew {
    203            /** Code for left high trees. */
    204            LEFT_HIGH,
    205
    206            /** Code for right high trees. */
    207            RIGHT_HIGH,
    208
    209            /** Code for Skew.BALANCED trees. */
    210            BALANCED;
    211        }
    212
    213        /** This class implements AVL trees nodes.
    214         * <p>AVL tree nodes implement all the logical structure of the
    215         * tree. Nodes are created by the {@link AVLTree AVLTree} class.</p>
    216         * <p>The nodes are not independant from each other but must obey
    217         * specific balancing constraints and the tree structure is
    218         * rearranged as elements are inserted or deleted from the tree. The
    219         * creation, modification and tree-related navigation methods have
    220         * therefore restricted access. Only the order-related navigation,
    221         * reading and delete methods are public.</p>
    222         * @see AVLTree
    223         */
    224        public class Node {
    225
    226            /** Element contained in the current node. */
    227            private T element;
    228
    229            /** Left sub-tree. */
    230            private Node left;
    231
    232            /** Right sub-tree. */
    233            private Node right;
    234
    235            /** Parent tree. */
    236            private Node parent;
    237
    238            /** Skew factor. */
    239            private Skew skew;
    240
    241            /** Build a node for a specified element.
    242             * @param element element
    243             * @param parent parent node
    244             */
    245            Node(final T element, final Node parent) {
    246                this.element = element;
    247                left         = null;
    248                right        = null;
    249                this.parent  = parent;
    250                skew         = Skew.BALANCED;
    251            }
    252
    253            /** Get the contained element.
    254             * @return element contained in the node
    255             */
    256            public T getElement() {
    257                return element;
    258            }
    259
    260            /** Get the number of elements of the tree rooted at this node.
    261             * @return number of elements contained in the tree rooted at this node
    262             */
    263            int size() {
    264                return 1 + ((left  == null) ? 0 : left.size()) + ((right == null) ? 0 : right.size());
    265            }
    266
    267            /** Get the node whose element is the smallest one in the tree
    268             * rooted at this node.
    269             * @return the tree node containing the smallest element in the
    270             * tree rooted at this node or null if the tree is empty
    271             * @see #getLargest
    272             */
    273            Node getSmallest() {
    274                Node node = this;
    275                while (node.left != null) {
    276                    node = node.left;
    277                }
    278                return node;
    279            }
    280
    281            /** Get the node whose element is the largest one in the tree
    282             * rooted at this node.
    283             * @return the tree node containing the largest element in the
    284             * tree rooted at this node or null if the tree is empty
    285             * @see #getSmallest
    286             */
    287            Node getLargest() {
    288                Node node = this;
    289                while (node.right != null) {
    290                    node = node.right;
    291                }
    292                return node;
    293            }
    294
    295            /** Get the node containing the next smaller or equal element.
    296             * @return node containing the next smaller or equal element or
    297             * null if there is no smaller or equal element in the tree
    298             * @see #getNext
    299             */
    300            public Node getPrevious() {
    301
    302                if (left != null) {
    303                    final Node node = left.getLargest();
    304                    if (node != null) {
    305                        return node;
    306                    }
    307                }
    308
    309                for (Node node = this; node.parent != null; node = node.parent) {
    310                    if (node != node.parent.left) {
    311                        return node.parent;
    312                    }
    313                }
    314
    315                return null;
    316
    317            }
    318
    319            /** Get the node containing the next larger or equal element.
    320             * @return node containing the next larger or equal element (in
    321             * which case the node is guaranteed not to be empty) or null if
    322             * there is no larger or equal element in the tree
    323             * @see #getPrevious
    324             */
    325            public Node getNext() {
    326
    327                if (right != null) {
    328                    final Node node = right.getSmallest();
    329                    if (node != null) {
    330                        return node;
    331                    }
    332                }
    333
    334                for (Node node = this; node.parent != null; node = node.parent) {
    335                    if (node != node.parent.right) {
    336                        return node.parent;
    337                    }
    338                }
    339
    340                return null;
    341
    342            }
    343
    344            /** Insert an element in a sub-tree.
    345             * @param newElement element to insert
    346             * @return true if the parent tree should be re-Skew.BALANCED
    347             */
    348            boolean insert(final T newElement) {
    349                if (newElement.compareTo(this.element) < 0) {
    350                    // the inserted element is smaller than the node
    351                    if (left == null) {
    352                        left = new Node(newElement, this);
    353                        return rebalanceLeftGrown();
    354                    }
    355                    return left.insert(newElement) ? rebalanceLeftGrown() : false;
    356                }
    357
    358                // the inserted element is equal to or greater than the node
    359                if (right == null) {
    360                    right = new Node(newElement, this);
    361                    return rebalanceRightGrown();
    362                }
    363                return right.insert(newElement) ? rebalanceRightGrown() : false;
    364
    365            }
    366
    367            /** Delete the node from the tree.
    368             */
    369            public void delete() {
    370                if ((parent == null) && (left == null) && (right == null)) {
    371                    // this was the last node, the tree is now empty
    372                    element = null;
    373                    top     = null;
    374                } else {
    375
    376                    Node node;
    377                    Node child;
    378                    boolean leftShrunk;
    379                    if ((left == null) && (right == null)) {
    380                        node       = this;
    381                        element    = null;
    382                        leftShrunk = node == node.parent.left;
    383                        child      = null;
    384                    } else {
    385                        node       = (left != null) ? left.getLargest() : right.getSmallest();
    386                        element    = node.element;
    387                        leftShrunk = node == node.parent.left;
    388                        child      = (node.left != null) ? node.left : node.right;
    389                    }
    390
    391                    node = node.parent;
    392                    if (leftShrunk) {
    393                        node.left = child;
    394                    } else {
    395                        node.right = child;
    396                    }
    397                    if (child != null) {
    398                        child.parent = node;
    399                    }
    400
    401                    while (leftShrunk ? node.rebalanceLeftShrunk() : node.rebalanceRightShrunk()) {
    402                        if (node.parent == null) {
    403                            return;
    404                        }
    405                        leftShrunk = node == node.parent.left;
    406                        node = node.parent;
    407                    }
    408
    409                }
    410            }
    411
    412            /** Re-balance the instance as left sub-tree has grown.
    413             * @return true if the parent tree should be reSkew.BALANCED too
    414             */
    415            private boolean rebalanceLeftGrown() {
    416                switch (skew) {
    417                case LEFT_HIGH:
    418                    if (left.skew == Skew.LEFT_HIGH) {
    419                        rotateCW();
    420                        skew       = Skew.BALANCED;
    421                        right.skew = Skew.BALANCED;
    422                    } else {
    423                        final Skew s = left.right.skew;
    424                        left.rotateCCW();
    425                        rotateCW();
    426                        switch(s) {
    427                        case LEFT_HIGH:
    428                            left.skew  = Skew.BALANCED;
    429                            right.skew = Skew.RIGHT_HIGH;
    430                            break;
    431                        case RIGHT_HIGH:
    432                            left.skew  = Skew.LEFT_HIGH;
    433                            right.skew = Skew.BALANCED;
    434                            break;
    435                        default:
    436                            left.skew  = Skew.BALANCED;
    437                            right.skew = Skew.BALANCED;
    438                        }
    439                        skew = Skew.BALANCED;
    440                    }
    441                    return false;
    442                case RIGHT_HIGH:
    443                    skew = Skew.BALANCED;
    444                    return false;
    445                default:
    446                    skew = Skew.LEFT_HIGH;
    447                    return true;
    448                }
    449            }
    450
    451            /** Re-balance the instance as right sub-tree has grown.
    452             * @return true if the parent tree should be reSkew.BALANCED too
    453             */
    454            private boolean rebalanceRightGrown() {
    455                switch (skew) {
    456                case LEFT_HIGH:
    457                    skew = Skew.BALANCED;
    458                    return false;
    459                case RIGHT_HIGH:
    460                    if (right.skew == Skew.RIGHT_HIGH) {
    461                        rotateCCW();
    462                        skew      = Skew.BALANCED;
    463                        left.skew = Skew.BALANCED;
    464                    } else {
    465                        final Skew s = right.left.skew;
    466                        right.rotateCW();
    467                        rotateCCW();
    468                        switch (s) {
    469                        case LEFT_HIGH:
    470                            left.skew  = Skew.BALANCED;
    471                            right.skew = Skew.RIGHT_HIGH;
    472                            break;
    473                        case RIGHT_HIGH:
    474                            left.skew  = Skew.LEFT_HIGH;
    475                            right.skew = Skew.BALANCED;
    476                            break;
    477                        default:
    478                            left.skew  = Skew.BALANCED;
    479                            right.skew = Skew.BALANCED;
    480                        }
    481                        skew = Skew.BALANCED;
    482                    }
    483                    return false;
    484                default:
    485                    skew = Skew.RIGHT_HIGH;
    486                    return true;
    487                }
    488            }
    489
    490            /** Re-balance the instance as left sub-tree has shrunk.
    491             * @return true if the parent tree should be reSkew.BALANCED too
    492             */
    493            private boolean rebalanceLeftShrunk() {
    494                switch (skew) {
    495                case LEFT_HIGH:
    496                    skew = Skew.BALANCED;
    497                    return true;
    498                case RIGHT_HIGH:
    499                    if (right.skew == Skew.RIGHT_HIGH) {
    500                        rotateCCW();
    501                        skew      = Skew.BALANCED;
    502                        left.skew = Skew.BALANCED;
    503                        return true;
    504                    } else if (right.skew == Skew.BALANCED) {
    505                        rotateCCW();
    506                        skew      = Skew.LEFT_HIGH;
    507                        left.skew = Skew.RIGHT_HIGH;
    508                        return false;
    509                    } else {
    510                        final Skew s = right.left.skew;
    511                        right.rotateCW();
    512                        rotateCCW();
    513                        switch (s) {
    514                        case LEFT_HIGH:
    515                            left.skew  = Skew.BALANCED;
    516                            right.skew = Skew.RIGHT_HIGH;
    517                            break;
    518                        case RIGHT_HIGH:
    519                            left.skew  = Skew.LEFT_HIGH;
    520                            right.skew = Skew.BALANCED;
    521                            break;
    522                        default:
    523                            left.skew  = Skew.BALANCED;
    524                            right.skew = Skew.BALANCED;
    525                        }
    526                        skew = Skew.BALANCED;
    527                        return true;
    528                    }
    529                default:
    530                    skew = Skew.RIGHT_HIGH;
    531                    return false;
    532                }
    533            }
    534
    535            /** Re-balance the instance as right sub-tree has shrunk.
    536             * @return true if the parent tree should be reSkew.BALANCED too
    537             */
    538            private boolean rebalanceRightShrunk() {
    539                switch (skew) {
    540                case RIGHT_HIGH:
    541                    skew = Skew.BALANCED;
    542                    return true;
    543                case LEFT_HIGH:
    544                    if (left.skew == Skew.LEFT_HIGH) {
    545                        rotateCW();
    546                        skew       = Skew.BALANCED;
    547                        right.skew = Skew.BALANCED;
    548                        return true;
    549                    } else if (left.skew == Skew.BALANCED) {
    550                        rotateCW();
    551                        skew       = Skew.RIGHT_HIGH;
    552                        right.skew = Skew.LEFT_HIGH;
    553                        return false;
    554                    } else {
    555                        final Skew s = left.right.skew;
    556                        left.rotateCCW();
    557                        rotateCW();
    558                        switch (s) {
    559                        case LEFT_HIGH:
    560                            left.skew  = Skew.BALANCED;
    561                            right.skew = Skew.RIGHT_HIGH;
    562                            break;
    563                        case RIGHT_HIGH:
    564                            left.skew  = Skew.LEFT_HIGH;
    565                            right.skew = Skew.BALANCED;
    566                            break;
    567                        default:
    568                            left.skew  = Skew.BALANCED;
    569                            right.skew = Skew.BALANCED;
    570                        }
    571                        skew = Skew.BALANCED;
    572                        return true;
    573                    }
    574                default:
    575                    skew = Skew.LEFT_HIGH;
    576                    return false;
    577                }
    578            }
    579
    580            /** Perform a clockwise rotation rooted at the instance.
    581             * <p>The skew factor are not updated by this method, they
    582             * <em>must</em> be updated by the caller</p>
    583             */
    584            private void rotateCW() {
    585
    586                final T tmpElt       = element;
    587                element              = left.element;
    588                left.element         = tmpElt;
    589
    590                final Node tmpNode   = left;
    591                left                 = tmpNode.left;
    592                tmpNode.left         = tmpNode.right;
    593                tmpNode.right        = right;
    594                right                = tmpNode;
    595
    596                if (left != null) {
    597                    left.parent = this;
    598                }
    599                if (right.right != null) {
    600                    right.right.parent = right;
    601                }
    602
    603            }
    604
    605            /** Perform a counter-clockwise rotation rooted at the instance.
    606             * <p>The skew factor are not updated by this method, they
    607             * <em>must</em> be updated by the caller</p>
    608             */
    609            private void rotateCCW() {
    610
    611                final T tmpElt        = element;
    612                element               = right.element;
    613                right.element         = tmpElt;
    614
    615                final Node tmpNode    = right;
    616                right                 = tmpNode.right;
    617                tmpNode.right         = tmpNode.left;
    618                tmpNode.left          = left;
    619                left                  = tmpNode;
    620
    621                if (right != null) {
    622                    right.parent = this;
    623                }
    624                if (left.left != null) {
    625                    left.left.parent = left;
    626                }
    627
    628            }
    629
    630        }
    631
    632    }