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