This file is complete, however, it\'s an \"able-to-be-improved\" ArrayMultiSet.

Question

This file is complete, however, it's an "able-to-be-improved" ArrayMultiSet.

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.

This is the file to be worked on:

VERIFY YOUR ANSWER BY USING THE TEST CASE PROVIDED BELOW:

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<Double> msd = new ArrayMultiSet<>();
setModCount(msd, 15);
Iterator<Double> testee = msd.iterator();
long collectionVersion = getCollectionVersion(testee);
assertEquals("Iterator constructor should assign _collectionVersion the correct value.", 15, collectionVersion);
setModCount(msd, 72);
Iterator<Double> 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<Double> msd = new ArrayMultiSet<>();
msd.add(null);
setModCount(msd, 1);
Iterator<Double> 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<Integer> msi = new ArrayMultiSet<>();
msi.add(0xDEADBEEF);
msi.add(0xFEEDFACE);
msi.add(0xBADACE);
setModCount(msi, 1);
Iterator<Integer> 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<Integer> msi = new ArrayMultiSet<>();
msi.add(0xDEADBEEF);
msi.add(null);
msi.add(0xBADACE);
msi.add(8192);
setModCount(msi, 0);
Iterator<Integer> 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<Character> msc = new ArrayMultiSet<>();
msc.add('-');
msc.add('^');
msc.add('v');
msc.add('@');
msc.add('');
Iterator<Character> 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<Double> msd = new ArrayMultiSet<>();
setModCount(msd, 2);
Iterator<Double> 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<String> mss = new ArrayMultiSet<>();
mss.add("Hello world!");
Iterator<String> 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<String> mss = new ArrayMultiSet<>();
mss.add("-");
mss.add("^");
mss.add("v");
mss.add("@");
mss.add("");
setModCount(mss, 5);
Iterator<String> 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<Number> msn = new ArrayMultiSet<>();
msn.add(0.1);
msn.add(23);
msn.add(-99);
Iterator<Number> 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<Number> msn = new ArrayMultiSet<>();
msn.add(0.1);
msn.add(23);
msn.add(-99);
setModCount(msn, 9);
Iterator<Number> 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<Integer> msi = new ArrayMultiSet<>();
msi.add(0xDEADBEEF);
msi.add(0xFEEDFACE);
msi.add(0xBADACE);
setModCount(msi, 3);
Iterator<Integer> 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<Integer> msi = new ArrayMultiSet<>();
msi.add(0xDEADBEEF);
msi.add(0xFEEDFACE);
msi.add(0xBADACE);
setModCount(msi, 2);
Iterator<Integer> 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<Integer> 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<Integer> 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<Integer> 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);
}
}

Explanation / Answer

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 <E> Type of data contained with the instance.
*/
public class ArrayMultiSet<E> implements Collection<E> {

/**
* 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;
Iterator<E> itr = iterator();
/**
* 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.
while(itr.hasNext()){
Object currObj = itr.next();
if ((obj == null) && (currObj == null)) {
return true;
} // Otherwise, we use .equals() to find a match
else if ((obj != null) && obj.equals(currObj)) {
return true;
}
}
// 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.<br />
* <b>Precondition</b>: {@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) {
while(itr.hasNext()){
Object currObj = itr.next();
if ((obj == null) && (currObj == null)) {
return true;
} // Otherwise, we use .equals() to find a match
else if ((obj != null) && obj.equals(currObj)) {
return true;
}
}
// Checked all VALID indices, so the result must be:
return false;
}

@Override
public boolean isEmpty() {
return _size == 0;
}
  
public Iterator<E> iterator() {
return new MultiSetIterator();
}

private class MultiSetIterator implements Iterator<E> {

/**
* 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() {
return _cursor < _size;
}

public E next() {
return _store[_cursor++];
}

public void remove(int i) {
if(i< 0 || i > _size) {
throw new UnsupportedOperationException();
}
// 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;
}
}

/*
* The remaining methods are part of the Collection<E> 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> T[] toArray(T[] a) {
throw new UnsupportedOperationException();
}

@Override
public boolean containsAll(Collection<?> c) {
throw new UnsupportedOperationException();
}

@Override
public boolean addAll(Collection<? extends E> c) {
throw new UnsupportedOperationException();
}

@Override
public boolean removeAll(Collection<?> c) {
throw new UnsupportedOperationException();
}

@Override
public boolean retainAll(Collection<?> c) {
throw new UnsupportedOperationException();
}
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.