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 */
020package 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 */
028public class LinkedAvlMapNode<K, V>
029{
030    /** The key stored in the node */
031    K key;
032
033    /** the value stored in the node */
034    SingletonOrOrderedSet<V> value;
035
036    /** The left child */
037    LinkedAvlMapNode<K, V> left;
038
039    /** The right child */
040    LinkedAvlMapNode<K, V> right;
041
042    /** The next node, superior to the current node */
043    LinkedAvlMapNode<K, V> next;
044
045    /** The previous node, inferior to the current node */
046    LinkedAvlMapNode<K, V> previous;
047
048    int depth;
049    int index;
050
051    boolean isLeft;
052    int height = 1;
053
054
055    /**
056     * Creates a new instance of LinkedAvlNode, containing a given value.
057     *
058     * @param theKey the stored key on the topmost node
059     * @param theValue The stored value on the topmost node
060     */
061    public LinkedAvlMapNode( K theKey, V theValue )
062    {
063        key = theKey;
064        value = new SingletonOrOrderedSet<>( 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}