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}