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