View Javadoc
1   /*
2    *  Licensed to the Apache Software Foundation (ASF) under one
3    *  or more contributor license agreements.  See the NOTICE file
4    *  distributed with this work for additional information
5    *  regarding copyright ownership.  The ASF licenses this file
6    *  to you under the Apache License, Version 2.0 (the
7    *  "License"); you may not use this file except in compliance
8    *  with the License.  You may obtain a copy of the License at
9    *
10   *    http://www.apache.org/licenses/LICENSE-2.0
11   *
12   *  Unless required by applicable law or agreed to in writing,
13   *  software distributed under the License is distributed on an
14   *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   *  KIND, either express or implied.  See the License for the
16   *  specific language governing permissions and limitations
17   *  under the License.
18   *
19   */
20  package org.apache.directory.api.ldap.util.tree;
21  
22  
23  import java.util.ArrayList;
24  import java.util.HashMap;
25  import java.util.List;
26  import java.util.Map;
27  
28  import org.apache.directory.api.ldap.model.exception.LdapException;
29  import org.apache.directory.api.ldap.model.exception.LdapInvalidDnException;
30  import org.apache.directory.api.ldap.model.exception.LdapUnwillingToPerformException;
31  import org.apache.directory.api.ldap.model.message.ResultCodeEnum;
32  import org.apache.directory.api.ldap.model.name.Dn;
33  import org.apache.directory.api.ldap.model.name.Rdn;
34  import org.slf4j.Logger;
35  import org.slf4j.LoggerFactory;
36  
37  
38  /**
39   * A class storing nodes in a tree designed to map DNs.<br/>
40   * Branch nodes in this tree refers to child nodes. Leaf nodes in the tree
41   * don't have any children. <br/>
42   * A node may contain a reference to an object whose suffix is the path through the
43   * nodes of the tree from the root. <br/>
44   * A node may also have no attached element.<br/>
45   * Each child node is referenced by a Rdn, and holds the full Dn corresponding to its position<br/>
46   *
47   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
48   * @param <N> The type of node we store
49   */
50  public class DnNode<N> implements Cloneable
51  {
52      /** The logger for this class */
53      private static final Logger LOG = LoggerFactory.getLogger( DnNode.class );
54  
55      /** The stored element */
56      private N nodeElement;
57  
58      /** The node's key */
59      private Rdn nodeRdn;
60  
61      /** The node's Dn */
62      private Dn nodeDn;
63  
64      /** The node's depth in the tree */
65      private int depth;
66  
67      /** The parent, if any */
68      private DnNode<N> parent;
69  
70      /** Stores the list of all the descendant */
71      private Map<Rdn, DnNode<N>> children;
72  
73  
74      //-------------------------------------------------------------------------
75      // Helper methods
76      //-------------------------------------------------------------------------
77      /**
78       * Check that the Dn is not null
79       */
80      private void checkDn( Dn dn ) throws LdapException
81      {
82          if ( ( dn == null ) || dn.isEmpty() )
83          {
84              String message = "Cannot process an empty Dn";
85              LOG.error( message );
86              throw new LdapUnwillingToPerformException( ResultCodeEnum.UNWILLING_TO_PERFORM, message );
87          }
88      }
89  
90  
91      /**
92       * Create a new DnNode, recursively creating all the intermediate nodes.
93       */
94      private DnNode<N> createNode( Dn dn, N element, int nbRdns ) throws LdapException
95      {
96          checkDn( dn );
97  
98          DnNode<N> rootNode = null;
99  
100         // No parent : add from the current position
101         for ( Rdn rdn : dn.getRdns() )
102         {
103             if ( nbRdns == 0 )
104             {
105                 break;
106             }
107 
108             if ( rootNode == null )
109             {
110                 // Create the new top node
111                 DnNode<N> node = new DnNode<N>( element );
112                 node.nodeRdn = rdn;
113                 node.nodeDn = dn;
114                 node.depth = dn.size() + depth;
115 
116                 rootNode = node;
117             }
118             else
119             {
120                 DnNode<N> node = new DnNode<N>();
121                 node.nodeRdn = rdn;
122                 node.nodeDn = rootNode.nodeDn.getParent();
123                 node.depth = node.nodeDn.size() + depth;
124                 rootNode.parent = node;
125                 node.children.put( rootNode.nodeRdn, rootNode );
126                 rootNode = node;
127             }
128 
129             nbRdns--;
130         }
131 
132         return rootNode;
133     }
134 
135 
136     /**
137      * Store the given element into the node
138      */
139     private synchronized void setElement( N element )
140     {
141         this.nodeElement = element;
142     }
143 
144 
145     //-------------------------------------------------------------------------
146     // Constructors
147     //-------------------------------------------------------------------------
148     /**
149      * Creates a new instance of DnNode.
150      */
151     public DnNode()
152     {
153         children = new HashMap<Rdn, DnNode<N>>();
154         nodeDn = Dn.EMPTY_DN;
155         nodeRdn = Rdn.EMPTY_RDN;
156     }
157 
158 
159     /**
160      * Creates a new instance of DnNode.
161      *
162      * @param element the element to store
163      */
164     public DnNode( N element )
165     {
166         this.nodeElement = element;
167         children = new HashMap<Rdn, DnNode<N>>();
168     }
169 
170 
171     /**
172      * Creates a new instance of DnNode.
173      *
174      * @param dn the node's Dn
175      * @param element the element to store
176      */
177     public DnNode( Dn dn, N element )
178     {
179         if ( ( dn == null ) || ( dn.isEmpty() ) )
180         {
181             children = new HashMap<Rdn, DnNode<N>>();
182             this.nodeDn = Dn.EMPTY_DN;
183 
184             return;
185         }
186 
187         try
188         {
189             DnNode<N> rootNode = createNode( dn, element, dn.size() );
190 
191             // Now copy back the created node into this
192             this.children = rootNode.children;
193             this.depth = rootNode.depth;
194             this.nodeDn = rootNode.nodeDn;
195             this.nodeElement = rootNode.nodeElement;
196             this.nodeRdn = rootNode.nodeRdn;
197             this.parent = null;
198         }
199         catch ( LdapException le )
200         {
201             // Special cas e: the Dn is empty, this is not allowed
202             throw new IllegalArgumentException( le.getMessage() );
203         }
204     }
205 
206 
207     /**
208      * Tells if the implementation is a leaf node. If it's a branch node
209      * then false is returned.
210      *
211      * @return <code>true</code> if the class is a leaf node, false otherwise.
212      */
213     public synchronized boolean isLeaf()
214     {
215         return !hasChildren();
216     }
217 
218 
219     /**
220      * Tells if the implementation is a leaf node. If it's a branch node
221      * then false is returned.
222      *
223      * @param dn The Dn we want to check
224      * @return <code>true</code> if this is a leaf node, false otherwise.
225      */
226     public synchronized boolean isLeaf( Dn dn )
227     {
228         DnNode<N> node = getNode( dn );
229 
230         if ( node == null )
231         {
232             return false;
233         }
234 
235         return node.children.size() == 0;
236     }
237 
238 
239     /**
240      * Returns the number of entries under this node. It includes
241      * the node itself, plus the number of all it children and descendants.
242      *
243      * @return The number of descendents
244      */
245     public synchronized int size()
246     {
247         // The node itself
248         int size = 1;
249 
250         // Iterate through the children if any
251         if ( children.size() != 0 )
252         {
253             for ( DnNode<N> node : children.values() )
254             {
255                 size += node.size();
256             }
257         }
258 
259         return size;
260     }
261 
262 
263     /**
264      * @return Return the stored element, if any
265      */
266     public synchronized N getElement()
267     {
268         return nodeElement;
269     }
270 
271 
272     /**
273      * @return Return the stored element, if any
274      * @param dn The Dn we want to get the element for
275      */
276     public synchronized N getElement( Dn dn )
277     {
278         DnNode<N> node = getNode( dn );
279 
280         if ( node == null )
281         {
282             return null;
283         }
284 
285         return node.nodeElement;
286     }
287 
288 
289     /**
290      * @return True if the Node stores an element. BranchNode may not hold any
291      * element.
292      */
293     public synchronized boolean hasElement()
294     {
295         return nodeElement != null;
296     }
297 
298 
299     /**
300      * @return True if the Node stores an element. BranchNode may not hold any
301      * element.
302      * @param dn The Dn we want to get the element for
303      */
304     public synchronized boolean hasElement( Dn dn )
305     {
306         DnNode<N> node = getNode( dn );
307 
308         if ( node == null )
309         {
310             return false;
311         }
312 
313         return node.nodeElement != null;
314     }
315 
316 
317     /**
318      * recursively check if the node has a descendant having an element
319      */
320     private synchronized boolean hasDescendantElement( DnNode<N> node )
321     {
322         if ( node == null )
323         {
324             return false;
325         }
326 
327         if ( node.hasElement() )
328         {
329             return true;
330         }
331 
332         for ( DnNode<N> child : node.getChildren().values() )
333         {
334             if ( hasDescendantElement( child ) )
335             {
336                 return true;
337             }
338         }
339 
340         // Nothing found ...
341         return false;
342     }
343 
344 
345     /**
346      * @return True if one of the node below the current node has one element, 
347      * False otherwise
348      * @param dn The Dn we want to get the element for
349      */
350     public synchronized boolean hasDescendantElement( Dn dn )
351     {
352         DnNode<N> node = getNode( dn );
353 
354         if ( node == null )
355         {
356             return false;
357         }
358 
359         // We must be at the right place in the tree
360         if ( node.getDn().size() != dn.size() )
361         {
362             return false;
363         }
364 
365         if ( node.hasChildren() )
366         {
367             for ( DnNode<N> child : node.getChildren().values() )
368             {
369                 if ( hasDescendantElement( child ) )
370                 {
371                     return true;
372                 }
373             }
374         }
375 
376         return false;
377     }
378 
379 
380     /**
381      * recursively get all the elements from nodes having an element
382      */
383     private synchronized void getDescendantElements( DnNode<N> node, List<N> descendants )
384     {
385         if ( node == null )
386         {
387             return;
388         }
389 
390         if ( node.hasElement() )
391         {
392             descendants.add( node.getElement() );
393 
394             // Stop here
395             return;
396         }
397 
398         for ( DnNode<N> child : node.getChildren().values() )
399         {
400             getDescendantElements( child, descendants );
401         }
402     }
403 
404 
405     /**
406      * @return True if one of the node below the current node has one element, 
407      * False otherwise
408      * @param dn The Dn we want to get the element for
409      */
410     public synchronized List<N> getDescendantElements( Dn dn )
411     {
412         List<N> descendants = new ArrayList<N>();
413 
414         DnNode<N> node = getNode( dn );
415 
416         if ( node == null )
417         {
418             return descendants;
419         }
420 
421         // We must be at the right place in the tree
422         if ( node.getDn().size() != dn.size() )
423         {
424             return descendants;
425         }
426 
427         if ( node.hasChildren() )
428         {
429             for ( DnNode<N> child : node.getChildren().values() )
430             {
431                 getDescendantElements( child, descendants );
432             }
433         }
434 
435         return descendants;
436     }
437 
438 
439     /**
440      * Tells if the current DnNode has some children or not
441      *
442      * @return <code>true</code> if the node has some children
443      */
444     public synchronized boolean hasChildren()
445     {
446         return ( children != null ) && children.size() != 0;
447     }
448 
449 
450     /**
451      * Tells if a node has some children or not.
452      *
453      * @param dn the node's Dn
454      * @return <code>true</code> if the node has some children
455      * @throws LdapException if the Dn is null or empty
456      */
457     public synchronized boolean hasChildren( Dn dn ) throws LdapException
458     {
459         checkDn( dn );
460 
461         DnNode<N> node = getNode( dn );
462 
463         return ( node != null ) && node.hasChildren();
464     }
465 
466 
467     /**
468      * @return The list of DnNode
469      */
470     public synchronized Map<Rdn, DnNode<N>> getChildren()
471     {
472         return children;
473     }
474 
475 
476     /**
477      * @return The parent DnNode, if any
478      */
479     public synchronized DnNode<N> getParent()
480     {
481         return parent;
482     }
483 
484 
485     /**
486      * @return True if the current DnNode has a parent
487      */
488     public synchronized boolean hasParent()
489     {
490         return parent != null;
491     }
492 
493 
494     /**
495      * Tells if there is a parent for a given Dn,. This parent should be a
496      * subset of the given dn.<br>
497      * For instance, if we have stored dc=acme, dc=org into the tree,
498      * the Dn: ou=example, dc=acme, dc=org will have a parent
499      * <br>For the Dn ou=apache, dc=org, there is no parent, so false will be returned.
500      *
501      * @param dn the normalized distinguished name to resolve to a parent
502      * @return true if there is a parent associated with the normalized dn
503      */
504     public synchronized boolean hasParent( Dn dn )
505     {
506         List<Rdn> rdns = dn.getRdns();
507 
508         DnNode<N> currentNode = this;
509         DnNode<N> parentNode = null;
510 
511         // Iterate through all the Rdn until we find the associated element
512         for ( int i = rdns.size() - 1; i >= 0; i-- )
513         {
514             Rdn rdn = rdns.get( i );
515 
516             if ( rdn.equals( currentNode.nodeRdn ) )
517             {
518                 parentNode = currentNode;
519             }
520             else if ( currentNode.hasChildren() )
521             {
522                 currentNode = currentNode.children.get( rdn );
523 
524                 if ( currentNode == null )
525                 {
526                     break;
527                 }
528 
529                 parentNode = currentNode;
530             }
531             else
532             {
533                 break;
534             }
535         }
536 
537         return ( parentNode != null );
538     }
539 
540 
541     /**
542      * Add a new node in the tree. The added node won't have any element.
543      *
544      * @param dn The node's Dn
545      * @return the corresponding node
546      * @throws LdapException if the Dn is null or empty
547      */
548     public synchronized DnNode<N> add( Dn dn ) throws LdapException
549     {
550         return add( dn, null );
551     }
552 
553 
554     /**
555      * Add a new node in the tree. We can't add a node if its Dn is empty. The
556      * added element is attached to the node, which is named by the Dn's Rdn.<br/>
557      *
558      * @param dn The node's Dn
559      * @param element The element to associate with this Node. Can be null.
560      * @return the corresponding node
561      * @throws LdapException if the Dn is null or empty
562      */
563     public synchronized DnNode<N> add( Dn dn, N element ) throws LdapException
564     {
565         checkDn( dn );
566 
567         // We first have to find the Node which will be the parent
568         DnNode<N> parentNode = getNode( dn );
569 
570         if ( parentNode == null )
571         {
572             // No parent : add a new node to the root
573             DnNode<N> childNode = createNode( dn, element, dn.size() );
574             childNode.parent = this;
575             children.put( childNode.nodeRdn, childNode );
576             
577             return childNode;
578         }
579         else
580         {
581             // We have a parent. Add the new node to the found parent
582             int nbRdns = dn.size() - parentNode.depth;
583 
584             if ( nbRdns == 0 )
585             {
586                 // That means the added Dn is already present. Check if it already has an element
587                 if ( parentNode.hasElement() )
588                 {
589                     String message = "Cannot add a node to a node already having an element";
590                     LOG.error( message );
591                     throw new LdapUnwillingToPerformException( ResultCodeEnum.UNWILLING_TO_PERFORM, message );
592                 }
593                 // We may try to add twice the same Dn, without any element
594                 else if ( element == null )
595                 {
596                     String message = "Cannot add a node with no element if it already exists";
597                     LOG.error( message );
598                     throw new LdapUnwillingToPerformException( ResultCodeEnum.UNWILLING_TO_PERFORM, message );
599                 }
600                 // All is fine : we are just injecting some data into an existing node
601                 else
602                 {
603                     parentNode.setElement( element );
604                     
605                     return parentNode;
606                 }
607             }
608             else
609             {
610                 DnNode<N> childNode = createNode( dn, element, nbRdns );
611 
612                 // done. now, add the newly created tree to the parent node
613                 childNode.parent = parentNode;
614                 parentNode.children.put( childNode.nodeRdn, childNode );
615 
616                 return childNode;
617             }
618         }
619     }
620 
621 
622     /**
623      * Removes a node from the tree.
624      *
625      * @param dn the node's Dn
626      * @throws LdapException if the Dn is null or empty
627      */
628     public synchronized void remove( Dn dn ) throws LdapException
629     {
630         checkDn( dn );
631 
632         // Find the parent first : we won't be able to remove
633         // a node if it's not present in the tree !
634         DnNode<N> parentNode = getNode( dn );
635 
636         if ( parentNode == null )
637         {
638             return;
639         }
640 
641         // Now, check that this parent has the same Dn than the one
642         // we gave and that there is no children
643         if ( ( dn.size() != parentNode.depth ) || parentNode.hasChildren() )
644         {
645             return;
646         }
647 
648         // Ok, no children, same Dn, let's remove what we can.
649         parentNode = parentNode.getParent();
650 
651         for ( Rdn rdn : dn.getRdns() )
652         {
653             parentNode.children.remove( rdn );
654 
655             if ( parentNode.children.size() > 0 )
656             {
657                 // We have to stop here, because the parent's node is shared with other Node.
658                 break;
659             }
660 
661             parentNode = parentNode.getParent();
662         }
663     }
664 
665 
666     /**
667      * Tells if the current DnBranchNode contains another node associated
668      * with an rdn.
669      *
670      * @param rdn The name we are looking for
671      * @return <code>true</code> if the tree instance contains this name
672      */
673     public synchronized boolean contains( Rdn rdn )
674     {
675         return children.containsKey( rdn );
676     }
677 
678 
679     /**
680      * Get's a child using an rdn string.
681      *
682      * @param rdn the rdn to use as the node key
683      * @return the child node corresponding to the rdn.
684      */
685     public synchronized DnNode<N> getChild( Rdn rdn )
686     {
687         if ( children.containsKey( rdn ) )
688         {
689             return children.get( rdn );
690         }
691 
692         return null;
693     }
694 
695 
696     /**
697      * @return The Node's Rdn
698      */
699     public synchronized Rdn getRdn()
700     {
701         return nodeRdn;
702     }
703 
704 
705     /**
706      * Get the Node for a given Dn, if present in the tree.<br>
707      * For instance, if we have stored dc=acme, dc=org into the tree,
708      * the Dn: ou=example, dc=acme, dc=org will have a parent, and
709      * dc=acme, dc=org will be returned.
710      * <br>For the Dn ou=apache, dc=org, there is no parent, so null will be returned.
711      *
712      * @param dn the normalized distinguished name to resolve to a parent
713      * @return the Node associated with the normalized dn
714      */
715     public synchronized DnNode<N> getNode( Dn dn )
716     {
717         List<Rdn> rdns = dn.getRdns();
718 
719         DnNode<N> currentNode = this;
720         DnNode<N> parentNode = null;
721 
722         // Iterate through all the Rdn until we find the associated partition
723         for ( int i = rdns.size() - 1; i >= 0; i-- )
724         {
725             Rdn rdn = rdns.get( i );
726 
727             if ( currentNode.hasChildren() )
728             {
729                 currentNode = currentNode.children.get( rdn );
730 
731                 if ( currentNode == null )
732                 {
733                     break;
734                 }
735 
736                 parentNode = currentNode;
737             }
738             else
739             {
740                 break;
741             }
742         }
743 
744         return parentNode;
745     }
746 
747 
748     /**
749      * Get the closest Node for a given Dn which has an element, if present in the tree.<br>
750      * For instance, if we have stored dc=acme, dc=org into the tree,
751      * the Dn: ou=example, dc=acme, dc=org will have a parent, and
752      * dc=acme, dc=org will be returned if it has an associated element.
753      * <br>For the Dn ou=apache, dc=org, there is no parent, so null will be returned.
754      *
755      * @param dn the normalized distinguished name to resolve to a parent
756      * @return the Node associated with the normalized dn
757      */
758     public synchronized boolean hasParentElement( Dn dn )
759     {
760         List<Rdn> rdns = dn.getRdns();
761 
762         DnNode<N> currentNode = this;
763         boolean hasElement = false;
764 
765         // Iterate through all the Rdn until we find the associated partition
766         for ( int i = rdns.size() - 1; i >= 0; i-- )
767         {
768             Rdn rdn = rdns.get( i );
769 
770             if ( currentNode.hasChildren() )
771             {
772                 currentNode = currentNode.children.get( rdn );
773 
774                 if ( currentNode == null )
775                 {
776                     break;
777                 }
778 
779                 if ( currentNode.hasElement() )
780                 {
781                     hasElement = true;
782                 }
783 
784                 parent = currentNode;
785             }
786             else
787             {
788                 break;
789             }
790         }
791 
792         return hasElement;
793     }
794 
795 
796     /**
797      * Get the closest Node for a given Dn which has an element, if present in the tree.<br>
798      * For instance, if we have stored dc=acme, dc=org into the tree,
799      * the Dn: ou=example, dc=acme, dc=org will have a parent, and
800      * dc=acme, dc=org will be returned if it has an associated element.
801      * <br>For the Dn ou=apache, dc=org, there is no parent, so null will be returned.
802      *
803      * @param dn the normalized distinguished name to resolve to a parent
804      * @return the Node associated with the normalized dn
805      */
806     public synchronized DnNode<N> getParentWithElement( Dn dn )
807     {
808         List<Rdn> rdns = dn.getRdns();
809 
810         DnNode<N> currentNode = this;
811         DnNode<N> element = null;
812 
813         // Iterate through all the Rdn until we find the associated partition
814         for ( int i = rdns.size() - 1; i >= 1; i-- )
815         {
816             Rdn rdn = rdns.get( i );
817 
818             if ( currentNode.hasChildren() )
819             {
820                 currentNode = currentNode.children.get( rdn );
821 
822                 if ( currentNode == null )
823                 {
824                     break;
825                 }
826 
827                 if ( currentNode.hasElement() )
828                 {
829                     element = currentNode;
830                 }
831 
832                 parent = currentNode;
833             }
834             else
835             {
836                 break;
837             }
838         }
839 
840         return element;
841     }
842 
843 
844     /**
845      * Get the closest Node for a given Dn which has an element, if present in the tree.<br>
846      * For instance, if we have stored dc=acme, dc=org into the tree,
847      * the Dn: ou=example, dc=acme, dc=org will have a parent, and
848      * dc=acme, dc=org will be returned if it has an associated element.
849      * <br>For the Dn ou=apache, dc=org, there is no parent, so null will be returned.
850      *
851      * @param dn the normalized distinguished name to resolve to a parent
852      * @return the Node associated with the normalized dn
853      */
854     public synchronized DnNode<N> getParentWithElement()
855     {
856         DnNode<N> currentNode = parent;
857 
858         while ( currentNode != null )
859         {
860             if ( currentNode.nodeElement != null )
861             {
862                 return currentNode;
863             }
864 
865             currentNode = currentNode.parent;
866         }
867 
868         return null;
869     }
870 
871 
872     /**
873      * rename the DnNode's Dn
874      * 
875      * @param newRdn the new Rdn of this node
876      * @throws LdapException
877      */
878     public synchronized void rename( Rdn newRdn ) throws LdapException
879     {
880         Dn temp = nodeDn.getParent();
881         temp = temp.add( newRdn );
882 
883         Rdn oldRdn = nodeRdn;
884 
885         nodeRdn = temp.getRdn();
886         nodeDn = temp;
887 
888         if ( parent != null )
889         {
890             parent.children.remove( oldRdn );
891             parent.children.put( nodeRdn, this );
892         }
893 
894         updateAfterModDn( nodeDn );
895     }
896 
897 
898     /**
899      * move the DnNode's Dn
900      *
901      * @param newParent the new parent Dn
902      * @throws LdapException
903      */
904     public synchronized void move( Dn newParent ) throws LdapException
905     {
906         DnNode<N> tmp = null;
907 
908         Dn tmpDn = null;
909 
910         // check if the new parent Dn is child of the parent
911         if ( newParent.isDescendantOf( parent.nodeDn ) )
912         {
913             tmp = parent;
914             tmpDn = parent.nodeDn;
915         }
916 
917         // if yes, then drill for the new parent node
918         if ( tmpDn != null )
919         {
920             int parentNodeSize = tmpDn.size();
921             int count = newParent.size() - parentNodeSize;
922 
923             while ( count-- > 0 )
924             {
925                 tmp = tmp.getChild( newParent.getRdn( parentNodeSize++ ) );
926             }
927         }
928 
929         // if not, we have to traverse all the way up to the 
930         // root node and then find the new parent node
931         if ( tmp == null )
932         {
933             tmp = this;
934             while ( tmp.parent != null )
935             {
936                 tmp = tmp.parent;
937             }
938 
939             tmp = tmp.getNode( newParent );
940         }
941 
942         nodeDn = newParent.add( nodeRdn );
943         updateAfterModDn( nodeDn );
944 
945         if ( parent != null )
946         {
947             parent.children.remove( nodeRdn );
948         }
949 
950         parent = tmp;
951         parent.children.put( nodeRdn, this );
952     }
953 
954 
955     /**
956      * update the children's Dn based on the new parent Dn created
957      * after a rename or move operation
958      * 
959      * @param newParentDn
960      */
961     private synchronized void updateAfterModDn( Dn newParentDn ) throws LdapInvalidDnException
962     {
963         if ( children != null )
964         {
965             for ( DnNode<N> child : children.values() )
966             {
967                 child.nodeDn = newParentDn.add( child.nodeRdn );
968                 child.updateAfterModDn( child.nodeDn );
969             }
970         }
971     }
972 
973 
974     /**
975      * {@inheritDoc}
976      */
977     public synchronized DnNode<N> clone()
978     {
979         DnNode<N> clonedDnNode = new DnNode<N>();
980 
981         clonedDnNode.nodeElement = nodeElement;
982         clonedDnNode.depth = depth;
983         clonedDnNode.parent = parent;
984         clonedDnNode.nodeRdn = nodeRdn;
985         clonedDnNode.nodeDn = nodeDn;
986 
987         for ( DnNode<N> node : children.values() )
988         {
989             clonedDnNode.children.put( node.getRdn(), node.clone() );
990         }
991 
992         return clonedDnNode;
993     }
994 
995 
996     private String toString( String tabs )
997     {
998         if ( nodeRdn == null )
999         {
1000             return tabs;
1001         }
1002 
1003         StringBuilder sb = new StringBuilder();
1004         sb.append( tabs );
1005 
1006         boolean hasChildren = hasChildren();
1007 
1008         if ( isLeaf() )
1009         {
1010             sb.append( "Leaf[" ).append( nodeDn ).append( "]: " ).append( "'" ).append( nodeElement ).append( "'" );
1011             return sb.toString();
1012         }
1013 
1014         sb.append( "Branch[" ).append( nodeDn ).append( "]: " );
1015 
1016         if ( nodeElement != null )
1017         {
1018             sb.append( "'" ).append( nodeElement ).append( "'" );
1019         }
1020 
1021         tabs += "    ";
1022 
1023         sb.append( '\n' );
1024 
1025         boolean isFirst = true;
1026 
1027         if ( hasChildren )
1028         {
1029             for ( Rdn rdn : children.keySet() )
1030             {
1031                 if ( isFirst )
1032                 {
1033                     isFirst = false;
1034                 }
1035                 else
1036                 {
1037                     sb.append( "\n" );
1038                 }
1039 
1040                 DnNode<N> child = children.get( rdn );
1041 
1042                 sb.append( child.toString( tabs ) );
1043             }
1044         }
1045 
1046         return sb.toString();
1047     }
1048 
1049 
1050     /**
1051      * {@inheritDoc}
1052      */
1053     public String toString()
1054     {
1055         return toString( "" );
1056     }
1057 
1058 
1059     /**
1060      * @return the dn
1061      */
1062     public synchronized Dn getDn()
1063     {
1064         return nodeDn;
1065     }
1066 }