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