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 }