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    }