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