Be sure you pass the test first. It wont take you more than 15 mins.

The class currently uses an Iterator, but one that is prone to errors. Update the ArrayMultiSet class AND/OR its inner-class Iterator so that it has a working fail-fast Iterator.

package edu.buffalo.cse116; import java.util.Arrays; import java.util.Collection; import java.util.ConcurrentModificationException; import java.util.Iterator; import java.util.NoSuchElementException; /** * Class which implements the concept of a multiset -- an unorganized collection which does not limited the number of * times an instance can be added. * * @author Carl Alphonce * @author Matthew Hertz * @param  Type of data contained with the instance. */ public class ArrayMultiSet implements Collection { /** Array in which the elements in this multiset are stored. */ private E[] _store; /** * Array indices below this amount contain the active elements in this collection. */ private int _size; /** * Modification counter used to preserve the fail-fast nature of its iterators. */ private long _modCount; /** * Create a new empty multiset. */ public ArrayMultiSet() { _modCount = 0; clear(); } /** * Remove all of the elements within the instance and invalidate any current iterators. */ @SuppressWarnings("unchecked") @Override public void clear() { _store = (E[]) (new Object[16]); _size = 0; // maintains the class invariant } /** * Update the multiset so that it includes all of the elements from before the call AND the given element. * * @param e Item to be added to this collection. */ @Override public boolean add(E e) { // Check if we do not have enough space in the underlying array to store the // new element if (_size == _store.length) { // We do not have space, so create a new larger space (doubling the size // is the most time efficient) _store = Arrays.copyOf(_store, _store.length * 2); } // Add the element to the store _store[_size] = e; // Finally, we can increase _size, since this change will no longer violate // any class invariants. _size += 1; return true; } /** * Return true if at least one element in the multiset is equal to the given object. When {@code obj} is null, it must * use the {@code ==} operator to perform these checks, but when {@code obj} is not null, the {@link Object#equals} * method is used. * * @param obj Object (or null) for which we will search * @return {@code true} if {@code obj} was found; {@code false} if a match could not be found. */ @Override public boolean contains(Object obj) { // Only scan through _size, since those are the only "real" entries for the // multiset. for (int i = 0; i < _size; i++ ) { // When obj is null, we need to use == if ((obj == null) && (_store[i] == null)) { return true; } // Otherwise, we use .equals() to find a match else if ((obj != null) && obj.equals(_store[i])) { return true; } // No else clause, since the match could be at a higher index! } // Checked all VALID indices, so the result must be: return false; } @Override public int size() { return _size; } /** * Remove the element found at the given index. This method also acts to maintain the class invariants.
 * Precondition: {@code i} is a valid index within {@code _store}. * * @param i Index of the element to remove from the multiset. */ private void removeAtIndex(int i) { // We do not need to check i, since we made that a precondition (assumption) // for this method. // Slide elements at highest index down to fill in "hole" we are creating _store[i] = _store[_size - 1]; // Update which is the first unused index in the array _size -= 1; // Finally set the newly unused index to null thus avoiding a space leak _store[_size] = null; } /** * Removes a single instance of the given object, if one can be found in the multiset. The method returns {@code true} * if a match was found (and removed) and {@code false} if no match was found. Normally, this uses * {@link Object#equals} to check if there is a match, but uses {@code ==} when {@code obj} is {@code null}. * * @param obj Object (or null) which we want to remove * @return {@code true} if {@code obj} was found and an instance removed; {@code false} if a match could not be found. */ @Override public boolean remove(Object obj) { for (int i = 0; i < _size; i++ ) { if ((obj == null) && (_store[i] == null)) { removeAtIndex(i); return true; } else if ((obj != null) && obj.equals(_store[i])) { removeAtIndex(i); return true; } // No else clause, since a match may still exist at a higher index! } // Checked all VALID indices, so the result must be: return false; } @Override public boolean isEmpty() { return _size == 0; } @Override public Iterator iterator() { return new MultiSetIterator(); } /** * Instances of this class are used as the iterators for a multiset. We must keep this as an inner-class, because the * multiset definition does not include any methods to access its elements. * * @author Carl Alphonse * @author Matthew Hertz */ private class MultiSetIterator implements Iterator { /** * The index of the _store entry which will be returned by the next call to next() */ private int _cursor; /** * In keeping with the fail-fast convention, the iterator is only valid while _modCount remains on this version. */ private long _collectionVersion; /** * Create a new instance of this class that will go through the (valid) entries in the store. */ public MultiSetIterator() { _cursor = 0; } public boolean hasNext() { } public E next() { } public void remove() { throw new UnsupportedOperationException(); } } /* * The remaining methods are part of the Collection interface, but are beyond what is necessary for CSE 116. * Students who want a complete Multiset implementation should investigate Google's "Guava" library. */ @Override public Object[] toArray() { throw new UnsupportedOperationException(); } @Override public  T[] toArray(T[] a) { throw new UnsupportedOperationException(); } @Override public boolean containsAll(Collection c) { throw new UnsupportedOperationException(); } @Override public boolean addAll(Collection c) { throw new UnsupportedOperationException(); } @Override public boolean removeAll(Collection c) { throw new UnsupportedOperationException(); } @Override public boolean retainAll(Collection c) { throw new UnsupportedOperationException(); } } 

----------------------------

test

package edu.buffalo.cse116;

import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertFalse; import static org.junit.Assert.*;

import java.lang.reflect.Field; import java.util.ConcurrentModificationException; import java.util.Iterator; import java.util.NoSuchElementException;

import org.junit.Before; import org.junit.Test;

public class ArrayMultiSetIteratorTest {

@Test public void checkIteratorVersioning() throws IllegalAccessException { ArrayMultiSet msd = new ArrayMultiSet<>(); setModCount(msd, 15); Iterator testee = msd.iterator(); long collectionVersion = getCollectionVersion(testee); assertEquals("Iterator constructor should assign _collectionVersion the correct value.", 15, collectionVersion); setModCount(msd, 72); Iterator testeeTwo = msd.iterator(); collectionVersion = getCollectionVersion(testee); assertEquals("_collectionVersion should be defined (and assigned) per instance.", 15, collectionVersion);

collectionVersion = getCollectionVersion(testeeTwo); assertEquals("Iterator constructor should assign _collectionVersion the correct value.", 72, collectionVersion);

}

@Test public void checkHasNextStart() throws IllegalAccessException { ArrayMultiSet msd = new ArrayMultiSet<>(); msd.add(null); setModCount(msd, 1); Iterator testee = msd.iterator(); assertTrue("hasNext() should return true before calling next() when the MultiSet has a length of 1", testee.hasNext()); }

@Test public void checkHasNextMiddle() throws IllegalAccessException { ArrayMultiSet msi = new ArrayMultiSet<>(); msi.add(0xDEADBEEF); msi.add(0xFEEDFACE); msi.add(0xBADACE); setModCount(msi, 1); Iterator testee = msi.iterator(); setCursor(testee, 1); assertTrue("hasNext() should return true while in the middle of the MultiSet", testee.hasNext()); }

@Test public void checkHasNextLast() throws IllegalAccessException { ArrayMultiSet msi = new ArrayMultiSet<>(); msi.add(0xDEADBEEF); msi.add(null); msi.add(0xBADACE); msi.add(8192); setModCount(msi, 0); Iterator testee = msi.iterator(); setCursor(testee, 3); assertTrue("hasNext() should return true when it has one more entry to go through in the MultiSet", testee.hasNext()); }

@Test public void checkHasNextAfterLast() throws IllegalAccessException { ArrayMultiSet msc = new ArrayMultiSet<>(); msc.add('-'); msc.add('^'); msc.add('v'); msc.add('@'); msc.add('\b'); Iterator testee = msc.iterator(); setCollectionVersion(testee, 4); setCursor(testee, 5); assertFalse("hasNext() should return false once next() has iterated over all of the elements in the MultiSet", testee.hasNext()); ArrayMultiSet msd = new ArrayMultiSet<>(); setModCount(msd, 2); Iterator testeeTwo = msd.iterator(); assertFalse("hasNext() should return false once next() has iterated over all of the elements in the MultiSet", testeeTwo.hasNext()); }

@Test public void checkNextStartNotEmpty() throws IllegalAccessException { ArrayMultiSet mss = new ArrayMultiSet<>(); mss.add("Hello world!"); Iterator testee = mss.iterator(); long collVersion = getCollectionVersion(testee); assertEquals("First call to next() should return the entry at index 0 in _store", "Hello world!", testee.next()); int cursor = getCursor(testee); assertEquals("next() should advance the Iterator's cursor", 1, cursor); long sameVersion = getCollectionVersion(testee); assertEquals("next() should not change the Iterator's collectionVersion", collVersion, sameVersion); }

@Test public void checkNextMiddle() throws IllegalAccessException { ArrayMultiSet mss = new ArrayMultiSet<>(); mss.add("-"); mss.add("^"); mss.add("v"); mss.add("@"); mss.add("\b"); setModCount(mss, 5); Iterator testee = mss.iterator(); long collVersion = getCollectionVersion(testee); setCursor(testee, 1); assertEquals("Second call to next() should entry at _store[1]", "^", testee.next()); int cursor = getCursor(testee); assertEquals("next() should advance the Iterator's cursor", 2, cursor); long sameVersion = getCollectionVersion(testee); assertEquals("next() should not change the Iterator's collectionVersion", collVersion, sameVersion); assertEquals("Third call to next() should entry at _store[2]", "v", testee.next()); cursor = getCursor(testee); assertEquals("next() should advance the Iterator's cursor", 3, cursor); sameVersion = getCollectionVersion(testee); assertEquals("next() should not change the Iterator's collectionVersion", collVersion, sameVersion); assertEquals("Fourth call to next() should entry at _store[3]", "@", testee.next()); cursor = getCursor(testee); assertEquals("next() should advance the Iterator's cursor", 4, cursor); }

@Test public void checkNextLast() throws IllegalAccessException { ArrayMultiSet msn = new ArrayMultiSet<>(); msn.add(0.1); msn.add(23); msn.add(-99); Iterator testee = msn.iterator(); setCursor(testee, 2); assertEquals("Should be able to return the last entry in _store from the iterator", -99, testee.next()); int cursor = getCursor(testee); assertEquals("next() should ALWAYS advance the Iterator's cursor", 3, cursor); }

@Test public void checkNextAfterLast() throws IllegalAccessException { ArrayMultiSet msn = new ArrayMultiSet<>(); msn.add(0.1); msn.add(23); msn.add(-99); setModCount(msn, 9); Iterator testee = msn.iterator(); setCursor(testee, 3); setCollectionVersion(testee, 9); try { testee.next(); fail( "next() should throw a NoSuchElementException when called after the cursor has advanced past all the elements."); } catch (NoSuchElementException e) { // This is the correct behavior; nothing should be done. } }

@Test public void checkNextModWhileInCollectionMiddle() throws IllegalAccessException { ArrayMultiSet msi = new ArrayMultiSet<>(); msi.add(0xDEADBEEF); msi.add(0xFEEDFACE); msi.add(0xBADACE); setModCount(msi, 3); Iterator testee = msi.iterator(); setCursor(testee, 1); setCollectionVersion(testee, 9); try { testee.next(); fail( "next() should throw a ConcurrentModificationException when called and _collectionVersion shows the MultiSet has changed."); } catch (ConcurrentModificationException e) { // This is the correct behavior; nothing should be done. } }

@Test public void checkNextModAfterCollectionEnd() throws IllegalAccessException { ArrayMultiSet msi = new ArrayMultiSet<>(); msi.add(0xDEADBEEF); msi.add(0xFEEDFACE); msi.add(0xBADACE); setModCount(msi, 2); Iterator testee = msi.iterator(); setCursor(testee, 3); setCollectionVersion(testee, 3); try { testee.next(); fail( "next() should throw a ConcurrentModificationException when called and an element was removed during the iteration."); } catch (ConcurrentModificationException e) { // This is the correct behavior; nothing should be done. } catch (NoSuchElementException e) { // This is also acceptable behavior; nothing should be done. } }

@Test public void checkAddUpdatesModCount() throws IllegalAccessException { ArrayMultiSet msi = new ArrayMultiSet<>(); setModCount(msi, 17); msi.add(0xDEADBEEF); long modCount = getModCount(msi); assertEquals("add() should increase the value of _modCount", 18, modCount); msi.add(null); modCount = getModCount(msi); assertEquals("add() should ALWAYS increase the value of _modCount", 19, modCount); }

@Test public void checkRemoveSuccessUpdatesModCount() throws IllegalAccessException { ArrayMultiSet msi = new ArrayMultiSet<>(); msi.add(0xDEADBEEF); msi.add(0xFEEDFACE); msi.add(0xBADACE); msi.add(null); setModCount(msi, 17); msi.remove(0xDEADBEEF); long modCount = getModCount(msi); assertEquals("remove() should increase the value of _modCount when it is successful", 18, modCount); msi.remove(0xBADACE); modCount = getModCount(msi); assertEquals("remove() should increase the value of _modCount when it is successful", 19, modCount); msi.remove(null); modCount = getModCount(msi); assertEquals("remove() should increase the value of _modCount when it is successful", 20, modCount); }

@Test public void checkRemoveFailsModCountUnchanged() throws IllegalAccessException { ArrayMultiSet msi = new ArrayMultiSet<>(); msi.add(0xDEADBEEF); msi.add(0xFEEDFACE); msi.add(0xBADACE); setModCount(msi, 17); msi.remove(0xDEADBEED); long modCount = getModCount(msi); assertEquals("remove() should NOT change the value of _modCount when it could not find the element", 17, modCount); msi.remove(null); modCount = getModCount(msi); assertEquals("remove() should NOT change the value of _modCount when it could not find the element", 17, modCount); }

private Field cursorField; private Field collectionVersionField; private Field modCountField;

@Before public final void checkFieldsUnchanged() { ArrayMultiSet ams = new ArrayMultiSet<>(); Class amsClass = ams.getClass(); try { modCountField = amsClass.getDeclaredField("_modCount"); modCountField.setAccessible(true); } catch (Exception e) { fail("Your ArrayMultiSet class should still define a field named \"_modCount\""); } Class cIterator = ams.iterator().getClass(); Field[] fields = cIterator.getDeclaredFields(); assertEquals("You should not add any fields to the MultiSetIterator class. This class's field count:", 3, fields.length); try { collectionVersionField = cIterator.getDeclaredField("_collectionVersion"); collectionVersionField.setAccessible(true); } catch (Exception e) { fail("Your MultiSetIterator class should still define a field named \"_collectionVersion\""); } try { cursorField = cIterator.getDeclaredField("_cursor"); cursorField.setAccessible(true); } catch (Exception e) { fail("Your MultiSetIterator class should still define a field named \"_cursor\""); } }

private long getModCount(ArrayMultiSet testee) throws IllegalAccessException { return modCountField.getLong(testee); }

private void setModCount(ArrayMultiSet testee, long newVersion) throws IllegalAccessException { modCountField.setLong(testee, newVersion); }

private long getCollectionVersion(Iterator testee) throws IllegalAccessException { return collectionVersionField.getLong(testee); }

private void setCollectionVersion(Iterator testee, long newVersion) throws IllegalAccessException { collectionVersionField.setLong(testee, newVersion); }

private int getCursor(Iterator testee) throws IllegalAccessException { return cursorField.getInt(testee); }

private void setCursor(Iterator testee, int newSize) throws IllegalAccessException { cursorField.setInt(testee, newSize); } }