Problem #2 -- Finding and Removing Elements in an AMS Download this file that is
ID: 3755460 • Letter: P
Question
Problem #2 -- Finding and Removing Elements in an AMS
Download this file that is getting much closer to being a completely functional MultiSet. Since Monday's lecture discusses how to find and remove an element is in the ArrayMultiSet, this homework has you coding the methods which contains() and remove() use to do this.
The first method is findFirstIndex(). This method checks if the element is found in the multiset. If obj is an element in the multiset, findFirstIndex() returns the SMALLEST index in which it is an element. When objis NOT an element in the multiset, the method returns -1 .
You will also need to implement removeAtIndex(). removeAtIndex() updates the instance variables to remove the element at index removeIdx properly.
You can check your findFirstIndex() code using the ArrayMultiSetTest class in this JAR file. The test cases for removeAtIndex() are only on AutoLab, so you will want to test this code on your own.
ARRAYMULTISET CLASS
package edu.buffalo.cse116;
import java.util.AbstractCollection;
import java.util.Collection;
import java.util.Iterator;
/**
* Instances of this class are used to represent a multiset -- a searchable collection in which one can add multiple
* copies of an element.
*
* @author Carl Alphonce
* @author Matthew Hertz
* @param <E> Element type for this collection
*/
@SuppressWarnings({ "unused", "unchecked" })
public class ArrayMultiSet<E> extends AbstractCollection<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;
/** Constant value used as the initial length of the backing store. */
private static final int DEFAULT_BACKING_STORE_LENGTH = 12;
/**
* Creates a new empty multiset.
*/
public ArrayMultiSet() {
_store = (E[]) new Object[DEFAULT_BACKING_STORE_LENGTH];
}
/**
* 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.
*/
public boolean contains(Object obj) {
int indexFound = findFirstIndex(obj);
return indexFound != -1;
}
/**
* Removes a single instance of the given object, if one can be found in the ArrayMultiSet. The method returns
* {@code true} if a match was found (and removed) and {@code false} if no match was found. Since the order of
* elements in a MultiSet is not guaranteed, we use this to simplify how we remove an item.
*
* @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) {
int indexFound = findFirstIndex(obj);
if (indexFound != -1) {
removeAtIndex(indexFound);
return true;
}
return false;
}
/**
* Removes the element found at the given index. This is done while maintaining the class invariant, by first
* replacing the element being removed with the element at the largest index in the MultiSet. Once this is done, we
* assign null to the element that has been moved and then update any instance variables to insure class invariant
* remain true.<br />
* Precondition: {@code i} is a valid index within {@code _store} AND {@code _size} is not 0.
*
* @param removeIdx Index of the element to remove from the MultiSet.
*/
private void removeAtIndex(int removeIdx) {
}
/**
* Returns the first backing store index where {@code obj} is found in the ArrayMultiSet. If {@code obj} is not an
* element in the ArrayMultiSet, -1 is returned.
*
* @param obj Object (or null) for which we return the first index at which it is found in a valid location in _store
* @return Index in _store at which the item is found or -1 if it is not in the ArrayMultiSet.
*/
private int findFirstIndex(Object obj) {
}
@Override
public int size() {
return _size;
}
@Override
public boolean isEmpty() {
return _size == 0;
}
@Override
public Iterator<E> iterator() {
// To be discussed next week
throw new UnsupportedOperationException();
}
}
ARRAYMULTISET TEST CLASS
package edu.buffalo.cse116;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertNull;
import static org.junit.Assert.assertSame;
import static org.junit.Assert.assertTrue;
import static org.junit.Assert.fail;
import java.lang.reflect.Field;
import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;
import java.lang.reflect.Modifier;
import java.util.Random;
import org.junit.Before;
import org.junit.Rule;
import org.junit.Test;
import org.junit.rules.Timeout;
import edu.buffalo.correctness.Scorable;
/*
* Homework test cases<br/>
* (C) 2018 by Matthew Hertz<br/>
* Posting this file to a website without the explicit written permission of the author is a violation of their
* copyright.
*/
@Scorable(problem = "Homework05Problem2")
public class ArrayMultiSetTest {
@Test
public final void testFindFirstIndexNonNullFirst() throws Throwable {
Object[] storeArr = new Object[64];
Object[] refArr = new Object[storeArr.length];
Random rnd = new Random();
for (int i = 0; i < storeArr.length; i++) {
storeArr[i] = new IntWrapper(rnd.nextInt(8));
refArr[i] = storeArr[i];
}
setSize(testeeInt, 13);
setStore(testeeInt, storeArr);
int index = callFindFirstIndex(testeeInt, new IntWrapper(((IntWrapper) refArr[0]).wrapped));
Object[] newStore = getStore(testeeInt);
assertEquals("When element is stored in the first index in _store, findFirstIndex() should return 0", 0, index);
int _size = getSize(testeeInt);
assertEquals("_size should not change in findFirstIndex()", 13, _size);
assertSame("findFirstIndex() should not make any changes in _store", storeArr, newStore);
for (int i = 0; i < _size; i++) {
assertEquals("findFirstIndex() should not shift elements. At _store[" + i + "]", refArr[i], newStore[i]);
}
}
@Test
public final void testFindFirstIndexNonNullMiddle() throws Throwable {
Object[] storeArr = new Object[32];
Object[] refArr = new Object[storeArr.length];
for (int i = 0; i < storeArr.length; i++) {
storeArr[i] = new StringWrapper(Integer.toOctalString(i * 5));
refArr[i] = storeArr[i];
}
setSize(testeeString, 31);
setStore(testeeString, storeArr);
int index = callFindFirstIndex(testeeString, new StringWrapper(((StringWrapper) refArr[18]).wrapped));
Object[] newStore = getStore(testeeString);
assertEquals("When element is stored in _store, findFirstIndex() should return the index at which it is found", 18,
index);
int _size = getSize(testeeString);
assertEquals("_size should not change in findFirstIndex()", 31, _size);
assertSame("findFirstIndex() should not make any changes in _store", storeArr, newStore);
for (int i = 0; i < _size; i++) {
assertEquals("findFirstIndex() should not shift elements. At _store[" + i + "]", refArr[i], newStore[i]);
}
}
@Test
public final void testFindFirstIndexNonNullLast() throws Throwable {
Object[] storeArr = new Object[32];
Object[] refArr = new Object[storeArr.length];
for (int i = 0; i < storeArr.length; i++) {
storeArr[i] = new StringWrapper(Integer.toOctalString(i * 5));
refArr[i] = storeArr[i];
}
setSize(testeeString, 31);
setStore(testeeString, storeArr);
int index = callFindFirstIndex(testeeString, new StringWrapper(((StringWrapper) refArr[30]).wrapped));
Object[] newStore = getStore(testeeString);
assertEquals("When element is stored in _store, findFirstIndex() should return the index at which it is found", 30,
index);
int _size = getSize(testeeString);
assertEquals("_size should not change in findFirstIndex()", 31, _size);
assertSame("findFirstIndex() should not make any changes in _store", storeArr, newStore);
for (int i = 0; i < _size; i++) {
assertEquals("findFirstIndex() should not shift elements. At _store[" + i + "]", refArr[i], newStore[i]);
}
}
@Test
public final void testFindFirstIndexNonNullNotFound() throws Throwable {
Object[] storeArr = new Object[32];
Object[] refArr = new Object[storeArr.length];
for (int i = 0; i < 31; i++) {
storeArr[i] = new IntWrapper((i * 5) % 33);
refArr[i] = storeArr[i];
}
setSize(testeeInt, 31);
setStore(testeeInt, storeArr);
int index = callFindFirstIndex(testeeInt, new IntWrapper(((31 * 5) % 33)));
Object[] newStore = getStore(testeeInt);
assertEquals("When element is not in _store, findFirstIndex() should return -1", -1, index);
int _size = getSize(testeeInt);
assertEquals("_size should NOT be decremented by findFirstIndex()", 31, _size);
assertSame("contains() should never allocate a new array for _store", storeArr, newStore);
for (int i = 0; i < _size; i++) {
assertEquals("contains() should not shift elements. At _store[" + i + "]", refArr[i], newStore[i]);
}
}
@Test
public final void testFindFirstIndexNullNotFound() throws Throwable {
Object[] storeArr = new Object[32];
Object[] refArr = new Object[storeArr.length];
for (int i = 0; i < 30; i++) {
storeArr[i] = new IntWrapper((i * 5) % 33);
refArr[i] = storeArr[i];
}
setSize(testeeInt, 30);
setStore(testeeInt, storeArr);
Object[] args = new Object[1];
int index = callFindFirstIndex(testeeInt, args);
Object[] newStore = getStore(testeeInt);
assertEquals("When null has not been added to the MultiSet, findFirstIndex(null) should return -1", -1, index);
int _size = getSize(testeeInt);
assertEquals("_size should NOT be decremented by findFirstIndex()", 30, _size);
assertSame("findFirstIndex() should never allocate a new array for _store", storeArr, newStore);
for (int i = 0; i < _size; i++) {
assertEquals("findFirstIndex() should not shift elements. At _store[" + i + "]", refArr[i], newStore[i]);
}
}
@Test
public final void testFindFirstIndexNullFound() throws Throwable {
Object[] storeArr = new Object[32];
Object[] refArr = new Object[storeArr.length];
for (int i = 0; i < 30; i++) {
storeArr[i] = new IntWrapper((i * 5) % 33);
refArr[i] = storeArr[i];
}
storeArr[17] = null;
setSize(testeeInt, 30);
setStore(testeeInt, storeArr);
Object[] args = new Object[1];
int index = callFindFirstIndex(testeeInt, args);
Object[] newStore = getStore(testeeInt);
assertEquals(
"When null HAS been added to the MultiSet, findFirstIndex(null) should return the first index at which null is found",
17, index);
int _size = getSize(testeeInt);
assertEquals("_size should NOT be decremented by contains()", 30, _size);
assertSame("findFirstIndex() should never allocate a new array for _store", storeArr, newStore);
for (int i = 0; i < _size; i++) {
if (i != 17) {
assertEquals("findFirstIndex() should not shift elements. At _store[" + i + "]", refArr[i], newStore[i]);
} else {
assertNull("findFirstIndex() should not shift elements. At _store[" + i + "]", newStore[17]);
}
}
}
private class IntWrapper {
private Integer wrapped;
public IntWrapper(Integer wrap) {
wrapped = wrap;
}
@Override
public boolean equals(Object o) {
if (o instanceof IntWrapper) {
IntWrapper other = (IntWrapper) o;
return other.wrapped.equals(wrapped);
}
return false;
}
}
private class StringWrapper {
private String wrapped;
public StringWrapper(String wrap) {
wrapped = wrap;
}
@Override
public boolean equals(Object o) {
if (o instanceof StringWrapper) {
StringWrapper other = (StringWrapper) o;
return other.wrapped.equals(wrapped);
}
return false;
}
}
private Field storeField;
private Field sizeField;
private Method findFirstIndexMethod;
private Method removeAtIndexMethod;
private ArrayMultiSet<IntWrapper> testeeInt;
private ArrayMultiSet<StringWrapper> testeeString;
@Before
public final void checkFieldsUnchanged() {
Class<?> mSet = ArrayMultiSet.class;
Field[] fields = mSet.getDeclaredFields();
assertEquals("You should not add any fields to the MostArrayMultiSet class. This class's field count:", 4,
fields.length);
try {
Field initialSizeField = mSet.getDeclaredField("DEFAULT_BACKING_STORE_LENGTH");
int mods = initialSizeField.getModifiers();
assertTrue("The DEFAULT_BACKING_STORE_LENGTH field should still be static", Modifier.isStatic(mods));
assertTrue("The DEFAULT_BACKING_STORE_LENGTH field should still be final", Modifier.isFinal(mods));
} catch (Exception e) {
fail("Your ArrayMultiSet class should still define a field named "DEFAULT_BACKING_STORE_LENGTH"");
}
try {
Field modCountField = mSet.getDeclaredField("_modCount");
assertEquals("The _store field should be an 1-d array of the generic type", Long.TYPE, modCountField.getType());
} catch (Exception e) {
fail("Your ArrayMultiSet class should still define a field named "_modCount"");
}
try {
storeField = mSet.getDeclaredField("_store");
storeField.setAccessible(true);
assertTrue("The _store field should be an 1-d array", storeField.getType().isArray());
assertEquals("The _store field should be an 1-d array of the generic type", Object.class,
storeField.getType().getComponentType());
} catch (Exception e) {
fail("Your ArrayMultiSet class should still define a field named "_store"");
}
try {
sizeField = mSet.getDeclaredField("_size");
sizeField.setAccessible(true);
assertEquals("The _size field should be of type int", Integer.TYPE, sizeField.getType());
} catch (Exception e) {
fail("Your ArrayMultiSet class should still define a field named "_size"");
}
try {
findFirstIndexMethod = mSet.getDeclaredMethod("findFirstIndex", Object.class);
findFirstIndexMethod.setAccessible(true);
} catch (Exception e) {
fail("Your ArrayMultiSet class should still define a method named "findFirstIndex"");
}
try {
removeAtIndexMethod = mSet.getDeclaredMethod("removeAtIndex", Integer.TYPE);
removeAtIndexMethod.setAccessible(true);
} catch (Exception e) {
fail("Your ArrayMultiSet class should still define a method named "removeAtIndex"");
}
testeeInt = new ArrayMultiSet<IntWrapper>();
testeeString = new ArrayMultiSet<StringWrapper>();
}
private void setSize(ArrayMultiSet<?> testee, int newSize) throws IllegalAccessException {
sizeField.setInt(testee, newSize);
}
private void setStore(ArrayMultiSet<?> testee, Object[] newStore) throws IllegalAccessException {
storeField.set(testee, newStore);
}
private Object[] getStore(ArrayMultiSet<?> testee) throws IllegalAccessException {
return (Object[]) storeField.get(testee);
}
private int getSize(ArrayMultiSet<?> testee) throws IllegalAccessException {
return sizeField.getInt(testee);
}
private int callFindFirstIndex(ArrayMultiSet<?> testee, Object arg)
throws IllegalAccessException, InvocationTargetException {
return (Integer) findFirstIndexMethod.invoke(testee, arg);
}
private int callFindFirstIndex(ArrayMultiSet<?> testee, Object[] args)
throws IllegalAccessException, InvocationTargetException {
return (Integer) findFirstIndexMethod.invoke(testee, args);
}
private void callRemoveAtIndex(ArrayMultiSet<?> testee, int idx)
throws IllegalAccessException, InvocationTargetException {
removeAtIndexMethod.invoke(testee, idx);
}
}
Explanation / Answer
That being said, you can use the remove(int index) or remove(Object obj) which are provided by the ArrayList class. Note, however, that calling these methods while you are iterating over the loop, will cause a ConcurrentModificationException, so this will not work:
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.