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}