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    }