AbstractTestCollection


1   /*
2    *  Copyright 2001-2004 The Apache Software Foundation
3    *
4    *  Licensed under the Apache License, Version 2.0 (the "License");
5    *  you may not use this file except in compliance with the License.
6    *  You may obtain a copy of the License at
7    *
8    *      http://www.apache.org/licenses/LICENSE-2.0
9    *
10   *  Unless required by applicable law or agreed to in writing, software
11   *  distributed under the License is distributed on an "AS IS" BASIS,
12   *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   *  See the License for the specific language governing permissions and
14   *  limitations under the License.
15   */
16  package org.apache.commons.collections.collection;
17  
18  import java.io.ByteArrayInputStream  ;
19  import java.io.ByteArrayOutputStream  ;
20  import java.io.ObjectInputStream  ;
21  import java.io.ObjectOutputStream  ;
22  import java.io.Serializable  ;
23  import java.lang.reflect.Array  ;
24  import java.util.ArrayList  ;
25  import java.util.Arrays  ;
26  import java.util.Collection  ;
27  import java.util.Collections  ;
28  import java.util.ConcurrentModificationException  ;
29  import java.util.HashMap  ;
30  import java.util.HashSet  ;
31  import java.util.Iterator  ;
32  import java.util.List  ;
33  import java.util.Map  ;
34  import java.util.NoSuchElementException  ;
35  
36  import org.apache.commons.collections.AbstractTestObject;
37  
38  /**
39   * Abstract test class for {@link java.util.Collection} methods and contracts.
40   * <p>
41   * You should create a concrete subclass of this class to test any custom
42   * {@link Collection} implementation.  At minimum, you'll have to 
43   * implement the {@link #makeCollection()} method.  You might want to 
44   * override some of the additional public methods as well:
45   * <p>
46   * <b>Element Population Methods</b>
47   * <p>
48   * Override these if your collection restricts what kind of elements are
49   * allowed (for instance, if <code>null</code> is not permitted):
50   * <ul>
51   * <li>{@link #getFullElements()}
52   * <li>{@link #getOtherElements()}
53   * </ul>
54   * <p>
55   * <b>Supported Operation Methods</b>
56   * <p>
57   * Override these if your collection doesn't support certain operations:
58   * <ul>
59   * <li>{@link #isAddSupported()}
60   * <li>{@link #isRemoveSupported()}
61   * <li>{@link #areEqualElementsDistinguishable()}
62   * <li>{@link #isNullSupported()}
63   * <li>{@link #isFailFastSupported()}
64   * </ul>
65   * <p>
66   * <b>Fixture Methods</b>
67   * <p>
68   * Fixtures are used to verify that the the operation results in correct state
69   * for the collection.  Basically, the operation is performed against your
70   * collection implementation, and an identical operation is performed against a
71   * <i>confirmed</i> collection implementation.  A confirmed collection
72   * implementation is something like <code>java.util.ArrayList</code>, which is
73   * known to conform exactly to its collection interface's contract.  After the
74   * operation takes place on both your collection implementation and the
75   * confirmed collection implementation, the two collections are compared to see
76   * if their state is identical.  The comparison is usually much more involved
77   * than a simple <code>equals</code> test.  This verification is used to ensure
78   * proper modifications are made along with ensuring that the collection does
79   * not change when read-only modifications are made.
80   * <p>
81   * The {@link #collection} field holds an instance of your collection
82   * implementation; the {@link #confirmed} field holds an instance of the
83   * confirmed collection implementation.  The {@link #resetEmpty()} and 
84   * {@link #resetFull()} methods set these fields to empty or full collections,
85   * so that tests can proceed from a known state.
86   * <p>
87   * After a modification operation to both {@link #collection} and
88   * {@link #confirmed}, the {@link #verify()} method is invoked to compare
89   * the results.  You may want to override {@link #verify()} to perform
90   * additional verifications.  For instance, when testing the collection
91   * views of a map, {@link AbstractTestMap} would override {@link #verify()} to make
92   * sure the map is changed after the collection view is changed.
93   * <p>
94   * If you're extending this class directly, you will have to provide 
95   * implementations for the following:
96   * <ul>
97   * <li>{@link #makeConfirmedCollection()}
98   * <li>{@link #makeConfirmedFullCollection()}
99   * </ul>
100  * <p>
101  * Those methods should provide a confirmed collection implementation 
102  * that's compatible with your collection implementation.
103  * <p>
104  * If you're extending {@link AbstractTestList}, {@link AbstractTestSet},
105  * or {@link AbstractTestBag}, you probably don't have to worry about the
106  * above methods, because those three classes already override the methods
107  * to provide standard JDK confirmed collections.<P>
108  * <p>
109  * <b>Other notes</b>
110  * <p>
111  * If your {@link Collection} fails one of these tests by design,
112  * you may still use this base set of cases.  Simply override the
113  * test case (method) your {@link Collection} fails.
114  *
115  * @version $Revision: 1.8 $ $Date: 2004/06/01 22:55:14 $
116  * 
117  * @author Rodney Waldhoff
118  * @author Paul Jack
119  * @author Michael A. Smith
120  * @author Neil O'Toole
121  * @author Stephen Colebourne
122  */
123 public abstract class AbstractTestCollection extends AbstractTestObject {
124 
125     //
126     // NOTE: 
127     //
128     // Collection doesn't define any semantics for equals, and recommends you
129     // use reference-based default behavior of Object.equals.  (And a test for
130     // that already exists in AbstractTestObject).  Tests for equality of lists, sets
131     // and bags will have to be written in test subclasses.  Thus, there is no
132     // tests on Collection.equals nor any for Collection.hashCode.
133     //
134 
135 
136     // These fields are used by reset() and verify(), and any test
137     // method that tests a modification.
138 
139     /** 
140      *  A collection instance that will be used for testing.
141      */
142     public Collection   collection;
143 
144     /** 
145      *  Confirmed collection.  This is an instance of a collection that is
146      *  confirmed to conform exactly to the java.util.Collection contract.
147      *  Modification operations are tested by performing a mod on your 
148      *  collection, performing the exact same mod on an equivalent confirmed
149      *  collection, and then calling verify() to make sure your collection
150      *  still matches the confirmed collection.
151      */
152     public Collection   confirmed;
153 
154     /**
155      * JUnit constructor.
156      * 
157      * @param testName  the test class name
158      */
159     public AbstractTestCollection(String   testName) {
160         super(testName);
161     }
162 
163     //-----------------------------------------------------------------------
164     /**
165      *  Specifies whether equal elements in the collection are, in fact,
166      *  distinguishable with information not readily available.  That is, if a
167      *  particular value is to be removed from the collection, then there is
168      *  one and only one value that can be removed, even if there are other
169      *  elements which are equal to it.  
170      *
171      *  <P>In most collection cases, elements are not distinguishable (equal is
172      *  equal), thus this method defaults to return false.  In some cases,
173      *  however, they are.  For example, the collection returned from the map's
174      *  values() collection view are backed by the map, so while there may be
175      *  two values that are equal, their associated keys are not.  Since the
176      *  keys are distinguishable, the values are.
177      *
178      *  <P>This flag is used to skip some verifications for iterator.remove()
179      *  where it is impossible to perform an equivalent modification on the
180      *  confirmed collection because it is not possible to determine which
181      *  value in the confirmed collection to actually remove.  Tests that
182      *  override the default (i.e. where equal elements are distinguishable),
183      *  should provide additional tests on iterator.remove() to make sure the
184      *  proper elements are removed when remove() is called on the iterator.
185      **/
186     public boolean areEqualElementsDistinguishable() {
187         return false;
188     }
189 
190     /**
191      *  Returns true if the collections produced by 
192      *  {@link #makeCollection()} and {@link #makeFullCollection()}
193      *  support the <code>add</code> and <code>addAll</code>
194      *  operations.<P>
195      *  Default implementation returns true.  Override if your collection
196      *  class does not support add or addAll.
197      */
198     public boolean isAddSupported() {
199         return true;
200     }
201 
202     /**
203      *  Returns true if the collections produced by 
204      *  {@link #makeCollection()} and {@link #makeFullCollection()}
205      *  support the <code>remove</code>, <code>removeAll</code>,
206      *  <code>retainAll</code>, <code>clear</code> and
207      *  <code>iterator().remove()</code> methods.
208      *  Default implementation returns true.  Override if your collection
209      *  class does not support removal operations.
210      */
211     public boolean isRemoveSupported() {
212         return true;
213     }
214 
215     /**
216      * Returns true to indicate that the collection supports holding null.
217      * The default implementation returns true;
218      */
219     public boolean isNullSupported() {
220         return true;
221     }
222 
223     /**
224      * Returns true to indicate that the collection supports fail fast iterators.
225      * The default implementation returns true;
226      */
227     public boolean isFailFastSupported() {
228         return false;
229     }
230 
231     /**
232      * Returns true to indicate that the collection supports equals() comparisons.
233      * This implementation returns false;
234      */
235     public boolean isEqualsCheckable() {
236         return false;
237     }
238 
239     //-----------------------------------------------------------------------
240     /**
241      *  Verifies that {@link #collection} and {@link #confirmed} have 
242      *  identical state.
243      */
244     public void verify() {
245         int confirmedSize = confirmed.size();
246         assertEquals("Collection size should match confirmed collection's",
247                      confirmedSize, collection.size());
248         assertEquals("Collection isEmpty() result should match confirmed " +
249                      " collection's", 
250                      confirmed.isEmpty(), collection.isEmpty());
251 
252         // verify the collections are the same by attempting to match each
253         // object in the collection and confirmed collection.  To account for
254         // duplicates and differing orders, each confirmed element is copied
255         // into an array and a flag is maintained for each element to determine
256         // whether it has been matched once and only once.  If all elements in
257         // the confirmed collection are matched once and only once and there
258         // aren't any elements left to be matched in the collection,
259         // verification is a success.
260 
261         // copy each collection value into an array
262         Object  [] confirmedValues = new Object  [confirmedSize];
263 
264         Iterator   iter;
265 
266         iter = confirmed.iterator(); 
267         int pos = 0;
268         while(iter.hasNext()) {
269             confirmedValues[pos++] = iter.next();
270         }
271 
272         // allocate an array of boolean flags for tracking values that have
273         // been matched once and only once.
274         boolean[] matched = new boolean[confirmedSize];
275         
276         // now iterate through the values of the collection and try to match
277         // the value with one in the confirmed array.
278         iter = collection.iterator();
279         while(iter.hasNext()) {
280             Object   o = iter.next();
281             boolean match = false;
282             for(int i = 0; i < confirmedSize; i++) {
283                 if(matched[i]) {
284                     // skip values already matched
285                     continue;
286                 }
287                 if(o == confirmedValues[i] ||
288                    (o != null && o.equals(confirmedValues[i]))) {
289                     // values matched
290                     matched[i] = true;
291                     match = true;
292                     break;
293                 }
294             }
295             // no match found!
296             if(!match) {
297                 fail("Collection should not contain a value that the " +
298                      "confirmed collection does not have: " + o +
299                      "\nTest: " + collection + "\nReal: " + confirmed);
300             }
301         }
302         
303         // make sure there aren't any unmatched values
304         for(int i = 0; i < confirmedSize; i++) {
305             if(!matched[i]) {
306                 // the collection didn't match all the confirmed values
307                 fail("Collection should contain all values that are in the confirmed collection" +
308                      "\nTest: " + collection + "\nReal: " + confirmed);
309             }
310         }
311     }
312     
313     //-----------------------------------------------------------------------
314     /**
315      *  Resets the {@link #collection} and {@link #confirmed} fields to empty
316      *  collections.  Invoke this method before performing a modification
317      *  test.
318      */
319     public void resetEmpty() {
320         this.collection = makeCollection();
321         this.confirmed = makeConfirmedCollection();
322     }
323 
324     /**
325      *  Resets the {@link #collection} and {@link #confirmed} fields to full
326      *  collections.  Invoke this method before performing a modification
327      *  test.
328      */
329     public void resetFull() {
330         this.collection = makeFullCollection();
331         this.confirmed = makeConfirmedFullCollection();
332     }
333 
334     //-----------------------------------------------------------------------
335     /**
336      *  Returns a confirmed empty collection.
337      *  For instance, an {@link java.util.ArrayList} for lists or a
338      *  {@link java.util.HashSet} for sets.
339      *
340      *  @return a confirmed empty collection
341      */
342     public abstract Collection   makeConfirmedCollection();
343 
344     /**
345      *  Returns a confirmed full collection.
346      *  For instance, an {@link java.util.ArrayList} for lists or a
347      *  {@link java.util.HashSet} for sets.  The returned collection
348      *  should contain the elements returned by {@link #getFullElements()}.
349      *
350      *  @return a confirmed full collection
351      */
352     public abstract Collection   makeConfirmedFullCollection();
353 
354     /**
355      * Return a new, empty {@link Collection} to be used for testing.
356      */
357     public abstract Collection   makeCollection();
358 
359     /**
360      *  Returns a full collection to be used for testing.  The collection
361      *  returned by this method should contain every element returned by
362      *  {@link #getFullElements()}.  The default implementation, in fact,
363      *  simply invokes <code>addAll</code> on an empty collection with
364      *  the results of {@link #getFullElements()}.  Override this default
365      *  if your collection doesn't support addAll.
366      */
367     public Collection   makeFullCollection() {
368         Collection   c = makeCollection();
369         c.addAll(Arrays.asList(getFullElements()));
370         return c;
371     }
372 
373     /**
374      *  Returns an empty collection for Object tests.
375      */
376     public Object   makeObject() {
377         return makeCollection();
378     }
379 
380     /**
381      * Creates a new Map Entry that is independent of the first and the map.
382      */
383     public Map.Entry   cloneMapEntry(Map.Entry   entry) {
384         HashMap   map = new HashMap  ();
385         map.put(entry.getKey(), entry.getValue());
386         return (Map.Entry  ) map.entrySet().iterator().next();
387     }
388 
389     //-----------------------------------------------------------------------
390     /**
391      *  Returns an array of objects that are contained in a collection
392      *  produced by {@link #makeFullCollection()}.  Every element in the
393      *  returned array <I>must</I> be an element in a full collection.<P>
394      *  The default implementation returns a heterogenous array of 
395      *  objects with some duplicates. null is added if allowed.
396      *  Override if you require specific testing elements.  Note that if you
397      *  override {@link #makeFullCollection()}, you <I>must</I> override
398      *  this method to reflect the contents of a full collection.
399      */
400     public Object  [] getFullElements() {
401         if (isNullSupported()) {
402             ArrayList   list = new ArrayList  ();
403             list.addAll(Arrays.asList(getFullNonNullElements()));
404             list.add(4, null);
405             return list.toArray();
406         } else {
407             return (Object  []) getFullNonNullElements().clone();
408         }
409     }
410 
411     /**
412      *  Returns an array of elements that are <I>not</I> contained in a
413      *  full collection.  Every element in the returned array must 
414      *  not exist in a collection returned by {@link #makeFullCollection()}.
415      *  The default implementation returns a heterogenous array of elements
416      *  without null.  Note that some of the tests add these elements
417      *  to an empty or full collection, so if your collection restricts
418      *  certain kinds of elements, you should override this method.
419      */
420     public Object  [] getOtherElements() {
421         return getOtherNonNullElements();
422     }
423     
424     //-----------------------------------------------------------------------
425     /**
426      *  Returns a list of elements suitable for return by
427      *  {@link #getFullElements()}.  The array returned by this method
428      *  does not include null, but does include a variety of objects 
429      *  of different types.  Override getFullElements to return
430      *  the results of this method if your collection does not support
431      *  the null element.
432      */
433     public Object  [] getFullNonNullElements() {
434         return new Object  [] {
435             new String  (""),
436             new String  ("One"),
437             new Integer  (2),
438             "Three",
439             new Integer  (4),
440             "One",
441             new Double  (5),
442             new Float  (6),
443             "Seven",
444             "Eight",
445             new String  ("Nine"),
446             new Integer  (10),
447             new Short  ((short)11),
448             new Long  (12),
449             "Thirteen",
450             "14",
451             "15",
452             new Byte  ((byte)16)
453         };
454     }
455 
456     /**
457      *  Returns the default list of objects returned by 
458      *  {@link #getOtherElements()}.  Includes many objects
459      *  of different types.
460      */
461     public Object  [] getOtherNonNullElements() {
462         return new Object  [] {
463             new Integer  (0),
464             new Float  (0),
465             new Double  (0),
466             "Zero",
467             new Short  ((short)0),
468             new Byte  ((byte)0),
469             new Long  (0),
470             new Character  ('\u0000'),
471             "0"
472         };
473     }
474 
475     /**
476      *  Returns a list of string elements suitable for return by
477      *  {@link #getFullElements()}.  Override getFullElements to return
478      *  the results of this method if your collection does not support
479      *  heterogenous elements or the null element.
480      */
481     public Object  [] getFullNonNullStringElements() {
482         return new Object  [] {
483             "If","the","dull","substance","of","my","flesh","were","thought",
484             "Injurious","distance","could","not","stop","my","way",
485         };
486     }
487 
488     /**
489      *  Returns a list of string elements suitable for return by
490      *  {@link #getOtherElements()}.  Override getOtherElements to return
491      *  the results of this method if your collection does not support
492      *  heterogenous elements or the null element.
493      */
494     public Object  [] getOtherNonNullStringElements() {
495         return new Object  [] {
496             "For","then","despite",/* of */"space","I","would","be","brought",
497             "From","limits","far","remote","where","thou","dost","stay"
498         };
499     }
500 
501     // Tests    
502     //-----------------------------------------------------------------------
503     /**
504      *  Tests {@link Collection#add(Object)}.
505      */
506     public void testCollectionAdd() {
507         if (!isAddSupported()) return;
508         
509         Object  [] elements = getFullElements();
510         for (int i = 0; i < elements.length; i++) {
511             resetEmpty();
512             boolean r = collection.add(elements[i]);
513             confirmed.add(elements[i]);
514             verify();
515             assertTrue("Empty collection changed after add", r);
516             assertEquals("Collection size is 1 after first add", 1, collection.size());
517         }
518         
519         resetEmpty();
520         int size = 0;
521         for (int i = 0; i < elements.length; i++) {
522             boolean r = collection.add(elements[i]);
523             confirmed.add(elements[i]);
524             verify();
525             if (r) size++;
526             assertEquals("Collection size should grow after add", 
527                          size, collection.size());
528             assertTrue("Collection should contain added element",
529                        collection.contains(elements[i]));
530         }
531     }
532     
533     
534     /**
535      *  Tests {@link Collection#addAll(Collection)}.
536      */
537     public void testCollectionAddAll() {
538         if (!isAddSupported()) return;
539 
540         resetEmpty();
541         Object  [] elements = getFullElements();
542         boolean r = collection.addAll(Arrays.asList(elements));
543         confirmed.addAll(Arrays.asList(elements));
544         verify();
545         assertTrue("Empty collection should change after addAll", r);
546         for (int i = 0; i < elements.length; i++) {
547             assertTrue("Collection should contain added element",
548                        collection.contains(elements[i]));
549         }
550 
551         resetFull();
552         int size = collection.size();
553         elements = getOtherElements();
554         r = collection.addAll(Arrays.asList(elements));
555         confirmed.addAll(Arrays.asList(elements));
556         verify();
557         assertTrue("Full collection should change after addAll", r);
558         for (int i = 0; i < elements.length; i++) {
559             assertTrue("Full collection should contain added element",
560                        collection.contains(elements[i]));
561         }
562         assertEquals("Size should increase after addAll", 
563                      size + elements.length, collection.size());
564         
565         resetFull();
566         size = collection.size();
567         r = collection.addAll(Arrays.asList(getFullElements()));
568         confirmed.addAll(Arrays.asList(getFullElements()));
569         verify();
570         if (r) {
571             assertTrue("Size should increase if addAll returns true", 
572                        size < collection.size());
573         } else {
574             assertEquals("Size should not change if addAll returns false",
575                          size, collection.size());
576         } 
577     }
578 
579 
580     /**
581      *  If {@link #isAddSupported()} returns false, tests that add operations
582      *  raise <code>UnsupportedOperationException.
583      */
584     public void testUnsupportedAdd() {
585         if (isAddSupported()) return;
586         
587         resetEmpty();
588         try {
589             collection.add(new Object  ());
590             fail("Emtpy collection should not support add.");
591         } catch (UnsupportedOperationException   e) {
592             // expected
593         }
594         // make sure things didn't change even if the expected exception was
595         // thrown.
596         verify();
597 
598         try {
599             collection.addAll(Arrays.asList(getFullElements()));
600             fail("Emtpy collection should not support addAll.");
601         } catch (UnsupportedOperationException   e) {
602             // expected
603         }
604         // make sure things didn't change even if the expected exception was
605         // thrown.
606         verify();
607 
608         resetFull();
609         try {
610             collection.add(new Object  ());
611             fail("Full collection should not support add.");
612         } catch (UnsupportedOperationException   e) {
613             // expected
614         }
615         // make sure things didn't change even if the expected exception was
616         // thrown.
617         verify();
618         
619         try {
620             collection.addAll(Arrays.asList(getOtherElements()));
621             fail("Full collection should not support addAll.");
622         } catch (UnsupportedOperationException   e) {
623             // expected
624         }
625         // make sure things didn't change even if the expected exception was
626         // thrown.
627         verify();
628     }
629 
630 
631     /**
632      *  Test {@link Collection#clear()}.
633      */
634     public void testCollectionClear() {
635         if (!isRemoveSupported()) return;
636 
637         resetEmpty();
638         collection.clear(); // just to make sure it doesn't raise anything
639         verify();
640 
641         resetFull();
642         collection.clear();
643         confirmed.clear();
644         verify();
645     }    
646 
647     
648     /**
649      *  Tests {@link Collection#contains(Object)}.
650      */
651     public void testCollectionContains() {
652         Object  [] elements;
653 
654         resetEmpty();
655         elements = getFullElements();
656         for(int i = 0; i < elements.length; i++) {
657             assertTrue("Empty collection shouldn't contain element[" + i + "]",
658                        !collection.contains(elements[i]));
659         }
660         // make sure calls to "contains" don't change anything
661         verify();
662 
663         elements = getOtherElements();
664         for(int i = 0; i < elements.length; i++) {
665             assertTrue("Empty collection shouldn't contain element[" + i + "]",
666                        !collection.contains(elements[i]));
667         }
668         // make sure calls to "contains" don't change anything
669         verify();
670 
671         resetFull();
672         elements = getFullElements();
673         for(int i = 0; i < elements.length; i++) {
674             assertTrue("Full collection should contain element[" + i + "]", 
675                        collection.contains(elements[i]));
676         }
677         // make sure calls to "contains" don't change anything
678         verify();
679 
680         resetFull();
681         elements = getOtherElements();
682         for(int i = 0; i < elements.length; i++) {
683             assertTrue("Full collection shouldn't contain element", 
684                        !collection.contains(elements[i]));
685         }
686     }
687 
688 
689     /**
690      *  Tests {@link Collection#containsAll(Collection)}.
691      */
692     public void testCollectionContainsAll() {
693         resetEmpty();
694         Collection   col = new HashSet  ();
695         assertTrue("Every Collection should contain all elements of an " +
696                    "empty Collection.", collection.containsAll(col));
697         col.addAll(Arrays.asList(getOtherElements()));
698         assertTrue("Empty Collection shouldn't contain all elements of " +
699                    "a non-empty Collection.", !collection.containsAll(col));
700         // make sure calls to "containsAll" don't change anything
701         verify();
702 
703         resetFull();
704         assertTrue("Full collection shouldn't contain other elements", 
705                    !collection.containsAll(col));
706         
707         col.clear();
708         col.addAll(Arrays.asList(getFullElements()));
709         assertTrue("Full collection should containAll full elements",
710                    collection.containsAll(col));
711         // make sure calls to "containsAll" don't change anything
712         verify();
713 
714         int min = (getFullElements().length < 2 ? 0 : 2);
715         int max = (getFullElements().length == 1 ? 1 : 
716                     (getFullElements().length <= 5 ? getFullElements().length - 1 : 5));
717         col = Arrays.asList(getFullElements()).subList(min, max);
718         assertTrue("Full collection should containAll partial full " +
719                    "elements", collection.containsAll(col));
720         assertTrue("Full collection should containAll itself", 
721                    collection.containsAll(collection));
722         // make sure calls to "containsAll" don't change anything
723         verify();
724         
725         col = new ArrayList  ();
726         col.addAll(Arrays.asList(getFullElements()));
727         col.addAll(Arrays.asList(getFullElements()));
728         assertTrue("Full collection should containAll duplicate full " +
729                    "elements", collection.containsAll(col));
730 
731         // make sure calls to "containsAll" don't change anything
732         verify();
733     }
734 
735     /**
736      *  Tests {@link Collection#isEmpty()}.
737      */
738     public void testCollectionIsEmpty() {
739         resetEmpty();
740         assertEquals("New Collection should be empty.", 
741                      true, collection.isEmpty());
742         // make sure calls to "isEmpty() don't change anything
743         verify();
744 
745         resetFull();
746         assertEquals("Full collection shouldn't be empty", 
747                      false, collection.isEmpty());
748         // make sure calls to "isEmpty() don't change anything
749         verify();
750     }
751 
752 
753     /**
754      *  Tests the read-only functionality of {@link Collection#iterator()}.
755      */
756     public void testCollectionIterator() {
757         resetEmpty();
758         Iterator   it1 = collection.iterator();
759         assertEquals("Iterator for empty Collection shouldn't have next.",
760                      false, it1.hasNext());
761         try {
762             it1.next();
763             fail("Iterator at end of Collection should throw " +
764                  "NoSuchElementException when next is called.");
765         } catch(NoSuchElementException   e) {
766             // expected
767         } 
768         // make sure nothing has changed after non-modification
769         verify();
770 
771         resetFull();
772         it1 = collection.iterator();
773         for (int i = 0; i < collection.size(); i++) {
774             assertTrue("Iterator for full collection should haveNext", 
775                        it1.hasNext());
776             it1.next();
777         }
778         assertTrue("Iterator should be finished", !it1.hasNext());
779         
780         ArrayList   list = new ArrayList  ();
781         it1 = collection.iterator();
782         for (int i = 0; i < collection.size(); i++) {
783             Object   next = it1.next();
784             assertTrue("Collection should contain element returned by " +
785                        "its iterator", collection.contains(next));
786             list.add(next);
787         }
788         try {
789             it1.next();
790             fail("iterator.next() should raise NoSuchElementException " +
791                  "after it finishes");
792         } catch (NoSuchElementException   e) {
793             // expected
794         }
795         // make sure nothing has changed after non-modification
796         verify();
797     }
798 
799 
800     /**
801      *  Tests removals from {@link Collection#iterator()}.
802      */
803     public void testCollectionIteratorRemove() {
804         if (!isRemoveSupported()) return;
805 
806         resetEmpty();
807         try {
808             collection.iterator().remove();
809             fail("New iterator.remove should raise IllegalState");
810         } catch (IllegalStateException   e) {
811             // expected
812         }
813         verify();
814 
815         try {
816             Iterator   iter = collection.iterator();
817             iter.hasNext();
818             iter.remove();
819             fail("New iterator.remove should raise IllegalState " +
820                  "even after hasNext");
821         } catch (IllegalStateException   e) {
822             // expected
823         }
824         verify();
825 
826         resetFull();
827         int size = collection.size();
828         Iterator   iter = collection.iterator();
829         while (iter.hasNext()) {
830             Object   o = iter.next();
831             // TreeMap reuses the Map Entry, so the verify below fails
832             // Clone it here if necessary
833             if (o instanceof Map.Entry  ) {
834                 o = cloneMapEntry((Map.Entry  ) o);
835             }
836             iter.remove();
837 
838             // if the elements aren't distinguishable, we can just remove a
839             // matching element from the confirmed collection and verify
840             // contents are still the same.  Otherwise, we don't have the
841             // ability to distinguish the elements and determine which to
842             // remove from the confirmed collection (in which case, we don't
843             // verify because we don't know how). 
844             //
845             // see areEqualElementsDistinguishable()
846             if(!areEqualElementsDistinguishable()) {
847                 confirmed.remove(o);
848                 verify();
849             }
850 
851             size--;
852             assertEquals("Collection should shrink by one after " +
853                          "iterator.remove", size, collection.size());
854         }
855         assertTrue("Collection should be empty after iterator purge",
856                    collection.isEmpty());
857         
858         resetFull();
859         iter = collection.iterator();
860         iter.next();
861         iter.remove();
862         try {
863             iter.remove();
864             fail("Second iter.remove should raise IllegalState");
865         } catch (IllegalStateException