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.Serializable;
24
25 import org.millscript.commons.alert.alerts.Fault;
26 import org.millscript.commons.util.IList;
27 import org.millscript.commons.util.ListIterator;
28 import org.millscript.commons.util.alerts.ListIndexOutOfBoundsAlert;
29 import org.millscript.commons.util.iterator.AbstractListIterator;
30 import org.millscript.commons.util.iterator.ArrayListIterator;
31
32 /**
33 * This class provides an immutable <code>List</code> implementation which is
34 * backed by singly linked list. We don't need the complexity of a doubly
35 * linked list as our iterators do not allow reverse iteration.
36 */
37 public class ILinkedList< V > extends AbstractIList< V > implements Cloneable, Serializable {
38
39 /**
40 * This is the ID from the release 0.1.0 for future compatibility.
41 */
42 private static final long serialVersionUID = -6204952779410669775L;
43
44 /**
45 * This class provides the link in the chain.
46 */
47 private static final class Link< V > implements Serializable {
48
49 /**
50 * This is the ID from the release 0.1.0 for future compatibility.
51 */
52 private static final long serialVersionUID = -5445309655157694312L;
53
54 /**
55 * The store for the object at this position in the list.
56 */
57 final V current;
58
59 /**
60 * The next link in the chain.
61 */
62 final Link< V > next;
63
64 /**
65 * Constructs a new link, for the specified object, with the given
66 * previous link in the chain.
67 *
68 * @param o the object this link represents
69 * @param n the next link in the chain or <code>null</code> if there is
70 * no such link
71 */
72 private Link( final V o, final Link< V > n ) {
73 this.current = o;
74 this.next = n;
75 }
76
77 }
78
79 /**
80 * This class provides a map interator implementation which iterates over
81 * this values in the specified linked list.
82 */
83 public static class LinkedListIterator< V > extends AbstractListIterator< V > {
84
85 /**
86 * The current link in the iteration. If this is <code>null</code> it
87 * means that there is no such element in the iteration.
88 */
89 private Link< V > link;
90
91 /**
92 * The next link in the iteration. If this is <code>null</code> it
93 * means that there are no more elements in the iteration.
94 */
95 private Link< V > nextLink;
96
97 /**
98 * Constructs a new linked list map iterator to iterate over the values
99 * in the specified linked list.
100 *
101 * @param list the linked list whose values to iterate over
102 */
103 public LinkedListIterator( final ILinkedList< V > list ) {
104 this.nextLink = list.chain;
105 }
106
107 /**
108 * Constructs a new singleton map iterator to iterate over the values
109 * in the specified chain.
110 *
111 * @param obj the chain to iterate over
112 */
113 LinkedListIterator( final Link< V > firstList ) {
114 this.nextLink = firstList;
115 }
116
117 /**
118 * @see org.millscript.commons.util.iterator.AbstractMapIterator#advance()
119 */
120 @Override
121 protected void advance() {
122
123 super.advance();
124 this.link = this.nextLink;
125 if ( this.link == null ) {
126 this.nextLink = null;
127 } else {
128 this.nextLink = this.link.next;
129 }
130 }
131
132 /**
133 * @see org.millscript.commons.util.iterator.AbstractMapIterator#getValue()
134 */
135 @Override
136 protected V getValue() {
137 return this.link.current;
138 }
139
140 /**
141 * @see org.millscript.commons.util.MapIterator#hasNext()
142 */
143 public boolean hasNext() {
144 return this.nextLink != null;
145 }
146
147 /**
148 * @see org.millscript.commons.util.iterator.AbstractMapIterator#outOfBounds()
149 */
150 @Override
151 protected boolean outOfBounds() {
152 return this.link == null;
153 }
154
155 }
156
157 /**
158 * This class implements a linked list which is backed by a shared slice of
159 * another linked list.
160 */
161 public static class ISharedLinkedList< V > extends AbstractIList< V > {
162
163 /**
164 * The first link in the shared part of the chain.
165 */
166 private final Link< V > firstLink;
167
168 /**
169 * The number of values in the list.
170 */
171 private final int size;
172
173 /**
174 * Constructs a new linked list which shared it's backing store with
175 * the specified list, starting and ending at the specified indices.
176 *
177 * @param list the link whose backing store to share
178 * @param start the index(one based, inclusive) to start iterating from
179 * @param end the index(one based, inclusive) to stop iterating at
180 */
181 public ISharedLinkedList( final Link< V > first, final int start, final int end ) {
182 Link< V > link = first;
183 int outerListCount = 1;
184
185 for ( ; outerListCount < start; outerListCount++ ) {
186 link = link.next;
187 }
188 this.firstLink = link;
189 this.size = end - start + 1;
190 }
191
192 /**
193 * @see org.millscript.commons.util.list.AbstractIList#doGet(int)
194 */
195 @Override
196 protected V doGet( final int pos ) {
197 int currentPos = 1;
198 for ( Link< V > link = this.firstLink; link != null; link = link.next ) {
199 if ( pos == currentPos++ ) {
200 return link.current;
201 }
202 }
203 throw new Fault(
204 "Specified position is neither out of bounds or within the list!"
205 ).culprit( "index", pos ).decorate( this ).mishap();
206 }
207
208 /**
209 * @see org.millscript.commons.util.list.AbstractIList#doSlice(int, int, boolean)
210 */
211 @Override
212 @SuppressWarnings( "unchecked" )
213 protected IList< V > doSlice( final int first, final int last, final boolean share ) {
214 if ( share ) {
215 return new ISharedLinkedList< V >(
216 this.firstLink,
217 first,
218 last
219 );
220 } else {
221
222 final V[] objects = (V[]) new Object[ first - last + 1 ];
223 Link< V > link = this.firstLink;
224 int outerListCount = 1;
225
226 for ( ; outerListCount <= first; outerListCount++ ) {
227 link = link.next;
228 }
229
230 int newArrayPos = 0;
231 for ( ; link != null && outerListCount <= last; link = link.next, outerListCount++ ) {
232 objects[ newArrayPos++ ] = link.current;
233 }
234 return new IArrayList< V >( objects, true );
235 }
236 }
237
238 /**
239 * @see org.millscript.commons.util.IList#indexOf(java.lang.Object)
240 */
241 public int indexOf( final V value ) {
242 int pos = 1;
243 if ( value == null ) {
244 for ( Link< V > link = this.firstLink; link != null && pos <= this.size; link = link.next, pos++ ) {
245 if ( link.current == null ) {
246 return pos;
247 }
248 }
249 } else {
250 for ( Link< V > link = this.firstLink; link != null && pos <= this.size; link = link.next, pos++ ) {
251 if ( value.equals( link.current ) ) {
252 return pos;
253 }
254 }
255 }
256 return 0;
257 }
258
259 /**
260 * @see org.millscript.commons.util.IMap#iterator(boolean)
261 */
262 @SuppressWarnings( "unchecked" )
263 public ListIterator< V > iterator( final boolean share ) {
264 if ( share ) {
265 return new ISharedLinkedListIterator< V >(
266 this.firstLink,
267 this.size()
268 );
269 } else {
270 final V[] objects = (V[]) new Object[ this.size() ];
271 int i = 0;
272 for ( Link< V > link = this.firstLink; link != null && i < objects.length; link = link.next, i++ ) {
273 objects[ i ] = link.current;
274 }
275 return new ArrayListIterator< V >( objects, true );
276 }
277 }
278
279 /**
280 * @see org.millscript.commons.util.IMap#size()
281 */
282 public int size() {
283 return this.size;
284 }
285
286 }
287
288 /**
289 * This class provides a map interator implementation which iterates over
290 * a shared poriton of the specified linked list.
291 */
292 public static class ISharedLinkedListIterator< V > extends AbstractListIterator< V > {
293
294 /**
295 * The current link in the iteration. If this is <code>null</code> it
296 * means that there is no such element in the iteration.
297 */
298 private Link< V > link;
299
300 /**
301 * The next link in the iteration. If this is <code>null</code> it
302 * means that there are no more elements in the iteration.
303 */
304 private Link< V > nextLink;
305
306 /**
307 * The number of values this iterator should return.
308 */
309 private final int size;
310
311 /**
312 * Constructs a new linked list map iterator to iterate over a shared
313 * portion of the values in the specified linked list.
314 *
315 * @param firstLink the first link in the iteration
316 * @param num the number of items this iterator should return
317 */
318 public ISharedLinkedListIterator( final Link< V > firstLink, final int num ) {
319 this.nextLink = firstLink;
320 this.size = num;
321 }
322
323 /**
324 * @see org.millscript.commons.util.iterator.AbstractMapIterator#advance()
325 */
326 @Override
327 protected void advance() {
328
329 super.advance();
330 this.link = this.nextLink;
331 if ( this.link == null ) {
332 this.nextLink = null;
333 } else {
334 this.nextLink = this.link.next;
335 }
336 }
337
338 /**
339 * @see org.millscript.commons.util.iterator.AbstractMapIterator#getValue()
340 */
341 @Override
342 protected V getValue() {
343 return this.link.current;
344 }
345
346 /**
347 * @see org.millscript.commons.util.MapIterator#hasNext()
348 */
349 public boolean hasNext() {
350 return super.position < this.size;
351 }
352
353 /**
354 * @see org.millscript.commons.util.iterator.AbstractMapIterator#outOfBounds()
355 */
356 @Override
357 protected boolean outOfBounds() {
358 return super.position == 0 || super.position > this.size;
359 }
360
361 }
362
363 /**
364 * Reutrns a copy of the specified chain, starting and ending at the
365 * specified indicies in the chain.
366 *
367 * @param c the chain to copy from
368 * @param i the index we are currently at
369 * @param start the index to start copying from the chain
370 * @param end the index to stop copying from the chain
371 * @return a copy of the supplied chain, starting and ending at the
372 * specified indicies
373 */
374 private static final < V > Link< V > copyChain( final Link< V > c, final int i, final int start, final int end ) {
375 if ( i < start ) {
376
377 return copyChain( c.next, i + 1, start, end );
378 } else if ( i > end ) {
379
380 return null;
381 } else {
382
383 return new Link< V >( c.current, copyChain( c.next, i + 1, start, end ) );
384 }
385 }
386
387
388 /**
389 * The first link in the chain.
390 */
391 final Link< V > chain;
392
393 /**
394 * The length of the chain.
395 */
396 private final int chainLength;
397
398 /**
399 * Constructs a new empty immutable linked list.
400 */
401 public ILinkedList() {
402 this.chain = null;
403 this.chainLength = 0;
404 }
405
406 /**
407 * Constructs a new immutable linked list with the objects in the given
408 * array, in the same order.
409 *
410 * @param objects the backing object array with objects to populate the
411 * list with
412 */
413 public ILinkedList( final V[] objects ) {
414 if ( objects.length == 0 ) {
415 this.chain = null;
416 this.chainLength = 0;
417 } else {
418 Link< V > currentLink = null;
419 for ( int i = objects.length - 1; i >= 0; i-- ) {
420 currentLink = new Link< V >( objects[ i ], currentLink );
421 }
422 this.chain = currentLink;
423 this.chainLength = objects.length;
424 }
425 }
426
427 /**
428 * Constructs a new immutable linked list with the objects in the given
429 * array, in the same order, starting and ending at the specified indices.
430 *
431 * @param objects the backing object array with objects to populate the
432 * list with
433 * @param start the index of the first element in the slice
434 * @param end the index of the last element in the slice. If end <
435 * start, the new list will be empty
436 */
437 public ILinkedList( final V[] objects, final int start, final int end ) {
438 if ( start > end ) {
439 this.chain = null;
440 this.chainLength = 0;
441 } else if ( start < 1 || start > objects.length ) {
442 throw new ListIndexOutOfBoundsAlert(
443 "First index in slice must be between 1 and the length of the array"
444 ).culprit(
445 "index",
446 start
447 ).decorate( objects ).mishap();
448 } else if ( end > objects.length ) {
449 throw new ListIndexOutOfBoundsAlert(
450 "Last index in slice must not be greater than the length of the array"
451 ).culprit(
452 "index",
453 end
454 ).decorate( objects ).mishap();
455 } else {
456 try {
457 Link< V > currentLink = null;
458 for ( int i = end - 1; i >= start; i-- ) {
459 currentLink = new Link< V >( objects[ i ], currentLink );
460 }
461 this.chain = currentLink;
462 this.chainLength = end - start + 1;
463 } catch ( Exception ex ) {
464 throw new Fault(
465 "Failed to take a copy of the specified array slice"
466 ).setParentThrowable( ex ).mishap();
467 }
468 }
469 }
470
471 /**
472 * @see java.lang.Object#clone()
473 */
474 @Override
475 public Object clone() throws CloneNotSupportedException {
476
477
478 return super.clone();
479 }
480
481 /**
482 * @see org.millscript.commons.util.list.AbstractIList#doGet(int)
483 */
484 @Override
485 protected V doGet( final int pos ) {
486 int currentPos = 1;
487 for ( Link< V > link = this.chain; link != null; link = link.next ) {
488 if ( pos == currentPos++ ) {
489 return link.current;
490 }
491 }
492 throw new Fault(
493 "Specified position is neither out of bounds or within the list!"
494 ).culprit( "index", pos ).decorate( this ).mishap();
495 }
496
497 /**
498 * @see org.millscript.commons.util.list.AbstractIList#doSlice(int, int, boolean)
499 */
500 @Override
501 @SuppressWarnings( "unchecked" )
502 protected IList< V > doSlice( final int first, final int last, final boolean share ) {
503 if ( share ) {
504 return new ISharedLinkedList< V >( this.chain, first, last );
505 } else {
506
507 final V[] objects = (V[]) new Object[ first - last + 1 ];
508 Link< V > link = this.chain;
509 int outerListCount = 1;
510
511 for ( ; outerListCount <= first; outerListCount++ ) {
512 link = link.next;
513 }
514
515 int newArrayPos = 0;
516 for ( ; link != null && outerListCount <= last; link = link.next, outerListCount++ ) {
517 objects[ newArrayPos++ ] = link.current;
518 }
519 return new IArrayList< V >( objects, true );
520 }
521 }
522
523 /**
524 * @see org.millscript.commons.util.IList#indexOf(java.lang.Object)
525 */
526 public int indexOf( final V value ) {
527 int currentPos = 1;
528 for ( Link< V > link = this.chain; link != null; link = link.next, currentPos++ ) {
529 if ( value == null ? link.current == null : value.equals( link.current ) ) {
530 return currentPos;
531 }
532 }
533 return 0;
534 }
535
536 /**
537 * @see org.millscript.commons.util.IMap#iterator(boolean)
538 */
539 @SuppressWarnings( "unchecked" )
540 public ListIterator< V > iterator( final boolean share ) {
541 if ( share ) {
542 return new LinkedListIterator< V >( this );
543 } else {
544 final V[] objects = (V[]) new Object[ this.size() ];
545 int i = 0;
546 for ( Link< V > link = this.chain; link != null; link = link.next, i++ ) {
547 objects[ i ] = link.current;
548 }
549 return new ArrayListIterator< V >( objects, true );
550 }
551 }
552
553 /**
554 * @see org.millscript.commons.util.IMap#size()
555 */
556 public int size() {
557 return this.chainLength;
558 }
559
560 }