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