Define and implement the following methods for the LinkedBag class. A private so
ID: 3902503 • Letter: D
Question
Define and implement the following methods for the LinkedBag class.
A private sort method that will sort the contents of the bag in ascending order
A method replace that replaces and returns any object currently in a bag with a given object. Header of this method is as follows: public T replace(T replacement)
A method removeEntry that removes all occurrences of a given entry from a bag. Header of this method is as follows: public void removeEntry(T anEntry)
An equals method (by overriding Object class's method) that returns true when the contents of two bags are the same. Note that two equal bags contain the same number of entries, and each entry occurs in each bag the same number of times. The order of the entries in each array is irrelevant.
The LinkedBag class and its interface BagInterface are below
/**
* An interface that describes the operations of a bag of objects.
*/
public interface BagInterface
{
/**
* 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 T[] toArray();
/**
* The union of two collections consists of their contents combined into a new collection.
* @param otherBag: The other bag that is to have its contents combined with this bag.
* @return A new bag the contains the combined contents of this bag and the other bag.
*/
public BagInterface union(BagInterface otherBag);
/**
* A new collection of the entries that occur in both collections (the overlapping entries).
* @param otherBag: The other bag is to have its contents compared to this bag.
* @return A new bag containing the overlapping entries of this bag and the other bag.
*/
public BagInterface intersection(BagInterface otherBag);
/**
* A new collection of the entries that would be left in one collection after removing
* the overlapping entries.
* @param otherBag: The other bag that is to have its contents compared to this bag.
* @return A new bag containing the contents that are left in this new bag after removing the
* duplicates that occur in this bag and the other bag.
*/
public BagInterface difference(BagInterface 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 T[] 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
public BagInterface<T> union(BagInterface<T> anotherBag)
{
LinkedBag<T> result = new LinkedBag<T>();
//add from current bag, all items
Node n = firstNode;
while(n != null)
{
result.add(n.data);
n = n.next;
}
T[] other = anotherBag.toArray();
for(int i = 0; i < other.length; i++)
{
result.add(other[i]);
}
return result;
}
public BagInterface<T> intersection(BagInterface<T> anotherBag)
{
LinkedBag<T> result = new LinkedBag<T>();
T[] other = anotherBag.toArray();
for(int i = 0; i < other.length; i++)
{
if(result.contains(other[i])) //already result contains this item processed
continue;
int f1 = getFrequencyOf(other[i]);
int f2 = anotherBag.getFrequencyOf(other[i]);
int common;
if(f1 < f2)
common = f1;
else
common = f2;
for(int j = 1; j <= common; j++)
result.add(other[i]);
}
return result;
}
public BagInterface<T> difference(BagInterface<T> anotherBag)
{
LinkedBag<T> result = new LinkedBag<T>();
Node n = firstNode;
while(n != null)
{
if(!result.contains(n.data)) //if not already processed
{
int f1 = getFrequencyOf(n.data);
int f2 = anotherBag.getFrequencyOf(n.data);
int diff = f1 - f2;
for(int j = 1; j <= diff; j++)
result.add(n.data);
}
n = n.next;
}
return result;
}
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
Explanation / Answer
I have implemented the sort(), removeEntry(), equals() methods.
I need more clarification on replace(). Does replace() method replace all elements in the bag with the given replacement? What needs to be written if there are more than one objects in the bag? Can you please tell me the exact requirement for replace. Should it search for a particular element in the bag and replace it or randomly replace some element?
/**
*
* 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 extends Comparable<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 T[] 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
public BagInterface<T> union(BagInterface<T> anotherBag) {
LinkedBag<T> result = new LinkedBag<T>();
// add from current bag, all items
Node n = firstNode;
while (n != null) {
result.add(n.data);
n = n.next;
}
T[] other = anotherBag.toArray();
for (int i = 0; i < other.length; i++) {
result.add(other[i]);
}
return result;
}
public BagInterface<T> intersection(BagInterface<T> anotherBag) {
LinkedBag<T> result = new LinkedBag<T>();
T[] other = anotherBag.toArray();
for (int i = 0; i < other.length; i++) {
if (result.contains(other[i])) // already result contains this item
// processed
continue;
int f1 = getFrequencyOf(other[i]);
int f2 = anotherBag.getFrequencyOf(other[i]);
int common;
if (f1 < f2)
common = f1;
else
common = f2;
for (int j = 1; j <= common; j++)
result.add(other[i]);
}
return result;
}
public BagInterface<T> difference(BagInterface<T> anotherBag) {
LinkedBag<T> result = new LinkedBag<T>();
Node n = firstNode;
while (n != null) {
if (!result.contains(n.data)) // if not already processed
{
int f1 = getFrequencyOf(n.data);
int f2 = anotherBag.getFrequencyOf(n.data);
int diff = f1 - f2;
for (int j = 1; j <= diff; j++)
result.add(n.data);
}
n = n.next;
}
return result;
}
public void sort()
{
Node i, j;
for(i = firstNode; i != null; i= i.next)
{
Node min = i;
for(j = i.next; j != null; j = j.next)
{
if(j.data.compareTo(min.data) < 0)
min = j;
}
if(i != min)
{
T temp = i.data;
i.data = min.data;
min.data = temp;
}
}
}
public void removeEntry(T anEntry)
{
while(contains(anEntry))
remove(anEntry);
}
@Override
public boolean equals(Object obj) {
if(obj instanceof BagInterface)
{
Node n = firstNode;
BagInterface other = (BagInterface) obj;
while(n != null)
{
if(getFrequencyOf(n.data) != other.getFrequencyOf(n.data))
return false;
n = n.next;
}
return true;
}
return false;
}
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
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.