001 /* 002 * Licensed to the Apache Software Foundation (ASF) under one 003 * or more contributor license agreements. See the NOTICE file 004 * distributed with this work for additional information 005 * regarding copyright ownership. The ASF licenses this file 006 * to you under the Apache License, Version 2.0 (the 007 * "License"); you may not use this file except in compliance 008 * with the License. You may obtain a copy of the License at 009 * 010 * http://www.apache.org/licenses/LICENSE-2.0 011 * 012 * Unless required by applicable law or agreed to in writing, 013 * software distributed under the License is distributed on an 014 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 015 * KIND, either express or implied. See the License for the 016 * specific language governing permissions and limitations 017 * under the License. 018 * 019 */ 020 package org.apache.directory.server.core.avltree; 021 022 023 import java.util.ArrayList; 024 import java.util.Comparator; 025 import java.util.List; 026 027 028 /** 029 * An AvlTreeMap implementation with support to store both key and value. 030 * This implementation also supports duplicate keys. The values of a same key 031 * will be stored in a AvlTree. 032 * 033 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 034 * @version $Rev$, $Date$ 035 */ 036 public class AvlTreeMapImpl<K,V> implements AvlTreeMap<K, V> 037 { 038 /** the root of the tree */ 039 private LinkedAvlMapNode<K,V> root; 040 041 /** The Comparator used for comparing the keys */ 042 private Comparator<K> keyComparator; 043 044 /** The Comparator used for comparing the values */ 045 private Comparator<V> valueComparator; 046 047 /** node representing the start of the doubly linked list formed with the tree nodes */ 048 private LinkedAvlMapNode<K,V> first; 049 050 /** node representing the end of the doubly linked list formed with the tree nodes */ 051 private LinkedAvlMapNode<K,V> last; 052 053 /** flag to allow storing duplicate keys */ 054 private boolean allowDuplicates; 055 056 /** size of the map */ 057 private int size; 058 059 /** 060 * Creates a new instance of AVLTreeMap without support for duplicate keys. 061 * 062 * @param comparator1 the comparator to be used for comparing keys 063 */ 064 public AvlTreeMapImpl( Comparator<K> keyComparator, Comparator<V> valueComparator ) 065 { 066 this( keyComparator, valueComparator, false ); 067 } 068 069 070 public AvlTreeMapImpl( Comparator<K> keyComparator, Comparator<V> valueComparator, boolean allowDuplicates ) 071 { 072 this.keyComparator = keyComparator; 073 this.valueComparator = valueComparator; 074 this.allowDuplicates = allowDuplicates; 075 } 076 077 078 /** 079 * {@inheritDoc} 080 */ 081 public Comparator<K> getKeyComparator() 082 { 083 return keyComparator; 084 } 085 086 087 /** 088 * {@inheritDoc} 089 */ 090 public Comparator<V> getValueComparator() 091 { 092 return valueComparator; 093 } 094 095 096 /** 097 * {@inheritDoc} 098 */ 099 public V insert( K key, V value ) 100 { 101 LinkedAvlMapNode<K,V> node, temp; 102 LinkedAvlMapNode<K,V> parent = null; 103 int c; 104 105 if ( root == null ) 106 { 107 root = new LinkedAvlMapNode<K,V>( key, value ); 108 first = root; 109 last = root; 110 size++; 111 return null; 112 } 113 114 node = new LinkedAvlMapNode<K,V>( key, value ); 115 116 temp = root; 117 118 List<LinkedAvlMapNode<K,V>> treePath = new ArrayList<LinkedAvlMapNode<K,V>>(); 119 120 while( temp != null ) 121 { 122 treePath.add(0, temp ); // last node first, for the sake of balance factor computation 123 parent = temp; 124 125 c = keyComparator.compare( key, temp.getKey() ); 126 127 if( c == 0 ) 128 { 129 if( allowDuplicates ) 130 { 131 return insertDupKey( key, value, temp ); // key already exists add another value 132 } 133 else 134 { 135 // replace the existing value with the new value 136 return temp.value.setSingleton( value ); 137 } 138 } 139 140 if( c < 0 ) 141 { 142 temp.isLeft = true; 143 temp = temp.getLeft(); 144 } 145 else 146 { 147 temp.isLeft = false; 148 temp = temp.getRight(); 149 } 150 } 151 152 if( ( c = keyComparator.compare( key, parent.getKey() ) ) < 0 ) 153 { 154 parent.setLeft( node ); 155 } 156 else 157 { 158 parent.setRight( node ); 159 } 160 161 insertInList( node, parent, c ); 162 163 treePath.add( 0, node ); 164 balance(treePath); 165 166 size++; 167 return null; 168 } 169 170 171 private V insertDupKey( K key, V value, LinkedAvlMapNode<K,V> existingNode ) 172 { 173 AvlTree<V> dupsTree = null; 174 175 if( existingNode.value.isOrderedSet() ) 176 { 177 dupsTree = existingNode.value.getOrderedSet(); 178 } 179 else 180 { 181 // create avlTree, insert singleton into it, then switch modes 182 dupsTree = new AvlTreeImpl<V>( valueComparator ); 183 dupsTree.insert( existingNode.value.getSingleton() ); 184 existingNode.value.switchToOrderedSet( dupsTree ); 185 } 186 187 // check if value already exists 188 if( dupsTree.find( value ) != null ) 189 { 190 return value; 191 } 192 193 // insert value into duplicate key holder 194 dupsTree.insert( value ); 195 196 return null; 197 } 198 199 200 private void removeFromList(LinkedAvlMapNode<K,V> node) 201 { 202 if( node.next == null && node.previous == null ) // should happen in case of tree having single node 203 { 204 first = last = null; 205 } 206 else if( node.next == null ) // last node 207 { 208 node.previous.next = null; 209 last = node.previous; 210 } 211 else if( node.previous == null ) // first node 212 { 213 node.next.previous = null; 214 first = node.next; 215 } 216 else // somewhere in middle 217 { 218 node.previous.next = node.next; 219 node.next.previous = node.previous; 220 } 221 222 } 223 224 225 private void insertInList(LinkedAvlMapNode<K,V> node, LinkedAvlMapNode<K,V> parentNode, int pos) 226 { 227 228 if( pos < 0 ) 229 { 230 if( last == null ) 231 { 232 last = parentNode; 233 } 234 235 if( parentNode.previous == null ) 236 { 237 first = node; 238 } 239 else 240 { 241 parentNode.previous.next = node ; 242 node.previous = parentNode.previous; 243 } 244 245 node.next = parentNode; 246 parentNode.previous = node; 247 } 248 else if( pos > 0 ) 249 { 250 if( parentNode.next == null ) 251 { 252 last = node; 253 } 254 else 255 { 256 parentNode.next.previous = node; 257 node.next = parentNode.next; 258 } 259 node.previous = parentNode; 260 parentNode.next = node; 261 } 262 263 } 264 265 266 /** 267 * {@inheritDoc} 268 */ 269 public SingletonOrOrderedSet<V> remove( K key ) 270 { 271 if( key == null ) 272 { 273 throw new IllegalArgumentException( "key cannot be null" ); 274 } 275 276 LinkedAvlMapNode<K,V> temp = null; 277 278 List<LinkedAvlMapNode<K,V>> treePath = new ArrayList<LinkedAvlMapNode<K,V>>(); 279 280 treePath = find( key, root, treePath); 281 282 if( treePath == null ) 283 { 284 return null; 285 } 286 287 temp = treePath.remove( 0 ); 288 289 if( temp.isLeaf() && ( temp == root ) ) 290 { 291 root = null; 292 } 293 else 294 { 295 balanceNodesAfterRemove( treePath, temp ); 296 } 297 298 size--; 299 return temp.value; 300 } 301 302 303 /** 304 * {@inheritDoc} 305 */ 306 public V remove( K key, V value ) 307 { 308 if( key == null || value == null ) 309 { 310 throw new IllegalArgumentException( "key or value cannot be null" ); 311 } 312 313 LinkedAvlMapNode<K,V> temp = null; 314 315 List<LinkedAvlMapNode<K,V>> treePath = new ArrayList<LinkedAvlMapNode<K,V>>(); 316 317 treePath = find( key, root, treePath); 318 319 if( treePath == null ) 320 { 321 return null; 322 } 323 324 temp = treePath.remove( 0 ); 325 326 // check if the value matches 327 if( allowDuplicates ) 328 { 329 if( temp.value.isOrderedSet() ) 330 { 331 AvlTree<V> dupsTree = temp.value.getOrderedSet(); 332 V removedVal = dupsTree.remove( value ); 333 334 // if the removal is successful and the tree is not empty 335 // we don't need to balance the tree, cause just one value 336 // of the same key was removed 337 // if the tree is empty because of the removal, the entire 338 // node will be removed which might require balancing, so we continue 339 // further down in this function 340 if( ( removedVal != null ) && ! dupsTree.isEmpty() ) 341 { 342 return removedVal;//no need to balance 343 } 344 /* 345 * if the value is not found then we should return 346 */ 347 else if ( removedVal == null ) 348 { 349 return removedVal;//no need to balance 350 } 351 } 352 else 353 { 354 if( valueComparator.compare( temp.value.getSingleton(), value ) != 0 ) 355 { 356 return null;// no need to balance 357 } 358 } 359 } 360 361 if( temp.isLeaf() && ( temp == root ) ) 362 { 363 if( allowDuplicates ) 364 { 365 if( temp.value.isSingleton() || temp.value.getOrderedSet().isEmpty() ) 366 { 367 root = null; 368 } 369 } 370 else // if dups are not allowed set root to null 371 { 372 root = null; 373 } 374 375 size--; 376 return value; 377 } 378 379 balanceNodesAfterRemove( treePath, temp ); 380 381 size--; 382 return value; 383 } 384 385 386 /** 387 * changes the order of nodes after a delete operation and then 388 * balances the tree 389 * 390 * @param treePath the path traversed to find the node temp 391 * @param delNode the node to be deleted 392 */ 393 private void balanceNodesAfterRemove( List<LinkedAvlMapNode<K,V>> treePath, LinkedAvlMapNode<K,V> delNode ) 394 { 395 LinkedAvlMapNode<K,V> y = null; 396 397 // remove from the doubly linked 398 removeFromList( delNode ); 399 400 if( delNode.isLeaf() ) 401 { 402 if( !treePath.isEmpty() ) 403 { 404 detachNodes( delNode, treePath.get( 0 ) ); 405 } 406 } 407 else 408 { 409 if( delNode.left != null ) 410 { 411 List<LinkedAvlMapNode<K,V>> leftTreePath = findMax( delNode.left ); 412 y = leftTreePath.remove( 0 ); 413 414 if( leftTreePath.isEmpty() ) // y is the left child of root and y is a leaf 415 { 416 detachNodes( y, delNode ); 417 } 418 else 419 { 420 detachNodes( y, leftTreePath.remove( 0 ) ); 421 } 422 423 leftTreePath.addAll( treePath ); 424 treePath = leftTreePath; 425 426 y.right = delNode.right; // assign the right here left will be assigned in replaceNode() 427 428 if( delNode == root ) 429 { 430 y.left = delNode.left; 431 root = y; 432 } 433 else 434 { 435 replaceNode( delNode, y, treePath.get( 0 ) ); 436 } 437 } 438 else if( delNode.right != null ) 439 { 440 List<LinkedAvlMapNode<K,V>> rightTreePath = findMin( delNode.right ); 441 y = rightTreePath.remove( 0 ); 442 443 if( rightTreePath.isEmpty() ) 444 { 445 detachNodes( y, delNode ); // y is the right child of root and y is a leaf 446 } 447 else 448 { 449 detachNodes( y, rightTreePath.remove( 0 ) ); 450 } 451 452 rightTreePath.addAll( treePath ); 453 treePath = rightTreePath; 454 455 y.right = delNode.right; // assign the right here left will be assigned in replaceNode() 456 457 if( delNode == root ) 458 { 459 y.right = delNode.right; 460 root = y; 461 } 462 else 463 { 464 replaceNode( delNode, y, treePath.get( 0 ) ); 465 } 466 } 467 } 468 469 treePath.add( 0, y ); // y can be null but getBalance returns 0 so np 470 balance( treePath ); 471 } 472 473 474 /** 475 * Balances the tree by visiting the nodes present in the List of nodes present in the 476 * treePath parameter.<br><br> 477 * 478 * This really does the balancing if the height of the tree is greater than 2 and the<br> 479 * balance factor is greater than +1 or less than -1.<br><br> 480 * For an excellent info please read the 481 * <a href="http://en.wikipedia.org/wiki/Avl_tree">Wikipedia article on AVL tree</a>. 482 * 483 * @param treePath the traversed list of LinkedAvlMapNodes after performing an insert/delete operation. 484 */ 485 private void balance( List<LinkedAvlMapNode<K,V>> treePath ) 486 { 487 LinkedAvlMapNode<K,V> parentNode = null; 488 489 int size = treePath.size(); 490 491 for( LinkedAvlMapNode<K,V> node: treePath ) 492 { 493 int balFactor = getBalance( node ); 494 495 if( node != root ) 496 { 497 if( treePath.indexOf( node ) < ( size - 1 ) ) 498 { 499 parentNode = treePath.get( treePath.indexOf( node ) + 1 ); 500 } 501 } 502 503 if( balFactor > 1 ) 504 { 505 if( getBalance( node.right ) <= -1) 506 { 507 //------rotate double-left-------- 508 rotateSingleRight( node.right, node ); 509 rotateSingleLeft( node, parentNode ); 510 } 511 else // rotate single-left 512 { 513 rotateSingleLeft( node, parentNode ); 514 } 515 } 516 else if( balFactor < -1 ) 517 { 518 if( getBalance( node.left ) >= 1) 519 { 520 //------rotate double-right-------- 521 rotateSingleLeft( node.left, node ); 522 rotateSingleRight( node, parentNode ); 523 } 524 else 525 { 526 rotateSingleRight( node, parentNode ); 527 } 528 } 529 } 530 } 531 532 533 /** 534 * {@inheritDoc} 535 */ 536 public boolean isEmpty() 537 { 538 return root == null; 539 } 540 541 542 /** 543 * {@inheritDoc} 544 */ 545 //NOTE: This method is internally used by AVLTreeMarshaller 546 public int getSize() 547 { 548 return size; 549 } 550 551 552 /** 553 * Set the root of the tree. 554 * 555 * Note : this method is used by the deserialization method 556 * 557 * @param root the root of the tree 558 */ 559 /* no protection */ void setRoot( LinkedAvlMapNode<K,V> root ) 560 { 561 this.root = root; 562 } 563 564 565 /** 566 * Set the first element of the tree 567 * 568 * Note : this method is used by the deserialization method 569 * 570 * @param first the first element to be added 571 */ 572 /* no protection */ void setFirst( LinkedAvlMapNode<K,V> first ) 573 { 574 this.first = first; 575 } 576 577 578 /** 579 * Set the last element of the tree 580 * 581 * Note : this method is used by the deserialization method 582 * 583 * @param last the last element to be added 584 */ 585 /* no protection */ void setLast( LinkedAvlMapNode<K,V> last ) 586 { 587 this.last = last; 588 } 589 590 591 /** 592 * {@inheritDoc} 593 */ 594 public LinkedAvlMapNode<K,V> getRoot() 595 { 596 return root; 597 } 598 599 600 /** 601 * {@inheritDoc} 602 */ 603 public List<K> getKeys() 604 { 605 List<K> keys = new ArrayList<K>(); 606 LinkedAvlMapNode<K,V> node = first; 607 608 while( node != null ) 609 { 610 keys.add( node.key ); 611 node = node.next; 612 } 613 614 return keys; 615 } 616 617 /** 618 * {@inheritDoc} 619 */ 620 public void printTree() 621 { 622 if( isEmpty() ) 623 { 624 System.out.println( "Tree is empty" ); 625 return; 626 } 627 628 getRoot().setDepth( 0 ); 629 630 System.out.println( getRoot() ); 631 632 visit( getRoot().getRight(), getRoot() ); 633 634 visit( getRoot().getLeft(), getRoot() ); 635 } 636 637 638 /** 639 * {@inheritDoc} 640 */ 641 public LinkedAvlMapNode<K,V> getFirst() 642 { 643 return first; 644 } 645 646 647 /** 648 * {@inheritDoc} 649 */ 650 public LinkedAvlMapNode<K,V> getLast() 651 { 652 return last; 653 } 654 655 656 /** 657 * Rotate the node left side once. 658 * 659 * @param node the LinkedAvlMapNode to be rotated 660 * @param parentNode parent LinkedAvlMapNode of node 661 */ 662 private void rotateSingleLeft(LinkedAvlMapNode<K,V> node, LinkedAvlMapNode<K,V> parentNode) 663 { 664 LinkedAvlMapNode<K,V> temp; 665 //------rotate single-left-------- 666 667 temp = node.right; 668 node.right = temp.left; 669 temp.left = node; 670 671 if( node == root ) 672 { 673 root = temp; 674 } 675 else if( parentNode != null ) 676 { 677 if( parentNode.left == node ) 678 { 679 parentNode.left = temp; 680 } 681 else if( parentNode.right == node ) 682 { 683 parentNode.right = temp; 684 } 685 } 686 } 687 688 689 /** 690 * Rotate the node right side once. 691 * 692 * @param node the LinkedAvlMapNode to be rotated 693 * @param parentNode parent LinkedAvlMapNode of node 694 */ 695 private void rotateSingleRight(LinkedAvlMapNode<K,V> node, LinkedAvlMapNode<K,V> parentNode) 696 { 697 LinkedAvlMapNode<K,V> temp; 698 //------rotate single-right-------- 699 700 temp = node.left; 701 node.left = temp.right; 702 temp.right = node; 703 704 if( node == root ) 705 { 706 root = temp; 707 } 708 else if( parentNode != null ) 709 { 710 if( parentNode.left == node ) 711 { 712 parentNode.left = temp; 713 } 714 else if( parentNode.right == node ) 715 { 716 parentNode.right = temp; 717 } 718 } 719 /* 720 when the 'parentNode' param is null then the node under rotation is a child of ROOT. 721 Most likely this condition executes when the root node is deleted and balancing is required. 722 */ 723 else if( root != null ) 724 { 725 if( root.left == node ) 726 { 727 root.left = temp; 728 } 729 // no need to check for right node 730 } 731 } 732 733 734 /** 735 * Detach a LinkedAvlMapNode from its parent 736 * 737 * @param node the LinkedAvlMapNode to be detached 738 * @param parentNode the parent LinkedAvlMapNode of the node 739 */ 740 private void detachNodes(LinkedAvlMapNode<K,V> node, LinkedAvlMapNode<K,V> parentNode) 741 { 742 if( parentNode != null ) 743 { 744 if( node == parentNode.left ) 745 { 746 parentNode.left = node.left; 747 } 748 else if( node == parentNode.right ) 749 { 750 parentNode.right = node.left; 751 } 752 } 753 } 754 755 756 /** 757 * 758 * Replace a LinkedAvlMapNode to be removed with a new existing LinkedAvlMapNode 759 * 760 * @param deleteNode the LinkedAvlMapNode to be deleted 761 * @param replaceNode the LinkedAvlMapNode to replace the deleteNode 762 * @param parentNode the parent LinkedAvlMapNode of deleteNode 763 */ 764 private void replaceNode(LinkedAvlMapNode<K,V> deleteNode, LinkedAvlMapNode<K,V> replaceNode, LinkedAvlMapNode<K,V> parentNode) 765 { 766 if( parentNode != null ) 767 { 768 replaceNode.left = deleteNode.left; 769 770 if( deleteNode == parentNode.left ) 771 { 772 parentNode.left = replaceNode; 773 } 774 else if( deleteNode == parentNode.right ) 775 { 776 parentNode.right = replaceNode; 777 } 778 } 779 } 780 781 782 /** 783 * 784 * Find a LinkedAvlMapNode with the given key value in the tree starting from the startNode. 785 * 786 * @param key the key to find 787 * @param startNode starting node of a subtree/tree 788 * @param path the list to be filled with traversed nodes 789 * @return the list of traversed LinkedAvlMapNodes. 790 */ 791 private List<LinkedAvlMapNode<K,V>> find( K key, LinkedAvlMapNode<K,V> startNode, List<LinkedAvlMapNode<K,V>> path ) 792 { 793 int c; 794 795 if( startNode == null ) 796 { 797 return null; 798 } 799 800 path.add( 0, startNode ); 801 c = keyComparator.compare( key, startNode.key ); 802 803 if( c == 0 ) 804 { 805 return path; 806 } 807 else if( c > 0 ) 808 { 809 return find( key, startNode.right, path ); 810 } 811 else if( c < 0 ) 812 { 813 return find( key, startNode.left, path ); 814 } 815 816 return null; 817 } 818 819 820 /** 821 * {@inheritDoc} 822 */ 823 public LinkedAvlMapNode<K,V> findGreater( K key ) 824 { 825 LinkedAvlMapNode<K,V> result = fetchNonNullNode( key, root, root); 826 827 if( result == null ) 828 { 829 return null; 830 } 831 else if( keyComparator.compare( key, result.key ) < 0 ) 832 { 833 return result; 834 } 835 836 return result.next; 837 } 838 839 840 /** 841 * {@inheritDoc} 842 */ 843 public LinkedAvlMapNode<K,V> findGreaterOrEqual( K key ) 844 { 845 LinkedAvlMapNode<K,V> result = fetchNonNullNode( key, root, root); 846 847 if( result == null ) 848 { 849 return null; 850 } 851 else if( keyComparator.compare( key, result.key ) <= 0 ) 852 { 853 return result; 854 } 855 856 return result.next; 857 } 858 859 860 /** 861 * {@inheritDoc} 862 */ 863 public LinkedAvlMapNode<K,V> findLess( K key ) 864 { 865 LinkedAvlMapNode<K,V> result = fetchNonNullNode( key, root, root); 866 867 if( result == null ) 868 { 869 return null; 870 } 871 else if( keyComparator.compare( key, result.key ) > 0 ) 872 { 873 return result; 874 } 875 876 return result.previous; 877 } 878 879 880 /** 881 * {@inheritDoc} 882 */ 883 public LinkedAvlMapNode<K,V> findLessOrEqual( K key ) 884 { 885 LinkedAvlMapNode<K,V> result = fetchNonNullNode( key, root, root); 886 887 if( result == null ) 888 { 889 return null; 890 } 891 else if( keyComparator.compare( key, result.key ) >= 0 ) 892 { 893 return result; 894 } 895 896 return result.previous; 897 } 898 899 900 /* 901 * This method returns the last visited non-null node in case if the node with the given key 902 * is not present. This method should not be used as general purpose lookup method. 903 * This is written to assist the findGreater, findLess methods. 904 */ 905 private LinkedAvlMapNode<K,V> fetchNonNullNode( K key, LinkedAvlMapNode<K,V> startNode, LinkedAvlMapNode<K,V> parent ) 906 { 907 908 if( startNode == null ) 909 { 910 return parent; 911 } 912 913 int c = keyComparator.compare( key, startNode.key ); 914 915 parent = startNode; 916 917 if( c > 0 ) 918 { 919 return fetchNonNullNode( key, startNode.right, parent ); 920 } 921 else if( c < 0 ) 922 { 923 return fetchNonNullNode( key, startNode.left, parent ); 924 } 925 926 return startNode; 927 } 928 929 /** 930 * {@inheritDoc} 931 */ 932 public LinkedAvlMapNode<K,V> find( K key ) 933 { 934 return find( key, root); 935 } 936 937 938 /** 939 * {@inheritDoc} 940 */ 941 public LinkedAvlMapNode<K,V> find( K key, V value ) 942 { 943 if( key == null || value == null ) 944 { 945 return null; 946 } 947 948 LinkedAvlMapNode<K,V> node = find( key, root ); 949 950 if( node == null ) 951 { 952 return null; 953 } 954 955 if( node.value.isOrderedSet() ) 956 { 957 AvlTree<V> dupsTree = node.value.getOrderedSet(); 958 959 if( dupsTree.find( value ) == null ) 960 { 961 return null; 962 } 963 } 964 else 965 { 966 if( valueComparator.compare( node.value.getSingleton(), value ) != 0 ) 967 { 968 return null; 969 } 970 } 971 972 return node; 973 } 974 975 976 private LinkedAvlMapNode<K,V> find( K key, LinkedAvlMapNode<K,V> startNode) 977 { 978 int c; 979 980 if( startNode == null ) 981 { 982 return null; 983 } 984 985 c = keyComparator.compare( key, startNode.key ); 986 987 if( c > 0 ) 988 { 989 startNode.isLeft = false; 990 return find( key, startNode.right ); 991 } 992 else if( c < 0 ) 993 { 994 startNode.isLeft = true; 995 return find( key, startNode.left ); 996 } 997 998 return startNode; 999 } 1000 1001 1002 /** 1003 * Find the LinkedAvlMapNode having the max key value in the tree starting from the startNode. 1004 * 1005 * @param startNode starting node of a subtree/tree 1006 * @return the list of traversed LinkedAvlMapNodes. 1007 */ 1008 private List<LinkedAvlMapNode<K,V>> findMax( LinkedAvlMapNode<K,V> startNode ) 1009 { 1010 LinkedAvlMapNode<K,V> x = startNode; 1011 LinkedAvlMapNode<K,V> y = null; 1012 List<LinkedAvlMapNode<K,V>> path; 1013 1014 if( x == null ) 1015 { 1016 return null; 1017 } 1018 1019 while( x.right != null ) 1020 { 1021 x.isLeft = false; 1022 y = x; 1023 x = x.right; 1024 } 1025 1026 path = new ArrayList<LinkedAvlMapNode<K,V>>(2); 1027 path.add( x ); 1028 1029 if ( y != null ) 1030 { 1031 path.add( y ); 1032 } 1033 1034 return path; 1035 } 1036 1037 1038 /** 1039 * Find the LinkedAvlMapNode having the min key value in the tree starting from the startNode. 1040 * 1041 * @param startNode starting node of a subtree/tree 1042 * @return the list of traversed LinkedAvlMapNodes. 1043 */ 1044 private List<LinkedAvlMapNode<K,V>> findMin( LinkedAvlMapNode<K,V> startNode ) 1045 { 1046 LinkedAvlMapNode<K,V> x = startNode; 1047 LinkedAvlMapNode<K,V> y = null; 1048 List<LinkedAvlMapNode<K,V>> path; 1049 1050 if( x == null ) 1051 { 1052 return null; 1053 } 1054 1055 while( x.left != null ) 1056 { 1057 x.isLeft = true; 1058 y = x; 1059 x = x.left; 1060 } 1061 1062 path = new ArrayList<LinkedAvlMapNode<K,V>>(2); 1063 path.add( x ); 1064 1065 if ( y != null ) 1066 { 1067 path.add( y ); 1068 } 1069 1070 return path; 1071 } 1072 1073 1074 /** 1075 * Get balance-factor of the given LinkedAvlMapNode. 1076 * 1077 * @param node a LinkedAvlMapNode 1078 * @return balance-factor of the node 1079 */ 1080 private int getBalance( LinkedAvlMapNode<K,V> node ) 1081 { 1082 if( node == null) 1083 { 1084 return 0; 1085 } 1086 1087 return node.getBalance(); 1088 } 1089 1090 1091 private void visit( LinkedAvlMapNode<K,V> node, LinkedAvlMapNode<K,V> parentNode ) 1092 { 1093 if( node == null ) 1094 { 1095 return; 1096 } 1097 1098 if( !node.isLeaf() ) 1099 { 1100 node.setDepth( parentNode.getDepth() + 1 ); 1101 } 1102 1103 for( int i=0; i < parentNode.getDepth(); i++ ) 1104 { 1105 System.out.print( "| " ); 1106 } 1107 1108 String type = ""; 1109 if( node == parentNode.left ) 1110 { 1111 type = "L"; 1112 } 1113 else if( node == parentNode.right ) 1114 { 1115 type = "R"; 1116 } 1117 1118 System.out.println( "|--" + node + type ); 1119 1120 if ( node.getRight() != null ) 1121 { 1122 visit( node.getRight(), node ); 1123 } 1124 1125 if( node.getLeft() != null ) 1126 { 1127 visit( node.getLeft(), node ); 1128 } 1129 } 1130 1131 1132 /** 1133 * {@inheritDoc} 1134 */ 1135 public boolean isDupsAllowed() 1136 { 1137 return allowDuplicates; 1138 } 1139 }