1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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
40
41
42
43
44
45
46
47
48
49
50 public class DnNode<N> implements Cloneable
51 {
52
53 private static final Logger LOG = LoggerFactory.getLogger( DnNode.class );
54
55
56 private N nodeElement;
57
58
59 private Rdn nodeRdn;
60
61
62 private Dn nodeDn;
63
64
65 private int depth;
66
67
68 private DnNode<N> parent;
69
70
71 private Map<Rdn, DnNode<N>> children;
72
73
74
75
76
77
78
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
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
101 for ( Rdn rdn : dn.getRdns() )
102 {
103 if ( nbRdns == 0 )
104 {
105 break;
106 }
107
108 if ( rootNode == null )
109 {
110
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
138
139 private synchronized void setElement( N element )
140 {
141 this.nodeElement = element;
142 }
143
144
145
146
147
148
149
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
161
162
163
164 public DnNode( N element )
165 {
166 this.nodeElement = element;
167 children = new HashMap<Rdn, DnNode<N>>();
168 }
169
170
171
172
173
174
175
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
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
202 throw new IllegalArgumentException( le.getMessage() );
203 }
204 }
205
206
207
208
209
210
211
212
213 public synchronized boolean isLeaf()
214 {
215 return !hasChildren();
216 }
217
218
219
220
221
222
223
224
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
241
242
243
244
245 public synchronized int size()
246 {
247
248 int size = 1;
249
250
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
265
266 public synchronized N getElement()
267 {
268 return nodeElement;
269 }
270
271
272
273
274
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
291
292
293 public synchronized boolean hasElement()
294 {
295 return nodeElement != null;
296 }
297
298
299
300
301
302
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
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
341 return false;
342 }
343
344
345
346
347
348
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
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
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
395 return;
396 }
397
398 for ( DnNode<N> child : node.getChildren().values() )
399 {
400 getDescendantElements( child, descendants );
401 }
402 }
403
404
405
406
407
408
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
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
441
442
443
444 public synchronized boolean hasChildren()
445 {
446 return ( children != null ) && children.size() != 0;
447 }
448
449
450
451
452
453
454
455
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
469
470 public synchronized Map<Rdn, DnNode<N>> getChildren()
471 {
472 return children;
473 }
474
475
476
477
478
479 public synchronized DnNode<N> getParent()
480 {
481 return parent;
482 }
483
484
485
486
487
488 public synchronized boolean hasParent()
489 {
490 return parent != null;
491 }
492
493
494
495
496
497
498
499
500
501
502
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
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
543
544
545
546
547
548 public synchronized DnNode<N> add( Dn dn ) throws LdapException
549 {
550 return add( dn, null );
551 }
552
553
554
555
556
557
558
559
560
561
562
563 public synchronized DnNode<N> add( Dn dn, N element ) throws LdapException
564 {
565 checkDn( dn );
566
567
568 DnNode<N> parentNode = getNode( dn );
569
570 if ( parentNode == null )
571 {
572
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
582 int nbRdns = dn.size() - parentNode.depth;
583
584 if ( nbRdns == 0 )
585 {
586
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
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
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
613 childNode.parent = parentNode;
614 parentNode.children.put( childNode.nodeRdn, childNode );
615
616 return childNode;
617 }
618 }
619 }
620
621
622
623
624
625
626
627
628 public synchronized void remove( Dn dn ) throws LdapException
629 {
630 checkDn( dn );
631
632
633
634 DnNode<N> parentNode = getNode( dn );
635
636 if ( parentNode == null )
637 {
638 return;
639 }
640
641
642
643 if ( ( dn.size() != parentNode.depth ) || parentNode.hasChildren() )
644 {
645 return;
646 }
647
648
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
658 break;
659 }
660
661 parentNode = parentNode.getParent();
662 }
663 }
664
665
666
667
668
669
670
671
672
673 public synchronized boolean contains( Rdn rdn )
674 {
675 return children.containsKey( rdn );
676 }
677
678
679
680
681
682
683
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
698
699 public synchronized Rdn getRdn()
700 {
701 return nodeRdn;
702 }
703
704
705
706
707
708
709
710
711
712
713
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
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
750
751
752
753
754
755
756
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
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
798
799
800
801
802
803
804
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
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
846
847
848
849
850
851
852
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
874
875
876
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
900
901
902
903
904 public synchronized void move( Dn newParent ) throws LdapException
905 {
906 DnNode<N> tmp = null;
907
908 Dn tmpDn = null;
909
910
911 if ( newParent.isDescendantOf( parent.nodeDn ) )
912 {
913 tmp = parent;
914 tmpDn = parent.nodeDn;
915 }
916
917
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
930
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
957
958
959
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
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
1052
1053 public String toString()
1054 {
1055 return toString( "" );
1056 }
1057
1058
1059
1060
1061
1062 public synchronized Dn getDn()
1063 {
1064 return nodeDn;
1065 }
1066 }