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>
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 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
90
91
92
93 public DnNode( N element )
94 {
95 this.nodeElement = element;
96 children = new HashMap<Rdn, DnNode<N>>();
97 }
98
99
100
101
102
103
104
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
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
131 throw new IllegalArgumentException( le.getMessage(), le );
132 }
133 }
134
135
136
137
138
139
140
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
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
163 for ( Rdn rdn : dn.getRdns() )
164 {
165 if ( nbRdns == 0 )
166 {
167 break;
168 }
169
170 if ( rootNode == null )
171 {
172
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
200
201 private synchronized void setElement( N element )
202 {
203 this.nodeElement = element;
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<>();
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 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
873
874
875
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
899
900
901
902
903 public synchronized void move( Dn newParent ) throws LdapException
904 {
905 DnNode<N> tmp = null;
906
907 Dn tmpDn = null;
908
909
910 if ( newParent.isDescendantOf( parent.nodeDn ) )
911 {
912 tmp = parent;
913 tmpDn = parent.nodeDn;
914 }
915
916
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
929
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
956
957
958
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
1029
1030 @Override
1031 public String toString()
1032 {
1033 return toString( "" );
1034 }
1035
1036
1037
1038
1039
1040 public synchronized Dn getDn()
1041 {
1042 return nodeDn;
1043 }
1044 }