IN JAVA: Implement the following methods in LinkedBag.java public BagInterface<T
ID: 3744590 • Letter: I
Question
IN JAVA:
Implement the following methods in LinkedBag.java
public BagInterface<T> union(BagInterface<T> anotherBag)
public BagInterface<T> intersection(BagInterface<T> anotherBag)
public BagInterface<T> difference(BagInterface<T> anotherBag)
public T replace(T replacement)
public boolean equals(Object otherBag)
---------------------------------------------------------------
/**
A class of bags whose entries are stored in a chain of linked nodes.
The bag is never full.
@author Frank M. Carrano
@author Timothy M. Henry
@version 4.1
*/
public final class LinkedBag<T> implements BagInterface<T>
{
private Node firstNode; // Reference to first node
private int numberOfEntries;
public LinkedBag()
{
firstNode = null;
numberOfEntries = 0;
} // end default constructor
/** Sees whether this bag is empty.
@return True if this bag is empty, or false if not. */
public boolean isEmpty()
{
return numberOfEntries == 0;
} // end isEmpty
/** Gets the number of entries currently in this bag.
@return The integer number of entries currently in this bag. */
public int getCurrentSize()
{
return numberOfEntries;
} // end getCurrentSize
/** 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, or false if not. */
public boolean add(T newEntry) // OutOfMemoryError possible
{
// Add to beginning of chain:
Node newNode = new Node(newEntry);
newNode.next = firstNode; // Make new node reference rest of chain
// (firstNode is null if chain is empty)
firstNode = newNode; // New node is at beginning of chain
numberOfEntries++;
return true;
} // end add
/** Retrieves all entries that are in this bag.
@return A newly allocated array of all the entries in this bag. */
public Object[] toArray()
{
// The cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
T[] result = (T[])new Object[numberOfEntries]; // Unchecked cast
int index = 0;
Node currentNode = firstNode;
while ((index < numberOfEntries) && (currentNode != null))
{
result[index] = currentNode.data;
index++;
currentNode = currentNode.next;
} // end while
return result;
} // end toArray
/** 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(T anEntry)
{
int frequency = 0;
int counter = 0;
Node currentNode = firstNode;
while ((counter < numberOfEntries) && (currentNode != null))
{
if (anEntry.equals(currentNode.data))
{
frequency++;
} // end if
counter++;
currentNode = currentNode.next;
} // end while
return frequency;
} // end getFrequencyOf
/** Tests whether this bag contains a given entry.
@param anEntry The entry to locate.
@return True if the bag contains anEntry, or false otherwise. */
public boolean contains(T anEntry)
{
boolean found = false;
Node currentNode = firstNode;
while (!found && (currentNode != null))
{
if (anEntry.equals(currentNode.data))
found = true;
else
currentNode = currentNode.next;
} // end while
return found;
} // end contains
// Locates a given entry within this bag.
// Returns a reference to the node containing the entry, if located,
// or null otherwise.
private Node getReferenceTo(T anEntry)
{
boolean found = false;
Node currentNode = firstNode;
while (!found && (currentNode != null))
{
if (anEntry.equals(currentNode.data))
found = true;
else
currentNode = currentNode.next;
} // end while
return currentNode;
} // end getReferenceTo
/** Removes all entries from this bag. */
public void clear()
{
while (!isEmpty())
remove();
} // end clear
/** Removes one unspecified entry from this bag, if possible.
@return Either the removed entry, if the removal
was successful, or null. */
public T remove()
{
T result = null;
if (firstNode != null)
{
result = firstNode.data;
firstNode = firstNode.next; // Remove first node from chain
numberOfEntries--;
} // end if
return result;
} // end 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 otherwise. */
public boolean remove(T anEntry)
{
boolean result = false;
Node nodeN = getReferenceTo(anEntry);
if (nodeN != null)
{
nodeN.data = firstNode.data; // Replace located entry with entry in first node
firstNode = firstNode.next; // Remove first node
numberOfEntries--;
result = true;
} // end if
return result;
} // end remove
private class Node
{
private T data; // Entry in bag
private Node next; // Link to next node
private Node(T dataPortion)
{
this(dataPortion, null);
} // end constructor
private Node(T dataPortion, Node nextNode)
{
data = dataPortion;
next = nextNode;
} // end constructor
} // end Node
} // end LinkedBag
-----------------------------------------------------
package edu.iastate.cs228.hw02;
/**
An interface that describes the operations of a bag of objects.
@author Frank M. Carrano
@author Timothy M. Henry
@version 4.0
*/
public interface BagInterface<T> {
/** Gets the current number of entries in this bag.
@return The integer number of entries currently in the bag. */
public int getCurrentSize();
/** Sees whether this bag is empty.
@return True if the 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, or false if not. */
public boolean add(T newEntry);
/** Removes one unspecified entry from this bag, if possible.
@return Either the removed entry, if the removal.
was successful, or null. */
public T remove();
/** Removes one occurrence of a given entry from this bag.
@param anEntry The entry to be removed.
@return True if the removal was successful, or false if not. */
public boolean remove(T 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 the bag. */
public int getFrequencyOf(T anEntry);
/** Tests whether this bag contains a given entry.
@param anEntry The entry to locate.
@return True if the bag contains anEntry, or false if not. */
public boolean contains(T anEntry);
/** Retrieves all entries that are in this bag.
@return A newly allocated array of all the entries in the bag.
Note: If the bag is empty, the returned array is empty. */
public Object[] toArray();
/** Creates a new bag that combines the contents of this bag and anotherBag.
@param anotherBag The bag that is to be added.
@return A combined bag. */
public BagInterface<T> union(BagInterface<T> anotherBag);
/** Creates a new bag that contains those objects that occur
in both this bag and anotherBag.
@param anotherBag The bag that is to be compared.
@return A combined bag. */
public BagInterface<T> intersection(BagInterface<T> anotherBag);
/** Creates a new bag of objects that would be left in this bag
after removing those that also occur in anotherBag.
@param anotherBag The bag that is to be removed.
@return A combined bag. */
public BagInterface<T> difference(BagInterface<T> anotherBag);
/**
Replaces an unspecified entry in this bag with a given object.
@param replacement The given object
@return The original entry in the bag that was replaced or null if bag was empty.
*/
public T replace(T replacement);
/**
Removes every occurrence of a given entry from this bag.
@param anEntry The entry to be removed.
*/
public void removeEvery(T anEntry);
} // end BagInterface
Explanation / Answer
Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts. Thanks
// LinkedBag.java
/**
* A class of bags whose entries are stored in a chain of linked nodes.
*
* The bag is never full.
*
* @author Frank M. Carrano
* @author Timothy M. Henry
* @version 4.1
*/
public final class LinkedBag<T> implements BagInterface<T>
{
private Node firstNode; // Reference to first node
private int numberOfEntries;
public LinkedBag()
{
firstNode = null;
numberOfEntries = 0;
} // end default constructor
/**
* Sees whether this bag is empty.
*
* @return True if this bag is empty, or false if not.
*/
public boolean isEmpty()
{
return numberOfEntries == 0;
} // end isEmpty
/**
* Gets the number of entries currently in this bag.
*
* @return The integer number of entries currently in this bag.
*/
public int getCurrentSize()
{
return numberOfEntries;
} // end getCurrentSize
/**
* 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, or false if not.
*/
public boolean add(T newEntry) // OutOfMemoryError possible
{
// Add to beginning of chain:
Node newNode = new Node(newEntry);
newNode.next = firstNode; // Make new node reference rest of chain
// (firstNode is null if chain is empty)
firstNode = newNode; // New node is at beginning of chain
numberOfEntries++;
return true;
} // end add
/**
* Retrieves all entries that are in this bag.
*
* @return A newly allocated array of all the entries in this bag.
*/
public Object[] toArray()
{
// The cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
T[] result = (T[]) new Object[numberOfEntries]; // Unchecked cast
int index = 0;
Node currentNode = firstNode;
while ((index < numberOfEntries) && (currentNode != null))
{
result[index] = currentNode.data;
index++;
currentNode = currentNode.next;
} // end while
return result;
} // end toArray
/**
* 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(T anEntry)
{
int frequency = 0;
int counter = 0;
Node currentNode = firstNode;
while ((counter < numberOfEntries) && (currentNode != null))
{
if (anEntry.equals(currentNode.data))
{
frequency++;
} // end if
counter++;
currentNode = currentNode.next;
} // end while
return frequency;
} // end getFrequencyOf
/**
* Tests whether this bag contains a given entry.
*
* @param anEntry
* The entry to locate.
* @return True if the bag contains anEntry, or false otherwise.
*/
public boolean contains(T anEntry)
{
boolean found = false;
Node currentNode = firstNode;
while (!found && (currentNode != null))
{
if (anEntry.equals(currentNode.data))
found = true;
else
currentNode = currentNode.next;
} // end while
return found;
} // end contains
// Locates a given entry within this bag.
// Returns a reference to the node containing the entry, if located,
// or null otherwise.
private Node getReferenceTo(T anEntry)
{
boolean found = false;
Node currentNode = firstNode;
while (!found && (currentNode != null))
{
if (anEntry.equals(currentNode.data))
found = true;
else
currentNode = currentNode.next;
} // end while
return currentNode;
} // end getReferenceTo
/** Removes all entries from this bag. */
public void clear()
{
while (!isEmpty())
remove();
} // end clear
/**
* Removes one unspecified entry from this bag, if possible.
*
* @return Either the removed entry, if the removal
*
* was successful, or null.
*/
public T remove()
{
T result = null;
if (firstNode != null)
{
result = firstNode.data;
firstNode = firstNode.next; // Remove first node from chain
numberOfEntries--;
} // end if
return result;
} // end 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 otherwise.
*/
public boolean remove(T anEntry)
{
boolean result = false;
Node nodeN = getReferenceTo(anEntry);
if (nodeN != null)
{
nodeN.data = firstNode.data; // Replace located entry with entry in
// first node
firstNode = firstNode.next; // Remove first node
numberOfEntries--;
result = true;
} // end if
return result;
} // end remove
private class Node
{
private T data; // Entry in bag
private Node next; // Link to next node
private Node(T dataPortion)
{
this(dataPortion, null);
} // end constructor
private Node(T dataPortion, Node nextNode)
{
data = dataPortion;
next = nextNode;
} // end constructor
} // end Node
@Override
public BagInterface<T> union(BagInterface<T> anotherBag) {
// creating a new bag
BagInterface<T> newBag = new LinkedBag<T>();
// getting contents of this bag
Object[] bagAcontents = toArray();
// getting contents of other bag
Object[] bagBcontents = anotherBag.toArray();
// adding both contents to new bag
for (Object ob : bagAcontents) {
newBag.add((T) ob);
}
for (Object ob : bagBcontents) {
newBag.add((T) ob);
}
return newBag;
}
@Override
public BagInterface<T> intersection(BagInterface<T> anotherBag) {
BagInterface<T> newBag = new LinkedBag<T>();
// getting contents of this bag
Object[] bagAcontents = toArray();
for (Object ob : bagAcontents) {
T item = (T) ob;
// adding item to new bag if it is present in other bag
if (anotherBag.contains(item)) {
newBag.add(item);
}
}
return newBag;
}
@Override
public BagInterface<T> difference(BagInterface<T> anotherBag) {
BagInterface<T> newBag = new LinkedBag<T>();
// getting contents of this bag
Object[] bagAcontents = toArray();
for (Object ob : bagAcontents) {
T item = (T) ob;
// adding item to new bag if it is NOT present in other bag
if (!anotherBag.contains(item)) {
newBag.add(item);
}
}
return newBag;
}
@Override
public T replace(T replacement) {
// replacing the first node's data
if (firstNode != null) {
T dataReplaced = firstNode.data;
firstNode.data = replacement;
return dataReplaced;
}
// bag is empty
return null;
}
@Override
public void removeEvery(T anEntry) {
// looping until all occurrences of anEntry is removed
while (contains(anEntry)) {
remove(anEntry);
}
}
@Override
public boolean equals(Object ob) {
if (ob instanceof LinkedBag) {
LinkedBag<T> otherBag = (LinkedBag<T>) ob;
/**
* two bags are equal if they have same number of elements & their
* intersection has same number of elements as they have
*/
if (this.getCurrentSize() == otherBag.getCurrentSize()
&& this.intersection(otherBag).getCurrentSize() == this
.getCurrentSize()) {
return true;
}
}
return false;
}
} // end LinkedBag
// Test.java (to test new methods)
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
//creating two linked bags
LinkedBag<Integer> bag1 = new LinkedBag<Integer>();
LinkedBag<Integer> bag2 = new LinkedBag<Integer>();
// adding numbers between 1 to 10 into bag1
for (int i = 1; i <= 10; i++) {
bag1.add(i);
}
// adding numbers between 5 to 15 into bag2
for (int i = 5; i <= 15; i++) {
bag2.add(i);
}
//demonstrating newly added operations
System.out.println("Bag1: " + Arrays.toString(bag1.toArray()));
System.out.println("Bag2: " + Arrays.toString(bag2.toArray()));
System.out.println("Bag1 union Bag2: "
+ Arrays.toString(bag1.union(bag2).toArray()));
System.out.println("Bag1 intersection Bag2: "
+ Arrays.toString(bag1.intersection(bag2).toArray()));
System.out.println("Bag1 difference Bag2: "
+ Arrays.toString(bag1.difference(bag2).toArray()));
System.out.println("Adding three occurrences of 99 to bag1");
bag1.add(99);
bag1.add(99);
bag1.add(99);
System.out.println("Bag1: " + Arrays.toString(bag1.toArray()));
System.out.println("Removing all occurrences of 99 from bag1");
bag1.removeEvery(99);
System.out.println("Bag1: " + Arrays.toString(bag1.toArray()));
System.out.println("Bag1 == Bag2: "+bag1.equals(bag2));
}
}
/*OUTPUT*/
Bag1: [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
Bag2: [15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5]
Bag1 union Bag2: [5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Bag1 intersection Bag2: [5, 6, 7, 8, 9, 10]
Bag1 difference Bag2: [1, 2, 3, 4]
Adding three occurrences of 99 to bag1
Bag1: [99, 99, 99, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
Removing all occurrences of 99 from bag1
Bag1: [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
Bag1 == Bag2: false