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 }