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