1
2 package eu.simuline.util;
3
4 import java.util.Set;
5 import java.util.SortedSet;
6 import java.util.List;
7 import java.util.ArrayList;
8 import java.util.Collection;
9 import java.util.Collections; // for javadoc only.
10 import java.util.Iterator;
11 import java.util.ListIterator;
12 import java.util.Comparator;
13 import java.util.NoSuchElementException;
14 import java.util.AbstractSet;
15
16 /**
17 * This class implements the Set interface,
18 * backed by a {@link java.util.ArrayList java.util.ArrayList}.
19 * The iteration order of the set
20 * is the iteration order of the underlying ArrayList.
21 * This class permits the null element.
22 * <p>
23 * The size, isEmpty, and iterator operations run in constant time.
24 * The add operation runs in amortized constant time, that is,
25 * adding n elements requires O(n) time.
26 * All of the other operations run in linear time (roughly speaking).
27 * <p>
28 * Each ListSet instance has a capacity.
29 * The capacity is the size of the array used
30 * to store the elements in the list.
31 * It is always at least as large as the set size.
32 * As elements are added an ListSet, its capacity grows automatically.
33 * The details of the growth policy are not specified
34 * beyond the fact that adding an element has constant amortized time cost.
35 * <p>
36 * <em>Note that this implementation is not synchronized. </em>
37 * If multiple threads access a set concurrently,
38 * and at least one of the threads modifies the set,
39 * it must be synchronized externally.
40 * This is typically accomplished by synchronizing on some object
41 * that naturally encapsulates the set.
42 * If no such object exists, the set should be "wrapped"
43 * using the Collections.synchronizedSet method.
44 * This is best done at creation time,
45 * to prevent accidental unsynchronized access to the ListSet instance:
46 * <pre>Set s = Collections.synchronizedSet(new ListSet(...));</pre>
47 * <p>
48 * The iterators returned by this class's iterator method are fail-fast:
49 * if the set ismodified at any time after the iterator is created,
50 * in any way except through the iterator's own remove method,
51 * the Iterator throws a ConcurrentModificationException.
52 * Thus, in the face of concurrent modification,
53 * the iterator fails quickly and cleanly, rather than risking arbitrary,
54 * non-deterministic behavior at an undetermined time in the future.
55 *
56 * @param <E>
57 * The type of the entries.
58 *
59 * @author <a href="mailto:ernst.reissner@simuline.eu">Ernst Reissner</a>
60 * @version 1.0
61 *
62 * @see java.util.Collection
63 * @see java.util.List
64 * @see java.util.ArrayList#add
65 * @see java.util.SortedSet
66 * @see java.util.HashSet
67 * @see java.util.TreeSet
68 * @see java.util.AbstractSet
69 * @see java.util.Collections
70 */
71 public final class ListSet<E> extends AbstractSet<E> implements SortedSet<E> {
72
73 /* -------------------------------------------------------------------- *
74 * inner classes. *
75 * -------------------------------------------------------------------- */
76
77 /* -------------------------------------------------------------------- *
78 * fields. *
79 * -------------------------------------------------------------------- */
80
81 /**
82 * Contains the elements of this set.
83 * By contract, <code>list.get(a).equals(list.get(b))</code>
84 * implies <code>a == b</code>.
85 */
86 private final List<E> list;
87
88 /**
89 * The comparator initialized in the constructor
90 * and returned by {@link #comparator()}.
91 * This may well be <code>null</code> and is nowhere used directly.
92 */
93 private final Comparator<? super E> outerCmp;
94
95 /**
96 * If {@link #outerCmp} is not <code>null</code>,
97 * the two comparators coincide.
98 * Otherwise this comparator reflects the natural ordering
99 * and throws a <code>ClassCastException</code>
100 * if feeded with no appropriate <code>Comparable</code>.
101 */
102 private final Comparator<? super E> innerCmp;
103
104 /* -------------------------------------------------------------------- *
105 * constructors. *
106 * -------------------------------------------------------------------- */
107
108 /**
109 * Creates a new <code>ListSet</code> with ordering as added
110 * in ascending ordering.
111 */
112 public static <E> ListSet<E> sortedAsAdded() {
113 return sortedAsListed(new ArrayList<E>());
114 }
115
116 /**
117 * Returns an <code>ListSet</code> with elements and ordering
118 * given by <code>list</code>
119 * as described in {@link Comparators#getAsListed(List)}.
120 * If an element is added to <code>list</code>,
121 * the ordering is as added at the end of <code>list</code>.
122 *
123 * CAUTION: The list backs this set:
124 * changes in the list affect this set and the other way round.
125 * Changing the list also changes the ordering.
126 *
127 * @throws NullPointerException
128 * if <code>list</code> is <code>null</code>.
129 */
130 public static <E> ListSet<E> sortedAsListed(List<E> list) {
131 return new ListSet<E>(list, Comparators.getAsListed(list));
132 }
133
134 /**
135 * Creates a new <code>ListSet</code>
136 * with elements given by <code>list</code>
137 * and ordering given by <code>cmp</code>.
138 * If the latter is <code>null</code>
139 * then the type parameter of <code>list</code>
140 * must be a <code>Comparable</code>.
141 * and <code>list</code> must
142 * This is inspired by a constructor of TreeSet.
143 *
144 * @param list
145 * the list wrapped by this set.
146 * It must be ordered ascending according to <code>cmp</code>
147 * if this is non-null, else as <code>Comparable</code>s.
148 * It is desireable that <code>list</code>
149 * contains each element once only.
150 * @param cmp
151 * A comparator or <code>null</code>.
152 */
153 private ListSet(List<E> list, Comparator<? super E> cmp) {
154 this.list = list;
155 this.outerCmp = cmp;
156
157 // set innerCmp
158 if (cmp == null) {
159 this.innerCmp = new Comparator<E>() {
160 // throws a ClassCastException if not comparable.
161 // **** it is not easy to eliminate the compiler warning.
162 // to that end, compare with TreeSet
163 public int compare(E obj1, E obj2) {
164 return ((Comparable<E>) obj1).compareTo(obj2);
165 }
166 };
167 } else {
168 this.innerCmp = cmp;
169 }
170 Collections.sort(this.list, this.innerCmp);
171
172
173 /*
174 this.innerCmp = (cmp == null)
175 ? new Comparator<E>() {
176 public int compare(E o1,E o2) {
177 return ((Comparable<E>)o1).compareTo(o2);
178 }
179 }
180 : cmp;
181 */
182 }
183
184 /**
185 * Constructs a new set containing the same elements
186 * and using the same ordering as the <code>sortedSet</code>.
187 *
188 * @param sortedSet
189 * sorted set whose elements will comprise the new set
190 * @throws NullPointerException
191 * if the specified sorted set is <code>null</code>.
192 */
193 public ListSet(SortedSet<E> sortedSet) {
194 this(sortedSet.comparator());
195 //addAll(sortedSet);
196 // could be improved by explicitely iterating
197 for (E elem : sortedSet) {
198 this.list.add(elem);
199 }
200 }
201
202 /**
203 * Creates a new set containing the elements of the specified collection
204 * in the natural ordering.
205 * All elements inserted into the set
206 * must implement the Comparable interface.
207 * Furthermore, all such elements must be mutually comparable:
208 * <code>e1.compareTo(e2)</code> must not throw a ClassCastException
209 * for any elements <code>e1</code> and <code>e2</code> in the set.
210 * <p>
211 * The backing ArrayList instance {@link #list}
212 * has an initial capacity of 110% the size of the specified collection.
213 *
214 * @param coll
215 * the collection whose elements are to be placed into this set.
216 * @throws ClassCastException
217 * if the elements in c are not Comparable,
218 * or are not mutually comparable.
219 * @throws NullPointerException
220 * if the specified collection is <code>null</code>.
221 */
222 public ListSet(Collection<? extends E> coll) { //,boolean isSortedAsAdded
223 this((Comparator<? super E>) null);
224 addAll(coll); // NOPMD
225 //this(new OrderingDesc<E>(coll,isSortedAsAdded));
226 }
227 /*
228 void test(Comparator<E> cmp) {
229 this.innerCmp = new Comparator<E>() {
230 public int compare(E o1,E o2) {
231 return ((Comparable<E>)o1).compareTo(o2);
232 }
233 };
234 }
235 */
236
237
238 /**
239 * Constructs a new, empty set,
240 * sorted according to the specified comparator <code>cmp</code>.
241 * For <code>cmp==null</code>
242 * a comparator defining the natural ordering is assumed.
243 * <p>
244 * All elements inserted into the set
245 * must be mutually comparable by the specified comparator:
246 * <code>cmp.compare(e1, e2)</code> must not throw a ClassCastException
247 * for any elements <code>e1</code> and <code>e2</code> in the set.
248 * If the user attempts to add an element to the set
249 * that violates this constraint,
250 * the add call will throw a {@link ClassCastException}.
251 * <p>
252 * Implementational note:
253 * Whereas {@link #outerCmp} is initialized with <code>cmp</code>
254 * whether it is <code>null</code> or not,
255 * {@link #innerCmp} is initialized with <code>cmp</code>
256 * only if this is not <code>null</code>.
257 * Otherwise, it is initialized with a comparator
258 * defining the natural ordering.
259 *
260 * @param cmp
261 * the comparator that will be used to order this set.
262 * If null, the natural ordering of the elements will be used.
263 */
264 public ListSet(Comparator<? super E> cmp) {
265 this(new ArrayList<E>(), cmp);
266 }
267
268 /**
269 * Constructs a new, empty set,
270 * sorted according to the natural ordering of its elements.
271 * All elements inserted into the set
272 * must implement the Comparable interface.
273 * Furthermore, all such elements must be mutually comparable:
274 * <code>e1.compareTo(e2)</code> must not throw a ClassCastException
275 * for any elements <code>e1</code> and <code>e2</code> in the set.
276 * If the user attempts to add an element to the set
277 * that violates this constraint
278 * (for example, the user attempts to add a string element to a set
279 * whose elements are integers),
280 * the add call will throw a {@link ClassCastException}.
281 * For a generalization to a given comparator
282 * see {@link #ListSet(Comparator)}.
283 */
284 public ListSet() {
285 this((Comparator<? super E>) null);
286 }
287
288 /* -------------------------------------------------------------------- *
289 * methods. *
290 * -------------------------------------------------------------------- */
291
292 /**
293 * Returns a list backing this set,
294 * so changes in the returned list are reflected in this set,
295 * and vice-versa.
296 */
297 public List<E> getList() {
298 return this.list;
299 }
300
301 /**
302 * Returns the number of elements in this set (its cardinality).
303 * If thisset contains more than <code>Integer.MAX_VALUE</code> elements,
304 * returns <code>Integer.MAX_VALUE</code>.
305 *
306 * @return the number of elements in this set (its cardinality).
307 */
308 public int size() {
309 return this.list.size();
310 //return containsNull ? this.list.size()+1 : this.list.size();
311 }
312
313 /**
314 * Returns <code>true</code> if this set contains no elements.
315 *
316 * @return
317 * <code>true</code> if this set contains no elements.
318 */
319 public boolean isEmpty() {
320 return this.list.isEmpty();
321 //return !containsNull && this.list.isEmpty();
322 }
323
324 /**
325 * Returns <code>true</code> if this set contains the specified element.
326 * More formally, returns <code>true</code> if and only
327 * if this set contains an element <code>e</code>
328 * such that <code>(obj==null ? e==null : obj.equals(e))</code>.
329 *
330 * @param obj
331 * obj is some object that may be in this collection.
332 * @return
333 * <code>true</code> if this set contains the specified element.
334 */
335 public boolean contains(Object obj) {
336 // if (isEmpty()) {
337 // return false;
338 // }
339 // if (!this.list.get(0).getClass().isInstance(obj)) {
340 // return false;
341 // }
342 // E eObj = (E)obj;
343
344 // int lastIdx = this.list.size()-1;
345 // return this.innerCmp.compare(this.list.get(0 ), eObj) <= 0
346 // && this.innerCmp.compare(this.list.get(lastIdx), eObj) >= 0;
347
348 //return obj == null : containsNull : this.list.contains(obj);
349 return this.list.contains(obj);
350 }
351
352 /**
353 * Returns an iterator over the elements in this set.
354 * The elements are returned in the particular order
355 * in which they are stored in {@link #list}.
356 *
357 * @return
358 * an iterator over the elements in this set.
359 */
360 public Iterator<E> iterator() {
361 return this.list.iterator();
362 // more complicated with null not in list.
363 }
364
365 /**
366 * Returns an iterator over the elements in this set.
367 * The elements are returned in the particular order
368 * in which they are stored in {@link #list}.
369 *
370 * @return
371 * an iterator over the elements in this set.
372 */
373 public ListIterator<E> listIterator() {
374 return this.list.listIterator();
375 // more complicated with null not in list.
376 }
377
378 /**
379 * Returns an array containing all of the elements in this set;
380 * the order is as in the backing list {@link #list}.
381 * Obeys the general contract of the <code>Collection.toArray</code> method.
382 *
383 * @return
384 * an array containing all of the elements in this set.
385 */
386 public Object[] toArray() {
387 return this.list.toArray();
388 }
389
390 /**
391 * Returns an array containing all of the elements in this set
392 * whose runtime type is that of the specified array;
393 * the order is as in the backing list {@link #list}.
394 * Obeys the general contract
395 * of the <code>Collection.toArray(Object[])</code> method.
396 *
397 * @param arr
398 * the array into which the elements of this set are to be stored,
399 * if it is big enough;
400 * otherwise, a new array of the same runtime type is allocated
401 * for this purpose.
402 * @return
403 * an array containing the elements of this set.
404 * @throws ArrayStoreException
405 * the runtime type of a is not a supertype
406 * of the runtime type of every element in this set.
407 */
408 public <T> T[] toArray(T[] arr) {
409 return this.list.toArray(arr);
410 }
411
412 /*----------------------------------------------------------------------*/
413 /* Modification Operations */
414 /*----------------------------------------------------------------------*/
415
416 /**
417 * Adds the specified element to this set if it is not already present.
418 * More formally, adds the specified element, <code>o</code>,
419 * to this set if this set contains no element <code>e</code>
420 * such that <code>(o==null ? e==null : o.equals(e))</code>.
421 * If this set already contains the specified element,
422 * the call leaves this set unchanged and returns <code>false</code>.
423 * In combination with the restriction on constructors,
424 * this ensures that sets never contain duplicate elements.
425 * <p>
426 * Note that also <code>null</code> may be added to this set,
427 * but only if it is not already present, this changes this set.
428 *
429 * @param obj
430 * element to be added to this set.
431 * @return
432 * <code>true</code> if this set did not already contain the specified
433 * element.
434 */
435 public boolean add(E obj) {
436 int index = Collections.binarySearch(this.list, obj, this.innerCmp);
437 if (index >= 0) {
438 return false;
439 }
440 index = -index - 1;
441
442 this.list.add(index, obj);
443 return true;
444 }
445
446 /**
447 * Removes the specified element from this set if it is present.
448 * More formally, removes an element <code>e</code>
449 * such that <code>(o==null ? e==null : o.equals(e))</code>,
450 * if the set contains such an element.
451 * Returns <code>true</code> if the set contained the specified element
452 * (or equivalently, if the set changed as a result of the call).
453 * (The set will not contain the specified element once the call returns.)
454 *
455 * @param obj
456 * object to be removed from this set, if present.
457 * @return
458 * <code>true</code> if the set contained the specified element.
459 */
460 public boolean remove(Object obj) {
461 return this.list.remove(obj);
462 }
463
464 /*----------------------------------------------------------------------*/
465 /* Bulk Operations */
466 /*----------------------------------------------------------------------*/
467
468 /**
469 * Returns <code>true</code> if this set contains all of the elements
470 * of the specified collection.
471 * If the specified collection is also a set,
472 * this method returns <code>true</code>
473 * if it is a <i>subset</i> of this set.
474 *
475 * @param coll
476 * collection to be checked for containment in this set.
477 * @return
478 * <code>true</code> if this set contains all of the elements
479 * of the specified collection.
480 */
481 public boolean containsAll(Collection<?> coll) {
482 // if (isSortedWithSameComparator(coll)) {
483 // // ***** here more efficient code would be possible
484 // int min = 0;
485 // int sup = this.list.size();
486 // int index;
487 // Iterator<?> iter = coll.iterator();
488 // E elem;
489 // while (iter.hasNext()) {
490 // try { /// **** not so good implementation.
491 // elem = (E)iter.next();
492 // } catch (ClassCastException cce) {
493 // return false;
494 // }
495
496 // index = Collections.binarySearch(this.list.subList(min,sup),
497 // elem,
498 // this.innerCmp);
499 // //index = this.cmp.search(this.list.subList(min,sup),o);
500 // if (index < 0) {
501 // return false;
502 // }
503 // min = index+1;
504 // }
505 // return true;
506 // } // same comparator
507
508 Iterator<?> iter = coll.iterator();
509 while (iter.hasNext()) {
510 if (!contains(iter.next())) {
511 return false;
512 }
513 }
514
515 return true;
516 }
517
518 /**
519 * Returns whether this set has the same comparator as
520 * the collection given.
521 *
522 * @param coll
523 * a collection which may be a <code>SortedSet</code> or not.
524 * @return
525 * <code>true</code> if <code>c</code> is a sorted set
526 * and if <code>c.comparator</code> yields the same result:
527 * <ul>
528 * <li>
529 * Either they coincide as pointers,
530 * including the case that both are <code>null</code>
531 * <li>
532 * or at least this comparator is not <code>null</code>
533 * and equals the other one.
534 * This case implies that neither are <code>null</code>.
535 * </ul>
536 */
537 private boolean isSortedWithSameComparator(Collection<?> coll) {
538 if (!(coll instanceof SortedSet)) {
539 return false;
540 }
541 SortedSet<?> sSet = (SortedSet) coll;
542 return sSet.comparator() == this.comparator() ||
543 (this.comparator() != null &&
544 this.comparator().equals(sSet.comparator()));
545 }
546
547 /**
548 * Adds all of the elements in the specified collection to this set
549 * if they're not already present.
550 * If the specified collection is also a set,
551 * the <code>addAll</code> operation effectively modifies this set so
552 * that its value is the <i>union</i> of the two sets.
553 * The behavior of this operation is unspecified if the specified
554 * collection is modified while the operation is in progress.
555 *
556 * @param coll
557 * collection whose elements are to be added to this set.
558 * @return
559 * <code>true</code> if this set changed as a result of the call.
560 * @see #add
561 */
562 public boolean addAll(Collection<? extends E> coll) {
563 if (isSortedWithSameComparator(coll)) {
564 List<E> cList;
565 // if (coll instanceof ListSet) {
566 // cList = ((ListSet)coll).getList();
567 // } else {
568 cList = new ArrayList<E>(coll);
569 // }
570 return addList(this.list, cList);
571 } else {
572 boolean modified = false;
573 for (E entry : coll) {
574 modified |= add(entry);
575 }
576 return modified;
577 }
578 }
579
580 // public final static int[] ab = new int[2];
581
582 /**
583 * Merges <code>list2</code> into <code>list1</code>
584 * and returns whether <code>l1</code> had been modified.
585 * At the end, <code>list2</code> is not modified
586 * and <code>list1</code> is ordered again.
587 *
588 * @param list1
589 * a list which is required to be sorted according to {@link #innerCmp}
590 * without duplicates.
591 * @param list2
592 * a list which is required to be sorted according to {@link #innerCmp}
593 * without duplicates.
594 * @return
595 * whether <code>list1</code> had been modified.
596 */
597 @SuppressWarnings("checkstyle:nowhitespacebefore")
598 private boolean addList(List<E> list1, List<E> list2) {
599
600 switch (list2.size()) { // NOPMD
601 case 0:
602 return false;
603 case 1:
604 int index = Collections.binarySearch(list1,
605 list2.get(0),
606 this.innerCmp);
607 if (index >= 0) {
608 return false;
609 } else {
610 index = -1 - index;
611 list1.add(index, list2.get(0));
612 return true;
613 }
614 default:
615 // fall through
616 } // end of switch
617 int index2 = list2.size() / 2;
618 int index1 = Collections
619 .binarySearch(list1, list2.get(index2), this.innerCmp);
620
621 if (index1 >= 0) {
622 boolean isModified;
623 int index1b = index1,
624 index2b = index2;
625
626 do {
627 index1b++;
628 index2b++;
629 } while (index1b < list1.size() &&
630 index2b < list2.size() &&
631 this.innerCmp.compare(list1.get(index1b),
632 list2.get(index2b)) == 0);
633 if (index1b == list1.size()) {
634 list1.addAll(list2.subList(index2b, list2.size()));
635 return addList(list1.subList(0, index1),
636 list2.subList(0, index2));
637 } else {
638 isModified = addList(list1.subList(index1b, list1.size()),
639 list2.subList(index2b, list2.size()));
640 isModified |= addList(list1.subList(0, index1),
641 list2.subList(0, index2));
642 return isModified;
643 }
644
645 /*
646 isModified = addList(l1.subList(index1b,l1.size()),
647 l2.subList(index2b,l2.size()));
648 isModified |= addList(l1.subList(0,index1),
649 l2.subList(0,index2));
650 return isModified;
651 */
652 /*
653 isModified = addList(l1.subList(index1+1,l1.size()),
654 l2.subList(index2+1,l2.size()));
655 isModified |= addList(l1.subList(0,index1),
656 l2.subList(0,index2));
657 return isModified;
658 */
659 } else {
660 index1 = -1 - index1;
661 if (index1 < list1.size()) {
662
663 int index2b = index2 + 1;
664 E obj = list1.get(index1);
665 Comparator<? super E> cmp = this.innerCmp;
666 while (index2b < list2.size() &&
667 cmp.compare(obj, list2.get(index2b)) > 0) {
668 index2b++;
669 }
670
671 addList(list1.subList(index1 , list1.size()),
672 list2.subList(index2b, list2.size()));
673 if (index2b > 1 + index2) {
674 list1.addAll(index1, list2.subList(index2, index2b));
675 } else {
676 list1.add(index1, list2.get(index2));
677 }
678
679 //l1.addAll(index1,l2.subList(index2,index2b));
680 //System.out.println("string:: " + (index2b-index2));
681
682 addList(list1.subList(0, index1),
683 list2.subList(0, index2));
684 return true;
685
686 } else {
687 list1.addAll(list2.subList(index2, list2.size()));
688 /*
689 addList(l1.subList(index1,l1.size()),
690 l2.subList(index2,l2.size()));
691 */
692 addList(list1.subList(0, index1),
693 list2.subList(0, index2));
694 return true;
695 } // end of else
696
697 /*
698 addList(l1.subList(index1,l1.size()),
699 l2.subList(index2,l2.size()));
700 addList(l1.subList(0,index1),
701 l2.subList(0,index2));
702 return true;
703 */
704 } // end of else
705 }
706
707 /**
708 * Retains only the elements in this set
709 * that are contained in the specified collection.
710 * In other words, removes from this set all of its elements
711 * that are not contained in the specified collection.
712 * If the specified collection is also a set,
713 * this operation effectively modifies this set so
714 * that its value is the <i>intersection</i> of the two sets.
715 *
716 * @param coll
717 * collection that defines which elements this set will retain.
718 * @return
719 * <code>true</code> if this collection changed as a result of the call.
720 * @see #remove
721 */
722 public boolean retainAll(Collection<?> coll) {
723 /*
724 if (isSortedWithSameComparator(coll)) {
725 // ***** here more efficient code would be possible
726 }
727 */
728 // **** not ideal if this and coll are both sorted!
729 return this.list.retainAll(coll);
730 }
731
732 /**
733 * Removes from this set all of its elements
734 * that are contained in the specified collection.
735 * If the specified collection is also a set,
736 * this operation effectively modifies this set so
737 * that its value is the <i>asymmetric set difference</i> of the two sets.
738 *
739 * @param coll
740 * collection that defines
741 * which elements will be removed from this set.
742 * @return
743 * <code>true</code> if this set changed as a result of the call.
744 * @see #remove
745 */
746 public boolean removeAll(Collection<?> coll) {
747 // **** not ideal if this and coll are both sorted!
748 return this.list.removeAll(coll);
749 }
750
751 /**
752 * Removes all of the elements from this set.
753 * This set will be empty after this call returns.
754 */
755 public void clear() {
756 this.list.clear();
757 }
758
759 /*----------------------------------------------------------------------*
760 * methods implementing SortedSet *
761 *----------------------------------------------------------------------*/
762
763 // api-docs inherited from SortedSet
764 public Comparator<? super E> comparator() {
765 return this.outerCmp;
766 }
767
768 // also used in {@link ListMap}
769 int obj2idx(E obj) {
770 int idx = Collections.binarySearch(this.list, obj, this.innerCmp);
771 if (idx < 0) {
772 idx = -idx - 1;
773 }
774 assert idx >= 0;
775 return idx;
776 }
777
778 // also used in {@link ListMap}
779 // **** seems to be compiler/vm bug:
780 // no failure when trying to compile subSetIdx renamed in subSet
781 // although this should give name clash when invoked with E=Integer
782 ListSet<E> subSetIdx(int fromIdx, int toIdx) {
783 return new ListSet<E>(this.list.subList(fromIdx, toIdx), this.outerCmp);
784 }
785
786 // api-docs inherited from SortedSet
787 public ListSet<E> subSet(E fromObj, E toObj) {
788 return subSetIdx(obj2idx(fromObj), obj2idx(toObj));
789 }
790
791 // api-docs inherited from SortedSet
792 public SortedSet<E> headSet(E toObj) {
793 return subSetIdx(0, obj2idx(toObj));
794 }
795
796 // api-docs inherited from SortedSet
797 public SortedSet<E> tailSet(E fromObj) {
798 return subSetIdx(obj2idx(fromObj), size());
799 }
800
801 // api-docs inherited from SortedSet
802 public E first() {
803 if (isEmpty()) {
804 throw new NoSuchElementException();
805 }
806 return this.list.get(0);
807 }
808
809 // api-docs inherited from SortedSet
810 public E last() {
811 if (isEmpty()) {
812 throw new NoSuchElementException();
813 }
814 return this.list.get(size() - 1);
815 }
816
817 /*----------------------------------------------------------------------*/
818 /* Comparison representation and hashing */
819 /*----------------------------------------------------------------------*/
820
821 /**
822 * **** ask at oracle whether for sorted sets equality
823 * should include ordering. ****
824 * Compares the specified object with this set for equality.
825 * Returns <code>true</code> if the specified object is also a set,
826 * the two sets have the same size,
827 * and every member of the specified set is contained in this set
828 * (or equivalently, every member of this set
829 * is contained in the specified set).
830 * This definition ensures that the equals method works properly
831 * across different implementations of the set interface.
832 *
833 * @param obj
834 * Object to be compared for equality with this set.
835 * @return
836 * <code>true</code> if the specified Object is equal to this set.
837 */
838 public boolean equals(Object obj) {
839 if (!(obj instanceof Set)) {
840 return false;
841 }
842 Set<?> other = (Set<?>) obj;
843
844 if (this.size() != other.size()) {
845 return false;
846 }
847 // **** what if this is sorted?
848 return this.containsAll(other);
849 }
850
851 /**
852 * Returns a string representation of this set.
853 *
854 * @return
855 * a comma separated list of <code>String</code>-representations
856 * of the elements of this list
857 * enclosed in triangle brackets.
858 */
859 public String toString() {
860 StringBuffer result = new StringBuffer();
861 result.append('[');
862 if (!this.isEmpty()) {
863 result.append(this.list.get(0).toString());
864 for (int i = 1; i < size(); i++) {
865 result.append(", ");
866 result.append(this.list.get(i));
867 }
868 }
869
870 result.append(']');
871 return result.toString();
872 }
873
874 /**
875 * Returns the hash code value for this set.
876 * The hash code of a set is defined to be the sum
877 * of the hash codes of the elements in the set,
878 * where the hashcode of a <code>null</code> element is defined to be zero.
879 * This ensures that <code>s1.equals(s2)</code> implies that
880 * <code>s1.hashCode()==s2.hashCode()</code> for any two sets
881 * <code>s1</code> and <code>s2</code>, as required by the general
882 * contract of the <code>Object.hashCode</code> method.
883 *
884 * @return
885 * the hash code value for this set.
886 * @see Object#hashCode()
887 * @see Object#equals(Object)
888 * @see Set#equals(Object)
889 */
890 public int hashCode() {
891 int code = 0;
892 Iterator<E> iter = this.iterator();
893 E cand;
894 while (iter.hasNext()) {
895 cand = iter.next();
896 code += cand == null ? 0 : cand.hashCode();
897 }
898 return code;
899 }
900
901 @SuppressWarnings("checkstyle:magicnumber")
902 public static void main(String[] args) {
903 ListSet<Integer> aSet;
904
905 // aSet = ListSet.sortedAsAdded();
906 // aSet.add(0);
907 // aSet.add(1);
908 // aSet.add(2);
909 // aSet.add(3);
910 // System.out.println(": "+aSet.getList());
911 // System.out.println(": "+aSet.comparator()
912 // .compare(aSet.first(),aSet.last()));
913
914 aSet = ListSet.sortedAsListed(java.util.Arrays.asList(new Integer[] {
915 3, 2, 1}));
916 System.out.println(": " + aSet.getList());
917
918
919 /*
920 List<Integer> list = new ArrayList<Integer>();
921 list.add(0);
922 list.add(1);
923 list.add(2);
924 list.add(3);
925 Iterator<Integer> iter1 = list.iterator();
926 Iterator<Integer> iter2 = list.iterator();
927 iter1.next();
928 iter1.remove();
929 iter2.next();// throws ConcurrentModificationException
930 // no correction of internal cursors
931 */
932 }
933 }
934
935 // ListSet.java:158: warning: [unchecked] unchecked cast
936 // return ((Comparable<E>)obj1).compareTo(obj2);
937 // ^
938 // required: Comparable<E>
939 // found: E
940 // where E is a type-variable:
941 // E extends Object declared in class ListSet
942 // 1 warning