The following Java files are provided in package

cs.lab3

.

BagInterface.java

is a Java interface representing the ADT Bag.

ArrayBag.java

is a dynamic capacity array-based implementation of ADT Bag. It has a non-

functional stub for the

equals

method that you must write in this lab.

LinkedBag.java

is a linked implementation of ADT Bag. It also has a non-functional stub for the

equals

method.

EqualsTest.java

is an example test client of the Bag

equals

method.

2.

Devise an algorithm for comparing two bags to determine if they contain the same contents. Here are

some steps you may want to follow:

Consider two "equal" bags. What items and frequencies need to be compared to determine that they

are equal? What existing bag methods can you reuse to accomplish this?

CS 445 Lab 3: Array vs. linked implementations

Introduction

Exercise

Determine an example of two bags that cannot be equal, yet no item comparisons are needed to

make that determination.

Write an algorithm for each of

ArrayBag

and

LinkedBag

that returns true if two bags contain

the same entries. Remember to consider the example from the previous step.

3.

Implement your algorithm(s) as method

boolean equals(Object other)

in each class. Since this

is overriding a method from the generic

Object

class, you cannot change the method signature, which

means you cannot accept a parameter of type

ArrayBag

. This means you must first check if

other instanceof ArrayBag

. If not, return

false

. If so, cast the reference to type

ArrayBag

to complete the rest of the algorithm.

4.

Test your

equals

method by running

EqualsTest

. To change which class is tested, change the

object type of the instances created for testing (i.e., from

ArrayBag

to

LinkedBag

)

package cs.lab3; import java.util.Random; public class EqualsTest { public static void main(String[] args) { BagInterface bag1 = new ArrayBag<>(); BagInterface bag2 = new ArrayBag<>(); BagInterface bag3 = new ArrayBag<>(); System.out.println("Testing ArrayBag.equals():"); testEquals(bag1, bag2, bag3); bag1 = new LinkedBag<>(); bag2 = new LinkedBag<>(); bag3 = new LinkedBag<>(); System.out.println("Testing LinkedBag.equals():"); testEquals(bag1, bag2, bag3); } private static void testEquals(BagInterface bag1, BagInterface bag2, BagInterface bag3) { System.out.println("empty, empty:\t" + bag1.equals(bag2)); System.out.println("empty, null:\t" + bag1.equals(null)); System.out.println("empty, String:\t" + bag1.equals("A string")); bag1.add("a"); bag3.add(1); System.out.println("String Bag, Int Bag:\t" + bag1.equals(bag3)); bag1.clear(); // Test strings, including different numbers of duplicates String[] testStrings = new String[] { "abc", "def", "ghi", "jkl", "mnop", "qrs", "tuv", "wxyz", "abc", "abc", "abc", "mnop", ".", ".", "." }; for (String s : testStrings) { bag1.add(s); } // Shuffle the test strings so they are added to bag2 in a different // order shuffle(testStrings); for (String s : testStrings) { bag2.add(s); } System.out.println("diff. order:\t" + bag1.equals(bag2)); // Remove 1 instance of "." from bag1 bag1.remove("."); System.out.println("after remove:\t" + bag1.equals(bag2)); } /** * Implements the Fisher-Yates shuffle on generic array * @param array The array to shuffle */ private static  void shuffle(T[] array) { int index; T temp; Random random = new Random(); for (int i = array.length - 1; i > 0; i--) { index = random.nextInt(i + 1); temp = array[index]; array[index] = array[i]; array[i] = temp; } } } 

package cs.lab3; /** * An interface that describes the operations of a bag of objects. * @author Frank M. Carrano * @author William C. Garrison III * @version 4.1 */ public interface BagInterface<E> { /** * Gets the current number of entries in this bag. * @return The integer number of entries currently in this bag. */ public int getCurrentSize(); /** * Sees whether this bag is empty. * @return True if this bag is empty, or false if not. */ public boolean isEmpty(); /** * Adds a new entry to this bag. * @param newEntry The object to be added as a new entry. * @return True if the addition is successful, false if not. */ public boolean add(E newEntry); /** * Removes one unspecified entry from this bag, if possible. * @return Either the removed entry, if the removal was successful, or * null. */ public E remove(); /** * Removes one occurrence of a given entry from this bag, if possible. * @param anEntry The entry to be removed. * @return True if the removal was successful, or false if not. */ public boolean remove(E anEntry); /** * Removes all entries from this bag. */ public void clear(); /** * Counts the number of times a given entry appears in this bag. * @param anEntry The entry to be counted. * @return The number of times anEntry appears in this bag. */ public int getFrequencyOf(E anEntry); /** * Tests whether this bag contains a given entry. * @param anEntry The entry to locate. * @return True if this bag contains anEntry, or false otherwise. */ public boolean contains(E anEntry); /** * Retrieves all entries that are in this bag. * @return A newly allocated array of all the entries in this bag. */ public E[] toArray(); } 

package cs.lab3; /** * A class that implements the ADT bag using a chain of linked nodes. * @author Frank M. Carrano * @author Timothy M. Henry * @author William C. Garrison III * @version 4.1 */ public final class LinkedBag<E> implements BagInterface<E> { private Node head; private int size; public LinkedBag() { head = null; size = 0; } /** * Sees whether this bag is empty. * @return True if this bag is empty, or false if not. */ @Override public boolean isEmpty() { return size == 0; } /** * Gets the current number of entries in this bag. * @return The integer number of entries currently in this bag. */ @Override public int getCurrentSize() { return size; } /** * Adds a new entry to this bag. * @param newEntry The object to be added as a new entry. * @return True. */ @Override public boolean add(E newEntry) { Node newNode = new Node(newEntry, head); head = newNode; size++; return true; } /** * Retrieves all entries that are in this bag. * @return A newly allocated array of all the entries in this bag. */ @Override public E[] toArray() { // the cast is safe because the new array contains null entries @SuppressWarnings("unchecked") E[] result = (E[]) new Object[size]; // Unchecked cast int index = 0; Node currentNode = head; while ((index < size) && (currentNode != null)) { result[index] = currentNode.data; index++; currentNode = currentNode.next; } return result; } /** * Counts the number of times a given entry appears in this bag. * @param anEntry The entry to be counted. * @return The number of times anEntry appears in this bag. */ @Override public int getFrequencyOf(E anEntry) { int frequency = 0; int loopCounter = 0; Node currentNode = head; while ((loopCounter < size) && (currentNode != null)) { if (anEntry != null && anEntry.equals(currentNode.data)) { frequency++; } loopCounter++; currentNode = currentNode.next; } return frequency; } /** * Tests whether this bag contains a given entry. * @param anEntry The entry to locate. * @return True if this bag contains anEntry, or false otherwise. */ @Override public boolean contains(E anEntry) { boolean found = false; Node currentNode = head; while (!found && (currentNode != null)) { if (anEntry != null && anEntry.equals(currentNode.data)) { found = true; } else { currentNode = currentNode.next; } } return found; } /** * Removes one occurrence of a given entry from this bag, if possible. * @param anEntry The entry to be removed. * @return True if the removal was successful, or false if not. */ @Override public boolean remove(E anEntry) { boolean result = false; Node nodeN = getReferenceTo(anEntry); if (nodeN != null) { nodeN.data = head.data; // Teplace located entry with entry // in first node head = head.next; // Remove first node size--; result = true; } return result; } // Locates a given entry within this bag. // Returns a reference to the node containing the entry, if located, // or null otherwise. private Node getReferenceTo(E anEntry) { boolean found = false; Node currentNode = head; while (!found && (currentNode != null)) { if (anEntry != null && anEntry.equals(currentNode.data)) { found = true; } else { currentNode = currentNode.next; } } return currentNode; } /** * Removes all entries from this bag. */ @Override public void clear() { while (!isEmpty()) { remove(); } } private class Node { private E data; // Entry in bag private Node next; // link to next node private Node(E dataPortion, Node nextNode) { data = dataPortion; next = nextNode; } } /** * Removes one unspecified entry from this bag, if possible. * @return Either the removed entry, if the removal was successful, or * null. */ @Override public E remove() { E result = null; if (head != null) { result = head.data; head = head.next; size--; } return result; } /** * Override the toString() method so that we get a more useful display of * the contents in the bag. * @return a string representation of the contents of the bag */ @Override public String toString() { StringBuilder result = new StringBuilder("Bag[ "); Node scout = head; for (int index = 0; index < size; index++) { result.append(scout.data.toString()); result.append(' '); scout = scout.next; } result.append(']'); return result.toString(); } /** * Determines if two bags are equal. * @param other Another object to check this bag against. * @return True if other is an ArrayBag containing the same objects, with * the same frequencies, as this bag. */ @Override public boolean equals(Object other) { // TODO: Rewrite this method so that it works according to the contents // of the bags (this and other). Be sure to consider if other is null, // or a type other than LinkedBag. return this == other; } } 

package cs.lab3; import java.util.Arrays; /** * A class that implements the ADT bag using a resizable array. * @author Frank M. Carrano * @author Timothy M. Henry * @author William C. Garrison III * @version 4.1 */ public class ArrayBag<E> implements BagInterface<E> { private E[] bag; private int size; // Initial capacity of bag private static final int DEFAULT_CAPACITY = 25; /** * Creates an empty bag whose initial capacity is 25. */ public ArrayBag() { this(DEFAULT_CAPACITY); } /** * Creates an empty bag having a given initial capacity. * @param initialCapacity The integer capacity desired. */ public ArrayBag(int initialCapacity) { @SuppressWarnings("unchecked") E[] tempBag = (E[])new Object[initialCapacity]; bag = tempBag; size = 0; } /** * Creates this bag containing given entries. * @param contents An array of objects. */ public ArrayBag(E[] contents) { bag = Arrays.copyOf(contents, contents.length); size = contents.length; } /** * Adds a new entry to this bag. * @param newEntry The object to be added as a new entry. * @return True. */ @Override public boolean add(E newEntry) { if (isArrayFull()) { doubleCapacity(); } bag[size] = newEntry; size++; return true; } /** * Retrieves all entries that are in this bag. * @return A newly allocated array of all the entries in this bag. */ @Override public E[] toArray() { @SuppressWarnings("unchecked") E[] result = (E[])new Object[size]; // Unchecked cast for (int index = 0; index < size; index++) { result[index] = bag[index]; } return result; } /** * Sees whether this bag is empty. * @return True if this bag is empty, or false if not. */ @Override public boolean isEmpty() { return size == 0; } /** * Gets the current number of entries in this bag. * @return The integer number of entries currently in this bag. */ @Override public int getCurrentSize() { return size; } /** * Counts the number of times a given entry appears in this bag. * @param anEntry The entry to be counted. * @return The number of times anEntry appears in this bag. */ @Override public int getFrequencyOf(E anEntry) { int counter = 0; for (int index = 0; index < size; index++) { if (anEntry != null && anEntry.equals(bag[index])) { counter++; } } return counter; } /** * Tests whether this bag contains a given entry. * @param anEntry The entry to locate. * @return True if this bag contains anEntry, or false otherwise. */ @Override public boolean contains(E anEntry) { return getIndexOf(anEntry) > -1; // or >= 0 } /** * Removes all entries from this bag. */ @Override public void clear() { while (!isEmpty()) { remove(); } } /** * Removes one unspecified entry from this bag, if possible. * @return Either the removed entry, if the removal was successful, or * null. */ @Override public E remove() { E result = removeEntry(size - 1); return result; } /** * Removes one occurrence of a given entry from this bag, if possible. * @param anEntry The entry to be removed. * @return True if the removal was successful, or false if not. */ @Override public boolean remove(E anEntry) { int index = getIndexOf(anEntry); E result = removeEntry(index); return anEntry != null && anEntry.equals(result); } // Locates a given entry within the array bag. // Returns the index of the entry, if located, // or -1 otherwise. private int getIndexOf(E anEntry) { int where = -1; boolean found = false; int index = 0; while (!found && (index < size)) { if (anEntry != null && anEntry.equals(bag[index])) { found = true; where = index; } index++; } // Assertion: If where > -1, anEntry is in the array bag, and it // equals bag[where]; otherwise, anEntry is not in the array. return where; } // Removes and returns the entry at a given index within the array. // If no such entry exists, returns null. // Precondition: 0 <= givenIndex < size. private E removeEntry(int givenIndex) { E result = null; if (!isEmpty() && (givenIndex >= 0)) { // Entry to remove result = bag[givenIndex]; int lastIndex = size - 1; // Replace entry to remove with last entry bag[givenIndex] = bag[lastIndex]; // Remove reference to last entry bag[lastIndex] = null; size--; } return result; } // Returns true if the array bag is full, or false if not. private boolean isArrayFull() { return size >= bag.length; } // Doubles the size of the array bag. private void doubleCapacity() { int newLength = 2 * bag.length; bag = Arrays.copyOf(bag, newLength); } /** * Override the toString() method so that we get a more useful display of * the contents in the bag. * @return a string representation of the contents of the bag */ @Override public String toString() { StringBuilder result = new StringBuilder("Bag[ "); for (int index = 0; index < size; index++) { result.append(bag[index].toString()); result.append(' '); } result.append(']'); return result.toString(); } /** * Determines if two bags are equal. * @param other Another object to check this bag against. * @return True if other is an ArrayBag containing the same objects, with * the same frequencies, as this bag. */ @Override public boolean equals(Object other) { // TODO: Rewrite this method so that it works according to the contents // of the bags (this and other). Be sure to consider if other is null, // or a type other than ArrayBag. return this == other; } }