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}