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.shared.ldap.util.tree; 021 022 023 import java.util.HashMap; 024 import java.util.List; 025 import java.util.Map; 026 027 import org.apache.directory.shared.i18n.I18n; 028 import org.apache.directory.shared.ldap.exception.LdapException; 029 import org.apache.directory.shared.ldap.exception.LdapUnwillingToPerformException; 030 import org.apache.directory.shared.ldap.message.ResultCodeEnum; 031 import org.apache.directory.shared.ldap.name.DN; 032 import org.apache.directory.shared.ldap.name.RDN; 033 import org.slf4j.Logger; 034 import org.slf4j.LoggerFactory; 035 036 037 /** 038 * 039 * The Hierarchical Container holds elements ordered by their DN. 040 * <br/> 041 * We can see them as directories, where the leaves are the files. 042 * <br/> 043 * This class is *not* thread safe 044 * 045 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 046 */ 047 public class DnBranchNode<N> implements DnNode<N> 048 { 049 /** The logger for this class */ 050 private static final Logger LOG = LoggerFactory.getLogger( DnBranchNode.class ); 051 052 /** Stores the list of all the descendant */ 053 private Map<String, DnNode<N>> children; 054 055 /** Stores the number of descendents */ 056 private int size; 057 058 /** 059 * Creates a new instance of a DnBranchNode. 060 */ 061 public DnBranchNode() 062 { 063 children = new HashMap<String, DnNode<N>>(3); 064 size = 0; 065 } 066 067 068 /** 069 * @see DnNode#isLeaf() 070 */ 071 public boolean isLeaf() 072 { 073 return false; 074 } 075 076 077 /** 078 * Recursively adds new nodes to the element lookup tree data structure. 079 * When called it will add an element to the tree in the appropriate leaf 080 * node position based on the DN passed in as an argument. 081 * 082 * @param current The current node having an element added to it 083 * @param dn The DN associated with the added element 084 * @param index The index of the current RDN being processed 085 * @param element The associated element to add as a tree node 086 * @return The modified tree structure. 087 */ 088 private DnNode<N> recursivelyAddElement( DnBranchNode<N> current, DN dn, int index, N element ) throws LdapException 089 { 090 String rdnAtIndex = dn.getRdn( index ).getNormName(); 091 092 if ( index == dn.size() - 1 ) 093 { 094 if ( !current.contains( rdnAtIndex ) ) 095 { 096 return current.addNode( rdnAtIndex, new DnLeafNode<N>( element ) ); 097 } 098 else 099 { 100 return null; 101 } 102 } 103 else 104 { 105 DnNode<N> newNode = ((DnBranchNode<N>)current).getChild( rdnAtIndex ); 106 107 if ( newNode instanceof DnLeafNode ) 108 { 109 String message = I18n.err( I18n.ERR_04334 ); 110 LOG.error( message ); 111 throw new LdapUnwillingToPerformException( ResultCodeEnum.UNWILLING_TO_PERFORM, message ); 112 } 113 114 if ( newNode == null ) 115 { 116 newNode = new DnBranchNode<N>(); 117 } 118 119 DnNode<N> child = recursivelyAddElement( (DnBranchNode<N>)newNode, dn, index + 1, element ); 120 121 if ( child != null ) 122 { 123 return current.addNode( rdnAtIndex, child ); 124 } 125 else 126 { 127 return null; 128 } 129 } 130 } 131 132 133 /** 134 * Directly adds a new child DnNode to the current DnBranchNode. 135 * 136 * @param rdn The rdn of the child node to add 137 * @param child The child node to add 138 * @return The modified branch node after the insertion 139 */ 140 public DnNode<N> addNode( String rdn, DnNode<N> child ) 141 { 142 children.put( rdn, child ); 143 size++; 144 return this; 145 } 146 147 148 /** 149 * Tells if the current DnBranchNode contains another node associated 150 * with an rdn. 151 * 152 * @param rdn The name we are looking for 153 * @return <code>true</code> if the tree instance contains this name 154 */ 155 public boolean contains( String rdn ) 156 { 157 return children.containsKey( rdn ); 158 } 159 160 161 /** 162 * Get's a child using an rdn string. 163 * 164 * @param rdn the rdn to use as the node key 165 * @return the child node corresponding to the rdn. 166 */ 167 public DnNode<N> getChild( String rdn ) 168 { 169 if ( children.containsKey( rdn ) ) 170 { 171 return children.get( rdn ); 172 } 173 174 return null; 175 } 176 177 178 /** 179 * Get the parent of a given DN, if present in the tree. This parent should be a 180 * subset of the given dn.<br> 181 * For instance, if we have stored dc=acme, dc=org into the tree, 182 * the DN: ou=example, dc=acme, dc=org will have a parent, and 183 * dc=acme, dc=org will be returned. 184 * <br>For the DN ou=apache, dc=org, there is no parent, so null will be returned. 185 * 186 * 187 * @param dn the normalized distinguished name to resolve to a parent 188 * @return the parent associated with the normalized dn 189 */ 190 public N getParentElement( DN dn ) 191 { 192 List<RDN> rdns = dn.getRdns(); 193 194 // This is synchronized so that we can't read the 195 // partitionList when it is modified. 196 synchronized ( this ) 197 { 198 DnNode<N> currentNode = this; 199 200 // Iterate through all the RDN until we find the associated partition 201 for ( int i = rdns.size() - 1; i >= 0; i-- ) 202 { 203 String rdnStr = rdns.get( i ).getNormName(); 204 205 if ( currentNode == null ) 206 { 207 break; 208 } 209 210 if ( currentNode instanceof DnLeafNode ) 211 { 212 return ( ( DnLeafNode<N> ) currentNode ).getElement(); 213 } 214 215 DnBranchNode<N> currentBranch = ( DnBranchNode<N> ) currentNode; 216 217 if ( currentBranch.contains( rdnStr ) ) 218 { 219 currentNode = currentBranch.getChild( rdnStr ); 220 221 if ( currentNode instanceof DnLeafNode ) 222 { 223 return ( ( DnLeafNode<N> ) currentNode ).getElement(); 224 } 225 } 226 } 227 } 228 229 return null; 230 } 231 232 233 /** 234 * Tells if the DN contains a parent in the tree. This parent should be a 235 * subset of the given dn.<br> 236 * For instance, if we have stored dc=acme, dc=org into the tree, 237 * the DN: ou=example, dc=acme, dc=org will have a parent. 238 * 239 * @param dn the normalized distinguished name to resolve to a parent 240 * @return the parent associated with the normalized dn 241 */ 242 public boolean hasParentElement( DN dn ) 243 { 244 List<RDN> rdns = dn.getRdns(); 245 246 // This is synchronized so that we can't read the 247 // partitionList when it is modified. 248 synchronized ( this ) 249 { 250 DnNode<N> currentNode = this; 251 252 // Iterate through all the RDN until we find the associated partition 253 for ( int i = rdns.size() - 1; i >= 0; i-- ) 254 { 255 String rdnStr = rdns.get( i ).getNormName(); 256 257 if ( currentNode == null ) 258 { 259 return false; 260 } 261 262 if ( currentNode instanceof DnLeafNode ) 263 { 264 return true; 265 } 266 267 DnBranchNode<N> currentBranch = ( DnBranchNode<N> ) currentNode; 268 269 if ( currentBranch.contains( rdnStr ) ) 270 { 271 currentNode = currentBranch.getChild( rdnStr ); 272 273 if ( currentNode instanceof DnLeafNode ) 274 { 275 return true; 276 } 277 } 278 } 279 } 280 281 return false; 282 } 283 284 285 /** 286 * Tells if a branchNode has some children or not 287 * 288 * @return <code>true</code> if the node has some children 289 */ 290 public boolean hasChildren() 291 { 292 return children.size() != 0; 293 } 294 295 296 /** 297 * Removes an element from the tree. 298 * 299 * @param element The element to remove 300 */ 301 private boolean recursivelyRemoveElement( DnBranchNode<N> currentNode, N element ) 302 { 303 // It might be a leaf 304 for ( String key: currentNode.children.keySet() ) 305 { 306 DnNode<N> child = currentNode.children.get( key ); 307 308 if ( child instanceof DnLeafNode ) 309 { 310 if ( ((DnLeafNode<N>)child).getElement().equals( element ) ) 311 { 312 // found ! Remove it from the children 313 currentNode.children.remove( key ); 314 currentNode.size--; 315 return true; 316 } 317 } 318 else 319 { 320 if ( recursivelyRemoveElement( (DnBranchNode<N>)child, element ) ) 321 { 322 if ( ((DnBranchNode<N>)child).children.size() == 0 ) 323 { 324 // If there are no more children, we can remove the node 325 currentNode.children.remove( key ); 326 currentNode.size--; 327 } 328 else 329 { 330 currentNode.size--; 331 } 332 333 return true; 334 } 335 } 336 } 337 338 339 return false; 340 } 341 342 343 /** 344 * 345 * TODO add. 346 * 347 * @param dn 348 * @param element 349 * @throws NamingException 350 */ 351 public void add( DN dn, N element ) throws LdapException 352 { 353 recursivelyAddElement( this, dn, 0, element ); 354 } 355 356 357 /** 358 * Removes an element from the tree. 359 * 360 * @param element The element to remove 361 */ 362 public void remove( N element ) 363 { 364 DnBranchNode<N> currentNode = this; 365 366 if ( currentNode.hasChildren() ) 367 { 368 recursivelyRemoveElement( currentNode, element ); 369 } 370 } 371 372 373 /** 374 * {@inheritDoc} 375 */ 376 public int size() 377 { 378 return size; 379 } 380 381 382 /** 383 * @see Object#toString() 384 */ 385 public String toString() 386 { 387 StringBuilder sb = new StringBuilder(); 388 sb.append( "{" ); 389 boolean isFirst = true; 390 391 for ( String key:children.keySet() ) 392 { 393 if ( isFirst ) 394 { 395 isFirst = false; 396 } 397 else 398 { 399 sb.append( ", " ); 400 } 401 402 DnNode<N> child = children.get( key ); 403 404 if ( child instanceof DnBranchNode ) 405 { 406 sb.append( "Branch[" ).append( key ).append( "]: ").append( child ); 407 } 408 else 409 { 410 sb.append( "Leaf: " ).append( "'" ).append( child ).append( "'" ); 411 } 412 } 413 414 sb.append( "}" ); 415 return sb.toString(); 416 } 417 }