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>
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      // Constructors
76      //-------------------------------------------------------------------------
77      /**
78       * Creates a new instance of DnNode.
79       */
80      public DnNode()
81      {
82          children = new HashMap<Rdn, DnNode<N>>();
83          nodeDn = Dn.EMPTY_DN;
84          nodeRdn = Rdn.EMPTY_RDN;
85      }
86  
87  
88      /**
89       * Creates a new instance of DnNode.
90       *
91       * @param element the element to store
92       */
93      public DnNode( N element )
94      {
95          this.nodeElement = element;
96          children = new HashMap<Rdn, DnNode<N>>();
97      }
98  
99  
100     /**
101      * Creates a new instance of DnNode.
102      *
103      * @param dn the node's Dn
104      * @param element the element to store
105      */
106     public DnNode( Dn dn, N element )
107     {
108         if ( ( dn == null ) || ( dn.isEmpty() ) )
109         {
110             children = new HashMap<Rdn, DnNode<N>>();
111             this.nodeDn = Dn.EMPTY_DN;
112 
113             return;
114         }
115 
116         try
117         {
118             DnNode<N> rootNode = createNode( dn, element, dn.size() );
119 
120             // Now copy back the created node into this
121             this.children = rootNode.children;
122             this.depth = rootNode.depth;
123             this.nodeDn = rootNode.nodeDn;
124             this.nodeElement = rootNode.nodeElement;
125             this.nodeRdn = rootNode.nodeRdn;
126             this.parent = null;
127         }
128         catch ( LdapException le )
129         {
130             // Special cas e: the Dn is empty, this is not allowed
131             throw new IllegalArgumentException( le.getMessage(), le );
132         }
133     }
134 
135 
136     //-------------------------------------------------------------------------
137     // Helper methods
138     //-------------------------------------------------------------------------
139     /**
140      * Check that the Dn is not null
141      */
142     private void checkDn( Dn dn ) throws LdapException
143     {
144         if ( ( dn == null ) || dn.isEmpty() )
145         {
146             String message = "Cannot process an empty Dn";
147             LOG.error( message );
148             throw new LdapUnwillingToPerformException( ResultCodeEnum.UNWILLING_TO_PERFORM, message );
149         }
150     }
151 
152 
153     /**
154      * Create a new DnNode, recursively creating all the intermediate nodes.
155      */
156     private DnNode<N> createNode( Dn dn, N element, int nbRdns ) throws LdapException
157     {
158         checkDn( dn );
159 
160         DnNode<N> rootNode = null;
161 
162         // No parent : add from the current position
163         for ( Rdn rdn : dn.getRdns() )
164         {
165             if ( nbRdns == 0 )
166             {
167                 break;
168             }
169 
170             if ( rootNode == null )
171             {
172                 // Create the new top node
173                 DnNode<N> node = new DnNode<>( element );
174                 node.nodeRdn = rdn;
175                 node.nodeDn = dn;
176                 node.depth = dn.size() + depth;
177 
178                 rootNode = node;
179             }
180             else
181             {
182                 DnNode<N> node = new DnNode<>();
183                 node.nodeRdn = rdn;
184                 node.nodeDn = rootNode.nodeDn.getParent();
185                 node.depth = node.nodeDn.size() + depth;
186                 rootNode.parent = node;
187                 node.children.put( rootNode.nodeRdn, rootNode );
188                 rootNode = node;
189             }
190 
191             nbRdns--;
192         }
193 
194         return rootNode;
195     }
196 
197 
198     /**
199      * Store the given element into the node
200      */
201     private synchronized void setElement( N element )
202     {
203         this.nodeElement = element;
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<>();
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      * @return the Node associated with the normalized dn
852      */
853     public synchronized DnNode<N> getParentWithElement()
854     {
855         DnNode<N> currentNode = parent;
856 
857         while ( currentNode != null )
858         {
859             if ( currentNode.nodeElement != null )
860             {
861                 return currentNode;
862             }
863 
864             currentNode = currentNode.parent;
865         }
866 
867         return null;
868     }
869 
870 
871     /**
872      * rename the DnNode's Dn
873      * 
874      * @param newRdn the new Rdn of this node
875      * @throws LdapException If the rename failed
876      */
877     public synchronized void rename( Rdn newRdn ) throws LdapException
878     {
879         Dn temp = nodeDn.getParent();
880         temp = temp.add( newRdn );
881 
882         Rdn oldRdn = nodeRdn;
883 
884         nodeRdn = temp.getRdn();
885         nodeDn = temp;
886 
887         if ( parent != null )
888         {
889             parent.children.remove( oldRdn );
890             parent.children.put( nodeRdn, this );
891         }
892 
893         updateAfterModDn( nodeDn );
894     }
895 
896 
897     /**
898      * move the DnNode's Dn
899      *
900      * @param newParent the new parent Dn
901      * @throws LdapException If the move failed
902      */
903     public synchronized void move( Dn newParent ) throws LdapException
904     {
905         DnNode<N> tmp = null;
906 
907         Dn tmpDn = null;
908 
909         // check if the new parent Dn is child of the parent
910         if ( newParent.isDescendantOf( parent.nodeDn ) )
911         {
912             tmp = parent;
913             tmpDn = parent.nodeDn;
914         }
915 
916         // if yes, then drill for the new parent node
917         if ( tmpDn != null )
918         {
919             int parentNodeSize = tmpDn.size();
920             int count = newParent.size() - parentNodeSize;
921 
922             while ( count-- > 0 )
923             {
924                 tmp = tmp.getChild( newParent.getRdn( parentNodeSize++ ) );
925             }
926         }
927 
928         // if not, we have to traverse all the way up to the 
929         // root node and then find the new parent node
930         if ( tmp == null )
931         {
932             tmp = this;
933             while ( tmp.parent != null )
934             {
935                 tmp = tmp.parent;
936             }
937 
938             tmp = tmp.getNode( newParent );
939         }
940 
941         nodeDn = newParent.add( nodeRdn );
942         updateAfterModDn( nodeDn );
943 
944         if ( parent != null )
945         {
946             parent.children.remove( nodeRdn );
947         }
948 
949         parent = tmp;
950         parent.children.put( nodeRdn, this );
951     }
952 
953 
954     /**
955      * update the children's Dn based on the new parent Dn created
956      * after a rename or move operation
957      * 
958      * @param newParentDn
959      */
960     private synchronized void updateAfterModDn( Dn newParentDn ) throws LdapInvalidDnException
961     {
962         if ( children != null )
963         {
964             for ( DnNode<N> child : children.values() )
965             {
966                 child.nodeDn = newParentDn.add( child.nodeRdn );
967                 child.updateAfterModDn( child.nodeDn );
968             }
969         }
970     }
971 
972 
973     private String toString( String tabs )
974     {
975         if ( nodeRdn == null )
976         {
977             return tabs;
978         }
979 
980         StringBuilder sb = new StringBuilder();
981         sb.append( tabs );
982 
983         boolean hasChildren = hasChildren();
984 
985         if ( isLeaf() )
986         {
987             sb.append( "Leaf[" ).append( nodeDn ).append( "]: " ).append( "'" ).append( nodeElement ).append( "'" );
988             return sb.toString();
989         }
990 
991         sb.append( "Branch[" ).append( nodeDn ).append( "]: " );
992 
993         if ( nodeElement != null )
994         {
995             sb.append( "'" ).append( nodeElement ).append( "'" );
996         }
997 
998         tabs += "    ";
999 
1000         sb.append( '\n' );
1001 
1002         boolean isFirst = true;
1003 
1004         if ( hasChildren )
1005         {
1006             for ( Map.Entry<Rdn, DnNode<N>> entry : children.entrySet() )
1007             {
1008                 if ( isFirst )
1009                 {
1010                     isFirst = false;
1011                 }
1012                 else
1013                 {
1014                     sb.append( "\n" );
1015                 }
1016 
1017                 DnNode<N> child = entry.getValue();
1018 
1019                 sb.append( child.toString( tabs ) );
1020             }
1021         }
1022 
1023         return sb.toString();
1024     }
1025 
1026 
1027     /**
1028      * {@inheritDoc}
1029      */
1030     @Override
1031     public String toString()
1032     {
1033         return toString( "" );
1034     }
1035 
1036 
1037     /**
1038      * @return the dn
1039      */
1040     public synchronized Dn getDn()
1041     {
1042         return nodeDn;
1043     }
1044 }