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    /**
024     * A linked AVL tree node.
025     *
026     * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
027     * @version $Rev$, $Date$
028     */
029    public class LinkedAvlNode<T> 
030    {
031        /** The data stored in the node */
032        T key;
033        
034        /** The left child */
035        LinkedAvlNode<T> left;
036        
037        /** The right child */
038        LinkedAvlNode<T> right;
039        
040        /** The next node, superior to the current node */
041        LinkedAvlNode<T> next;
042    
043        /** The previous node, inferior to the current node */
044        LinkedAvlNode<T> previous;
045        
046        transient int depth;
047        transient int index;
048        
049        boolean isLeft;
050        transient int height = 1;
051        
052        
053        /**
054         * Creates a new instance of LinkedAvlNode, containing a given value.
055         *
056         * @param theKey the stored value on the topmost node
057         */
058        public LinkedAvlNode( T theKey )
059        {
060            key = theKey;
061            left = null;
062            right = null;
063        }
064    
065    
066        public void setLeft( LinkedAvlNode<T> left )
067        {
068            this.left = left;
069        }
070    
071    
072        public void setRight( LinkedAvlNode<T> right )
073        {
074            this.right = right;
075        }
076    
077    
078        public LinkedAvlNode<T> getNext()
079        {
080            return next;
081        }
082    
083    
084        public LinkedAvlNode<T> getPrevious()
085        {
086            return previous;
087        }
088    
089    
090        public LinkedAvlNode<T> getLeft() {
091            return left;
092        }
093    
094    
095        public LinkedAvlNode<T> getRight() {
096            return right;
097        }
098    
099        public T getKey() {
100            return key;
101        }
102    
103        public boolean isLeaf()
104        {
105            return ( right == null && left == null );
106        }
107        
108        public int getDepth() {
109            return depth;
110        }
111    
112        public void setDepth( int depth ) {
113            this.depth = depth;
114        }
115    
116        public int getHeight()
117        {
118            return height;
119        }
120        
121        
122       public void setNext( LinkedAvlNode<T> next )
123       {
124          this.next = next;
125       }
126    
127       
128       public void setPrevious( LinkedAvlNode<T> previous )
129       {
130          this.previous = previous;
131       }    
132       
133       
134        public int computeHeight()
135        {
136    
137            if(right == null && left == null)
138            {
139                height = 1;
140                return height;
141            }
142            
143            int lh,rh;
144            
145            if( isLeft )
146            {
147                lh = ( left == null ? -1 : left.computeHeight() );
148                rh = ( right == null ? -1 : right.getHeight() );
149            }
150            else 
151            {
152                rh = ( right == null ? -1 : right.computeHeight() );
153                lh = ( left == null ? -1 : left.getHeight() );
154            }
155            
156            height = 1 + Math.max( lh, rh );
157            
158            return height;
159        }
160        
161        public int getBalance()
162        {
163            int lh = ( left == null ? 0 : left.computeHeight() );
164            int rh = ( right == null ? 0 : right.computeHeight() );
165            
166            return ( rh - lh );
167        }
168    
169        public int getIndex()
170        {
171          return index;
172        }
173    
174        public void setIndex(int index)
175        {
176            this.index = index;
177        }
178    
179    
180        @Override
181        public String toString() {
182            return "[" + key + "]";
183        }
184        
185    }