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