1
2 package eu.simuline.util;
3
4 import java.util.List;
5 import java.util.Collection;
6 import java.util.Iterator;
7
8 /**
9 * An ordered cyclic list.
10 * The user of this interface has precise control
11 * over where in the list each element is inserted.
12 * The user can access elements by their integer index
13 * (position in the list) which is modulo its length,
14 * and search for elements in the list.
15 * <p>
16 * Unlike sets, lists typically allow duplicate elements.
17 * More formally,
18 * lists typically allow pairs of elements <code>e1</code> and <code>e2</code>
19 * such that <code>e1.equals(e2)</code>,
20 * and they typically allow multiple null elements
21 * if they allow null elements at all.
22 * It is not inconceivable
23 * that someone might wish to implement a list that prohibits duplicates,
24 * by throwing runtime exceptions when the user attempts to insert them,
25 * but we expect this usage to be rare.
26 * <p>
27 * The <code>CyclicList</code> interface places additional stipulations,
28 * beyond those specified in the <code>Collection</code> interface,
29 * on the contracts of the
30 * <code>iterator</code>, <code>add</code>,
31 * <code>remove</code>, <code>equals</code>,
32 * and <code>hashCode</code> methods.
33 * On the other hand, some methods do not make sense (such as add)
34 * and are hence not supported.
35 * This is the reason why <code>CyclicList</code>
36 * does not extend <code>Collection</code>.
37 * <p>
38 * The <code>CyclicList</code> interface
39 * provides four methods for positional (indexed) access to list elements.
40 * <code>CyclicLists</code> (like Java arrays) are zero based.
41 * Note that these operations may execute
42 * in time proportional to the index value
43 * for some implementations
44 * (the <code>LinkedCyclicList</code> class, for example).
45 * Thus, iterating over the elements in a list is typically
46 * preferable to indexing through it
47 * if the caller does not know the implementation.
48 * <p>
49 * The <code>CyclicList</code> interface provides a special iterator,
50 * called a <code>CyclicIterator</code>,
51 * that allows element insertion and replacement,
52 * and bidirectional access similar to the normal operations that the
53 * <code>ListIterator</code> interface provides.
54 * A method is provided to obtain a <code>CyclicIterator</code>
55 * that starts at a specified position in the list.
56 * <p>
57 * The <code>CyclicList</code> interface
58 * provides two methods to search for a specified object.
59 * From a performance standpoint,
60 * these methods should be used with caution.
61 * In many implementations they will perform costly linear searches.
62 * <p>
63 * The <code>CyclicList</code> interface
64 * provides two methods to efficiently insert and
65 * remove multiple elements at an arbitrary point in the list.
66 * <p>
67 * Note: While it is permissible for lists to contain themselves as elements,
68 * extreme caution is advised:
69 * the <code>equals</code> and <code>hashCode</code>
70 * methods are no longer well defined on a such a list.
71 *
72 * @param <E>
73 * the class of the elements of this list.
74 *
75 * @author <a href="mailto:ernst.reissner@simuline.eu">Ernst Reissner</a>
76 * @version 1.0
77 */
78 public interface CyclicList<E> extends Collection<E> {
79
80 // ***** to be removed later.
81 int shiftIndex(int index);
82
83 /**
84 * Returns the number of elements in this list.
85 * If this list contains more than <code>Integer.MAX_VALUE</code> elements,
86 * returns <code>Integer.MAX_VALUE</code>.
87 *
88 * @return
89 * the number of elements in this list.
90 */
91 int size();
92
93 /**
94 * Returns <code>true</code> iff this list contains no elements.
95 *
96 * @return <code>true</code> iff this list contains no elements.
97 */
98 boolean isEmpty();
99
100 /**
101 * Returns the inverse of this cyclic list:
102 * the list with inverse order.
103 *
104 * @return
105 * The list with the same entries but inverse order.
106 */
107 CyclicList<E> getInverse();
108
109 /**
110 *
111 * Returns <code>true</code> if this list contains the specified element.
112 * More formally, returns <code>true</code>
113 * if and only if this list contains at least one element <code>e</code>
114 * such that
115 * <code>(o==null ? e==null : o.equals(e))</code>.
116 *
117 * @param obj element whose presence in this list is to be tested.
118 * @return <code>true</code> if this list contains the specified element.
119 */
120 boolean contains(Object obj);
121
122 //boolean containsAll(Collection<? extends E> coll);
123
124 /**
125 * Returns {@link #cyclicIterator(int) cyclicIterator(index)}
126 * for some unspecified <code>index</code>.
127 *
128 * @return
129 * {@link #cyclicIterator(int) cyclicIterator(index)}
130 * for some unspecified <code>index</code>.
131 */
132 // defined already in Collection
133 Iterator<E> iterator();
134
135 /**
136 * Returns a <code>CyclicIterator</code>
137 * of the elements in this list (in proper sequence),
138 * starting at the specified position in this list.
139 * The specified index indicates the first element
140 * that would be returned
141 * by an initial call to the <code>next</code> method.
142 * An initial call to the <code>previous</code> method
143 * would return the element with the specified index minus one
144 * (modulo the length of this cyclic list).
145 *
146 * @param index
147 * index of first element to be returned from the list iterator
148 * (by a call to the <code>next</code> method).
149 * This is interpreted modulo the length of this cyclic list.
150 * Any index (even negative ones) are valid.
151 * @return
152 * a cyclic iterator of the elements in this list
153 * (in proper sequence),
154 * starting at the specified position in this list.
155 */
156 CyclicIterator<E> cyclicIterator(int index);
157
158 /**
159 * Returns an array containing all of the elements in this cyclic list
160 * in proper sequence, i.e. in the ordering
161 * returned by the iterator given by {@link #cyclicIterator(int)}.
162 * Modifying the return value
163 * does not modify this <code>CyclicList</code>.
164 *
165 * @param index
166 * index of the element in the cyclic list
167 * which comes first in the array returned.
168 * This is interpreted modulo the length of this cyclic list.
169 * Any index (even negative ones) are valid.
170 * @return
171 * an array containing all of the elements in this list
172 * in proper sequence.
173 */
174 Object[] toArray(int index);
175
176 /**
177 * Returns an array containing all of the elements in this cyclic list
178 * in proper sequence, i.e. in the ordering
179 * returned by the iterator given by {@link #cyclicIterator(int)};
180 * the runtime type of the returned array is that of the specified array.
181 * Modifying the return value
182 * does not modify this <code>CyclicList</code>.
183 *
184 * @param index
185 * index of the element in the cyclic list
186 * which comes first in the array returned.
187 * This is interpreted modulo the length of this cyclic list.
188 * Any index (even negative ones) are valid.
189 * @param array
190 * the array into which the elements of this list are to be stored,
191 * if it is big enough;
192 * otherwise, a new array of the same runtime type
193 * is allocated for this purpose.
194 * @return
195 * an array containing all of the elements in this list
196 * in proper sequence.
197 * @throws ArrayStoreException
198 * if the runtime type of the specified array
199 * is not a supertype of the runtime type
200 * of every element in this list.
201 */
202 <E> E[] toArray(int index, E[] array);
203
204 /**
205 * Returns a List containing all of the elements in this cyclic list
206 * in proper sequence.
207 * Modifying the return value does not modify this CyclicList.
208 *
209 * @param index
210 * index of the element in the cyclic list
211 * which comes first in the List returned.
212 * This is interpreted modulo the length of this cyclic list.
213 * Any index (even negative ones) are valid.
214 * @return
215 * a list containing all of the elements in this cyclic list
216 * in proper sequence.
217 * @throws ArrayStoreException
218 * if the runtime type of the specified array
219 * is not a supertype of the runtime type
220 * of every element in this list.
221 */
222 List<E> asList(int index);
223
224 List<E> asList();
225
226 /**
227 * Returns a cyclic permutation <code>p</code> of this cyclic list.
228 *
229 * @param num
230 * an <code>int</code> value.
231 * @return
232 * a cyclic permutation <code>p</code> of this cyclic list.
233 * It satisfies <code>p.size() == this.size()</code> and
234 * <code>p.get(i) == this.get(i+num)</code>.
235 */
236 CyclicList<E> cycle(int num);
237
238 // Modification Operations
239
240 /**
241 * Removes all of the elements from this list (optional operation).
242 * This list will be empty after this call returns
243 * (unless it throws an exception).
244 *
245 * @throws UnsupportedOperationException
246 * if the <code>clear</code> method
247 * is not supported by this cyclic list implementation.
248 */
249 void clear();
250
251 // not supported by list either
252 /*
253 * Returns a clone of this <code>CyclicArrayList</code>.
254 * This includes copying <code>vertices</code>.
255 *
256 * @return
257 * a clone of this <code>CyclicList</code>.
258 * This includes copying <code>vertices</code>.
259 */
260 //public Object clone();
261
262 /**
263 * Compares the specified object with this cyclic list for equality.
264 * Returns <code>true</code>
265 * if and only if the specified object is also a cyclic list,
266 * both lists have the same size and
267 * all corresponding pairs of elements the two lists are <i>equal</i>.
268 * (Two elements <code>e1</code> and <code>e2</code> are <i>equal</i>
269 * if <code>(e1==null ? e2==null : e1.equals(e2))</code>.)
270 * In other words, two cyclic lists are defined to be
271 * equal if they contain the same elements in the same order
272 * according to their iterators.
273 * This definition ensures that the equals method works properly
274 * across different implementations
275 * of the <code>CyclicList</code> interface.
276 *
277 * @param obj
278 * the object to be compared for equality with this list.
279 * @return
280 * <code>true</code> if the specified object is equal to this list.
281 * @see #equalsCyclic(Object)
282 */
283 boolean equals(Object obj);
284
285 /**
286 * Compares the specified object with this cyclic list for equality.
287 * Returns <code>true</code>
288 * if and only if the specified object is also a cyclic list,
289 * both lists have the same size,
290 * and, up to a cyclic permutation,
291 * all corresponding pairs of elements the two lists are <i>equal</i>.
292 * (Two elements <code>e1</code> and <code>e2</code> are <i>equal</i>
293 * if <code>(e1==null ? e2==null : e1.equals(e2))</code>.)
294 * In other words, two lists are defined to be
295 * equal if they contain the same elements in the same order
296 * up to a cyclic permutation.
297 * This definition ensures that the equals method works properly
298 * across different implementations
299 * of the <code>CyclicList</code> interface.
300 *
301 * @param obj
302 * the object to be compared for equality with this list.
303 * @return
304 * <code>true</code> if the specified object is equal to this list.
305 * @see #equals(Object)
306 */
307 boolean equalsCyclic(Object obj);
308
309 /**
310 * Returns the hash code value for this cyclic list.
311 * The hash code of a list
312 * is defined to be the result of the following calculation:
313 * <pre>
314 * hashCode = 1;
315 * Iterator i = list.iterator();
316 * while (i.hasNext()) {
317 * Object obj = i.next();
318 * hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
319 * }
320 * </pre>
321 * This ensures that <code>list1.equals(list2)</code> implies that
322 * <code>list1.hashCode()==list2.hashCode()</code> for any two lists,
323 * <code>list1</code> and <code>list2</code>,
324 * as required by the general contract of <code>Object.hashCode</code>.
325 *
326 * @return the hash code value for this list.
327 * @see #equals(Object)
328 * @see #hashCodeCyclic()
329 */
330 int hashCode();
331
332 /**
333 * Returns a hash code value for this cyclic list
334 * which is invariant under cyclic permutation.
335 * This kind of hash code is conform with {@link #equalsCyclic(Object)}
336 * and with {@link #equals(Object)},
337 * i.e. equals objects have equal hash codes.
338 * The hash code of this cyclic list
339 * is the hash code of the underlying set.
340 * This ensures that <code>list1.equalsCyclic(list2)</code> implies that
341 * <code>list1.hashCodeCyclic()==list2.hashCodeCyclic()</code>
342 * for any two lists <code>list1</code> and <code>list2</code>.
343 *
344 * @return the "cyclic hash code" value for this list.
345 * @see #hashCode()
346 * @see #equalsCyclic(Object)
347 */
348 int hashCodeCyclic();
349
350 // Positional Access Operations
351
352 /**
353 * Returns the element at the specified position in this list.
354 *
355 * @param index
356 * index of element to return.
357 * This is interpreted modulo the length of this cyclic list.
358 * Any index (even negative ones) are valid.
359 * @return
360 * the element at the specified position in this list.
361 */
362 E get(int index);
363
364 /**
365 * Replaces the element at the specified position in this list
366 * with the specified element (optional operation).
367 *
368 * @param index
369 * index of element to replace.
370 * @param element
371 * element to be stored at the specified position.
372 * This is interpreted modulo the length of this cyclic list.
373 * Any index (even negative ones) are valid.
374 * @return
375 * the element previously at the specified position.
376 *
377 * @throws UnsupportedOperationException
378 * if the <code>set</code> method is not supported by this list.
379 * @throws ClassCastException
380 * if the class of the specified element
381 * prevents it from being added to this list.
382 * @throws IllegalArgumentException
383 * if some aspect of the specified element
384 * prevents it from being added to this list.
385 */
386 E set(int index, E element);
387
388 /**
389 * Replaces the element at the specified position in this list
390 * with the cyclic list of the specified iterator (optional operation).
391 * Places the elements of that list as returned by <code>iter.next</code>
392 * in this list.
393 *
394 * @param index
395 * index of element to replace.
396 * @param iter
397 * a <code>CyclicIterator</code> which determines an index in a list
398 * which replaces <code>this.get(i)</code>.
399 *
400 * @throws UnsupportedOperationException
401 * if the <code>replace</code> method is not supported by this list.
402 * @throws ClassCastException
403 * if the class of some element returned by <code>iter.next()</code>
404 * prevents it from being added to this list.
405 * @throws IllegalArgumentException
406 * if some aspect of some element returned by <code>iter.next()</code>
407 * prevents it from being added to this list.
408 * @throws EmptyCyclicListException
409 * if this list is empty.
410 * @throws IllegalArgumentException
411 * if the specified iterator is empty.
412 * @see #replace(int, List)
413 */
414 void replace(int index, Iterator<E> iter);
415
416 /**
417 * Replaces the element at the specified position in this list
418 * with the specified list (optional operation).
419 * Places the elements of that list as returned by <code>iter.next</code>
420 * in this list.
421 *
422 * @param index
423 * index of element to replace.
424 * @param list
425 * a <code>List</code> which determines an index in a list
426 * which replaces <code>this.get(i)</code>.
427 *
428 * @throws UnsupportedOperationException
429 * if the <code>replace</code> method is not supported by this list.
430 * @throws ClassCastException
431 * if the class of some element returned by <code>iter.next()</code>
432 * prevents it from being added to this list.
433 * @throws IllegalArgumentException
434 * if some aspect of some element returned by <code>iter.next()</code>
435 * prevents it from being added to this list.
436 * @throws EmptyCyclicListException
437 * if this list is empty.
438 * @throws IllegalArgumentException
439 * if the specified list is empty.
440 * @see #replace(int, Iterator)
441 */
442 void replace(int index, List<E> list);
443
444
445 /**
446 * Inserts the specified element at the specified position in this list
447 * (optional operation).
448 * Contract:
449 * <code>list.add(i,o);return list.get(i)</code> yields <code>o</code>.
450 * In contrast to {@link #set},
451 * the element currently at the specified position is not lost.
452 *
453 * @param index
454 * index at which the specified element is to be inserted.
455 * This is interpreted modulo the length of this cyclic list plus one
456 * (The list emerging after the insertion).
457 * In contrast to {@link java.util.List#add(int,Object)}
458 * any index (even a negative one) is valid.
459 * @param element
460 * element to be inserted.
461 *
462 * @throws UnsupportedOperationException
463 * if the <code>add</code> method is not supported by this list.
464 * @throws ClassCastException
465 * if the class of the specified element
466 * prevents it from being added to this list.
467 * @throws IllegalArgumentException
468 * if some aspect of the specified element
469 * prevents it from being added to this list.
470 */
471 void add(int index, E element);
472
473 /**
474 * Inserts the cyclic list of the specified iterator
475 * at the specified position in this list (optional operation).
476 * In contrast to {@link #replace(int, Iterator)},
477 * the element currently at the specified position is not lost.
478 *
479 * @param index
480 * index at which the specified list is to be inserted.
481 * This is interpreted modulo the length of this cyclic list.
482 * Any index (even negative ones) are valid.
483 * @param iter
484 * element to be inserted. *****
485 *
486 * @throws UnsupportedOperationException
487 * if the <code>add</code> method is not supported by this list.
488 * @throws ClassCastException
489 * if the class of the specified element
490 * prevents it from being added to this list.
491 * @throws IllegalArgumentException
492 * if some aspect of the specified element
493 * prevents it from being added to this list.
494 * @see #addAll(int, List)
495 */
496 void addAll(int index, Iterator<E> iter);
497
498 /**
499 * Inserts the specified list at the given position
500 * in this cyclic list (optional operation).
501 * In contrast to {@link #replace(int, Iterator)},
502 * the element currently at the specified position is not lost.
503 *
504 * @param index
505 * index at which the specified list is to be inserted.
506 * This is interpreted modulo the length of this cyclic list.
507 * Any index (even negative ones) are valid.
508 * @param list
509 * the list to be inserted.
510 *
511 * @throws UnsupportedOperationException
512 * if the <code>add</code> method is not supported by this list.
513 * @throws ClassCastException
514 * if the class of the specified element
515 * prevents it from being added to this list.
516 * @throws IllegalArgumentException
517 * if some aspect of the specified element
518 * prevents it from being added to this list.
519 * @see #addAll(int, Iterator)
520 */
521 void addAll(int index, List<? extends E> list);
522
523 /**
524 * Removes the element at the specified position in this list
525 * (optional operation).
526 * Returns the element that was removed from the list.
527 *
528 * @param index
529 * the index of the element to removed.
530 * This is interpreted modulo the length of this cyclic list.
531 * Any index (even negative ones) are valid.
532 * @return
533 * the element previously at the specified position.
534 *
535 * @throws UnsupportedOperationException
536 * if the <code>remove</code> method is not supported by this list.
537 * @throws EmptyCyclicListException
538 * if this list is empty.
539 */
540 E remove(int index) throws EmptyCyclicListException;
541
542
543 // Search Operations
544
545 /**
546 * Returns the non-negative index in this cyclic list
547 * of the first occurrence of the specified element,
548 * or <code>-1</code> if this cyclic list does not contain this element.
549 * More formally, returns the lowest index <tt>i</tt> such that
550 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
551 * or some negative index if there is no such index.
552 * <p>
553 * Note that this specification slightly differs from
554 * {@link java.util.List#indexOf(Object)}.
555 *
556 * @param idx
557 * the index to start search with.
558 * Independently of this,
559 * the search comprises all entries of this cyclic list.
560 * @param obj
561 * element to search for or <code>null</code>.
562 * @return
563 * the index in this cyclic list
564 * of the first occurrence of the specified
565 * element, or <code>-1</code>
566 * if this list does not contain this element.
567 */
568 int getIndexOf(int idx, Object obj);
569
570 /**
571 * Returns a <code>CyclicList</code>
572 * which is by copying this list step by step
573 * such that the length of the result is <code>len</code>.
574 * For example <code>len == size()*n</code>
575 * yields an n-fold copy of this cyclic list.
576 *
577 * @param len
578 * a non-negative <code>int</code> value.
579 * @return
580 * a <code>CyclicList</code>
581 * which is by copying this list step by step
582 * such that the length of the result is as specified.
583 * @throws IllegalArgumentException
584 * if <code>len</code> is negative.
585 * @throws EmptyCyclicListException
586 * if this list is empty and <code>len > 0</code>.
587 */
588 CyclicList<E> getCopy(int len);
589 }
590