View Javadoc

1   /*
2    *   Licensed to the Apache Software Foundation (ASF) under one
3    *   or more contributor license agreements.  See the NOTICE file
4    *   distributed with this work for additional information
5    *   regarding copyright ownership.  The ASF licenses this file
6    *   to you under the Apache License, Version 2.0 (the
7    *   "License"); you may not use this file except in compliance
8    *   with the License.  You may obtain a copy of the License at
9    *
10   *     http://www.apache.org/licenses/LICENSE-2.0
11   *
12   *   Unless required by applicable law or agreed to in writing,
13   *   software distributed under the License is distributed on an
14   *   "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   *   KIND, either express or implied.  See the License for the
16   *   specific language governing permissions and limitations
17   *   under the License.
18   *
19   */
20  package org.apache.directory.server.core.avltree;
21  
22  
23  /**
24   * A linked AVL tree node.
25   *
26   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
27   * @version $Rev$, $Date$
28   */
29  public class LinkedAvlNode<T> 
30  {
31      /** The data stored in the node */
32      T key;
33      
34      /** The left child */
35      LinkedAvlNode<T> left;
36      
37      /** The right child */
38      LinkedAvlNode<T> right;
39      
40      /** The next node, superior to the current node */
41      LinkedAvlNode<T> next;
42  
43      /** The previous node, inferior to the current node */
44      LinkedAvlNode<T> previous;
45      
46      transient int depth;
47      transient int index;
48      
49      boolean isLeft;
50      transient int height = 1;
51      
52      
53      /**
54       * Creates a new instance of LinkedAvlNode, containing a given value.
55       *
56       * @param theKey the stored value on the topmost node
57       */
58      public LinkedAvlNode( T theKey )
59      {
60          key = theKey;
61          left = null;
62          right = null;
63      }
64  
65  
66  	public void setLeft( LinkedAvlNode<T> left )
67      {
68          this.left = left;
69      }
70  
71  
72      public void setRight( LinkedAvlNode<T> right )
73      {
74          this.right = right;
75      }
76  
77  
78      public LinkedAvlNode<T> getNext()
79      {
80          return next;
81      }
82  
83  
84      public LinkedAvlNode<T> getPrevious()
85      {
86          return previous;
87      }
88  
89  
90      public LinkedAvlNode<T> getLeft() {
91  		return left;
92  	}
93  
94  
95  	public LinkedAvlNode<T> getRight() {
96  		return right;
97  	}
98  
99  	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 }