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.Arrays; 025import java.util.Comparator; 026import java.util.List; 027 028 029/** 030 * A data structure simulating a tree (ie, a sorted list of elements) using an array. 031 * 032 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 033 */ 034public class ArrayTree<K> 035{ 036 /** The Comparator used for comparing the keys */ 037 private Comparator<K> comparator; 038 039 /** The array containing the data */ 040 private K[] array; 041 042 /** The current number of elements in the array. May be lower than the array size */ 043 private int size; 044 045 /** The extend size to use when increasing the array size */ 046 private static final int INCREMENT = 16; 047 048 049 /** 050 * Creates a new instance of AVLTree. 051 * 052 * @param comparator the comparator to be used for comparing keys 053 */ 054 public ArrayTree( Comparator<K> comparator ) 055 { 056 this.comparator = comparator; 057 array = ( K[] ) new Object[INCREMENT]; 058 size = 0; 059 } 060 061 062 /** 063 * Creates a new instance of AVLTree. 064 * 065 * @param comparator the comparator to be used for comparing keys 066 * @param array The array of keys 067 */ 068 public ArrayTree( Comparator<K> comparator, K[] array ) 069 { 070 this.comparator = comparator; 071 072 if ( array != null ) 073 { 074 size = array.length; 075 int arraySize = size; 076 077 if ( size % INCREMENT != 0 ) 078 { 079 arraySize += INCREMENT - size % INCREMENT; 080 } 081 082 this.array = ( K[] ) new Object[arraySize]; 083 System.arraycopy( array, 0, this.array, 0, size ); 084 } 085 } 086 087 088 /** 089 * @return the comparator associated with this tree 090 */ 091 public Comparator<K> getComparator() 092 { 093 return comparator; 094 } 095 096 097 /** 098 * Inserts a key. Null value insertion is not allowed. 099 * 100 * @param key the item to be inserted, should not be null 101 * @return the replaced key if it already exists 102 * Note: Ignores if the given key already exists. 103 */ 104 public K insert( K key ) 105 { 106 if ( key == null ) 107 { 108 // We don't allow null values in the tree 109 return null; 110 } 111 112 // Check if the key already exists, and if so, return the 113 // existing one 114 K existing = find( key ); 115 116 if ( existing != null ) 117 { 118 return existing; 119 } 120 121 if ( size == array.length ) 122 { 123 // The array is full, let's extend it 124 K[] newArray = ( K[] ) new Object[size + INCREMENT]; 125 126 System.arraycopy( array, 0, newArray, 0, size ); 127 array = newArray; 128 } 129 130 // Currently, just add the element at the end of the array 131 // and sort the array. We could be more efficient by inserting the 132 // element at the right position by splitting the array in two 133 // parts and copying the right part one slot on the right. 134 array[size++] = key; 135 Arrays.sort( array, 0, size, comparator ); 136 137 return null; 138 } 139 140 141 /**q< 142 * Reduce the array size if neede 143 */ 144 private void reduceArray() 145 { 146 // We will reduce the array size when the number of elements 147 // in it is leaving twice the number of INCREMENT empty slots. 148 // We then remove INCREMENT slots 149 if ( ( array.length - size ) > ( INCREMENT << 1 ) ) 150 { 151 K[] newArray = ( K[] ) new Object[array.length - INCREMENT]; 152 System.arraycopy( array, 0, newArray, 0, array.length ); 153 } 154 } 155 156 157 /** 158 * Removes a key present in the tree 159 * 160 * @param key the value to be removed 161 * @return the removed key, if any, or null if the key does not exist 162 */ 163 public K remove( K key ) 164 { 165 // Search for the key position in the tree 166 int pos = getPosition( key ); 167 168 if ( pos != -1 ) 169 { 170 // Found... 171 if ( pos != size - 1 ) 172 { 173 // If the element is not the last one, we have to 174 // move the end of the array one step to the left 175 System.arraycopy( array, pos + 1, array, pos, size - pos - 1 ); 176 177 reduceArray(); 178 } 179 180 size--; 181 182 return key; 183 } 184 else 185 { 186 return null; 187 } 188 } 189 190 191 /** 192 * Tests if the tree is empty. 193 * 194 * @return true if the tree is empty, false otherwise 195 */ 196 public boolean isEmpty() 197 { 198 return size == 0; 199 } 200 201 202 /** 203 * returns the number of nodes present in this tree. 204 * 205 * @return the number of nodes present in this tree 206 */ 207 public int size() 208 { 209 return size; 210 } 211 212 213 /** 214 * @return a list of the stored keys in this tree 215 */ 216 public List<K> getKeys() 217 { 218 List<K> list = new ArrayList<>( size ); 219 220 for ( int i = 0; i < size; i++ ) 221 { 222 list.add( array[i] ); 223 } 224 225 return list; 226 } 227 228 229 /** 230 * Prints the contents of AVL tree in pretty format 231 */ 232 public void printTree() 233 { 234 if ( isEmpty() ) 235 { 236 System.out.println( "Tree is empty" ); 237 return; 238 } 239 240 boolean isFirst = true; 241 242 for ( K key : array ) 243 { 244 if ( isFirst ) 245 { 246 isFirst = false; 247 } 248 else 249 { 250 System.out.print( ", " ); 251 } 252 253 System.out.println( key ); 254 } 255 } 256 257 258 /** 259 * Get the element at a given position 260 * @param position The position in the tree 261 * @return The found key, or null if the position is out of scope 262 */ 263 public K get( int position ) 264 { 265 if ( ( position < 0 ) || ( position >= size ) ) 266 { 267 throw new ArrayIndexOutOfBoundsException(); 268 } 269 270 return array[position]; 271 } 272 273 274 /** 275 * Get the first element in the tree. It sets the current position to this 276 * element. 277 * @return The first element of this tree 278 */ 279 public K getFirst() 280 { 281 if ( size != 0 ) 282 { 283 return array[0]; 284 } 285 else 286 { 287 return null; 288 } 289 } 290 291 292 /** 293 * Get the last element in the tree. It sets the current position to this 294 * element. 295 * @return The last element in this tree 296 */ 297 public K getLast() 298 { 299 if ( size != 0 ) 300 { 301 return array[size - 1]; 302 } 303 else 304 { 305 return null; 306 } 307 } 308 309 310 /** 311 * Finds a key higher than the given key. Sets the current position to this 312 * element. 313 * 314 * @param key the key to find 315 * @return the LinkedAvlNode whose key is greater than the given key ,<br> 316 * null if there is no node with a higher key than the given key. 317 */ 318 public K findGreater( K key ) 319 { 320 if ( key == null ) 321 { 322 return null; 323 } 324 325 switch ( size ) 326 { 327 case 0: 328 return null; 329 330 case 1: 331 if ( comparator.compare( array[0], key ) > 0 ) 332 { 333 return array[0]; 334 } 335 else 336 { 337 return null; 338 } 339 340 case 2: 341 if ( comparator.compare( array[0], key ) > 0 ) 342 { 343 return array[0]; 344 } 345 else if ( comparator.compare( array[1], key ) > 0 ) 346 { 347 return array[1]; 348 } 349 else 350 { 351 return null; 352 } 353 354 default: 355 // Split the array in two parts, the left part an the right part 356 int current = size >> 1; 357 int start = 0; 358 int end = size - 1; 359 360 while ( end - start + 1 > 2 ) 361 { 362 int res = comparator.compare( array[current], key ); 363 364 if ( res == 0 ) 365 { 366 // Current can't be equal to zero at this point 367 return array[current + 1]; 368 } 369 else if ( res < 0 ) 370 { 371 start = current; 372 current = ( current + end + 1 ) >> 1; 373 } 374 else 375 { 376 end = current; 377 current = ( current + start + 1 ) >> 1; 378 } 379 } 380 381 switch ( end - start + 1 ) 382 { 383 case 1: 384 int res = comparator.compare( array[start], key ); 385 386 if ( res <= 0 ) 387 { 388 if ( start == size ) 389 { 390 return null; 391 } 392 else 393 { 394 return array[start + 1]; 395 } 396 } 397 398 return array[start]; 399 400 case 2: 401 res = comparator.compare( array[start], key ); 402 403 if ( res <= 0 ) 404 { 405 res = comparator.compare( array[start + 1], key ); 406 407 if ( res <= 0 ) 408 { 409 if ( start == size - 2 ) 410 { 411 return null; 412 } 413 414 return array[start + 2]; 415 } 416 417 return array[start + 1]; 418 } 419 420 return array[start]; 421 422 default: 423 return null; 424 } 425 } 426 } 427 428 429 /** 430 * Finds a key higher than the given key. 431 * 432 * @param key the key 433 * @return the key chich is greater than the given key ,<br> 434 * null if there is no higher key than the given key. 435 */ 436 public K findGreaterOrEqual( K key ) 437 { 438 if ( key == null ) 439 { 440 return null; 441 } 442 443 switch ( size ) 444 { 445 case 0: 446 return null; 447 448 case 1: 449 if ( comparator.compare( array[0], key ) >= 0 ) 450 { 451 return array[0]; 452 } 453 else 454 { 455 return null; 456 } 457 458 case 2: 459 if ( comparator.compare( array[0], key ) >= 0 ) 460 { 461 return array[0]; 462 } 463 else if ( comparator.compare( array[1], key ) >= 0 ) 464 { 465 return array[1]; 466 } 467 else 468 { 469 return null; 470 } 471 472 default: 473 // Split the array in two parts, the left part an the right part 474 int current = size >> 1; 475 int start = 0; 476 int end = size - 1; 477 478 while ( end - start + 1 > 2 ) 479 { 480 int res = comparator.compare( array[current], key ); 481 482 if ( res == 0 ) 483 { 484 return array[current]; 485 } 486 else if ( res < 0 ) 487 { 488 start = current; 489 current = ( current + end + 1 ) >> 1; 490 } 491 else 492 { 493 end = current; 494 current = ( current + start + 1 ) >> 1; 495 } 496 } 497 498 switch ( end - start + 1 ) 499 { 500 case 1: 501 int res = comparator.compare( array[start], key ); 502 503 if ( res >= 0 ) 504 { 505 return array[start]; 506 } 507 else 508 { 509 if ( start == size - 1 ) 510 { 511 return null; 512 } 513 else 514 { 515 return array[start + 1]; 516 } 517 } 518 519 case 2: 520 res = comparator.compare( array[start], key ); 521 522 if ( res < 0 ) 523 { 524 res = comparator.compare( array[start + 1], key ); 525 526 if ( res < 0 ) 527 { 528 if ( start == size - 2 ) 529 { 530 return null; 531 } 532 533 return array[start + 2]; 534 } 535 536 return array[start + 1]; 537 } 538 539 return array[start]; 540 541 default: 542 return null; 543 } 544 } 545 } 546 547 548 /** 549 * Finds a key which is lower than the given key. 550 * 551 * @param key the key 552 * @return the key lower than the given key ,<br> 553 * null if there is no node with a lower key than the given key. 554 */ 555 public K findLess( K key ) 556 { 557 if ( key == null ) 558 { 559 return null; 560 } 561 562 switch ( size ) 563 { 564 case 0: 565 return null; 566 567 case 1: 568 if ( comparator.compare( array[0], key ) >= 0 ) 569 { 570 return null; 571 } 572 else 573 { 574 return array[0]; 575 } 576 577 case 2: 578 if ( comparator.compare( array[0], key ) >= 0 ) 579 { 580 return null; 581 } 582 else if ( comparator.compare( array[1], key ) >= 0 ) 583 { 584 return array[0]; 585 } 586 else 587 { 588 return array[1]; 589 } 590 591 default: 592 // Split the array in two parts, the left part an the right part 593 int current = size >> 1; 594 int start = 0; 595 int end = size - 1; 596 597 while ( end - start + 1 > 2 ) 598 { 599 int res = comparator.compare( array[current], key ); 600 601 if ( res == 0 ) 602 { 603 // Current can't be equal to zero at this point 604 return array[current - 1]; 605 } 606 else if ( res < 0 ) 607 { 608 start = current; 609 current = ( current + end + 1 ) >> 1; 610 } 611 else 612 { 613 end = current; 614 current = ( current + start + 1 ) >> 1; 615 } 616 } 617 618 switch ( end - start + 1 ) 619 { 620 case 1: 621 // Three cases : 622 // o The value is equal to the current position, or below 623 // the current position : 624 // - if the current position is at the beginning 625 // of the array, return null 626 // - otherwise, return the previous position in the array 627 // o The value is above the current position : 628 // - return the current position 629 int res = comparator.compare( array[start], key ); 630 631 if ( res >= 0 ) 632 { 633 // start can be equal to 0. Check that 634 if ( start == 1 ) 635 { 636 return null; 637 } 638 else 639 { 640 return array[start - 1]; 641 } 642 } 643 else 644 { 645 return array[start]; 646 } 647 648 case 2: 649 // Four cases : 650 // o the value is equal the current position, or below 651 // the first position : 652 // - if the current position is at the beginning 653 // of the array, return null 654 // - otherwise, return the previous element 655 // o the value is above the first position but below 656 // or equal the second position, return the first position 657 // o otherwise, return the second position 658 res = comparator.compare( array[start], key ); 659 660 if ( res >= 0 ) 661 { 662 if ( start == 0 ) 663 { 664 return null; 665 } 666 else 667 { 668 return array[start - 1]; 669 } 670 } 671 else if ( comparator.compare( array[start + 1], key ) >= 0 ) 672 { 673 return array[start]; 674 } 675 else 676 { 677 return array[start + 1]; 678 } 679 680 default: 681 return null; 682 } 683 } 684 } 685 686 687 /** 688 * Finds a key chich is lower than the given key. 689 * 690 * @param key the key 691 * @return the key which is lower than the given key ,<br> 692 * null if there is no node with a lower key than the given key. 693 */ 694 public K findLessOrEqual( K key ) 695 { 696 if ( key == null ) 697 { 698 return null; 699 } 700 701 switch ( size ) 702 { 703 case 0: 704 return null; 705 706 case 1: 707 if ( comparator.compare( array[0], key ) <= 0 ) 708 { 709 return array[0]; 710 } 711 else 712 { 713 return null; 714 } 715 716 case 2: 717 int res = comparator.compare( array[0], key ); 718 719 if ( res > 0 ) 720 { 721 return null; 722 } 723 else if ( res == 0 ) 724 { 725 return array[0]; 726 } 727 728 res = comparator.compare( array[1], key ); 729 730 if ( res == 0 ) 731 { 732 return array[1]; 733 } 734 else if ( comparator.compare( array[1], key ) > 0 ) 735 { 736 return array[0]; 737 } 738 else 739 { 740 return array[1]; 741 } 742 743 default: 744 // Split the array in two parts, the left part an the right part 745 int current = size >> 1; 746 int start = 0; 747 int end = size - 1; 748 749 while ( end - start + 1 > 2 ) 750 { 751 res = comparator.compare( array[current], key ); 752 753 if ( res == 0 ) 754 { 755 return array[current]; 756 } 757 else if ( res < 0 ) 758 { 759 start = current; 760 current = ( current + end + 1 ) >> 1; 761 } 762 else 763 { 764 end = current; 765 current = ( current + start + 1 ) >> 1; 766 } 767 } 768 769 switch ( end - start + 1 ) 770 { 771 case 1: 772 // Three cases : 773 // o The value is equal to the current position, or below 774 // the current position : 775 // - if the current position is at the beginning 776 // of the array, return null 777 // - otherwise, return the previous position in the array 778 // o The value is above the current position : 779 // - return the current position 780 res = comparator.compare( array[start], key ); 781 782 if ( res > 0 ) 783 { 784 // start can be equal to 0. Check that 785 if ( start == 1 ) 786 { 787 return null; 788 } 789 else 790 { 791 return array[start - 1]; 792 } 793 } 794 else 795 { 796 return array[start]; 797 } 798 799 case 2: 800 // Four cases : 801 // o the value is equal the current position, or below 802 // the first position : 803 // - if the current position is at the beginning 804 // of the array, return null 805 // - otherwise, return the previous element 806 // o the value is above the first position but below 807 // or equal the second position, return the first position 808 // o otherwise, return the second position 809 res = comparator.compare( array[start], key ); 810 811 if ( res > 0 ) 812 { 813 if ( start == 0 ) 814 { 815 return null; 816 } 817 else 818 { 819 return array[start - 1]; 820 } 821 } 822 823 res = comparator.compare( array[start + 1], key ); 824 825 if ( res > 0 ) 826 { 827 return array[start]; 828 } 829 else 830 { 831 return array[start + 1]; 832 } 833 834 default: 835 return null; 836 } 837 } 838 } 839 840 841 /** 842 * Find an element in the array. 843 * 844 * @param key the key to find 845 * @return the found node, or null 846 */ 847 public K find( K key ) 848 { 849 if ( key == null ) 850 { 851 return null; 852 } 853 854 switch ( size ) 855 { 856 case 0: 857 return null; 858 859 case 1: 860 if ( comparator.compare( array[0], key ) == 0 ) 861 { 862 return array[0]; 863 } 864 else 865 { 866 return null; 867 } 868 869 case 2: 870 if ( comparator.compare( array[0], key ) == 0 ) 871 { 872 return array[0]; 873 } 874 else if ( comparator.compare( array[1], key ) == 0 ) 875 { 876 return array[1]; 877 } 878 else 879 { 880 return null; 881 } 882 883 default: 884 // Split the array in two parts, the left part an the right part 885 int current = size >> 1; 886 int start = 0; 887 int end = size - 1; 888 889 while ( end - start + 1 > 2 ) 890 { 891 int res = comparator.compare( array[current], key ); 892 893 if ( res == 0 ) 894 { 895 return array[current]; 896 } 897 else if ( res < 0 ) 898 { 899 start = current; 900 current = ( current + end + 1 ) >> 1; 901 } 902 else 903 { 904 end = current; 905 current = ( current + start + 1 ) >> 1; 906 } 907 } 908 909 switch ( end - start + 1 ) 910 { 911 case 1: 912 if ( comparator.compare( array[start], key ) == 0 ) 913 { 914 return array[start]; 915 } 916 else 917 { 918 return null; 919 } 920 921 case 2: 922 if ( comparator.compare( array[start], key ) == 0 ) 923 { 924 return array[start]; 925 } 926 else if ( comparator.compare( array[end], key ) == 0 ) 927 { 928 return array[end]; 929 } 930 else 931 { 932 return null; 933 } 934 935 default: 936 return null; 937 } 938 } 939 } 940 941 942 /** 943 * Find the element position in the array. 944 * 945 * @param key the key to find 946 * @return the position in the array, or -1 if not found 947 */ 948 public int getPosition( K key ) 949 { 950 if ( key == null ) 951 { 952 return -1; 953 } 954 955 switch ( size ) 956 { 957 case 0: 958 return -1; 959 960 case 1: 961 if ( comparator.compare( array[0], key ) == 0 ) 962 { 963 return 0; 964 } 965 else 966 { 967 return -1; 968 } 969 970 case 2: 971 if ( comparator.compare( array[0], key ) == 0 ) 972 { 973 return 0; 974 } 975 else if ( comparator.compare( array[1], key ) == 0 ) 976 { 977 return 1; 978 } 979 else 980 { 981 return -1; 982 } 983 984 default: 985 // Split the array in two parts, the left part an the right part 986 int current = size >> 1; 987 int start = 0; 988 int end = size - 1; 989 990 while ( end - start + 1 > 2 ) 991 { 992 int res = comparator.compare( array[current], key ); 993 994 if ( res == 0 ) 995 { 996 return current; 997 } 998 else if ( res < 0 ) 999 { 1000 start = current; 1001 current = ( current + end + 1 ) >> 1; 1002 } 1003 else 1004 { 1005 end = current; 1006 current = ( current + start + 1 ) >> 1; 1007 } 1008 } 1009 1010 switch ( end - start + 1 ) 1011 { 1012 case 1: 1013 if ( comparator.compare( array[start], key ) == 0 ) 1014 { 1015 return start; 1016 } 1017 else 1018 { 1019 return -1; 1020 } 1021 1022 case 2: 1023 if ( comparator.compare( array[start], key ) == 0 ) 1024 { 1025 return start; 1026 } 1027 else if ( comparator.compare( array[end], key ) == 0 ) 1028 { 1029 return end; 1030 } 1031 else 1032 { 1033 return -1; 1034 } 1035 1036 default: 1037 return -1; 1038 } 1039 } 1040 } 1041 1042 1043 /** 1044 * Find the element position in the array, or the position of the closest greater element in the array. 1045 * 1046 * @param key the key to find 1047 * @return the position in the array, or -1 if not found 1048 */ 1049 public int getAfterPosition( K key ) 1050 { 1051 if ( key == null ) 1052 { 1053 return -1; 1054 } 1055 1056 switch ( size ) 1057 { 1058 case 0: 1059 return -1; 1060 1061 case 1: 1062 if ( comparator.compare( array[0], key ) > 0 ) 1063 { 1064 return 0; 1065 } 1066 else 1067 { 1068 return -1; 1069 } 1070 1071 case 2: 1072 if ( comparator.compare( array[0], key ) > 0 ) 1073 { 1074 return 0; 1075 } 1076 1077 if ( comparator.compare( array[1], key ) > 0 ) 1078 { 1079 return 1; 1080 } 1081 else 1082 { 1083 return -1; 1084 } 1085 1086 default: 1087 // Split the array in two parts, the left part an the right part 1088 int current = size >> 1; 1089 int start = 0; 1090 int end = size - 1; 1091 1092 while ( end - start + 1 > 2 ) 1093 { 1094 int res = comparator.compare( array[current], key ); 1095 1096 if ( res == 0 ) 1097 { 1098 if ( current != size - 1 ) 1099 { 1100 return current + 1; 1101 } 1102 else 1103 { 1104 return -1; 1105 } 1106 } 1107 else if ( res < 0 ) 1108 { 1109 start = current; 1110 current = ( current + end + 1 ) >> 1; 1111 } 1112 else 1113 { 1114 end = current; 1115 current = ( current + start + 1 ) >> 1; 1116 } 1117 } 1118 1119 switch ( end - start + 1 ) 1120 { 1121 case 1: 1122 if ( comparator.compare( array[start], key ) > 0 ) 1123 { 1124 return start; 1125 } 1126 else 1127 { 1128 return -1; 1129 } 1130 1131 case 2: 1132 if ( comparator.compare( array[start], key ) > 0 ) 1133 { 1134 return start; 1135 } 1136 1137 if ( comparator.compare( array[end], key ) > 0 ) 1138 { 1139 return end; 1140 } 1141 else 1142 { 1143 return -1; 1144 } 1145 1146 default: 1147 return -1; 1148 } 1149 } 1150 } 1151 1152 1153 /** 1154 * Find the element position in the array, or the position of the closest greater element in the array. 1155 * 1156 * @param key the key to find 1157 * @return the position in the array, or -1 if not found 1158 */ 1159 public int getBeforePosition( K key ) 1160 { 1161 if ( key == null ) 1162 { 1163 return -1; 1164 } 1165 1166 switch ( size ) 1167 { 1168 case 0: 1169 return -1; 1170 1171 case 1: 1172 if ( comparator.compare( array[0], key ) < 0 ) 1173 { 1174 return 0; 1175 } 1176 else 1177 { 1178 return -1; 1179 } 1180 1181 case 2: 1182 if ( comparator.compare( array[1], key ) < 0 ) 1183 { 1184 return 1; 1185 } 1186 1187 if ( comparator.compare( array[0], key ) < 0 ) 1188 { 1189 return 0; 1190 } 1191 else 1192 { 1193 return -1; 1194 } 1195 1196 default: 1197 // Split the array in two parts, the left part an the right part 1198 int current = size >> 1; 1199 int start = 0; 1200 int end = size - 1; 1201 1202 while ( end - start + 1 > 2 ) 1203 { 1204 int res = comparator.compare( array[current], key ); 1205 1206 if ( res == 0 ) 1207 { 1208 if ( current == 0 ) 1209 { 1210 return -1; 1211 } 1212 else 1213 { 1214 return current - 1; 1215 } 1216 } 1217 else if ( res < 0 ) 1218 { 1219 start = current; 1220 current = ( current + end + 1 ) >> 1; 1221 } 1222 else 1223 { 1224 end = current; 1225 current = ( current + start + 1 ) >> 1; 1226 } 1227 } 1228 1229 switch ( end - start + 1 ) 1230 { 1231 case 1: 1232 if ( comparator.compare( array[start], key ) < 0 ) 1233 { 1234 return start; 1235 } 1236 else 1237 { 1238 return -1; 1239 } 1240 1241 case 2: 1242 if ( comparator.compare( array[end], key ) < 0 ) 1243 { 1244 return end; 1245 } 1246 1247 if ( comparator.compare( array[start], key ) < 0 ) 1248 { 1249 return start; 1250 } 1251 else 1252 { 1253 return -1; 1254 } 1255 1256 default: 1257 return -1; 1258 } 1259 } 1260 } 1261 1262 1263 /** 1264 * Tells if a key exist in the array. 1265 * 1266 * @param key The key to look for 1267 * @return true if the key exist in the array 1268 */ 1269 public boolean contains( K key ) 1270 { 1271 return find( key ) != null; 1272 } 1273 1274 1275 /** 1276 * {@inheritDoc} 1277 */ 1278 public String toString() 1279 { 1280 if ( isEmpty() ) 1281 { 1282 return "[]"; 1283 } 1284 1285 StringBuilder sb = new StringBuilder(); 1286 1287 boolean isFirst = true; 1288 1289 for ( int i = 0; i < size; i++ ) 1290 { 1291 K key = array[i]; 1292 1293 if ( isFirst ) 1294 { 1295 isFirst = false; 1296 } 1297 else 1298 { 1299 sb.append( ", " ); 1300 } 1301 1302 sb.append( key ); 1303 } 1304 1305 return sb.toString(); 1306 } 1307}