Properly implement the remove() method in the MultiSetIterator class. The MutlsetIterator is provided below:

package 110; 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. * @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 // This is optional, since hasNext() will already return false! _modCount += 1; } /** * 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; // Invalidate any iterators since the contents are about to change. _modCount += 1; // 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. // Since we are changing the collection, we need to invalidate any iterators _modCount += 1; // 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. * */ 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; /** * Can only remove an element once, so we need remove() to fail if called multiple times between calls to next() */ private boolean _failRemove; /** * Create a new instance of this class that will go through the (valid) entries in the store. */ public MultiSetIterator() { _cursor = 0; _collectionVersion = _modCount; // Enforces that we must call next() before we can call remove() _failRemove = true; } public boolean hasNext() { // Check to see if cursor's location is valid return _cursor < size(); } public E next() { // hasNext() checks for any issues with us not having a next element if (hasNext()) { // Now we check if we need to fail fast if (_modCount != _collectionVersion) { throw new ConcurrentModificationException("There have been " + (_modCount - _collectionVersion) + " changes to the collection since the Iterator was created!"); } // Finally, we can return the value E retVal = _store[_cursor]; _cursor += 1; return retVal; } else { throw new NoSuchElementException("That's not my bag, baby!"); } } public void remove() { } } /* * 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() { // TODO Auto-generated method stub return null; } @Override public  T[] toArray(T[] a) { // TODO Auto-generated method stub return null; } @Override public boolean containsAll(Collection c) { // TODO Auto-generated method stub return false; } @Override public boolean addAll(Collection c) { // TODO Auto-generated method stub return false; } @Override public boolean removeAll(Collection c) { // TODO Auto-generated method stub return false; } @Override public boolean retainAll(Collection c) { // TODO Auto-generated method stub return false; } } 

Please also makesure that the code passes the tests given below:

package 110;

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 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); boolean failRemove = getFailRemove(testee); assertFalse("next() should allow remove() to succeed!", failRemove); }

@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); boolean failRemove = getFailRemove(testee); assertFalse("next() should allow remove() to succeed!", failRemove); 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); failRemove = getFailRemove(testee); assertFalse("next() should allow remove() to succeed!", failRemove); 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); failRemove = getFailRemove(testee); assertFalse("next() should allow remove() to succeed!", failRemove); }

@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); boolean failRemove = getFailRemove(testee); assertFalse("next() should allow remove() to succeed!", failRemove); }

@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. } catch (Exception e) { fail( "next() should throw a NoSuchElementException when called after the cursor has advanced past all the elements. You threw: " + e.toString()); } }

@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. } catch (Exception e) { fail( "next() should throw a ConcurrentModificationException when called and versioning does not match. You threw: " + e.toString()); } }

@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); }

@Test public void checkRemoveBeforeNextFails() throws IllegalAccessException { ArrayMultiSet msi = new ArrayMultiSet<>(); msi.add(0xDEADBEEF); msi.add(0xFEEDFACE); msi.add(0xBADACE); setModCount(msi, 17); Iterator testee = msi.iterator(); try { testee.remove(); fail("remove() should throw an IllegalStateException when called before next() has been called"); } catch (IllegalStateException ise) { // Nothing to do -- this is expected. } catch (Exception e) { fail("remove() should throw an IllegalStateException when called before next(). You called: " + e.toString()); }

testee.hasNext(); try { testee.remove(); fail("remove() should throw an IllegalStateException when called before next() has been called"); } catch (IllegalStateException ise) { // Nothing to do -- this is expected. } catch (Exception e) { fail("remove() should throw an IllegalStateException when called before next(). You called: " + e.toString()); } }

@Test public void checkRemoveAfterNext() throws IllegalAccessException { ArrayMultiSet msi = new ArrayMultiSet<>(); msi.add(0xDEADBEEF); msi.add(0xFEEDFACE); msi.add(0xBADACE); setModCount(msi, 17); Iterator testee = msi.iterator(); setCursor(testee, 1); setFailRemove(testee, false); testee.remove(); assertEquals("Calling remove() in Iterator (when legal) should call removeAtIndex() to remove the element", 2, msi.size()); long modCount = getModCount(msi); assertEquals("Calling remove() in Iterator (when legal) should call removeAtIndex() to remove the element", 18, modCount); boolean elemRemoved = msi.contains(0xDEADBEEF); assertFalse("Calling remove() in Iterator (when legal) should call removeAtIndex() to remove the element", elemRemoved); boolean failRemove = getFailRemove(testee); assertTrue("remove() in Iterator should not allow it to succeed until next() is called", failRemove); long collVersion = getCollectionVersion(testee); assertEquals("remove() in Iterator needs to update its expected version!", 18, collVersion); }

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

@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:", 4, 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\""); } try { failRemoveField = cIterator.getDeclaredField("_failRemove"); failRemoveField.setAccessible(true); } catch (Exception e) { fail("Your MultiSetIterator class should still define a field named \"failRemove\""); } }

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 boolean getFailRemove(Iterator testee) throws IllegalAccessException { return failRemoveField.getBoolean(testee); }

private void setFailRemove(Iterator testee, boolean shouldFail) throws IllegalAccessException { failRemoveField.setBoolean(testee, shouldFail); }

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

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