AVLTree.java

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

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

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

  54.     /** Build an empty tree.
  55.      */
  56.     public AVLTree() {
  57.         top = null;
  58.     }

  60.     /** Insert an element in the tree.
  61.      * @param element element to insert (silently ignored if null)
  62.      */
  63.     public void insert(final T element) {
  64.         if (element != null) {
  65.             if (top == null) {
  66.                 top = new Node(element, null);
  67.             } else {
  68.                 top.insert(element);
  69.             }
  70.         }
  71.     }

  73.     /** Delete an element from the tree.
  74.      * <p>The element is deleted only if there is a node {@code n}
  75.      * containing exactly the element instance specified, i.e. for which
  76.      * {@code n.getElement() == element}. This is purposely
  77.      * <em>different</em> from the specification of the
  78.      * {@code java.util.Set} {@code remove} method (in fact,
  79.      * this is the reason why a specific class has been developed).</p>
  80.      * @param element element to delete (silently ignored if null)
  81.      * @return true if the element was deleted from the tree
  82.      */
  83.     public boolean delete(final T element) {
  84.         if (element != null) {
  85.             for (Node node = getNotSmaller(element); node != null; node = node.getNext()) {
  86.                 // loop over all elements neither smaller nor larger
  87.                 // than the specified one
  88.                 if (node.element == element) {
  89.                     node.delete();
  90.                     return true;
  91.                 } else if (node.element.compareTo(element) > 0) {
  92.                     // all the remaining elements are known to be larger,
  93.                     // the element is not in the tree
  94.                     return false;
  95.                 }
  96.             }
  97.         }
  98.         return false;
  99.     }

  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.     }


  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.     }

  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.     }

  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.     }

  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.     }

  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.     }

  203.     /** Enum for tree skew factor. */
  204.     private static enum Skew {
  205.         /** Code for left high trees. */
  206.         LEFT_HIGH,

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

  211.         /** Code for Skew.BALANCED trees. */
  212.         BALANCED;
  213.     }

  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 {

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

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

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

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

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

  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.         }

  255.         /** Get the contained element.
  256.          * @return element contained in the node
  257.          */
  258.         public T getElement() {
  259.             return element;
  260.         }

  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.         }

  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.         }

  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.         }

  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() {

  304.             if (left != null) {
  305.                 final Node node = left.getLargest();
  306.                 if (node != null) {
  307.                     return node;
  308.                 }
  309.             }

  311.             for (Node node = this; node.parent != null; node = node.parent) {
  312.                 if (node != node.parent.left) {
  313.                     return node.parent;
  314.                 }
  315.             }

  317.             return null;

  319.         }

  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() {

  329.             if (right != null) {
  330.                 final Node node = right.getSmallest();
  331.                 if (node != null) {
  332.                     return node;
  333.                 }
  334.             }

  336.             for (Node node = this; node.parent != null; node = node.parent) {
  337.                 if (node != node.parent.right) {
  338.                     return node.parent;
  339.                 }
  340.             }

  342.             return null;

  344.         }

  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.             }

  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;

  367.         }

  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 {

  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.                 }

  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.                 }

  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.                 }

  411.             }
  412.         }

  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.         }

  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.         }

  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.         }

  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.         }

  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() {

  588.             final T tmpElt       = element;
  589.             element              = left.element;
  590.             left.element         = tmpElt;

  592.             final Node tmpNode   = left;
  593.             left                 = tmpNode.left;
  594.             tmpNode.left         = tmpNode.right;
  595.             tmpNode.right        = right;
  596.             right                = tmpNode;

  598.             if (left != null) {
  599.                 left.parent = this;
  600.             }
  601.             if (right.right != null) {
  602.                 right.right.parent = right;
  603.             }

  605.         }

  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() {

  613.             final T tmpElt        = element;
  614.             element               = right.element;
  615.             right.element         = tmpElt;

  617.             final Node tmpNode    = right;
  618.             right                 = tmpNode.right;
  619.             tmpNode.right         = tmpNode.left;
  620.             tmpNode.left          = left;
  621.             left                  = tmpNode;

  623.             if (right != null) {
  624.                 right.parent = this;
  625.             }
  626.             if (left.left != null) {
  627.                 left.left.parent = left;
  628.             }

  630.         }

  632.     }

  634. }
Created with JaCoCo 0.7.2.201409121644