1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 package org.apache.directory.server.core.avltree;
21
22
23 import java.util.ArrayList;
24 import java.util.Comparator;
25 import java.util.List;
26
27
28
29
30
31
32
33
34
35 public class AvlTreeMapImpl<K, V> implements AvlTreeMap<K, V>
36 {
37
38 private LinkedAvlMapNode<K, V> root;
39
40
41 private Comparator<K> keyComparator;
42
43
44 private Comparator<V> valueComparator;
45
46
47 private LinkedAvlMapNode<K, V> first;
48
49
50 private LinkedAvlMapNode<K, V> last;
51
52
53 private boolean allowDuplicates;
54
55
56 private int size;
57
58
59
60
61
62
63
64
65 public AvlTreeMapImpl( Comparator<K> keyComparator, Comparator<V> valueComparator )
66 {
67 this( keyComparator, valueComparator, false );
68 }
69
70
71
72
73
74
75
76
77
78 public AvlTreeMapImpl( Comparator<K> keyComparator, Comparator<V> valueComparator, boolean allowDuplicates )
79 {
80 this.keyComparator = keyComparator;
81 this.valueComparator = valueComparator;
82 this.allowDuplicates = allowDuplicates;
83 }
84
85
86
87
88
89 public Comparator<K> getKeyComparator()
90 {
91 return keyComparator;
92 }
93
94
95
96
97
98 public Comparator<V> getValueComparator()
99 {
100 return valueComparator;
101 }
102
103
104
105
106
107 public V insert( K key, V value )
108 {
109 LinkedAvlMapNode<K, V> node, temp;
110 LinkedAvlMapNode<K, V> parent = null;
111 int c;
112
113 if ( root == null )
114 {
115 root = new LinkedAvlMapNode<K, V>( key, value );
116 first = root;
117 last = root;
118 size++;
119 return null;
120 }
121
122 node = new LinkedAvlMapNode<K, V>( key, value );
123
124 temp = root;
125
126 List<LinkedAvlMapNode<K, V>> treePath = new ArrayList<LinkedAvlMapNode<K, V>>();
127
128 while ( temp != null )
129 {
130 treePath.add( 0, temp );
131 parent = temp;
132
133 c = keyComparator.compare( key, temp.getKey() );
134
135 if ( c == 0 )
136 {
137 if ( allowDuplicates )
138 {
139 return insertDupKey( value, temp );
140 }
141 else
142 {
143
144 return temp.value.setSingleton( value );
145 }
146 }
147
148 if ( c < 0 )
149 {
150 temp.isLeft = true;
151 temp = temp.getLeft();
152 }
153 else
154 {
155 temp.isLeft = false;
156 temp = temp.getRight();
157 }
158 }
159
160 if ( ( c = keyComparator.compare( key, parent.getKey() ) ) < 0 )
161 {
162 parent.setLeft( node );
163 }
164 else
165 {
166 parent.setRight( node );
167 }
168
169 insertInList( node, parent, c );
170
171 treePath.add( 0, node );
172 balance( treePath );
173
174 size++;
175 return null;
176 }
177
178
179 private V insertDupKey( V value, LinkedAvlMapNode<K, V> existingNode )
180 {
181 AvlTree<V> dupsTree = null;
182
183 if ( existingNode.value.isOrderedSet() )
184 {
185 dupsTree = existingNode.value.getOrderedSet();
186 }
187 else
188 {
189
190 dupsTree = new AvlTreeImpl<V>( valueComparator );
191 dupsTree.insert( existingNode.value.getSingleton() );
192 existingNode.value.switchToOrderedSet( dupsTree );
193 }
194
195
196 if ( dupsTree.find( value ) != null )
197 {
198 return value;
199 }
200
201
202 dupsTree.insert( value );
203
204 return null;
205 }
206
207
208 private void removeFromList( LinkedAvlMapNode<K, V> node )
209 {
210 if ( node.next == null && node.previous == null )
211 {
212 first = last = null;
213 }
214 else if ( node.next == null )
215 {
216 node.previous.next = null;
217 last = node.previous;
218 }
219 else if ( node.previous == null )
220 {
221 node.next.previous = null;
222 first = node.next;
223 }
224 else
225
226 {
227 node.previous.next = node.next;
228 node.next.previous = node.previous;
229 }
230
231 }
232
233
234 private void insertInList( LinkedAvlMapNode<K, V> node, LinkedAvlMapNode<K, V> parentNode, int pos )
235 {
236
237 if ( pos < 0 )
238 {
239 if ( last == null )
240 {
241 last = parentNode;
242 }
243
244 if ( parentNode.previous == null )
245 {
246 first = node;
247 }
248 else
249 {
250 parentNode.previous.next = node;
251 node.previous = parentNode.previous;
252 }
253
254 node.next = parentNode;
255 parentNode.previous = node;
256 }
257 else if ( pos > 0 )
258 {
259 if ( parentNode.next == null )
260 {
261 last = node;
262 }
263 else
264 {
265 parentNode.next.previous = node;
266 node.next = parentNode.next;
267 }
268 node.previous = parentNode;
269 parentNode.next = node;
270 }
271
272 }
273
274
275
276
277
278 public SingletonOrOrderedSet<V> remove( K key )
279 {
280 if ( key == null )
281 {
282 throw new IllegalArgumentException( "key cannot be null" );
283 }
284
285 LinkedAvlMapNode<K, V> temp = null;
286
287 List<LinkedAvlMapNode<K, V>> treePath = new ArrayList<LinkedAvlMapNode<K, V>>();
288
289 treePath = find( key, root, treePath );
290
291 if ( treePath == null )
292 {
293 return null;
294 }
295
296 temp = treePath.remove( 0 );
297
298 if ( temp.isLeaf() && ( temp == root ) )
299 {
300 root = null;
301 }
302 else
303 {
304 balanceNodesAfterRemove( treePath, temp );
305 }
306
307 size--;
308 return temp.value;
309 }
310
311
312
313
314
315 public V remove( K key, V value )
316 {
317 if ( key == null || value == null )
318 {
319 throw new IllegalArgumentException( "key or value cannot be null" );
320 }
321
322 LinkedAvlMapNode<K, V> temp = null;
323
324 List<LinkedAvlMapNode<K, V>> treePath = new ArrayList<LinkedAvlMapNode<K, V>>();
325
326 treePath = find( key, root, treePath );
327
328 if ( treePath == null )
329 {
330 return null;
331 }
332
333 temp = treePath.remove( 0 );
334
335
336 if ( allowDuplicates )
337 {
338 if ( temp.value.isOrderedSet() )
339 {
340 AvlTree<V> dupsTree = temp.value.getOrderedSet();
341 V removedVal = dupsTree.remove( value );
342
343
344
345
346
347
348
349 if ( ( removedVal != null ) && !dupsTree.isEmpty() )
350 {
351 return removedVal;
352 }
353
354
355
356 else if ( removedVal == null )
357 {
358 return removedVal;
359 }
360 }
361 else
362 {
363 if ( valueComparator.compare( temp.value.getSingleton(), value ) != 0 )
364 {
365 return null;
366 }
367 }
368 }
369
370 if ( temp.isLeaf() && ( temp == root ) )
371 {
372 if ( allowDuplicates )
373 {
374 if ( temp.value.isSingleton() || temp.value.getOrderedSet().isEmpty() )
375 {
376 root = null;
377 }
378 }
379 else
380
381 {
382 root = null;
383 }
384
385 size--;
386 return value;
387 }
388
389 balanceNodesAfterRemove( treePath, temp );
390
391 size--;
392 return value;
393 }
394
395
396
397
398
399
400
401
402
403 private void balanceNodesAfterRemove( List<LinkedAvlMapNode<K, V>> treePath, LinkedAvlMapNode<K, V> delNode )
404 {
405 LinkedAvlMapNode<K, V> y = null;
406
407
408 removeFromList( delNode );
409
410 if ( delNode.isLeaf() )
411 {
412 if ( !treePath.isEmpty() )
413 {
414 detachNodes( delNode, treePath.get( 0 ) );
415 }
416 }
417 else
418 {
419 if ( delNode.left != null )
420 {
421 List<LinkedAvlMapNode<K, V>> leftTreePath = findMax( delNode.left );
422 y = leftTreePath.remove( 0 );
423
424 if ( leftTreePath.isEmpty() )
425 {
426 detachNodes( y, delNode );
427 }
428 else
429 {
430 detachNodes( y, leftTreePath.remove( 0 ) );
431 }
432
433 leftTreePath.addAll( treePath );
434 treePath = leftTreePath;
435
436 y.right = delNode.right;
437
438 if ( delNode == root )
439 {
440 y.left = delNode.left;
441 root = y;
442 }
443 else
444 {
445 replaceNode( delNode, y, treePath.get( 0 ) );
446 }
447 }
448 else if ( delNode.right != null )
449 {
450 List<LinkedAvlMapNode<K, V>> rightTreePath = findMin( delNode.right );
451 y = rightTreePath.remove( 0 );
452
453 if ( rightTreePath.isEmpty() )
454 {
455 detachNodes( y, delNode );
456 }
457 else
458 {
459 detachNodes( y, rightTreePath.remove( 0 ) );
460 }
461
462 rightTreePath.addAll( treePath );
463 treePath = rightTreePath;
464
465 y.right = delNode.right;
466
467 if ( delNode == root )
468 {
469 y.right = delNode.right;
470 root = y;
471 }
472 else
473 {
474 replaceNode( delNode, y, treePath.get( 0 ) );
475 }
476 }
477 }
478
479 treePath.add( 0, y );
480 balance( treePath );
481 }
482
483
484
485
486
487
488
489
490
491
492
493
494
495 private void balance( List<LinkedAvlMapNode<K, V>> treePath )
496 {
497 LinkedAvlMapNode<K, V> parentNode = null;
498
499 int size = treePath.size();
500
501 for ( LinkedAvlMapNode<K, V> node : treePath )
502 {
503 int balFactor = getBalance( node );
504
505 if ( node != root && treePath.indexOf( node ) < ( size - 1 ) )
506 {
507 parentNode = treePath.get( treePath.indexOf( node ) + 1 );
508 }
509
510 if ( balFactor > 1 )
511 {
512 if ( getBalance( node.right ) <= -1 )
513 {
514
515 rotateSingleRight( node.right, node );
516 rotateSingleLeft( node, parentNode );
517 }
518 else
519
520 {
521 rotateSingleLeft( node, parentNode );
522 }
523 }
524 else if ( balFactor < -1 )
525 {
526 if ( getBalance( node.left ) >= 1 )
527 {
528
529 rotateSingleLeft( node.left, node );
530 rotateSingleRight( node, parentNode );
531 }
532 else
533 {
534 rotateSingleRight( node, parentNode );
535 }
536 }
537 }
538 }
539
540
541
542
543
544 public boolean isEmpty()
545 {
546 return root == null;
547 }
548
549
550
551
552
553
554 public int getSize()
555 {
556 return size;
557 }
558
559
560
561
562
563
564
565
566
567
568 {
569 this.root = root;
570 }
571
572
573
574
575
576
577
578
579
580
581 {
582 this.first = first;
583 }
584
585
586
587
588
589
590
591
592
593
594 {
595 this.last = last;
596 }
597
598
599
600
601
602 public LinkedAvlMapNode<K, V> getRoot()
603 {
604 return root;
605 }
606
607
608
609
610
611 public List<K> getKeys()
612 {
613 List<K> keys = new ArrayList<K>();
614 LinkedAvlMapNode<K, V> node = first;
615
616 while ( node != null )
617 {
618 keys.add( node.key );
619 node = node.next;
620 }
621
622 return keys;
623 }
624
625
626
627
628
629 public void printTree()
630 {
631 if ( isEmpty() )
632 {
633 System.out.println( "Tree is empty" );
634 return;
635 }
636
637 getRoot().setDepth( 0 );
638
639 System.out.println( getRoot() );
640
641 visit( getRoot().getRight(), getRoot() );
642
643 visit( getRoot().getLeft(), getRoot() );
644 }
645
646
647
648
649
650 public LinkedAvlMapNode<K, V> getFirst()
651 {
652 return first;
653 }
654
655
656
657
658
659 public LinkedAvlMapNode<K, V> getLast()
660 {
661 return last;
662 }
663
664
665
666
667
668
669
670
671 private void rotateSingleLeft( LinkedAvlMapNode<K, V> node, LinkedAvlMapNode<K, V> parentNode )
672 {
673 LinkedAvlMapNode<K, V> temp;
674
675
676 temp = node.right;
677 node.right = temp.left;
678 temp.left = node;
679
680 if ( node == root )
681 {
682 root = temp;
683 }
684 else if ( parentNode != null )
685 {
686 if ( parentNode.left == node )
687 {
688 parentNode.left = temp;
689 }
690 else if ( parentNode.right == node )
691 {
692 parentNode.right = temp;
693 }
694 }
695 }
696
697
698
699
700
701
702
703
704 private void rotateSingleRight( LinkedAvlMapNode<K, V> node, LinkedAvlMapNode<K, V> parentNode )
705 {
706 LinkedAvlMapNode<K, V> temp;
707
708
709 temp = node.left;
710 node.left = temp.right;
711 temp.right = node;
712
713 if ( node == root )
714 {
715 root = temp;
716 }
717 else if ( parentNode != null )
718 {
719 if ( parentNode.left == node )
720 {
721 parentNode.left = temp;
722 }
723 else if ( parentNode.right == node )
724 {
725 parentNode.right = temp;
726 }
727 }
728
729
730
731
732 else if ( root != null && root.left == node )
733 {
734 root.left = temp;
735
736 }
737 }
738
739
740
741
742
743
744
745
746 private void detachNodes( LinkedAvlMapNode<K, V> node, LinkedAvlMapNode<K, V> parentNode )
747 {
748 if ( parentNode != null )
749 {
750 if ( node == parentNode.left )
751 {
752 parentNode.left = node.left;
753 }
754 else if ( node == parentNode.right )
755 {
756 parentNode.right = node.left;
757 }
758 }
759 }
760
761
762
763
764
765
766
767
768
769
770 private void replaceNode( LinkedAvlMapNode<K, V> deleteNode, LinkedAvlMapNode<K, V> replaceNode,
771 LinkedAvlMapNode<K, V> parentNode )
772 {
773 if ( parentNode != null )
774 {
775 replaceNode.left = deleteNode.left;
776
777 if ( deleteNode == parentNode.left )
778 {
779 parentNode.left = replaceNode;
780 }
781 else if ( deleteNode == parentNode.right )
782 {
783 parentNode.right = replaceNode;
784 }
785 }
786 }
787
788
789
790
791
792
793
794
795
796
797
798 private List<LinkedAvlMapNode<K, V>> find( K key, LinkedAvlMapNode<K, V> startNode,
799 List<LinkedAvlMapNode<K, V>> path )
800 {
801 int c;
802
803 if ( startNode == null )
804 {
805 return null;
806 }
807
808 path.add( 0, startNode );
809 c = keyComparator.compare( key, startNode.key );
810
811 if ( c == 0 )
812 {
813 return path;
814 }
815 else if ( c > 0 )
816 {
817 return find( key, startNode.right, path );
818 }
819 else if ( c < 0 )
820 {
821 return find( key, startNode.left, path );
822 }
823
824 return null;
825 }
826
827
828
829
830
831 public LinkedAvlMapNode<K, V> findGreater( K key )
832 {
833 LinkedAvlMapNode<K, V> result = fetchNonNullNode( key, root, root );
834
835 if ( result == null )
836 {
837 return null;
838 }
839 else if ( keyComparator.compare( key, result.key ) < 0 )
840 {
841 return result;
842 }
843
844 return result.next;
845 }
846
847
848
849
850
851 public LinkedAvlMapNode<K, V> findGreaterOrEqual( K key )
852 {
853 LinkedAvlMapNode<K, V> result = fetchNonNullNode( key, root, root );
854
855 if ( result == null )
856 {
857 return null;
858 }
859 else if ( keyComparator.compare( key, result.key ) <= 0 )
860 {
861 return result;
862 }
863
864 return result.next;
865 }
866
867
868
869
870
871 public LinkedAvlMapNode<K, V> findLess( K key )
872 {
873 LinkedAvlMapNode<K, V> result = fetchNonNullNode( key, root, root );
874
875 if ( result == null )
876 {
877 return null;
878 }
879 else if ( keyComparator.compare( key, result.key ) > 0 )
880 {
881 return result;
882 }
883
884 return result.previous;
885 }
886
887
888
889
890
891 public LinkedAvlMapNode<K, V> findLessOrEqual( K key )
892 {
893 LinkedAvlMapNode<K, V> result = fetchNonNullNode( key, root, root );
894
895 if ( result == null )
896 {
897 return null;
898 }
899 else if ( keyComparator.compare( key, result.key ) >= 0 )
900 {
901 return result;
902 }
903
904 return result.previous;
905 }
906
907
908
909
910
911
912
913 private LinkedAvlMapNode<K, V> fetchNonNullNode( K key, LinkedAvlMapNode<K, V> startNode,
914 LinkedAvlMapNode<K, V> parent )
915 {
916
917 if ( startNode == null )
918 {
919 return parent;
920 }
921
922 int c = keyComparator.compare( key, startNode.key );
923
924 parent = startNode;
925
926 if ( c > 0 )
927 {
928 return fetchNonNullNode( key, startNode.right, parent );
929 }
930 else if ( c < 0 )
931 {
932 return fetchNonNullNode( key, startNode.left, parent );
933 }
934
935 return startNode;
936 }
937
938
939
940
941
942 public LinkedAvlMapNode<K, V> find( K key )
943 {
944 return find( key, root );
945 }
946
947
948
949
950
951 public LinkedAvlMapNode<K, V> find( K key, V value )
952 {
953 if ( key == null || value == null )
954 {
955 return null;
956 }
957
958 LinkedAvlMapNode<K, V> node = find( key, root );
959
960 if ( node == null )
961 {
962 return null;
963 }
964
965 if ( node.value.isOrderedSet() )
966 {
967 AvlTree<V> dupsTree = node.value.getOrderedSet();
968
969 if ( dupsTree.find( value ) == null )
970 {
971 return null;
972 }
973 }
974 else
975 {
976 if ( valueComparator.compare( node.value.getSingleton(), value ) != 0 )
977 {
978 return null;
979 }
980 }
981
982 return node;
983 }
984
985
986 private LinkedAvlMapNode<K, V> find( K key, LinkedAvlMapNode<K, V> startNode )
987 {
988 int c;
989
990 if ( startNode == null )
991 {
992 return null;
993 }
994
995 c = keyComparator.compare( key, startNode.key );
996
997 if ( c > 0 )
998 {
999 startNode.isLeft = false;
1000 return find( key, startNode.right );
1001 }
1002 else if ( c < 0 )
1003 {
1004 startNode.isLeft = true;
1005 return find( key, startNode.left );
1006 }
1007
1008 return startNode;
1009 }
1010
1011
1012
1013
1014
1015
1016
1017
1018 private List<LinkedAvlMapNode<K, V>> findMax( LinkedAvlMapNode<K, V> startNode )
1019 {
1020 LinkedAvlMapNode<K, V> x = startNode;
1021 LinkedAvlMapNode<K, V> y = null;
1022 List<LinkedAvlMapNode<K, V>> path;
1023
1024 if ( x == null )
1025 {
1026 return null;
1027 }
1028
1029 while ( x.right != null )
1030 {
1031 x.isLeft = false;
1032 y = x;
1033 x = x.right;
1034 }
1035
1036 path = new ArrayList<LinkedAvlMapNode<K, V>>( 2 );
1037 path.add( x );
1038
1039 if ( y != null )
1040 {
1041 path.add( y );
1042 }
1043
1044 return path;
1045 }
1046
1047
1048
1049
1050
1051
1052
1053
1054 private List<LinkedAvlMapNode<K, V>> findMin( LinkedAvlMapNode<K, V> startNode )
1055 {
1056 LinkedAvlMapNode<K, V> x = startNode;
1057 LinkedAvlMapNode<K, V> y = null;
1058 List<LinkedAvlMapNode<K, V>> path;
1059
1060 if ( x == null )
1061 {
1062 return null;
1063 }
1064
1065 while ( x.left != null )
1066 {
1067 x.isLeft = true;
1068 y = x;
1069 x = x.left;
1070 }
1071
1072 path = new ArrayList<LinkedAvlMapNode<K, V>>( 2 );
1073 path.add( x );
1074
1075 if ( y != null )
1076 {
1077 path.add( y );
1078 }
1079
1080 return path;
1081 }
1082
1083
1084
1085
1086
1087
1088
1089
1090 private int getBalance( LinkedAvlMapNode<K, V> node )
1091 {
1092 if ( node == null )
1093 {
1094 return 0;
1095 }
1096
1097 return node.getBalance();
1098 }
1099
1100
1101 private void visit( LinkedAvlMapNode<K, V> node, LinkedAvlMapNode<K, V> parentNode )
1102 {
1103 if ( node == null )
1104 {
1105 return;
1106 }
1107
1108 if ( !node.isLeaf() )
1109 {
1110 node.setDepth( parentNode.getDepth() + 1 );
1111 }
1112
1113 for ( int i = 0; i < parentNode.getDepth(); i++ )
1114 {
1115 System.out.print( "| " );
1116 }
1117
1118 String type = "";
1119 if ( node == parentNode.left )
1120 {
1121 type = "L";
1122 }
1123 else if ( node == parentNode.right )
1124 {
1125 type = "R";
1126 }
1127
1128 System.out.println( "|--" + node + type );
1129
1130 if ( node.getRight() != null )
1131 {
1132 visit( node.getRight(), node );
1133 }
1134
1135 if ( node.getLeft() != null )
1136 {
1137 visit( node.getLeft(), node );
1138 }
1139 }
1140
1141
1142
1143
1144
1145 public boolean isDupsAllowed()
1146 {
1147 return allowDuplicates;
1148 }
1149
1150
1151
1152
1153
1154 public void removeAll()
1155 {
1156 LinkedAvlMapNode<K, V> tmp;
1157
1158 while ( first != null )
1159 {
1160 tmp = first;
1161 first = tmp.next;
1162 tmp = null;
1163 }
1164
1165 last = null;
1166 root = null;
1167 size = 0;
1168 }
1169 }