1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 package org.millscript.commons.util.list;
22
23 import java.io.IOException;
24 import java.io.ObjectInputStream;
25 import java.io.ObjectOutputStream;
26 import java.io.Serializable;
27
28 import org.millscript.commons.alert.alerts.Fault;
29 import org.millscript.commons.util.IList;
30 import org.millscript.commons.util.ListIterator;
31 import org.millscript.commons.util.alerts.ListIndexOutOfBoundsAlert;
32 import org.millscript.commons.util.iterator.AbstractListIterator;
33 import org.millscript.commons.util.iterator.ArrayListIterator;
34
35 /**
36 * This class provides a mutable <code>List</code> implementation which is
37 * backed by singly linked list. We don't need the complexity of a doubly
38 * linked list as our iterators do not allow reverse iteration.
39 */
40 public class ELinkedList< V > extends AbstractEList< V > implements Cloneable, Serializable {
41
42 /**
43 * This is the ID from the release 0.1.0 for future compatibility.
44 */
45 private static final long serialVersionUID = 2809326606072322642L;
46
47 /**
48 * This class provides a map interator implementation which iterates over
49 * this values in the specified linked list.
50 */
51 public static class ELinkedListIterator< V > extends AbstractListIterator< V > {
52
53 /**
54 * The current link in the iteration. If this is <code>null</code> it
55 * means that there is no such element in the iteration.
56 */
57 private Link< V > link;
58
59 /**
60 * The next link in the iteration. If this is <code>null</code> it
61 * means that there are no more elements in the iteration.
62 */
63 Link< V > nextLink;
64
65 /**
66 * Constructs a new singleton map iterator to iterate over the values
67 * in the specified linked list.
68 *
69 * @param obj the linked list whose values to iterate over
70 */
71 public ELinkedListIterator( final ELinkedList< V > list ) {
72 this.nextLink = list.firstLink;
73 }
74
75 /**
76 * Constructs a new singleton map iterator to iterate over the values
77 * in the specified link chain.
78 *
79 * @param first the link chain whose values to iterate over
80 */
81 ELinkedListIterator( final Link< V > first ) {
82 this.nextLink = first;
83 }
84
85 /**
86 * @see org.millscript.commons.util.iterator.AbstractMapIterator#advance()
87 */
88 @Override
89 protected void advance() {
90
91 super.advance();
92 this.link = this.nextLink;
93 if ( this.link == null ) {
94 this.nextLink = null;
95 } else {
96 this.nextLink = this.link.next;
97 }
98 }
99
100 /**
101 * @see org.millscript.commons.util.iterator.AbstractMapIterator#getValue()
102 */
103 @Override
104 protected V getValue() {
105 return this.link.current;
106 }
107
108 /**
109 * @see org.millscript.commons.util.MapIterator#hasNext()
110 */
111 public boolean hasNext() {
112 return this.nextLink != null;
113 }
114
115 /**
116 * @see org.millscript.commons.util.iterator.AbstractMapIterator#outOfBounds()
117 */
118 @Override
119 protected boolean outOfBounds() {
120 return this.link == null;
121 }
122
123 }
124
125 /**
126 * This class provides the link in the chain.
127 */
128 private static final class Link< V > {
129
130 /**
131 * The store for the object at this position in the list.
132 */
133 V current;
134
135 /**
136 * The next link in the chain.
137 */
138 Link< V > next;
139
140 /**
141 * Constructs a new link, for the specified object, with the given
142 * previous link in the chain.
143 *
144 * @param o the object this link represents
145 * @param n the next link in the chain or <code>null</code> if there is
146 * no such link
147 */
148 private Link( final V o, final Link< V > n ) {
149 this.current = o;
150 this.next = n;
151 }
152
153 }
154
155 /**
156 * This class implements a linked list which is backed by a shared slice of
157 * another linked list.
158 */
159 public static class SharedLinkedListList< V > extends AbstractIList< V > {
160
161 /**
162 * The first link in the shared part of the chain.
163 */
164 private final Link< V > firstLink;
165
166 /**
167 * The number of values in the list.
168 */
169 private final int size;
170
171 /**
172 * Constructs a new linked list which shared it's backing store with
173 * the specified list, starting and ending at the specified indices.
174 *
175 * @param first the first link in a chain we will share
176 * @param start the index(one based, inclusive) to start iterating from
177 * @param end the index(one based, inclusive) to stop iterating at
178 */
179 public SharedLinkedListList( final Link< V > first, final int start, final int end ) {
180 Link< V > link = first;
181 int outerListCount = 1;
182
183 for ( ; outerListCount < start; outerListCount++ ) {
184 link = link.next;
185 }
186 this.firstLink = link;
187 this.size = end - start + 1;
188 }
189
190 /**
191 * @see org.millscript.commons.util.list.AbstractIList#doGet(int)
192 */
193 @Override
194 protected V doGet( final int pos ) {
195 int currentPos = 1;
196 for ( Link< V > link = this.firstLink; link != null; link = link.next ) {
197 if ( pos == currentPos++ ) {
198 return link.current;
199 }
200 }
201 throw new Fault(
202 "Specified position is neither out of bounds or within the list!"
203 ).culprit( "index", pos ).decorate( this ).mishap();
204 }
205
206 /**
207 * @see org.millscript.commons.util.list.AbstractIList#doSlice(int, int, boolean)
208 */
209 @Override
210 @SuppressWarnings( "unchecked" )
211 protected IList< V > doSlice( final int first, final int last, final boolean share ) {
212 if ( share ) {
213 return new SharedLinkedListList< V >(
214 this.firstLink,
215 first,
216 last
217 );
218 } else {
219
220 final V[] objects = (V[]) new Object[ first - last + 1 ];
221 Link< V > link = this.firstLink;
222 int outerListCount = 1;
223
224 for ( ; outerListCount <= first; outerListCount++ ) {
225 link = link.next;
226 }
227
228 int newArrayPos = 0;
229 for ( ; link != null && outerListCount <= last; link = link.next, outerListCount++ ) {
230 objects[ newArrayPos++ ] = link.current;
231 }
232 return new IArrayList< V >( objects, true );
233 }
234 }
235
236 /**
237 * @see org.millscript.commons.util.IList#indexOf(java.lang.Object)
238 */
239 public int indexOf( final V value ) {
240 int pos = 1;
241 if ( value == null ) {
242 for ( Link< V > link = this.firstLink; link != null && pos <= this.size; link = link.next, pos++ ) {
243 if ( link.current == null ) {
244 return pos;
245 }
246 }
247 } else {
248 for ( Link< V > link = this.firstLink; link != null && pos <= this.size; link = link.next, pos++ ) {
249 if ( value.equals( link.current ) ) {
250 return pos;
251 }
252 }
253 }
254 return 0;
255 }
256
257 /**
258 * @see org.millscript.commons.util.IMap#iterator(boolean)
259 */
260 @SuppressWarnings( "unchecked" )
261 public ListIterator< V > iterator( final boolean share ) {
262 if ( share ) {
263 return new SharedLinkedListIterator< V >(
264 this.firstLink,
265 this.size()
266 );
267 } else {
268 final V[] objects = (V[]) new Object[ this.size() ];
269 int i = 0;
270 for ( Link< V > link = this.firstLink; link != null && i < objects.length; link = link.next, i++ ) {
271 objects[ i ] = link.current;
272 }
273 return new ArrayListIterator< V >( objects, true );
274 }
275 }
276
277 /**
278 * @see org.millscript.commons.util.IMap#size()
279 */
280 public int size() {
281 return this.size;
282 }
283
284 }
285
286 /**
287 * This class provides a map interator implementation which iterates over
288 * a shared poriton of the specified linked list.
289 */
290 public static class SharedLinkedListIterator< V > extends ELinkedListIterator< V > {
291
292 /**
293 * The number of values this iterator should return.
294 */
295 private final int size;
296
297 /**
298 * Constructs a new linked list map iterator to iterate over a shared
299 * portion of the values in the specified linked list.
300 *
301 * @param firstLink the first link in the iteration
302 * @param num the number of items this iterator should return
303 */
304 public SharedLinkedListIterator( final Link< V > firstLink, final int num ) {
305 super( firstLink );
306 this.size = num;
307 }
308
309 /**
310 * @see org.millscript.commons.util.iterator.AbstractMapIterator#advance()
311 */
312 @Override
313 protected void advance() {
314
315 super.advance();
316
317
318 if ( super.position == this.size ) {
319 super.nextLink = null;
320 }
321 }
322
323 }
324
325
326 /**
327 * Reutrns a copy of the specified chain, starting and ending at the
328 * specified indicies in the chain.
329 *
330 * @param c the chain to copy from
331 * @param i the index we are currently at
332 * @param start the index to start copying from the chain
333 * @param end the index to stop copying from the chain
334 * @return a copy of the supplied chain, starting and ending at the
335 * specified indicies
336 */
337 private static final < V > Link< V > copyChain( final Link< V > c, final int i, final int start, final int end ) {
338 if ( i < start ) {
339
340 return copyChain( c.next, i + 1, start, end );
341 } else if ( i > end ) {
342
343 return null;
344 } else {
345
346 return new Link< V >( c.current, copyChain( c.next, i + 1, start, end ) );
347 }
348 }
349
350
351 /**
352 * The first link in the chain.
353 */
354 transient Link< V > firstLink;
355
356 /**
357 * The last link in the chain.
358 */
359 private transient Link< V > lastLink;
360
361 /**
362 * The length of the chain.
363 */
364 private transient int chainLength;
365
366 /**
367 * Constructs a new empty mutable linked list.
368 */
369 public ELinkedList() {
370 this.firstLink = null;
371 this.chainLength = 0;
372 }
373
374 /**
375 * Constructs a new mutable linked list with the objects in the given
376 * array, in the same order.
377 *
378 * @param objects the backing object array with objects to populate the
379 * list with
380 */
381 public ELinkedList( final V[] objects ) {
382 if ( objects.length == 0 ) {
383 this.firstLink = null;
384 this.chainLength = 0;
385 } else {
386 this.firstLink = null;
387 for ( int i = objects.length - 1; i >= 0; i-- ) {
388 this.firstLink = new Link< V >( objects[ i ], this.firstLink );
389 }
390 this.chainLength = objects.length;
391
392 this.lastLink = this.firstLink;
393 while ( this.lastLink.next != null ) {
394 this.lastLink = this.lastLink.next;
395 }
396 }
397 }
398
399 /**
400 * Constructs a new mutable linked list with the objects in the given
401 * array, in the same order, starting and ending at the specified indices.
402 *
403 * @param objects the backing object array with objects to populate the
404 * list with
405 * @param start the index of the first element in the slice
406 * @param end the index of the last element in the slice. If end <
407 * start, the new list will be empty
408 */
409 public ELinkedList( final V[] objects, final int start, final int end ) {
410 if ( start > end ) {
411 this.firstLink = null;
412 this.chainLength = 0;
413 } else if ( start < 1 || start > objects.length ) {
414 throw new ListIndexOutOfBoundsAlert(
415 "First index in slice must be between 1 and the length of the array"
416 ).culprit(
417 "index",
418 start
419 ).decorate( objects ).mishap();
420 } else if ( end > objects.length ) {
421 throw new ListIndexOutOfBoundsAlert(
422 "Last index in slice must not be greater than the length of the array"
423 ).culprit(
424 "index",
425 end
426 ).decorate( objects ).mishap();
427 } else {
428 try {
429 this.firstLink = null;
430 for ( int i = end - 1; i >= start; i-- ) {
431 this.firstLink = new Link< V >( objects[ i ], this.firstLink );
432 }
433 this.chainLength = end - start + 1;
434
435 this.lastLink = this.firstLink;
436 while ( this.lastLink.next != null ) {
437 this.lastLink = this.lastLink.next;
438 }
439 } catch ( Exception ex ) {
440 throw new Fault(
441 "Failed to take a copy of the specified array slice"
442 ).setParentThrowable( ex ).mishap();
443 }
444 }
445 }
446
447 /**
448 * @see org.millscript.commons.util.EList#addFirst(java.lang.Object)
449 */
450 public void addFirst( final V value ) {
451 if ( this.firstLink == null ) {
452 this.firstLink = new Link< V >( value, null );
453 this.lastLink = this.firstLink;
454 } else {
455 this.firstLink = new Link< V >( value, this.firstLink );
456 }
457 this.chainLength++;
458 }
459
460 /**
461 * @see org.millscript.commons.util.EList#addLast(java.lang.Object)
462 */
463 public void addLast( final V value ) {
464 if ( this.lastLink == null ) {
465 this.firstLink = new Link< V >( value, null );
466 this.lastLink = this.firstLink;
467 } else {
468
469 this.lastLink.next = new Link< V >( value, null );
470 this.lastLink = this.lastLink.next;
471 }
472 this.chainLength++;
473 }
474
475 /**
476 * @see java.lang.Object#clone()
477 */
478 @Override
479 @SuppressWarnings( "unchecked" )
480 public Object clone() throws CloneNotSupportedException {
481 final ELinkedList<V> list = (ELinkedList<V>) super.clone();
482 Link< V > first = null;
483 Link< V > last = null;
484 int length = 0;
485 for ( Link< V > link = this.firstLink; link != null; link = link.next ) {
486 if ( first == null ) {
487 first = new Link< V >( link.current, null );
488 last = first;
489 } else {
490 last.next = new Link< V >( link.current, null );
491 last = last.next;
492 }
493 length++;
494 }
495 list.firstLink = first;
496 list.lastLink = last;
497 list.chainLength = length;
498 return list;
499 }
500
501 /**
502 * @see org.millscript.commons.util.EList#deleteAll()
503 */
504 public void deleteAll() {
505 this.firstLink = null;
506 this.chainLength = 0;
507 }
508
509 /**
510 * @see org.millscript.commons.util.EList#deleteFirst()
511 */
512 public void deleteFirst() {
513
514
515 if ( this.firstLink != null ) {
516 this.firstLink = this.firstLink.next;
517 this.chainLength--;
518 } else {
519 throw new ListIndexOutOfBoundsAlert(
520 "List must have at least one element before you can delete it's first one"
521 ).decorate( this ).mishap();
522 }
523 }
524
525 /**
526 * @see org.millscript.commons.util.EList#deleteLast()
527 */
528 public void deleteLast() {
529 if ( this.size() == 0 ) {
530 throw new ListIndexOutOfBoundsAlert(
531 "List must have at least one element before you can delete it's last one"
532 ).decorate( this ).mishap();
533 } else if ( this.size() == 1 ) {
534 this.firstLink = null;
535 this.lastLink = null;
536 this.chainLength = 0;
537 } else {
538
539 Link< V > penultimate = this.firstLink;
540 while ( penultimate.next != this.lastLink ) {
541 penultimate = penultimate.next;
542 }
543
544 penultimate.next = null;
545 this.lastLink = penultimate;
546 this.chainLength--;
547 }
548 }
549
550 /**
551 * @see org.millscript.commons.util.EList#deleteValue(java.lang.Object)
552 */
553 public void deleteValue( final V value ) {
554 if ( this.firstLink != null ) {
555 while ( this.firstLink != null && value == null ? this.firstLink.current == null : value.equals( this.firstLink.current ) ) {
556 this.firstLink = this.firstLink.next;
557 this.chainLength--;
558 }
559 for ( Link< V > previousLink = this.firstLink, link = this.firstLink.next; link != null; link = link.next ) {
560 if ( value == null ? link.current == null : value.equals( link.current ) ) {
561 previousLink.next = link.next;
562 this.chainLength--;
563 } else {
564 previousLink = link;
565 }
566 }
567 }
568 }
569
570 /**
571 * @see org.millscript.commons.util.list.AbstractEList#doDelete(int, java.lang.Object)
572 */
573 @Override
574 protected void doDelete( final int key, final V value ) {
575 if ( key == 1 ) {
576 if ( value == null ? this.firstLink.current == null : value.equals( this.firstLink.current ) ) {
577
578 this.firstLink = this.firstLink.next;
579 if ( this.chainLength == 1 ) {
580 this.lastLink = null;
581 }
582 this.chainLength--;
583 }
584 } else {
585 int currentPos = 2;
586 for ( Link< V > previousLink = this.firstLink, link = this.firstLink.next; link != null; previousLink = link, link = link.next ) {
587 if ( key == currentPos++ && value == null ? link.current == null : value.equals( link.current ) ) {
588 previousLink.next = link.next;
589 if ( link == this.lastLink ) {
590 this.lastLink = previousLink;
591 }
592 this.chainLength--;
593 break;
594 }
595 }
596 }
597 }
598
599 /**
600 * @see org.millscript.commons.util.list.AbstractEList#doDeleteKey(int)
601 */
602 @Override
603 protected void doDeleteKey( final int key ) {
604 if ( key == 1 ) {
605 this.deleteFirst();
606 } else if ( key == this.size() ) {
607 this.deleteLast();
608 } else {
609 int currentPos = 2;
610 for ( Link< V > previousLink = this.firstLink, link = this.firstLink.next; link != null; previousLink = link, link = link.next ) {
611 if ( key == currentPos++ ) {
612 previousLink.next = link.next;
613 if ( link == this.lastLink ) {
614 this.lastLink = previousLink;
615 }
616 this.chainLength--;
617 break;
618 }
619 }
620 }
621 }
622
623 /**
624 * @see org.millscript.commons.util.list.AbstractIList#doGet(int)
625 */
626 @Override
627 protected V doGet( final int pos ) {
628 int currentPos = 1;
629 for ( Link< V > link = this.firstLink; link != null; link = link.next ) {
630 if ( pos == currentPos++ ) {
631 return link.current;
632 }
633 }
634 throw new Fault(
635 "Specified position is neither out of bounds or within the list!"
636 ).culprit( "index", pos ).decorate( this ).mishap();
637 }
638
639 /**
640 * @see org.millscript.commons.util.list.AbstractEList#doRemoveSlice(int, int)
641 */
642 @Override
643 protected void doRemoveSlice( final int first, final int last ) {
644
645
646 if ( first == 1 ) {
647
648 if ( last == this.size() ) {
649
650 this.firstLink = null;
651 this.lastLink = null;
652 this.chainLength = 0;
653 } else {
654
655
656 Link< V > lastLinkToRemove = this.firstLink.next;
657 for ( int currentPos = 2; currentPos != last; currentPos++ ) {
658 lastLinkToRemove = lastLinkToRemove.next;
659 }
660
661 this.firstLink = lastLinkToRemove.next;
662 this.chainLength -= last;
663
664 }
665 } else {
666
667
668
669 int currentPos = 2;
670 Link< V > preFirstLink = this.firstLink;
671 for ( ; currentPos < first ; currentPos++ ) {
672 preFirstLink = preFirstLink.next;
673 }
674
675
676 if ( last == this.size() ) {
677 preFirstLink.next = null;
678 this.lastLink = preFirstLink;
679 this.chainLength = first - 1;
680 } else {
681
682 Link< V > lastLinkToRemove = preFirstLink;
683 for ( ; last != currentPos; currentPos++ ) {
684 lastLinkToRemove = lastLinkToRemove.next;
685 }
686
687
688 preFirstLink.next = lastLinkToRemove.next.next;
689 this.chainLength -= last - first + 1;
690
691 }
692 }
693 }
694
695 /**
696 * @see org.millscript.commons.util.list.AbstractIList#doSlice(int, int, boolean)
697 */
698 @Override
699 @SuppressWarnings( "unchecked" )
700 protected IList< V > doSlice( final int first, final int last, boolean share ) {
701 if ( share ) {
702 return new SharedLinkedListList< V >( this.firstLink, first, last );
703 } else {
704
705 final V[] objects = (V[]) new Object[ first - last + 1 ];
706 Link< V > link = this.firstLink;
707 int outerListCount = 1;
708
709 for ( ; outerListCount <= first; outerListCount++ ) {
710 link = link.next;
711 }
712
713 int newArrayPos = 0;
714 for ( ; link != null && outerListCount <= last; link = link.next, outerListCount++ ) {
715 objects[ newArrayPos++ ] = link.current;
716 }
717 return new IArrayList< V >( objects, true );
718 }
719 }
720
721 /**
722 * @see org.millscript.commons.util.list.AbstractUList#doUpdate(int, java.lang.Object)
723 */
724 @Override
725 protected void doUpdate( final int key, final V value ) {
726
727 if ( key < 1 || key > this.chainLength ) {
728 throw new ListIndexOutOfBoundsAlert().culprit(
729 "index",
730 key
731 ).decorate( this ).mishap();
732 }
733 int currentPos = 1;
734 for ( Link< V > link = this.firstLink; link != null; link = link.next ) {
735 if ( key == currentPos++ ) {
736 link.current = value;
737 }
738 }
739 throw new Fault(
740 "Specified position is neither out of bounds or within the list!"
741 ).culprit( "index", key ).decorate( this ).mishap();
742 }
743
744 /**
745 * @see org.millscript.commons.util.IList#indexOf(java.lang.Object)
746 */
747 public int indexOf( final V value ) {
748 int currentPos = 1;
749 for ( Link< V > link = this.firstLink; link != null; link = link.next, currentPos++ ) {
750 if ( value == null ? link.current == null : value.equals( link.current ) ) {
751 return currentPos;
752 }
753 }
754 return 0;
755 }
756
757 /**
758 * @see org.millscript.commons.util.EList#insert(int, java.lang.Object)
759 */
760 public void insert( final int pos, final V value ) {
761
762 if ( pos < 1 || pos > this.chainLength + 1 ) {
763 throw new ListIndexOutOfBoundsAlert().culprit(
764 "index",
765 pos
766 ).decorate( this ).mishap();
767 }
768 if ( pos == 1 ) {
769 this.addFirst( value );
770 } else if ( pos > this.size() ) {
771 this.addLast( value );
772 } else {
773 int currentPos = 2;
774 for ( Link< V > link = this.firstLink; link != null; link = link.next, currentPos++ ) {
775 if ( pos == currentPos ) {
776 link.next = new Link< V >( value, link.next );
777 this.chainLength++;
778 return;
779 }
780 }
781 throw new Fault(
782 "Specified position is neither out of bounds or within the list!"
783 ).culprit( "index", pos ).decorate( this ).mishap();
784 }
785 }
786
787 /**
788 * @see org.millscript.commons.util.IMap#iterator(boolean)
789 */
790 @SuppressWarnings( "unchecked" )
791 public ListIterator< V > iterator( final boolean share ) {
792
793
794
795
796 if ( share ) {
797 return new ELinkedListIterator< V >( this );
798 } else {
799 final V[] objects = (V[]) new Object[ this.size() ];
800 int i = 0;
801 for ( Link< V > link = this.firstLink; link != null; link = link.next, i++ ) {
802 objects[ i ] = link.current;
803 }
804 return new ArrayListIterator< V >( objects, true );
805 }
806 }
807
808 /**
809 * Reads this object from the specified {@link ObjectInputStream}.
810 *
811 * @param stream the {@link ObjectInputStream} to read the objects data
812 * from
813 * @serialData Reads the default object, followed by the integer
814 * number of elements and then the sequence of elements pairs
815 * @throws ClassNotFoundException if a required class cannot be found
816 * @throws IOException if something goes wrong during the
817 * deserialization process
818 */
819 @SuppressWarnings( "unchecked" )
820 private void readObject( final ObjectInputStream stream ) throws ClassNotFoundException, IOException {
821
822 stream.defaultReadObject();
823
824 final int size = stream.readInt();
825
826 this.firstLink = null;
827 for ( int i = 0; i < size; i++ ) {
828 if ( this.lastLink == null ) {
829 this.firstLink = new Link< V >( (V) stream.readObject(), null );
830 this.lastLink = this.firstLink;
831 } else {
832
833 this.lastLink.next = new Link< V >( (V) stream.readObject(), null );
834 this.lastLink = this.lastLink.next;
835 }
836 this.chainLength++;
837 }
838 }
839
840 /**
841 * @see org.millscript.commons.util.IMap#size()
842 */
843 public int size() {
844 return this.chainLength;
845 }
846
847 /**
848 * Writes this object to the specified {@link ObjectOutputStream}.
849 *
850 * @param stream the {@link ObjectOutputStream} to write this object to
851 * @serialData Writes the default object, followed by the integer
852 * number of elements and then the sequence of elements pairs
853 * @throws IOException if something goes wrong during the
854 * serialization process
855 */
856 private void writeObject( final ObjectOutputStream stream ) throws IOException {
857
858 stream.defaultWriteObject();
859
860 stream.writeInt( this.size() );
861
862 for ( ListIterator< V > it = this.iterator( true ); it.hasNext(); ) {
863 stream.writeObject( it.nextValue() );
864 }
865 }
866
867 }