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 AVL tree implementation
030     *
031     * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
032     * @version $Rev$, $Date$
033     */
034    public class AvlTreeImpl<K> implements AvlTree<K>
035    {
036        /** the root of the tree */
037        private LinkedAvlNode<K> root;
038    
039        /** The Comparator used for comparing the keys */
040        private Comparator<K> comparator;
041    
042        /** node representing the start of the doubly linked list formed with the tree nodes */
043        private LinkedAvlNode<K> first;
044        
045        /** node representing the end of the doubly linked list formed with the tree nodes */
046        private LinkedAvlNode<K> last;
047    
048        /** size of the tree */
049        private int size;
050    
051        /**
052         * Creates a new instance of AVLTree.
053         *
054         * @param comparator the comparator to be used for comparing keys
055         */
056        public AvlTreeImpl( Comparator<K> comparator)
057        {
058            this.comparator = comparator;
059        }
060        
061        
062        /* (non-Javadoc)
063         * @see org.apache.directory.server.core.avltree.AvlTree#getComparator()
064         */
065        public Comparator<K> getComparator()
066        {
067            return comparator;
068        }
069        
070        
071        /* (non-Javadoc)
072         * @see org.apache.directory.server.core.avltree.AvlTree#insert(K)
073         */
074        public K insert( K key )
075        {
076            LinkedAvlNode<K> node, temp;
077            LinkedAvlNode<K> parent = null;
078            int c;
079            
080            if ( root == null )
081            {
082              root = new LinkedAvlNode<K>( key );
083              first = root;
084              last = root;
085              size++;
086              return null;
087            }
088            
089            node = new LinkedAvlNode<K>( key );
090            
091            temp = root;
092            
093            List<LinkedAvlNode<K>> treePath = new ArrayList<LinkedAvlNode<K>>();
094    
095            while( temp != null )
096            {
097                treePath.add(0, temp ); // last node first, for the sake of balance factor computation
098                parent = temp;
099                
100                c = comparator.compare( key, temp.getKey() );
101                
102                if( c == 0 )
103                {
104                    return key; // key already exists
105                }
106                
107                if( c < 0 )
108                {
109                    temp.isLeft = true;
110                    temp = temp.getLeft();
111                }
112                else
113                {
114                    temp.isLeft = false;
115                    temp = temp.getRight();
116                }
117            }
118            
119            if( ( c = comparator.compare( key, parent.getKey() ) ) < 0 )
120            {
121                parent.setLeft( node );
122            }
123            else
124            {
125                parent.setRight( node );
126            }
127            
128            insertInList( node, parent, c );
129            
130            treePath.add( 0, node );
131            balance(treePath);
132            
133            size++;
134            return null;
135        }
136        
137        
138        private void removeFromList(LinkedAvlNode<K> node)
139        {
140            if( node.next == null && node.previous == null ) // should happen in case of tree having single node
141            {
142                first = last = null;
143            }
144            else if( node.next == null ) // last node
145            {
146                node.previous.next = null;
147                last = node.previous;
148            }
149            else if( node.previous == null ) // first node
150            {
151                node.next.previous = null;
152                first = node.next;
153            }
154            else // somewhere in middle
155            {
156                node.previous.next = node.next;
157                node.next.previous = node.previous;
158            }
159            
160        }
161        
162        
163        private void insertInList(LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode, int pos)
164        {
165    
166            if( pos < 0 )
167            {
168                if( last == null )
169                {
170                  last = parentNode;  
171                }
172                
173                if( parentNode.previous == null )
174                {
175                    first = node;
176                }
177                else
178                {
179                    parentNode.previous.next = node ;
180                    node.previous = parentNode.previous;
181                }
182                
183                node.next = parentNode;
184                parentNode.previous = node;
185            }
186            else if( pos > 0 )
187            {
188                if( parentNode.next == null )
189                {
190                    last = node;
191                }
192                else
193                {
194                    parentNode.next.previous = node;
195                    node.next = parentNode.next;
196                }
197                node.previous = parentNode;
198                parentNode.next = node;
199             }
200            
201        }
202        
203        
204        /* (non-Javadoc)
205         * @see org.apache.directory.server.core.avltree.AvlTree#remove(K)
206         */
207        public K remove( K key )
208        {
209            LinkedAvlNode<K> temp = null;
210            LinkedAvlNode<K> y = null;
211            
212            List<LinkedAvlNode<K>> treePath = new ArrayList<LinkedAvlNode<K>>();
213            
214            treePath = find( key, root, treePath);
215            
216            if( treePath == null )
217            {
218                return null;
219            }
220            
221            temp = treePath.remove( 0 );
222    
223            // remove from the doubly linked
224            removeFromList(temp);        
225            
226            if( temp.isLeaf() )
227            {
228                if( temp == root )
229                {
230                  root = null;
231                  size--;
232                  return key;
233                }
234                
235                if( !treePath.isEmpty() )
236                {
237                    detachNodes( temp, treePath.get( 0 ) );
238                }
239            }
240            else
241            {
242                if( temp.left != null )
243                {
244                    List<LinkedAvlNode<K>> leftTreePath = findMax( temp.left );
245                    y = leftTreePath.remove( 0 );
246                    
247                    if( leftTreePath.isEmpty() ) // y is the left child of root and y is a leaf
248                    {
249                        detachNodes( y, temp );
250                    }
251                    else
252                    {
253                        detachNodes( y, leftTreePath.remove( 0 ) );
254                    }
255                    
256                    leftTreePath.addAll( treePath );
257                    treePath = leftTreePath;
258                    
259                    y.right = temp.right; // assign the right here left will be assigned in replaceNode()
260    
261                    if( temp == root )
262                    {
263                        y.left = temp.left;
264                        root = y;
265                    }
266                    else
267                    {
268                        replaceNode( temp, y, treePath.get( 0 ) );
269                    }
270                }
271                else if( temp.right != null )
272                {
273                    List<LinkedAvlNode<K>> rightTreePath = findMin( temp.right );
274                    y = rightTreePath.remove( 0 );
275                    
276                    if( rightTreePath.isEmpty() )
277                    {
278                        detachNodes( y, temp ); // y is the right child of root and y is a leaf
279                    }
280                    else
281                    {
282                        detachNodes( y, rightTreePath.remove( 0 ) );
283                    }
284                    
285                    rightTreePath.addAll( treePath );
286                    treePath = rightTreePath;
287                    
288                    y.right = temp.right; // assign the right here left will be assigned in replaceNode()
289                    
290                    if( temp == root )
291                    {
292                        y.right = temp.right;
293                        root = y;
294                    }
295                    else
296                    {
297                        replaceNode( temp, y, treePath.get( 0 ) );
298                    }
299                }
300            }
301           
302           treePath.add( 0, y ); // y can be null but getBalance returns 0 so np
303           balance( treePath );
304           
305           size--;
306           return key;
307        }
308        
309        
310        /**
311         * Balances the tree by visiting the nodes present in the List of nodes present in the
312         * treePath parameter.<br><br>
313         *
314         * This really does the balancing if the height of the tree is greater than 2 and the<br> 
315         * balance factor is greater than +1 or less than -1.<br><br>
316         * For an excellent info please read the 
317         * <a href="http://en.wikipedia.org/wiki/Avl_tree">Wikipedia article on AVL tree</a>.
318         * 
319         * @param treePath the traversed list of LinkedAvlNodes after performing an insert/delete operation.
320         */
321        private void balance( List<LinkedAvlNode<K>> treePath )
322        {
323            LinkedAvlNode<K> parentNode = null;
324            
325            int size = treePath.size();
326            
327            for( LinkedAvlNode<K> node: treePath )
328            {
329                int balFactor = getBalance( node );
330    
331                if( node != root )
332                {
333                    if( treePath.indexOf( node ) < ( size - 1 ) )
334                    {
335                        parentNode = treePath.get( treePath.indexOf( node ) + 1 );
336                    }
337                }
338    
339                if( balFactor > 1 )
340                {
341                    if( getBalance( node.right ) <= -1)
342                    {
343                        //------rotate double-left--------
344                        rotateSingleRight( node.right, node );
345                        rotateSingleLeft( node, parentNode );
346                    }
347                    else // rotate single-left
348                    {
349                       rotateSingleLeft( node, parentNode );
350                    }
351                }
352                else if( balFactor < -1 )
353                {
354                    if( getBalance( node.left ) >= 1)
355                    {
356                       //------rotate double-right--------
357                       rotateSingleLeft( node.left, node ); 
358                       rotateSingleRight( node, parentNode );
359                    }
360                    else
361                    {
362                        rotateSingleRight( node, parentNode );
363                    }
364                }
365            }
366        }
367        
368    
369        /* (non-Javadoc)
370         * @see org.apache.directory.server.core.avltree.AvlTree#isEmpty()
371         */
372        public boolean isEmpty()
373        {
374          return root == null;   
375        }
376    
377        
378        /* (non-Javadoc)
379         * @see org.apache.directory.server.core.avltree.AvlTree#getSize()
380         */
381        //NOTE: This method is internally used by AVLTreeMarshaller
382        public int getSize()
383        {
384            return size;
385        }
386        
387        /**
388         * Set the size of the tree.
389         * 
390         * Note : this method is used by the deserialization method
391         *
392         * @param size the size of the tree
393         */
394        /* no protection */ void setSize( int size )
395        {
396            this.size = size;
397        }
398        
399        
400        /**
401         * Set the root of the tree.
402         * 
403         * Note : this method is used by the deserialization method
404         *
405         * @param root the root of the tree
406         */
407        /* no protection */ void setRoot( LinkedAvlNode<K> root )
408        {
409            this.root = root;
410        }
411    
412        
413        /**
414         * Set the first element of the tree
415         * 
416         * Note : this method is used by the deserialization method
417         *
418         * @param first the first element to be added
419         */
420        /* no protection */  void setFirst( LinkedAvlNode<K> first )
421        {
422            this.first = first;
423            size++;
424        }
425    
426        
427        /**
428         * Set the last element of the tree
429         * 
430         * Note : this method is used by the deserialization method
431         *
432         * @param last the last element to be added
433         */
434        /* no protection */  void setLast( LinkedAvlNode<K> last )
435        {
436            this.last = last;
437        }
438    
439    
440        /* (non-Javadoc)
441         * @see org.apache.directory.server.core.avltree.AvlTree#getRoot()
442         */
443        public LinkedAvlNode<K> getRoot()
444        {
445            return root;
446        }
447        
448        
449        /* (non-Javadoc)
450         * @see org.apache.directory.server.core.avltree.AvlTree#getKeys()
451         */
452        public List<K> getKeys()
453        {
454            List<K> keys = new ArrayList<K>();
455            LinkedAvlNode<K> node = first;
456            
457            while( node != null )
458            {
459                keys.add( node.key );
460                node = node.next;
461            }
462            
463            return keys;
464        }
465    
466        /* (non-Javadoc)
467         * @see org.apache.directory.server.core.avltree.AvlTree#printTree()
468         */
469        public void printTree() 
470        {
471            if( isEmpty() )
472            {
473                System.out.println( "Tree is empty" );
474                return;
475            }
476            
477            getRoot().setDepth( 0 );
478    
479            System.out.println( getRoot() );
480            
481            visit( getRoot().getRight(), getRoot() );
482            
483            visit( getRoot().getLeft(), getRoot() );
484        }
485        
486    
487        /* (non-Javadoc)
488         * @see org.apache.directory.server.core.avltree.AvlTree#getFirst()
489         */
490        public LinkedAvlNode<K> getFirst()
491        {
492            return first;
493        }
494    
495        
496        /* (non-Javadoc)
497         * @see org.apache.directory.server.core.avltree.AvlTree#getLast()
498         */
499        public LinkedAvlNode<K> getLast()
500        {
501            return last;
502        }
503    
504        
505        /**
506         * Rotate the node left side once.
507         *
508         * @param node the LinkedAvlNode to be rotated
509         * @param parentNode parent LinkedAvlNode of node
510         */
511        private void rotateSingleLeft(LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode)
512        {
513            LinkedAvlNode<K> temp;
514            //------rotate single-left--------
515            
516            temp = node.right;
517            node.right = temp.left;
518            temp.left = node;
519            
520            if( node == root )
521            {
522              root = temp;  
523            }
524            else if( parentNode != null )
525            {
526                if( parentNode.left == node )
527                {
528                    parentNode.left = temp;
529                }
530                else if( parentNode.right == node )
531                {
532                    parentNode.right = temp;
533                }
534            }
535        }
536        
537        
538        /**
539         * Rotate the node right side once.
540         *
541         * @param node the LinkedAvlNode to be rotated
542         * @param parentNode parent LinkedAvlNode of node
543         */
544        private void rotateSingleRight(LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode)
545        {
546            LinkedAvlNode<K> temp;
547            //------rotate single-right--------
548            
549            temp = node.left;
550            node.left = temp.right;
551            temp.right = node;
552           
553            if( node == root )
554            {
555              root = temp;  
556            }
557            else if( parentNode != null )
558            {
559                if( parentNode.left == node )
560                {
561                    parentNode.left = temp;
562                }
563                else if( parentNode.right == node )
564                {
565                    parentNode.right = temp;
566                }
567            }
568            /*
569             when the 'parentNode' param is null then the node under rotation is a child of ROOT.
570             Most likely this condition executes when the root node is deleted and balancing is required.
571             */
572            else if( root != null )
573            {
574                if( root.left == node )
575                {
576                    root.left = temp;
577                }
578                // no need to check for right node
579            }
580        }
581            
582    
583        /**
584         * Detach a LinkedAvlNode from its parent
585         *
586         * @param node the LinkedAvlNode to be detached
587         * @param parentNode the parent LinkedAvlNode of the node
588         */
589        private void detachNodes(LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode)
590        {
591            if( parentNode != null )
592            {
593                if( node == parentNode.left )
594                {
595                    parentNode.left = node.left;
596                }
597                else if( node == parentNode.right )
598                {
599                    parentNode.right = node.left;
600                }
601            }
602        }
603    
604    
605        /**
606         * 
607         * Replace a LinkedAvlNode to be removed with a new existing LinkedAvlNode 
608         *
609         * @param deleteNode the LinkedAvlNode to be deleted
610         * @param replaceNode the LinkedAvlNode to replace the deleteNode
611         * @param parentNode the parent LinkedAvlNode of deleteNode
612         */
613        private void replaceNode(LinkedAvlNode<K> deleteNode, LinkedAvlNode<K> replaceNode, LinkedAvlNode<K> parentNode)
614        {
615            if( parentNode != null )
616            {
617                replaceNode.left = deleteNode.left;
618                
619                if( deleteNode == parentNode.left )
620                {
621                    parentNode.left = replaceNode;
622                }
623                else if( deleteNode == parentNode.right )
624                {
625                    parentNode.right = replaceNode;
626                }
627            }
628        }
629        
630        
631        /**
632         * 
633         * Find a LinkedAvlNode with the given key value in the tree starting from the startNode.
634         *
635         * @param key the key to find
636         * @param startNode starting node of a subtree/tree
637         * @param path the list to be filled with traversed nodes
638         * @return the list of traversed LinkedAvlNodes.
639         */
640        private List<LinkedAvlNode<K>> find( K key, LinkedAvlNode<K> startNode, List<LinkedAvlNode<K>> path )
641        {
642            int c;
643            
644            if( startNode == null )
645            {
646                return null;
647            }
648            
649            path.add( 0, startNode );
650            c = comparator.compare( key, startNode.key );
651            
652            if( c == 0 )
653            {
654                return path;
655            }
656            else if( c > 0 )
657            {
658                return find( key, startNode.right, path );
659            }
660            else if( c < 0 )
661            {
662                return find( key, startNode.left, path );
663            }
664            
665            return null;
666        }
667    
668    
669        /* (non-Javadoc)
670         * @see org.apache.directory.server.core.avltree.AvlTree#findGreater(K)
671         */
672        public LinkedAvlNode<K> findGreater( K key )
673        {
674            LinkedAvlNode<K> result = fetchNonNullNode( key, root, root);
675    
676            if( result == null )
677            {
678                return null;
679            }
680            else if( comparator.compare( key, result.key ) < 0 )
681            {
682                return result;
683            }
684    
685            return result.next;
686        }
687    
688    
689        /* (non-Javadoc)
690         * @see org.apache.directory.server.core.avltree.AvlTree#findGreaterOrEqual(K)
691         */
692        public LinkedAvlNode<K> findGreaterOrEqual( K key )
693        {
694            LinkedAvlNode<K> result = fetchNonNullNode( key, root, root);
695    
696            if( result == null )
697            {
698                return null;
699            }
700            else if( comparator.compare( key, result.key ) <= 0 )
701            {
702                return result;
703            }
704    
705            return result.next;
706        }
707    
708    
709        /* (non-Javadoc)
710         * @see org.apache.directory.server.core.avltree.AvlTree#findLess(K)
711         */
712        public LinkedAvlNode<K> findLess( K key )
713        {
714            LinkedAvlNode<K> result = fetchNonNullNode( key, root, root);
715    
716            if( result == null )
717            {
718                return null;
719            }
720            else if( comparator.compare( key, result.key ) > 0 )
721            {
722                return result;
723            }
724    
725            return result.previous;
726        }
727    
728    
729        /* (non-Javadoc)
730         * @see org.apache.directory.server.core.avltree.AvlTree#findLessOrEqual(K)
731         */
732        public LinkedAvlNode<K> findLessOrEqual( K key )
733        {
734            LinkedAvlNode<K> result = fetchNonNullNode( key, root, root);
735    
736            if( result == null )
737            {
738                return null;
739            }
740            else if( comparator.compare( key, result.key ) >= 0 )
741            {
742                return result;
743            }
744    
745            return result.previous;
746        }
747    
748    
749        /*
750         * This method returns the last visited non-null node in case if the node with the given key
751         * is not present. This method should not be used as general purpose lookup method.
752         * This is written to assist the findGreater, findLess methods. 
753         */
754        private LinkedAvlNode<K> fetchNonNullNode( K key, LinkedAvlNode<K> startNode, LinkedAvlNode<K> parent )
755        {
756            
757            if( startNode == null )
758            {
759                return parent;
760            }
761            
762            int c = comparator.compare( key, startNode.key );
763            
764            parent = startNode;
765    
766            if( c > 0 )
767            {
768                return fetchNonNullNode( key, startNode.right, parent );
769            }
770            else if( c < 0 )
771            {
772                return fetchNonNullNode( key, startNode.left, parent );
773            }
774            
775            return startNode;
776        }
777        
778        /* (non-Javadoc)
779         * @see org.apache.directory.server.core.avltree.AvlTree#find(K)
780         */
781        public LinkedAvlNode<K> find( K key )
782        {
783            return find( key, root);
784        }
785        
786    
787        private LinkedAvlNode<K> find( K key, LinkedAvlNode<K> startNode)
788        {
789            int c;
790            
791            if( startNode == null )
792            {
793                return null;
794            }
795            
796            c = comparator.compare( key, startNode.key );
797            
798            if( c > 0 )
799            {
800                startNode.isLeft = false;
801                return find( key, startNode.right );
802            }
803            else if( c < 0 )
804            {
805                startNode.isLeft = true;
806                return find( key, startNode.left );
807            }
808            
809            return startNode;
810        }
811        
812        
813        /**
814         * Find the LinkedAvlNode having the max key value in the tree starting from the startNode.
815         *
816         * @param startNode starting node of a subtree/tree
817         * @return the list of traversed LinkedAvlNodes.
818         */
819        private List<LinkedAvlNode<K>> findMax( LinkedAvlNode<K> startNode )
820        {
821            LinkedAvlNode<K> x = startNode;
822            LinkedAvlNode<K> y = null;
823            List<LinkedAvlNode<K>> path;
824            
825            if( x == null )
826            {
827                return null;
828            }
829            
830            while( x.right != null )
831            {
832                x.isLeft = false;
833                y = x;
834                x = x.right;
835            }
836            
837            path = new ArrayList<LinkedAvlNode<K>>(2);
838            path.add( x );
839            
840            if ( y != null )
841            {
842              path.add( y );  
843            }
844            
845            return path;
846        }
847    
848        
849        /**
850         * Find the LinkedAvlNode having the min key value in the tree starting from the startNode.
851         *
852         * @param startNode starting node of a subtree/tree
853         * @return the list of traversed LinkedAvlNodes.
854         */
855        private List<LinkedAvlNode<K>> findMin( LinkedAvlNode<K> startNode )
856        {
857            LinkedAvlNode<K> x = startNode;
858            LinkedAvlNode<K> y = null;
859            List<LinkedAvlNode<K>> path;
860           
861            if( x == null )
862            {
863                return null;
864            }
865           
866            while( x.left != null )
867            {
868                x.isLeft = true;
869                y = x;
870                x = x.left;
871            }
872            
873            path = new ArrayList<LinkedAvlNode<K>>(2);
874            path.add( x );
875            
876            if ( y != null )
877            {
878              path.add( y );  
879            }
880            
881            return path;
882        }
883       
884        
885        /**
886         * Get balance-factor of the given LinkedAvlNode.
887         *
888         * @param node a LinkedAvlNode 
889         * @return balance-factor of the node
890         */
891        private int getBalance( LinkedAvlNode<K> node )
892        {
893            if( node == null)
894            {
895                return 0;
896            }
897            
898            return node.getBalance();
899        }
900        
901        
902        private void visit( LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode ) 
903        {
904            if( node == null )
905            {
906                return;
907            }
908            
909            if( !node.isLeaf() )
910            {
911                node.setDepth( parentNode.getDepth() + 1 );
912            }
913            
914            for( int i=0; i < parentNode.getDepth(); i++ )
915            {
916                System.out.print( "|  " );
917            }
918    
919            String type = "";
920            if( node == parentNode.left )
921            {
922                type = "L";
923            }
924            else if( node == parentNode.right )
925            {
926                type = "R";
927            }
928            
929            System.out.println( "|--" + node + type );
930            
931            if ( node.getRight() != null )
932            {
933                visit( node.getRight(), node );
934            }
935            
936            if( node.getLeft() != null )
937            {
938                visit( node.getLeft(), node );
939            }
940        }
941    }