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 @Deprecated
49 public abstract class AbstractLinkedList<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 AbstractLinkedList<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 AbstractLinkedList<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 AbstractLinkedList<E> parent;
231
232 int offset;
233
234 int size;
235
236 int expectedModCount;
237
238 protected LinkedSubList(final AbstractLinkedList<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 AbstractLinkedList() {
528 }
529
530
531
532
533
534
535 protected AbstractLinkedList(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 boolean addFirst(final E o) {
567 addNodeAfter(header, o);
568 return true;
569 }
570
571 public boolean addLast(final E o) {
572 addNodeBefore(header, o);
573 return true;
574 }
575
576
577
578
579
580
581
582
583 protected void addNode(final Node<E> nodeToInsert, final Node<E> insertBeforeNode) {
584 Objects.requireNonNull(nodeToInsert, "nodeToInsert");
585 Objects.requireNonNull(insertBeforeNode, "insertBeforeNode");
586 nodeToInsert.next = insertBeforeNode;
587 nodeToInsert.previous = insertBeforeNode.previous;
588 insertBeforeNode.previous.next = nodeToInsert;
589 insertBeforeNode.previous = nodeToInsert;
590 size++;
591 modCount++;
592 }
593
594
595
596
597
598
599
600
601
602
603
604
605 protected void addNodeAfter(final Node<E> node, final E value) {
606 final Node<E> newNode = createNode(value);
607 addNode(newNode, node.next);
608 }
609
610
611
612
613
614
615
616
617
618
619
620
621 protected void addNodeBefore(final Node<E> node, final E value) {
622 final Node<E> newNode = createNode(value);
623 addNode(newNode, node);
624 }
625
626 @Override
627 public void clear() {
628 removeAllNodes();
629 }
630
631 @Override
632 public boolean contains(final Object value) {
633 return indexOf(value) != -1;
634 }
635
636 @Override
637 public boolean containsAll(final Collection<?> coll) {
638 for (final Object o : coll) {
639 if (!contains(o)) {
640 return false;
641 }
642 }
643 return true;
644 }
645
646
647
648
649
650
651
652
653 protected Node<E> createHeaderNode() {
654 return new Node<>();
655 }
656
657
658
659
660
661
662
663
664
665 protected Node<E> createNode(final E value) {
666 return new Node<>(value);
667 }
668
669
670
671
672
673
674
675 protected Iterator<E> createSubListIterator(final LinkedSubList<E> subList) {
676 return createSubListListIterator(subList, 0);
677 }
678
679
680
681
682
683
684
685
686 protected ListIterator<E> createSubListListIterator(final LinkedSubList<E> subList, final int fromIndex) {
687 return new LinkedSubListIterator<>(subList, fromIndex);
688 }
689
690
691
692
693
694
695
696
697
698
699
700 @SuppressWarnings("unchecked")
701 protected void doReadObject(final ObjectInputStream inputStream) throws IOException, ClassNotFoundException {
702 init();
703 final int size = inputStream.readInt();
704 for (int i = 0; i < size; i++) {
705 add((E) inputStream.readObject());
706 }
707 }
708
709
710
711
712
713
714
715
716
717
718 protected void doWriteObject(final ObjectOutputStream outputStream) throws IOException {
719
720 outputStream.writeInt(size());
721 for (final E e : this) {
722 outputStream.writeObject(e);
723 }
724 }
725
726 @Override
727 public boolean equals(final Object obj) {
728 if (obj == this) {
729 return true;
730 }
731 if (!(obj instanceof List)) {
732 return false;
733 }
734 final List<?> other = (List<?>) obj;
735 if (other.size() != size()) {
736 return false;
737 }
738 final ListIterator<?> it1 = listIterator();
739 final ListIterator<?> it2 = other.listIterator();
740 while (it1.hasNext() && it2.hasNext()) {
741 if (!Objects.equals(it1.next(), it2.next())) {
742 return false;
743 }
744 }
745 return !(it1.hasNext() || it2.hasNext());
746 }
747
748 @Override
749 public E get(final int index) {
750 final Node<E> node = getNode(index, false);
751 return node.getValue();
752 }
753
754 public E getFirst() {
755 final Node<E> node = header.next;
756 if (node == header) {
757 throw new NoSuchElementException();
758 }
759 return node.getValue();
760 }
761
762 public E getLast() {
763 final Node<E> node = header.previous;
764 if (node == header) {
765 throw new NoSuchElementException();
766 }
767 return node.getValue();
768 }
769
770
771
772
773
774
775
776
777
778
779
780
781 protected Node<E> getNode(final int index, final boolean endMarkerAllowed) throws IndexOutOfBoundsException {
782
783 if (index < 0) {
784 throw new IndexOutOfBoundsException("Couldn't get the node: " +
785 "index (" + index + ") less than zero.");
786 }
787 if (!endMarkerAllowed && index == size) {
788 throw new IndexOutOfBoundsException("Couldn't get the node: " +
789 "index (" + index + ") is the size of the list.");
790 }
791 if (index > size) {
792 throw new IndexOutOfBoundsException("Couldn't get the node: " +
793 "index (" + index + ") greater than the size of the " +
794 "list (" + size + ").");
795 }
796
797 Node<E> node;
798 if (index < size / 2) {
799
800 node = header.next;
801 for (int currentIndex = 0; currentIndex < index; currentIndex++) {
802 node = node.next;
803 }
804 } else {
805
806 node = header;
807 for (int currentIndex = size; currentIndex > index; currentIndex--) {
808 node = node.previous;
809 }
810 }
811 return node;
812 }
813
814 @Override
815 public int hashCode() {
816 int hashCode = 1;
817 for (final E e : this) {
818 hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
819 }
820 return hashCode;
821 }
822
823 @Override
824 public int indexOf(final Object value) {
825 int i = 0;
826 for (Node<E> node = header.next; node != header; node = node.next) {
827 if (isEqualValue(node.getValue(), value)) {
828 return i;
829 }
830 i++;
831 }
832 return CollectionUtils.INDEX_NOT_FOUND;
833 }
834
835
836
837
838
839
840
841 protected void init() {
842 header = createHeaderNode();
843 }
844
845 @Override
846 public boolean isEmpty() {
847 return size() == 0;
848 }
849
850
851
852
853
854
855
856
857
858
859 protected boolean isEqualValue(final Object value1, final Object value2) {
860 return Objects.equals(value1, value2);
861 }
862
863 @Override
864 public Iterator<E> iterator() {
865 return listIterator();
866 }
867
868 @Override
869 public int lastIndexOf(final Object value) {
870 int i = size - 1;
871 for (Node<E> node = header.previous; node != header; node = node.previous) {
872 if (isEqualValue(node.getValue(), value)) {
873 return i;
874 }
875 i--;
876 }
877 return CollectionUtils.INDEX_NOT_FOUND;
878 }
879
880 @Override
881 public ListIterator<E> listIterator() {
882 return new LinkedListIterator<>(this, 0);
883 }
884
885 @Override
886 public ListIterator<E> listIterator(final int fromIndex) {
887 return new LinkedListIterator<>(this, fromIndex);
888 }
889
890 @Override
891 public E remove(final int index) {
892 final Node<E> node = getNode(index, false);
893 final E oldValue = node.getValue();
894 removeNode(node);
895 return oldValue;
896 }
897
898 @Override
899 public boolean remove(final Object value) {
900 for (Node<E> node = header.next; node != header; node = node.next) {
901 if (isEqualValue(node.getValue(), value)) {
902 removeNode(node);
903 return true;
904 }
905 }
906 return false;
907 }
908
909
910
911
912
913
914
915
916
917
918 @Override
919 public boolean removeAll(final Collection<?> coll) {
920 boolean modified = false;
921 final Iterator<E> it = iterator();
922 while (it.hasNext()) {
923 if (coll.contains(it.next())) {
924 it.remove();
925 modified = true;
926 }
927 }
928 return modified;
929 }
930
931
932
933
934 protected void removeAllNodes() {
935 header.next = header;
936 header.previous = header;
937 size = 0;
938 modCount++;
939 }
940
941 public E removeFirst() {
942 final Node<E> node = header.next;
943 if (node == header) {
944 throw new NoSuchElementException();
945 }
946 final E oldValue = node.getValue();
947 removeNode(node);
948 return oldValue;
949 }
950
951 public E removeLast() {
952 final Node<E> node = header.previous;
953 if (node == header) {
954 throw new NoSuchElementException();
955 }
956 final E oldValue = node.getValue();
957 removeNode(node);
958 return oldValue;
959 }
960
961
962
963
964
965
966
967 protected void removeNode(final Node<E> node) {
968 Objects.requireNonNull(node, "node");
969 node.previous.next = node.next;
970 node.next.previous = node.previous;
971 size--;
972 modCount++;
973 }
974
975
976
977
978
979
980
981
982
983
984 @Override
985 public boolean retainAll(final Collection<?> coll) {
986 boolean modified = false;
987 final Iterator<E> it = iterator();
988 while (it.hasNext()) {
989 if (!coll.contains(it.next())) {
990 it.remove();
991 modified = true;
992 }
993 }
994 return modified;
995 }
996
997 @Override
998 public E set(final int index, final E value) {
999 final Node<E> node = getNode(index, false);
1000 final E oldValue = node.getValue();
1001 updateNode(node, value);
1002 return oldValue;
1003 }
1004
1005 @Override
1006 public int size() {
1007 return size;
1008 }
1009
1010
1011
1012
1013
1014
1015
1016
1017 @Override
1018 public List<E> subList(final int fromIndexInclusive, final int toIndexExclusive) {
1019 return new LinkedSubList<>(this, fromIndexInclusive, toIndexExclusive);
1020 }
1021
1022 @Override
1023 public Object[] toArray() {
1024 return toArray(new Object[size]);
1025 }
1026
1027 @Override
1028 @SuppressWarnings("unchecked")
1029 public <T> T[] toArray(T[] array) {
1030
1031 if (array.length < size) {
1032 final Class<?> componentType = array.getClass().getComponentType();
1033 array = (T[]) Array.newInstance(componentType, size);
1034 }
1035
1036 int i = 0;
1037 for (Node<E> node = header.next; node != header; node = node.next, i++) {
1038 array[i] = (T) node.getValue();
1039 }
1040
1041 if (array.length > size) {
1042 array[size] = null;
1043 }
1044 return array;
1045 }
1046
1047 @Override
1048 public String toString() {
1049 if (isEmpty()) {
1050 return "[]";
1051 }
1052 final StringBuilder buf = new StringBuilder(16 * size());
1053 buf.append(CollectionUtils.DEFAULT_TOSTRING_PREFIX);
1054
1055 final Iterator<E> it = iterator();
1056 boolean hasNext = it.hasNext();
1057 while (hasNext) {
1058 final Object value = it.next();
1059 buf.append(value == this ? "(this Collection)" : value);
1060 hasNext = it.hasNext();
1061 if (hasNext) {
1062 buf.append(", ");
1063 }
1064 }
1065 buf.append(CollectionUtils.DEFAULT_TOSTRING_SUFFIX);
1066 return buf.toString();
1067 }
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077 protected void updateNode(final Node<E> node, final E value) {
1078 node.setValue(value);
1079 }
1080
1081 }