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