1 /*
2 * Copyright (c) 2005, 2011, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24 /*
25 * @test
26 * @bug 6207984 6272521 6192552 6269713 6197726 6260652 5073546 4137464
27 * 4155650 4216399 4294891 6282555 6318622 6355327 6383475 6420753
28 * 6431845 4802633 6570566 6570575 6570631 6570924 6691185 6691215
29 * 4802647 7123424
30 * @summary Run many tests on many Collection and Map implementations
31 * @author Martin Buchholz
32 * @run main MOAT
33 */
34
35 /* Mother Of All (Collection) Tests
36 *
37 * Testing of collection classes is often spotty, because many tests
38 * need to be performed on many implementations, but the onus on
39 * writing the tests falls on the engineer introducing the new
40 * implementation.
41 *
42 * The idea of this mega-test is that:
43 *
44 * An engineer adding a new collection implementation could simply add
45 * their new implementation to a list of implementations in this
46 * test's main method. Any general purpose Collection<Integer> or
47 * Map<Integer,Integer> class is appropriate.
48 *
49 * An engineer fixing a regression could add their regression test here and
50 * simultaneously test all other implementations.
51 */
52
53 import java.io.*;
54 import java.util.*;
55 import java.util.concurrent.*;
56 import static java.util.Collections.*;
57
58 public class MOAT {
59 public static void realMain(String[] args) {
60
61 testCollection(new NewAbstractCollection<Integer>());
62 testCollection(new NewAbstractSet<Integer>());
63 testCollection(new LinkedHashSet<Integer>());
64 testCollection(new HashSet<Integer>());
65 testCollection(new Vector<Integer>());
66 testCollection(new Vector<Integer>().subList(0,0));
67 testCollection(new ArrayDeque<Integer>());
68 testCollection(new ArrayList<Integer>());
69 testCollection(new ArrayList<Integer>().subList(0,0));
70 testCollection(new LinkedList<Integer>());
71 testCollection(new LinkedList<Integer>().subList(0,0));
72 testCollection(new TreeSet<Integer>());
73 testCollection(Collections.checkedList(new ArrayList<Integer>(), Integer.class));
74 testCollection(Collections.synchronizedList(new ArrayList<Integer>()));
75 testCollection(Collections.checkedSet(new HashSet<Integer>(), Integer.class));
76 testCollection(Collections.checkedSortedSet(new TreeSet<Integer>(), Integer.class));
77 testCollection(Collections.checkedNavigableSet(new TreeSet<Integer>(), Integer.class));
78 testCollection(Collections.synchronizedSet(new HashSet<Integer>()));
79 testCollection(Collections.synchronizedSortedSet(new TreeSet<Integer>()));
80 testCollection(Collections.synchronizedNavigableSet(new TreeSet<Integer>()));
81
82 testCollection(new CopyOnWriteArrayList<Integer>());
83 testCollection(new CopyOnWriteArrayList<Integer>().subList(0,0));
84 testCollection(new CopyOnWriteArraySet<Integer>());
85 testCollection(new PriorityQueue<Integer>());
86 testCollection(new PriorityBlockingQueue<Integer>());
87 testCollection(new ArrayBlockingQueue<Integer>(20));
88 testCollection(new LinkedBlockingQueue<Integer>(20));
89 testCollection(new LinkedBlockingDeque<Integer>(20));
90 testCollection(new ConcurrentLinkedDeque<Integer>());
91 testCollection(new ConcurrentLinkedQueue<Integer>());
92 testCollection(new LinkedTransferQueue<Integer>());
93 testCollection(new ConcurrentSkipListSet<Integer>());
94 testCollection(Arrays.asList(new Integer(42)));
95 testCollection(Arrays.asList(1,2,3));
96 testCollection(nCopies(25,1));
97 testImmutableList(nCopies(25,1));
98 testImmutableList(unmodifiableList(Arrays.asList(1,2,3)));
99
100 testMap(new HashMap<Integer,Integer>());
101 testMap(new LinkedHashMap<Integer,Integer>());
102 testMap(new WeakHashMap<Integer,Integer>());
103 testMap(new IdentityHashMap<Integer,Integer>());
104 testMap(new TreeMap<Integer,Integer>());
105 testMap(new Hashtable<Integer,Integer>());
106 testMap(new ConcurrentHashMap<Integer,Integer>(10, 0.5f));
107 testMap(new ConcurrentSkipListMap<Integer,Integer>());
108 testMap(Collections.checkedMap(new HashMap<Integer,Integer>(), Integer.class, Integer.class));
109 testMap(Collections.checkedSortedMap(new TreeMap<Integer,Integer>(), Integer.class, Integer.class));
110 testMap(Collections.checkedNavigableMap(new TreeMap<Integer,Integer>(), Integer.class, Integer.class));
111 testMap(Collections.synchronizedMap(new HashMap<Integer,Integer>()));
112 testMap(Collections.synchronizedSortedMap(new TreeMap<Integer,Integer>()));
113 testMap(Collections.synchronizedNavigableMap(new TreeMap<Integer,Integer>()));
114
115 // Empty collections
116 final List<Integer> emptyArray = Arrays.asList(new Integer[]{});
117 testCollection(emptyArray);
118 testEmptyList(emptyArray);
119 THROWS(IndexOutOfBoundsException.class,
120 new Fun(){void f(){ emptyArray.set(0,1); }});
121 THROWS(UnsupportedOperationException.class,
122 new Fun(){void f(){ emptyArray.add(0,1); }});
123
124 List<Integer> noOne = nCopies(0,1);
125 testCollection(noOne);
126 testEmptyList(noOne);
127 testImmutableList(noOne);
128
129 Set<Integer> emptySet = emptySet();
130 testCollection(emptySet);
131 testEmptySet(emptySet);
132 testEmptySet(EMPTY_SET);
133 testEmptySet(Collections.emptySet());
134 testEmptySet(Collections.emptySortedSet());
135 testEmptySet(Collections.emptyNavigableSet());
136 testImmutableSet(emptySet);
137
138 List<Integer> emptyList = emptyList();
139 testCollection(emptyList);
140 testEmptyList(emptyList);
141 testEmptyList(EMPTY_LIST);
142 testEmptyList(Collections.emptyList());
143 testImmutableList(emptyList);
144
145 Map<Integer,Integer> emptyMap = emptyMap();
146 testMap(emptyMap);
147 testEmptyMap(emptyMap);
148 testEmptyMap(EMPTY_MAP);
149 testEmptyMap(Collections.emptyMap());
150 testEmptyMap(Collections.emptySortedMap());
151 testEmptyMap(Collections.emptyNavigableMap());
152 testImmutableMap(emptyMap);
153 testImmutableMap(Collections.emptyMap());
154 testImmutableMap(Collections.emptySortedMap());
155 testImmutableMap(Collections.emptyNavigableMap());
156
157 // Singleton collections
158 Set<Integer> singletonSet = singleton(1);
159 equal(singletonSet.size(), 1);
160 testCollection(singletonSet);
161 testImmutableSet(singletonSet);
162
163 List<Integer> singletonList = singletonList(1);
164 equal(singletonList.size(), 1);
165 testCollection(singletonList);
166 testImmutableList(singletonList);
167 testImmutableList(singletonList.subList(0,1));
168 testImmutableList(singletonList.subList(0,1).subList(0,1));
169 testEmptyList(singletonList.subList(0,0));
170 testEmptyList(singletonList.subList(0,0).subList(0,0));
171
172 Map<Integer,Integer> singletonMap = singletonMap(1,2);
173 equal(singletonMap.size(), 1);
174 testMap(singletonMap);
175 testImmutableMap(singletonMap);
176 }
177
178 private static void checkContainsSelf(Collection<Integer> c) {
179 check(c.containsAll(c));
180 check(c.containsAll(Arrays.asList(c.toArray())));
181 check(c.containsAll(Arrays.asList(c.toArray(new Integer[0]))));
182 }
183
184 private static void checkContainsEmpty(Collection<Integer> c) {
185 check(c.containsAll(new ArrayList<Integer>()));
186 }
187
188 private static <T> void testEmptyCollection(Collection<T> c) {
189 check(c.isEmpty());
190 equal(c.size(), 0);
191 equal(c.toString(),"[]");
192 equal(c.toArray().length, 0);
193 equal(c.toArray(new Object[0]).length, 0);
194 check(c.toArray(new Object[]{42})[0] == null);
195
196 Object[] a = new Object[1]; a[0] = Boolean.TRUE;
197 equal(c.toArray(a), a);
198 equal(a[0], null);
199 testEmptyIterator(c.iterator());
200 }
201
202 static <T> void testEmptyIterator(final Iterator<T> it) {
203 if (rnd.nextBoolean())
204 check(! it.hasNext());
205
206 THROWS(NoSuchElementException.class,
207 new Fun(){void f(){ it.next(); }});
208
209 try { it.remove(); }
210 catch (IllegalStateException _) { pass(); }
211 catch (UnsupportedOperationException _) { pass(); }
212 catch (Throwable t) { unexpected(t); }
213
214 if (rnd.nextBoolean())
215 check(! it.hasNext());
216 }
217
218 private static void testEmptyList(List<?> c) {
219 testEmptyCollection(c);
220 equal(c.hashCode(), 1);
221 equal2(c, Collections.<Integer>emptyList());
222 }
223
224 private static <T> void testEmptySet(Set<T> c) {
225 testEmptyCollection(c);
226 equal(c.hashCode(), 0);
227 equal2(c, Collections.<Integer>emptySet());
228 if (c instanceof NavigableSet<?>)
229 testEmptyIterator(((NavigableSet<T>)c).descendingIterator());
230 }
231
232 private static void testImmutableCollection(final Collection<Integer> c) {
233 THROWS(UnsupportedOperationException.class,
234 new Fun(){void f(){ c.add(99); }},
235 new Fun(){void f(){ c.addAll(singleton(99)); }});
236 if (! c.isEmpty()) {
237 final Integer first = c.iterator().next();
238 THROWS(UnsupportedOperationException.class,
239 new Fun(){void f(){ c.clear(); }},
240 new Fun(){void f(){ c.remove(first); }},
241 new Fun(){void f(){ c.removeAll(singleton(first)); }},
242 new Fun(){void f(){ c.retainAll(emptyList()); }}
243 );
244 }
245 }
246
247 private static void testImmutableSet(final Set<Integer> c) {
248 testImmutableCollection(c);
249 }
250
251 private static void testImmutableList(final List<Integer> c) {
252 testList(c);
253 testImmutableCollection(c);
254 THROWS(UnsupportedOperationException.class,
255 new Fun(){void f(){ c.set(0,42); }},
256 new Fun(){void f(){ c.add(0,42); }},
257 new Fun(){void f(){ c.addAll(0,singleton(86)); }});
258 if (! c.isEmpty())
259 THROWS(UnsupportedOperationException.class,
260 new Fun(){void f(){
261 Iterator<Integer> it = c.iterator();
262 it.next(); it.remove();}},
263 new Fun(){void f(){
264 ListIterator<Integer> it = c.listIterator();
265 it.next(); it.remove();}});
266 }
267
268 private static void clear(Collection<Integer> c) {
269 try { c.clear(); }
270 catch (Throwable t) { unexpected(t); }
271 testEmptyCollection(c);
272 }
273
274 private static <K,V> void testEmptyMap(final Map<K,V> m) {
275 check(m.isEmpty());
276 equal(m.size(), 0);
277 equal(m.toString(),"{}");
278 testEmptySet(m.keySet());
279 testEmptySet(m.entrySet());
280 testEmptyCollection(m.values());
281
282 try { check(! m.containsValue(null)); }
283 catch (NullPointerException _) { /* OK */ }
284 try { check(! m.containsKey(null)); }
285 catch (NullPointerException _) { /* OK */ }
286 check(! m.containsValue(1));
287 check(! m.containsKey(1));
288 }
289
290 private static void testImmutableMap(final Map<Integer,Integer> m) {
291 THROWS(UnsupportedOperationException.class,
292 new Fun(){void f(){ m.put(1,1); }},
293 new Fun(){void f(){ m.putAll(singletonMap(1,1)); }});
294 if (! m.isEmpty()) {
295 final Integer first = m.keySet().iterator().next();
296 THROWS(UnsupportedOperationException.class,
297 new Fun(){void f(){ m.remove(first); }},
298 new Fun(){void f(){ m.clear(); }});
299 final Map.Entry<Integer,Integer> me
300 = m.entrySet().iterator().next();
301 Integer key = me.getKey();
302 Integer val = me.getValue();
303 THROWS(UnsupportedOperationException.class,
304 new Fun(){void f(){ me.setValue(3); }});
305 equal(key, me.getKey());
306 equal(val, me.getValue());
307 }
308 testImmutableSet(m.keySet());
309 testImmutableCollection(m.values());
310 //testImmutableSet(m.entrySet());
311 }
312
313 private static void clear(Map<?,?> m) {
314 try { m.clear(); }
315 catch (Throwable t) { unexpected(t); }
316 testEmptyMap(m);
317 }
318
319 private static void oneElement(Collection<Integer> c) {
320 clear(c);
321 try {
322 check(c.add(-42));
323 equal(c.toString(), "[-42]");
324 if (c instanceof Set) check(! c.add(-42));
325 } catch (Throwable t) { unexpected(t); }
326 check(! c.isEmpty()); check(c.size() == 1);
327 }
328
329 private static boolean supportsAdd(Collection<Integer> c) {
330 try { check(c.add(778347983)); }
331 catch (UnsupportedOperationException t) { return false; }
332 catch (Throwable t) { unexpected(t); }
333
334 try {
335 check(c.contains(778347983));
336 check(c.remove(778347983));
337 } catch (Throwable t) { unexpected(t); }
338 return true;
339 }
340
341 private static boolean supportsRemove(Collection<Integer> c) {
342 try { check(! c.remove(19134032)); }
343 catch (UnsupportedOperationException t) { return false; }
344 catch (Throwable t) { unexpected(t); }
345 return true;
346 }
347
348 private static void checkFunctionalInvariants(Collection<Integer> c) {
349 try {
350 checkContainsSelf(c);
351 checkContainsEmpty(c);
352 check(c.size() != 0 ^ c.isEmpty());
353
354 {
355 int size = 0;
356 for (Integer i : c) size++;
357 check(c.size() == size);
358 }
359
360 check(c.toArray().length == c.size());
361 check(c.toArray().getClass() == Object[].class
362 ||
363 // !!!!
364 // 6260652: (coll) Arrays.asList(x).toArray().getClass()
365 // should be Object[].class
366 (c.getClass().getName().equals("java.util.Arrays$ArrayList"))
367 );
368 for (int size : new int[]{0,1,c.size(), c.size()+1}) {
369 Integer[] a = c.toArray(new Integer[size]);
370 check((size > c.size()) || a.length == c.size());
371 int i = 0; for (Integer j : c) check(a[i++] == j);
372 check((size <= c.size()) || (a[c.size()] == null));
373 check(a.getClass() == Integer[].class);
374 }
375
376 check(c.equals(c));
377 if (c instanceof Serializable) {
378 //System.out.printf("Serializing %s%n", c.getClass().getName());
379 try {
380 Object clone = serialClone(c);
381 equal(c instanceof Serializable,
382 clone instanceof Serializable);
383 equal(c instanceof RandomAccess,
384 clone instanceof RandomAccess);
385 if ((c instanceof List) || (c instanceof Set))
386 equal(c, clone);
387 else
388 equal(new HashSet<Integer>(c),
389 new HashSet<Integer>(serialClone(c)));
390 } catch (Error xxx) {
391 if (! (xxx.getCause() instanceof NotSerializableException))
392 throw xxx;
393 }
394 }
395 }
396 catch (Throwable t) { unexpected(t); }
397 }
398
399 //----------------------------------------------------------------
400 // If add(null) succeeds, contains(null) & remove(null) should succeed
401 //----------------------------------------------------------------
402 private static void testNullElement(Collection<Integer> c) {
403 // !!!! 5018849: (coll) TreeSet.contains(null) does not agree with Javadoc
404 if (c instanceof TreeSet) return;
405
406 try {
407 check(c.add(null));
408 if (c.size() == 1)
409 equal(c.toString(), "[null]");
410 try {
411 checkFunctionalInvariants(c);
412 check(c.contains(null));
413 check(c.remove(null));
414 }
415 catch (Throwable t) { unexpected(t); }
416 }
417 catch (NullPointerException e) { /* OK */ }
418 catch (Throwable t) { unexpected(t); }
419 }
420
421
422 //----------------------------------------------------------------
423 // If add("x") succeeds, contains("x") & remove("x") should succeed
424 //----------------------------------------------------------------
425 @SuppressWarnings("unchecked")
426 private static void testStringElement(Collection<Integer> c) {
427 Collection x = (Collection)c; // Make type-unsafe
428 try {
429 check(x.add("x"));
430 try {
431 check(x.contains("x"));
432 check(x.remove("x"));
433 } catch (Throwable t) { unexpected(t); }
434 }
435 catch (ClassCastException e) { /* OK */ }
436 catch (Throwable t) { unexpected(t); }
437 }
438
439 private static void testConcurrentCollection(Collection<Integer> c) {
440 try {
441 c.add(1);
442 Iterator<Integer> it = c.iterator();
443 check(it.hasNext());
444 clear(c);
445 check(it.next() instanceof Integer); // No CME
446 check(c.isEmpty());
447 }
448 catch (Throwable t) { unexpected(t); }
449 }
450
451 private static void testQueue(Queue<Integer> q) {
452 q.clear();
453 for (int i = 0; i < 5; i++) {
454 testQueueAddRemove(q, null);
455 testQueueAddRemove(q, 537);
456 q.add(i);
457 }
458 equal(q.size(), 5);
459 checkFunctionalInvariants(q);
460 q.poll();
461 equal(q.size(), 4);
462 checkFunctionalInvariants(q);
463 if ((q instanceof LinkedBlockingQueue) ||
464 (q instanceof LinkedBlockingDeque) ||
465 (q instanceof ConcurrentLinkedDeque) ||
466 (q instanceof ConcurrentLinkedQueue)) {
467 testQueueIteratorRemove(q);
468 }
469 }
470
471 private static void testQueueAddRemove(final Queue<Integer> q,
472 final Integer e) {
473 final List<Integer> originalContents = new ArrayList<Integer>(q);
474 final boolean isEmpty = q.isEmpty();
475 final boolean isList = (q instanceof List);
476 final List asList = isList ? (List) q : null;
477 check(!q.contains(e));
478 try {
479 q.add(e);
480 } catch (NullPointerException npe) {
481 check(e == null);
482 return; // Null elements not supported
483 }
484 check(q.contains(e));
485 check(q.remove(e));
486 check(!q.contains(e));
487 equal(new ArrayList<Integer>(q), originalContents);
488
489 if (q instanceof Deque<?>) {
490 final Deque<Integer> deq = (Deque<Integer>) q;
491 final List<Integer> singleton = Collections.singletonList(e);
492
493 // insert, query, remove element at head
494 if (isEmpty) {
495 THROWS(NoSuchElementException.class,
496 new Fun(){void f(){ deq.getFirst(); }},
497 new Fun(){void f(){ deq.element(); }},
498 new Fun(){void f(){ deq.iterator().next(); }});
499 check(deq.peekFirst() == null);
500 check(deq.peek() == null);
501 } else {
502 check(deq.getFirst() != e);
503 check(deq.element() != e);
504 check(deq.iterator().next() != e);
505 check(deq.peekFirst() != e);
506 check(deq.peek() != e);
507 }
508 check(!deq.contains(e));
509 check(!deq.removeFirstOccurrence(e));
510 check(!deq.removeLastOccurrence(e));
511 if (isList) {
512 check(asList.indexOf(e) == -1);
513 check(asList.lastIndexOf(e) == -1);
514 }
515 switch (rnd.nextInt(isList ? 4 : 3)) {
516 case 0: deq.addFirst(e); break;
517 case 1: check(deq.offerFirst(e)); break;
518 case 2: deq.push(e); break;
519 case 3: asList.add(0, e); break;
520 default: throw new AssertionError();
521 }
522 check(deq.peekFirst() == e);
523 check(deq.getFirst() == e);
524 check(deq.element() == e);
525 check(deq.peek() == e);
526 check(deq.iterator().next() == e);
527 check(deq.contains(e));
528 if (isList) {
529 check(asList.get(0) == e);
530 check(asList.indexOf(e) == 0);
531 check(asList.lastIndexOf(e) == 0);
532 check(asList.subList(0, 1).equals(singleton));
533 }
534 switch (rnd.nextInt(isList ? 11 : 9)) {
535 case 0: check(deq.pollFirst() == e); break;
536 case 1: check(deq.removeFirst() == e); break;
537 case 2: check(deq.remove() == e); break;
538 case 3: check(deq.pop() == e); break;
539 case 4: check(deq.removeFirstOccurrence(e)); break;
540 case 5: check(deq.removeLastOccurrence(e)); break;
541 case 6: check(deq.remove(e)); break;
542 case 7: check(deq.removeAll(singleton)); break;
543 case 8: Iterator it = deq.iterator(); it.next(); it.remove(); break;
544 case 9: asList.remove(0); break;
545 case 10: asList.subList(0, 1).clear(); break;
546 default: throw new AssertionError();
547 }
548 if (isEmpty) {
549 THROWS(NoSuchElementException.class,
550 new Fun(){void f(){ deq.getFirst(); }},
551 new Fun(){void f(){ deq.element(); }},
552 new Fun(){void f(){ deq.iterator().next(); }});
553 check(deq.peekFirst() == null);
554 check(deq.peek() == null);
555 } else {
556 check(deq.getFirst() != e);
557 check(deq.element() != e);
558 check(deq.iterator().next() != e);
559 check(deq.peekFirst() != e);
560 check(deq.peek() != e);
561 }
562 check(!deq.contains(e));
563 check(!deq.removeFirstOccurrence(e));
564 check(!deq.removeLastOccurrence(e));
565 if (isList) {
566 check(isEmpty || asList.get(0) != e);
567 check(asList.indexOf(e) == -1);
568 check(asList.lastIndexOf(e) == -1);
569 }
570 equal(new ArrayList<Integer>(deq), originalContents);
571
572 // insert, query, remove element at tail
573 if (isEmpty) {
574 check(deq.peekLast() == null);
575 THROWS(NoSuchElementException.class,
576 new Fun(){void f(){ deq.getLast(); }});
577 } else {
578 check(deq.peekLast() != e);
579 check(deq.getLast() != e);
580 }
581 switch (rnd.nextInt(isList ? 6 : 4)) {
582 case 0: deq.addLast(e); break;
583 case 1: check(deq.offerLast(e)); break;
584 case 2: check(deq.add(e)); break;
585 case 3: deq.addAll(singleton); break;
586 case 4: asList.addAll(deq.size(), singleton); break;
587 case 5: asList.add(deq.size(), e); break;
588 default: throw new AssertionError();
589 }
590 check(deq.peekLast() == e);
591 check(deq.getLast() == e);
592 check(deq.contains(e));
593 if (isList) {
594 ListIterator it = asList.listIterator(asList.size());
595 check(it.previous() == e);
596 check(asList.get(asList.size() - 1) == e);
597 check(asList.indexOf(e) == asList.size() - 1);
598 check(asList.lastIndexOf(e) == asList.size() - 1);
599 int size = asList.size();
600 check(asList.subList(size - 1, size).equals(singleton));
601 }
602 switch (rnd.nextInt(isList ? 8 : 6)) {
603 case 0: check(deq.pollLast() == e); break;
604 case 1: check(deq.removeLast() == e); break;
605 case 2: check(deq.removeFirstOccurrence(e)); break;
606 case 3: check(deq.removeLastOccurrence(e)); break;
607 case 4: check(deq.remove(e)); break;
608 case 5: check(deq.removeAll(singleton)); break;
609 case 6: asList.remove(asList.size() - 1); break;
610 case 7:
611 ListIterator it = asList.listIterator(asList.size());
612 it.previous();
613 it.remove();
614 break;
615 default: throw new AssertionError();
616 }
617 if (isEmpty) {
618 check(deq.peekLast() == null);
619 THROWS(NoSuchElementException.class,
620 new Fun(){void f(){ deq.getLast(); }});
621 } else {
622 check(deq.peekLast() != e);
623 check(deq.getLast() != e);
624 }
625 check(!deq.contains(e));
626 equal(new ArrayList<Integer>(deq), originalContents);
627
628 // Test operations on empty deque
629 switch (rnd.nextInt(isList ? 4 : 2)) {
630 case 0: deq.clear(); break;
631 case 1:
632 Iterator it = deq.iterator();
633 while (it.hasNext()) {
634 it.next();
635 it.remove();
636 }
637 break;
638 case 2: asList.subList(0, asList.size()).clear(); break;
639 case 3:
640 ListIterator lit = asList.listIterator(asList.size());
641 while (lit.hasPrevious()) {
642 lit.previous();
643 lit.remove();
644 }
645 break;
646 default: throw new AssertionError();
647 }
648 testEmptyCollection(deq);
649 check(!deq.iterator().hasNext());
650 if (isList) {
651 check(!asList.listIterator().hasPrevious());
652 THROWS(NoSuchElementException.class,
653 new Fun(){void f(){ asList.listIterator().previous(); }});
654 }
655 THROWS(NoSuchElementException.class,
656 new Fun(){void f(){ deq.iterator().next(); }},
657 new Fun(){void f(){ deq.element(); }},
658 new Fun(){void f(){ deq.getFirst(); }},
659 new Fun(){void f(){ deq.getLast(); }},
660 new Fun(){void f(){ deq.pop(); }},
661 new Fun(){void f(){ deq.remove(); }},
662 new Fun(){void f(){ deq.removeFirst(); }},
663 new Fun(){void f(){ deq.removeLast(); }});
664
665 check(deq.poll() == null);
666 check(deq.pollFirst() == null);
667 check(deq.pollLast() == null);
668 check(deq.peek() == null);
669 check(deq.peekFirst() == null);
670 check(deq.peekLast() == null);
671 check(!deq.removeFirstOccurrence(e));
672 check(!deq.removeLastOccurrence(e));
673
674 check(deq.addAll(originalContents) == !isEmpty);
675 equal(new ArrayList<Integer>(deq), originalContents);
676 check(!deq.addAll(Collections.<Integer>emptyList()));
677 equal(new ArrayList<Integer>(deq), originalContents);
678 }
679 }
680
681 private static void testQueueIteratorRemove(Queue<Integer> q) {
682 System.err.printf("testQueueIteratorRemove %s%n",
683 q.getClass().getSimpleName());
684 q.clear();
685 for (int i = 0; i < 5; i++)
686 q.add(i);
687 Iterator<Integer> it = q.iterator();
688 check(it.hasNext());
689 for (int i = 3; i >= 0; i--)
690 q.remove(i);
691 equal(it.next(), 0);
692 equal(it.next(), 4);
693
694 q.clear();
695 for (int i = 0; i < 5; i++)
696 q.add(i);
697 it = q.iterator();
698 equal(it.next(), 0);
699 check(it.hasNext());
700 for (int i = 1; i < 4; i++)
701 q.remove(i);
702 equal(it.next(), 1);
703 equal(it.next(), 4);
704 }
705
706 private static void testList(final List<Integer> l) {
707 //----------------------------------------------------------------
708 // 4802633: (coll) AbstractList.addAll(-1,emptyCollection)
709 // doesn't throw IndexOutOfBoundsException
710 //----------------------------------------------------------------
711 try {
712 l.addAll(-1, Collections.<Integer>emptyList());
713 fail("Expected IndexOutOfBoundsException not thrown");
714 }
715 catch (UnsupportedOperationException _) {/* OK */}
716 catch (IndexOutOfBoundsException _) {/* OK */}
717 catch (Throwable t) { unexpected(t); }
718
719 // equal(l instanceof Serializable,
720 // l.subList(0,0) instanceof Serializable);
721 if (l.subList(0,0) instanceof Serializable)
722 check(l instanceof Serializable);
723
724 equal(l instanceof RandomAccess,
725 l.subList(0,0) instanceof RandomAccess);
726 }
727
728 private static void testCollection(Collection<Integer> c) {
729 try { testCollection1(c); }
730 catch (Throwable t) { unexpected(t); }
731 }
732
733 private static void testCollection1(Collection<Integer> c) {
734
735 System.out.println("\n==> " + c.getClass().getName());
736
737 checkFunctionalInvariants(c);
738
739 if (! supportsAdd(c)) return;
740 //System.out.println("add() supported");
741
742 if (c instanceof NavigableSet) {
743 System.out.println("NavigableSet tests...");
744
745 NavigableSet<Integer> ns = (NavigableSet<Integer>)c;
746 testNavigableSet(ns);
747 testNavigableSet(ns.headSet(6, false));
748 testNavigableSet(ns.headSet(5, true));
749 testNavigableSet(ns.tailSet(0, false));
750 testNavigableSet(ns.tailSet(1, true));
751 testNavigableSet(ns.subSet(0, false, 5, true));
752 testNavigableSet(ns.subSet(1, true, 6, false));
753 }
754
755 if (c instanceof Queue)
756 testQueue((Queue<Integer>)c);
757
758 if (c instanceof List)
759 testList((List<Integer>)c);
760
761 check(supportsRemove(c));
762
763 try {
764 oneElement(c);
765 checkFunctionalInvariants(c);
766 }
767 catch (Throwable t) { unexpected(t); }
768
769 clear(c); testNullElement(c);
770 oneElement(c); testNullElement(c);
771
772 clear(c); testStringElement(c);
773 oneElement(c); testStringElement(c);
774
775 if (c.getClass().getName().matches(".*concurrent.*"))
776 testConcurrentCollection(c);
777
778 //----------------------------------------------------------------
779 // The "all" operations should throw NPE when passed null
780 //----------------------------------------------------------------
781 {
782 clear(c);
783 try {
784 c.removeAll(null);
785 fail("Expected NullPointerException");
786 }
787 catch (NullPointerException e) { pass(); }
788 catch (Throwable t) { unexpected(t); }
789
790 oneElement(c);
791 try {
792 c.removeAll(null);
793 fail("Expected NullPointerException");
794 }
795 catch (NullPointerException e) { pass(); }
796 catch (Throwable t) { unexpected(t); }
797
798 clear(c);
799 try {
800 c.retainAll(null);
801 fail("Expected NullPointerException");
802 }
803 catch (NullPointerException e) { pass(); }
804 catch (Throwable t) { unexpected(t); }
805
806 oneElement(c);
807 try {
808 c.retainAll(null);
809 fail("Expected NullPointerException");
810 }
811 catch (NullPointerException e) { pass(); }
812 catch (Throwable t) { unexpected(t); }
813
814 oneElement(c);
815 try {
816 c.addAll(null);
817 fail("Expected NullPointerException");
818 }
819 catch (NullPointerException e) { pass(); }
820 catch (Throwable t) { unexpected(t); }
821
822 oneElement(c);
823 try {
824 c.containsAll(null);
825 fail("Expected NullPointerException");
826 }
827 catch (NullPointerException e) { pass(); }
828 catch (Throwable t) { unexpected(t); }
829 }
830 }
831
832 //----------------------------------------------------------------
833 // Map
834 //----------------------------------------------------------------
835 private static void checkFunctionalInvariants(Map<Integer,Integer> m) {
836 check(m.keySet().size() == m.entrySet().size());
837 check(m.keySet().size() == m.size());
838 checkFunctionalInvariants(m.keySet());
839 checkFunctionalInvariants(m.values());
840 check(m.size() != 0 ^ m.isEmpty());
841 }
842
843 private static void testMap(Map<Integer,Integer> m) {
844 System.out.println("\n==> " + m.getClass().getName());
845
846 if (m instanceof ConcurrentMap)
847 testConcurrentMap((ConcurrentMap<Integer,Integer>) m);
848
849 if (m instanceof NavigableMap) {
850 System.out.println("NavigableMap tests...");
851
852 NavigableMap<Integer,Integer> nm =
853 (NavigableMap<Integer,Integer>) m;
854 testNavigableMapRemovers(nm);
855 testNavigableMap(nm);
856 testNavigableMap(nm.headMap(6, false));
857 testNavigableMap(nm.headMap(5, true));
858 testNavigableMap(nm.tailMap(0, false));
859 testNavigableMap(nm.tailMap(1, true));
860 testNavigableMap(nm.subMap(1, true, 6, false));
861 testNavigableMap(nm.subMap(0, false, 5, true));
862 }
863
864 checkFunctionalInvariants(m);
865
866 if (supportsClear(m)) {
867 try { clear(m); }
868 catch (Throwable t) { unexpected(t); }
869 }
870
871 if (supportsPut(m)) {
872 try {
873 check(m.put(3333, 77777) == null);
874 check(m.put(9134, 74982) == null);
875 check(m.get(9134) == 74982);
876 check(m.put(9134, 1382) == 74982);
877 check(m.get(9134) == 1382);
878 check(m.size() == 2);
879 checkFunctionalInvariants(m);
880 checkNPEConsistency(m);
881 }
882 catch (Throwable t) { unexpected(t); }
883 }
884 }
885
886 private static boolean supportsPut(Map<Integer,Integer> m) {
887 // We're asking for .equals(...) semantics
888 if (m instanceof IdentityHashMap) return false;
889
890 try { check(m.put(778347983,12735) == null); }
891 catch (UnsupportedOperationException t) { return false; }
892 catch (Throwable t) { unexpected(t); }
893
894 try {
895 check(m.containsKey(778347983));
896 check(m.remove(778347983) != null);
897 } catch (Throwable t) { unexpected(t); }
898 return true;
899 }
900
901 private static boolean supportsClear(Map<?,?> m) {
902 try { m.clear(); }
903 catch (UnsupportedOperationException t) { return false; }
904 catch (Throwable t) { unexpected(t); }
905 return true;
906 }
907
908 //----------------------------------------------------------------
909 // ConcurrentMap
910 //----------------------------------------------------------------
911 private static void testConcurrentMap(ConcurrentMap<Integer,Integer> m) {
912 System.out.println("ConcurrentMap tests...");
913
914 try {
915 clear(m);
916
917 check(m.putIfAbsent(18357,7346) == null);
918 check(m.containsKey(18357));
919 check(m.putIfAbsent(18357,8263) == 7346);
920 try { m.putIfAbsent(18357,null); fail("NPE"); }
921 catch (NullPointerException t) { }
922 check(m.containsKey(18357));
923
924 check(! m.replace(18357,8888,7777));
925 check(m.containsKey(18357));
926 try { m.replace(18357,null,7777); fail("NPE"); }
927 catch (NullPointerException t) { }
928 check(m.containsKey(18357));
929 check(m.get(18357) == 7346);
930 check(m.replace(18357,7346,5555));
931 check(m.replace(18357,5555,7346));
932 check(m.get(18357) == 7346);
933
934 check(m.replace(92347,7834) == null);
935 try { m.replace(18357,null); fail("NPE"); }
936 catch (NullPointerException t) { }
937 check(m.replace(18357,7346) == 7346);
938 check(m.replace(18357,5555) == 7346);
939 check(m.get(18357) == 5555);
940 check(m.replace(18357,7346) == 5555);
941 check(m.get(18357) == 7346);
942
943 check(! m.remove(18357,9999));
944 check(m.get(18357) == 7346);
945 check(m.containsKey(18357));
946 check(! m.remove(18357,null)); // 6272521
947 check(m.get(18357) == 7346);
948 check(m.remove(18357,7346));
949 check(m.get(18357) == null);
950 check(! m.containsKey(18357));
951 check(m.isEmpty());
952
953 m.putIfAbsent(1,2);
954 check(m.size() == 1);
955 check(! m.remove(1,null));
956 check(! m.remove(1,null));
957 check(! m.remove(1,1));
958 check(m.remove(1,2));
959 check(m.isEmpty());
960
961 testEmptyMap(m);
962 }
963 catch (Throwable t) { unexpected(t); }
964 }
965
966 private static void throwsConsistently(Class<? extends Throwable> k,
967 Iterable<Fun> fs) {
968 List<Class<? extends Throwable>> threw
969 = new ArrayList<Class<? extends Throwable>>();
970 for (Fun f : fs)
971 try { f.f(); threw.add(null); }
972 catch (Throwable t) {
973 check(k.isAssignableFrom(t.getClass()));
974 threw.add(t.getClass());
975 }
976 if (new HashSet<Object>(threw).size() != 1)
977 fail(threw.toString());
978 }
979
980 private static <T> void checkNPEConsistency(final Map<T,Integer> m) {
981 m.clear();
982 final ConcurrentMap<T,Integer> cm = (m instanceof ConcurrentMap)
983 ? (ConcurrentMap<T,Integer>) m
984 : null;
985 List<Fun> fs = new ArrayList<Fun>();
986 fs.add(new Fun(){void f(){ check(! m.containsKey(null));}});
987 fs.add(new Fun(){void f(){ equal(m.remove(null), null);}});
988 fs.add(new Fun(){void f(){ equal(m.get(null), null);}});
989 if (cm != null) {
990 fs.add(new Fun(){void f(){ check(! cm.remove(null,null));}});}
991 throwsConsistently(NullPointerException.class, fs);
992
993 fs.clear();
994 final Map<T,Integer> sm = singletonMap(null,1);
995 fs.add(new Fun(){void f(){ equal(m.put(null,1), null); m.clear();}});
996 fs.add(new Fun(){void f(){ m.putAll(sm); m.clear();}});
997 if (cm != null) {
998 fs.add(new Fun(){void f(){ check(! cm.remove(null,null));}});
999 fs.add(new Fun(){void f(){ equal(cm.putIfAbsent(null,1), 1);}});
1000 fs.add(new Fun(){void f(){ equal(cm.replace(null,1), null);}});
1001 fs.add(new Fun(){void f(){ equal(cm.replace(null,1, 1), 1);}});
1002 }
1003 throwsConsistently(NullPointerException.class, fs);
1004 }
1005
1006 //----------------------------------------------------------------
1007 // NavigableMap
1008 //----------------------------------------------------------------
1009 private static void
1010 checkNavigableMapKeys(NavigableMap<Integer,Integer> m,
1011 Integer i,
1012 Integer lower,
1013 Integer floor,
1014 Integer ceiling,
1015 Integer higher) {
1016 equal(m.lowerKey(i), lower);
1017 equal(m.floorKey(i), floor);
1018 equal(m.ceilingKey(i), ceiling);
1019 equal(m.higherKey(i), higher);
1020 }
1021
1022 private static void
1023 checkNavigableSetKeys(NavigableSet<Integer> m,
1024 Integer i,
1025 Integer lower,
1026 Integer floor,
1027 Integer ceiling,
1028 Integer higher) {
1029 equal(m.lower(i), lower);
1030 equal(m.floor(i), floor);
1031 equal(m.ceiling(i), ceiling);
1032 equal(m.higher(i), higher);
1033 }
1034
1035 static final Random rnd = new Random();
1036 static void equalNext(final Iterator<?> it, Object expected) {
1037 if (rnd.nextBoolean())
1038 check(it.hasNext());
1039 equal(it.next(), expected);
1040 }
1041
1042 static void equalMaps(Map m1, Map m2) {
1043 equal(m1, m2);
1044 equal(m2, m1);
1045 equal(m1.size(), m2.size());
1046 equal(m1.isEmpty(), m2.isEmpty());
1047 equal(m1.toString(), m2.toString());
1048 check(Arrays.equals(m1.entrySet().toArray(), m2.entrySet().toArray()));
1049 }
1050
1051 @SuppressWarnings({"unchecked", "rawtypes"})
1052 static void testNavigableMapRemovers(NavigableMap m)
1053 {
1054 final Map emptyMap = new HashMap();
1055
1056 final Map singletonMap = new HashMap();
1057 singletonMap.put(1, 2);
1058
1059 abstract class NavigableMapView {
1060 abstract NavigableMap view(NavigableMap m);
1061 }
1062
1063 NavigableMapView[] views = {
1064 new NavigableMapView() { NavigableMap view(NavigableMap m) {
1065 return m; }},
1066 new NavigableMapView() { NavigableMap view(NavigableMap m) {
1067 return m.headMap(99, true); }},
1068 new NavigableMapView() { NavigableMap view(NavigableMap m) {
1069 return m.tailMap(-99, false); }},
1070 new NavigableMapView() { NavigableMap view(NavigableMap m) {
1071 return m.subMap(-99, true, 99, false); }},
1072 };
1073
1074 abstract class Remover {
1075 abstract void remove(NavigableMap m, Object k, Object v);
1076 }
1077
1078 Remover[] removers = {
1079 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1080 equal(m.remove(k), v); }},
1081
1082 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1083 equal(m.descendingMap().remove(k), v); }},
1084 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1085 equal(m.descendingMap().headMap(-86, false).remove(k), v); }},
1086 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1087 equal(m.descendingMap().tailMap(86, true).remove(k), v); }},
1088
1089 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1090 equal(m.headMap(86, true).remove(k), v); }},
1091 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1092 equal(m.tailMap(-86, true).remove(k), v); }},
1093 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1094 equal(m.subMap(-86, false, 86, true).remove(k), v); }},
1095
1096 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1097 check(m.keySet().remove(k)); }},
1098 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1099 check(m.navigableKeySet().remove(k)); }},
1100
1101 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1102 check(m.navigableKeySet().headSet(86, true).remove(k)); }},
1103 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1104 check(m.navigableKeySet().tailSet(-86, false).remove(k)); }},
1105 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1106 check(m.navigableKeySet().subSet(-86, true, 86, false)
1107 .remove(k)); }},
1108
1109 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1110 check(m.descendingKeySet().headSet(-86, false).remove(k)); }},
1111 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1112 check(m.descendingKeySet().tailSet(86, true).remove(k)); }},
1113 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1114 check(m.descendingKeySet().subSet(86, true, -86, false)
1115 .remove(k)); }},
1116 };
1117
1118 for (NavigableMapView view : views) {
1119 for (Remover remover : removers) {
1120 try {
1121 m.clear();
1122 equalMaps(m, emptyMap);
1123 equal(m.put(1, 2), null);
1124 equalMaps(m, singletonMap);
1125 NavigableMap v = view.view(m);
1126 remover.remove(v, 1, 2);
1127 equalMaps(m, emptyMap);
1128 } catch (Throwable t) { unexpected(t); }
1129 }
1130 }
1131 }
1132
1133 private static void testNavigableMap(NavigableMap<Integer,Integer> m)
1134 {
1135 clear(m);
1136 checkNavigableMapKeys(m, 1, null, null, null, null);
1137
1138 equal(m.put(1, 2), null);
1139 equal(m.put(3, 4), null);
1140 equal(m.put(5, 9), null);
1141
1142 equal(m.put(1, 2), 2);
1143 equal(m.put(3, 4), 4);
1144 equal(m.put(5, 6), 9);
1145
1146 checkNavigableMapKeys(m, 0, null, null, 1, 1);
1147 checkNavigableMapKeys(m, 1, null, 1, 1, 3);
1148 checkNavigableMapKeys(m, 2, 1, 1, 3, 3);
1149 checkNavigableMapKeys(m, 3, 1, 3, 3, 5);
1150 checkNavigableMapKeys(m, 5, 3, 5, 5, null);
1151 checkNavigableMapKeys(m, 6, 5, 5, null, null);
1152
1153 for (final Iterator<Integer> it :
1154 (Iterator<Integer>[])
1155 new Iterator<?>[] {
1156 m.descendingKeySet().iterator(),
1157 m.navigableKeySet().descendingIterator()}) {
1158 equalNext(it, 5);
1159 equalNext(it, 3);
1160 equalNext(it, 1);
1161 check(! it.hasNext());
1162 THROWS(NoSuchElementException.class,
1163 new Fun(){void f(){it.next();}});
1164 }
1165
1166 {
1167 final Iterator<Map.Entry<Integer,Integer>> it
1168 = m.descendingMap().entrySet().iterator();
1169 check(it.hasNext()); equal(it.next().getKey(), 5);
1170 check(it.hasNext()); equal(it.next().getKey(), 3);
1171 check(it.hasNext()); equal(it.next().getKey(), 1);
1172 check(! it.hasNext());
1173 THROWS(NoSuchElementException.class,
1174 new Fun(){void f(){it.next();}});
1175 }
1176 }
1177
1178
1179 private static void testNavigableSet(NavigableSet<Integer> s) {
1180 clear(s);
1181 checkNavigableSetKeys(s, 1, null, null, null, null);
1182
1183 check(s.add(1));
1184 check(s.add(3));
1185 check(s.add(5));
1186
1187 check(! s.add(1));
1188 check(! s.add(3));
1189 check(! s.add(5));
1190
1191 checkNavigableSetKeys(s, 0, null, null, 1, 1);
1192 checkNavigableSetKeys(s, 1, null, 1, 1, 3);
1193 checkNavigableSetKeys(s, 2, 1, 1, 3, 3);
1194 checkNavigableSetKeys(s, 3, 1, 3, 3, 5);
1195 checkNavigableSetKeys(s, 5, 3, 5, 5, null);
1196 checkNavigableSetKeys(s, 6, 5, 5, null, null);
1197
1198 for (final Iterator<Integer> it :
1199 (Iterator<Integer>[])
1200 new Iterator<?>[] {
1201 s.descendingIterator(),
1202 s.descendingSet().iterator()}) {
1203 equalNext(it, 5);
1204 equalNext(it, 3);
1205 equalNext(it, 1);
1206 check(! it.hasNext());
1207 THROWS(NoSuchElementException.class,
1208 new Fun(){void f(){it.next();}});
1209 }
1210 }
1211
1212 //--------------------- Infrastructure ---------------------------
1213 static volatile int passed = 0, failed = 0;
1214 static void pass() { passed++; }
1215 static void fail() { failed++; Thread.dumpStack(); }
1216 static void fail(String msg) { System.out.println(msg); fail(); }
1217 static void unexpected(Throwable t) { failed++; t.printStackTrace(); }
1218 static void check(boolean cond) { if (cond) pass(); else fail(); }
1219 static void equal(Object x, Object y) {
1220 if (x == null ? y == null : x.equals(y)) pass();
1221 else {System.out.println(x + " not equal to " + y); fail();}}
1222 static void equal2(Object x, Object y) {equal(x, y); equal(y, x);}
1223 public static void main(String[] args) throws Throwable {
1224 try { realMain(args); } catch (Throwable t) { unexpected(t); }
1225
1226 System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
1227 if (failed > 0) throw new Exception("Some tests failed");
1228 }
1229 private static abstract class Fun {abstract void f() throws Throwable;}
1230 private static void THROWS(Class<? extends Throwable> k, Fun... fs) {
1231 for (Fun f : fs)
1232 try { f.f(); fail("Expected " + k.getName() + " not thrown"); }
1233 catch (Throwable t) {
1234 if (k.isAssignableFrom(t.getClass())) pass();
1235 else unexpected(t);}}
1236 static byte[] serializedForm(Object obj) {
1237 try {
1238 ByteArrayOutputStream baos = new ByteArrayOutputStream();
1239 new ObjectOutputStream(baos).writeObject(obj);
1240 return baos.toByteArray();
1241 } catch (IOException e) { throw new Error(e); }}
1242 static Object readObject(byte[] bytes)
1243 throws IOException, ClassNotFoundException {
1244 InputStream is = new ByteArrayInputStream(bytes);
1245 return new ObjectInputStream(is).readObject();}
1246 @SuppressWarnings("unchecked")
1247 static <T> T serialClone(T obj) {
1248 try { return (T) readObject(serializedForm(obj)); }
1249 catch (Exception e) { throw new Error(e); }}
1250 private static class NewAbstractCollection<E> extends AbstractCollection<E> {
1251 ArrayList<E> list = new ArrayList<>();
1252 public boolean remove(Object obj) {
1253 return list.remove(obj);
1254 }
1255 public boolean add(E e) {
1256 return list.add(e);
1257 }
1258 public Iterator<E> iterator() {
1259 return list.iterator();
1260 }
1261 public int size() {
1262 return list.size();
1263 }
1264 }
1265 private static class NewAbstractSet<E> extends AbstractSet<E> {
1266 HashSet<E> set = new HashSet<>();
1267 public boolean remove(Object obj) {
1268 return set.remove(obj);
1269 }
1270 public boolean add(E e) {
1271 return set.add(e);
1272 }
1273 public Iterator<E> iterator() {
1274 return set.iterator();
1275 }
1276 public int size() {
1277 return set.size();
1278 }
1279 }
1280
1281 }