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 public abstract class AbstractLinkedList<E> implements List<E> {
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65 protected static class LinkedListIterator<E> implements ListIterator<E>, OrderedIterator<E> {
66
67
68 protected final AbstractLinkedList<E> parent;
69
70
71
72
73
74 protected Node<E> next;
75
76
77
78
79 protected int nextIndex;
80
81
82
83
84
85
86
87
88
89 protected Node<E> current;
90
91
92
93
94
95
96
97 protected int expectedModCount;
98
99
100
101
102
103
104
105
106 protected LinkedListIterator(final AbstractLinkedList<E> parent, final int fromIndex)
107 throws IndexOutOfBoundsException {
108 this.parent = parent;
109 this.expectedModCount = parent.modCount;
110 this.next = parent.getNode(fromIndex, true);
111 this.nextIndex = fromIndex;
112 }
113
114 @Override
115 public void add(final E obj) {
116 checkModCount();
117 parent.addNodeBefore(next, obj);
118 current = null;
119 nextIndex++;
120 expectedModCount++;
121 }
122
123
124
125
126
127
128
129
130 protected void checkModCount() {
131 if (parent.modCount != expectedModCount) {
132 throw new ConcurrentModificationException();
133 }
134 }
135
136
137
138
139
140
141
142
143 protected Node<E> getLastNodeReturned() throws IllegalStateException {
144 if (current == null) {
145 throw new IllegalStateException();
146 }
147 return current;
148 }
149
150 @Override
151 public boolean hasNext() {
152 return next != parent.header;
153 }
154
155 @Override
156 public boolean hasPrevious() {
157 return next.previous != parent.header;
158 }
159
160 @Override
161 public E next() {
162 checkModCount();
163 if (!hasNext()) {
164 throw new NoSuchElementException("No element at index " + nextIndex + ".");
165 }
166 final E value = next.getValue();
167 current = next;
168 next = next.next;
169 nextIndex++;
170 return value;
171 }
172
173 @Override
174 public int nextIndex() {
175 return nextIndex;
176 }
177
178 @Override
179 public E previous() {
180 checkModCount();
181 if (!hasPrevious()) {
182 throw new NoSuchElementException("Already at start of list.");
183 }
184 next = next.previous;
185 final E value = next.getValue();
186 current = next;
187 nextIndex--;
188 return value;
189 }
190
191 @Override
192 public int previousIndex() {
193
194 return nextIndex() - 1;
195 }
196
197 @Override
198 public void remove() {
199 checkModCount();
200 if (current == next) {
201
202 next = next.next;
203 parent.removeNode(getLastNodeReturned());
204 } else {
205
206 parent.removeNode(getLastNodeReturned());
207 nextIndex--;
208 }
209 current = null;
210 expectedModCount++;
211 }
212
213 @Override
214 public void set(final E obj) {
215 checkModCount();
216 getLastNodeReturned().setValue(obj);
217 }
218
219 }
220
221
222
223
224
225
226 protected static class LinkedSubList<E> extends AbstractList<E> {
227
228 AbstractLinkedList<E> parent;
229
230 int offset;
231
232 int size;
233
234 int expectedModCount;
235
236 protected LinkedSubList(final AbstractLinkedList<E> parent, final int fromIndex, final int toIndex) {
237 if (fromIndex < 0) {
238 throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
239 }
240 if (toIndex > parent.size()) {
241 throw new IndexOutOfBoundsException("toIndex = " + toIndex);
242 }
243 if (fromIndex > toIndex) {
244 throw new IllegalArgumentException("fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
245 }
246 this.parent = parent;
247 this.offset = fromIndex;
248 this.size = toIndex - fromIndex;
249 this.expectedModCount = parent.modCount;
250 }
251
252 @Override
253 public void add(final int index, final E obj) {
254 rangeCheck(index, size + 1);
255 checkModCount();
256 parent.add(index + offset, obj);
257 expectedModCount = parent.modCount;
258 size++;
259 modCount++;
260 }
261
262 @Override
263 public boolean addAll(final Collection<? extends E> coll) {
264 return addAll(size, coll);
265 }
266
267 @Override
268 public boolean addAll(final int index, final Collection<? extends E> coll) {
269 rangeCheck(index, size + 1);
270 final int cSize = coll.size();
271 if (cSize == 0) {
272 return false;
273 }
274
275 checkModCount();
276 parent.addAll(offset + index, coll);
277 expectedModCount = parent.modCount;
278 size += cSize;
279 modCount++;
280 return true;
281 }
282
283 protected void checkModCount() {
284 if (parent.modCount != expectedModCount) {
285 throw new ConcurrentModificationException();
286 }
287 }
288
289 @Override
290 public void clear() {
291 checkModCount();
292 final Iterator<E> it = iterator();
293 while (it.hasNext()) {
294 it.next();
295 it.remove();
296 }
297 }
298
299 @Override
300 public E get(final int index) {
301 rangeCheck(index, size);
302 checkModCount();
303 return parent.get(index + offset);
304 }
305
306 @Override
307 public Iterator<E> iterator() {
308 checkModCount();
309 return parent.createSubListIterator(this);
310 }
311
312 @Override
313 public ListIterator<E> listIterator(final int index) {
314 rangeCheck(index, size + 1);
315 checkModCount();
316 return parent.createSubListListIterator(this, index);
317 }
318
319 protected void rangeCheck(final int index, final int beyond) {
320 if (index < 0 || index >= beyond) {
321 throw new IndexOutOfBoundsException("Index '" + index + "' out of bounds for size '" + size + "'");
322 }
323 }
324
325 @Override
326 public E remove(final int index) {
327 rangeCheck(index, size);
328 checkModCount();
329 final E result = parent.remove(index + offset);
330 expectedModCount = parent.modCount;
331 size--;
332 modCount++;
333 return result;
334 }
335
336 @Override
337 public E set(final int index, final E obj) {
338 rangeCheck(index, size);
339 checkModCount();
340 return parent.set(index + offset, obj);
341 }
342
343 @Override
344 public int size() {
345 checkModCount();
346 return size;
347 }
348
349 @Override
350 public List<E> subList(final int fromIndexInclusive, final int toIndexExclusive) {
351 return new LinkedSubList<>(parent, fromIndexInclusive + offset, toIndexExclusive + offset);
352 }
353 }
354
355
356
357
358
359
360 protected static class LinkedSubListIterator<E> extends LinkedListIterator<E> {
361
362
363 protected final LinkedSubList<E> sub;
364
365 protected LinkedSubListIterator(final LinkedSubList<E> sub, final int startIndex) {
366 super(sub.parent, startIndex + sub.offset);
367 this.sub = sub;
368 }
369
370 @Override
371 public void add(final E obj) {
372 super.add(obj);
373 sub.expectedModCount = parent.modCount;
374 sub.size++;
375 }
376
377 @Override
378 public boolean hasNext() {
379 return nextIndex() < sub.size;
380 }
381
382 @Override
383 public boolean hasPrevious() {
384 return previousIndex() >= 0;
385 }
386
387 @Override
388 public int nextIndex() {
389 return super.nextIndex() - sub.offset;
390 }
391
392 @Override
393 public void remove() {
394 super.remove();
395 sub.expectedModCount = parent.modCount;
396 sub.size--;
397 }
398 }
399
400
401
402
403
404
405
406 protected static class Node<E> {
407
408
409 protected Node<E> previous;
410
411 protected Node<E> next;
412
413 protected E value;
414
415
416
417
418 protected Node() {
419 previous = this;
420 next = this;
421 }
422
423
424
425
426
427
428 protected Node(final E value) {
429 this.value = value;
430 }
431
432
433
434
435
436
437
438
439 protected Node(final Node<E> previous, final Node<E> next, final E value) {
440 this.previous = previous;
441 this.next = next;
442 this.value = value;
443 }
444
445
446
447
448
449
450
451 protected Node<E> getNextNode() {
452 return next;
453 }
454
455
456
457
458
459
460
461 protected Node<E> getPreviousNode() {
462 return previous;
463 }
464
465
466
467
468
469
470
471 protected E getValue() {
472 return value;
473 }
474
475
476
477
478
479
480
481 protected void setNextNode(final Node<E> next) {
482 this.next = next;
483 }
484
485
486
487
488
489
490
491 protected void setPreviousNode(final Node<E> previous) {
492 this.previous = previous;
493 }
494
495
496
497
498
499
500
501 protected void setValue(final E value) {
502 this.value = value;
503 }
504 }
505
506
507
508
509
510
511 transient Node<E> header;
512
513
514 transient int size;
515
516
517 transient int modCount;
518
519
520
521
522
523
524
525 protected AbstractLinkedList() {
526 }
527
528
529
530
531
532
533 protected AbstractLinkedList(final Collection<? extends E> coll) {
534 init();
535 addAll(coll);
536 }
537
538 @Override
539 public boolean add(final E value) {
540 addLast(value);
541 return true;
542 }
543
544 @Override
545 public void add(final int index, final E value) {
546 final Node<E> node = getNode(index, true);
547 addNodeBefore(node, value);
548 }
549
550 @Override
551 public boolean addAll(final Collection<? extends E> coll) {
552 return addAll(size, coll);
553 }
554
555 @Override
556 public boolean addAll(final int index, final Collection<? extends E> coll) {
557 final Node<E> node = getNode(index, true);
558 for (final E e : coll) {
559 addNodeBefore(node, e);
560 }
561 return true;
562 }
563
564 public boolean addFirst(final E o) {
565 addNodeAfter(header, o);
566 return true;
567 }
568
569 public boolean addLast(final E o) {
570 addNodeBefore(header, o);
571 return true;
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 }