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