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