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